The Dichotomy Between Pattern Recognition and Step-by-Step Reasoning

Amrut Nadgir; Pratik Chaudhari; Vijay Balasubramanian

cs.LGOct 6, 2026

The Dichotomy Between Pattern Recognition and Step-by-Step Reasoning

Authors: Amrut Nadgir, Pratik Chaudhari, Vijay Balasubramanian

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 $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.

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

c

and

V

. Left: The minimum number of start-to-answer paths required to cover every edge in the DAG

P_{\text{min}}

shrinks relative to the total number of paths

P_{\text{tot}}

as the number of nodes grows. Right: The minimum length of paths to cover every edge

L_{\text{cover}}

shrinks relative to the longest path

L_{\text{max}}

. Details: DAGs were created with

S=5

start nodes,

N=10

answer nodes. Dotted curves denote an average over random orderings for nodes in the DAG. Solid curves correspond to using a particular ordering

\pi^{*}

in the proof of Thms. 1 and 2 . We computed

P_{\text{min}}

using a min-flow problem and

L_{\text{cover}}

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

\pi

, 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

c

and

V

, and trained transformers on start-to-answer paths from 5 replicate DAGs for each configuration (random

\pi

, 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

1/P_{\text{tot}}

>

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 (

\sim x^{0.61}

for the blue curve and

\sim x^{0.91}

for the green curve). Right: The length of reasoning traces in the training data scales linearly in

L_{\text{max}}

and is smaller than

L_{\text{max}}

. The gap between

L_{\text{train}}

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

s=4,8,16

; 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

s

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

k=\infty

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,

k=1

was trained on only 24,536 samples. In both left and right panels, without perturbation, using a small emission interval

k=1

is optimal. With perturbation, the trend flips and the

k=\infty

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

c/L_{i,c}

where

c

is the memory size,

L_{i,c}

is the generated length of reasoning on problem

i

for memory size

c

. All memory fractions, indexed by

(i,c)

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

$V$	$c$	$S$	$N$
8	2	5	8
10	2	6	10
12	2	8	12
8	3	10	20
10	3	12	24
11	3	14	28

Appendix

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

Appendix

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

g_{c}=0.35

and the four physical rows by

1-g_{c}=0.65

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%

Appendix

Table 3: Distribution of the

14{,}261

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

76.2\%

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).

Explore similar work

Dec 16, 2025cs.CL

Step-Tagging: Toward controlling the generation of Language Reasoning Models through step monitoring

The field of Language Reasoning Models (LRMs) has been very active over the past few years with advances in training and inference techniques enabling LRMs to reason longer, and more accurately. However, a growing body of studies show that LRMs are still inefficient, over-generating verification and reflection steps. To address this challenge, we introduce the Step-Tagging framework, a lightweight sentence-classifier enabling real-time annotation of the type of reasoning steps that an LRM is generating. To monitor reasoning behaviors, we introduced ReasonType: a novel taxonomy of reasoning steps. Building on this framework, we demonstrated that online monitoring of the count of specific steps can produce effective interpretable early stopping criteria of LRM inferences. We evaluate the Step-tagging framework on three open-source reasoning models across standard benchmark datasets: MATH500, GSM8K, AIME and non-mathematical tasks (GPQA and MMLU-Pro). We achieve 20 to 50% token reduction while maintaining comparable accuracy to standard generation, with largest gains observed on more computation-heavy tasks. This work offers a novel way to increase control over the generation of LRMs, and a new tool to study behaviors of LRMs.

Yannis Belkhiter, Seshu Tirupathi, Giulio Zizzo +1

1IBM Research Europe, Dublin, Ireland · 2Trinity College Dublin, Ireland · 3ADAPT Research Centre, Dublin, Ireland

Large Reasoning Models Progressive Reasoning Tagging Natural Language Inference Stance

Ask PDF

Sep 30, 2026cs.IT

Interpreting Reasoning of Large Language Models via Partial Information Decomposition

Large reasoning models (LRMs) have achieved substantial improvements in solving complex mathematical problems, but often produce lengthy, repetitive, or erroneous reasoning trajectories. In this work, we introduce a new interpretability framework, SLIDER, to evaluate the quality of the reasoning process. SLIDER leverages an emerging body of work from information theory called Partial Information Decomposition to disentangle the information about the final answer between two consecutive reasoning steps into non-negative components: unique information (in preceding steps or current step), redundant information, and synergistic information. Building on this decomposition, we propose the Step-wise Repetitive Reasoning Index (Step-RRI), a theoretically grounded measure that assesses whether the answer-relevant information in the current step

S_i

is predominantly redundant with the past steps

S_{<i}

, relative to its unique and synergistic contributions. To evaluate the effectiveness of Step-RRI in detecting repetitiveness, we apply SLIDER to the redundancy class of the PRMBench dataset where Step-RRI improves step-level redundancy identification accuracy by over

10

points compared to embedding-similarity and information-gain baselines. Next, we define Trajectory-RRI, an aggregate measure of repetitiveness for an individual reasoning trajectory. To demonstrate its practical relevance, we show that average Trajectory-RRI strongly correlates with actual reasoning length across QwQ-32B, DeepSeek-R1-Distill-Qwen-32B, and GPT-4.1, motivating its use as a signal for improving reasoning efficiency. Finally, we introduce Trajectory-RRI-guided data selection for fine-tuning, demonstrating that selecting training data based on Trajectory-RRI can improve a fine-tuned model's reasoning efficiency while largely preserving its task performance.

Barproda Halder, Qiuyi Zhang, Sanghamitra Dutta

University of Maryland, College Park · Elorian AI

Large Reasoning Models Reasoning Trajectory Reasoning Errors Interpretability

Ask PDF

Date pendingcs.CL

ReasoningFlow: Discourse Structures for Understanding LLM Reasoning Traces

Large reasoning models (LRMs) produce reasoning traces with non-linear structures, such as backtracking and self-correction, that complicate the evaluation and monitoring of the reasoning process. We introduce ReasoningFlow, a framework that captures the discourse structures of LRM reasoning traces into fine-grained directed acyclic graphs (DAGs). We develop and validate our annotation schema through careful manual annotation of 31 traces (2.1k steps), achieving high inter-annotator agreement, then scale to automatic annotation of 1,260 traces (247.7k steps) spanning three tasks (math, science, argumentation) and five models (Qwen2.5-32B-Inst, QwQ-32B, DeepSeek-V3, DeepSeek-R1, GPT-oss-120B). By analyzing ReasoningFlow graphs, we find: (1) LRMs exhibit structurally similar traces, despite being trained from different base models and potentially non-overlapping post-training data. (2) ReasoningFlow reveals diverse fine-grained reasoning behaviors (e.g., local verification, self-reflection, and assumptions) that can be used for better reasoning trace monitorability. (3) In LRMs, most of the erroneous steps are not used to derive final answers. (4) Mechanistic causal dependencies between steps do not reflect the language-level discourse structure. We release the dataset and code in: https://github.com/jinulee-v/reasoningflow.

Jinu Lee, Shivam Agarwal, Amruta Parulekar +3

The Grainger College of Engineering University of Illinois Urbana-Champaign

Reasoning Traces LLM Reasoning Strategies Large Reasoning Models Reasoning Graphs Discourse Annotations

Ask PDF