Written, Not Trained: LLM-Written Stack Machines Proven Correct at Every Length
Stack- and tape-augmented recurrent networks were made differentiable so that they could be trained, yet on the Chomsky-hierarchy benchmark of Delétang et al. they rarely extrapolate exactly beyond the training lengths. We hand the hard version of the machine to a large language model (LLM). R0S is a recurrent controller with Heaviside units, ternary weights and integer biases that drives an unbounded discrete stack through argmax push, pop and no-op actions. From a plain-language specification and without running the network, Claude Opus wrote R0S networks for five benchmark tasks and Dyck-2; all 30 attempts pass our scorer. Two mechanical methods, a grammar-summary fixpoint and a lockstep product with a reference pushdown automaton, prove all 25 networks on five tasks correct on every input the task generator produces, at every length; the 5 bucket-sort networks pass the scorer but are wrong, because they count with bounded counters. On modular arithmetic and equation solving the proven networks have 185–591 non-zero parameters.Learning from input-output examples finds no exact network there: straight-through training of R0S itself (20,000 steps, 4 learning-rate and initialisation arms) is exact in 0 of 120 runs and Delétang's four differentiable models in 0 of 120 runs; in a near-full version of their training setting on modular arithmetic, 0 of 180 runs are exact, although the best Stack-RNN reaches a Delétang score (accuracy averaged over lengths 41–500) of 95.1 (theirs: 96.1).Placed behind a 16k-parameter interface inside a frozen Qwen3.5-0.8B, with a read-in trained per token on the generator's labels, the proven modular-arithmetic network answers correctly at all 14 tested lengths from 5 to 500 (0 errors on 4,500 test-length inputs, in each of 3 seeds); the same interface around the trained Stack-RNN reaches 88.4% exact match at length 500, and LoRA fine-tuning without a module, trained on answers only, falls to the majority-answer rate. We do not claim that stack networks are untrainable in general, or that the interface can be learned from answers alone
Authors
- Xintian Huang (ORCID: https://orcid.org/0009-0000-7664-7108)
Publication Details
- Journal
- Zenodo (CERN European Organization for Nuclear Research)
- Published
- 2026-11-13
- DOI
- https://doi.org/10.5281/zenodo.24179468
- Primary Topic
- semigroups and automata theory
- Type
- preprint