- 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 bits of private state can be estimated with an overhead proportional to 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 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