Pith. sign in

REVIEW 3 major objections 5 minor 5 cited by

Learning Compositional Functions with Transformers from Easy-to-Hard Data

T0 review · 3 major / 5 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read A transformer with $O(\log k)$ layers can learn $k$-fold composition from easy-to-hard data with $\mathrm{poly}(k,N)$ samples, while $k$-fold-only data provably costs exponential resources.

desk verdict First end-to-end gradient guarantee for a deep transformer on a compositional task, with a real SQ lower bound and an honest disclosure that the value matrices are fixed, not learned. read the letter →

arxiv 2505.23683 v1 pith:EKHB24BR submitted 2025-05-29 cs.LG

Zixuan Wang , Eshaan Nichani , Alberto Bietti , Alex Damian , Daniel Hsu , Jason D. Lee , Denny Wu This is my paper · ORCID
classification cs.LG MSC 68T0768Q32
keywords k-foldcompositiontransformerscurriculumlearningstatisticalquerylowerboundgradientdescentmulti-hopreasoningeasy-to-harddatacompositional
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

Transformers are known to represent deep compositional computations with only $O(\log k)$ layers, but whether gradient-based training can actually learn such computations was open; this paper settles a concrete instance. For the $k$-fold composition task — applying $k$ input permutations interleaved with $k$ hidden permutations to an index — it proves that a learner seeing only $k$-fold examples pays an exponential cost: any learner using statistical queries (the standard oracle model for gradient-based learning) needs $N^{\Omega(k)}$ queries or a tolerance of $N^{-\Omega(k)}$, meaning exponential sample size or runtime under the usual concentration heuristic. The paper then shows that the exponential dependence disappears once the training data contains easier sub-tasks: with $M \ge \widetilde{\Omega}(k^4 N^6)$ samples of $2^{\ell-1}$-hop functions for all $\ell$, presented either as an increasing curriculum or as a single mixture, an $O(\log k)$-depth transformer trained by one gradient step per stage learns every hop length up to $\varepsilon$ softmax error, including the full $k$-fold composition. The reason easy examples matter is made precise: each layer learns to double the composition length step by step, structure that hard-only data does not reveal.

What carries the argument

The central object is the hop function $hop^r_i(\sigma, \cdot) = \sigma_{i+r-1} \circ \pi_{i+r-1} \circ \cdots \circ \sigma_{i+1} \circ \pi_{i+1} \circ \sigma_i \circ \pi_i$, a sliding window of $r$ composed permutations whose full-task value is $hop^k_1(\sigma, x)$. Both the expressivity construction and the learning dynamics use recursive doubling: layer $\ell$ is wired so that token $(i, j)$ attends to token $(i + 2^{\ell-2}, hop^{2^{\ell-2}}_i(j))$ and copies its stored value, composing two length-$2^{\ell-2}$ hops into one length-$2^{\ell-1}$ hop, so $L = \log_2 k + 1$ layers suffice. The gradient analysis shows that at each stage the dominant block of the population gradient of the cross-entropy loss with respect to the key-query matrix $W^{(\ell)}_{KQ}$ is exactly the map that creates this attention pattern, and concentration bounds on the empirical gradient make the finite-sample softmax attention concentrate there. The value matrices $W_{OV}$ are fixed to block-sparse matrices from the explicit construction, and the SQ lower bound rests on the correlation formula $\langle f_\pi, f_\rho\rangle = \frac{1}{N(N-1)^{k-1}} \prod_{i=1}^k (\langle \pi_i, \rho_i\rangle - 1)$, which yields a nearly orthogonal subfamily of the function class of size $(r!/4)^{k/2}$.

What would settle it

Train the same $O(\log k)$-layer transformer with the value matrices also updated by gradient descent from a small random non-zero initialization, on curriculum or mixture data with $M \ge \widetilde{\Omega}(k^4 N^6)$ samples at the paper's own scale ($k = 16$, $N = 5$); if the fully trained model consistently fails to reach $\varepsilon$-softmax accuracy on the $k$-fold task, the guarantee does not extend beyond the fixed-value-matrix setting, and a direct numerical check of whether the value-matrix gradient is non-zero at that initialization would localize the failure.

Watch

Extended reading notes

Core claim

The central claim is a matched pair of results about the learnability of the $k$-fold composition task, in which the model sees $k$ in-context permutations $\sigma_1, \dots, \sigma_k$ and must output $(\sigma_k \circ \pi_k \circ \cdots \circ \sigma_1 \circ \pi_1)(x)$ using hidden permutations $\pi_1, \dots, \pi_k$ that must be learned from data. On the negative side, Theorem 2 states that any statistical-query learner given only $k$-fold examples needs either $q \ge N^{\Omega(k)}$ queries or tolerance $\tau \le N^{-\Omega(k)}$ to reach constant error, which under the standard $\tau \approx n^{-1/2}$ heuristic means exponential sample size or runtime. On the positive side, Theorems 3 and 4 state that an $O(\log k)$-depth transformer trained by one gradient step per stage on its key-query and readout matrices, with $M \ge \widetilde{\Omega}(k^4 N^6)$ samples of $2^{\ell-1}$-hop data for every $\ell \le \log_2 k + 1$, outputs a softmax vector within $\varepsilon$ of the correct answer for every hop length, including the full $k$-fold composition; this holds both when the data is presented as an increasing curriculum and when all hop lengths are mixed together. The proofs show that the first layer's key-query matrix learns all hidden permutations from the population gradient, and each later layer's key-query matrix learns to compose the two $2^{\ell-2}$-hop values produced by the previous layer, with the accumulated error growing only linearly in depth.

