acceptodds
Under review as a conference paper at ICLR 2027

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

Primary area:
foundation or frontier models, including LLMs
Keywords:
chain of thought, reasoning, thinking, step by step, pattern matching, inference

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_DUdUOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes a De Bruijn-graph perspective on the relationship between pattern recognition and step-by-step reasoning in autoregressive language models. It argues that when valid next-token predictions depend only on a short recent context, reasoning traces can be represented as paths in a directed acyclic subgraph of a De Bruijn graph, allowing a model to compose learned local transitions into longer unseen traces. The paper provides combinatorial results comparing the number and length of paths needed to cover all edges of particular De Bruijn DAGs, synthetic transformer experiments, controlled fine-tuning experiments on equation solving and synthetic story reasoning with explicit state emissions, and sliding-window attention evaluations of Qwen3 models on GSM8K, MATH-500, and GPQA-Diamond.

Critical strengths
  1. The paper advances a useful and clearly articulated structural framing. Figure 1 makes the central compression argument intuitive: a large prefix tree of possible traces may be represented by a much smaller transition graph when local contexts recur. This is a productive lens for thinking about why intermediate states, scratchpads, and state summaries can improve compositional generalization.
  2. The synthetic experiments are thoughtfully designed to probe the mechanism rather than merely report a scaling curve. Figure 3 relates empirical training requirements to the number of graph edges and evaluates extrapolation to paths longer than those used in training. Figure 4 is a particularly helpful control: position-dependent token remapping preserves the underlying graph structure while removing its explicit token-local form, and the observed increase in sample complexity supports the narrower claim that transformers exploit explicitly available local transition structure.
  3. The perturbation findings are interesting and potentially important. Figure 8 distinguishes final-answer accuracy from derivation accuracy and shows that frequent state emissions produce more locally faithful derivations but greater propagation of state errors. This is a real empirical tension worth understanding, rather than an unqualified claim that more explicit state always helps.
Critical weaknesses
  1. The formal results do not establish the paper’s stated sample-complexity claim for transformers. Theorems 1 and 2 on Page 3 are combinatorial existence statements about a specially constructed family DπD_\pi. In particular, Equation (1) shows that for some ordering π\pi, Pmin⁡≤∣E∣P_{\min}\leq |E| while PtotP_{\mathrm{tot}} can be much larger; Equation (2) gives a short edge-covering path bound relative to one long path. These are useful properties of the graph family, but they do not yield a statistical sample-complexity result for learning a next-token conditional distribution, let alone for learning it with a transformer trained by SGD.

  2. The evaluation criterion in Figure 3 is not a direct test that the model learned all edges or compositionally generalizes over the DAG. The green criterion calls a path “covered” if the model gives it probability greater than 0.1/Ptot0.1/P_{\mathrm{tot}}, and the blue criterion asks that invalid next tokens receive probability below 5%. Neither condition directly measures edge recovery, exact support recovery, or likelihood under the uniform distribution over valid paths. For very large PtotP_{\mathrm{tot}}, the path-probability threshold can be extremely small. It is therefore possible for a model to satisfy the criterion while assigning highly nonuniform probabilities across valid traces or while failing on rare transitions.

  3. The breadth of the headline claims exceeds the empirical coverage. The title and abstract propose a “dichotomy” or spectrum between pattern recognition and step-by-step reasoning in LLMs generally. The empirical evidence instead covers one constructed graph family, one small transformer architecture, LoRA fine-tuning of one 1.5B model on two synthetic tasks, and two Qwen3 models under a single decoding configuration on 192 sampled instances per benchmark. This is a promising package of evidence, but it does not support universal statements about why reasoning emerges in LLMs or about the general equivalence between large context dependence and pattern recognition.

Questions for authors
  1. Theorems 1 and 2 are existential statements about a family of DAG orderings. Can the authors state precisely which empirical conclusion follows from these theorems alone, and which conclusions require assumptions about training distribution, model capacity, optimization, and error accumulation? In particular, can they avoid describing the theorems themselves as a transformer sample-complexity result?

  2. For Figure 3, are evaluation paths guaranteed not to have occurred in training? What fraction of evaluation paths are exact training duplicates for each graph configuration? Please report edge-level recovery metrics, valid-path likelihood or KL divergence relative to the target path distribution, and generalization to deliberately held-out compositions of otherwise observed edges.

  3. Can the authors empirically verify their key conditional-independence premise for the equation task? For example, after conditioning on the latest emitted state, how much predictive information remains in the earlier chain of thought or the original prompt? This would make the mapping from state-emission interval kk to an effective context length cc substantially more convincing.

