Pith. sign in

REVIEW 2 major objections 4 minor 23 references

From Expressivity to Sample Complexity: Narrow Teachers for Transformers via C-RASP

T0 review · 2 major / 4 minor · reviewed 2026-07-14 · grok-4.5

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

Pith's one-line read C-RASP constructions give sample-complexity bounds for learning with wider Transformers via narrow teachers.

desk verdict Clean conversion of C-RASP size facts into PAC sample-complexity upper bounds via a transparent multi-layer embedding argument; useful theory bridge, idealized learner and single-embedding volume are the real limits. read the letter →

arxiv 2607.11760 v1 pith:FC47AFDE submitted 2026-07-13 cs.LG cs.CL

Michael Rizvi-Martel , Satwik Bhattamishra , Guillaume Rabusseau , Michael Hahn This is my paper
classification cs.LGcs.CL
keywords TransformerssamplecomplexityC-RASPnarrowteachersexpressivitylearnabilitylosslandscapequantizednetworks
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

Most theory about Transformers tells us what functions they can encode with carefully chosen weights, but not whether those functions are easy to learn from data. This paper bridges that gap for a large class of constructions called C-RASP programs, which compile into fixed-precision Transformers. It shows that if a narrow teacher Transformer can implement a C-RASP program, then a wider student of sufficient depth can embed that teacher with a quantifiable number of free parameters. Under an idealized guess-and-check learner that samples quantized weights until training error is zero, the volume of those embeddings yields an explicit sample-complexity bound: roughly order L d log Q / epsilon examples suffice for the student to generalize. The same bound explains why short constant-size programs such as Dyck-1 are readily learned.

What carries the argument

The constraint-counting argument (Lemma B.2 and Theorem B.1) that embeds a narrow teacher into a student residual stream by zeroing interfering dimensions, then preserves the teacher block with weak-identity layers; the resulting free-parameter count M_C-RASP lower-bounds the volume of teacher-equivalent solutions.

What would settle it

Train a width-d Transformer on Dyck-1 or a_n b_n with N well below the predicted O(L d / epsilon) bound and check whether zero-training-error solutions still generalize, or measure the empirical volume of teacher-equivalent weights under quantization.

Watch

Extended reading notes

Core claim

Any C-RASP program of depth n with m variables can be realized by a narrow single-head teacher of width 2m+c. Embedding that teacher into a wider, deeper Q-quantized student produces a positive-volume set of teacher-equivalent parameters whose measure is at least Q to the minus M_C-RASP. Conditioning a uniform prior on zero training error therefore yields a sample complexity of order (L d log Q)/epsilon that guarantees small true risk with high probability.

Load-bearing premise

The learner is idealized Guess-and-Check that draws quantized weights uniformly until training error vanishes; real gradient methods may not sample from that posterior.

Editorial extensions

If this is right

  • Constant-depth C-RASP languages such as Dyck-1 become learnable with sample size linear in width rather than quadratic.
  • Any future expressivity construction that admits a narrow C-RASP (or equivalent) teacher immediately inherits a concrete sample-complexity upper bound for wider students.
  • The same volume argument can be applied layer-wise to multi-head or deeper residual architectures once their free-parameter counts are known.
  • Length generalization for short formal languages is predicted to improve once student width exceeds the teacher width needed by the C-RASP program.

Reading between the lines

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

  • If many distinct embeddings of the same teacher exist, the true volume is larger and the sample bound can be tightened further.
  • The same counting technique should extend to state-space models once their residual-stream constraints are written down.
  • Empirical loss-landscape measurements on formal languages would test whether the predicted volume of good solutions actually appears under gradient descent.
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

2 major / 4 minor

Summary. The paper derives PAC-style sample-complexity upper bounds for learning C-RASP programs with Transformers by combining C-RASP expressivity constructions with the narrow-teacher volume argument of Buzaglo et al. It shows that a depth-n C-RASP program with m variables can be realized by a constant-width (2m+c) single-head teacher, then counts the number of parameter constraints needed to embed that teacher into any wider/deeper Q-quantized student (zero-padding unused residual dimensions and weak-identity layers). The resulting volume lower bound is plugged into a Guess-and-Check posterior-sampling lemma to obtain Theorem 2.1 / B.2: N = O((L d log Q)/ε) samples suffice for LD < ε with high probability. The Dyck-1 program is given as a concrete illustration.

