cs.LGOct 6, 2026
SaveThe Dichotomy Between Pattern Recognition and Step-by-Step Reasoning
Organizations: University of Pennsylvania
Abstract
We argue that pattern recognition and step-by-step reasoning are two ends of a spectrum. A large language model (LLM) learns to reason step-by-step when data is structured such that the next token depends on a small amount of preceding context. Inference in LLMs resembles pattern recognition when the next token depends on a large amount of preceding context. If the next token depends on only the most recent tokens, reasoning traces are paths on a De Bruijn graph whose nodes are -length contexts and edges are next-token transitions between contexts. The set of reasoning traces of a task forms a directed acyclic subgraph of the De Bruijn graph. An LLM that has learned all edges of this subgraph can compose them to solve longer, unseen tasks, i.e., it reasons step-by-step. We prove that the number of edges is vanishingly small compared to the number of reasoning traces. Empirically, the number of training samples a transformer needs is a power law in the number of edges, so learning to reason step-by-step is sample efficient. We can induce De Bruijn structure in any task by maintaining a ``state'' that makes future reasoning independent of the past. The frequency of states in the reasoning trace determines . We show, by fine-tuning Qwen2.5-1.5B-Instruct to solve equations and answer questions about stories, that frequent states (small ) result in higher accuracy but greater fragility to perturbations at test time. LLMs trained with a large are only as good as models that perform pattern recognition without reasoning. A moderate density of states balances accuracy and robustness. We show that real-world data has De Bruijn structure: Qwen3-14B and Qwen3-32B retain over 75% of their accuracy on GSM8K, MATH-500 and GPQA-Diamond when attention is restricted to a sliding window less than 15% as long as the full reasoning trace.
Figures & tables
Figure 1: De Bruijn graph: Edges (both bold and gray) show transitions from one 4-gram to another by appending a token. Bold edges form a directed acyclic subgraph (DAG). Green and orange shaded nodes are start and answer nodes in the DAG respectively. Each path corresponds to a reasoning trace.
Figure 2: Data with De Bruijn structure can be learned with few, short traces . We created a synthetic dataset of De Bruijn graphs and DAGs for different values of and . Left: The minimum number of start-to-answer paths required to cover every edge in the DAG shrinks relative to the total number of paths as the number of nodes grows. Right: The minimum length of paths to cover every edge shrinks relative to the longest path . Details: DAGs were created with start nodes, answer nodes. Dotted curves denote an average over random orderings for nodes in the DAG. Solid curves correspond to using a particular ordering in the proof of Thms. 1 and 2 . We computed using a min-flow problem and as the maximum over edges for the length of the shortest path from any start node to any answer node containing that edge. For random , curves show the mean ratio over random orderings and its standard error over ten DAGs (too small to see).
Figure 3: Transformers can learn paths on a De Bruijn DAG with few and short samples . We created a synthetic dataset of De Bruijn graphs and DAGs for different values of and , and trained transformers on start-to-answer paths from 5 replicate DAGs for each configuration (random , error bars are standard error). The green curve indicates the sample complexity (left) or the length of reasoning traces in the training data (right) required for achieving 95% path coverage, i.e., when the trained transformer assigns probability greater than 10% of the probability under the uniform distribution to 95% of paths. The blue curve corresponds to the situation where the trained transformer assigns a probability smaller than 5% to invalid next-tokens that do not lie on valid reasoning paths in the DAG. Left: The number of training samples required to reproduce paths of the DAG scales as a power law in the number of edges ( for the blue curve and for the green curve). Right: The length of reasoning traces in the training data scales linearly in and is smaller than . The gap between and the longest covered path grows with DAG size. Details in App. B .
Figure 4: Sample complexity of learning remapped reasoning traces . Connected line segments correspond to remapping with block lengths ; there are 10 different DAGs drawn on this plot. Dashed lines indicate the fit obtained in Fig. 3 for the original reasoning traces. Smaller values of have a larger number of edges and sample complexity. Learning on remapped traces follows a similar power-law trend as seen in Fig. 3 .
Figure 7: Reasoning with more frequent state emissions results in greater accuracy with fewer samples, but such reasoning is less robust to external perturbations. Left: Accuracy of the final answer for different emission intervals and perturbation probabilities on a held-out test set. A different model was trained for each state-emission interval. Each model was trained on 50,000 samples. Right: Accuracy when models are trained with a fixed number of tokens is nearly identical to when models are trained with a fixed number of samples (left). Configurations corresponding to and those with no reasoning get 50,000 training samples, while smaller state-emission intervals get fewer samples because their reasoning traces contain more tokens per sample. For example, was trained on only 24,536 samples. In both left and right panels, without perturbation, using a small emission interval is optimal. With perturbation, the trend flips and the condition is optimal. Error-bars are standard error of the mean over three replicate experiments with different sets of train and test samples. They are mostly too small to see in the plot. Details in App. D .
Figure 8: Frequent state emissions result in faithful, step-by-step reasoning instead of pattern recognition. Left: For all perturbation probabilities, correctness of the intermediate sequence of reasoning steps (the “derivation accuracy”) decays as the state-emission interval grows. When we compare to the trends in final-answer accuracy shown in Fig. 7 , we see that models with large state-emission intervals tend to get the correct answer with incorrect derivations when their reasoning is perturbed. Right: Given that a model makes a mistake in a state prediction, future predictions can either “drift” or “recover”. A model drifts when its current state is correct conditioned on the recent past context (up to the previous state) but incorrect given the entire past sequence of operations (ignoring previous states). This means it propagated an error from a previous state. It recovers if the opposite is true, i.e., when it corrects a mistake in a previous incorrect state. As the emission interval increases, it is more likely for a state prediction to recover than drift into further incorrect states. Both curves add to one. Error-bars are standard error over three replicate experiments with different sets of train and test samples. They are mostly too small to see in the plot. All models were trained on 50,000 samples. Details in App. D
Figure 11: Qwen3-14B and Qwen3-32B perform quite well on reasoning benchmarks like GSM8K, MATH-500 and GPQA-Diamond in spite of attending only to the prompt and a few recent few tokens (denoted as “memory size”) during inference. Left: With a memory size of only 70, 400 and 900 tokens on GSM8K, MATH-500 and GPQA-Diamond respectively, Qwen3-14B reaches 75% of its full-context accuracy. Qwen3-32B reaches the same percentage of its full-context accuracy with equal or smaller memory (40, 400 and 600 tokens). As a control, we evaluated Qwen3-14B on these benchmarks while only attending to the prompt and a random subset of past reasoning tokens of the same sizes (70, 400 and 900 tokens). It reached only 0%, 2% and 27% of its full-context accuracy. The third GPQA-Diamond result corresponds to an absolute accuracy of 0.161, below the chance level of 0.25. Middle: These memory sizes are a small fraction of the length of correct reasoning. For both models the length of correct reasoning exceeds 992, 4027 and 6054 tokens for GSM8K, MATH-500 and GPQA-Diamond respectively (incorrect reasoning is longer). Right: Accuracy as a function of memory fraction where is the memory size, is the generated length of reasoning on problem for memory size . All memory fractions, indexed by pairs, are quantile-binned into ten equal-count bins per model and benchmark. The x-value of each point is the median memory fraction across a bin and the y-value is the mean accuracy across that bin. Both LLMs achieve good accuracy at only 15% memory fraction. Error bars in the plots denote standard error over 192 problems per benchmark. Details in App. E
Appendix figures & tables4 assets
Supplementary material from the paper’s appendix.
Appendix
| 8 | 2 | 5 | 8 |
| 10 | 2 | 6 | 10 |
| 12 | 2 | 8 | 12 |
| 8 | 3 | 10 | 20 |
| 10 | 3 | 12 | 24 |
| 11 | 3 | 14 | 28 |
Table 1: The parameters for the De Bruijn DAGs in the experiment.
| Action | Templated sentence | Prob. |
| Enter room | {P} entered the {R}. | 0.170 |
| Leave room | {P} left the {R}. | 0.085 |
| Move to container | {P} moved the {O} to the {C}, which is also located in the {R}. | 0.255 |
| Move to room | {P} moved the {O} to the {R}, leaving the {C} in its original location. | 0.170 |
| Tell privately (topic) | {P1} told privately to {P2} about the {T}. | 0.092 |
| Tell privately (location) | {P1} told privately to {P2} that the {O} is in the {C}. | 0.137 |
Table 2: The seven action types, the exact sentence template each emits, and the probability with which each is proposed at every step. Placeholders: {P}, {P1}, {P2} are persons, {O} an object, {C} a container, {R} a room, and {T} a topic. Probabilities follow from unnormalized base weights (2,1,3,2,2,3,2), with the three communication rows scaled by and the four physical rows by before normalizing. A witnessed action additionally emits “While this action was happening, {P} witnessed this action in secret (and only this action).”
| Question type | Share | False-belief share |
| Knowledge, second-order | 55.9% | 34.9% |
| Knowledge, first-order | 18.7% | 0.0% |
| Room location, second-order | 11.8% | 34.3% |
| Container location, second-order | 8.4% | 53.7% |
| Container location, first-order | 5.1% | 33.3% |
| All | 100.0% | 29.8% |
Table 3: Distribution of the generated questions by type, with the fraction of each type that is a false-belief question (the queried belief differs from the truth). Second-order questions constitute of the corpus.
Figure 12: The ignored and replaced accuracies show similar trends as the derivation accuracy in Fig. 8 (left). They do not explain the discrepancy between the final-answer accuracy in Fig. 7 and the derivation accuracy in Fig. 8 (left).