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.