acceptodds
Under review as a conference paper at ICLR 2027

Exact Parsing with Looped Transformers: Storage, Depth, and Scheduling

Abstract

Exact context-free parsing with looped transformers requires both organizing intermediate states in memory and scheduling updates that advance the computation. We study these requirements through theoretical constructions and experiments on a separate learned parser. On the construction side, we establish storage and loop bounds for strictly causal averaging-hard-attention transformers. For input length , fixed deterministic and unambiguous context-free languages admit and blank padding, respectively, with loops including initialization. General context-free languages admit padding, with loops under supplied fields or loops including blank initialization. All constructions have fixed parameters, constant width, logarithmic precision, and replayable parsing certificates. On the learning side, learned rankings under a fixed verifier improve completion on some grammars but deteriorate on longer Palindrome inputs. Exploratory scheduling interventions recover most unfinished Palindrome decisions without retraining, while cyclic updates guarantee bounded waiting under the verified-update assumptions. Together, these results identify memory organization and reliable scheduling as complementary means of turning repeated computation into verified progress.

Primary area:
learning theory
Keywords:
Looped Transformer, Context-free Languages, Certified Neural Parsing, Proposal Scheduling

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_VfDDOpenReview ↗
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 O(n2)O(n^2) and O(log⁡2n)O(\log^2 n) loops, respectively, for deterministic CFLs; O(nlog⁡27+ε)O(n^{\log_2 7+ε}) padding and O(log⁡2n)O(\log^2 n) loops for unambiguous CFLs; and O(n2ωQ+ε)O(n^{2ω_Q+ε}) padding with O(log⁡n)O(\log n) to O(log⁡2n)O(\log^2 n) 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:

  1. 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
  1. 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.

  2. The size of the improvement over [4] needs justification: Loop counts match prior work, so the gains are polynomial reductions in padding (e.g., n6→n7→⋯→≈n4.75n^6 \to n^7 \to \dots \to \approx n^{4.75} 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?

  3. 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.

  4. 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.

  5. 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.

  6. 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.

  7. The learned-scheduling setup makes the comparison of limited value.

    • Experiments use a static and very generous quota (q=0.3mq = 0.3m) 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-qq 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.
  8. Narrow benchmark: All grammars (Dyck(1), Dyck(2), anbna^nb^n, 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).

  9. 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:

  1. Newtonian program analysis (JACM 2010).
  2. On the parallel recognition of unambiguous context-free languages (Theoretical Computer Science, 1991).
  3. A parallel algorithm for context-free parsing (1983).
  4. Context-Free Recognition with Transformers (2026).
Questions for authors
  1. Beyond layout and arithmetic sharing, what is the key new technical idea in Section 3 compared with [4] and the classical PRAM algorithms?
  2. 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?
  3. How would your bounds compare with a chain-of-thought transformer parsing the same languages?
  4. Given that the verifier already computes the frontier, in what setting would a learned proposer reduce cost?
  5. Why are there no experiments on ambiguous or larger grammars (e.g., JSON, treebank-induced CFGs)?
  6. Please specify the full training objective: loss per head, weighting, whether proposals have a dedicated loss, and the curriculum over loops.
  7. Since Rotating alone reaches 99.31% on Palindrome, what does the neural proposer contribute in the hybrid schedules?
  8. Please consider adding a Figure with a real example that visualizes the notation/contribution of the paper.
Reviewer_6YhkOpenReview ↗
Rating
4(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies exact context-free parsing with strictly causal looped transformers under averaging hard attention (AHAT). It asks what padding storage and loop depth suffice, including when the auxiliary layout must be generated internally from identical blank tokens.

Three constructions are given, all with fixed parameters, constant width, O(log⁡n)O(\log n) precision and replayable parsing certificates:

  • DCFLs: DPDA call summaries are merged in reusable interval banks, giving O(n2)O(n^2) blank padding and O(log⁡2n)O(\log^2 n) loops.
  • UCFLs Newton/Strahler reachability corrections are evaluated by unique-path status contraction, with counts from fast bilinear matrix products. This gives O(nωQ+ε)O(n^{\omega_Q+\varepsilon}) padding with public fields, O(nlog⁡27+ε)O(n^{\log_2 7+\varepsilon}) from blank padding, and O(log⁡2n)O(\log^2 n) loops.
  • General CFLs: Brent–Goldschlager tree/context doubling gives O(n2ωQ+ε)O(n^{2\omega_Q+\varepsilon}) padding, with O(log⁡n)O(\log n) public or O(log⁡2n)O(\log^2 n) blank loops.

The authors compare these bounds with Jerad et al. (2026) and with full-layer causal simulation. They also give limits for explicit dependency records and for direct chart-mask encodings.

Separately, a softmax looped proposer feeding an external chart verifier is evaluated on five toy grammars over three seeds. Learned rankings beat Random and Rotating on Dyck and anbna^nb^n but fail on longer Palindrome inputs. Inserting cyclic (Rotating) steps restores coverage, and cyclic scheduling admits a bounded-waiting guarantee. The supplementary code covers the experiments and includes finite component checkers for the constructions.

Critical strengths

[S1] The paper gives explicit, complete resource accounting for causal AHAT parsing, and the bounds improve on prior work. It counts every auxiliary record, separates supplied public fields from internal blank initialization, and retains certificates.

[S2] The scoping is candid and the supplementary material is checkable. The authors state that dense attention work does not beat CKY, and that the frontier oracle does not establish a need for learned rankings. I ran the supplied theory suites on CPU, and all passed. As the README itself states, these are finite component checks, not an end-to-end AHAT. The experiment code matches the described quota, eligibility and schedule protocol.

Critical weaknesses

[W1] The learning half is loosely connected to the theory, and the scheduling problem it tests is only weakly constrained. RQ2 uses a softmax encoder plus an external verifier that already computes all binary consequences D(X)D(X) before filtering.

The per-loop quota is ⌊0.3m⌋\lfloor 0.3m\rfloor of all legal spans, while Table 5 shows that the oracle frontier never exceeds 18.8% of it. Proposing every enabled item would therefore always complete within budget. Rotating sweeps all addresses in ⌈m/q⌉=4\lceil m/q\rceil=4 loops, so the bounded-waiting result of Prop. D.2 is essentially a round-robin fairness argument. On Palindrome, the Alternating and Switch interventions reach 92.22% and 97.36%, which does not exceed the 99.31% of pure Rotating in Table 2b. They show that scheduling restores progress, not that the learned ranker adds value there. The clearest eligibility result, that NN inference beats AA inference under either training policy, is close to holding by construction: NN keeps the quota fixed while excluding already-verified items, which frees slots for new ones.

The Palindrome failure also has a confound in the training data. Training sizes are 1–6, with a minimum of 2 forced for Palindrome, so the positive training words are just the 26 palindromes of length 2–6 over {a,b}\{a,b\}, while OOD inputs have 12–60 tokens. Small support alone cannot explain the failure, since anbna^nb^n has even fewer distinct positives and generalizes, but it is an untested alternative to the "proposal starvation" interpretation. None of these experiments bears on whether the AHAT constructions can be learned or scheduled.

[W2] The significance of the theory is harder to judge than it should be. The main text compresses a roughly 40-page appendix into dense prose, and the two research questions read as separate papers. Table 1 places public-field rows beside blank-padding rows without grouping them by initialization model, and the gap between the public and blank UCFL bounds is not explained. From the main text alone, it is hard to see which ideas go beyond realizing the classical parallel algorithms of Chytil et al., Brent and Goldschlager, and Valiant and Strassen in this model.

Questions for authors

Clarifications:

  1. The public UCFL module already uses uniform constant-depth division circuits to recover DqD^q-scaled counts. What prevents the blank UCFL construction from using a general rational identity in the same way, which would close the gap between Thm. 3.2(i) and (ii)? Section E.2 lists this as future work without naming the obstacle.
  2. Could Table 1 list the Jerad et al. rows that apply to DCFLs explicitly, and group rows by initialization model? For context, please also state the exponents realized with Strassen: n2.81+εn^{2.81+\varepsilon} for UCFLs and n5.61+εn^{5.61+\varepsilon} for general CFLs.
  3. The Palindrome training positives come from only 26 distinct words. Does the collapse persist with more diverse or longer training palindromes? Relatedly, does the choice of absolute sinusoidal positions matter?
  4. With a quota that binds for exhaustive propagation (e.g., qq below the typical frontier size), do learned rankings outperform Rotating and Random?

Suggestions (these would strengthen the paper but are not required for my assessment): 5. A study connecting the two halves, for example whether trained models can realize the bank or contraction schedules, would make the paper's central principle more convincing.

Reviewer_ux8LOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary
  • The paper investigates the theoretical bounds and learning behaviors of exact context-free parsing using Looped Transformers under strict causal attention mechanisms. The authors point out that translating iterative computation into exact parsing requires both effective intermediate state storage (memory organization) and reliable proposal scheduling. They propose strict causal looped Averaging-Hard-Attention (AHAT) model constructions for deterministic context-free languages (DCFLs), unambiguous context-free languages (UCFLs), and general context-free languages (CFLs). They achieve precise characterizations of storage space, loop depth, and blank padding initialization bounds. Through simple exploratory interventions, the verification completion rate for palindromes is significantly improved without retraining.
Critical strengths
  1. The paper seamlessly integrates classical parallel parsing algorithms with modern Looped Transformers featuring strict causal attention, logarithmic precision, and constant width architecture. It not only provides asymptotic space and depth bounds but also rigorously proves the internal initialization process starting from blank padding, offering exceptionally solid theoretical support.
  2. The paper innovatively decomposes "computational capability" into two complementary dimensions: memory organization and scheduling mechanisms. Through an in-depth diagnosis of why neural proposal strategies fail on the palindrome task, and experiments showing substantial performance recovery merely by modifying the scheduling strategy, it reveals an important and universal principle: "increasing test-time compute must rely on reliable scheduling to avoid deadlocks."
Critical weaknesses
  1. The theoretical construction heavily relies on Averaging-Hard-Attention (AHAT) and strict causal masks, which differ significantly from standard Softmax Attention widely used in large language models. Although the authors mention extensions to soft attention in future work, it remains questionable to what extent the current conclusions can transfer to mainstream Softmax architectures.
Questions for authors
  1. On the Scalability of Softmax Attention (Clarification Request): The theoretical construction and deterministic pointer addressing in the paper strongly rely on the "hard choice" (hard-max / argmax) property of AHAT to ensure precise score gaps. For smoothed (Softmax) attention mechanisms, will the information dispersion caused by exponential normalization lead to the failure of precise pointer addressing and state contraction required for grammar parsing? Is there a smooth approximation scheme that can achieve the same asymptotic bounds?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.