Significance. The work is a clean first bridge from C-RASP expressivity results to concrete sample-complexity statements. The embedding construction (Lemma B.2, Theorem B.1) is elementary, fully spelled out, and algebraically checkable; the reduction to the Buzaglo et al. lemma is direct. If the idealized Guess-and-Check model is accepted as a proxy for landscape volume, the bound improves on naïve Occam arguments (O(Ld) vs O(Ld^{2})) and supplies a principled reason why constant-size formal-language constructions are easily learned. The limitations (single embedding, quantized G&C learner) are stated openly, so the contribution is modest but genuine and usable as a template for later tighter analyses.

major comments (2)
  1. Fact A.1 and Theorem 2.1 leave the absolute constant c in the teacher width 2m+c unspecified. Because M_C-RASP is linear in (2m+c), an unspecified c makes the leading constant of the sample-complexity bound non-constructive. A short derivation or citation of the precise additive overhead from the Yang & Chiang constructions would make the bound fully explicit.
  2. The volume lower bound of Theorem B.1 counts only a single embedding of the teacher (zero-padding one particular block of residual dimensions). The Conclusion correctly notes that many more embeddings may exist; without even a crude multiplicity factor the stated O(Ld log Q / ε) bound is therefore only a first upper bound on sample complexity. A remark quantifying how multiplicity would improve the exponent would strengthen the claim.
minor comments (4)
  1. In the statement of Theorem 2.1 the quantity M_C-RASP is written with an unclosed parenthesis in the middle term; the same expression appears correctly in Corollary B.2. Align the two displays.
  2. Algorithm 1 uses the comparison C_r(i) > C_l(i) while Definition A.1 lists only ≤; a one-line remark that the missing predicates are obtained by Boolean combinations would remove the small inconsistency.
  3. The parameter-count formula M(Θ) in §A.3 is never used after it is introduced; either drop it or cite it when deriving the constraint counts.
  4. A few typographical slips remain (“compiliation”, missing spaces around “MC-RASP”, inconsistent use of T F_θ vs TF_θ). A light copy-edit pass would suffice.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: sample-complexity bound is a direct constraint-counting application of an external PAC lemma to independently published C-RASP constructions.

full rationale

The derivation chain is self-contained and non-circular. Theorem 2.1 / B.2 is obtained by (i) fixing parameters so that a wide student embeds a narrow teacher (Lemma B.2, explicit zero-padding of W_Q, W_K, W_V, W_O, W_1, W_2), (ii) inducting over L* teacher layers and L-L* weak-identity layers (Theorem B.1), (iii) specializing dimensions via Fact A.1 / Yang & Chiang constructions (d* = 2m+c, h*=1) to obtain M_C-RASP, and (iv) plugging the resulting volume lower bound p̃ ≥ Q^{-M} into the external G&C generalization lemma of Buzaglo et al. (Lemma B.1). No quantity is fitted to data and then re-presented as a prediction; no uniqueness theorem is imported from the authors’ own prior work to forbid alternatives; the C-RASP size facts and the PAC lemma are external, independently published results. Self-citations (e.g., Rizvi et al. 2024) appear only as related expressivity background and are not load-bearing for the sample-complexity claim. The idealized Guess-and-Check learner and single-embedding volume estimate are openly stated limitations, not hidden circular reductions. Score 0 is therefore appropriate.

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

The central claim is a pure counting + PAC argument. It inherits the Guess-and-Check generalization lemma and the C-RASP-to-Transformer size facts from prior literature; the only new ingredients are the explicit constraint counts for embedding a narrow Transformer teacher. No free parameters are fitted to data. The absolute constant c and the finite quantization set Q are modeling choices required for the finite-hypothesis-class argument.

