View a PDF of the paper titled The Dichotomy Between Pattern Recognition and Step-by-Step Reasoning, by Amrut Nadgir and Vijay Balasubramanian and Pratik Chaudhari
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 $c$ most recent tokens, reasoning traces are paths on a de Bruijn graph whose nodes are $c$-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. We also prove and show empirically that the number of training samples a transformer needs is a linear 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 $c$. We show, by fine-tuning Qwen2.5-1.5B-Instruct to solve equations and answer questions about stories, that frequent states (small $c$) result in higher accuracy but greater fragility to perturbations at test time. LLMs trained with a large $c$ are only as good as models that perform pattern recognition without reasoning. A moderate density of states balances accuracy and robustness. 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.
Submission history
From: Amrut Nadgir [view email]
[v1]
Tue, 6 Oct 2026 22:36:42 UTC (527 KB)
[v2]
Sat, 17 Oct 2026 20:14:13 UTC (527 KB)
[v3]
Thu, 19 Nov 2026 16:59:46 UTC (574 KB)
![[2610.09186] The Dichotomy Between Pattern Recognition and Step-by-Step Reasoning [2610.09186] The Dichotomy Between Pattern Recognition and Step-by-Step Reasoning](https://techwavedispatch.com/wp-content/uploads/2026/11/261009186-The-Dichotomy-Between-Pattern-Recognition-and-Step-by-Step-Reasoning-1024x597.png)