{"id":"91d083c1-9b7b-477c-8574-9e956a0090a6","arxiv_id":"2607.11760","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":2,"one_line_summary":"Embedding a narrow C-RASP teacher into a wider quantized Transformer yields sample complexity O((L d log Q)/ε) under posterior sampling of zero-training-error models.","lead":"The paper turns known C-RASP expressivity constructions for Transformers into sample-complexity upper bounds by counting how many quantized parameters must be fixed to embed a narrow teacher into a wider student. It suggests why constant-size formal languages like Dyck-1 can be learned with relatively few samples under a guess-and-check model.","discovery_kind":"extension","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified","rationale":"The reader's weakest-assumption diagnosis (G&C + single embedding) is accurate and already reflected in the paper's own Conclusion. Because the theorem is carefully scoped to the posterior PS rather than to gradient descent, those limitations affect only the interpretation and tightness, not the correctness of the formal statement. The elementary linear-algebra constructions check out, the rewrite that produces the displayed MC-RASP expression is algebraically identical to the general M of Theorem B.1, and no hidden dependence on sequence length or vocabulary size enters the leading term. Consequently the existing CONDITIONAL verdict, low correctness risk, and high confidence remain appropriate; no adjustment is required.","tokens_in":10138,"tokens_out":452,"duration_ms":58805,"concrete_test":"Fix the concrete Dyck-1 program (n=7, m=9) and expand every block matrix appearing in the 1-layer construction of Lemma B.2 with h*=1, d_k=d_ff=d, d*=2m+c. Count the exactly constrained entries and verify that the per-layer total equals d*^2 + 5 d* d + 2d; any discrepancy larger than the O(1) terms absorbed by c would falsify the MC-RASP formula used in the main bound.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim (Theorem 2.1/B.2) is a PAC sample-complexity upper bound that holds strictly for the Guess-and-Check posterior over Q-quantized weights. After checking the zero-padding constructions (Lemma B.2), the inductive multi-layer extension (Theorem B.1), the algebraic simplification that recovers MC-RASP, and the direct invocation of the Buzaglo et al. lemma, the counting and the probability lower bound ~p ≥ Q^{-M} appear correct. The single-embedding volume estimate and the idealized learner are openly acknowledged limitations on tightness and practical transfer; they do not create an internal inconsistency or false claim inside the stated theorem.","agreement_with_reader":"agree"},"referee_report":{"model":"grok-4.5","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.","tokens_in":10315,"tokens_out":901,"duration_ms":7343,"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":[{"comment":"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.","section":null},{"comment":"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.","section":null}],"minor_comments":[{"comment":"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.","section":null},{"comment":"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.","section":null},{"comment":"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.","section":null},{"comment":"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.","section":null}],"recommendation":"minor_revision","confidential_remarks":"The manuscript is short and the technical novelty is modest (constraint counting + an off-the-shelf PAC lemma). It is nevertheless correct, clearly written, and fills a genuine gap between expressivity and learnability. Suitable for a short-format venue or a workshop track; for a full journal it would benefit from either a multiplicity argument or a small empirical check of the volume claim."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"The one thing worth knowing is that this paper turns existing C-RASP expressivity constructions into explicit PAC sample-complexity upper bounds for quantized Transformers. Theorem 2.1 / B.2 is the payoff: for a depth-n program with m variables, any wider/deeper single-head student of width d needs only O((L d log Q)/ε) samples under the Guess-and-Check posterior to get true risk < ε with high probability.\n\nWhat is new is the multi-layer embedding (Lemma B.2 + Theorem B.1). They carefully zero unused dimensions so the residual stream keeps a clean teacher block, then use weak-identity layers for the extra depth. The algebra that produces M_C-RASP is elementary and checkable; the reduction through Buzaglo et al.’s volume lemma is direct. The Dyck-1 example shows the bound improves on a naïve Occam count (O(Ld) vs O(Ld^{2})). Citations to Yang & Chiang and Buzaglo are used correctly; the circularity burden is low.\n\nSoft spots are real but openly stated and do not break the theorem. The learner is pure Guess-and-Check over a finite Q-grid; nothing is claimed about gradient descent. The volume lower bound counts only one embedding, so the sample-complexity number is not tight. The absolute constant c in teacher width 2m+c is left unspecified, and there are zero experiments. These limit practical transfer and tightness, not correctness of the stated claim.\n\nThis is for people who already care about RASP/C-RASP and want a first quantitative handle on learnability of those constructions. The math is solid enough that a serious editor should send it to referees; they will ask for a clearer c and a tighter volume argument, but the core contribution is already there. I would engage with it and cite the embedding lemmas if I am writing about Transformer sample complexity.","headline":"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.","tokens_in":10947,"tokens_out":505,"would_cite":true,"duration_ms":4502,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"grok-4.5","headline":"C-RASP constructions give sample-complexity bounds for learning with wider Transformers via narrow teachers.","keywords":["Transformers","sample complexity","C-RASP","narrow teachers","expressivity","learnability","loss landscape","quantized networks"],"falsifier":"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.","tokens_in":11034,"feed_emoji":"📐","tokens_out":836,"duration_ms":6458,"temperature":0.7,"pith_summary":"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.","feed_headline":"Narrow C-RASP teachers give sample bounds for wide Transformers","feed_subtitle":"A volume argument turns expressivity constructions into concrete O(Ld/eps) learning guarantees.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"fun_headline_variants":["Narrow C-RASP teachers convert expressivity into Transformer sample bounds","C-RASP constructions yield O(Ld/eps) sample complexity via narrow teachers","Volume argument turns C-RASP teachers into concrete learning guarantees","Narrow single-head teachers give sample bounds for wide Transformers","Embedding C-RASP teachers produces positive-volume sample complexity results"],"cache_read_input_tokens":128,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Narrow C-RASP teachers convert expressivity into Transformer sample bounds","C-RASP constructions yield O(Ld/eps) sample complexity via narrow teachers","Volume argument turns C-RASP teachers into concrete learning guarantees","Narrow single-head teachers give sample bounds for wide Transformers","Embedding C-RASP teachers produces positive-volume sample complexity results"]},"model":"grok-4.5","effort":"low","cost_usd":0.00387,"raw_usage":{"total_tokens":1127,"prompt_tokens":675,"num_sources_used":0,"completion_tokens":95,"cost_in_usd_ticks":38700000,"prompt_tokens_details":{"text_tokens":675,"audio_tokens":0,"image_tokens":0,"cached_tokens":128},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":357,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":675,"tokens_out":95,"duration_ms":3195,"temperature":1.0,"reasoning_tokens":357,"cache_read_input_tokens":128,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-14T03:22:05.820519+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"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.","supporting_citations":[],"review_version":1}