- Rating
- 3(+1)
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper uses the harmonic basis of the de Bruijn graph Laplacian to understand sequential biases in LLMs.
- Given a vocabulary , the de Bruijn graph contains vertices that corresponds to all possible contexts for a given context length and its edges correspond to appending the next token.
- The authors use an existing closed form expression for the harmonic basis of the de Bruijn graph Laplacian and project the stationary distribution onto this basis.
- The authors apply this framework to analyse LLM strategies in Rock-Paper-Scissors and sequential biases in binary sequence generation. They also provide a preliminary extension to part-of-speech sequences from open-ended generation.
Overall, this is an interesting use of harmonic analysis of de Bruijn graphs to understand phenomena in LLMs. It would be helpful to clarify the following:
- What additional insight do the individual harmonic coordinates provide over simpler sequence statistics or alternative bases?
- How can the framework be applied to larger vocabularies and longer graph contexts beyond the controlled settings studied here?
Critical strengths
- Presentation and setup: This is an interesting application of de Bruijn graphs to understanding learned sequential biases in LLMs, supported by an experimental setup that is well motivated. This can motivate further research in similar directions to develop mathematical tools for understanding different aspects of LLMs.
- Novelty: The mathematical analysis in the paper is strong and presented in a clear and intuitive manner. Given that harmonic analysis of autoregressive models is relatively new in the literature, the paper also offers an accessible introduction to the topic.
Critical weaknesses
The framework's scalability to longer contexts remains unclear. Moreover, the incremental utility of the harmonic basis over simpler observables is not clearly established. While the application of harmonic analysis to this setting is impressive, the above concerns raise questions about the framework's utility and its added value over existing approaches to analysing LLM behaviour.
The presentation is clear and intuitive on the mathematical side, but can benefit from more focus on the experiments and exploring the coefficients in more detail. Section 4 could be trimmed by moving the supporting Taylor expansion and toy numerical verification to the appendix, leading to a more elaborate experiments section in the main text.
Questions for authors
- It would be helpful to have more clarity on the applicability of this framework to models at scale and to more involved experimental settings with larger vocabularies and longer contexts. Are there approximation schemes that make this approach scalable for longer contexts?
- How do errors in estimating the transition matrix propagate to the stationary distribution and the observed coefficients ?
- Appendix E.4 establishes that can be computed without constructing the harmonic basis, and the paper identifies the individual coordinates as its added value. Can you demonstrate what those coordinates reveal beyond simpler sequence statistics or alternative bases, for example through a comparison with other summary statistics on de Bruijn graphs?
4 comments
3. Added Interpretation from Individual Harmonic Coordinates
Can you demonstrate what those coordinates reveal beyond simpler sequence statistics or alternative bases?
We thank the reviewer for this question allowing us to state more clearly the benefits of using harmonic spectrum. In the nutshell, our framework answers a different question from inspecting one conditional logit or a handful of sampled strings: what long-run distribution over contexts do the local generation rules induce, and which recurring patterns account for it? We compute the stationary context distribution and decompose its departure from uniform into a fixed family of signed, graph-derived coordinates. This lets us analyze the previously studied binary-generation biases (Bigelow et al.) and mixed-strategy behavior (West and Potts) with the same construction, rather than introducing unrelated task-specific summaries. Our perturbation theorem further explains how centered conditional logits drive the first-order stationary response through a Poisson equation.
For example, in the added Figure 1 provided in the revision of our paper, we consider a model conditioned on its last two binary symbols, with logit differences in context order at . The logits show that the conditional probability of choosing after is 95.3%. They do not by themselves report how frequently the generated process visits or repeats; those are global consequences of transitions across all four contexts. Solving for stationarity gives
(\widehat\gamma_1,\widehat\gamma_2,\widehat\gamma_3) \approx(-0.4380,0,0.2572).$$ Here 68.8% of contexts are $11$, despite the 95.3% conditional preference following $11$. The coordinates resolve the stationary distribution into signed, interpretable contrasts: $$\widehat\gamma_1=\frac{\pi_{00}-\pi_{11}}{\sqrt2},\qquad \widehat\gamma_2=\frac{\pi_{10}-\pi_{01}}{\sqrt2},\qquad \widehat\gamma_3=\Pr(\mathrm{repeat})-\frac12.$$ Thus the first measures $00$ versus $11$ occupancy, the second $10$ versus $01$, and the third repetition relative to uniform generation; here $\Pr(\mathrm{repeat})\approx75.7\%$. The aggregate $\widehat\Gamma=\sum_i\widehat\gamma_i^2=\|\pi-\pi_{\mathrm{unif}}\|_2^2\approx0.258$ measures total departure from uniform but loses the signs and identities of the contributing patterns. For instance, swapping the labels $0$ and $1$ reverses $\widehat\gamma_1$ while leaving $\widehat\Gamma$ and the repetition rate unchanged. This illustrates what the coordinates make directly readable: not just that behavior departs from uniform, but which structured contrasts contribute and in what direction. A few sampled strings can suggest these behaviors; the decomposition puts them in a common coordinate system for comparing models, conditions, and tasks. We have added Figure 1 and a dedicated paragraph in the end of Section 4 to provide these details. Does this example clarify what the individual coordinates reveal beyond the aggregate $\widehat\Gamma$, or is there a particular alternative basis or sequence statistic you would find useful as a comparison?As the discussion period draws to its end, we would like to kindly ask the reviewer to let us know if we can provide any further details to incorporate their feedback into our revision.
Thank you for addressing the weaknesses raised here. After going through the response to all the reviewers, I have raised my rating to 3 (weak acceptance).
We thank the reviewer for recognizing the strength and clarity of the mathematical analysis and the motivation of the experimental setup. We first address applicability beyond the binary and RPS settings.
1. Open-Ended Generation and Larger Alphabets
As the reviewer notes, the appendix includes "Feasibility Extension: Open-Ended Generation via Part-of-Speech Sequences." We would like to emphasize the concrete route this experiment demonstrates: the model generates unrestricted prose, and the analysis maps that text to a linguistically meaningful alphabet rather than enumerating its full tokenizer vocabulary. Using 12 Universal POS tags at graph order k=3 gives 122=144 context states, extending the analysis beyond the two- and three-symbol tasks.
The experiment analyzes Qwen2.5-0.5B-Instruct articles across rotating topics at temperatures 0.7, 1.0, and 1.3, with approximately 15,000 tags per temperature, alongside 35,401 tags from the Brown corpus. Both generated and reference text use the same tagger. Each sequence is compared with a shuffled version that preserves its unigram tag frequencies while destroying its ordering. The reported excess harmonic mass over this control is 0.098, 0.086, and 0.082 for the three temperatures, respectively, and 0.121 for the reference text. These descriptive results demonstrate sensitivity to sequential linguistic structure beyond tag frequencies in ordinary generated text.
This experiment establishes feasibility on a larger linguistic alphabet without constraining the model's output to that alphabet. Structure-preserving graph coarsening is another natural future direction, but would need to control how aggregation changes the stationary distribution and the interpretation of the modes.
2. Transition-Estimation Error and Harmonic Coefficients
This propagation can be stated directly. Let PT be the row-stochastic transition matrix, PT an estimated row-stochastic matrix, and let πT and πT be their stationary column vectors. Define
\qquad \kappa_T=\|Z_T\|_2.$$ The stationary equations imply the perturbation identity $$\widehat\pi_T-\pi_T =Z_T(\widehat P_T^\top-P_T^\top)\widehat\pi_T, \qquad \|\widehat\pi_T-\pi_T\|_2 \leq \kappa_T\|\widehat P_T-P_T\|_2.$$ Thus transition error is amplified according to the stationary sensitivity of the chain, which can be large when mixing is slow; for a nonreversible chain, $\kappa_T$ captures this sensitivity without assuming that it is summarized by the spectral gap alone. Since each harmonic mode $x_i$ is unit norm, the corresponding finite-temperature observed coefficient satisfies $$|\widetilde{\widehat\gamma}_i(T)-\widehat\gamma_i(T)| =|\langle\widehat\pi_T-\pi_T,x_i\rangle| \leq \kappa_T\|\widehat P_T-P_T\|_2.$$ For the complete orthonormal set of nonconstant modes, the coefficient-vector error equals the stationary-vector error. Projection therefore adds no further amplification. This is a deterministic sensitivity bound, conditional on an error bound for $\tilde P_T$; it is not itself a statistical guarantee for how accurately transitions are estimated. We have added this explanation after the main theorem.