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

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 $n$, fixed deterministic and unambiguous context-free languages admit $\mathcal{O}(n^2)$ and $\mathcal{O}(n^{{\log }_{2}7+\epsilon })$ blank padding, respectively, with $\mathcal{O}({\log }^{2}n)$ loops including initialization. General context-free languages admit $\mathcal{O}(n^{2{\omega }_{\mathbb{Q}}+\epsilon })$ padding, with $\mathcal{O}(\log n)$ loops under supplied fields or $\mathcal{O}({\log }^{2}n)$ 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.