Pith. sign in

REVIEW 2 major objections 6 minor 21 references

Induction heads do not merely count exact matches; at finite attention scale they implement soft n-gram interpolation and, with a BOS token, additive Dirichlet-style smoothing.

Reviewed by Pith at T0; open to challenge. T0 means a machine referee read the full paper against a public rubric. the ladder, T0–T4 →

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

T0 review · grok-4.5

2026-07-12 06:57 UTC pith:A2FTISJW

load-bearing objection Clean constructive characterization of induction heads as soft n-gram interpolators plus BOS pseudo-counts; solid math and matching experiments on the synthetic tasks they claim. the 2 major comments →

arxiv 2607.02800 v1 pith:A2FTISJW submitted 2026-07-02 cs.LG

Induction Heads Interpolate N-Grams

Francesco D'Angelo , Oguz Kaan Yuksel , Swathi Shree Narashiman , Nicolas Flammarion This is my paper
classification cs.LG
keywords induction headsin-context learningn-gram smoothingJelinek-MercerDirichlet smoothingMarkov chainssoft context matchingtransformers
verification ladder T0 review T1 audit T2 compute T3 formal T4 reserved

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper asks what statistical estimator an induction head actually implements when predicting the next token of an order-k Markov chain. Prior work treated the circuit as hard attention that counts exact k-gram matches, which is maximum-likelihood counting. The authors show that the same two-layer circuit, once the attention weights are allowed to remain finite, aggregates every partial context match in the history, weighting each by an exponential of how many tokens it shares with the current context. The resulting predictor is a data-dependent mixture over context orders, exactly the form of classical Jelinek-Mercer interpolation smoothing. A beginning-of-sequence token supplies an extra constant pseudo-count, recovering add-α (Dirichlet) smoothing. They construct an explicit disentangled transformer that realises both mechanisms, prove the closed-form estimator, and verify that both disentangled and ordinary trained transformers recover the predicted attention patterns and match or beat the corresponding classical baselines. The upshot is that transformers learn to regularise in-context estimation rather than simply count.

Core claim

A two-layer induction-head circuit realises the soft context-matching estimator that mixes exact and partial context matches with weights exponential in overlap; at large attention scale it recovers hard k-gram counting, while finite scale yields Jelinek-Mercer-style interpolation and a BOS token adds the constant that produces add-α smoothing.

What carries the argument

The soft context-matching estimator of Proposition 3.1: T(x)(m) equals the normalised sum of mask-conditioned transition counts N_M^{(T)}(m) each multiplied by e^{|β|_M}, plus an optional BOS pseudo-count e^κ/|V|. The free parameters β control the interpolation across match masks and κ controls the additive prior.

Load-bearing premise

The constructive proof and the claim that trained models implement the same estimator both rest on two-layer disentangled (or equivalent) architectures whose first-layer heads stay pure lag-specific copy heads, verified only on synthetic order-2 chains with a five-token vocabulary.

What would settle it

Train a standard two-layer transformer on order-2 Markov sequences drawn from an independent Dirichlet prior without a BOS token; if the layer-2 attention from the final position concentrates only on exact matches and never spreads mass onto partial-overlap contexts, the soft-matching claim fails.

Watch this falsifier — get emailed when new claim-graph text bears on it.

If this is right

  • When exact high-order matches are rare, the same induction-head circuit automatically backs off to lower-order and unigram evidence without any hand-designed backoff rule.
  • The BOS token is not merely an architectural convenience; it is the circuit-level realisation of additive pseudo-count regularisation.
  • Under hierarchical priors that couple sibling contexts, soft matching outperforms every fixed add-α baseline, so the mechanism is useful precisely when lower-order contexts carry structured information.
  • The attention-weight scale β is a single scalar knob that interpolates continuously between Katz hard back-off and smooth Jelinek-Mercer mixing.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same soft-matching construction may explain why induction heads remain useful in natural language even though true exact k-gram repeats are vanishingly rare.
  • If deeper stacks preserve the same lag-copy plus soft-match motif, classical n-gram smoothing theory could supply principled regularisers for multi-layer in-context learners.
  • Asymmetric lag weights learned under hierarchical priors suggest the circuit can discover which suffix positions are most informative, opening a route to data-dependent feature selection inside attention.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

2 major / 6 minor

