Limitations on Autoregressive Token Generation via Sequential Sampling

1.1 Our Results

• A distribution has a small next-block pseudoentropy gap if and only if it admits an efficient stateless sequential sampler with small KL error.This formalizes the connection between conditional sampleability and pseudoentropy.Source: §1.1 · p. 4
• A sequential sampler with k bits of state can be approximated in KL-divergence by a stateless sampler with circuit-size overhead 2^k and polynomial in other parameters.In the worst case, a factor 2^k overhead is inevitable when estimating the state distribution from independent samples.Source: §1.1 · p. 4
• A distribution has a small insertional pseudoentropy gap if and only if it admits an efficient stateless insertional sampler with small KL error.Insertional sampling can also exceed every fixed-order sampler: for a one-way function f, (f(X), X) is hard to sample left-to-right but easy insertionally.Source: §1.1 · p. 5
• Assuming one-way functions exist, there is a pseudorandom generator whose output distribution can be sampled by a stateless insertional sampler.The paper contrasts this with the next-bit pseudoentropy obstruction for fixed orderings.Source: §1.1 · p. 5
• Assuming very hard-to-invert one-way functions, an efficiently sampleable distribution may not admit efficient stateless insertional sampling.The hard distribution uses tokens with bit-length linear in the sequence length, and the authors do not know whether this dependence is necessary.Source: §1.1 · p. 5
• Bounded state constrains covert communication, while autoregressive models cannot faithfully sample pseudorandom-generator output, a capability the paper identifies as necessary for encryption.The paper says supporting these cryptographic capabilities requires sufficient private state or access to external resources.Source: §1.1 · p. 5

1.2 Further Related Work

• The paper builds on links between computational entropy and sampleability, while noting that insertional generation does not seem to be captured by monotone compression.The cited related work connects next-block pseudoentropy to monotone incompressibility and develops complementary compression and sampling perspectives.Source: §1.2 · p. 6

2.1 Basic Information Theory

• KL divergence decomposes across variables and, for Markov chains, across transitions; applying the same randomized map cannot increase it.The section also recalls nonnegativity, Pinsker’s inequality, and the Markov property.Source: §2.1 · pp. 8–9

2.2 Laplace Estimator

• The Laplace estimator assigns positive mass to every symbol, avoiding infinite KL cases; the section extends its standard expected-KL bound from Q = P to an arbitrary target Q.A separate lemma gives a conditional KL bound using joint and conditional Laplace estimates from sampled pairs.Source: §2.2 · pp. 9–10
• For N = O(K^c), a circuit with Õ(N + K) gates samples within 2^-log2 N KL distance of the Laplace estimator using ⌈(log2 N)^2⌉ + ⌈log2(N + K)⌉ + 1 uniform bits.The circuit depends only on the sample values and domain size.Source: §2.2 · p. 11
• Batched table lookup retrieves L entries from an M-entry table over [K] using Õ(M + L) two-input gates, with a deterministic circuit construction.The stated bound is O((M + L) log^3(2(M + L))).Source: §2.2 · p. 12
• Batched Laplace sampling uses Õ(λ(N + K)) gates and Nλ independent uniform bits to produce N independent outputs with a common distribution.The circuit takes the N input samples and is fixed by N, K, and λ.Source: §2.2 · p. 13
• For η < 1, the cited result gives the following bound for σ: eP(σ) ≥ (1−η)bP(σ).When H = 0, bP is uniform.Source: §2.2 · pp. 13–14

2.3 One-Way Functions

• The cryptographic assumptions use length-preserving one-way functions against nonuniform circuits; Proposition 7.1 needs polynomial-size security, while Theorem 7.2 assumes subexponential security.The latter assumption is T(λ) = 2^{γλ^α} for constants γ > 0 and 1/2 < α < 1.Source: §2.3 · p. 14

2.4 Pseudoentropy

