Universal Transformers for Circuit Computations: Perfect Length Generalization in Tiny Transformers

• URL: http://arxiv.org/abs/2608.31067v1
• Date: Mon, 31 Aug 2026 16:42:11 GMT
• Title: Universal Transformers for Circuit Computations: Perfect Length Generalization in Tiny Transformers
• Abstract summary: We present a provably correct, transformer parameterization capable of learning and evaluating problems of any depth or length.<n>Our approach conceptualizes algorithmic tasks as circuit models embedded in transformers, enabling depth-1 circuit reduction in a single forward pass.
• Score: 15.437559038107144
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Learning generalizable algorithmic computations remains a challenge for neural networks, as reflected in persistent failures on compositional and length generalization benchmarks. We present a provably correct, transformer parameterization (with only 280 learnable parameters for Boolean algebra tasks) capable of learning and evaluating problems of any depth or length. We assume inputs are fully parenthesized, well-formed expressions. Our approach conceptualizes algorithmic tasks as circuit models embedded in transformers, enabling depth-1 circuit reduction in a single forward pass. To achieve depth generalization, we introduce a positional encoding that tracks each gate's depth within the circuit, enabling the model to identify evaluable subexpressions at each iteration via masked hard attention, with $O(n)$ per-iteration complexity via linear attention. Combined with an autonomous halting criterion, the model terminates after $d$ iterations for problems of depth $d$, yielding $O(n \cdot d)$ total complexity. We show that training on shallow problem instances (depth 1 and depth 2) effectively recovers interpretable parameters that {\em snap} into place, resulting in exact length generalization. Though we establish that our construction provably evaluates Boolean expressions -- a universal symbolic computation -- of arbitrary length perfectly, in other experiments we also demonstrate that our transformer variant can learn and generalize perfectly (100% accuracy) on other common length generalization benchmarks, including modular arithmetic and ListOps.

Related papers

• Revisiting Padded Transformer Expressivity: Which Architectural Choices Matter and Which Don't [78.36679389968772]
  We find that padded $textL$ constantprecision transformers are surprisingly robust to expressivity.<n>$logd-looped constant-precision transformers reach $textFO-uniform TCd$, and growing-precision ones reach $textFO-uniform TCd$.
  arXiv  Detail & Related papers  (2026-05-28T19:58:43Z)
• Barriers to Universal Reasoning With Transformers (And How to Overcome Them) [46.59247939156339]
  Chain-of-Thought (CoT) has been shown to empirically improve Transformers' performance, and theoretically increase their expressivity to Turing completeness.<n>We use recent theoretical frameworks for Transformer length generalization and find that -- under standard positional encodings and a finite alphabet -- Transformers with CoT cannot solve problems beyond $TC0$.<n>We attain a length-generalizable simulation of Turing machines where the CoT trace length is linear in the simulated runtime up to a constant.
  arXiv  Detail & Related papers  (2026-04-28T16:10:37Z)
• Looped Transformers for Length Generalization [41.99378201613648]
  We show that looped Transformers with an adaptive number of steps significantly improve length generalization.<n>We train looped Transformers using our proposed learning algorithm and observe that they learn highly length-generalizable solutions for various tasks.
  arXiv  Detail & Related papers  (2024-09-24T01:21:17Z)
• On the Constant Depth Implementation of Pauli Exponentials [49.48516314472825]
  We decompose $Zotimes n$ exponentials of arbitrary length into circuits of constant depth using $mathcalO(n)$ ancillae and two-body XX and ZZ interactions.<n>We prove the correctness of our approach, after introducing novel rewrite rules for circuits which benefit from qubit recycling.
  arXiv  Detail & Related papers  (2024-08-15T17:09:08Z)
• Chain of Thought Empowers Transformers to Solve Inherently Serial Problems [57.58801785642868]
  Chain of thought (CoT) is a highly effective method to improve the accuracy of large language models (LLMs) on arithmetics and symbolic reasoning tasks. This work provides a theoretical understanding of the power of CoT for decoder-only transformers through the lens of expressiveness.
  arXiv  Detail & Related papers  (2024-02-20T10:11:03Z)
• Transformers Can Achieve Length Generalization But Not Robustly [76.06308648699357]
  We show that the success of length generalization is intricately linked to the data format and the type of position encoding. We show for the first time that standard Transformers can extrapolate to a sequence length that is 2.5x the input length.
  arXiv  Detail & Related papers  (2024-02-14T18:18:29Z)
• What Algorithms can Transformers Learn? A Study in Length Generalization [23.970598914609916]
  We study the scope of Transformers' abilities in the specific setting of length generalization on algorithmic tasks. Specifically, we leverage RASP -- a programming language designed for the computational model of a Transformer. Our work provides a novel perspective on the mechanisms of compositional generalization and the algorithmic capabilities of Transformers.
  arXiv  Detail & Related papers  (2023-10-24T17:43:29Z)
• Transformers Learn Shortcuts to Automata [52.015990420075944]
  We find that a low-depth Transformer can represent the computations of any finite-state automaton. We show that a Transformer with $O(log T)$ layers can exactly replicate the computation of an automaton on an input sequence of length $T$. We further investigate the brittleness of these solutions and propose potential mitigations.
  arXiv  Detail & Related papers  (2022-10-19T17:45:48Z)
• Iterative Decoding for Compositional Generalization in Transformers [5.269770493488338]
  In sequence-to-sequence learning, transformers are often unable to predict correct outputs for even marginally longer examples. This paper introduces iterative decoding, an alternative to seq2seq learning. We show that transfomers trained via iterative decoding outperform their seq2seq counterparts on the PCFG dataset.
  arXiv  Detail & Related papers  (2021-10-08T14:52:25Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.