- 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
- 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.
- 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.
- 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
-
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 . In particular, Equation (1) shows that for some ordering , while 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.
-
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 , 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 , 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.
-
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
-
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?
-
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.
-
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 to an effective context length substantially more convincing.
4 comments
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 , 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.
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 Pmin, the minimum number of paths required to cover every edge in the de Bruijn DAG, relative to Ptot, 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ϵ, 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−ϵ of paths. The result is simple, Pϵ≤\absE/ϵ where \absE 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 in terms of the vocabulary size V and the context size c. This value is much smaller than the total number of paths Ptot.
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.01 (the uncertainty on the exponent is small, ±0.05). This is close to the upper bound from the new Theorem 1 which gives 20\absE. Furthermore, transformers can achieve a proportion 0.95 of path coverage despite the training data only consisting of as small as a fraction 10−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/Ptot 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−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.