acceptodds
Under review as a conference paper at ICLR 2027

A Harmonic Basis for Auditing Learned Sequential Biases in LLMs

Abstract

In this paper, we show that the next‑token statistics of any autoregressive language model, when observed at a chosen context order , induce a weighted random walk on the de Bruijn graph . We develop a harmonic analysis of this induced walk using the recently derived closed-form eigenvectors of the de Bruijn graph Laplacian. Each eigenvector captures an independent pattern of token co-occurrence at a definite oscillatory scale, and projecting the model's stationary distribution onto this basis yields temperature-independent coefficients – the model's harmonic spectrum – that depend only on the model's centred logits and account exactly for every deviation from uniform generation. We validate the framework with several experiments. First, the harmonic coordinates reveal distinct sequential biases in the task of binary random sequence generation with LLMs. Second, the harmonic spectrum decomposes the exploitable structure of LLM strategies in Rock-Paper-Scissors game into interpretable components, and correlates strongly with win rate across 19 models. Finally, we apply our framework to open-ended generation, projecting part-of-speech tag sequences onto the harmonic basis.

Primary area:
learning theory
Keywords:
LLMs, autoregressive inference, harmonic analysis

Reviews

Among:
Shape:
1234this paper, Bottom 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.25 over 4 reviews, above 49% of the others.
Reviewer_HYKLOpenReview ↗
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 V\mathcal{V}, 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 γi\gamma_i 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
  1. 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?
  2. How do errors in estimating the transition matrix propagate to the stationary distribution and the observed coefficients γ^i(T)\widehat{\gamma}_i(T)?
  3. Appendix E.4 establishes that Γ^\widehat{\Gamma} 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

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

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.

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=3k=3 gives 122=14412^2=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.70.7, 1.01.0, and 1.31.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.0980.098, 0.0860.086, and 0.0820.082 for the three temperatures, respectively, and 0.1210.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

How do errors in estimating the transition matrix propagate to the stationary distribution and the observed coefficients?

This propagation can be stated directly. Let PTP_T be the row-stochastic transition matrix, P^T\widehat P_T an estimated row-stochastic matrix, and let πT\pi_T and π^T\widehat\pi_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.

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 (2,−1,0,3)(2,-1,0,3) in context order (00,01,10,11)(00,01,10,11) at T=1T=1. The logits show that the conditional probability of choosing 11 after 1111 is 95.3%. They do not by themselves report how frequently the generated process visits 1111 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).

Reviewer_u3yYOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The authors perform a harmonic analysis of language model sequences to investigate biases in model generations.

Critical strengths

Having new tools for analyzing statistical patterns in language model text is useful for the community, and I can see potential applications in language model text detection, using these patterns as a fingerprint, as the authors say.

I am pleased to see attempts to formalize linguistic patterns in language model generations, and I would be interested to see what a human baseline would look like here. Are we better or worse than post-trained language models at RPS? Overall, I like the approach of applying recent advances in mathematical tooling other better understand language models.

Critical weaknesses

My chief worry about this paper is that I am not convinced of the usefulness of this particular method for analysis. The risk is that, though the closed form solution to the spectral decomposition is an interesting development, its actual utility here less well established. It might be a hammer looking for a nail. The authors use the spectrum to decompose RPS strategies into current move bias and repetition bias, but were these biases not already measurable and exploitable via other analyses? It would be nice to have an example of what this type of analysis gives us that existing analyses would not. As a guess for what this would look like, perhaps the higher order biases can only be found via this analysis, so prior to the Philippakis (2024) paper we would have no other way to measure, say, repetition bias. It would also be good to know what the limitations of this analysis.

The assumption that the model uses a sliding window attention is not realistic for modern language models, which use much longer contexts. The fact that the analysis scales poorly with alphabet size cc and context length kk as O(ck)O(c^k) calls into question whether this method would actually be useful for a nontrivial analysis of the model outputs beyond toy games like RPS and binary sequence prediction. The authors acknowledge this, but it nonetheless tempers my enthusiasm somewhat. This is a minor concern, since the paper's proposed method seems general and I would expect algorithmic improvements and approximations to appear in work building on this one.