4 comments
AuthorsOpenReview ↗

Part 1 of the response

We appreciate the review and are glad you found that our paper advances a useful and clearly articulated structural framing. We will address your comments below.

> The results are an existence statements. They do not establish the paper’s stated sample-complexity claim for transformers…

Our theorems bounded PminP_{\text{min}}, the minimum number of paths required to cover every edge in the de Bruijn DAG, relative to PtotP_{\text{tot}}, the total number of paths in the DAG. This is not a typical sample-complexity result. Thanks for raising this point. Based on your suggestion, we have now managed to obtain a new result that shows a sample-complexity bound on learning a de Bruijn DAG (described below). This bound has strong agreement with our empirical experiment on transformers. And it substantially strengthens our paper.

Our new Theorem 1 bounds PϵP_{\epsilon}, which is the expected number of samples (samples are drawn uniformly at random) required to have learned all the edges in a fraction larger than 1−ϵ1-\epsilon of paths. The result is simple, Pϵ≤\absE/ϵP_{\epsilon} \leq \abs{E}/\epsilon where \absE\abs{E} is the number of edges in the de Bruijn DAG. The new Theorem 2 contains the same result as the previous Theorem 1 and bounds the number of edges in the de Bruijn DAG \absE\abs{E} in terms of the vocabulary size VV and the context size cc. This value is much smaller than the total number of paths PtotP_{\text{tot}}.

Our results using transformers in Figure 3 corroborate these theorems. The sample-complexity of learning a fraction 0.95 of the total number of paths in the DAG is linear in the number of edges with a fitted curve of 7.1\absE1.017.1 \abs{E}^{1.01} (the uncertainty on the exponent is small, ±0.05\pm 0.05). This is close to the upper bound from the new Theorem 1 which gives 20\absE20 \abs{E}. Furthermore, transformers can achieve a proportion 0.95 of path coverage despite the training data only consisting of as small as a fraction 10−1110^{-11} of all paths in the DAG.

> The evaluation criteria in Figure 3 is not a direct test that the model learned all edges or compositionally generalizes over the DAG … What fraction of paths are exact training duplicates for each graph configuration?

Actually, our goal is not to check whether a model has learned all the edges. We are interested in studying whether or not the model has learned all the paths in the DAG using few samples relative to the total number of paths. If a model can do this, that means it must have acquired some ability to compose its learned edges to form new, unseen sequences. We included a new result that tests if the model can compose its learned edges, described next.

We say that a model has “learned” a set of sequences if it assigns those sequences a joint probability close to their true underlying probability in the data and assigns zero probability to sequences outside that set. This is a very reasonable definition of what it means to learn the elements of a set. The evaluation criteria in Figure 3 directly follow from this definition. The path coverage criterion states that a path is learned if the model assigns it a probability larger than one-tenth of its true probability under the uniform distribution. The invalid tokens criterion states that a model should not assign probability greater than 0.05 to any tokens that are not a valid continuation of the trace. It is true that the probability threshold for path coverage, 0.1/Ptot0.1/P_{\text{tot}} can be quite small. That is why the comparisons are done using sums of log-probabilities. If this value was so small that even an untrained model assigns non-trivial probabilities to paths in the DAG, then we wouldn’t have the clean scaling result from Figure 3 (left) that the number of samples required to achieve path coverage scales linearly with the number of edges in the de Bruijn DAG.

We study the number of samples required for the model to achieve both criteria. Our new result in Figure 3 (middle) shows that the number of samples is a tiny fraction of the total number of paths, in some cases as small as 10−1110^{-11}. The fact that the model assigns non-trivial probability to over 95% of all the paths in the DAG despite only having seen such a small fraction of the paths means that it has learned to compose its learned edges to form new sequences.

AuthorsOpenReview ↗

Part 2 of the response

