Metraipolis › archive › dc_01fd604ec54a
A Fine-Grained Hierarchy and Benchmark for State Tracking in Language Models — arXiv:2611.03094
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.03094
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-03T10:54:28.333Z
- SHA-256 of the archived text
c61a72b669f51c9c19df8c3497a0b9021b390c4d9327582436e0b5485c739396- Stable URL of this page
https://metraipolis.com/documento/dc_01fd604ec54a
How to cite
A Fine-Grained Hierarchy and Benchmark for State Tracking in Language Models — arXiv:2611.03094 — arXiv (en), https://arxiv.org/abs/2611.03094 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_01fd604ec54a (Metraipolis archive dc_01fd604ec54a, sha256 c61a72b669f51c9c19df8c3497a0b9021b390c4d9327582436e0b5485c739396)
BibTeX
@misc{dc01fd604ec54a,
title = {A Fine-Grained Hierarchy and Benchmark for State Tracking in Language Models — arXiv:2611.03094},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.03094},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_01fd604ec54a; sha256 c61a72b669f51c9c19df8c3497a0b9021b390c4d9327582436e0b5485c739396},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.03094. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Theoretical limitations of transformers on state tracking---the ability to track information about entities or variables over long contexts---have motivated new recurrent language modeling (LM) architectures such as Gated DeltaNet (GDN). These architectures have, in particular, been benchmarked against the $S_5$ word problem, a theoretically hard state-tracking task that captures abilities such as code evaluation under arbitrary variable assignment. It, however, remains open whether other, simpler forms of state tracking might both be more relevant in practice and already explain observed differences between these architectures. We propose evaluating state tracking using a hierarchy of word problems with four increasing levels of difficulty: r-trivial, corresponding to immutable assignment to variables in programming; aperiodic, where assignments are mutable; soluble, where assignments are self-referential; and general finite state tracking. Theoretically, we show that the class of problems transformers are thought to length-generalize on does not even contain all aperiodic state tracking. On the other hand, we prove that GDN with positive eigenvalues expresses all aperiodic problems, and the regular languages recognized by certain transformers are precisely all soluble ones, thus providing a fine-grained picture of state tracking capabilities of various architectures. Taking these ideas to practice, we construct StateBench, a 4-tier long-horizon state-tracking benchmark. Our systematic direct training experiments across architectures largely align with theoretical expectation, albeit with interesting observations at very large scale length-generalization. Additionally, we also evaluate pretrained models---both open hybrid and closed frontier ones---on StateBench, finding that none of them robustly solves even soluble state tracking, suggesting a direction for future improvement. Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.AI, nuovi lavori del giorno). Categorie arXiv: Artificial Intelligence (cs.AI). Pagina del lavoro: https://arxiv.org/abs/2611.03094 — 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-11-03T10:49:38.409Z dalla pagina https://arxiv.org/list/cs.AI/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).