Questions for authors

See Weaknesses.

4 comments
AuthorsOpenReview ↗

Thank you for your positive feedback

We thank the reviewer for the encouraging assessment, for recognizing the value of mathematical tools for analyzing LLM sequences, and for suggesting higher-order correlations as a useful direction for clarifying the framework's contribution. We address the added-value and applicability questions below.

1. Added Interpretation Beyond Inspecting Logits

Were the move and repetition biases not already measurable through other analyses? What does the framework add, particularly for higher-order biases?

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 (2,−1,0,3)(2,-1,0,3) in context order (00,01,10,11)(00,01,10,11) at T=1T=1. The logits show that the conditional probability of choosing 11 after 1111 is 95.3%. They do not by themselves report how frequently the generated process visits 1111 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. We have added Figure 1 and a dedicated paragraph in the end of Section 4 to provide these details. Do these explanations clarify the distinction between inspecting conditional logits and summarizing stationary sequential structure, or is there a particular alternative analysis you would find especially informative as a comparison? ### 2. Alphabet Size and the Exponential State Space > Can the method be useful beyond binary prediction and RPS, given the growth in alphabet size and context length? We would like to draw attention to the appendix experiment, **"Feasibility Extension: Open-Ended Generation via Part-of-Speech Sequences."** It analyzes ordinary generated prose by mapping words to a 12-symbol part-of-speech alphabet, rather than enumerating the model's full tokenizer vocabulary. At $k=3$, this yields $12^2=144$ context states. This provides a concrete route to studying linguistic sequential structure beyond two- or three-symbol output tasks. The experiment compares Qwen2.5-0.5B-Instruct generations at temperatures $0.7$, $1.0$, and $1.3$ with a Brown-corpus reference. Each tag sequence is also compared with a shuffled version that preserves its unigram frequencies while destroying its ordering. The reported excess harmonic mass over the shuffled control is $0.098$, $0.086$, and $0.082$ for the three model temperatures, respectively, and $0.121$ for the reference text. These results illustrate the application to a larger linguistic alphabet and sensitivity to ordering beyond tag frequencies. For larger alphabets and longer contexts, structure-preserving graph coarsening can be also a natural direction for future work, connecting this limitation to the graph-coarsening literature. Such methods would need to control how aggregation changes the stationary distribution and the interpretation of the harmonic modes; arbitrary state merging need not preserve the de Bruijn structure.

3. Graph Context Order Versus Model Attention

The sliding-window assumption is unrealistic for models with much longer contexts.

We believe there is a misunderstanding: our theoretical analysis does not assume sliding-window attention. If the reviewer is referring to a different assumption, could they please clarify which one?

4. Human Baselines

What would a human baseline look like, and are humans better or worse than post-trained models at RPS?

Thank you for raising this comparison. Human players are not an ideal randomness baseline. The behavioral study already cited in our RPS motivation, Wang, Xu, and Zhou (2014), Social cycling and conditional responses in the Rock-Paper-Scissors game, reports that participants favored repeating an action after a win, with outcome-dependent switching after losses. Thus, human play can appear close to uniform at the level of individual move frequencies while still exhibiting systematic sequential structure. This reinforces the motivation for examining dependencies beyond marginal preferences and suggests a natural use of our framework for comparing human and model-generated sequences.

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 your additional clarifications. I am overall pleased with the approach the authors take and think this is a potentially interesting direction, as the analysis allows us to formalize certain classes of generation patterns over limited alphabets and context lengths. The main drawback that I see is that there does not seem to be a strong extrinsic use case yet. I will maintain my recommendation for acceptance.

Reviewer_X3q1OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper models autoregressive inference as de Bruijn graphs per Philippakis et al. (2024). Subsequently, it applies harmonic analysis through spectral methods to uncover sequential biases. Applying these proposed analyses on various LLMs (e.g., to emitted Rock-Paper-Scissors) indeed shows biases in various LLMs (particularly, instruction-tuned ones).

Critical strengths
  • The paper offers an interesting mathematically grounded method for analyzing LLMs.

  • The proposed harmonic analysis is applied to a broad range of LLMs (App. E).

