- Rating
- 2(+1)
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 2(+1)
Read review
Paper summary
The paper studies the resources a looped transformer needs to parse context-free languages exactly. Assuming causality in looped transformers and averaging hard attention, the model decides membership and keeps a replayable parse certificates using padding tokens as scratch memory. By implementing classical parallel parsing algorithms so attention reads left positions, they bound padding and loop depth to and loops, respectively, for deterministic CFLs; padding and loops for unambiguous CFLs; and padding with to loops for general CFLs. These bounds match the loop counts of [1] while reducing padding and adding strict causality and certificates. Authors provide an empirical study where a separate learned looped transformer proposes chart items that an exact verifier accepts only when valid. The learned proposals outperform simple schedules on Dyck but fail on longer Palindrome inputs, and mixing in round-robin scheduling without retraining raises Palindrome coverage from 18.75% to 97.36%.
References:
- Context-Free Recognition with Transformers (2026).
Critical strengths
Definition of the theoretical bounds of looped transformers for parsing deterministic, unambiguous and general CFL by using padding entries. In simple tasks, rules from the grammar can be learned with a neural parser,
Critical weaknesses
-
Limited algorithmic novelty: The paper is upfront that the algorithms are classical: reachability corrections are Boolean Newton iteration [1], the DCFL construction adapts [2], and the general case is [3]. The contribution is compiling these into strictly causal AHAT with low padding. The paper should state more clearly which parts are technically new beyond layout engineering.
-
The size of the improvement over [4] needs justification: Loop counts match prior work, so the gains are polynomial reductions in padding (e.g., for general CFLs). Both are far from practical, and the ε-dependent fast matrix-multiplication identities hide very large constants. Why do these exponent reductions matter?
-
Weakly motivated paper: Overall I missed better motivations of the two main components of the methodology:
- Strict causality is the central design constraint, and it is what forces the copying and fresh banks. But [4] already have a mixed-mask (MAHAT) variant with less padding. The paper should argue why the strictly causal setting is the right one, e.g., its relevance to decoder-only LMs.
- Why looped transformers, compared with alternatives? Why transformers and not graph neural networks with passing over chart cells, which could run the same doubling algorithms?
This does not mean that causality and looped transformers are not a valid research contribution, but the narrative presents them in a very niche topic and makes them a default setting when they are not without proper justification.
-
Weak connection between the two parts. The learned parser (Section 4) is a looped softmax encoder with an external verifier and chart. It is not the strictly causal AHAT of Section 3, and it does not appear to be causal at all. The experiments therefore do not test the setting the theory addresses, and the theory does not predict or explain the empirical findings. The "complementary" framing in the abstract and conclusion feels like two papers combined.
-
Bounds are proposed, but it is not clear to me whether they are learnable The constructions show that weights exist, but they say nothing about whether such weights can be learned, or whether trained looped LMs parse this way, or whether they can help learning other tasks. From my point of view this is very concerning since the paper is presented in a conference of learning representations.
-
Parsing scope: Only one derivation per item is stored. For ambiguous grammars the other parses are discarded, so this is not parsing in the sense of recovering all or the best parses. Is the title appropriate then (exact parsing)? For DCFLs the certificate is an accepting DPDA run, annotated to recover a derivation in an associated grammar built from the automaton, not the user's grammar. Calling this a "parsing certificate" on a par with the CFG cases is somewhat misleading.
-
The learned-scheduling setup makes the comparison of limited value.
- Experiments use a static and very generous quota () where the proposer may submit 30% of all legal cells every loop. How do the results change with a small quota?
- The verifier "computes all binary consequences before filtering by proposals", and the proposer is trained to imitate exactly this frontier. The learned component predicts something the system has already computed, so the practical motivation for learned scheduling is unclear.
- Rotating is an external selection rule that replaces the network's top- cells on some loops; the model is unchanged. Rotating alone, with no neural model, already reaches 99.31% on Palindrome (Table 2b), higher than both hybrids (92.22% Alternating, 97.36% Switch after 24). The result therefore shows that the learned proposer hinders progress on this task, not that combining neural and cyclic scheduling is beneficial.
-
Narrow benchmark: All grammars (Dyck(1), Dyck(2), , Palindrome, Arithmetic) are small, synthetic and unambiguous, with inputs of at most 240 tokens. No experiment involves ambiguity, even though the general-CFL construction exists precisely to handle it. Larger or more realistic grammars would strengthen the empirical claims (e.g. JSON or a natural language CFG from the Penn Treebank).
-
The training objective is underspecified: Appendix D.2 describes supervision in one paragraph: the exact chart supervises a chart head, per-loop proposal targets are the current frontier, membership/halt heads get "auxiliary supervision", no gradients pass through the verifier, and "supervision gradually extends" across the 24 loops. Missing:
- Loss functions (entropy? ranking loss?) and how the heads' losses are weighted.
- Whether the proposal head has its own loss: checkpoint selection uses the "sum of chart, membership, and halt losses" with no proposal loss, even though proposals are the only thing evaluated;
- Whether the training trajectory is teacher-forced (oracle charts) or follows the model's own proposals.
In general I feel the empirical contribution is very hard to reproduce due to the poor presentation of the experimental setup.
References:
- Newtonian program analysis (JACM 2010).
- On the parallel recognition of unambiguous context-free languages (Theoretical Computer Science, 1991).
- A parallel algorithm for context-free parsing (1983).
- Context-Free Recognition with Transformers (2026).
Questions for authors
- Beyond layout and arithmetic sharing, what is the key new technical idea in Section 3 compared with [4] and the classical PRAM algorithms?
- Why strictly causal AHAT instead of the mixed-mask setting? Is there a lower bound showing that the extra padding is necessary under strict causality?
- How would your bounds compare with a chain-of-thought transformer parsing the same languages?
- Given that the verifier already computes the frontier, in what setting would a learned proposer reduce cost?
- Why are there no experiments on ambiguous or larger grammars (e.g., JSON, treebank-induced CFGs)?
- Please specify the full training objective: loss per head, weighting, whether proposals have a dedicated loss, and the curriculum over loops.
- Since Rotating alone reaches 99.31% on Palindrome, what does the neural proposer contribute in the hybrid schedules?
- Please consider adding a Figure with a real example that visualizes the notation/contribution of the paper.