Load-bearing premise

The load-bearing premise is that every layer's value matrix — the component that copies attended information into the residual stream — is fixed to a hand-designed block-sparse pattern and only the key-query and readout matrices are trained; the paper shows the gradient for those value matrices vanishes at the standard zero initialization, so it does not establish that a fully parameterized transformer learns the construction end to end.

Editorial extensions

If this is right

  • Including easier sub-task hops ($k'$-fold data for $k' \le k$) in the training distribution cuts the sample complexity of learning the $k$-fold composition from exponential in $k$ to polynomial in $k$ and $N$; the SQ lower bound applies only to data restricted to the hardest examples.
  • A single mixture of all hop lengths produces the same implicit curriculum as staged training, so the benefit of easy examples does not depend on the training schedule.
  • The learned network's layers implement recursive hop-doubling, giving a mechanistic account of why multi-hop compositional reasoning is efficiently parallelizable in $O(\log k)$ depth.
  • The guarantee covers every hop length $2^{\ell-1}$ simultaneously, including the cyclic variant, so one trained network answers queries at all difficulty levels.
  • The upper-bound theorems fix the value matrices to hand-specified block-sparse patterns and train only key-query and readout matrices; the paper shows the population gradient for the value matrices vanishes at zero initialization, so the fully end-to-end setting remains open.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A testable extension the authors do not pursue: on natural-language multi-hop benchmarks, injecting easy compositional examples into the training mixture should reproduce the implicit-curriculum effect, making explicit curriculum scheduling unnecessary.
  • The vanishing-gradient obstruction for value matrices at zero initialization suggests that end-to-end training would need non-zero or random initialization; whether the $\mathrm{poly}(k,N)$ guarantee survives random initialization is an open question a simulation could answer.
  • Because the SQ lower bound only uses near-orthogonality of the function class under the correlation inner product, other permutation-based compositional tasks, such as interleaved group products, likely exhibit the same exponential gap, and the easy-data cure may generalize.
  • The paper conjectures that non-power-of-two $k$ requires embedding dimension $\Theta(k^2 N)$; checking whether the one-step-per-stage proof extends there would complete the curriculum guarantee for all $k$.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

3 major / 5 minor

Summary. The paper studies the learnability of the k-fold composition task, which requires computing an interleaved composition of k input permutations and k hidden permutations. It provides an O(log k)-depth attention-only transformer construction (Theorem 1), an SQ lower bound showing that any SQ learner with polynomially many queries requires query count or tolerance exponential in k (Theorem 2), and upper bounds showing that a curriculum or a mixture of easy-to-hard data allows gradient descent to learn the task with poly(N,k) samples (Theorems 3 and 4). The upper-bound analysis trains only key-query and readout matrices; the value matrices are fixed to the block-sparse construction from Theorem 1. Experiments on small instances support the theoretical findings.

Significance. If the upper bounds held for fully parameterized transformers, this would be a significant contribution: it would provide a rigorous example of a statistical-computational gap for a compositional reasoning task and a theoretical explanation for the benefit of curriculum learning in deep transformers. The SQ lower bound is self-contained and uses standard packing arguments; the gradient computations in the appendix are explicit and detailed; and the empirical validation is consistent with the theory. However, the central gradient-descent claim is conditional on the value matrices being fixed to the construction. Since the paper itself shows in Appendix E that the value-matrix gradient vanishes at zero initialization, the abstract's phrasing that the task is 'learned by gradient descent' overstates the proven scope. This is a genuine limitation, not an internal inconsistency: the theorems as stated hold under the stated assumptions.

major comments (3)
  1. [§5.1, §7, Appendix E] The main gradient-based learning theorems (Theorems 3 and 4) fix each layer's value matrix W_OV^(ℓ) to the block-sparse matrix e_{L+2,ℓ+2} e_{L+2,ℓ+1}^T ⊗ I_{kN} and train only the key-query and readout matrices. Appendix E shows that the population gradient with respect to W_OV at zero initialization vanishes under the data model (for ℓ=1, and by the same uniform-softmax argument for all layers). Since W_OV is the mechanism that copies hop blocks between layers, the paper does not establish that a fully parameterized transformer learns the value matrices by gradient descent. This is a load-bearing gap for the abstract's claim that the task is 'learned by gradient descent ... by a transformer.' I recommend either providing an analysis that shows how W_OV can be learned (e.g., under non-zero initialization or modified data distribution) or reframing the contribution as learning key-query and readout matrices given the value matrices.
  2. [§5.2, Theorem 4] Theorem 4 states 'For sufficiently small ϵ > 0' without an explicit condition, whereas the proof in Appendix D requires the quantitative bound ϵ ≤ ~O(1/(k^6 N^6)) and ϵ log^{2L}(1/ϵ) ≤ 1. The theorem statement should include the explicit range of ϵ to match the proof and to make the result reproducible.
  3. [§1.1, §5.1] The paper claims in the introduction to provide 'the first end-to-end optimization and statistical guarantee for a deep transformer.' Since the value matrices are fixed and not learned, the guarantee is not end-to-end in the usual sense of training all parameters. This overstatement should be corrected to accurately describe the scope of the optimization guarantee.