• Nonuniform pseudoentropy is defined using circuit indistinguishability, and conditional pseudoentropy gap is the supremum pseudoentropy minus H(B | X).The conditional definition requires the comparison variable to preserve indistinguishability jointly with X.Source: §2.4 · p. 15
• Next-block pseudoentropy compares a block following a uniform random index with an indistinguishable replacement given the preceding blocks; for one-bit blocks, it is next-bit pseudoentropy.Its asymptotic convention uses polynomial rescaling when comparing it with conditional pseudoentropy.Source: §2.4 · p. 15
• Theorem 2.23 characterizes conditional pseudoentropy gaps through conditional-sampling KL divergence in both directions, with resulting samplers running polynomially in inverse accuracy.The theorem separates distinguishing error from additive KL-divergence loss.Source: §2.4 · p. 16

3 Sequential Sampling Algorithms

• When s = 0, the sequential sampling algorithm is called a stateless sequential sampler.Each circuit samples a block using the preceding outputs and state; invocations use fresh independent coins.Source: §3 · p. 16

3.1 Characterization of Sequential Sampling

• A distribution has a small next-block pseudoentropy gap if and only if it admits an efficient stateless sequential sampler with small KL error.The characterization is formalized quantitatively for fixed-order generation.Source: §3.1 · p. 17
• The characterization relates average next-block KL divergence to joint KL divergence for a uniformly chosen index and its visible prefix.The theorem's construction selects a next-block circuit using the index and prefix; its size remains polynomial when the alphabet bit-length is logarithmic in n.Source: §3.1 · pp. 17–19

4.2 Sampling from an Empirical Distribution

• Estimating the hidden-state distribution conditioned on the visible prefix lets a stateless circuit recover the next-token distribution.The simulator estimates the joint token-state distribution before conditioning on the observed token; the KL chain rule bounds expected error after conditioning, including for rare tokens.Source: §4 · p. 19, §4.2 · pp. 20–21

4.1 Sequential Samplers with State

• The augmented variables A_i = (X_≤i, S_i) form a Markov chain, so the next step depends on earlier history through the current prefix and state.This follows from each circuit's fresh random coins.Source: §4.1 · p. 20

4.2 Sampling from an Empirical Distribution

• For polynomial-size alphabets and k = O(log n), stateful samplers admit polynomial-size stateless approximations at inverse-polynomial KL accuracy.The dependence on the number of states is linear up to logarithmic factors.Source: §4.2 · pp. 20, 24

4.3 Sample Complexity of Estimating the State Distribution

• N ≥ 3|S|/8 independent samples are necessary for expected KL error at most 1/4 on every distribution over S.This lower bound concerns estimating an unknown state distribution from samples and does not establish a matching circuit-size lower bound for the simulation theorem.Source: §4.3 · pp. 24–25

5 Insertional Sampling and Insertional Pseudoentropy

• An insertional sampler chooses both the next token and its position, retains only the current string, and preserves that string as a subsequence at each step.Each circuit uses fresh independent coins.Source: §5 · p. 25
• Insertional pseudoentropy requires an indistinguishable auxiliary insertion whose conditional entropy exceeds the actual insertion entropy by at least k-H(L)/n for every decomposition.The comparison uses a uniform insertion index and (T, ε) indistinguishability; subtracting actual conditional entropy prevents randomness in the insertion order from inflating the gap.Source: §5 · pp. 26–27

5.1 Characterization of Insertional Samplability

• Theorem 5.6 gives both directions: high insertional pseudoentropy constrains every size-B stateless sampler, while low pseudoentropy guarantees a size-B sampler.Lemma 5.11 specifies that the resulting sampler has size bounded by a polynomial in the stated parameters.Source: §5.1 · pp. 27, 28, 32
• For any valid insertional sampler, the final KL divergence is related to conditional divergences along a decomposition, and a Markov insertional decomposition attains the infimum.This connects approximation of the final distribution to conditional sampling at each insertion step.Source: §5.1 · pp. 28, 30
• For each i, a randomized circuit Si has size at most p0(t′, mi, Ki, 1/η′) and KL divergence at most gi + 2η′ from the target conditional distribution.Source: §5.1 · p. 34
• The constructed insertional samplers use fresh independent coins at each step, and their maximum circuit size is bounded by p(t, n, 2ℓ, 1/ϵ).Source: §5.1 · p. 34
• Under 2γλα-secure one-way functions, insertion does not recover all efficient sampling; the construction uses 2t tokens over an alphabet of size 2t · 22t.Source: §5.1 · p. 35