>... The empirical evidence instead covers one graph family, … but it does not support universal statements about why reasoning emerges in LLMs or about the general equivalence between large context dependence and pattern recognition.

First, to clarify, our paper does not make any claims regarding how current training paradigms cause reasoning to emerge LLMs. This is an interesting question but it is not the topic of our paper.

Second, in practice, all reasoning traces have a finite length. Any set of finite-length reasoning traces are paths on a de Bruijn DAG. So de Bruijn DAG is not a "model" or a specific graph family that we are studying in this paper. It is a literal description of the reasoning traces. Unstructured reasoning traces will have a large context dependence cc, and structured ones will have a small context dependence. Thus, our theorems and results in transformers on synthetic data hold for any set of reasoning traces. To test that claim, we performed additional experiments in LLMs where we searched for this structure in their reasoning traces. We also curated training data to elicit the entire spectrum of inference mechanisms between pattern recognition and step-by-step reasoning in Qwen2.5-1.5B. Our theory accurately predicted the results at these larger scales as well.

> Can the authors state precisely which empirical conclusion follows from these theorems alone

With our updated results, Theorem 1 directly predicts the linear scaling of sample-complexity with respect to edges in the de Bruijn DAG that is seen in Figure 3 (left). Theorem 2 states that the number of edges will be much smaller than the total number of paths. Theorem 2, combined with the sample-complexity result from Theorem 1 predicts Figure 3 (middle), which shows that the amount of training data an LLM requires to learn most reasoning paths is a small fraction of the total number of paths. Finally, Theorem 3 predicts the length generalization result from Figure 3 (right). At the larger scale, Theorems 1 and 2 suggest that the 1.5B parameter Qwen model should be more accurate with fewer samples when fine-tuned on reasoning traces that have de Bruijn structure, which is what we observe in Figure 7 (left, middle). Theorem 3 indicates that models which reason with de Bruijn should have more stable accuracy across problem lengths, which we observe in the new Figure 7 (right).

> Can the authors verify their key conditional-independence premise for the equation task?