Critical weaknesses
  • The contribution feels relatively incremental. As prior work has already shown how to model inference as de Bruijn graphs, the paper’s main contribution lies in the harmonic analysis based on standard spectral methods. It’s unclear if this extension is sufficiently deep and useful (more on this below).

  • While the paper demonstrates a couple of applications for the proposed harmonic analysis, it doesn’t establish the benefit of using the proposed technique. Wouldn’t it be possible to perform the same analysis directly on the LLM output, without applying additional potentially expensive analysis techniques? What’s the advantage of applying the proposed method? Moreover, the selected use cases seem like niche applications with little real-world implications.

  • The paper doesn’t analyze and report the computational overhead and complexity of the proposed harmonic analysis.

  • I wonder if there are any mitigations of the uncovered biases that can be informed by the proposed technique. The paper doesn’t appear to propose any.

  • Minor typo in Line 277: “equation equation”

Questions for authors

See above.

3 comments
AuthorsOpenReview ↗

Lack of prior word modelling autoregressive inference using de Bruijn graphs

We thank the reviewer for recognizing the mathematically grounded approach and the breadth of the model evaluation. We address the four critical weaknesses individually below.

1. Novelty Relative to Prior de Bruijn Work

As prior work has already shown how to model inference as de Bruijn graphs, the contribution feels relatively incremental.

We would like to clarify the relationship to the cited work. Philippakis et al. provide the closed-form eigenvectors of the uniform walk on the de Bruijn graph Laplacian; they do not present the harmonic analysis of LLM stationary behavior developed here that requires to analyze a weighted walk derived from the LLM's logits. Our contribution is the use of this basis to characterize sequential structure in autoregressive models. To our knowledge, prior work does not provide this harmonic stationary analysis of LLM behavior; our novelty claim concerns this analysis, rather than the use of de Bruijn graphs in general.

We have also broadened the Related Work discussion to cover n-gram and higher-order graph methods, theoretical work on transformer expressivity and formal languages, Markov-chain views of autoregressive generation, and theories of in-context learning. We added surveys of transformer formal-language expressivity and ICL interpretation and analysis, and clarified that these works address complementary questions rather than the stationary harmonic organization studied here.

Could you kindly point us to the prior work you had in mind, so that we can address that comparison explicitly in the related-work discussion?

2. Added Value Beyond Simply Inspecting Logits

Could the same analysis be performed directly on the LLM output? What is the advantage, and are the applications too niche?

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.

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 (2,−1,0,3)(2,-1,0,3) in context order (00,01,10,11)(00,01,10,11) at T=1T=1. The logits show that the conditional probability of choosing 11 after 1111 is 95.3%. They do not by themselves report how frequently the generated process visits 1111 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 the added interpretation beyond inspecting conditional logits, or did you have a different direct-output analysis in mind that would be useful to compare against?

3. Computational Cost and Overhead

The computational overhead and complexity are not reported.

We thank the reviewer for this suggestion. Relative to analyzing the same queried logits, our binary/gender analysis adds only the construction of a 4×44\times4 transition matrix, a 5×45\times4 least-squares solve for stationarity, and three length-four dot products with predefined basis vectors, requiring no additional LLM forward passes or numerical eigendecomposition. We included the algorithmic complexity in the appendix and mentioned it in the opening paragraph of Section 5.

4. Potential Mitigation and the Scope of the Paper

Can the uncovered biases inform mitigation?

We thank the reviewer for this insightful suggestion. Our framework can provide a natural target for model alignment in settings where states have externally defined (as in LLM-as-a-judge paradigm) safe/unsafe labels. The stationary distribution quantifies the probability mass assigned to unsafe states, while the harmonic decomposition characterizes the sequential structure associated with that bias. If the audit reveals a strong bias toward unsafe states, standard safety-alignment techniques, such as safety-focused supervised fine-tuning or preference optimization, can be applied with the aim of reducing that mass. Repeating the audit would then assess whether the targeted bias has decreased.

Our contribution focuses on auditing and understanding LLM sequential behavior. We added this as a future direction in the Limitations section, alongside a complementary possibility of auditing sequences of validated sparse-autoencoder features. Using these diagnostics to guide and evaluate safety alignment remains a potential application; we have not developed or evaluated a mitigation procedure in this work.