minor comments (5)
  1. [§5.1, Algorithm 1] The initialization line uses the notation Ψ^{(ℓ)} but the rest of the algorithm and text use Ψ_ℓ; please unify the notation for the readout layers.
  2. [Appendix E] The vanishing-gradient calculation is explicitly carried out only for ℓ=1; state that the same symmetry argument applies to all layers because the softmax is uniform at zero initialization, so the conclusion holds for every W_OV^(ℓ).
  3. [§7] The phrase 'these matrices are not fixed at the identity' is imprecise: the value matrices are fixed to block-sparse matrices containing identity blocks, not to the identity matrix itself. Please rephrase.
  4. [Lemma 2 proof] The symbol 'DS−i' appears to be a typo for the derangement number D_{N-i}; please correct it.
  5. [§5.2, Theorem 3] The bound '0<ϵ≤~O(1/(k^2 N^3))' mixes tilde and O in an unusual way; define explicitly that the tilde hides poly-log factors in k and N.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the learning theorems are gradient-convergence proofs under a stated fixed-value-matrix assumption, not restatements of their inputs.

full rationale

The claimed derivations are not circular. Theorem 1 is a complete, self-contained transformer construction for the k-fold composition task, with the key-query and value matrices explicitly written in Appendix A. The SQ lower bound in Theorem 2 is proved from a nearly orthogonal packing construction and standard statistical-query arguments, not from the paper's own learning results. Theorems 3 and 4 analyze gradient dynamics: although the curriculum and mixed objectives contain the 2^{ℓ-1}-hop labels that the theorems later guarantee the model can output, the substantive claim is that one gradient step on the key-query matrices finds the correct attention pattern, established via gradient computation, signal-noise separation, concentration, and perturbation accumulation. The fixed W_OV assumption in Section 5.1 is an explicit architectural restriction, and Section 7 plus Appendix E candidly state that the population gradient of W_OV vanishes at zero initialization; this narrows the end-to-end scope of the abstract's wording, but it is a stated assumption and acknowledged limitation, not a circular reduction. Citations to Sanford et al. and Liu et al. are for construction style, with the construction itself reproduced, and the only self-citation in the SQ proof follows a standard argument that is written out in the appendix. No parameter is fitted to a closely related quantity and then renamed a prediction, and no load-bearing uniqueness claim is imported from the authors' own prior work.

Assumptions & free parameters 2 free parameters · 6 assumptions · 0 invented entities

The central claim rests on explicit modeling choices: fixed value matrices, power-of-two k, uniform distribution, and the SQ model. There are no fitted constants in the derivation; the learning rate and initialization scale are proof-required hyperparameters. The paper is transparent about the fixed-value-matrix limitation, which is the main load-bearing assumption.

free parameters (2)
  • learning rate eta = Omega~(k^2 N^3 / beta0 * log(1/epsilon))
    Proof requires a large one-step learning rate to saturate the attention; chosen by theorem, not estimated from data.
  • initialization scale beta0 = 0 < beta0 <= 1
    Small readout initialization needed for the gradient computation and mean-centering cancellation.
assumptions (6)
  • ad hoc to paper k is a power of two (k=2^{L-1})
    Theorem 1 construction and both upper-bound theorems assume this; general k is deferred to future work with larger embedding.
  • ad hoc to paper Value matrices W_OV^{(l)} are fixed to the block-sparse construction, not learned
    Section 5.1 fixes W_OV; Section 7 notes the population gradient at zero initialization vanishes, so end-to-end learning of these matrices is not covered.
  • domain assumption Uniform distribution over input permutations and query indices
    Task distribution defined in Section 2.1; all expectations and lower bounds depend on uniformity.
  • domain assumption SQ oracle model and the heuristic that gradient descent can be modeled by SQ queries
    Appendix B derives the connection but labels it heuristic due to noise model mismatch; the exponential lower bound is for SQ learners, not proven for SGD directly.
  • domain assumption Attention-only transformer, single head per layer, residual connections
    Architecture in Definition 2; the analysis does not cover MLPs, layer norm, multi-head, or decoder-only causal variants.
  • standard math Concentration and permutation-counting tools
    Uses Hoeffding, union bound, derangement counting, and Cauchy-Schwarz without restating proofs.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Learning Compositional Functions with Transformers from Easy-to-Hard Data." pith.science (2026). https://pith.science/paper/EKHB24BR

@misc{pith2026250523683,
  author       = {Pith},
  title        = {Pith review of: Learning Compositional Functions with Transformers from Easy-to-Hard Data},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/EKHB24BR}},
  note         = {Machine review of arXiv:2505.23683}
}
abstract

Transformer-based language models have demonstrated impressive capabilities across a range of complex reasoning tasks. Prior theoretical work exploring the expressive power of transformers has shown that they can efficiently perform multi-step reasoning tasks involving parallelizable computations. However, the learnability of such constructions, particularly the conditions on the data distribution that enable efficient learning via gradient-based optimization, remains an open question. Towards answering this question, in this work we study the learnability of the $k$-fold composition task, which requires computing an interleaved composition of $k$ input permutations and $k$ hidden permutations, and can be expressed by a transformer with $O(\log k)$ layers. On the negative front, we prove a Statistical Query (SQ) lower bound showing that any SQ learner that makes only polynomially-many queries to an SQ oracle for the $k$-fold composition task distribution must have sample size exponential in $k$, thus establishing a statistical-computational gap. On the other hand, we show that this function class can be efficiently learned, with runtime and sample complexity polynomial in $k$, by gradient descent on an $O(\log k)$-depth transformer via two different curriculum learning strategies: one in which data consists of $k'$-fold composition functions with $k' \le k$ presented in increasing difficulty, and another in which all such data is presented simultaneously. Our work sheds light on the necessity and sufficiency of having both easy and hard examples in the data distribution for transformers to learn complex compositional tasks.

Figures

