Skip to content
DraconiticResearch
Search Sources API
203,234 studies31 sourcesUpdated 38 min ago
PreprintCC BY 4.0arXiv

Limitations on Autoregressive Token Generation via Sequential Sampling

  • Gal Arnon
  • Andrej Bogdanov
  • Paul Lou
  • Giulio Malavolta
  • Alon Rosen
  • Lorenzo Taschin
Open at sourcePDFDOICite

Abstract

We study autoregressive token generation through the notion of sequential samplers: A circuit that samples the next symbol only given the previous ones and possibly a small amount of state. We show that (1) a sequential sampler with k bits of state can be simulated by a stateless one at a roughly O(2k) size overhead; (2) efficient insertional sampling (Stern, Chan, Kiros, Uszkoreit, ICML 2019) is more powerful than efficient sequential sampling in any fixed order; (3) sequential samplers with small state cannot establish certain forms of covert cryptographic channels. Result (1), together with the pseudoentropy vs. sequential sampleability duality of Vadhan and Zheng (STOC 2012), characterizes efficient sequential sampleability with small state. Result (3) provides a potential safety mechanism against subliminal coordination among malicious LLM agents.

Related

  1. Sampling with Autoregressive Clock Jitter: Infinite-Dimensional Stability Failure and Finite-Dimensional Conditioning
    Daniele Gerosa, Thomas Eriksson
    arXivPreprintCC BY-NC-ND 4.0Full textGeneral mathematicsarXiv
  2. SkillComm: Skill-Driven Semantic Communication for Sequential Workflows via Incremental Token Transmission
    Ziyang Meng, Lu Lu
    arXivPreprintarXiv licenceFull textGeneral mathematicsarXiv
  3. Ada-TokenCom: Rate-Adaptive Token Communications via Large-Model-Driven Token Compression and Generation
    Zijun Zhang, Li Qiao, Mahdi Boloursaz Mashhadi +3
    arXivPreprintarXiv licenceFull textGeneral mathematicsarXiv
  4. Nonlinear Assimilation via Score-Based Sequential Langevin Sampling
    Zhao Ding, Chenguang Duan, Yuling Jiao +3
    IEEE Transactions on Information TheoryPeer-reviewedLicence not statedFull text14 citedStatisticsOpenAlex
  5. Sequential Random Sampling PIR with Multiple Colluding Servers in DNA-Based Data Storage
    Chen Wang, Natalia Silberstein, Eitan Yaakobi
    arXivPreprintarXiv licenceFull textGeneral mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{arnon2026limitations,
  title = {{Limitations on Autoregressive Token Generation via Sequential Sampling}},
  author = {Gal Arnon and Andrej Bogdanov and Paul Lou and Giulio Malavolta and Alon Rosen and Lorenzo Taschin},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.14615},
  eprint = {2610.14615},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.14615},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Limitations on Autoregressive Token Generation via Sequential Sampling
AU  - Gal Arnon
AU  - Andrej Bogdanov
AU  - Paul Lou
AU  - Giulio Malavolta
AU  - Alon Rosen
AU  - Lorenzo Taschin
PY  - 2026
DA  - 2026/10/14
PB  - arXiv
DO  - 10.48550/arxiv.2610.14615
UR  - https://arxiv.org/abs/2610.14615
AB  - We study autoregressive token generation through the notion of sequential samplers: A circuit that samples the next symbol only given the previous ones and possibly a small amount of state. We show that (1) a sequential sampler with k bits of state can be simulated by a stateless one at a roughly O(2^k) size overhead; (2) efficient insertional sampling (Stern, Chan, Kiros, Uszkoreit, ICML 2019) is more powerful than efficient sequential sampling in any fixed order; (3) sequential samplers with small state cannot establish certain forms of covert cryptographic channels. Result (1), together with the pseudoentropy vs. sequential sampleability duality of Vadhan and Zheng (STOC 2012), characterizes efficient sequential sampleability with small state. Result (3) provides a potential safety mechanism against subliminal coordination among malicious LLM agents.
ER  -