5. Minor Typo

Line 277: "equation equation".

Thank you for pointing this out; we removed the duplicated word in the revision.

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.

Reviewer_irpCOpenReview ↗
Rating
1(−1)
Confidence
2
Informativeness
1
Presentation
2
Soundness
3
Read review
Paper summary

The paper considers language models as a random walk over a graph of n-grams (the "de Bruijn graph"). With this perspective, they propose a harmonic decomposition of such objects, and do some numerical validation of their results.

Critical strengths

I'd like to thank the authors for their paper. It is nice to see a treatment of language models as a probabilistic model over a natural object (in this case the "de Bruijn graph", i.e. a graph over n-grams).

Critical weaknesses

I have two major concerns.

  • My main concern is that I don't see what makes this math interesting. Doing math is nice, don't get me wrong -- but I'm not sure I see why this particular math is helpful other than being 'cute'.
    • The phenomena being analyzed in the experiments could be a little relevant (hard to tell, they are not written very clearly), but I don't see what it is that the proposed framework allows us to do that couldn't have been done by, e.g., just sampling the model a couple of times and looking at the outcomes.
  • Secondly, I think the exposition falls short of the level expected of ICLR.
    • While doing a high-level read of the paper wasn't that bad, actually understanding the paper -- and in particular, the mathematical details (which is the crux of the paper) and the experiments -- is quite challenging.
    • As a consequence, I was not able (yet) to carefully check the correctness of the math.