Figures reproduced from arXiv: 2505.23683 by the authors.

Figure 1
Figure 1. k-fold composition task – red arrows represent the hidden permutation πi and green arrows denote input permutations σi . Given an input (σ, x), fπ(·, ·) composes 2k permutations to output fπ(σ, x). π not given in the input (e.g., Quarterback → Football) which may represent “parametric” or “in-weights” knowledge [11, 65, 15]. The contextual permutation is a standard feature in the k-hop reasoning task [54], whereas t… view at source ↗
Figure 2
Figure 2. Illustration the format of input X(0) and the attention pattern in Theorem 1. where the columns of X(σ) are indexed by the tuples (i, j) ∈ [k] × [N]. The output of TFθ(X(σ)) must also be decoded to a prediction in [N] as follows. Let Ψ ∈ R d×N , be the readout layer. The predictions of the learner for the permutation composition and the cyclic permutation tasks are given by ˆf(σ, x) = (Ψ⊤TFθ(X(σ))(1,x) ∈ R N , and ˆ… view at source ↗
Figure 3
Figure 3. Left: Curriculum learning (Algorithm 1). Middle: Learning with data mixture (Algorithm 2). Right: Comparison between training with and without mixed data on standard encoder transformer. 6 Experiments In this section, we provide empirical support for the conclusions of Theorem 3 and Theorem 4. In the leftmost plot of [PITH_FULL_IMAGE:figures/full_fig_p013_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 5 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Scaling Latent Reasoning via Looped Language Models

    cs.CL 2025-10 unverdicted novelty 7.0 of 10

    Looped language models with latent iterative computation and entropy-regularized depth allocation achieve performance matching up to 12B standard LLMs through superior knowledge manipulation.

  2. The Power of Power Law: Asymmetry Enables Compositional Reasoning

    cs.AI 2026-04 unverdicted novelty 6.0 of 10

    Power-law data sampling creates beneficial asymmetry in the loss landscape that lets models acquire high-frequency skill compositions first, enabling more efficient learning of rare long-tail skills than uniform distr...

  3. Breaking the Reversal Curse in Autoregressive Language Models via Identity Bridge

    cs.AI 2026-02 conditional novelty 6.0 of 10

    Identity-bridge regularization, rephrased into an out-of-context reasoning form, yields ~40% reversal accuracy in a 1B LLM and provably fixes reversal in an idealized one-layer transformer.

  4. Transformers with RL or SFT Provably Learn Sparse Boolean Functions, But Differently

    cs.LG 2025-11 conditional novelty 6.0 of 10

    Under hand-designed masks and task-specific activations, RL fine-tuning learns a k-sparse Boolean reasoning chain in one gradient update while SFT learns it one CoT step per update.

  5. Beyond Statistical Learning: Exact Learning Is Essential for General Intelligence

    cs.AI 2025-06 conditional novelty 5.0 of 10

    Reliable deductive reasoning in AI requires replacing average-case statistical objectives with the exact learning criterion of universal correctness, a thesis supported by sample-complexity lower bounds showing statis...

Reference graph

Works this paper leans on

71 extracted references · 36 canonical work pages · cited by 5 Pith papers

  1. [1]

    The staircase property: How hierarchical structure can guide deep learning.Advances in Neural Information Processing Systems, 34:26989–27002, 2021

    Emmanuel Abbe, Enric Boix-Adsera, Matthew S Brennan, Guy Bresler, and Dheeraj Nagaraj. The staircase property: How hierarchical structure can guide deep learning.Advances in Neural Information Processing Systems, 34:26989–27002, 2021

    2021

  2. [2]

    The merged-staircase property: a necessary and nearly sufficient condition for sgd learning of sparse functions on two-layer neural networks

    Emmanuel Abbe, Enric Boix Adsera, and Theodor Misiakiewicz. The merged-staircase property: a necessary and nearly sufficient condition for sgd learning of sparse functions on two-layer neural networks. InConference on Learning Theory, pages 4782–4887. PMLR, 2022

    work page 2022

  3. [3]

    Provable advantage of curriculum learning on parity targets with mixed inputs.Advances in Neural Information Processing Systems, 36:24291–24321, 2023

    Emmanuel Abbe, Elisabetta Cornacchia, and Aryo Lotfi. Provable advantage of curriculum learning on parity targets with mixed inputs.Advances in Neural Information Processing Systems, 36:24291–24321, 2023

    2023

  4. [4]

    How far can transformers reason? The locality barrier and inductive scratchpad

    Emmanuel Abbe, Samy Bengio, Aryo Lotfi, Colin Sandon, and Omid Saremi. How far can transformers reason? The locality barrier and inductive scratchpad. InAdvances in Neural Information Processing Systems, 2024

    work page 2024

  5. [5]

    Transformers learn to implement preconditioned gradient descent for in-context learning

    Kwangjun Ahn, Xiang Cheng, Hadi Daneshmand, and Suvrit Sra. Transformers learn to implement preconditioned gradient descent for in-context learning. InAdvances in Neural Information Processing Systems, volume 36, 2024

    work page 2024

  6. [6]

    Graph streaming lower bounds for parameter estimation and property testing via a streaming xor lemma

    Sepehr Assadi and Vishvajeet N. Graph streaming lower bounds for parameter estimation and property testing via a streaming xor lemma. InProceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pages 612–625, 2021

    work page 2021

  7. [7]

    The pitfalls of next-token prediction

    Gregor Bachmann and Vaishnavh Nagarajan. The pitfalls of next-token prediction. In International Conference on Machine Learning (ICML), 2024

    work page 2024

  8. [8]

    Curriculum learning

    Yoshua Bengio, J´erˆome Louradour, Ronan Collobert, and Jason Weston. Curriculum learning. InProceedings of the 26th Annual International Conference on Machine Learning, ICML ’09, page 41–48, New York, NY , USA, 2009. Association for Computing Machinery. ISBN 9781605585161. doi: 10.1145/1553374.1553380. URL https://doi.org/10.1145/ 1553374.1553380

    arXiv 2009

Show all 71 references
  1. [9]

    Separations in the representational capabilities of transformers and recurrent architectures.arXiv preprint arXiv:2406.09347, 2024

    Satwik Bhattamishra, Michael Hahn, Phil Blunsom, and Varun Kanade. Separations in the representational capabilities of transformers and recurrent architectures.arXiv preprint arXiv:2406.09347, 2024. 15

    2024 arXiv

  2. [10]

    Birth of a transformer: A memory viewpoint

    Alberto Bietti, Vivien Cabannes, Diane Bouchacourt, Herve Jegou, and Leon Bottou. Birth of a transformer: A memory viewpoint. InAdvances in Neural Information Processing Systems (NeurIPS), 2023

    2023

  3. [11]

    Data distributional properties drive emergent in-context learning in transformers

    Stephanie Chan, Adam Santoro, Andrew Lampinen, Jane Wang, Aaditya Singh, Pierre Richemond, James McClelland, and Felix Hill. Data distributional properties drive emergent in-context learning in transformers. InAdvances in neural information processing systems, 2022

    2022

  4. [12]

    Theoretical limitations of multi-layer transformer

    Lijie Chen, Binghui Peng, and Hongxun Wu. Theoretical limitations of multi-layer transformer. arXiv preprint arXiv:2412.02975, 2024

    2024 arXiv

  5. [13]

    Training dynamics of multi- head softmax attention for in-context learning: Emergence, convergence, and optimality.arXiv preprint arXiv:2402.19442, 2024

    Siyu Chen, Heejune Sheen, Tianhao Wang, and Zhuoran Yang. Training dynamics of multi- head softmax attention for in-context learning: Emergence, convergence, and optimality.arXiv preprint arXiv:2402.19442, 2024

    2024 arXiv

  6. [14]

    Unveiling induction heads: Provable training dynamics and feature learning in transformers.arXiv preprint arXiv:2409.10559, 2024

    Siyu Chen, Heejune Sheen, Tianhao Wang, and Zhuoran Yang. Unveiling induction heads: Provable training dynamics and feature learning in transformers.arXiv preprint arXiv:2409.10559, 2024

    2024 arXiv

  7. [15]

    Understand- ing the interplay between parametric and contextual knowledge for large language models

    Sitao Cheng, Liangming Pan, Xunjian Yin, Xinyi Wang, and William Yang Wang. Understand- ing the interplay between parametric and contextual knowledge for large language models. arXiv preprint arXiv:2410.08414, 2024

    2024 arXiv

  8. [16]

    Neural networks can learn represen- tations with gradient descent

    Alexandru Damian, Jason Lee, and Mahdi Soltanolkotabi. Neural networks can learn represen- tations with gradient descent. InConference on Learning Theory, pages 5413–5452. PMLR, 2022

    2022

  9. [17]

    From explicit cot to implicit cot: Learning to internalize cot step by step.arXiv preprint arXiv:2405.14838, 2024

    Yuntian Deng, Yejin Choi, and Stuart Shieber. From explicit cot to implicit cot: Learning to internalize cot step by step.arXiv preprint arXiv:2405.14838, 2024

    2024 arXiv

  10. [18]

    The llama 3 herd of models.arXiv preprint arXiv:2407.21783, 2024

    Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Amy Yang, Angela Fan, et al. The llama 3 herd of models.arXiv preprint arXiv:2407.21783, 2024

    2024 arXiv

  11. [19]

    Hwang, Soumya Sanyal, Sean Welleck, Xiang Ren, Allyson Ettinger, Zaid Harchaoui, and Yejin Choi

    Nouha Dziri, Ximing Lu, Melanie Sclar, Xiang Lorraine Li, Liwei Jiang, Bill Yuchen Lin, Peter West, Chandra Bhagavatula, Ronan Le Bras, Jena D. Hwang, Soumya Sanyal, Sean Welleck, Xiang Ren, Allyson Ettinger, Zaid Harchaoui, and Yejin Choi. Faith and fate: Limits of transforme...

    2023 arXiv

  12. [20]

    Learning and development in neural networks: The importance of starting small.Cognition, 48(1):71–99, 1993

    Jeffrey L Elman. Learning and development in neural networks: The importance of starting small.Cognition, 48(1):71–99, 1993

    1993

  13. [21]

    Towards revealing the mystery behind chain of thought: a theoretical perspective.Advances in Neural Information Processing Systems, 36, 2024

    Guhao Feng, Bohang Zhang, Yuntian Gu, Haotian Ye, Di He, and Liwei Wang. Towards revealing the mystery behind chain of thought: a theoretical perspective.Advances in Neural Information Processing Systems, 36, 2024. 16

    2024

  14. [22]

    Global convergence in training large-scale transformers.arXiv preprint arXiv:2410.23610, 2024

    Cheng Gao, Yuan Cao, Zihao Li, Yihan He, Mengdi Wang, Han Liu, Jason Matthew Klusowski, and Jianqing Fan. Global convergence in training large-scale transformers.arXiv preprint arXiv:2410.23610, 2024

    2024 arXiv

  15. [23]

    Better & faster large language models via multi-token prediction.arXiv preprint arXiv:2404.19737, 2024

    Fabian Gloeckle, Badr Youbi Idrissi, Baptiste Rozi`ere, David Lopez-Paz, and Gabriel Syn- naeve. Better & faster large language models via multi-token prediction.arXiv preprint arXiv:2404.19737, 2024

    2024 arXiv

  16. [24]

    Interleaved group products.SIAM Journal on Computing, 48(2):554–580, 2019

    William Timothy Gowers and Emanuele Viola. Interleaved group products.SIAM Journal on Computing, 48(2):554–580, 2019

    2019

  17. [25]

    Transformers learn to implement multi-step gradient descent with chain of thought.arXiv preprint arXiv:2502.21212, 2025

    Jianhao Huang, Zixuan Wang, and Jason D Lee. Transformers learn to implement multi-step gradient descent with chain of thought.arXiv preprint arXiv:2502.21212, 2025

    2025 arXiv

  18. [26]

    In-context convergence of transformers.arXiv preprint arXiv:2310.05249, 2023

    Yu Huang, Yuan Cheng, and Yingbin Liang. In-context convergence of transformers.arXiv preprint arXiv:2310.05249, 2023

    2023 arXiv

  19. [27]

    Mas- sively parallel computation: Algorithms and applications.Foundations and Trends® in Optimization, 5(4):340–417, 2023

    Sungjin Im, Ravi Kumar, Silvio Lattanzi, Benjamin Moseley, and Sergei Vassilvitskii. Mas- sively parallel computation: Algorithms and applications.Foundations and Trends® in Optimization, 5(4):340–417, 2023

    2023

  20. [28]

    Vision transformers provably learn spatial structure

    Samy Jelassi, Michael Sander, and Yuanzhi Li. Vision transformers provably learn spatial structure. InAdvances in Neural Information Processing Systems (NeurIPS), 2022

    2022

  21. [29]

    Repeat after me: Transformers are better than state space models at copying.arXiv preprint arXiv:2402.01032, 2024

    Samy Jelassi, David Brandfonbrener, Sham M Kakade, and Eran Malach. Repeat after me: Transformers are better than state space models at copying.arXiv preprint arXiv:2402.01032, 2024

    2024 arXiv

  22. [30]

    Efficient noise-tolerant learning from statistical queries.J

    Michael Kearns. Efficient noise-tolerant learning from statistical queries.J. ACM, 45(6): 983–1006, 1998

    1998

  23. [31]

    Transformers provably solve parity efficiently with chain of thought.arXiv preprint arXiv:2410.08633, 2024

    Juno Kim and Taiji Suzuki. Transformers provably solve parity efficiently with chain of thought.arXiv preprint arXiv:2410.08633, 2024

    2024 arXiv

  24. [32]

    Adam: A method for stochastic optimization.arXiv preprint arXiv:1412.6980, 2014

    Diederik P Kingma. Adam: A method for stochastic optimization.arXiv preprint arXiv:1412.6980, 2014

    2014 arXiv

  25. [33]

    Learning to reason and memorize with self-notes

    Jack Lanchantin, Shubham Toshniwal, Jason Weston, and Sainbayar Sukhbaatar. Learning to reason and memorize with self-notes. InAdvances in Neural Information Processing Systems, volume 36, 2024

    2024

  26. [34]

    Solving quantitative reasoning problems with language models

    Aitor Lewkowycz, Anders Andreassen, David Dohan, Ethan Dyer, Henryk Michalewski, Vinay Ramasesh, Ambrose Slone, Cem Anil, Imanol Schlag, Theo Gutman-Solo, Yuhuai Wu, Behnam Neyshabur, Guy Gur-Ari, and Vedant Misra. Solving quantitative reasoning problems with language models. ...

    2022

  27. [35]

    How do transformers learn topic structure: Towards a mechanistic understanding

    Yuchen Li, Yuanzhi Li, and Andrej Risteski. How do transformers learn topic structure: Towards a mechanistic understanding. InICML, 2023. 17

    2023

  28. [36]

    Chain of thought empowers transformers to solve inherently serial problems.arXiv preprint arXiv:2402.12875, 2024

    Zhiyuan Li, Hong Liu, Denny Zhou, and Tengyu Ma. Chain of thought empowers transformers to solve inherently serial problems.arXiv preprint arXiv:2402.12875, 2024

    2024 arXiv

  29. [37]

    Let’s verify step by step.arXiv preprint arXiv:2305.20050, 2023

    Hunter Lightman, Vineet Kosaraju, Yura Burda, Harri Edwards, Bowen Baker, Teddy Lee, Jan Leike, John Schulman, Ilya Sutskever, and Karl Cobbe. Let’s verify step by step.arXiv preprint arXiv:2305.20050, 2023

    2023 arXiv

  30. [38]

    Deepseek-v3 technical report.arXiv preprint arXiv:2412.19437, 2024

    Aixin Liu, Bei Feng, Bing Xue, Bingxuan Wang, Bochao Wu, Chengda Lu, Chenggang Zhao, Chengqi Deng, Chenyu Zhang, Chong Ruan, et al. Deepseek-v3 technical report.arXiv preprint arXiv:2412.19437, 2024

    2024 arXiv

  31. [39]

    Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang

    Bingbin Liu, Jordan T. Ash, Surbhi Goel, Akshay Krishnamurthy, and Cyril Zhang. Transform- ers learn shortcuts to automata. InThe Eleventh International Conference on Learning Repre- sentations, 2023. URLhttps://openreview.net/forum?id=De4FYqjFueZ

    2023

  32. [40]

    Regmix: Data mixture as regression for language model pre-training

    Qian Liu, Xiaosen Zheng, Niklas Muennighoff, Guangtao Zeng, Longxu Dou, Tianyu Pang, Jing Jiang, and Min Lin. Regmix: Data mixture as regression for language model pre-training. arXiv preprint arXiv:2407.01492, 2024

    2024 arXiv

  33. [41]

    The expresssive power of transformers with chain of thought.arXiv preprint arXiv:2310.07923, 2023

    William Merrill and Ashish Sabharwal. The expresssive power of transformers with chain of thought.arXiv preprint arXiv:2310.07923, 2023

    2023 arXiv

  34. [42]

    The parallelism tradeoff: Limitations of log-precision transformers.Transactions of the Association for Computational Linguistics, 11:531–545, 2023

    William Merrill and Ashish Sabharwal. The parallelism tradeoff: Limitations of log-precision transformers.Transactions of the Association for Computational Linguistics, 11:531–545, 2023

    2023

  35. [43]

    How transformers learn causal structure with gradient descent

    Eshaan Nichani, Alex Damian, and Jason D Lee. How transformers learn causal structure with gradient descent. InInternational Conference on Machine Learning (ICML), 2024

    2024

  36. [44]

    Understanding factual recall in transformers via associative memories.arXiv preprint arXiv:2412.06538, 2024

    Eshaan Nichani, Jason D Lee, and Alberto Bietti. Understanding factual recall in transformers via associative memories.arXiv preprint arXiv:2412.06538, 2024

    2024 arXiv

  37. [45]

    Rounds in communication complexity revisited.SIAM Journal on Computing, 22(1):211–219, 1993

    Noam Nisan and Avi Wigderson. Rounds in communication complexity revisited.SIAM Journal on Computing, 22(1):211–219, 1993. doi: 10.1137/0222016. URL https://doi. org/10.1137/0222016

    1993 doi

  38. [46]

    Show your work: scratchpads for intermediate computation with language models.arXiv preprint arXiv:2112.00114, 2021

    Maxwell Nye, Anders Johan Andreassen, Guy Gur-Ari, Henryk Michalewski, Jacob Austin, David Bieber, David Dohan, Aitor Lewkowycz, Maarten Bosma, David Luan, Charles Sutton, and Augustus Odena. Show your work: scratchpads for intermediate computation with language models.arXiv p...

    2021 arXiv

  39. [47]

    In-context learning and induction heads.Transformer Cir- cuits Thread, 2022

    Catherine Olsson, Nelson Elhage, Neel Nanda, Nicholas Joseph, Nova DasSarma, Tom Henighan, Ben Mann, Amanda Askell, Yuntao Bai, Anna Chen, Tom Conerly, Dawn Drain, Deep Ganguli, Zac Hatfield-Dodds, Danny Hernandez, Scott Johnston, Andy Jones, Jackson Kernion, Liane Lovitt, Kam...

    2022

  40. [48]

    Pro- gressive distillation induces an implicit curriculum.arXiv preprint arXiv:2410.05464, 2024

    Abhishek Panigrahi, Bingbin Liu, Sadhika Malladi, Andrej Risteski, and Surbhi Goel. Pro- gressive distillation induces an implicit curriculum.arXiv preprint arXiv:2410.05464, 2024

    2024 arXiv

  41. [49]

    Papadimitriou and Michael Sipser

    Christos H. Papadimitriou and Michael Sipser. Communication complexity.Journal of Computer and System Sciences, 28(2):260–269, 1984. ISSN 0022-0000. doi: https://doi.org/10. 1016/0022-0000(84)90069-2. URL https://www.sciencedirect.com/science/ article/pii/0022000084900692

    1984

  42. [50]

    On limitations of the trans- former architecture

    Binghui Peng, Srini Narayanan, and Christos Papadimitriou. On limitations of the trans- former architecture. InFirst Conference on Language Modeling, 2024. URL https: //openreview.net/forum?id=KidynPuLNW

    2024

  43. [51]

    Learning and transferring sparse contextual bi- grams with linear transformers

    Yunwei Ren, Zixuan Wang, and Jason D Lee. Learning and transferring sparse contextual bi- grams with linear transformers. InThe Thirty-eighth Annual Conference on Neural Information Processing Systems, 2024

    2024

  44. [52]

    Representational strengths and limitations of transformers

    Clayton Sanford, Daniel Hsu, and Matus Telgarsky. Representational strengths and limitations of transformers. InAdvances in Neural Information Processing Systems 36, 2023

    2023

  45. [53]

    Understanding transformer reasoning capabilities via graph algorithms.arXiv preprint arXiv:2405.18512, 2024

    Clayton Sanford, Bahare Fatemi, Ethan Hall, Anton Tsitsulin, Mehran Kazemi, Jonathan Hal- crow, Bryan Perozzi, and Vahab Mirrokni. Understanding transformer reasoning capabilities via graph algorithms.arXiv preprint arXiv:2405.18512, 2024

    2024 arXiv

  46. [54]

    Transformers, parallel computation, and logarithmic depth

    Clayton Sanford, Daniel Hsu, and Matus Telgarsky. Transformers, parallel computation, and logarithmic depth. InForty-First International Conference on Machine Learning, 2024

    2024

  47. [55]

    End-to-end memory networks

    Sainbayar Sukhbaatar, Jason Weston, and Rob Fergus. End-to-end memory networks. In Advances in Neural Information Processing Systems, volume 28, 2015

    2015

  48. [56]

    Characterizing statistical query learning: simplified notions and proofs

    Bal´azs Sz¨or´enyi. Characterizing statistical query learning: simplified notions and proofs. In International Conference on Algorithmic Learning Theory, pages 186–200. Springer, 2009

    2009

  49. [57]

    Scan and snap: Understanding training dynamics and token composition in 1-layer transformer

    Yuandong Tian, Yiping Wang, Beidi Chen, and Simon Du. Scan and snap: Understanding training dynamics and token composition in 1-layer transformer. InAdvances in Neural Information Processing Systems (NeurIPS), 2023

    2023

  50. [58]

    Solving math word problems with process-and outcome-based feedback.arXiv preprint arXiv:2211.14275, 2022

    Jonathan Uesato, Nate Kushman, Ramana Kumar, Francis Song, Noah Siegel, Lisa Wang, Antonia Creswell, Geoffrey Irving, and Irina Higgins. Solving math word problems with process-and outcome-based feedback.arXiv preprint arXiv:2211.14275, 2022

    2022 arXiv

  51. [59]

    Zixuan Wang, Stanley Wei, Daniel Hsu, and Jason D. Lee. Transformers provably learn sparse token selection while fully-connected nets cannot. InICML, 2024

    2024

  52. [60]

    Chain-of-thought prompting elicits reasoning in large language models

    Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, and Denny Zhou. Chain-of-thought prompting elicits reasoning in large language models. In Advances in Neural Information Processing Systems, volume 35, 2022

    2022

  53. [61]

    From sparse dependence to sparse attention: unveiling how chain-of-thought enhances transformer sample efficiency

    Kaiyue Wen, Huaqing Zhang, Hongzhou Lin, and Jingzhao Zhang. From sparse dependence to sparse attention: unveiling how chain-of-thought enhances transformer sample efficiency. arXiv preprint arXiv:2410.05459, 2024. 19

    2024 arXiv

  54. [62]

    Memory networks.arXiv preprint arXiv:1410.3916, 2014

    Jason Weston, Sumit Chopra, and Antoine Bordes. Memory networks.arXiv preprint arXiv:1410.3916, 2014

    2014 arXiv

  55. [63]

    Towards ai-complete question answering: A set of prerequisite toy tasks.arXiv preprint arXiv:1502.05698, 2015

    Jason Weston, Antoine Bordes, Sumit Chopra, Alexander M Rush, Bart Van Merri ¨enboer, Armand Joulin, and Tomas Mikolov. Towards ai-complete question answering: A set of prerequisite toy tasks.arXiv preprint arXiv:1502.05698, 2015

    2015 arXiv

  56. [64]

    Doremi: Optimizing data mixtures speeds up language model pretraining

    Sang Michael Xie, Hieu Pham, Xuanyi Dong, Nan Du, Hanxiao Liu, Yifeng Lu, Percy S Liang, Quoc V Le, Tengyu Ma, and Adams Wei Yu. Doremi: Optimizing data mixtures speeds up language model pretraining. InAdvances in Neural Information Processing Systems, volume 36, 2024

    2024

  57. [65]

    Do large language models latently perform multi-hop reasoning?arXiv preprint arXiv:2402.16837, 2024

    Sohee Yang, Elena Gribovskaya, Nora Kassner, Mor Geva, and Sebastian Riedel. Do large language models latently perform multi-hop reasoning?arXiv preprint arXiv:2402.16837, 2024

    2024 arXiv

  58. [66]

    Tree of thoughts: deliberate problem solving with large language models

    Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Tom Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: deliberate problem solving with large language models. Advances in Neural Information Processing Systems, 36, 2024

    2024

  59. [67]

    Pointer chasing via triangular discrimination.Combinatorics, Probability and Computing, 29(4):485–494, 2020

    Amir Yehudayoff. Pointer chasing via triangular discrimination.Combinatorics, Probability and Computing, 29(4):485–494, 2020

    2020

  60. [68]

    exact gradients

    Ruiqi Zhang, Spencer Frei, and Peter L Bartlett. Trained transformers learn linear models in-context.arXiv preprint arXiv:2306.09927, 2023. 20 Contents 1 Introduction 1 1.1 Related Work: Transformer Theory . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.2 Related Work:...

    2023 arXiv

  61. [69]

    Then we have for any ℓ′ < ℓ0, the infinity norm of theℓ 0th stage gradient is upper bounded by ∥∇W (ℓ′) KQ L(ℓ)∥∞ ≤6β 0k(kN L)3/2ϵ,∀ℓ > ℓ′. Proof.Recall the gradient for a single sample(X, i, j) ∇W (ℓ′) KQ L(ℓ) =−   X s′∈[N] 1{s′ = hop2ℓ−1 i (j)} − S(Ψ⊤ ℓ f (ℓ) (i,j))s′ ∇W (...

  62. [70]

    Since the softmax in layer ℓ is nearly saturated and thus close to one-hot, the update norm is very small and can be bounded as noise terms

    During the tth gradient step, layers ℓ < twill still be updated. Since the softmax in layer ℓ is nearly saturated and thus close to one-hot, the update norm is very small and can be bounded as noise terms

  63. [71]

    That means in the tth gradient step, there will be some small gradient updates for later layersℓ′ ≥t introduced by the perturbation

    Due to the non-saturation error, the input is not ideal one-hot vectors for each hop. That means in the tth gradient step, there will be some small gradient updates for later layersℓ′ ≥t introduced by the perturbation. We can also upper bound this amount of noise. The full pro...

Pith tools

Reviewed August 7, 2026 · model on record in the stance chip above.