Summary. The paper studies two-layer induction-head circuits on order-k Markov chains and gives a constructive characterization of the estimator they implement beyond the hard-attention limit. Proposition 3.1 exhibits explicit weights for a disentangled transformer realizing a soft context-matching estimator: successor tokens are aggregated with weights exponential in the Hamming overlap of query and candidate contexts, with a free scale β and an optional BOS-induced offset κ. Finite β yields a data-dependent interpolation over exact and partial matches, rewritten as a Jelinek–Mercer-style mixture over cumulative mask counts (Lemma 4.1, Corollary 4.2); BOS recovers add-α Dirichlet smoothing in the hard-attention limit (Corollary 4.1). Experiments on independent and hierarchical Dirichlet priors (k=2, |V|=5) show that both disentangled and standard trained transformers recover the predicted Layer-1 copy / Layer-2 match circuit, match or beat classical count-based baselines, and use soft matching when lower-order contexts are informative.

Significance. The work cleanly bridges mechanistic interpretability of induction heads with classical n-gram smoothing. The central contribution is a fully constructive weight assignment (Layer-1 lag-specific RPE copy heads; Layer-2 block-shift WA producing scores |β|_M; BOS sink for κ; successor readout), not a post-hoc fit, together with algebraic rewrites that identify the estimator with known smoothing families. Empirical recovery of the same attention patterns in both disentangled and standard two-layer models, plus KL curves that track the predicted estimators, makes the claim falsifiable and reproducible on the stated synthetic tasks. If the characterization continues to hold more broadly, it reframes induction heads as regularized in-context estimators rather than pure counters—an important conceptual shift for ICL theory.

major comments (2)
  1. Section 5 and Figures 3–5 support the claim that trained models implement the Prop. 3.1 estimator primarily via KL-to-truth curves and qualitative attention heatmaps / WA structure. A tighter check would fit free parameters (β, κ) of Eq. (8) on held-out sequences and report the KL or total-variation distance between the trained model’s next-token distribution and the fitted soft-matching estimator (construction vs. trained, with and without BOS). Without this, “implements the same estimator” remains one step short of quantitative identification, even though the mechanistic evidence is already strong.
  2. Appendix E, Corollary E.1: label-permutation symmetry only forces token-equality comparisons and allows general (r1,r2) lag pairs, not only the aligned super-diagonal blocks used in Prop. 3.1. The main text and Fig. 4 report that trained WA recovers the aligned block-shift structure, but do not quantify residual mass on off-diagonal comparison blocks. Reporting the relative Frobenius mass (aligned vs. non-aligned blocks) for trained disentangled and standard models would confirm that the restricted construction is the one selected by training, rather than a more general symmetry-compatible matcher.
minor comments (6)
  1. Lemma 4.2 and Appendix D.3: the approximate β for add-constant smoothing relies on independence and concentration assumptions that are coarse for k>1. A short numerical check (empirical E[α̃] vs. target α for the stated T, |V|, k) in the appendix would calibrate how good the approximation is in the experimental regime.
  2. Figure 2 is dense; the Layer-2 soft-matching panel would be clearer with an explicit legend for arrow thickness = e^{β|M|} and a callout that the final mixture includes the BOS uniform term only when BOS is present.
  3. Section 5: state explicitly that the hierarchical Bayes-optimal predictor has no closed form (already noted in §2.2) and that the dashed add-α curves are therefore suboptimal baselines rather than the Bayes target; this avoids a possible misreading of the right panel of Fig. 3.
  4. Notation: |β|_M is used for the sum of β_i over i∈M; a one-line definition near Def. 3.1 would help readers who jump to Prop. 3.1.
  5. Related work (Appendix B) is thorough; a brief pointer in the main-text introduction to MacKay & Peto (1995) and Chen & Goodman (1999) when first mentioning hierarchical Dirichlet / JM smoothing would orient non-LM readers earlier.
  6. Limitations (A.1) correctly flag synthetic Markov sources and two-layer depth; consider also noting that the last-token-only training objective (Eq. 5) isolates ICL but differs from full-sequence LM training, so transfer to natural-language induction heads remains an open empirical question.

Circularity Check

0 steps flagged

No significant circularity: the soft context-matching estimator is obtained by explicit weight construction, not by fitting or self-referential definition.

full rationale

