TLDR: This research paper investigates whether the length of intermediate tokens, often called Chain of Thought (CoT), generated by language models correlates with the actual difficulty of a problem. By training transformer models on A* search algorithm traces for maze-solving, the authors found that CoT length often does not reflect problem complexity, especially for out-of-distribution problems. The study suggests that apparent correlations are more likely due to approximate recall from training data rather than genuine problem-adaptive computation, cautioning against anthropomorphizing these “thinking” tokens.
In the rapidly evolving world of artificial intelligence, particularly with the rise of large language models (LLMs), a common assumption has emerged regarding how these models “think.” When an AI generates a sequence of intermediate tokens—often referred to as a Chain of Thought (CoT) or reasoning trace—before providing a final answer, it’s frequently interpreted as the model engaging in deeper, problem-adaptive computation. The longer the trace, the more “thought” is presumed to have gone into solving a complex problem.
However, a recent research paper titled “PERFORMATIVETHINKING? THEBRITTLECORRELATION BETWEENCOT LENGTH ANDPROBLEMCOMPLEXITY” challenges this prevailing notion. Authored by Vardhan Palod, Kaya Stechly, Karthik Valmeekam, and Subbarao Kambhampati, this study critically examines whether the length of these intermediate token sequences truly reflects or correlates with the inherent difficulty of a problem. You can read the full paper here: https://arxiv.org/pdf/2509.07339.
Unpacking AI’s Reasoning Process
To investigate this, the researchers adopted a controlled approach. They trained transformer models from scratch on derivational traces of the A* search algorithm, a well-known pathfinding algorithm. This method allowed them to precisely and verifiably measure problem complexity by counting the number of operations A* required to solve a maze. The study focused on a standard grid-based pathfinding domain, using 30×30 grids where an agent had to find a path from a start to a goal cell, avoiding walls.
The mazes used for training were generated using Wilson’s algorithm, with additional evaluations conducted on mazes created by various other algorithms like Kruskal, Depth-First Search (DFS), Drunkard’s Walk, and Searchformer-style generation, as well as simple “free-space” problems with no obstacles.
Surprising Findings on “Thinking” Length
The results of the study revealed several key insights that challenge the intuitive link between CoT length and problem difficulty:
- Excessive Length for Simple Tasks: Even for the simplest “free-space” problems (mazes with no obstacles), the models often produced excessively long reasoning traces. Strikingly, in many cases, they failed to generate a valid solution at all, sometimes continuing to produce tokens up to the maximum context limit without success. This indicated a very weak correlation between the model’s intermediate token length and the actual A* trace length required for these trivial problems.
- Loose Correlation Across Diverse Mazes: When evaluated on problems generated by different maze algorithms, the core finding persisted. The length of the intermediate traces remained largely disconnected from the actual problem complexity, showing only a very loose correlation with the ground-truth A* trace lengths.
- In-Distribution vs. Out-of-Distribution Performance: The researchers observed a noticeable difference when comparing in-distribution problems (similar to the training data) with out-of-distribution problems. For Wilson-generated mazes (the training distribution), there was some visible alignment between intermediate token lengths and ground-truth trace lengths. However, this correlation vanished entirely when the model was tested on structurally distinct distributions, such as Searchformer-style mazes.
Also Read:
- Just-in-Time Learning: Task Representations in Language Models
- Enhancing Language Model Reasoning with Dynamic Confidence Assessment
Implications for AI Interpretation
These findings suggest that the apparent problem-adaptive computation observed in some cases is not evidence of genuine “thinking” or problem-sensitive computation. Instead, it appears to be largely a result of approximate recall from the training distribution. As the problems become more dissimilar to what the model was trained on, the correlation between trace length and problem complexity disappears.
The research cautions against anthropomorphizing intermediate reasoning tokens and interpreting longer sequences as automatically indicative of “thinking effort” or deeper computation. It implies that the inherent computational complexity of a problem instance is not the primary factor determining the length of an AI’s reasoning trace; rather, the distributional distance of that instance from the training data plays a more significant role.
This work has important implications for how we understand and evaluate large reasoning models. It suggests that methods aiming to improve efficiency by reducing reasoning-chain length might be based on a flawed premise if they assume a direct link between trace length and computational effort. The study highlights the need for more rigorous methodologies when interpreting the internal processes of transformer-based reasoning models, moving beyond simple assumptions about “thinking time.”
