REVIEW 4 major objections 6 minor 2 references
On the Computational Complexity of Structural Generalization
T0 review · 4 major / 6 minor · reviewed 2026-08-01 · deepseek-v4-flash
Pith's one-line read 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⁰.
desk verdict 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. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
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
What would settle it
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
Extended reading notes
Core claim
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 '
Load-bearing premise
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.
Editorial extensions
If this is right
- 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.
Reading between the lines
- 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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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).
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 (4)
- [§4.2–4.3, Theorem 4 and Proposition 6] 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
- [§5.3, §4.3, Abstract] 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.
- [§4.1, after Proposition 3] 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.
- [§2.2–§3.2, Definition 1 vs. Proposition 6] 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.
minor comments (6)
- [§4.1, text after Theorem 2] The text says 'Proposition 2 establishes the computational lower bound' but it should refer to Proposition 3.
- [Abstract] 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.
- [§4.2–4.3] 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.
- [§5.3] 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.
- [§3.3] 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.
- [References] 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.
Circularity Check
No significant circularity found; the derivation is a conditional chain from definitions to externally cited theorems.
full rationale
The paper's central argument is a conditional syllogism, not a circular derivation. Definition 1 formalizes structural generalization as correct evaluation of every expression generated by a finite operation set; the paper explicitly acknowledges this definition is neutral because a compiler satisfies it (Section 3.1). The lower bound (Proposition 3) is a genuine reduction from BFVP to a constructed Montagovian fragment (Eq. 1 and the grammar G_B), not a renaming or a definitional equivalence. The learnability ceiling is imported from Kraus et al. (2026, Theorem 3.4), which is an external citation by different authors; it is not derived from the target conclusion, and the paper does not redefine that theorem in terms of structural generalization. The impossibility result (Proposition 6) is explicitly conditional on TC^0 ≠ NC^1 and on Theorem 4. The paper also flags its own scope limitation in Section 5.3: architectures with continuous latent-space iteration fall outside the theorem's premises, and the question of breaking the TC^0 ceiling is left open. While the load-bearing external theorem is not proved in this paper—a correctness/verifiability concern—that does not constitute circularity under the criteria. No fitted parameters are renamed as predictions, and no self-citation chain is used to force the conclusion.
Assumptions & free parameters
assumptions (6)
- domain assumption TC⁰ ⊊ NC¹ (circuit complexity separation conjecture)
- standard math BFVP is NC¹-complete under AC⁰ reductions (Buss 1987)
- standard math Constant-depth log-precision transformers are in TC⁰ (Merrill & Sabharwal 2023)
- domain assumption Kraus et al. (2026) Theorem 3.4: CoT-learnable functions with length generalization are TC⁰-definable
- domain assumption Postulates 1 and 2: structure is compositional (finite n-ary operations) and generalization is unbounded (all expressions)
- domain assumption Montagovian homomorphism is the right instantiation of natural-language compositionality
Cite this review
Pith. "Pith review of On the Computational Complexity of Structural Generalization." pith.science (2026). https://pith.science/paper/ET75SEOH
@misc{pith2026260719573,
author = {Pith},
title = {Pith review of: On the Computational Complexity of Structural Generalization},
year = {2026},
howpublished = {\url{https://pith.science/paper/ET75SEOH}},
note = {Machine review of arXiv:2607.19573}
}
abstract
Structural generalization has been measured repeatedly by several benchmarks, yet it has never been formally defined. We give a definition that translates the two premises (compositional structure and unbounded generalization) into mathematical language. The definition itself is neutral: a compiler that hard-codes the rules satisfies it just as well. But structural generalization becomes a scientific question only insofar as the capacity can autonomously emerge from finite data. This question pits the computational lower bound $\mathrm{NC}^1$ against the learnable ceiling $\mathrm{TC}^0$ of pure Transformers. Under a Montagovian instantiation, each compositional rule splits into two projections: a syntactic face ($F_\gamma$) and a semantic face ($G_\gamma$). Tree evaluation on the $G_\gamma$ side is an instantiation of BFVP, which is $\mathrm{NC}^1$-complete (Buss, 1987). A pure Transformer must learn both faces at once, but Kraus et al. (2026) prove that its learnable class $\subseteq \mathrm{TC}^0$. Under the standard assumption $\mathrm{TC}^0 \neq \mathrm{NC}^1$, a pure Transformer cannot learn structural generalization. Neuro-symbolic systems achieve the best benchmark scores precisely because they inject $G_\gamma$, sidestepping the genuinely hard half. Benchmark scores cannot distinguish "learned" from "given." This is what this paper sets out to make clear.
Reference graph
Works this paper leans on
-
[2]
Cambridge University Press, 2007. Hauser, M. D., Chomsky, N., and Fitch, W. T. The faculty of language: What is it, who has it, and how did it evolve?. Science, 298(5598), 1569–1579, 2002. https://doi.org/10.1126/science.298. 5598.1569 Humboldt, W. von. Über die verschiedenheit des menschlichen sprachbaues und ihren einfluss auf die geistige entwickelung ...
arXiv 2007
-
[2022]
Compositional reasoning with transformers, RNNs, and chain of thought
https://doi.org/10.18653/v1/2022.emnlp-main.337 Yehudai, G., Amsel, N., and Bruna, J. Compositional reasoning with transformers, RNNs, and chain of thought. arXiv, 2025. https://doi.org/10.48550/ARXIV.2503.01544 Zadrozny, W. From compositional to systematic semantics. Linguistics and Philosophy, 17(4), 329– 342, 1994. https://doi.org/10.1007/BF00985744 10
Reviewed August 1, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.