Metraipolis › archive › dc_609bab0ae889

Length-Independent State Tracking Under a Parallel Scan — arXiv:2609.32447

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.32447
License (as archived)
CC0-1.0
Archived
2026-10-07T22:36:35.348Z
SHA-256 of the archived text
af6bacaccf1d26ca91f2644e4a44cb9c295ea5f20964cdadf99c3ec09bf4a633
Stable URL of this page
https://metraipolis.com/documento/dc_609bab0ae889

How to cite

Length-Independent State Tracking Under a Parallel Scan — arXiv:2609.32447 — arXiv (en), https://arxiv.org/abs/2609.32447 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_609bab0ae889 (Metraipolis archive dc_609bab0ae889, sha256 af6bacaccf1d26ca91f2644e4a44cb9c295ea5f20964cdadf99c3ec09bf4a633)
BibTeX
@misc{dc609bab0ae889,
  title = {Length-Independent State Tracking Under a Parallel Scan — arXiv:2609.32447},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.32447},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_609bab0ae889; sha256 af6bacaccf1d26ca91f2644e4a44cb9c295ea5f20964cdadf99c3ec09bf4a633},
  year = {2026}
}

Archived text

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

Learning robust and scalable finite-state tracking is fundamental to sequence processing. While linear recurrent neural networks (RNNs), linear attention, and state space models enable scalable parallel training through affine recurrences, their theoretical expressivity guarantees assume idealized arithmetic and do not extend to finite precision, where the parallel scan that makes them fast is itself a source of perturbation. We formalize finite-state tracking at finite precision and characterize length independence: tracking that stays correct at every sequence length, at a precision cost that does not grow with the length. We show that length-independent state tracking requires two competing dynamics within a single map: contraction to suppress numerical perturbations and separation to keep distinct states apart. We prove that affine recurrences, which offer a single rate at each step to serve both roles, realize at most definite automata at finite precision. Instead of treating scan compatibility as a restriction on the update map, we reinterpret it as a computational budget and introduce the Neural Finite-State Machine (NFSM): a nonaffine, scan-compatible RNN built for length-independent finite-state tracking. On synthetic benchmarks spanning abelian and nonabelian groups, noninvertible monoids, and textual state-tracking tasks, affine baselines fail on every nondefinite task, most of them within a few hundred steps. A single NFSM layer instead learns the exact transition tables of every algebraic task, which certifies correctness beyond the tested lengths, and a stack of NFSMs keeps perfect accuracy on the textual tasks at every tested length.

Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-29 in cs.LG).
Categorie arXiv: Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2609.32447 — 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-07T22:14:27.685Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-09-29?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).