Some additional (comparatively) minor comments:

  • I feel like Remark 4.6 is out of place, and should be moved to the experiments section
    • Relatedly, why is Section 4.3 -- which reports a sort of experimental validation -- not in the clearly-labelled "Experiments" Section 5?
  • The discussion of related work is extremely lacking. Theory of LLMs, transformers and related models have spanned a huge breadth of papers, of which the paper only seems to mention the "physics of language models" line of work, for no apparent reason (the paper isn't even particularly closely related to this line of work).
  • There are a bunch of sentences that are rather unnatural (perhaps remnants of the disclosed AI-assisted writing?). For example:
    • In line 113-114, the authors seemingly explain what they don't do, in an obfuscated sentence?
    • The exposition of the proofs follow a rather nonstandard format (see e.g., Appendix A.3), and a number of the steps are rather opaque.
  • Note that this work only addresses langugage models defined on a fixed context size, with one special element of the alphabet corresponding to a padding token (and part of the graph left unexplored). As far as I could tell this was glossed over.

Overall, this leads me to give a weak reject score. The aforementioned issues keep me from giving any positive score; that said, the analysis still appears somewhat sensible, making a straight rejection undue.

Questions for authors

Why is the proposed theory useful?

5 comments
AuthorsOpenReview ↗

The proposed theory identifies long-run inference patterns within a well-posed coordinate system

We thank the reviewer for recognizing the value of the probabilistic perspective and for identifying where the manuscript needs clarification. We respond to each concern below.

1. Usefulness beyond inspecting samples

What does the proposed framework allow us to do that could not be done by sampling the model and looking at the outcomes?

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 question that differs 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 Figure 1 added to the revision of our paper, we consider a model conditioned on its last two binary symbols, with logit differences (2,−1,0,3)(2,-1,0,3) in context order (00,01,10,11)(00,01,10,11) at T=1T=1. The logits show that the conditional probability of choosing 11 after 1111 is 95.3%. They do not by themselves report how frequently the generated process visits 1111 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. We have added Figure 1 and a dedicated paragraph in the end of Section 4 to provide these details. We remain open to any suggestion the reviewer might have to improve our manuscript further. ### 2. Difficulty following the mathematics and experiments > Understanding the mathematical details and experiments is challenging. We recognize that de Bruijn graph harmonics are less familiar in the ML community. To account for this, we provided a proof sketch of the main theorem and significantly expanded the proofs in the Appendix to provide more intuitions to the mathematical details. We also included an illustration of the algorithmic pipeline in Figure 1 to explain how the different experiments are carried out. Beyond Appendix A.3 and lines 113--114, mentioned earlier, could you indicate further equations or experimental passages where the explanation becomes difficult to follow? This would help us target the revision. ### 3. Placement of Remark 4.6 > Remark 4.6 should be moved to the experiments section. We agree that the finite-temperature discussion belongs with the experiments. In the revised manuscript, the main text briefly motivates the $T=1$ evaluation in the opening of the experiments section, while the temperature sweep and its interpretation are reported in the appendix. ### 4. Placement of Section 4.3 > Why is the numerical validation in Section 4.3 rather than Section 5? We thank the reviewer for this question. We placed it immediately after the theorem to illustrate the asymptotic expansion. Following the reviewer's suggestion, we moved the toy numerical verification, its logit specification, and the closed-form stationary-distribution calculations to an appendix, with a brief reference from the theorem discussion. The main empirical studies will remain together in Section 5.

5. Related work and the emphasis on physics of language models

The related-work discussion is lacking, and the emphasis on physics of language models is not well motivated.

We broadened the Related Work section beyond the synthetic-language literature. It now covers transformer expressivity and formal-language recognition, synthetic context-free grammar learning, Markov-chain views of autoregressive generation, and theoretical accounts of in-context learning, including Bayesian and gradient-based interpretations. We also relate our binary-sequence analysis to Bigelow et al. and our game analysis to West and Potts, and added pointers to surveys of transformer formal-language expressivity and ICL interpretation and analysis (Strobl et al.; Zhou et al.).

Does the reviewer have anything else they would like us to add in this paragrpah?

6. Unnatural wording, including lines 113--114

The sentence at lines 113--114 explains what the authors do not do in an obfuscated way.

We changed the sentence on lines 113-114 to make them more natural.

7. Opaque proof steps in Appendix A.3

The proof presentation is nonstandard and several steps are opaque.

We expanded Appendix A.3 into a more conventional proof, making normalization, the mean-zero Poisson equation, and the stationary-distribution expansion explicit. In particular, the revised proof writes out the uniform walk's finite-step transition equation and the resulting inverse on the mean-zero subspace rather than relying on a kernel/span shortcut. We also added a proof sketch of the main theorem.

We hope this will help to make the proof easier to follow.

8. Fixed context, padding, and unexplored states

The analysis assumes a fixed context size, with a special padding token and part of the graph unexplored.

Kindly note that a special padding symbol is not required for our model: the chain can be initialized with any context in Ak−1\mathcal A^{k-1}. The confusion may arise from the de Bruijn vector that is used to "pad" tensors in the basis construction but this one is the normalized uniform vector over symbols, not a literal padding token.

Under finite logits and positive-temperature, unmasked softmax on the chosen alphabet, every valid edge has positive probability and every graph vertex is reachable. Thus there is no permanently unexplored component under these assumptions, although finite samples may leave many states unvisited.

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.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of the revision

We sincerely thank all four reviewers for their careful reading, constructive questions, and generous comments about the paper's mathematical perspective and potential. Reviewers described it as “an interesting mathematically grounded method,” praised the “new tools for analyzing statistical patterns in language model text,” and called the mathematical analysis “strong and presented in a clear and intuitive manner”; their feedback also helped us sharpen the exposition, state limitations more clearly, and better connect the theory to the experiments as follows:

  1. Added an illustration of the proposed framework (Figure 1 and the "Beyond logits" paragraph) and clarified what stationary harmonic coordinates add to inspecting local conditional logits.

  2. Expanded Related Work to cover transformer and formal-language theory, Markov-chain views of language models, in-context-learning theory, and surveys of transformer expressivity and ICL analysis.

  3. Added a transition-estimation sensitivity bound and computational complexity analysis, and expanded the theorem proofs with explicit equations.

  4. Improved the readability of the manuscript by moving the toy numerical verification and logit specification to the appendix, adding practical-estimation explanations, and identifying mitigation and sparse-autoencoder feature audits as future directions.

We believe that these revisions strengthen the paper by making its mathematical claims more transparent, its examples and experiments easier to interpret, and its framework more easily distinguishable from local model preferences.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.