Autoregressive generation hits a wall: small-state samplers cannot fake pseudorandomness or hide messages, but insertion-based ones can

The limits of token-by-token generation now have a complete characterization: what a sampler can produce when each next symbol depends only on the prefix already emitted is governed by a quantity called next-block pseudoentropy. Earlier characterizations of this obstruction covered only stateless, fixed-order samplers, such as the fact that a stateless sampler cannot output a number followed by its prime factorization unless factoring is easy. Treating the visible prefix as the conditioning variable and the next block as the variable to be sampled, a small next-block pseudoentropy gap holds if and only if an efficient stateless sequential sampler exists with small KL divergence from the target.

Private state can be eliminated: a sequential sampler carrying some bits of state can be approximated in KL divergence by a stateless one. State had been treated as a resource the sampler keeps, and the new simulation shows it can be traded for circuit size that grows with the number of possible states. The simulation estimates the state distribution given the visible prefix from independent samples, using a Laplace estimate so no state gets zero probability; for polynomially many states and inverse-polynomial accuracy the simulating circuits stay polynomial in size.

Insertional sampling is strictly stronger than sequential sampling in any fixed order, because the sampler may place a new symbol anywhere rather than only at the end. For any one-way function, the pair consisting of an input and its image is hard to sample left to right, yet an insertional sampler can emit the image first and insert the preimage afterwards. Assuming one-way functions exist, there is a pseudorandom generator whose output distribution a stateless insertional sampler samples exactly, while that same output is not sequentially samplable in any fixed ordering.

The same boundary acts as a safety property: a state-bounded autoregressive agent cannot open a covert cryptographic channel. Covert communication had been treated as a detection or alignment problem, and the new statement is a computational limit set by the sampler's state and output order. Under IND-CPA-secure public-key encryption and public-key steganography, the encoding distributions of two distinct messages cannot both be sampled with negligible KL divergence by sequential samplers with polynomial-size circuits and logarithmically many private bits.

The characterization addresses researchers and engineers who model generation as a sequence of probabilistic circuits, and it concerns which distributions can be sampled efficiently when circuit size is polynomial in the output length and only bounded private state is kept between steps. It covers stateless sequential sampling, stateful sequential sampling, and insertional sampling, and it relates the three through inclusions and separations. Applying it to a concrete system means deciding which class the target distribution falls into and whether the private-state budget suffices for the cryptographic functionality at stake.

The separation between insertional and general sampling relies on very hard-to-invert one-way functions, and in that construction the token alphabet has bit-length linear in the sequence length, a dependence the authors do not know to be necessary. The cost of eliminating state grows linearly with the number of possible states, and that linear dependence is proved necessary only when the state distribution must be estimated from independent samples, not as a matching circuit-size lower bound for the state-elimination construction. The insertionally samplable pseudorandom generator rests on the assumption that one-way functions exist.