acceptodds
Under review as a conference paper at ICLR 2027

Limitations on Autoregressive Token Generation via Sequential Sampling

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 bits of state can be simulated by a stateless one at a roughly 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.

Primary area:
other topics in machine learning (i.e., none of the above)
Keywords:
cryptography, autoregressive generation

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_d9gvOpenReview ↗
Rating
4
Confidence
3
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

The paper studies the computational limitations of autoregressive token generation through sequential samplers. In this model, each step generates the next token using the previously generated tokens and possibly a bounded amount of private state. Building on the pseudoentropy–sampleability connection of [Vadhan–Zheng, 2012] and [Agrawal et al., 2019], the paper shows that kk bits of private state can be estimated with an overhead proportional to 2k2^k in the circuit size, up to polynomial factors in the other parameters. The paper then studies the more powerful insertional sampler, which can insert a new token anywhere in the output. It characterizes insertional sampling by establishing the connection between insertional pseudoentropy and sampleability. Then, it constructs a pseudorandom distribution that can be sampled efficiently by insertion but cannot be accurately sampled by efficient sequential samplers in any fixed order. However, the paper shows that the insertional sequential sampler is still weaker than general samplers. Lastly, the paper discusses implications for the cryptographic capabilities and safety of autoregressive models, including limitations on cryptographic tasks and potential safeguards against certain forms of covert communication.

Critical strengths

S1. Theorem 1.2 provides a substantive extension of the previous characterization for stateless sequential sampling. Particularly, it shows that allowing logarithmic private state does not remove the computational limitations established in the stateless setting. This gives a useful general result about the role of private memory in sequential generation.

S2. The separation between insertional sampling and sequential sampling in every fixed order is an important conceptual contribution. The simpler example (f(X),X)(f(X),X) can be handled by changing the generation order, whereas the pseudorandom construction rules out every fixed-order sampling. The idea of using the intermediate string to retain a seed and then concealing its origin through randomized insertions is nice and intuitive.

S3. The problem has a direct connection to autoregressive LLMs and alternative generation mechanisms. Since the next-token computations can be arbitrary polynomial-size circuits, the results identify limitations that persist even when training and model selection are unrestricted. The consequences for public-key encryption and steganography also give concrete examples of how restrictions on generation and private memory affect cryptographic capabilities.

Critical weaknesses

W1. The discussion of covert communication is broader than the formal guarantee. In particular, Corollary 6.4 concerns public-key steganography without a pre-shared secret and under specific correctness, security, and approximation requirements. It does not establish that small-state agents cannot covertly communicate in general. Although these assumptions are stated in Section 6, Appendix G makes the broader claim that such agents “cannot covertly communicate.” The paper should qualify this statement consistently and clarify the scope of the proposed safety implication.

W2. The writing could be improved to cater to a more general ICLR audience. The paper would benefit from more discussion of its connection to general AI/ML and the implications of each main result. Moreover, the paper should explain more about the relation between its main results. It might also be helpful to provide intuitions for key technical ideas in Section 1.1 to highlight the technical contribution.

Questions for authors

N/A

Reviewer_Wu8bOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper models autoregressive generation as a sequential sampler: a sequence of efficient randomized circuits in which each step sees the visible prefix and possibly a few bits of private state. It also studies insertional samplers, which may insert each new token anywhere in the current string. For both models, the paper links the existence of an efficient sampler with small KL error to a pseudoentropy gap.

The authors restate the known characterization for fixed-order samplers, show that a small amount of private state can be removed at modest cost, and prove a new characterization for insertional samplers. They show that insertion can sample some distributions, including a pseudorandom generator, that no fixed order can, but that insertion cannot sample everything. Finally, they argue that small-state sequential samplers cannot perform certain cryptographic tasks, and present this as a safety mechanism against covert communication between LLM agents.

Critical strengths
  1. Well written and sound.

The paper is clear and easy to follow for its level of technicality. Definitions are precise and the proof overviews and well written. The paper comprehensively addresses the problem, and is easy to understand for a diverse audience.

  1. Technical paper with new ideas.

The paper introduces insertional samplers and a matching notion of insertional pseudoentropy, and proves a characterization connecting the two. It shows how to remove a small amount of private state from a sequential sampler. It also gives clear examples of separation: a pseudorandom generator that can be sampled by insertion but not in any fixed order, and a distribution that even insertion cannot sample.

Critical weaknesses
  1. The claims about cryptography and LLM agents feel overstated.

The abstract, Section 1.1, and Appendix G present the results as a safety mechanism against covert communication between LLM agents. The results only cover the case where the agents share no secret. Copies of the same model share weights, which can store a secret key, and with a shared key secret communication is possible without memory. Real agents also usually have far more private state than the paper allows. These claims should be narrowed.

Questions for authors
  1. Can you clarify the novelty of the arguments in the paper? What parts are known from before, and what are the precise contributions of this paper?
  2. Are there cryptographic schemes where your results apply when agents share a secret, for example through shared weights?
Reviewer_C5VYOpenReview ↗
Rating
3
Confidence
1
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

The paper models autoregressive generation as sequential samplers and proves several results. First, a stateless sampler can approximate a stateful one at additional cost: k bits of state can be removed at 2^k × poly overhead. The authors use this to argue that samplers with O(log n) bits of state cannot generate several cryptographic distributions, which they present as a potential safety mechanism against subliminal coordination among malicious LLM agents. The paper also studies insertional samplers, which can place tokens at any position, and shows that they are strictly more powerful than fixed-order sequential samplers. The results are purely theoretical, with no empirical validation.

Critical strengths
  1. The paper appears to provide rigorous theoretical guarantees, although I have not checked the proofs in detail, as they fall outside my area of expertise.

  2. The security implications are timely and relevant, especially given current LLM research and recent public concerns about LLM agents acting in unintended or adversarial ways.

Critical weaknesses

In practice, sequential samplers such as LLM agents often have substantial hidden state through chain-of-thought, scratchpads, and tools, which places them outside the setting in which the paper's guarantees apply.

Questions for authors

N/A

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.