free parameters (2)
  • absolute constant c in teacher width 2m+c
    Left unspecified; arises from the concrete C-RASP compilation of Yang & Chiang. Affects the precise leading term of M_C-RASP but not the O(Ld log Q) asymptotic.
  • quantization cardinality Q
    Finite set size that makes the hypothesis class finite; appears in every sample-complexity expression. Chosen by the modeler, not fitted.
assumptions (4)
  • domain assumption Lemma B.1 (G&C generalization): N > (-log p̃ + 3 log(2/δ))/ε implies posterior sampling yields LD < ε w.p. ≥ 1-δ
    Imported verbatim from Buzaglo et al. 2024; the entire sample-complexity claim rests on it.
  • domain assumption A C-RASP program of depth n with m variables is realized by a fixed-precision Transformer of depth n and width 2m+O(1)
    Fact A.1 / Theorem A.1, taken from Yang & Chiang / Yang et al.; supplies the narrow-teacher dimensions.
  • ad hoc to paper All network parameters lie in a finite set Q containing 0 with |Q| ≤ Q
    Definition 2.1; required to turn volume into a discrete probability Q^-M.
  • domain assumption Uniform prior over Q-quantized weights; posterior is the prior conditioned on zero training error
    Standard in the Guess-and-Check framework of Chiang et al. / Buzaglo et al.; not justified for gradient descent.

how reviews work

0 comments
Cite this review

Pith. "Pith review of From Expressivity to Sample Complexity: Narrow Teachers for Transformers via C-RASP." pith.science (2026). https://pith.science/paper/FC47AFDE

@misc{pith2026260711760,
  author       = {Pith},
  title        = {Pith review of: From Expressivity to Sample Complexity: Narrow Teachers for Transformers via C-RASP},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/FC47AFDE}},
  note         = {Machine review of arXiv:2607.11760}
}
read the original abstract

A theoretical understanding of Transformers is crucial to better understand the capacities and limitations of large language models (LLMs). There is much work analyzing the expressivity of attention-based models. By proposing handcrafted weights or using computational complexity arguments, a large amount of past theoretical works have sought to characterize which tasks are and which are not in the hypothesis class of Transformer models. However, little work investigates the learnability of such solutions. In this work, we make progress towards this goal. Inspired by recent loss landscape analysis work, we propose preliminary sample complexity bounds for learning C-RASP constructions with Transformers.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

23 extracted references · 7 linked inside Pith

  1. [2]

    arXiv preprint arXiv:2506.03085 , year=

    Non-Asymptotic Length Generalization , author=. arXiv preprint arXiv:2506.03085 , year=

    arXiv

  2. [3]

    Advances in neural information processing systems , volume=

    Attention is all you need , author=. Advances in neural information processing systems , volume=

  3. [4]

    arXiv preprint arXiv:2410.02140 , year=

    A formal framework for understanding length generalization in transformers , author=. arXiv preprint arXiv:2410.02140 , year=

    arXiv

  4. [6]

    arXiv preprint arXiv:2310.16028 , year=

    What algorithms can transformers learn? a study in length generalization , author=. arXiv preprint arXiv:2310.16028 , year=

    arXiv

  5. [7]

    The Eleventh International Conference on Learning Representations , year=

    Loss landscapes are all you need: Neural network generalization can be explained without the implicit bias of gradient descent , author=. The Eleventh International Conference on Learning Representations , year=

  6. [8]

    International Conference on Machine Learning , pages=

    Inductive biases and variable creation in self-attention mechanisms , author=. International Conference on Machine Learning , pages=. 2022 , organization=

    2022

  7. [9]

    International Conference on Machine Learning , pages=

    Thinking like transformers , author=. International Conference on Machine Learning , pages=. 2021 , organization=

    2021

  8. [10]

    International Conference on Artificial Intelligence and Statistics , pages=

    Sequence length independent norm-based generalization bounds for transformers , author=. International Conference on Artificial Intelligence and Statistics , pages=. 2024 , organization=

    2024