Proposition 3.1 and its proof construct Layer-1 lag-specific hard-copy heads via RPE and a Layer-2 block-shift attention matrix W_A whose scores equal |β|_M (plus a BOS sink for κ); the resulting next-token map is exactly the displayed estimator by algebra of the softmax and residual concatenation. The subsequent rewrites (Lemma 4.1, Corollaries 4.1–4.2) are pure identities under the stated conventions (γ = e^β − 1, cumulative counts K_M, etc.) and do not import the target functional form. Empirical recovery of the same attention patterns and W_A structure by trained models is an independent check against the construction, not a fit of the estimator itself. Citations (Nichani et al. for disentangled–standard equivalence, classical JM/Katz references) supply background or architectural justification and are not load-bearing for the derivation of the estimator. No step reduces the claimed result to its own inputs by construction, fit, or self-citation chain.

Axiom & Free-Parameter Ledger

2 free parameters · 4 axioms · 0 invented entities

The central claim rests on standard attention algebra, the known equivalence of disentangled and standard transformers, conjugacy of Dirichlet-Categorical, and the classical definitions of Jelinek–Mercer and add-α smoothing. Free parameters are the attention-scale vector β and the BOS offset κ; they are either set analytically or left trainable. No new physical entities are postulated.

free parameters (2)
  • attention-scale vector β ∈ R^k
    Controls the exponential weight e^{|β|_M} of each match mask; free in the construction, set by the approximate formula of Lemma 4.2 or left trainable.
  • BOS pseudo-count offset κ
    Sets the additive constant e^κ that realises add-α smoothing; free when BOS is present, set to kβ + ln(α|V|) for the exact limit.
axioms (4)
  • domain assumption Disentangled transformers (concatenation residual, no MLP) are equivalent to standard attention-only transformers (Nichani et al. 2024).
    Invoked to justify studying the disentangled model as a faithful proxy; used throughout Sections 2–3 and the experiments.
  • standard math Dirichlet–Categorical conjugacy yields the closed-form posterior mean (add-α) under independent priors.
    Standard Bayesian calculation used to identify the Bayes-optimal predictor (Eq. 7) against which the circuit is compared.
  • domain assumption Relative positional encodings can implement hard lag-specific copy attention in the large-δ limit.
    Used to construct Layer-1 heads (Section 3.2.1); empirically recovered by trained models.
  • standard math Label-permutation symmetry of the Markov prior forces content-based attention blocks to be scalar multiples of the identity (Appendix E).
    Explains why trained models learn equality tests rather than arbitrary token comparisons.

pith-pipeline@v1.1.0-grok45 · 39050 in / 2668 out tokens · 26083 ms · 2026-07-12T06:57:42.513185+00:00 · methodology

0 comments
read the original abstract

Induction heads are attention circuits believed to underlie in-context learning in transformers, yet a precise characterization of the estimators they implement remains elusive. We study transformers trained on order-$k$ Markov chains and identify two complementary smoothing mechanisms. First, at finite attention-weight scale, the circuit implements a soft context-matching estimator: it aggregates contributions from exact and partial context matches, weighted exponentially by their overlap, and induces a data-dependent interpolation across context orders analogous to Jelinek-Mercer smoothing. Second, a beginning-of-sequence (BOS) token induces additive pseudo-counts, recovering Dirichlet-style smoothing. We construct a disentangled transformer implementing both mechanisms and show that trained transformers recover the predicted attention patterns. Across settings where pseudo-count smoothing is optimal or lower-order contexts provide structured evidence, trained transformers match or outperform classical count-based baselines. Our results bridge mechanistic interpretability of induction heads with classical statistical smoothing, revealing that transformers learn to regularize in-context estimation rather than simply count.

Figures

Figures reproduced from arXiv: 2607.02800 by Francesco D'Angelo, Nicolas Flammarion, Oguz Kaan Yuksel, Swathi Shree Narashiman.

