Paper: Algebraic Decomposition Theory for Transformer Length Generalization
tokenbender · x · 2026-08-16
This paper addresses the problem of length generalization in Transformers: determining if a model trained on short sequences will function correctly on longer ones. The authors provide the first complete characterization of which regular languages allow for length generalization and introduce a polynomial-time decision algorithm. The research reveals that classical algebraic tools like Krohn-Rhodes decomposition are insufficient for C-RASP, the formalism describing length generalization, because key building blocks like unbounded counting are invisible to finite semigroup theory.
More from Research
- New Architecture RHEA: Train 1B Model on 8GB VRAM — zemondza · 2026-08-24
- Trained two 16M-param models to do generative CAD with real physics — debreuil · 2026-08-24
- Claude model helps discover complex structure on S^6, solving 60-year-old math problem — Singularitarian · 2026-08-24
- Study: Agents read instructions/notes 60.5% of the time, rarely touch API docs — dair_ai · 2026-08-24
- Claude Verifies 43 Lean Modules autonomously, Tackling Theoretical Physics — Tkaraletsos · 2026-08-24
- AI fakes memory: why it gets confidently wrong without forgetting — PrajwalTomar_ · 2026-08-24