Metraipolis › archive › dc_5c2d848786eb

Length Generalization for Transformers via Compression — arXiv:2609.08851

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.08851
License (as archived)
CC0-1.0
Archived
2026-10-16T13:58:25.259Z
SHA-256 of the archived text
6eb718cb03a5ca5500105e353340b56de28f4b854a2a10fd05be7cc090badcac
Stable URL of this page
https://metraipolis.com/documento/dc_5c2d848786eb

How to cite

Length Generalization for Transformers via Compression — arXiv:2609.08851 — arXiv (en), https://arxiv.org/abs/2609.08851 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_5c2d848786eb (Metraipolis archive dc_5c2d848786eb, sha256 6eb718cb03a5ca5500105e353340b56de28f4b854a2a10fd05be7cc090badcac)
BibTeX
@misc{dc5c2d848786eb,
  title = {Length Generalization for Transformers via Compression — arXiv:2609.08851},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.08851},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_5c2d848786eb; sha256 6eb718cb03a5ca5500105e353340b56de28f4b854a2a10fd05be7cc090badcac},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.08851. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Recent advancements in transformer length generalization theory enable us to reliably predict when a transformer can learn to solve a task. In particular, the C-RASP hypothesis (a formalized version of the so-called RASP-l conjecture) posits that transformers length-generalize on a task if and only if a solution is expressible in the C-RASP language. While this hypothesis has strong empirical validation, theoretical problems arise from the fact that no computable length generalization bounds exist for C-RASP, alongside the discovery of seemingly contradictory experiments. To address these problems, we refine the C-RASP hypothesis utilizing the recently-proposed fragments C-RASP+ and C-RASP1. These fragments have computable length generalization bounds, though in the worst case requiring an extremely large (double exponential) sample size. It is an open question whether these sample size bounds are tight. In this paper, we resolve this open question by providing an exponentially tighter bound. In doing so, we show a polynomial length generalization bound for transformers if we adopt compressed strings, via a novel connection to power words. As an application, we show how this yields a fine-grained analysis of the C-RASP conjecture that resolves contradicting experimental evidence against it.

Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-09 in cs.LG).
Categorie arXiv: Machine Learning (cs.LG) ; Formal Languages and Automata Theory (cs.FL); Logic in Computer Science (cs.LO).
Pagina del lavoro: https://arxiv.org/abs/2609.08851 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T13:39:43.071Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-09-09?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).