6 Insertionally-Samplable PRGs

• A secure PRG G with seed length t and output length 2t^2 yields a PRG H with seed length 3t^2 and output length 4t^2 whose distribution has an exact polynomial-size stateless insertional bit sampler.The construction uses 3t^2 independent uniform bits.Source: §6 · p. 35
• Inserting fresh random bits before or after each original bit makes the final string conceal which bits were originally generated.The sampler uses only the current string and fresh coins for each transition.Source: §6 · pp. 35–36
• Except with probability at most t2^-t, every group contains an unequal pair, making the seed bits independent and uniform given the inserted-pair string.This statistical closeness, followed by security of G, establishes security of H.Source: §6 · p. 36

7.1 Separating Insertional Samplers from Sequential Samplers

• Every polynomial-size stateless sequential sampler has KL divergence greater than log(n) from a one-way-function-based distribution that a polynomial-size insertional sampler samples exactly.The distribution is L = (f(X), X) for uniform X.Source: §7.1 · p. 36

7.2 Separating General Samplers from Insertional Samplers

• Every sufficiently small stateless insertional sampler has KL error at least γt^(2α) − 2t on a distribution that a polynomial-size randomized circuit samples exactly.The construction uses a one-way function with the stated security parameters; its ramp secret-sharing evaluations let any fixed t tokens be sampled given only the image, while a valid completion reveals a preimage.Source: §7.2 · pp. 37–38

7.3 Separating Pseudoentropy Notions

• For L = (f_n(X), X), the insertional pseudoentropy gap is at most 1/n, while the next-block pseudoentropy gap is at least 1/2 log(n).This separation holds for sufficiently large constants and sufficiently large n, assuming a length-preserving one-way function secure against polynomial-size circuits.Source: §7.3 · p. 39
• For the constructed distribution, ordinary pseudoentropy gap is at most 1/t, while insertional pseudoentropy gap is at least γ2t^(2α).These bounds separate ordinary from insertional pseudoentropy under the stated parameters.Source: §7.3 · p. 40

8.1 Cryptographic hardness for sequential sampling

• A noticeable nonuniform next-block pseudoentropy gap given W rules out a polynomial-size sequential sampler with O(log n) private bits and negligible KL error, even when W and the visible prefix are available at each step.The section also states that such samplers cannot sample pseudorandom-generator distributions, even for any a priori fixed ordering.Source: §8.1 · pp. 40–41
• With polynomial-size circuits and O(log n) private bits, sequential samplers cannot achieve negligible KL error for both ciphertext distributions of any two distinct equal-length messages under the stated encryption assumptions.The public key, message, and visible prefix are available at each step, and divergence is measured jointly with the public key.Source: §8.1 · p. 42
• Under the stated cover-indistinguishability and decoding assumptions, both public-key steganographic encoding distributions cannot be sampled with negligible KL error by such sequential samplers.The public key, message, and visible prefix are available at every step; divergence is measured jointly with the public key.Source: §8.1 · p. 42

8.2 Insertional versus Left-to-Right Token Generation

• A one-token-per-step randomized insertion framework corresponds to stateless insertional sampling, while restricting insertions to the rightmost position gives stateless sequential sampling.Insertional generation can exactly sample some binary-string distributions that efficient left-to-right generation cannot sample even with small KL error; choosing where to write can expand what is efficiently generatable without private memory.Source: §8.2 · pp. 43–44

• The authors used Chat-GPT 6 Astra to assist with writing and revising the manuscript.Source: AI use statement · p. 44
• The authors used the model to help check mathematical arguments for gaps and errors.Source: AI use statement · p. 44
• The authors take full responsibility for the final content, including claims, proofs, and references.Source: AI use statement · p. 44