Limits on sequential token generation and secure sampling methods

Limitations on Autoregressive Token Generation via Sequential Sampling

Information TheoryArtificial IntelligenceCryptography and Security

Summary

This paper looks at how certain algorithms generate tokens one after another based only on the previous tokens and a little extra memory. The authors find that having a small memory doesn’t give much advantage over having none, besides making the process bigger and more complex. They also show that another approach, called insertional sampling, can do things more powerfully than just following the natural token order. Lastly, they find that simple memory-limited methods can’t hide secret communications, which could help stop bad AI agents from secretly working together. These insights help clarify what such token-generating systems can and cannot do.

What this means in practice

  • For ai security teams: Prevent covert communication among malicious AI agents by restricting token generation models to limited-memory sequential samplers.
  • For machine learning engineers: Design token generation systems knowing the limitations of state size on efficiency and sampleability to guide algorithm choices.

A theory result. No direct application yet.

Authors

Gal Arnon, Andrej Bogdanov, Paul Lou, Giulio Malavolta, Alon Rosen, Lorenzo Taschin

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(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.
View PDFOpen arXiv