{"id":"f1b6853a-df98-4241-910b-832eac34e21f","arxiv_id":"2607.19573","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":4.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Structural generalization, formally defined as unbounded evaluation of a finite compositional rule set, is NC^1-hard, so pure transformers (learnable class ⊆ TC^0) cannot learn it if TC^0 ≠ NC^1.","lead":"The paper defines structural generalization as error-free evaluation of every expression formed by a finite set of compositional rules, then shows this task is NC^1-hard. Since pure transformers can only learn TC^0 functions under the assumed separation TC^0 ≠ NC^1, it concludes they cannot learn structural generalization, and that benchmarks cannot tell learned rules from hand-injected ones.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The impossibility rests entirely on the unproved Kraus et al. learnability ceiling; if that ceiling is wrong or inapplicable to trained Transformers, Proposition 6 falls.","rationale":"The reader's weakest_assumption identifies precisely the same load-bearing point: the impossibility depends on the Kraus et al. learnability ceiling, which is not proved or fully specified in this paper. My independent reading confirms this is the most fragile premise. The lower bound (Buss/BFVP, Proposition 3) is standard and the AC⁰ reduction is plausible; the definition of structural generalization is clear and appropriately scoped by the Montagovian instantiation. However, the inference from 'expressible in TC⁰' to 'not learnable' requires a formal learning model that the paper does not supply. The paper's own discussion in §5.3 narrows the claim by acknowledging that latent-space iteration falls outside the theorem's scope, yet the abstract and conclusion state the impossibility broadly. Since the reader already recommends a conditional acceptance with the same concern, no verdict change is needed. The concern is substantive but addressable: making the Kraus et al. theorem's premises explicit and verifying that they apply to trained Transformers would either strengthen the result or reveal a gap. Until then, the central claim should be treated as conditional on an unverified external result.","tokens_in":10121,"tokens_out":5926,"duration_ms":54523,"concrete_test":"Read Kraus et al. (2026) Theorem 3.4 and its proof in full. Check whether the theorem's conclusion (L ∈ TC⁰) follows from the assumption that F_L has a CoT in C-RASP[Pos] and whether C-RASP[Pos] provably captures all functions learnable by gradient-based training on finite samples with length generalization. If the proof only concerns C-RASP programs and does not establish a learnability upper bound for gradient descent, the bridge in §4.3 is invalid. Alternatively, attempt to train a Transformer (e.g., a small decoder-only model) on the Boolean fragment of §4.1 with training depths 0–4 and test on depths up to 20; if any model achieves perfect accuracy at all tested depths, that would empirically contradict Corollary 3.5 and force a re-evaluation of the premise.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central conclusion (Proposition 6, §4.3) is a syllogism: (1) Montagovian evaluation is NC¹-hard (Proposition 3); (2) TC⁰ ≠ NC¹; (3) by Theorem 4 (Kraus et al. Theorem 3.4), any function a CoT Transformer can learn with length generalization lies in TC⁰. Premise (3) is the load-bearing link, and it is neither proved nor even precisely stated in this paper. The quoted theorem is a definability result about C-RASP[Pos] programs: if F_L has a CoT in C-RASP[Pos], then L ∈ TC⁰. To reach the conclusion 'not learnable', one needs a converse bridge: every function learned by gradient descent with length generalization is expressible as such a CoT. The paper gives no argument for this bridge, and the theorem as stated is about expressibility, not learnability. Moreover, the paper's own §5.3 concedes that latent-space iteration falls outside the theorem's premises, so the scope of 'pure Transformer' is already narrowed. If Kraus et al.'s result fails to cover actual trained Transformers (e.g., due to continuous hidden states, nonstandard encodings, or training dynamics), the impossibility does not follow. The rest of the proof—the AC⁰ reduction to BFVP—is sound, but it is not enough.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a formal definition of structural generalization as the ability to correctly evaluate every expression generated by a finite set of compositional operations over a finite domain (Definition 1, §2.2). It then argues that, under a Montagovian instantiation, the semantic side of compositional evaluation is at least NC¹-hard because it encodes Boolean Formula Value Problem (Proposition 3, §4.1). Citing a learnability ceiling for Chain-of-Thought Transformers from Kraus et al. (Theorem 4, §4.2), the paper concludes that a pure Transformer cannot learn structural generalization (Proposition 6, §4.3) and that neuro-symbolic systems succeed only because they inject the hard semantic half. The paper also discusses why unboundedness is required, why finite benchmarks cannot detect the 'mirage' of a TC⁰ function, and why certain extensions (latent-space iteration) fall outside the cited ceiling (§5.3).","tokens_in":10420,"tokens_out":5871,"duration_ms":53500,"significance":"If the main claim were established, the paper would be a significant contribution: it gives a rare formal definition of a frequently measured but loosely defined notion, and it draws a clear complexity-theoretic line between what pure Transformers can and cannot learn. The paper's articulation of the TC⁰/NC¹ split, its critique of benchmark interpretation, and its observation that neuro-symbolic systems essentially outsource the hard part are thought-provoking and likely to influence the debate. The proof of Proposition 3, while narrow, contains a sound AC⁰ reduction from BFVP to a Montagovian Boolean fragment. However, the central impossibility result is conditional on an externally cited theorem that is not proved in the manuscript and, as stated, does not directly entail 'not learnable' without an additional bridge. The paper is honest about some of these limitations, but the headline claims go beyond what the proof supports.","major_comments":[{"comment":"The main syllogism has a missing bridge. Theorem 4 is stated as: 'If F_L has a CoT in C-RASP[Pos], then L is definable in TC⁰.' This is an expressibility result, not a learnability ceiling. To infer from 'Montagovian evaluation ∉ TC⁰' that it 'cannot be learned with length generalization', the paper needs the converse: every function learnable by a CoT Transformer with length generalization has a CoT in C-RASP[Pos]. The paper does not state, prove, or cite such a converse; Theorem 5 is a corollary about length generalization failure under an unspecified 'learning model of Kraus et al.', and the proof sketch of Proposition 6 simply asserts the bridge. If the learnability model of Kraus et al. does not cover actual gradient-trained Transformers, or if that model is not exactly C-RASP[Pos] expressibility, Proposition 6 fails. This is load-bearing and needs either a precise statement and pro","section":"§4.2–4.3, Theorem 4 and Proposition 6"},{"comment":"The paper's scope is internally inconsistent. The abstract and Proposition 6 claim that 'a pure Transformer cannot learn structural generalization' without qualification. Yet §5.3 explicitly concedes that latent-space iteration (e.g., depth-recurrent Transformers, latent reasoning) falls outside the premises of Kraus et al.'s Theorem 3.4 because the theorem does not apply to continuous hidden states. Those architectures are still pure Transformers by any reasonable reading. Therefore, the impossibility result cannot be stated for all pure Transformers; it can only be claimed for the specific subclass covered by the theorem (finite alphabet, standard positional encoding, discrete-token CoT). The paper should either prove the ceiling for those additional architectures or restrict the main claim accordingly.","section":"§5.3, §4.3, Abstract"},{"comment":"The lower bound is proved only for the constructed Boolean fragment G_B, not for natural language. The paper asserts that 'Montagovian semantic evaluation for any natural language we care about is at least NC¹-hard' because natural languages contain G_B as a subgrammar. This is not established: the reduction from BFVP to G_B depends on the specific grammar and homomorphism, and natural language grammars are not literally formal grammars with productions 'both S and S'. A precise formalization of the relevant fragment of English and a demonstration that the reduction survives embedding in a larger grammar would be needed. As written, the universal claim over all natural languages outruns the proof. Additionally, the abstract's phrase 'Tree evaluation ... is an instantiation of BFVP, which is NC¹-complete' conflates hardness with completeness; Proposition 3 only shows NC¹-hardness.","section":"§4.1, after Proposition 3"},{"comment":"Definition 1 defines structural generalization purely as capacity (correct evaluation on all expressions) and the paper explicitly says a compiler satisfies it. The impossibility result, however, concerns learning from finite data. The move from 'capacity' to 'learnability' is made informally in §3.2, where the paper argues that benchmarks presuppose learning. But the formal machinery (Theorems 4 and 5) is about a specific learning model that is never described in the manuscript. The reader cannot verify that the model matches the informal notion of 'autonomously emerges from finite data'. A precise definition of the learning setting—training distribution, parameterization, optimization, length-generalization criterion—is required before Proposition 6 can be evaluated.","section":"§2.2–§3.2, Definition 1 vs. Proposition 6"}],"minor_comments":[{"comment":"The text says 'Proposition 2 establishes the computational lower bound' but it should refer to Proposition 3.","section":"§4.1, text after Theorem 2"},{"comment":"The abstract states 'Tree evaluation on the G_γ side is an instantiation of BFVP, which is NC¹-complete.' The paper only proves NC¹-hardness of a specific fragment; 'NC¹-complete' is not established for the G_γ side in general. Suggest rewording to 'NC¹-hard' or explicitly stating the completeness claim as conditional on the fragment being exactly BFVP.","section":"Abstract"},{"comment":"The terms C-RASP[Pos], C*-RASP, and 'standard positional encoding' are used without definition. A reader not familiar with Kraus et al. (2026) cannot assess the scope of the theorem. Please provide at least a summary of the programming model and a formal definition of the learning model, or an appendix.","section":"§4.2–4.3"},{"comment":"The claim that C-RASP[Pos] can accumulate 'at most O(log N) bits of effective information per step' is cited to Kraus et al. Appendix A.2 but not explained. Since this is central to the bandwidth argument, a short self-contained explanation would improve readability.","section":"§5.3"},{"comment":"The statement 'A formal complexity characterization of the F_γ side is left to future work' is fine, but the paper later relies on the F_γ/G_γ split for the neuro-symbolic comparison. Clarify whether the F_γ side is assumed to be in TC⁰ or whether the argument only requires that injecting G_γ helps.","section":"§3.3"},{"comment":"The reference to Kraus et al. (2026) and the use of 'Theorem 4' and 'Corollary 3.5' should include the exact relationship between the numbering in this paper and the numbering in the cited arXiv preprint, since the reader may want to verify the quoted results.","section":"References"}],"recommendation":"major_revision","confidential_remarks":"The paper has a sound core—the AC⁰ reduction to BFVP and the clear conceptual separation of capacity from learnability—but the headline impossibility result is currently overclaimed. The missing bridge from Kraus et al.'s expressibility theorem to a learnability ceiling, and the paper's own caveat about latent-space iteration, mean that Proposition 6 as stated is not established. I would encourage the editor to invite a revision that either proves the missing bridge or carefully restates the theorem to match the actual scope of the cited results, and that fixes the 'NC¹-complete' vs 'NC¹-hard' issue. The paper is likely to be worth publishing once these load-bearing points are addressed."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear colleague,\n\nThe paper is worth reading for its clean formalization of structural generalization as unbounded term-algebra evaluation, and for its explicit neutrality: a compiler satisfies the definition, so the scientific question is about autonomous learning from finite data. That framing is genuinely useful for the benchmarks literature. The reduction from BFVP to a Boolean Montagovian fragment (Proposition 3) is sound as far as it goes, and the Fγ/Gγ split is a nice way to see why neuro-symbolic systems like AM-Parser outsource the hard half.\n\nBut the main result, Proposition 6, does not follow from what is proved in this paper. The load-bearing premise is Theorem 4 from Kraus et al., which is a definability statement: if a language's indicator has a CoT in C-RASP[Pos], then the language is in TC0. To conclude that a pure Transformer cannot learn structural generalization, you need the converse bridge: every function learned by gradient descent with length generalization is expressible as such a CoT. No argument for that bridge is given, and the theorem as quoted is about expressibility, not learnability. Without that bridge, the impossibility is conditional on an external result that may not cover actual trained Transformers—especially continuous hidden states or nonstandard encodings. The paper's own §5.3 concedes that latent-space iteration falls outside the theorem's premises, so the \"pure Transformer\" being discussed is narrower than the abstract suggests.\n\nTwo smaller issues. First, Proposition 3 shows NC1-hardness for a Boolean fragment, not completeness, and the paper sometimes says \"NC1-complete\" without the proof. Hardness is enough for the lower bound, but the slip should be fixed. Second, the extension from the Boolean fragment to all natural languages, via typological universals like coordination and negation, is too quick; that argument would need a lot more care.\n\nOn the positive side, the paper is honest about its own limitations: it flags the compiler triviality, and it lists per-category complexity as an open question. The discussion of data augmentation as enlarging a \"mirage\" is a useful way to think about why benchmark scores plateau.\n\nWho this is for: anyone working on compositional generalization or neuro-symbolic parsing will get value from the conceptual framing, even if the impossibility conclusion is not yet proven. It deserves a serious referee, but the referee should require the author to either prove or explicitly state the expressibility-to-learnability bridge, and to scope Proposition 6 to the actual fragment and learning model. I would send it to review with major revision.","headline":"Clean formalization of structural generalization as unbounded term-algebra evaluation, with a sound NC1-hardness reduction, but the impossibility claim leans on an unproved learnability ceiling and overstates its scope.","tokens_in":10890,"tokens_out":3164,"would_cite":false,"duration_ms":27480,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q15","68Q17"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper argues that pure Transformers cannot learn structural generalization, because the underlying tree evaluation is NC¹-hard while trainable Transformers are limited to TC⁰.","keywords":["structural generalization","compositional generalization","Transformer","TC0","NC1","Boolean Formula Value Problem","learnability ceiling","chain-of-thought"],"falsifier":"A concrete disproof would be to exhibit a trained pure Transformer (no symbolic components) that correctly evaluates arbitrarily deep compositions of a rule set containing coordination and negation — e.g., all Boolean formulas of increasing depth sampled far past the training range — in a way that provably matches the true evaluation on infinitely many unseen depths, not just a finite window. Alternatively, a counterexample to the learnability ceiling itself — a chain-of-thought Transformer with finite alphabet and standard positional encoding that learns a function outside TC⁰ from finite dat","tokens_in":9996,"feed_emoji":"🧩","tokens_out":5897,"duration_ms":42514,"temperature":0.7,"pith_summary":"The paper gives the first formal definition of structural generalization as correct evaluation of a finite rule set on every compositional configuration, finite or not. It then shows that under this definition, the semantic half of compositional evaluation is a tree-evaluation problem that is at least NC¹-hard. Since pure Transformers — even with chain-of-thought and length generalization — can only learn functions inside TC⁰, and TC⁰ is believed to be strictly weaker than NC¹, the paper concludes that no pure Transformer can learn structural generalization from finite data. A key consequence is that benchmark scores cannot distinguish a learned rule from a hard-coded one, since any finite test set can be passed by a TC⁰ lookup table. The paper thus reframes the empirical gap between neuro-symbolic and purely neural systems as a difference in learning task, not in learning capacity.","feed_headline":"Pure Transformers can't learn structural generalization","feed_subtitle":"Tree evaluation is NC¹-hard, but trainable Transformers stay in TC⁰ — so benchmarks can't prove a rule was learned.","key_machinery":"The central object is the split of each compositional rule into two projections — the syntactic face F_gamma (which rule applies where) and the semantic face G_gamma (how to compute the resulting meaning) — bound together by a compositional-semantics homomorphism. The argument's load-bearing identity is that evaluating expressions over G_gamma is exactly the Boolean Formula Value Problem, a tree-evaluation problem known to be NC¹-complete. Against this lower bound is the learnability ceiling: the class of functions a chain-of-thought Transformer can learn with length generalization is contained in TC⁰. The proof that this ceiling holds is not developed in the paper; it is imported from a cit","core_discovery":"The central claim is that structural generalization, once defined as unbounded evaluation of a finite compositional rule system, is not learnable by a pure Transformer. The argument splits each compositional rule into a syntactic face and a semantic face. The semantic face is bottom-up tree evaluation, which encodes the Boolean Formula Value Problem and is therefore NC¹-hard. The learnability ceiling for chain-of-thought Transformers under finite alphabets is TC⁰. Under the standard conjecture TC⁰ ≠ NC¹, the two classes are disjoint, so the true compositional evaluation function lies outside what any pure Transformer can learn with length generalization. What a Transformer can produce is a '","pith_inferences":["If the TC⁰ ceiling theorem applies beyond the paper's specific learning model, the same argument would also rule out pure RNNs or other sequence models whose learnable class stays within TC⁰; the paper only states the result for Transformers.","The syntactic face F_gamma is left uncharacterized; the argument would be stronger if that side were shown to be learnable within TC⁰, because the impossibility currently focuses on G_gamma alone.","A direct empirical test suggests itself: train a pure Transformer on a compositional task with unbounded depth and measure whether errors concentrate at depths far beyond the training range; the mirage account predicts divergence exactly at the boundary of augmentation or training depth.","The paper's cross-linguistic caveat implies that benchmark categories such as PP attachment may not be universal compositional rules; if a rule is not genuinely productive in a language, the NC¹-hardness lower bound may not apply to it."],"forward_implications":["No finite benchmark can certify that a pure Transformer learned a compositional rule, because any finite test set can be fit by a TC⁰ function that agrees with the true function on those inputs.","Data augmentation and training-strategy improvements only enlarge the agreement window of the TC⁰ approximation; they cannot lift it out of TC⁰.","Neuro-symbolic systems outperform pure Transformers on structural generalization benchmarks not because they learn better, but because they are handed the semantic evaluation half (G_gamma) and only learn the syntactic half (F_gamma).","To break the TC⁰ ceiling while keeping a finite alphabet, iteration would need to happen in a continuous latent space rather than through discrete chain-of-thought tokens.","The formal definition implies that a hard-coded compiler satisfies structural generalization as a capacity, making learnability from finite data the real scientific question."],"fun_headline_variants":["Structure beyond Transformers: NC1 hardness vs TC0 ceiling","Pure Transformers can't learn compositional rules","No benchmark proves rule learning: it's NC1 vs TC0","The hard truth: Transformer generalization is TC0-bound","Why structural generalization defeats pure Transformers"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"The impossibility result rests on the imported theorem that a chain-of-thought Transformer with finite alphabet and standard positional encoding can only learn functions in TC⁰; if that learnability ceiling is wrong or does not cover real trained Transformers, the conclusion that pure Transformers cannot learn structural generalization collapses.","fun_headline_variants_meta":{"raw":{"variants":["Structure beyond Transformers: NC1 hardness vs TC0 ceiling","Pure Transformers can't learn compositional rules","No benchmark proves rule learning: it's NC1 vs TC0","The hard truth: Transformer generalization is TC0-bound","Why structural generalization defeats pure Transformers"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000229,"raw_usage":{"total_tokens":1333,"prompt_tokens":779,"completion_tokens":554,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":523,"completion_tokens_details":{"reasoning_tokens":478}},"tokens_in":523,"tokens_out":554,"duration_ms":5644,"temperature":1.0,"reasoning_tokens":478,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-01T12:19:57.107620+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A concrete disproof would be to exhibit a trained pure Transformer (no symbolic components) that correctly evaluates arbitrarily deep compositions of a rule set containing coordination and negation — e.g., all Boolean formulas of increasing depth sampled far past the training range — in a way that provably matches the true evaluation on infinitely many unseen depths, not just a finite window. Alternatively, a counterexample to the learnability ceiling itself — a chain-of-thought Transformer with finite alphabet and standard positional encoding that learns a function outside TC⁰ from finite dat","supporting_citations":[],"review_version":1}