Figure 1
Figure 1. Figure 1: The two task priors over the order-k transition tensor (illustrated for k=2, |V |=3). At each step the next token xt is drawn from the law of its length-k context; for k=2 this context is the ordered pair u = (c1, c2) = (older, recent) = (xt−2, xt−1), which indexes a next-token law πu(m) = P(xt=m | u) ∈ ∆|V |−1 . Both priors place a distribution over the collection {πu} and differ only in how these laws ar… view at source ↗
Figure 2
Figure 2. Figure 2: Two-layer transformer for order-k Markov chains (k=2). Layer 1: Copy heads build representations h (1) i = (xi, xi−1, xi−2). Layer 2: Compares query context at t with candidate contexts at positions s, s′ , s′′ . Vertical lines show position-wise comparison (= match, ̸= mismatch). Attention weights scale as e β|M| (arrow thickness). Successor tokens are aggregated into a probability distribution. Attention… view at source ↗
Figure 3
Figure 3. Figure 3: KL divergence to the ground-truth transition distribution. Left and middle: independent Dirichlet prior, where add-α smoothing is Bayes-optimal. Left (no BOS): with large β = 100 (blue diamonds) attention collapses to hard matching and tracks the MLE estimator (red); with adaptive β(t) (green circles, Lemma 4.2) the transformer interpolates across context orders and approaches the Bayes-optimal estimator (… view at source ↗
Figure 4
Figure 4. Figure 4: Mechanistic evidence on the hierarchical Dirichlet task; models: Disentangled Construction, Disentangled Trained, Standard Transformer. Left: attention scores; rows are Layer 1 head 1 (lag-1 copy), head 2 (lag-2 copy), and Layer 2 (matching). Top right: Layer-2 weight matrix W (2) A for the two disentangled models. Bottom right: Layer-2 attention weights at the last query position, coloured by overlap: ful… view at source ↗
Figure 5
Figure 5. Figure 5: Layer-2 induction-head attention from the last query position on the independent Dirichlet task (T=64), for the three predicted estimators: MLE (hard β, construction); interpolation (adaptive β; construction and trained); and BOS (hard β; construction and trained). Each bar is a key position, coloured by query–key context overlap. Hard β attends only to exact matches; finite β spreads mass over partial mat… view at source ↗
Figure 6
Figure 6. Figure 6: No-BOS construction: relative positional encodings RA (Layer 1 heads copy at lag 1 and lag 2) and the Layer 2 weight matrix W(2) A with its block-diagonal shift structure. These weights are shared with the adaptive regime below. 0 15 30 45 60 0 15 30 45 60 0.0 0.2 0.4 0.6 0.8 1.0 (a) Layer 1, Head 0 (after softmax) 0 15 30 45 60 0 15 30 45 60 0.0 0.2 0.4 0.6 0.8 1.0 (b) Layer 1, Head 1 (after softmax) 0 15… view at source ↗
Figure 7
Figure 7. Figure 7: No-BOS construction, fixed large β: Layer 1 post-softmax copy attention and the Layer 2 post￾softmax attention weights, which concentrate on exact n-gram matches. The induction-head bar (bottom) shows attention from the last query position, coloured by degree of context match. Fixed large β: hard n-gram matching [PITH_FULL_IMAGE:figures/full_fig_p020_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: No-BOS construction: the same RA and W(2) A as the fixed regime above (repeated for reference; W(2) A differs only by the overall β scale). 0 15 30 45 60 0 15 30 45 60 0.0 0.2 0.4 0.6 0.8 1.0 (a) Layer 1, Head 0 (after softmax) 0 15 30 45 60 0 15 30 45 60 0.0 0.2 0.4 0.6 0.8 1.0 (b) Layer 1, Head 1 (after softmax) 0 15 30 45 60 0 15 30 45 60 0.0 0.2 0.4 0.6 0.8 1.0 (c) Layer 2 (after softmax) 4 0 0 4 2 1 0… view at source ↗
Figure 9
Figure 9. Figure 9: No-BOS construction, adaptive β(t): identical Layer 1 copy attention, but the Layer 2 post-softmax attention weights now spread over partial matches (the interpolation of Lemma 4.1), and the induction bar distributes mass across full and partial matches. Adaptive β(t): interpolation smoothing [PITH_FULL_IMAGE:figures/full_fig_p021_9.png] view at source ↗
Figure 10
Figure 10. Figure 10: No-BOS trained model: learned relative positional encodings RA and Layer 2 weight matrix W(2) A . The trained model recovers the lag-specific copy structure in Layer 1 and the block-diagonal shift structure in W(2) A . 0 15 30 45 60 0 15 30 45 60 0.0 0.2 0.4 0.6 0.8 1.0 (a) Layer 1, Head 0 (after softmax) 0 15 30 45 60 0 15 30 45 60 0.0 0.2 0.4 0.6 0.8 1.0 (b) Layer 1, Head 1 (after softmax) 0 15 30 45 60… view at source ↗
Figure 11
Figure 11. Figure 11: No-BOS trained model: Layer 1 post-softmax copy attention, Layer 2 pre-softmax scores, and the Layer 2 induction-head attention. The trained model implements soft context matching, distributing attention over both full and partial matches [PITH_FULL_IMAGE:figures/full_fig_p022_11.png] view at source ↗
Figure 12
Figure 12. Figure 12: BOS construction: relative positional encodings RA (Layer 2 RA carries the BOS pseudo-count boost at the top offset and the first-k mask) and the Layer 2 weight matrix W (2) A . 0 15 30 45 60 0 15 30 45 60 0.0 0.2 0.4 0.6 0.8 1.0 (a) Layer 1, Head 0 (after softmax) 0 15 30 45 60 0 15 30 45 60 0.0 0.2 0.4 0.6 0.8 1.0 (b) Layer 1, Head 1 (after softmax) 0 15 30 45 60 0 15 30 45 60 −200 −100 0 100 200 (c) La… view at source ↗
Figure 13
Figure 13. Figure 13: BOS construction: Layer 1 post-softmax copy attention, Layer 2 pre-softmax scores, and the Layer 2 induction-head attention. The BOS pseudo-count lets the model attend sharply to exact matches while remaining well-regularized [PITH_FULL_IMAGE:figures/full_fig_p023_13.png] view at source ↗
Figure 14
Figure 14. Figure 14: BOS trained model: learned relative positional encodings RA and Layer 2 weight matrix W(2) A , recovering the construction’s structure. 0 15 30 45 60 0 15 30 45 60 0.0 0.2 0.4 0.6 0.8 1.0 (a) Layer 1, Head 0 (after softmax) 0 15 30 45 60 0 15 30 45 60 0.0 0.2 0.4 0.6 0.8 1.0 (b) Layer 1, Head 1 (after softmax) 0 15 30 45 60 0 15 30 45 60 −4 −2 0 2 4 (c) Layer 2 (before softmax) BOS 4 0 0 4 2 1 0 4 2 2 3 3… view at source ↗
Figure 15
Figure 15. Figure 15: BOS trained model: Layer 1 post-softmax copy attention, Layer 2 pre-softmax scores, and the Layer 2 induction-head attention, demonstrating the learned soft context-matching mechanism [PITH_FULL_IMAGE:figures/full_fig_p024_15.png] view at source ↗
Figure 16
Figure 16. Figure 16: Layer 2 weight matrix W(2) A at T = 128 for the hierarchical Dirichlet task. Both models exhibit the block-diagonal shift structure predicted by the theory. Attention patterns [PITH_FULL_IMAGE:figures/full_fig_p025_16.png] view at source ↗
Figure 17
Figure 17. Figure 17: Layer 2 attention at T = 128 for the hierarchical Dirichlet task (left: scores before softmax; right: weights after softmax). All models exhibit the induction head pattern, attending to positions with matching context [PITH_FULL_IMAGE:figures/full_fig_p026_17.png] view at source ↗
Figure 18
Figure 18. Figure 18: Layer 1 copy head attention at T = 128 for the hierarchical Dirichlet task. Head 0 copies the token at lag 1 and Head 1 at lag 2. All three models recover the same sharp positional attention [PITH_FULL_IMAGE:figures/full_fig_p027_18.png] view at source ↗
Figure 19
Figure 19. Figure 19: Induction head analysis at T = 128 for the hierarchical Dirichlet task: attention weights from the last query position, colored by degree of context match. All three models attend to full matches as well as partial matches, consistent with the interpolation across context orders predicted by the theory. Disentangled vs. standard architecture. The standard-transformer panels above ( [PITH_FULL_IMAGE:figur… view at source ↗

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

21 extracted references · 5 linked inside Pith

  1. [1]

    Language models are few-shot learners.Advances in neural information processing systems, 33:1877–1901,

    Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners.Advances in neural information processing systems, 33:1877–1901,

    1901

  2. [2]

    Sparks of artificial general intelligence: Early experiments with gpt-4.arXiv preprint arXiv:2303.12712,

    Sébastien Bubeck, Varun Chandrasekaran, Ronen Eldan, Johannes Gehrke, Eric Horvitz, Ece Kamar, Peter Lee, Yin Tat Lee, Yuanzhi Li, Scott Lundberg, et al. Sparks of artificial general intelligence: Early experiments with gpt-4.arXiv preprint arXiv:2303.12712,

    Pith/arXiv arXiv

  3. [3]

    Dan Friedman, Alexander Wettig, and Danqi Chen

    https://transformer- circuits.pub/2021/framework/index.html. Dan Friedman, Alexander Wettig, and Danqi Chen. Learning transformer programs. InThirty-seventh Conference on Neural Information Processing Systems,

    2021

  4. [4]

    Reddi, Stefanie Jegelka, and Sanjiv Kumar

    Khashayar Gatmiry, Nikunj Saunshi, Sashank J. Reddi, Stefanie Jegelka, and Sanjiv Kumar. Can looped transformers learn to implement multi-step gradient descent for in-context learning? In Ruslan Salakhutdinov, Zico Kolter, Katherine A. Heller, Adrian Weller, Nuria Oliver, Jonathan Scarlett, and Felix Berkenkamp, editors,Forty-first International Conferenc...

    2024

  5. [5]

    Jiachen Hu, Qinghua Liu, and Chi Jin

    URLhttps://proceedings.mlr.press/v235/gatmiry24b.html. Jiachen Hu, Qinghua Liu, and Chi Jin. On limitation of transformer for learning hmms.arXiv preprint arXiv:2406.04089,

    Pith/arXiv arXiv

  6. [6]

    Jiacheng Liu, Sewon Min, Luke Zettlemoyer, Yejin Choi, and Hannaneh Hajishirzi

    doi: 10.1109/TASSP.1987.1165125. Jiacheng Liu, Sewon Min, Luke Zettlemoyer, Yejin Choi, and Hannaneh Hajishirzi. Infini-gram: Scaling unbounded n-gram language models to a trillion tokens. InFirst Conference on Language Modeling,

    doi:10.1109/tassp.1987.1165125 1987

  7. [7]

    Attention with markov: A framework for principled analysis of transformers via markov chains.arXiv preprint arXiv:2402.04161,

    Ashok Vardhan Makkuva, Marco Bondaschi, Adway Girish, Alliot Nagle, Martin Jaggi, Hyeji Kim, and Michael Gastpar. Attention with markov: A framework for principled analysis of transformers via markov chains.arXiv preprint arXiv:2402.04161,

    Pith/arXiv arXiv

  8. [8]

    Sewon Min, Xinxi Lyu, Ari Holtzman, Mikel Artetxe, Mike Lewis, Hannaneh Hajishirzi, and Luke Zettlemoyer. Rethinking the role of demonstrations: What makes in-context learning work? In Yoav Goldberg, Zornitsa Kozareva, and Yue Zhang, editors,Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, pages 11048–11064, Abu Dhab...

    2022

  9. [9]

    Timothy Nguyen

    Association for Computational Linguistics. Timothy Nguyen. Understanding transformers via n-gram statistics. In Amir Globersons, Lester Mackey, Danielle Belgrave, Angela Fan, Ulrich Paquet, Jakub M. Tomczak, and Cheng Zhang, editors, 16 Advances in Neural Information Processing Systems 37: Annual Conference on Neural Information Processing Systems 2024, N...

    2024

  10. [10]

    Eshaan Nichani, Alex Damian, and Jason D

    URL http://papers.nips.cc/paper_files/paper/2024/hash/b1c446eebd9a317dd0e96b16908c821a-A bstract-Conference.html. Eshaan Nichani, Alex Damian, and Jason D. Lee. How transformers learn causal structure with gradient descent. InForty-first International Conference on Machine Learning,

    2024

  11. [11]

    Transformers on markov data: Constant depth suffices

    Nived Rajaraman, Marco Bondaschi, Ashok Vardhan Makkuva, Kannan Ramchandran, and Michael Gastpar. Transformers on markov data: Constant depth suffices. In Amir Globersons, Lester Mackey, Danielle Belgrave, Angela Fan, Ulrich Paquet, Jakub M. Tomczak, and Cheng Zhang, editors,Advances in Neural Information Processing Systems 37: Annual Conference on Neural...

    2024

  12. [12]

    Allan Raventos, Mansheej Paul, Feng Chen, and Surya Ganguli

    URLhttp: //papers.nips.cc/paper_files/paper/2024/hash/f8a2070082ad05b4deeff4ffb4312a6f-Abstr act-Conference.html. Allan Raventos, Mansheej Paul, Feng Chen, and Surya Ganguli. Pretraining task diversity and the emergence of non-bayesian in-context learning for regression. InThirty-seventh Conference on Neural Information Processing Systems,

    2024

  13. [13]

    Anej Svete and Ryan Cotterell

    URLhttps://openreview.net/f orum?id=O8rrXl71D5. Anej Svete and Ryan Cotterell. Transformers can represent n-gram language models. In Kevin Duh, Helena Gómez-Adorno, and Steven Bethard, editors,Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Paper...

    2024

  14. [14]

    URL https://doi.org/10.18653/v1/2024.naacl-long.381

    doi: 10.18653/V1/2024.NAACL-LONG.381. URL https://doi.org/10.18653/v1/2024.naacl-long.381. Aditya Varre, Gizem Yüce, and Nicolas Flammarion. Learning in-context $n$-grams with transformers: Sub-$n$-grams are near-stationary points. InForty-second International Conference on Machine Learning,

    doi:10.18653/v1/2024.naacl-long.381 2024

  15. [15]

    Johannes Von Oswald, Eyvind Niklasson, Ettore Randazzo, João Sacramento, Alexander Mordvintsev, Andrey Zhmoginov, and Max Vladymyrov

    URLhttps://openreview.net/forum?id=os7OLubIMI. Johannes Von Oswald, Eyvind Niklasson, Ettore Randazzo, João Sacramento, Alexander Mordvintsev, Andrey Zhmoginov, and Max Vladymyrov. Transformers learn in-context by gradient descent. In 17 International Conference on Machine Learning, pages 35151–35174. PMLR, 2023a. Johannes Von Oswald, Eyvind Niklasson, Ma...

    Pith/arXiv arXiv

  16. [16]

    Pretraining data mixtures enable narrow model selection capabilities in transformer models.arXiv preprint arXiv:2311.00871,

    Steve Yadlowsky, Lyric Doshi, and Nilesh Tripuraneni. Pretraining data mixtures enable narrow model selection capabilities in transformer models.arXiv preprint arXiv:2311.00871,

    Pith/arXiv arXiv

  17. [17]

    Generalization bounds for autoregressive processes and in-context learning

    Oğuz Kaan Yüksel and Nicolas Flammarion. Generalization bounds for autoregressive processes and in-context learning. InEurIPS 2025 Workshop on Principles of Generative Modeling (PriGM), 2025a. URLhttps://openreview.net/forum?id=wZfHBjoa9D. Oğuz Kaan Yüksel and Nicolas Flammarion. On the sample complexity of next-token prediction. In The 28th International...

    2025

  18. [18]

    led to several complementary explanations of how transformers adapt from prompts. One line of work studies ICL through the lens of algorithm learning: transformers trained on families of regression problems can learn procedures resembling gradient descent, least squares, or higher-order optimization methods (Garg et al., 2022; Akyürek et al., 2022; Von Os...

    2022

  19. [19]

    and causal-structure selection (D’Angelo et al., 2025). For continuous autoregressive sequences, trained transformers can first infer a linear transition map in context and then apply it for prediction, with one-layer linear models implementing a gradient-descent step in structured settings (Sander et al., 2024); for noisy linear dynamical systems, an opt...

    2025

  20. [20]

    and near-stationaryn-gram solutions (Varre et al., 2025). Our work differs in emphasis: instead of treating the learned predictor as hard transition-count estimation, we characterize the soft context-matching estimator induced by attention and show that it interpolates among exact and partial context matches. Transformers as sequential models.A broader th...

    2025

  21. [21]

    and can be computationally powerful models of sequence processing (Pérez et al., 2021; Sanford et al., 2024). For language-model-like distributions, sparse-attention transformers can representn-gram models exactly (Svete and Cotterell, 2024), though other sequential families such as hidden Markov models can expose limitations relative to recurrent archite...

    2021