In our updated manuscript, we included a new experiment in Figure 8 (right) which addresses this comment. We gave models a correct reasoning trace for a task, up to a randomly chosen state. We measured the accuracy of the model completions of the trace when (i) it was given the correct next state ("own state'') and (ii) it was given a next state from a different problem ("other problem's state'') which requires the same number of operations to simplify as the correct state. Accuracy, in this case, measures how often the model correctly simplified the recently inserted state, not whether or not it correctly solved the initial prompt. Models with smaller state-emission intervals correctly adapt their answer to the new problem's state. Their accuracy in case (ii) is similar to that of case (i). Those with larger state-emission intervals do not adapt as well and therefore have a much higher accuracy in case (i).

This experiment provides added evidence to our drift/recovery plot in Figure 8 (middle) indicating that, when state-emissions are frequent, the reasoning continuations depend mostly on the most recent state and not as much on the earlier tokens.

Thanks for the new theorem and the state-swap experiment; both strengthen the paper. My main concern is that the edge-coverage bound still doesn’t tell us how many training examples a Transformer needs to learn the paths in Figure 3, therefore I maintain my original score.

Deriving exact sample complexity bounds for transformers is an important question but beyond the scope of this paper. No one has managed to derive a result like this, by explicitly modeling the structure in the data like we seek to do in our paper, up to our knowledge. We would like to note that our result predicts the linear scaling of sample-complexity of transformers with edges in the de Bruijn DAG. Furthermore, our results hold for any autoregressive learner which is capable of learning the de Bruijn structure in sequences.

Reviewer_ukY6OpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The authors argue that step-by-step reasoning and pattern recognition in LLM inference are two aspects of the same phenomena, and that reasoning traces specifically display a particular directed acyclic graph structure. This is because as they state that the reasoning steps depend on a small amount of context preceding the step, while pattern recognition takes / requires a large amount of context.

They show that models fine tuned using De Bruijn structured reasoning traces out perform those trained on less formally structured reasoning traces, who are no better than pure pattern recognition.

Critical strengths

They authors show that  the reasoning traces do exhibit this De Bruijn structure, and that looking at how much of the training data contains traces of this type will indicate how much a model uses pattern recognition vs step wise reasoning.

The analysis of real world data showing that it contained the desired structure was interesting, and I wonder if the framing around what data ought a reasoning corpus contain and how to measure it might be a strong helpful framing for the paper?

Critical weaknesses

The focus on De Bruijn type reasoning traces feels like it could be well motivated, but leads me to wonder if there is a simpler explanation that needs disproving. Are non De Bruijn traces simply bad examples of reasoning? There are plenty of complex reasoning tasks that require combining a large portion of context from many threads (programming and mathmatical tasks immediately come to mind) It would be very instructive if the authors could also provide some examples of the kind of prompts that fall into these two categories? And to quantify this it would be very interesting to provide traces that to a human reader clearly show the same contextual information but to the LLM do not have this same DAG structure. In this case would we expect to see a significant difference in task performance?

The formatting of the paper feels quite difficult to read, the figure placements and caption size in combination with many bold heading sections that do not follow the typical numbered section style expected from an ICLR paper. It makes it feel like the authors were trying very hard to hit the page limit, and I suggest perhaps some more concise explanations rather than compressing the text to benefit legibility?

Questions for authors

The structure of the paper was fairly hard to follow, could the authors please reformat it into a more typical arrangement?

The claim that reasoning traces ought to have this pattern is interesting, but the analysis feels limited in scope. Is this something that applies specifically to more rigid domains that operate in this step-wise manner, or would this apply to more general reasoning tasks? Naively I would expect those to have quite a different structure to the mathematical / QA ones, so it would be interesting to see if the 15% reasoning trace claim survives in those settings?

In a similar way, I would be interested to know how general task performance degrades as the model context is limited to a sliding 15%, a 25% reduction in accuracy on benchmarks is significant.

3 comments
AuthorsOpenReview ↗

Part 1 of the response

We appreciate the comments and are glad you thought our analysis showing de Bruijn structure in real world data was interesting. We address your comments below.

> … leads me to wonder if there is a simpler explanation that needs disproving. Are non-de Bruijn traces simply bad examples of reasoning?

All sets of finite-length reasoning traces can be described by a de Bruijn DAG. If the reasoning traces have no de Bruijn structure, the length of the context dependence cc is simply equal to the length of the entire trace---so the de Bruijn structure is trivial in this case. Our choice to analyze reasoning token sequences using de Bruijn DAGs is not just a modeling choice or an explanation, it is instead a literal description of these traces.

We show that, if an LLM is trained on reasoning traces with greater amounts of de Bruijn structure (smaller context dependence), it learns to reason step-by-step. It learns a set of transitions between local contexts or, equivalently, intermediate states, and it can compose these transitions in new ways to make longer chains. If an LLM is trained on reasoning traces with little de Bruijn structure, the number of these local transitions is too large to learn, so the model defaults to pattern recognition. We show that these two inference mechanisms are merely two extreme ends of a spectrum. Where on this spectrum an LLM lies is controlled by the amount of de Bruijn structure in its reasoning.

When the traces have more de Bruijn structure, models are more accurate on a well-defined task but are less robust to perturbations in the text. There is a trade-off here. When the task is ambiguous, robustness is important so it is better to reason with less de Bruijn structure. When the task is well-defined, accuracy is important so it is better to reason with more de Bruijn structure. What constitutes a “good” or “bad” structure in reasoning traces depends on the task. Effective reasoning traces have some intermediate amount of de Bruijn structure that is suitable for the task. Some reasoning steps might depend on only the local context while others might use pattern recognition.

> … There are plenty of complex reasoning tasks that require combining a large portion of context from many threads …

This is a very interesting point. We think of this as follows. Even when sub-agents are spawned across threads, each of them operates sequentially upon its own context. And equally importantly, the main agent operates upon the results produced by these sub-agents sequentially by ingesting them into the context. So the attention-based transformer always runs on the context sequentially, even if the context may be populated by sub-agents.

Our construction of the de Bruijn graph applies to to all reasoning traces, including these situations that you have described. In the case of multiple threads, the main agent reasons based on the results provided by the sub-agents, perhaps with a larger context cc to handle ambiguity in the task or the results (more robustness). The sub-agents are generally given more straightforward or algorithmic tasks, and should therefore produce reasoning traces with more local structure, i.e., a smaller cc.

In fact, if one reads the reasoning traces of LLMs, we see that they often handle this complex context dependency using several techniques that organize the dependencies in such a way that they become local. LLMs will often restate or reread relevant information for a problem so that it stays in its local context. They can also maintain an external memory document that remains a part of its local context. This document can contain pointers to important pieces of information that it reproduces in its local context as needed. In effect, LLMs perhaps due to reinforcement learning on such agentic reasoning traces, are learning to improve the de Bruijn structure---and thereby improve the accuracy on the task.

Thank you for this comment. We have incorporated this response in the narrative (see lines 504-515).

AuthorsOpenReview ↗

Part 2 of the response

> It would be interesting to provide traces that to a human reader clearly show the same contextual information but to the LLM do not have this same DAG structure.

Our experiments in the equation-solving task and the story question-answer task provide good examples of such traces. We study several different kinds of reasoning traces which contain the same semantic meaning to a human reader. For example, in the equation-solving task, we consider reasoning traces that contain the same exact steps as each other except that some contain more states than others. Both are understood in the same way by a human reader. In addition, in the story question-answer task, we study several kinds of reasoning, including one which describes the local change to the object after each step of the story rather than tracking the state. These reasoning traces carry the same meaning to a human reader. And, among these kinds of reasoning, only the stateful traces have de Bruijn structure. This is because statefulness induces de Bruijn structure in reasoning traces by decoupling future predictions from past reasoning. And reasoning traces with de Bruijn structure are by definition stateful (the recent cc tokens are the state).

In our experiments, we find that training on reasoning traces with more de Bruijn structure leads to significantly higher accuracy and less robustness to perturbations in the text. Traces that are semantically equivalent to the stateful traces but do not have de Bruijn structure have much lower accuracy but higher robustness.

>The claim that reasoning traces ought to have this pattern is interesting … Is this something that applies specifically to more rigid domains, or would this apply to more general reasoning tasks?

We do not make the claim that reasoning step-by-step is better than pattern recognition. Our experiments show that both strategies have their pros and cons. Step-by-step reasoning is more accurate but brittle to changes in the chain of thought. Pattern recognition is more robust to these changes and is therefore likely to perform better in more ambiguous cases. LLMs are versatile problem-solvers precisely because they can mix both strategies and do not need to rely on one or the other. For example, they can use pattern recognition to execute reasoning steps with long-range dependencies followed by using step-by-step reasoning to draw a direct deduction from the previous step.

This trade-off applies to any set of token sequences and, therefore, to any domain. In some domains, it may be preferable to use pattern recognition while in others step-by-step reasoning might be preferred. We do experiments on GSM8K and MATH-500 which are well-defined math benchmarks, as well as on GPQA-Diamond which is a more general scientific reasoning benchmark. In both cases, Qwen3 models could correctly continue its reasoning while attending to only a small fraction of its past reasoning.

Roughly speaking, we believe that when there is global structure in the reasoning traces, LLMs can exploit it using pattern matching. And more local structure (like successive steps) is readily exploited using step-by-step reasoning. We will include this sentence in the Discussion (see lines 500-503).

> I would be interested to know how general task performance degrades as the model context is limited to a sliding 15%, a 25% reduction in accuracy on benchmarks is significant.

We would like to clarify that limiting the LLM context to 15% of its window did not cause a 25% reduction in benchmark accuracy. The LLM reached greater than 75% of its full-context accuracy in spite of this limitation. So perhaps you mean to say that the relative change in the accuracy was 25%.

The goal of our paper is to understand when models reason step-by-step and when they fall back to pattern recognition. Our evaluations of LLMs on benchmark tasks illustrate that current LLMs can reason with some de Bruijn structure despite not having been explicitly trained to do so. The goal of this experiment is not to evaluate whether sliding window attention is a useful technique for implementing reasoning in LLMs. Aghajohari et al. already do this in their paper “The Markovian Thinker: Architecture-Agnostic Linear Scaling of Reasoning”, which we cite. They show that LLMs that are trained to discard their earlier context when solving long-context tasks do remarkably well on these tasks.

AuthorsOpenReview ↗

About the formatting

>The structure of the paper was fairly hard to follow…numbered section of the ICLR style

We appreciate this point. This is a slightly non-traditional paper because it does not propose a "method". It instead discusses different types of analyses and each section digs into the central question of the paper with a different perspective. The figures contain a number of important technical insights, and we have also made all figures self-contained in order to help the reader follow the paper at a high level. That is why the captions are slightly longer. Other than a couple of wrapfigures to save space, the paper is quite conventional in how it is typeset. We will be very happy to make any changes if you have specific suggestions.

We have now modified the structure of the paper to have section 1 that acts an "Introduction", section 2 that contains "Results" which each sub-section containing one set of results, and a section 3 that contains the "Related Works and Discussion". We hope that this will make the paper easier to follow.

Reviewer_ETVMOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

Through theoretical analysis based on De Bruijn graphs and empirical experiments, this manuscript demonstrate that step-by-step reasoning of LLMs can achieve efficient generalization by learning and composing local state-transition rules. While maintaining intermediate states frequently enhances both reasoning accuracy and sample efficiency, it simultaneously reduces the model's robustness against perturbations in the reasoning process.

Critical strengths
  1. Explaining why NTP can give rise to composable, long-chain reasoning is a problem of theoretical value.
  2. Use a De Bruijn DAG as the structural representation for reasoning, and yield favorable experimental results.
Critical weaknesses
  1. The general assumption regarding De Bruijn DAGs does not hold, as the existence of finite-length reasoning traces does not guarantee that a De Bruijn graph (constructed by merging identical contexts) to be acyclic. I suggest that the authors clarify that all proofs are based on the properties of a specific and specially constructed class of De Bruijn DAGs.
  2. ‌Experiments on the frequency of state outputs cannot directly prove that the model switches between two different reasoning mechanisms. Varying k does not merely alter the length of context dependency, it also changes the density of explicit intermediate-state supervision within the training objective.
Questions for authors

‌See Weaknesses.

2 comments
AuthorsOpenReview ↗

Reasoning traces with de Bruijn structure are automatically stateful, and vice versa.

Thank you for the feedback. We are glad you think the paper is clear and addresses a problem of value. We included a response to your comment below.

>the existence of finite length reasoning traces does not guarantee that a de Bruijn graph … to be acyclic

No. All reasoning traces have a finite length in practice. Any set of finite length reasoning traces can be represented by a sub-DAG of a de Bruijn graph. Due to this fact, the graph representation of these finite-length reasoning traces must be acyclic.

>Varying k does not merely alter the length of context dependency, it also changes the density of explicit intermediate-state supervision within the training objective.

The reviewer suggests that the primary variable driving our results might be the density of states and not de Bruijn structure. However, observe that the two are actually equivalent to one another. A “state” is any sequence of tokens which contains the information necessary to predict future continuations. By definition, any token sequence which decouples past reasoning from the future is a state, i.e., an LLM can predict valid next tokens despite only attending to reasoning tokens after the most recent state emission. Therefore, in any reasoning trace with De Bruijn structure, the past cc tokens at any step contains a legitimate state. In other words, any reasoning trace that is stateful automatically has de Bruijn structure. And any reasoning trace with de Bruijn structure is automatically stateful (the past cc tokens are the state). Thank you for bringing this up. We have modified the narrative in the paper (see lines 86-90; 256-263) to describe this argument.

In our experiments, we induce de Bruijn structure (reduce the length of context dependency) in a model’s reasoning traces by varying the frequency at which it emits intermediate states during its reasoning. We show that, when a model is trained on stateful reasoning traces, it conditions its next-token predictions on primarily the recent context after the most recent state-emission. This indicates it has learned the de Bruijn structure induced by the state-emissions in the reasoning.

To handle other potential hidden confounding variables, we showed consistent results between two very different kinds of tasks (equation-solving and story question-answer). In the latter case, we tried many different kinds of reasoning including one which only tracks key sentences from the story, as well as a length-control which restates every step in the story without tracking a state variable. The stateful reasoning trace, which automatically has de Bruijn structure, is the most accurate. The other conditions, which do not have any de Bruijn structure, do no better than direct prediction.

Thanks to the authors for the clarification, which have addressed my concerns. So I raise my score to 3.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.