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

arXiv:2608.31067 · cs.LG · Submitted 2026-08-31 · Read on arXiv

cs.LG

Submitted: 2026-08-31

Updated: 2026-08-31

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Terminology

• Transformer — 94× in this paper · explained in 2 episodes
• Generalization — 45× in this paper · explained in 13 episodes
• Attention Mechanism — 13× in this paper · explained in 2 episodes
• Accuracy — 12× in this paper · explained in 1 episode
• Embeddings — 8× in this paper · explained in 2 episodes
• Benchmark — 7× in this paper · explained in 2 episodes
• Interpretability — 6× in this paper · explained in 15 episodes
• Activation Function — 3× in this paper · explained in 1 episode
• Adam — 2× in this paper · explained in 2 episodes
• Aggregation — 2× in this paper · explained in 1 episode
• GNNs — 2× in this paper · explained in 2 episodes
• In-Context Learning — 2× in this paper · explained in 4 episodes
• Clustering — 1× in this paper · explained in 2 episodes
• Compositional Generalization — 1× in this paper · explained in 4 episodes
• Core — 1× in this paper · explained in 2 episodes
• Degeneracy — 1× in this paper · explained in 3 episodes
• Graph Neural Networks (GNNs) — 1× in this paper · explained in 7 episodes
• Objective Function — 1× in this paper · explained in 2 episodes
• Quantization — 1× in this paper · explained in 12 episodes
• Representation Learning — 1× in this paper · explained in 2 episodes
• Transformer Architecture — 1× in this paper · explained in 2 episodes

Sources

• Towards Combinatorial Interpretability of Neural Computation
• On the Bottleneck of Graph Neural Networks and its Practical Implications
• Lower Bounds for Chain-of-Thought Reasoning in Hard-Attention Transformers
• Estimating or Propagating Gradients Through Stochastic Neurons for Conditional Computation
• Arithmetic Transformers Can Length-Generalize in Both Operand Length and Count
• On the Design Space Between Transformers and Recursive Neural Nets
• The Neural Data Router: Adaptive Control Flow in Transformers Improves Systematic Generalization
• A Generalization of Transformer Networks to Graphs
• Looped Transformers for Length Generalization
• Looped Transformers as Programmable Computers
• Contextual Position Encoding: Learning to Count What's Important
• On Oversquashing in Graph Neural Networks Through the Lens of Dynamical Systems
• Universal Length Generalization with Turing Programs
• A Formal Framework for Understanding Length Generalization in Transformers
• Length Generalization in Arithmetic Transformers
• Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention
• Functional Interpolation for Relative Positions Improves Long Context Transformers
• What graph neural networks cannot learn: depth vs width
• Transformers Can Do Arithmetic with the Right Embeddings
• A Little Depth Goes a Long Way: The Expressive Power of Log-Depth Transformers

Related papers

• Polynomial-Augmented Neural Networks (PANNs) with Weak Orthogonality Constraints for Enhanced Function and PDE Approximation
• AIRL-S: Unifying Reinforcement Learning and Search-Based Test-Time Scaling via Adversarial Inverse Reinforcement Learning
• Transformers as Bayesian In-Context Experimenters: Smoothness-Adaptive Efficient ATE Estimation
• Convergence issues in Relational Concept Analysis based on AOC-posets
• Beliefs Beyond Posteriors: Local-Consistency Optimisation for Bayesian Neural Networks
• Understanding Diffusion Models via Ratio-Based Function Approximation with SignReLU Networks