The Dichotomy Between Pattern Recognition and Step-by-Step Reasoning
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. 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 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. 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.
Related
- Machine Learning Meets High-Energy Nuclear Physics: From Pattern Recognition to Physics-Integrated Discovery
- Hybrid pattern recognition for charged particle tracking: Hough transform and convolutional neural efficiency networks
- Role of chirality in the polarizer-filter dichotomy in nonmagnetic junctions
- Odd-even dichotomy in the waveforms of modified Emden oscillators of arbitrary integer power
- A Dichotomy for MIP* in the Presence of Unital Noise
BibTeX
@misc{nadgir2026dichotomy,
title = {{The Dichotomy Between Pattern Recognition and Step-by-Step Reasoning}},
author = {Amrut Nadgir and Vijay Balasubramanian and Pratik Chaudhari},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.09186},
eprint = {2610.09186},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.09186},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - The Dichotomy Between Pattern Recognition and Step-by-Step Reasoning
AU - Amrut Nadgir
AU - Vijay Balasubramanian
AU - Pratik Chaudhari
PY - 2026
DA - 2026/10/17
PB - arXiv
DO - 10.48550/arxiv.2610.09186
UR - https://arxiv.org/abs/2610.09186
AB - 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. 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 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. 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.
ER -