Show all 23 references
  1. [12]

    Transactions of the Association for Computational Linguistics , volume=

    Theoretical limitations of self-attention in neural sequence models , author=. Transactions of the Association for Computational Linguistics , volume=. 2020 , publisher=

    2020

  2. [14]

    Advances in Neural Information Processing Systems , volume=

    Separations in the representational capabilities of transformers and recurrent architectures , author=. Advances in Neural Information Processing Systems , volume=

  3. [15]

    Journal of Machine Learning Research , volume=

    Attention is turing-complete , author=. Journal of Machine Learning Research , volume=

  4. [16]

    arXiv preprint arXiv:2402.09963 , year=

    Why are sensitive functions hard for transformers? , author=. arXiv preprint arXiv:2402.09963 , year=

    arXiv

  5. [17]

    Transactions of the Association for Computational Linguistics , volume=

    Saturated transformers are constant-depth threshold circuits , author=. Transactions of the Association for Computational Linguistics , volume=. 2022 , publisher=

    2022

  6. [19]

    On the A bility and L imitations of T ransformers to R ecognize F ormal L anguages

    Satwik Bhattamishra, Kabir Ahuja, and Navin Goyal. On the A bility and L imitations of T ransformers to R ecognize F ormal L anguages. In Bonnie Webber, Trevor Cohn, Yulan He, and Yang Liu, editors, Proceedings of the 2020 Conference on Empirical Methods in Natural Language Pr...

    2020 doi

  7. [20]

    Separations in the representational capabilities of transformers and recurrent architectures

    Satwik Bhattamishra, Michael Hahn, Phil Blunsom, and Varun Kanade. Separations in the representational capabilities of transformers and recurrent architectures. Advances in Neural Information Processing Systems, 37: 0 36002--36045, 2024

    2024

  8. [21]

    How uniform random weights induce non-uniform bias: Typical interpolating neural networks generalize with narrow teachers

    Gon Buzaglo, Itamar Harel, Mor Shpigel Nacson, Alon Brutzkus, Nathan Srebro, and Daniel Soudry. How uniform random weights induce non-uniform bias: Typical interpolating neural networks generalize with narrow teachers. arXiv preprint arXiv:2402.06323, 2024

    2024 arXiv

  9. [22]

    Loss landscapes are all you need: Neural network generalization can be explained without the implicit bias of gradient descent

    Ping-yeh Chiang, Renkun Ni, David Yu Miller, Arpit Bansal, Jonas Geiping, Micah Goldblum, and Tom Goldstein. Loss landscapes are all you need: Neural network generalization can be explained without the implicit bias of gradient descent. In The Eleventh International Conference...

    2022

  10. [23]

    Theoretical limitations of self-attention in neural sequence models

    Michael Hahn. Theoretical limitations of self-attention in neural sequence models. Transactions of the Association for Computational Linguistics, 8: 0 156--171, 2020

    2020

  11. [24]

    Saturated transformers are constant-depth threshold circuits

    William Merrill, Ashish Sabharwal, and Noah A Smith. Saturated transformers are constant-depth threshold circuits. Transactions of the Association for Computational Linguistics, 10: 0 843--856, 2022

    2022

  12. [25]

    Simulating weighted automata over sequences and trees with transformers

    Michael Rizvi, Maude Lizaire, Clara Lacroce, and Guillaume Rabusseau. Simulating weighted automata over sequences and trees with transformers. arXiv preprint arXiv:2403.09728, 2024

    2024 arXiv

  13. [26]

    Thinking like transformers

    Gail Weiss, Yoav Goldberg, and Eran Yahav. Thinking like transformers. In International Conference on Machine Learning, pages 11080--11090. PMLR, 2021

    2021

  14. [27]

    Counting like transformers: Compiling temporal counting logic into softmax transformers

    Andy Yang and David Chiang. Counting like transformers: Compiling temporal counting logic into softmax transformers. arXiv preprint arXiv:2404.04393, 2024

    2024 arXiv

  15. [28]

    Knee-deep in c-rasp: A transformer depth hierarchy

    Andy Yang, Micha \"e l Cadilhac, and David Chiang. Knee-deep in c-rasp: A transformer depth hierarchy. arXiv preprint arXiv:2506.16055, 2025

    2025

Pith tools

Reviewed July 14, 2026 · model on record in the stance chip above.