Paper deep dive
Limitations on Autoregressive Token Generation via Sequential Sampling
Gal Arnon, Andrej Bogdanov, Paul Lou, Giulio Malavolta, Alon Rosen, Lorenzo Taschin
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 93%
Last extracted: 10/14/2026, 10:13:31 AM
Summary
This paper investigates the theoretical limitations of autoregressive token generation by modeling it as sequential sampling. It establishes that stateful sequential samplers with k bits of state can be simulated by stateless ones with an exponential size overhead of O(2^k). The study introduces 'insertional sampling' as a more powerful alternative to fixed-order sequential sampling, showing that insertional samplers can generate distributions (like those from certain pseudorandom generators) that fixed-order samplers cannot. These findings characterize efficient sampleability via pseudoentropy gaps and suggest that restricting model state or generation order can provide safety mechanisms against covert cryptographic channels in LLMs.
Entities (8)
Relation Signals (5)
Insertional Sampler → ismorepowerfulthan → Sequential Sampler
confidence 96% · efficient insertional sampling ... is more powerful than efficient sequential sampling in any fixed order
Sequential Sampler → hasstateoverhead → Stateless Sampler
confidence 95% · a sequential sampler with k bits of state can be simulated by a stateless one at a roughly O(2^k) size overhead
Pseudoentropy → dualto → Sequential Sampleability
confidence 93% · pseudoentropy vs. sequential sampleability duality of Vadhan and Zheng
Sequential Sampler → cannotestablish → Covert Cryptographic Channels
confidence 90% · sequential samplers with small state cannot establish certain forms of covert cryptographic channels
Insertional Sampler → cansample → Pseudorandom Generator Output
confidence 89% · there is a PRG whose distribution can be sampled by a stateless insertional sampler
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
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.
Tags
Links
- Source: https://arxiv.org/abs/2610.14615v1
- Canonical: https://arxiv.org/abs/2610.14615v1
Trouble viewing inline? Open PDF directly →
Full Text
146,722 characters extracted from source content.
Expand or collapse full text
Limitations on Autoregressive Token Generation via Sequential Sampling Gal Arnon †thanks: galarnon42@gmail.com. The majority of this work was done while the author was a postdoc at Bocconi University Affiliation: NTT Research Andrej Bogdanov †thanks: abogdano@uottawa.ca Affiliation: University of Ottawa Paul Lou †thanks: paul96lou@gmail.com Affiliation: Bocconi University Giulio Malavolta †thanks: giulio.malavolta@hotmail.it Affiliation: Bocconi University Alon Rosen †thanks: alon.rosen@unibocconi.it Affiliation: Bocconi University Lorenzo Taschin †thanks: taschin1998@gmail.com Affiliation: University of Ottawa 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(2k)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. Contents 1 Introduction 1.1 Our Results 1.2 Further Related Work 2 Preliminaries 2.1 Basic Information Theory 2.2 Laplace Estimator 2.3 One-Way Functions 2.4 Pseudoentropy 3 Sequential Sampling Algorithms 3.1 Characterization of Sequential Sampling 4 Stateful Sequential Sampling 4.1 Sequential Samplers with State 4.2 Sampling from an Empirical Distribution 4.3 Sample Complexity of Estimating the State Distribution 5 Insertional Sampling and Insertional Pseudoentropy 5.1 Characterization of Insertional Samplability 6 Insertionally-Samplable PRGs 7 Separations in Sampling and Pseudoentropy 7.1 Separating Insertional Samplers from Sequential Samplers 7.2 Separating General Samplers from Insertional Samplers 7.3 Separating Pseudoentropy Notions 8 Consequences 8.1 Cryptographic hardness for sequential sampling 8.2 Insertional versus Left-to-Right Token Generation References 1 Introduction Autoregressive language models generate an entire response through a sequence of local decisions: sample the next token given the prompt and the tokens already produced. An ordinary randomized sampler, in contrast, is unconstrained by the order in which its output is produced. A long pseudorandom string, for example, can be derived from a short random seed, even though the visible prefix does not reveal its continuation. In this work we fully characterize the class of distributions that can be sampled efficiently one token at a time, using only the preceding output. The probability chain rule factors every distribution into next-token conditionals: p(x1x2x3)=p(x1)p(x2|x1)p(x3|x1x2)p(x_1x_2x_3)=p(x_1)p(x_2|x_1)p(x_3|x_1x_2). However, this formula says nothing about the complexity of sampling those conditionals. An efficient algorithm for generating a whole string need not provide an efficient way to continue from a prefix drawn from the same distribution. Impagliazzo and Levin [7] furnish a sufficient hypothesis for universal efficient sequential sampleability: The average-case invertibility of all efficient functions. Their hypothesis is unreasonable as it would forbid cryptography. (We may be in for surprises!) C1C_1C2C_2C3C_3s1s_1s2s_2X1X_1X2X_2X3X_3 Figure 1: A three-token sequential sampler. We study an abstraction of autoregressive generation called a sequential sampler (see Fig. 1). This is a collection of probabilistic circuits C(1n)=(C1,C2,…,Cn)C(1^n)=(C_1,C_2,…,C_n) generating token sequence X1,X2,…,XnX_1,X_2,…,X_n. Circuit CiC_i takes as inputs the prefix X<i=(X1,…,Xi−1)X_<i=(X_1,…,X_i-1), and possibly a bounded state si−1s_i-1 produced by Ci−1C_i-1. It outputs the next token-state pair (Xi,si)(X_i,s_i). When sis_i are empty the sampler is stateless. Every step can reread the entire prefix sampled so far. Private information generated during one step, including randomness, can only be explicitly passed along through the state. Prompts, as well as other fixed model parameters, can be hardwired into the circuits, so we impose no restriction on the training procedure, attention mechanism, or depth of the next-token computation beyond efficiency, i.e., that the circuit size be polynomial in the total output length. The model captures generation from fixed autoregressive parameters when all information retained between steps is determined by the prompt and generated prefix. Earlier work by Lin et al. [11] identifies sampleability limitations for autoregressive models satisfying the stronger assumption that next-token probabilities are efficiently computable. Fortnow [5] shows that the distributions that can be sampled in this manner are precisely the ones whose cumulative distribution function is efficiently computable [10]. Our model allows for a richer class of distributions. More relevant to our model is the limitation observed by Wu [17]: A stateless sequential sampler cannot generate a number followed by its prime factorization, unless factoring is easy. Vadhan and Zheng [16] and Agrawal et al. [1] fully characterize this type of obstruction for stateless, fixed-order samplers. Our approach is based on the duality between conditional sampleability and pseudoentropy discovered by Vadhan and Zheng [16]. Agrawal et al. [1] interpret this connection in the context of stateless sequential sampling. We derive analogous characterizations for stateful and insertional samplers. 1.1 Our Results All reasonable sampling notions tolerate some error of the sampler C(1n)C(1^n) relative to the target distribution Y. A natural measure, which we adopt in this work, is their KL-divergence D(Y∥C(1n))D_ KL (Y~\|~C(1^n) ). Note that small KL-divergence implies small total variation distance. Characterizing sequential samplers. For left-to-right generation, the relevant quantity is next-block pseudoentropy. It measures how much entropy the next token can appear to have, given the true preceding prefix, summed over the positions. The next-block pseudoentropy gap is the difference between this quantity and the true entropy of the complete string. This equivalence follows from the work of Vadhan and Zheng [16] and was informally discussed by Agrawal et al. [1]. We give a formal, quantitative statement and proof: Theorem 1.1 (Vadhan and Zheng [16], Agrawal et al. [1], see Theorem 3.3). 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 next-token circuits can be chosen with full knowledge of the target, independently of any learning algorithm. A large pseudoentropy gap therefore identifies a limitation that persists even when training and model selection are unrestricted. We show that the above extends beyond stateless samplers. The reason is that private state can be eliminated, at a cost polynomial in the number of possible states: Theorem 1.2 (Theorem 4.3, informal). A sequential sampler with k bits of state can be approximated in KL-divergence by a stateless sequential sampler. The circuit-size overhead is 2k2^k and polynomial in the other parameters, including token alphabet size. A factor 2k2^k blowup in overhead is inevitable—in the worst case—for simulation that estimates the state distribution from independent samples. As intuition, a pseudorandom generator with a k-bit seed admits an efficient stateful implementation that stores the seed. A stateless implementation, however, seems to effectively require brute-force search over all possible seeds. See Section 4.3. Insertional Samplers. An insertional sampler can insert a new token anywhere in the output, not just at the terminal position. The Insertion Transformer [15] is endowed with this capability. The sampler still retains bounded private state, but can generate information in an order suited to the task. We introduce the notion of insertional pseudoentropy gap to measure how much the apparent conditional entropy can exceed the actual conditional entropy, summed over the insertions, for every insertional decomposition of the target. We show a duality between insertional pseudoentropy and sampleability: Theorem 1.3 (Theorem 5.6, informal). A distribution has a small insertional pseudoentropy gap if and only if it admits an efficient stateless insertional sampler with small KL error. Insertional samplers are more powerful than sequential ones: Going back to the factoring example, one can simply output the factors first, then insert their product in the first position of the sequence. In fact, this is not just a property of factoring: For any one-way function f,11 1 Recall that a one-way function f is a function where y=f(x)y=f(x) is easy to compute for every x, but it is hard to find a preimage of y when x is sampled uniformly at random. the pair (f(X),X)(f(X),X) is hard to sample in a left-to-right manner but easy to sample insertionally (Proposition 7.1). In contrast to the pair (f(X),X)(f(X),X) which is easy to sample from right-to-left, a pseudorandom generator22 2 A pseudorandom generator G:0,1n→0,1mG \0,1\^n→\0,1\^m is a length-extending function where G(s)G(s) for a uniformly random s←0,1ns←\0,1\^n is computationally indistinguishable from a uniformly sampled string over 0,1m\0,1\^m. is not sequentially samplable for any fixed ordering. This is because it has next-bit pseudoentropy with respect to every fixed ordering of the output bits (see Corollary 8.2). Thus, one might expect that the pseudorandom generator output distribution is not insertionally sampleable. Yet, surprisingly, we demonstrate the existence of pseudorandom generators whose output can be sampled insertionally: Theorem 1.4 (Theorem 6.1, informal). Assuming one-way functions exist, there is a PRG whose distribution can be sampled by a stateless insertional sampler. Our construction crucially exploits the stochasticity of the insertion positions. We further demonstrate a separation between insertional and arbitrary samplers, indicating a limitation of their computational capabilities: Theorem 1.5 (Theorem 7.2, informal). Assuming the existence of very hard-to-invert one-way functions, there is an efficiently sampleable distribution that cannot be sampled efficiently in a stateless insertional manner. The token alphabet in our hard distribution has bit-length linear in the sequence length n. We do not know if this dependence is necessary. Consequences (Section 8). Our results reveal fundamental tradeoffs between the expressive power of generative models and their cryptographic capabilities. More restrictive architectures provide automatic safety guarantees. More expressive architectures, in contrast, could be useful for training cryptographic functionalities. Cryptographic capabilities and safeguards. Autoregressive models face limits even on useful tasks that ordinary programs perform routinely. Our results imply that they cannot faithfully sample the output of a pseudorandom generator, a necessity for encryption. Supporting these capabilities requires sufficient private state or access to external resources. This limitation can be beneficial for safety. Untrusted agents might try to establish a covert channel via steganographic techniques. Bounding the state of transformer-type agents constrains their ability to communicate in secret. A case for insertion-based models. At the level of generation rules, insertion is strictly more expressive than left-to-right generation in our stateless setting. The freedom to choose where to write can therefore expand a model’s capabilities without adding private memory. For example, as we have shown, useful cryptography can be computed statelessly by insertion-based models but not by models with any apriori fixed order. This provides a theoretical foundation for pursuing insertion-based models as an alternative to strictly autoregressive generation. 1.2 Further Related Work Computational entropy provides several ways to express the difficulty of producing correlated outputs. Inaccessible entropy, introduced by Haitner et al. [6], measures the entropy an online generator can produce when its previous random coins are included in the conditioning information. Agrawal et al. [1] unify this notion with next-block pseudoentropy through hardness in relative entropy. We use the prefix-only sampling connection from this theory as a foundation; the insertional analysis must additionally handle intermediate strings and the information in their generation order. Our next-token circuits sample their outputs, and their output probabilities need not be efficiently evaluable. This distinguishes the model from the probability-evaluation setting of Lin et al. [11]. Wu’s factoring-based example [17] already exhibits a limitation for randomized prefix-only generation. The entropy characterization provides a general criterion; our insertional analysis extends this viewpoint to alternative generation orders. Recent work also studies the computational role of generation order. Kim et al. [9] analyze hard masking conditionals under computational assumptions and the benefits of choosing favorable orders. Yang et al. [18] compare autoregressive, masked, and editing-based generation; their autoregressive simulation of arbitrary orders emits position–token pairs and permits postprocessing. Our samplers must directly produce the prescribed output string, so that simulation does not imply equivalence in our model. Jiang et al. [8] study parallel sampling efficiency and simulation of randomized circuits by diffusion models with auxiliary tokens. Their resource bounds complement our focus on the distributions that can be generated under restrictions on private state and output order. Mazor, Morgan, and Pass [12] show that efficient autoregressive models with efficiently evaluable next-token probabilities are equivalent to efficient monotone, prefix-free compression, up to an additive two bits between excess cross-entropy and compression redundancy. Combining this with the Vadhan–Zheng characterization relates next-bit pseudoentropy to monotone incompressibility. Their cryptographic separation uses a distribution of the form (G(U),U)(G(U),U) for a pseudorandom generator G, closely related to our fixed-order sampling obstruction based on (f(U),U)(f(U),U). Our main results quantify the cost of eliminating private state and characterize the power and limitations of insertional sampling, allowing general randomized transitions without requiring efficient probability evaluation. Thus, the two works share a fixed-order pseudoentropy foundation while developing complementary compression and sampling perspectives. Interestingly, the notion of insertional generation does not seem to be captured by monotone compression. 2 Preliminaries For n∈ℕn , define the set [n]=1,…,n[n]=\1,…,n\. For any set X, we define X0≔∅X^0 \ \ where ∅ denotes the empty string. We say that a string x is a subsequence of y if x can be produced from y by deletions. For any two random variables or two distributions X,YX,Y, we will use Δ(X,Y)≔12⋅∑a∈(X)∪(Y)|Pr[X=a]−Pr[Y=a]|∈[0,1] (X,Y) 12· _a∈ supp(X)∪ supp(Y) [X = a] - [Y =a] ∈[0,1] to denote the total variation distance between X and Y. Our default logarithm function log is in base two. Every randomized circuit uses fresh independent fair coins. If X,YX,Y are random variables where Y has support Y, then for any y∈y we use the notation X∣Y=yX _Y=y to denote the conditional distribution of X conditioned on the event that Y=yY=y. A function f in parameter λ∈ℕλ is noticeable if there exists a polynomial p(λ)p(λ) such that for all sufficiently large λ, f(λ)>1/p(λ)f(λ)>1/p(λ). For a parameter λ∈ℕλ , for any two functions α=α(λ)α=α(λ) and β=β(λ)β=β(λ), we say that β is noticeably larger α if there exists a noticeable function γ=γ(λ)γ=γ(λ) such that β>α+γβ>α+γ. A function f in parameter λ∈ℕλ is negligible if for all polynomials p(λ)p(λ), for sufficiently large enough λ, we have f(λ)<1/p(λ)f(λ)<1/p(λ). 2.1 Basic Information Theory We now recall relevant definitions and related facts from information theory. Definition 2.1 (Shannon entropy). For a discrete random variable X with finite support, we define the Shannon entropy of X to be H(X)≔−x∼X[log2Pr(X=x)]H(X) - _x X[ _2 (X = x)]. Definition 2.2 (Binary entropy). For p∈[0,1]p∈[0,1], define the binary entropy function h(p)=−plog2p−(1−p)log2(1−p)h(p)=-p _2p-(1-p) _2(1-p). Definition 2.3 (KL divergence). Let P,QP,Q be distributions over a finite set Ω . If P is absolutely continuous with respect to Q, meaning that P(a)>0P(a)>0 implies Q(a)>0Q(a)>0, then the KL divergence from P to Q is DKL(P∥Q)≔∑a∈ΩP(a)logP(a)Q(a).D_KL(P\|Q) _a∈ P(a) P(a)Q(a). If P is not absolutely continuous with respect to Q, we define DKL(P∥Q)=+∞D_KL(P\|Q)=+∞. Fact 2.4 (Nonnegativity of KL divergence; see Theorem 2.6.3 in Cover and Thomas [4]). For any two distributions P,QP,Q over a finite set Ω , DKL(P∥Q)≥0D_KL(P\|Q)≥ 0. Fact 2.5 (Pinsker’s inequality; Lemma 11.6.1 in Cover and Thomas [4]). For finite distributions P,QP,Q, Δ(P,Q)≤(ln2)D(P∥Q)/2. (P,Q)≤ ( 2)D_ KL (P~\|~Q )/2. Definition 2.6 (Markov chain; see Chapter 4 in Cover and Thomas [4]). A sequence of random variables Z1,…,ZnZ_1,…,Z_n over finite sets is a Markov chain, denoted Z1−Z2−⋯−ZnZ_1-Z_2-·s-Z_n if for every i∈2,…,n−1i∈\2,…,n-1\, Pr[Zi+1=zi+1∣Z1=z1,…,Zi=zi]=Pr[Zi+1=zi+1∣Zi=zi] [Z_i+1=z_i+1 Z_1=z_1,…,Z_i=z_i]= [Z_i+1=z_i+1 Z_i=z_i] whenever the conditioning event has positive probability. Equivalently, for every i∈2,…,n−1i∈\2,…,n-1\, Zi+1Z_i+1 is conditionally independent of (Z1,…,Zi−1)(Z_1,…,Z_i-1) given ZiZ_i. The KL chain rule compares two joint distributions by first comparing one variable, then comparing the other conditioned on the first. Fact 2.7 (KL chain rule; Theorem 2.5.3 in Cover and Thomas [4]). Let PXYP_XY and QXYQ_XY be distributions over the same finite set ×X×Y. Then D(PXY∥QXY)=D(PX∥QX)+x∼PXD(PY|X=x∥QY|X=x).D_ KL (P_XY~\|~Q_XY )=D_ KL (P_X~\|~Q_X )+ _x P_XD_ KL (P_Y X=x~\|~Q_Y X=x ). Conditional distributions on events of probability zero may be chosen arbitrarily, and the expectation sums only over x with PX(x)>0P_X(x)>0. The identity allows infinite divergence. Iterating the chain rule gives a sum over steps, each conditioned on the full preceding history. For Markov chains, the conditioning reduces to the preceding variable. Fact 2.8 (KL chain rule for Markov chains). Let n≥1n≥ 1 and let X0,…,XnX_0,…,X_n and Y0,…,YnY_0,…,Y_n be Markov chains, where for each i the variables Xi,YiX_i,Y_i take values in the same finite set, which may depend on i. If they have the same initial distribution, X0≡Y0X_0≡ Y_0, then D((X0,…,Xn)∥(Y0,…,Yn))=∑i=1nx∼Xi−1D(Xi∣Xi−1=x∥Yi∣Yi−1=x).D_ KL ((X_0,…,X_n)~\|~(Y_0,…,Y_n) )= _i=1^n _x X_i-1D_ KL (X_i _X_i-1=x~\|~Y_i _Y_i-1=x ). (1) Both transitions are conditioned on the same value x, sampled from Xi−1X_i-1, with the same conventions for zero-probability events as above. Proof. Applying Fact 2.7 to the first coordinate gives D((X0,…,Xn)∥(Y0,…,Yn)) D_ KL ((X_0,…,X_n)~\|~(Y_0,…,Y_n) ) =D(X0∥Y0)+x0∼X0D((X1,…,Xn)∣X0=x0∥(Y1,…,Yn)∣Y0=x0). =D_ KL (X_0~\|~Y_0 )+ _x_0 X_0D_ KL ((X_1,…,X_n) _X_0=x_0~\|~(Y_1,…,Y_n) _Y_0=x_0 ). Here D(X0∥Y0)=0D_ KL (X_0~\|~Y_0 )=0 because X0≡Y0X_0≡ Y_0. For n=1n=1, this already gives the claim. For i∈[n]i∈[n], write X<i=(X0,…,Xi−1)X_<i=(X_0,…,X_i-1) and Y<i=(Y0,…,Yi−1)Y_<i=(Y_0,…,Y_i-1). For n≥2n≥ 2, applying the same fact inside the expectation separates the next coordinate: D((X0,…,Xn)∥(Y0,…,Yn)) D_ KL ((X_0,…,X_n)~\|~(Y_0,…,Y_n) ) =D(X0∥Y0)+x0∼X0D(X1∣X0=x0∥Y1∣Y0=x0) =D_ KL (X_0~\|~Y_0 )+ _x_0 X_0D_ KL (X_1 _X_0=x_0~\|~Y_1 _Y_0=x_0 ) +(x0,x1)∼(X0,X1)D((X2,…,Xn)∣X0=x0,X1=x1∥(Y2,…,Yn)∣Y0=x0,Y1=x1) + _(x_0,x_1) (X_0,X_1)D_ KL ((X_2,…,X_n) _X_0=x_0,\,X_1=x_1~\|~(Y_2,…,Y_n) _Y_0=x_0,\,Y_1=x_1 ) =∑i=1nx<i∼X<iD(Xi∣X<i=x<i∥Yi∣Y<i=x<i). = _i=1^n _x_<i X_<iD_ KL (X_i _X_<i=x_<i~\|~Y_i _Y_<i=x_<i ). The Markov property gives Xi∣X<i=x<i X_i _X_<i=x_<i ≡Xi∣Xi−1=xi−1, ≡ X_i _X_i-1=x_i-1, Yi∣Y<i=x<i Y_i _Y_<i=x_<i ≡Yi∣Yi−1=xi−1. ≡ Y_i _Y_i-1=x_i-1. Consequently, tuples x<ix_<i with the same last value xi−1=x_i-1=x give the same KL divergence. Their weights in the expectation add up to Pr[Xi−1=x] [X_i-1=x]: x<i∼X<iD(Xi∣X<i=x<i∥Yi∣Y<i=x<i) _x_<i X_<iD_ KL (X_i _X_<i=x_<i~\|~Y_i _Y_<i=x_<i ) =∑x(∑x<i:xi−1=xPr[X<i=x<i])D(Xi∣Xi−1=x∥Yi∣Yi−1=x) = _x ( _ subarraycx_<i:\,x_i-1=x subarray [X_<i=x_<i] )D_ KL (X_i _X_i-1=x~\|~Y_i _Y_i-1=x ) =x∼Xi−1D(Xi∣Xi−1=x∥Yi∣Yi−1=x). = _x X_i-1D_ KL (X_i _X_i-1=x~\|~Y_i _Y_i-1=x ). Substituting these equalities into the expansion proves (1). ∎ The KL inequality below follows from the log-sum inequality [4, Theorem 2.7.1]. Fact 2.9 (Data processing inequality). Let PX,QXP_X,Q_X be distributions on a finite set X. Let PY,QYP_Y,Q_Y be obtained by applying the same randomized map from X to a finite set Y. Then D(PY∥QY)≤D(PX∥QX)D_ KL (P_Y~\|~Q_Y )≤ D_ KL (P_X~\|~Q_X ). 2.2 Laplace Estimator The Laplace estimator allows us to smooth over the cases in which the KL-divergence may be infinity, i.e. it gives every sample non-zero probability mass to prevent this occurrence. In this preliminary section, we recall its definition, basic properties, and the Boolean circuit complexity of the Laplace estimator. In particular, we recall results that imply that we can efficiently batch-sample the Laplace estimator. Definition 2.10 (Laplace estimator; see e.g. [3]). Let P be a distribution over a finite domain Ω of size |Ω|=K| |=K. For N>0N>0, let x¯=x(1),…x(N) x=x^(1),… x^(N) be i.i.d. samples according to P. The Laplace estimator is defined (w.r.t. x¯ x) for any ω∈Ωω∈ as P^N(ω)=1N+K(1+∑j=1N(x(j)=ω)) P_N(ω)= 1N+K (1+ _j=1^N 1(x^(j)=ω) ) (2) The following claim extends the standard expected KL bound for the Laplace estimator (the case Q=PQ=P; see 14, Proposition 4) to an arbitrary target distribution Q. Claim 2.11. Let P,QP,Q be distributions over a finite domain Ω of size K≥1K≥ 1, and let N≥1N≥ 1 be an integer. Let P^N P_N be the Laplace estimate from N independent samples of P. Then D(Q∥P^N)≤D(Q∥P)+logN+KN+1≤D(Q∥P)+(K−1)logeN+1, D_ KL (Q~\|~ P_N )≤ D_ KL (Q~\|~P )+ N+KN+1≤ D_ KL (Q~\|~P )+ (K-1) eN+1, where the expectation is over the samples and logarithms have base two. Proof. If Q is not absolutely continuous with respect to P, the right-hand side is infinite and the claim holds. Otherwise, fix x∈(Q)x∈ supp(Q) and put p=P(x)>0p=P(x)>0. Its sample count VxV_x has distribution Bin(N,p)Bin(N,p), and P^N(x)=(Vx+1)/(N+K) P_N(x)=(V_x+1)/(N+K). Hence [P(x)P^N(x)] [ P(x) P_N(x) ] =p(N+K)[1Vx+1] =p(N+K) [ 1V_x+1 ] =N+KN+1(1−(1−p)N+1)≤N+KN+1. = N+KN+1 (1-(1-p)^N+1 )≤ N+KN+1. The second equality follows by expanding the binomial expectation and using (Nv)/(v+1)=(N+1v+1)/(N+1) Nv/(v+1)= N+1v+1/(N+1). Expanding KL divergence and applying Jensen’s inequality now gives D(Q∥P^N) D_ KL (Q~\|~ P_N ) =D(Q∥P)+∑x∈(Q)Q(x)logP(x)P^N(x) =D_ KL (Q~\|~P )+ _x∈ supp(Q)Q(x) P(x) P_N(x) ≤D(Q∥P)+∑x∈(Q)Q(x)log[P(x)P^N(x)] ≤ D_ KL (Q~\|~P )+ _x∈ supp(Q)Q(x) [ P(x) P_N(x) ] ≤D(Q∥P)+logN+KN+1. ≤ D_ KL (Q~\|~P )+ N+KN+1. Finally, log(1+y)≤yloge (1+y)≤ y e for y≥0y≥ 0 gives the second bound. ∎ Lemma 2.12 (Conditional KL bound from joint Laplace estimation). Let A and ℬB be finite domains, and K=||⋅|ℬ|K= · . Let P,QP,Q be two distributions over ×ℬA×B. Let (Zt,Tt)t=1M(Z_t,T_t)_t=1^M be i.i.d. samples from Q, and let Q Q and Q^ℬ|(⋅∣x) Q_B (· x) denote the corresponding joint and conditional (given x∈x ) Laplace estimates respectively. Then, (Zt,Tt)t=1M∼QMx∼PD(Pℬ|(⋅∣x)∥Q^ℬ|(⋅∣x))≤D(P∥Q)+K−1M+1loge. _(Z_t,T_t)^M_t=1 Q^M\, _x P_AD_ KL (P_B (· x)~\|~ Q_B (· x) )≤ D_ KL (P~\|~Q )+ K-1M+1 e. Proof. For any realization of the sample pairs (Zt,Tt)t=1M(Z_t,T_t)^M_t=1, by the chain rule of KL divergence, x∼PD(Pℬ|(⋅∣x)∥Q^ℬ|(⋅∣x))≤D(P∥Q^). _x P_AD_ KL (P_B (· x)~\|~ Q_B (· x) )≤ D_ KL (P~\|~ Q ). Moreover, by Claim 2.11, (Zt,Tt)t=1M∼QMD(P∥Q^)≤D(P∥Q)+K−1M+1loge. _(Z_t,T_t)^M_t=1 Q^MD_ KL (P~\|~ Q )≤ D_ KL (P~\|~Q )+ K-1M+1 e. Putting the two bounds together gives the promised result. ∎ We now give an analysis of the circuit complexity of sampling the Laplace estimator. Recall that given N samples from an alphabet of size K, the Laplace estimator outputs one of K output symbols with probability exactly given by one plus the number of its occurrences in the N samples divided by N+KN+K. A simple circuit with unbounded-fan-in OR gates implements this estimator with N+KN+K input wires that are all set to zero except for a single input wire that is set to 11. This circuit has one unbounded fan-in OR gate for each of the K output symbols. Enumerate the K OR gates. For i∈[K]i∈[K], connect the iith input wire as an input to the iith OR gate. Then, letting each of the remaining N input wires represent the samples, connect these to their corresponding symbol. This circuit exactly implements the Laplace estimator. However, we consider circuit complexity in terms of fan-in two and in terms of input wires that are uniformly distributed on 0,1\0,1\. This results in the following fact. Fact 2.13. Let P be any distribution over a finite domain of size K. For any constant c≥0c≥ 0, for any N=O(Kc)N=O(K^c) samples sampled from P, there exists a Boolean circuit C depending only on the N sample values and the domain size K with O~(N+K) O(N+K) two-input gates such that C on λ=⌈(log2N)2⌉+⌈log2(N+K)⌉+1λ= ( _2N)^2 + _2(N+K) +1 independent uniform random input wires samples a distribution that is 2−log2N2^- ^2N KL-distance within the Laplace estimator define above. Proof. Fix any N samples x1,…xN∈[K]x_1,… x_N∈[K]. Given λ≔⌈log2N⌉+⌈log2(N+K)⌉+1λ ^2N + _2(N+K) +1 input wires uniform randomly distributed, let U be uniformly distributed over [0,…,2λ−1][0,…,2^λ-1], compute J≔1+⌊(N+K)⋅U⋅2−λ⌋∈[N+K]J 1+ (N+K)· U· 2^-λ ∈[N+K]. If J≤KJ≤ K output the J-th symbol. If J>KJ>K, output the symbol xJ−Kx_J-K. The total Boolean circuit complexity is O~(N+K) O(N+K). Multiplying U with N+KN+K takes O(λ⋅log(N+K))O(λ· (N+K)) gates, dividing by 2λ2^λ is throwing away the lower λ bits using zero gates, and adding 11 takes log(N+K) (N+K) gates. Encode J by the ⌈log2(N+K)⌉ _2(N+K) -bit representation of J−1J-1. First convert this encoding into N+KN+K wires, exactly one of which is one, using O(N+K)O(N+K) gates. Combine the wires corresponding to each symbol using N two-input OR gates in total, and encode the resulting K symbol-indicator wires in binary using O(K)O(K) additional gates. Thus this conversion costs O(N+K)O(N+K) gates. We now bound the KL-divergence. Let P~(σ)=Pr[C(U)=σ] P(σ)= [C(U)=σ] for σ∈[K]σ∈[K]. Let P P be the Laplace estimate of the samples x1,…xNx_1,… x_N. Each index j∈[N+K]j∈[N+K] satisfies Pr[J=j]≤1N+K+12λ. [J=j]≤ 1N+K+ 12^λ. Summing over the 1+|i∈[N]:xi=σ|1+ \i ∈[N]:x_i= σ\ indices that output symbol σ, we obtain P~(σ)≤(1+N+K2λ)P^(σ)≤(1+2−log2N−1)P^(σ). P(σ)≤ (1+ N+K2^λ ) P(σ)≤(1+2^- ^2N-1) P(σ). Therefore, opening the definition of KL divergence, DKL(P~∥P^) D_KL( P\| P) =∑σ∈[K]P~(σ)log2P~(σ)P^(σ) = _σ∈[K] P(σ) _2 P(σ) P(σ) ≤∑σ∈[K]P~(σ)log2(1+2−log2N−1) ≤ _σ∈[K] P(σ) _2(1+2^- ^2N-1) ≤∑σ∈[K]P~(σ) 2−log2N ≤ _σ∈[K] P(σ)\,2^- ^2N =2−log2N, =2^- ^2N, where we used log2(1+t)≤tlog2e≤2t _2(1+t)≤ t _2e≤ 2t for any t>0t>0. ∎ If we naively sample the Laplace estimator N times, the resulting circuit complexity would blow-up by N, resulting in a complexity of O~(N(N+K)) O(N(N+K)). This complexity is primarily due to a table look-up, i.e. the above algorithm looks up one of K symbols in a table of size N+KN+K. However, it has long been known how to batch table look-ups to remove this overhead. We now recall the sorting-network bound used for this construction. A sorting network is a fixed sequence of compare-and-swap operations: each operation takes two binary integers and returns their minimum and maximum. The locations compared do not depend on the input values. Mazor and Pass [13, Lemma 10] recall a sorting-circuit bound of O(N⋅poly(logN,w))O(N·poly( N,w)) for N integers of w bits each. We use the following explicit bound from Batcher’s construction to keep track of the logarithmic factors. Theorem 2.14 (Sorting networks [2]). For every pair of integers N,w≥1N,w≥ 1, there is a sorting network with O(Nlog2(2N))O(N ^2(2N)) compare-and-swap operations that sorts any N w-bit integers in nondecreasing order. Each operation can be implemented using O(w)O(w) two-input Boolean gates. Consequently, there is a deterministic Boolean circuit N,w Sort_N,w of size O(Nwlog2(2N))O (Nw ^2(2N) ) that outputs a sorted permutation of its N inputs. The circuit construction is deterministic and depends only on N,wN,w. Corollary 2.15 (Batched table lookup). Let M,K,L≥1M,K,L≥ 1 be integers with 2≤K≤M2≤ K≤ M. There exists a Boolean circuit depending only on M,K,LM,K,L that, on binary-encoded inputs a=(a1,…,aM)∈[K]Ma=(a_1,…,a_M)∈[K]^M and (J1,…,JL)∈[M]L(J_1,…,J_L)∈[M]^L, outputs (aJ1,…,aJL)(a_J_1,…,a_J_L), using O((M+L)log3(2(M+L)))=O~(M+L)O((M+L) ^3(2(M+L)))= O(M+L) two-input gates. The circuit construction is deterministic. Proof. Set R=M+LR=M+L. A record is a tuple (d,τ,q,v)(d,τ,q,v) whose coordinates are a table address d, a type bit τ (00 for a table entry, 11 for a query), a query index q, and a value v. Unused coordinates are set to zero. Form the R records (j,0,0,aj)(j∈[M]),(Jq,1,q,0)(q∈[L]).(j,0,0,a_j) (j∈[M]), (J_q,1,q,0) (q∈[L]). For h=⌈log(R+1)⌉h= (R+1) , represent (d,τ,q,v)(d,τ,q,v) by the 4h4h-bit integer d 23h+τ 22h+q 2h+v.d\,2^3h+τ\,2^2h+q\,2^h+v. Since d,q,v≤R<2hd,q,v≤ R<2^h, numerical order on these encodings agrees with lexicographic order on the tuples, and 4h=O(log(2R))4h=O( (2R)). Apply Theorem 2.14 to sort these records lexicographically. Thus, for each q∈[L]q∈[L], the query record (Jq,1,q,0)(J_q,1,q,0) occurs after (Jq,0,0,aJq)(J_q,0,0,a_J_q), with no other table, i.e. type bit 00, between them. Write the sorted records as (dr,τr,qr,vr)r=1R(d_r, _r,q_r,v_r)_r=1^R, and compute c0=0,cr=vr,τr=0,cr−1,τr=1.c_0=0, c_r= casesv_r,& _r=0,\\ c_r-1,& _r=1. cases For a query record with qr=q_r=q, we have cr=aJqc_r=a_J_q. This computation uses O(RlogK)O(R K) gates. Finally, sort the triples (1−τr,qr,cr)(1- _r,q_r,c_r) lexicographically, using the integer encodings (1−τr)22h+qr2h+cr(1- _r)2^2h+q_r2^h+c_r. The first L triples correspond to queries in increasing order of q, so their third coordinates give (aJ1,…,aJL)(a_J_1,…,a_J_L). Each of the two sorting networks uses O(Rlog3(2R))O(R ^3(2R)) gates, giving the claimed size bound. All operations are fixed by M,K,LM,K,L, so the circuit construction is deterministic. ∎ Corollary 2.16 (Batched sampling from a Laplace estimate). Let N,K,λ≥1N,K,λ≥ 1. There exists a Boolean circuit depending only on N,K,λN,K,λ, with O~(λ(N+K)) O(λ(N+K)) two-input gates, that takes binary-encoded samples x1,…,xN∈[K]x_1,…,x_N∈[K] as inputs and uses NλNλ independent uniform random bits. For every fixed input, its N outputs are independent with a common distribution P~ P satisfying DKL(P~⊗N∥P^⊗N)≤2N(N+K) 2−λ.D_KL\! ( P N\, \|\, P N )≤ 2N(N+K)\,2^-λ. Here, P P is the Laplace estimate of the input samples, and O~ O hides polylogarithmic factors in N and K. Proof. For K=1K=1, output N copies of the sole symbol. Henceforth assume K≥2K≥ 2. Write T=N+KT=N+K, and form the table a=(1,…,K,x1,…,xN)∈[K]Ta=(1,…,K,x_1,…,x_N)∈[K]^T. For each i∈[N]i∈[N], use a separate block of λ random bits to generate UiU_i uniformly in 0,…,2λ−1\0,…,2^λ-1\, and compute Ji=1+⌊TUi2λ⌋J_i=1+ TU_i2^λ . Computing all indices requires O(Nλlog(2T))O(Nλ (2T)) two-input gates. By Corollary 2.15, computing (aJ1,…,aJN)(a_J_1,…,a_J_N) requires O(Tlog3(2T))O(T ^3(2T)) additional gates. The total size is therefore O~(λT) O(λ T). For every fixed input, the outputs are independent, since each equals aJia_J_i and the indices are independent. Moreover, for every j∈[T]j∈[T], Pr[Ji=j]≤1T+2−λ [J_i=j]≤ 1T+2^-λ. Summing over the table positions containing σ gives P~(σ)≤(1+T2−λ)P^(σ) P(σ)≤(1+T2^-λ) P(σ). Consequently, DKL(P~⊗N∥P^⊗N) D_KL\! ( P N\, \|\, P N ) =NDKL(P~∥P^) =ND_KL( P\| P) ≤Nlog2(1+T2−λ) ≤ N _2(1+T2^-λ) ≤2NT 2−λ, ≤ 2NT\,2^-λ, using the fact that log2(1+t)≤2t _2(1+t)≤ 2t for t>0t>0. ∎ The same construction allows an input bit for each sample to specify whether it is used. We record this extension with the KL bound needed below. Corollary 2.17 (Batched Laplace sampling from selected samples). Let N,K,λ≥1N,K,λ≥ 1, T=N+KT=N+K, and η=T2−λ<1η=T2^-λ<1. There is a Boolean circuit depending only on N,K,λN,K,λ, of size O(Tlog3(2T)+Nλlog(2T))=O~(λT),O (T ^3(2T)+Nλ (2T) )= O(λ T), that takes binary-encoded samples x1,…,xN∈[K]x_1,…,x_N∈[K] and selection bits b1,…,bN∈0,1b_1,…,b_N∈\0,1\ as inputs, where bt=1b_t=1 means that xtx_t is included in the estimate. Set H=∑t=1NbtH= _t=1^Nb_t, and let P P be the Laplace estimate of the selected samples: P^(σ)=1+∑t=1Nbt[xt=σ]H+K(σ∈[K]). P(σ)= 1+ _t=1^Nb_t1[x_t=σ]H+K (σ∈[K]). Thus P P is uniform when H=0H=0. Using NλNλ independent uniform random bits, the Boolean circuit outputs N symbols that, conditional on these inputs, are independent with a common distribution P~ P. This distribution depends only on the selected samples, in their original order. Then, for every distribution Q over [K][K], D(Q∥P~)≤D(Q∥P^)+log211−η.D_ KL (Q~\|~ P )≤ D_ KL (Q~\|~ P )+ _2 11-η. The circuit construction is deterministic, and O~ O hides polylogarithmic factors in N and K. Proof. The case K=1K=1 is immediate. Assume K≥2K≥ 2 and compute H=∑t=1NbtH= _t=1^Nb_t. For h=⌈log(2T)⌉h= (2T) , represent each triple (1−bt,t−1,xt−1)(1-b_t,t-1,x_t-1) by the (2h+1)(2h+1)-bit integer (1−bt)22h+(t−1)2h+(xt−1),(1-b_t)2^2h+(t-1)2^h+(x_t-1), and sort these integers. This sorts the triples lexicographically. The first coordinate places the selected samples first. The second coordinate preserves their original order, and the third coordinate is the sample encoded as xt−1x_t-1. Let y1,…,yNy_1,…,y_N be the corresponding samples in sorted order. Then y1,…,yHy_1,…,y_H are exactly the selected samples, in their original order. By Theorem 2.14, sorting costs O(Nlog2(2N)log(2T))O(N ^2(2N) (2T)) gates; computing H costs O(Nlog(2N))O(N (2N)) gates. Use the construction of Corollary 2.16 with the table a=(1,…,K,y1,…,yN)a=(1,…,K,y_1,…,y_N), but compute Ji=1+⌊(H+K)Ui2λ⌋(i∈[N]).J_i=1+ (H+K)U_i2^λ (i∈[N]). Here the UiU_i are independent and uniform in 0,…,2λ−1\0,…,2^λ-1\. The indices lie in [H+K][H+K], so the lookups are restricted to (1,…,K,y1,…,yH)(1,…,K,y_1,…,y_H); this also handles H=0H=0. Computing the indices costs O(Nλlog(2T))O(Nλ (2T)) gates, and the lookups cost O(Tlog3(2T))O(T ^3(2T)) gates. The sorting and counting costs are absorbed in this bound. The outputs remain independent conditional on the inputs, and their common distribution depends only on the selected samples in their original order. For every j∈[H+K]j∈[H+K], the lower rounding bound gives Pr[Ji=j]≥1H+K−2−λ≥1−ηH+K. [J_i=j]≥ 1H+K-2^-λ≥ 1-ηH+K. Summing over the positions containing σ gives P~(σ)≥(1−η)P^(σ) P(σ)≥(1-η) P(σ). For η<1η<1, D(Q∥P~)=D(Q∥P^)+∑σ∈[K]Q(σ)log2P^(σ)P~(σ)≤D(Q∥P^)+log211−η.D_ KL (Q~\|~ P )=D_ KL (Q~\|~ P )+ _σ∈[K]Q(σ) _2 P(σ) P(σ)≤ D_ KL (Q~\|~ P )+ _2 11-η. ∎ 2.3 One-Way Functions We use the length-preserving form of one-way functions, with security against nonuniform circuits. Definition 2.18 (One-way functions against circuits). Let f=(fλ)λ≥1f=(f_λ)_λ≥ 1 be a function family with fλ:0,1λ→0,1λf_λ:\0,1\^λ→\0,1\^λ, where fλ(x)f_λ(x) is computable from (1λ,x)(1^λ,x) in deterministic polynomial time. For functions T:ℕ→[1,∞)T:N→[1,∞) and ε:ℕ→[0,1] :N→[0,1], we say that f is (T,ε)(T, )-one-way against circuits if, for all sufficiently large λ, every randomized circuit AλA_λ of size at most T(λ)T(λ) satisfies PrX←Uλ,R[Aλ(fλ(X);R)∈fλ−1(fλ(X))]≤ε(λ). _X← U_λ,R [A_λ(f_λ(X);R)∈ f_λ^-1(f_λ(X)) ]≤ (λ). Here R denotes independent uniform random coins for AλA_λ. The circuit may depend arbitrarily on λ, and success means finding any preimage; an output ⊥ counts as failure. We call f a one-way function against polynomial-size circuits if it is (λc,λ−c)(λ^c,λ^-c)-one-way for every constant c>0c>0. For a size bound T, we call f T-secure if it is (T,1/T)(T,1/T)-one-way. Proposition 7.1 uses one-wayness against polynomial-size circuits. Theorem 7.2 assumes the stronger subexponential security T(λ)=2γλαT(λ)=2^γλ^α for constants γ>0γ>0 and 1/2<α<11/2<α<1. 2.4 Pseudoentropy Definition 2.19 (Pseudoentropy, nonuniform setting [16]). Let X be a random variable over a finite set. We say that X has (T,ε)(T, ) nonuniform pseudoentropy at least k if there exists a random variable Y over the same set with 1. H(Y)≥kH(Y)≥ k and 2. X and Y are (T,ε)(T, ) nonuniformly indistinguishable. Here indistinguishability means that every Boolean circuit of size at most T has distinguishing advantage at most ε in absolute value. If X=X(n)X=X(n), we say that X has nonuniform pseudoentropy at least k=k(n)k=k(n) if, for every constant c>0c>0, it has (nc,n−c)(n^c,n^-c) nonuniform pseudoentropy at least k(n)−n−ck(n)-n^-c for all sufficiently large n. Definition 2.20 (Conditional pseudoentropy, nonuniform setting [16]). Let (X,B)(X,B) take values in the finite set ×ℬX×B. We say that B has (T,ε)(T, ) conditional pseudoentropy at least k given X if there exists a random variable Z over ℬB, jointly distributed with X, such that 1. H(Z∣X)≥kH(Z X)≥ k and 2. (X,B)(X,B) and (X,Z)(X,Z) are (T,ε)(T, ) nonuniformly indistinguishable. The conditional pseudoentropy is the supremum of such k. The (T,ε)(T, ) conditional pseudoentropy gap of B given X is this supremum minus H(B∣X)H(B X). The asymptotic definition uses the same quantifiers and entropy slack as Definition 2.19. The maximum exists: the conditional distributions of Z form a compact set, the indistinguishability constraints are closed, and conditional entropy is continuous. Taking Z=BZ=B shows that the gap is nonnegative. Definition 2.21 (Next-block pseudoentropy [16, Definition 2.12]). Let n,ℓ≥1n, ≥ 1, let Y=(Y1,…,Yn)Y=(Y_1,…,Y_n) take values in (0,1ℓ)n(\0,1\ )^n, and let I be uniform on [n][n], independently of Y. We say that Y has (t,ϵ)(t,ε) next-block pseudoentropy at least k if there exists a random variable Z over 0,1ℓ\0,1\ , jointly distributed with (I,Y)(I,Y), such that 1. H(Z∣Y<I)≥k/nH(Z Y_<I)≥ k/n and 2. (Y<I,YI)(Y_<I,Y_I) and (Y<I,Z)(Y_<I,Z) are (t,ϵ)(t,ε) nonuniformly indistinguishable. For ℓ=1 =1, we also call this next-bit pseudoentropy. For families indexed by n, next-block pseudoentropy at least k(n)k(n) means that, for every c>0c>0 and all sufficiently large n, the (nc,n−c)(n^c,n^-c) next-block pseudoentropy is at least k(n)−n−ck(n)-n^-c. This is the nonuniform asymptotic convention; polynomial rescaling absorbs the number of blocks when comparing it with the conditional definition. Definition 2.22 (KL-hardness for conditional sampling [16]). Let (X,B)(X,B) take values in 0,1m×[q]\0,1\^m×[q]. We say that B is (t,δ)(t,δ) KL-hard to sample given X if every randomized circuit S:0,1m→[q]S:\0,1\^m→[q] of size at most t satisfies D((X,B)∥(X,S(X)))>δD_ KL ((X,B)~\|~(X,S(X)) )>δ. We use the following two consequences of the Vadhan–Zheng characterization, stated directly in terms of conditional samplers. In the first part, the distinguishing error ϵε and the additive KL-divergence loss η are separate parameters. Theorem 2.23 (Characterizing conditional pseudoentropy, nonuniform setting). There exist a universal constant c1∈(0,1]c_1∈(0,1] and a polynomial p0p_0 with nonnegative coefficients and constant term at least one such that the following holds. Let (X,B)(X,B) take values in 0,1m×[q]\0,1\^m×[q], with m≥0m≥ 0 and q≥2q≥ 2, and let t≥1t≥ 1, δ,g≥0δ,g≥ 0, and 0<ϵ,η,σ<10<ε,η,σ<1. 1. If B has (t,ϵ)(t,ε) conditional pseudoentropy gap at least δ given X, then every randomized circuit S:0,1m→[q]S:\0,1\^m→[q] of size at most mintc1,σ/ϵp0(m,q,1/η,log(1/σ)) \t^c_1,\,σ/ε\p_0(m,q,1/η, (1/σ)) satisfies D((X,B)∥(X,S(X)))>δ−σ−ηD_ KL ((X,B)~\|~(X,S(X)) )>δ-σ-η. 2. If the (t,η)(t,η) conditional pseudoentropy gap of B given X is at most g, then there exists a randomized circuit S:0,1m→[q]S:\0,1\^m→[q] of size at most p0(t,m,q,1/η)p_0(t,m,q,1/η) such that D((X,B)∥(X,S(X)))≤g+2η.D_ KL ((X,B)~\|~(X,S(X)) )≤ g+2η. Proof. The first part combines [16, Theorem 3.8 and Lemma 3.6], with respective KL-divergence losses σ and η. Choosing c1c_1 sufficiently small and p0p_0 sufficiently large gives the stated circuit sizes. For m=0m=0, add a fixed conditioning bit; for δ=0δ=0, the first part follows from nonnegativity of KL-divergence. For the second part, suppose that every sampler of size at most p0(t,m,q,1/η)p_0(t,m,q,1/η) has KL-divergence greater than g+2ηg+2η. For sufficiently large p0p_0, the same results give a (t,η)(t,η) conditional pseudoentropy gap at least g+ηg+η, contradicting its upper bound g. One polynomial p0p_0 can be chosen large enough for both parts, absorbing constant shifts of its arguments. ∎ The running time of the resulting sampler is polynomial in the inverse accuracy. Consequently, the finite-parameter statement supplies a family of polynomial-size samplers for inverse-polynomial accuracies. 3 Sequential Sampling Algorithms Definition 3.1 ((ℓ,s,B)( ,s,B)-Sequential Sampling Algorithm). We define a sequential sampling algorithm of size B to be a sequence of randomized boolean circuits C(1n)=(C1,C2,…,Cn)C(1^n)=(C_1,C_2,…,C_n) for an output length n∈ℕn such that all circuits CiC_i are of size at most B. We use C(1n)C(1^n) to denote the distribution of (x1,…,xn)(x_1,…,x_n) sampled iteratively as follows: for i=1i=1, sample (x1,1)←C1(1n)(x_1, st_1)← C_1(1^n) and for i>1i>1 sample (xi,i)←Ci(1n,i−1,x1,…,xi−1)(x_i, st_i)← C_i(1^n, st_i-1,x_1,…,x_i-1). We use ℓ and s to denote the lengths of the xix_i’s and i st_i’s respectively. All invocations use fresh independent random coins. The input 1n1^n is fixed for each circuit family and is suppressed when convenient. Remark 3.2. When s=0s=0, we refer to an (ℓ,0,B)( ,0,B)-sequential sampler simply as a stateless (ℓ,B)( ,B)-sequential sampler. 3.1 Characterization of Sequential Sampling We apply Theorem 2.23 with the visible prefix as the conditioning variable and the next block as the variable to be sampled. Choosing the block uniformly gives a characterization of stateless sequential sampling. The dependence on the alphabet size 2ℓ2 is polynomial, contributing a polynomial factor in n when ℓ=O(logn) =O( n). Theorem 3.3 (Characterization of stateless sequential sampling). There exist a universal constant c0∈(0,1]c_0∈(0,1] and a polynomial p with nonnegative coefficients and constant term at least one such that the following holds. Let n,ℓ≥1n, ≥ 1, let Y=(Y1,…,Yn)Y=(Y_1,…,Y_n) take values in (0,1ℓ)n(\0,1\ )^n, and let t≥1t≥ 1, δ≥0δ≥ 0, and 0<ϵ,η,σ<10<ε,η,σ<1. 1. If Y has (t,ϵ)(t,ε) next-block pseudoentropy at least H(Y)+δH(Y)+δ, then, for every B≥1B≥ 1 satisfying B≤mintc0,σ/(nϵ)p(n,2ℓ,1/η,log(n/σ)),B≤ \t^c_0,\,σ/(nε)\p(n,2 ,1/η, (n/σ)), every stateless (ℓ,B)( ,B)-sequential sampler C satisfies D(Y∥C(1n))>δ−σ−nηD_ KL (Y~\|~C(1^n) )>δ-σ-nη. 2. If δ≥ϵδ≥ε and the (t,ϵ)(t,ε) next-block pseudoentropy of Y is at most H(Y)+δ−ϵH(Y)+δ-ε, then there exists a stateless (ℓ,B)( ,B)-sequential sampler C with B≤p(t,n,2ℓ,1/ϵ),D(Y∥C(1n))≤δ.B≤ p(t,n,2 ,1/ε), D_ KL (Y~\|~C(1^n) )≤δ. We prove the two directions separately. Throughout, I is uniform on [n][n] and independent of Y, and X=(I,Y<I)X=(I,Y_<I). Write m=O(nℓ)m=O(n ) for the input length of X and q=2ℓq=2 for the alphabet size. Lemma 3.4 (Next-block pseudoentropy implies conditional sampling hardness). Under the hypotheses and size condition of the first part of Theorem 3.3, every stateless (ℓ,B)( ,B)-sequential sampler C satisfies i←[n]D((Y<i,Yi)∥(Y<i,Ci(Y<i)))>δ−σn−η. _i←[n]D_ KL ((Y_<i,Y_i)~\|~(Y_<i,C_i(Y_<i)) )> δ-σn-η. Proof. By Definition 2.21, there is a random variable Z jointly distributed with (I,Y)(I,Y) such that (X,Z)(X,Z) and (X,YI)(X,Y_I) are (t,ϵ)(t,ε)-indistinguishable and H(Z∣Y<I)=1n∑i=1nH(Z∣Y<i,I=i)≥H(Y)+δn.H(Z Y_<I)= 1n _i=1^nH(Z Y_<i,I=i)≥ H(Y)+δn. Here Y<IY_<I determines I. Since H(YI∣X)=H(Y)/nH(Y_I X)=H(Y)/n, the (t,ϵ)(t,ε) conditional pseudoentropy gap of YIY_I given X is at least δ/nδ/n. This is an average over the index and does not give the same gap for each fixed i. Fix a stateless sampler C. To apply Theorem 2.23, we therefore need a sampler that, given (I,Y<I)(I,Y_<I), samples exactly CI(Y<I)C_I(Y_<I). The loss η in that theorem comes from approximating a sampler’s output probabilities to obtain the predictor used in its proof. We now construct this sampler, which we call S. It contains one copy of each CjC_j and, on input (i,y<i)(i,y_<i), selects CiC_i to produce the output Ci(y<i)C_i(y_<i). The size increases, but remains sufficiently small for the first part of Theorem 2.23 to apply. Namely, we implement this selection by ANDing each output bit of CjC_j with the comparison i=ji=j, and then ORing these bits over j∈[n]j∈[n]. This sets every unselected output to zero, leaving only the output of CiC_i. Each CjC_j contributes at most B gates, with O(nℓ)O(n ) more for its index comparison and output masking, giving B+O(nℓ)B+O(n ) gates per copy. With n copies and O(nℓ)O(n ) gates for the final ORs, the size of S is O(n(B+nℓ))=O(n2qB)O(n(B+n ))=O(n^2qB). Take c0=c1c_0=c_1. Since m=O(nq)m=O(nq) and p0p_0 has nonnegative coefficients, choose the fixed polynomial p sufficiently large to absorb the O(n2q)O(n^2q) overhead and the dependence of p0p_0 on m. The assumed bound on B then makes the size of S at most mintc1,σ/(nϵ)p0(m,q,1/η,log(n/σ)). \t^c_1,\,σ/(nε)\p_0(m,q,1/η, (n/σ)). Therefore, the first part of Theorem 2.23, with gap δ/nδ/n, loss σ/nσ/n, and the same t, ϵε, and η, gives D((X,YI)∥(X,S(X))) D_ KL ((X,Y_I)~\|~(X,S(X)) ) =1n∑i=1nD((Y<i,Yi)∥(Y<i,Ci(Y<i))) = 1n _i=1^nD_ KL ((Y_<i,Y_i)~\|~(Y_<i,C_i(Y_<i)) ) (3) >δ−σn−η. > δ-σn-η. The equality conditions on the common uniform index I. ∎ Lemma 3.5 (Small next-block pseudoentropy gap gives samplers). Under the hypotheses of the second part of Theorem 3.3, there is a stateless (ℓ,B)( ,B)-sequential sampler C, with B≤p(t,n,2ℓ,1/ϵ)B≤ p(t,n,2 ,1/ε), such that i←[n]D((Y<i,Yi)∥(Y<i,Ci(Y<i)))≤δn. _i←[n]D_ KL ((Y_<i,Y_i)~\|~(Y_<i,C_i(Y_<i)) )≤ δn. Proof. By assumption, the (t,ϵ)(t,ε) next-block pseudoentropy of Y is at most H(Y)+δ−ϵH(Y)+δ-ε. We use this bound in the second part of Theorem 2.23 to obtain a sampler S that receives (i,y<i)(i,y_<i) and samples YIY_I given X up to KL-divergence δ/nδ/n. Fixing its index input to i gives the circuit CiC_i: on input y<iy_<i, it outputs S(i,y<i)S(i,y_<i). By Definition 2.21 and H(YI∣X)=H(Y)/nH(Y_I X)=H(Y)/n, the (t,ϵ)(t,ε) conditional pseudoentropy gap of YIY_I given X is at most (δ−ϵ)/n(δ-ε)/n. The target KL-divergence δ/nδ/n leaves ϵ/nε/n for the theorem’s additive loss 2η2η. We therefore set η′=ϵ/(2n)η =ε/(2n). Since η′≤ϵη ≤ε, every distribution satisfying (t,η′)(t,η )-indistinguishability also satisfies (t,ϵ)(t,ε)-indistinguishability, so the same upper bound on the gap holds at error η′η . Since δ≥ϵδ≥ε and 0<η′<10<η <1, we can therefore apply that theorem with g=(δ−ϵ)/ng=(δ-ε)/n and η′η in place of η. It gives a randomized circuit S of size at most p0(t,m,q,2n/ϵ)p_0(t,m,q,2n/ε) such that D((X,YI)∥(X,S(X)))≤δ−ϵn+2η′=δn.D_ KL ((X,Y_I)~\|~(X,S(X)) )≤ δ-εn+2η = δn. For each i∈[n]i∈[n], define Ci(y<i)=S(i,y<i)C_i(y_<i)=S(i,y_<i) by hardwiring the index input to i. This does not increase the circuit size. Using fresh independent coins at every step, the circuits CiC_i form a stateless sequential sampler. Since m=O(nq)m=O(nq), their size is bounded by a fixed polynomial in t,n,q,1/ϵt,n,q,1/ε. Enlarge the polynomial p from the preceding lemma to dominate this bound, retaining nonnegative coefficients and constant term at least one. This is compatible with that lemma because enlarging p only strengthens its size hypothesis. Thus B≤p(t,n,2ℓ,1/ϵ)B≤ p(t,n,2 ,1/ε). Finally, the two distributions in the KL-divergence have the same uniform index I. Conditioning on this index gives i←[n]D((Y<i,Yi)∥(Y<i,Ci(Y<i)))=D((X,YI)∥(X,S(X)))≤δn. _i←[n]D_ KL ((Y_<i,Y_i)~\|~(Y_<i,C_i(Y_<i)) )=D_ KL ((X,Y_I)~\|~(X,S(X)) )≤ δn. ∎ Proof of Theorem 3.3. Since the sampler is stateless and uses fresh coins at each step, Pr[C(1n)=y]=∏iPr[Ci(y<i)=yi] [C(1^n)=y]= _i [C_i(y_<i)=y_i]. Together with the analogous factorization of Pr[Y=y] [Y=y], this gives D(Y∥C(1n)) D_ KL (Y~\|~C(1^n) ) =∑i=1nD((Y<i,Yi)∥(Y<i,Ci(Y<i))) = _i=1^nD_ KL ((Y_<i,Y_i)~\|~(Y_<i,C_i(Y_<i)) ) =ni←[n]D((Y<i,Yi)∥(Y<i,Ci(Y<i))). =n _i←[n]D_ KL ((Y_<i,Y_i)~\|~(Y_<i,C_i(Y_<i)) ). Indeed, when the divergence is finite, its definition gives D(Y∥C(1n))=∑y∈(Y)Pr[Y=y]∑i=1nlogPr[Yi=yi∣Y<i=y<i]Pr[Ci(y<i)=yi].D_ KL (Y~\|~C(1^n) )= _y∈ supp(Y) [Y=y] _i=1^n [Y_i=y_i Y_<i=y_<i] [C_i(y_<i)=y_i]. For each i, marginalizing over y>iy_>i identifies its contribution as D((Y<i,Yi)∥(Y<i,Ci(Y<i)))D_ KL ((Y_<i,Y_i)~\|~(Y_<i,C_i(Y_<i)) ). If some y∈(Y)y∈ supp(Y) has zero probability under C, at least one of its next-block probabilities is zero; the corresponding summand and the total KL-divergence are both infinite. The first conclusion now follows from Lemma 3.4, and the second from Lemma 3.5. ∎ 4 Stateful Sequential Sampling Private state lets a sampler retain information that its visible output has not revealed. We show how to recover the next-token distribution from the prefix alone, at a cost essentially linear in the number of possible states. The simulation estimates the distribution of the hidden state conditioned on the visible prefix. 4.1 Sequential Samplers with State Let X denote the output alphabet of a block, so that ||=2ℓ =2 , and let =0,1kS=\0,1\^k denote the state space. Definition 4.1 (Sequential sampler with k bits of state). A sequential sampler with k bits of state and size B for n blocks over alphabet X is a sequence C=(C1,…,Cn)C=(C_1,…,C_n) of randomized circuits, each of size at most B, with state space =0,1kS=\0,1\^k. The variables (X1,S1),…,(Xn,Sn)(X_1,S_1),…,(X_n,S_n) are generated using independent random coins for each circuit: (X1,S1)←C1(1n),(X_1,S_1)← C_1(1^n), and for i≥2i≥ 2, (Xi,Si)←Ci(1n,X<i,Si−1).(X_i,S_i)← C_i(1^n,X_<i,S_i-1). The sampler C outputs X=(X1,…,Xn)X=(X_1,…,X_n); the states S1,…,SnS_1,…,S_n are not part of its output. To simulate CiC_i for i≥2i≥ 2 on a prefix x<ix_<i such that Pr[X<i=x<i]>0 [X_<i=x_<i]>0, it suffices to sample Si−1S_i-1 conditioned on X<i=x<iX_<i=x_<i, and then run Ci(1n,x<i,Si−1)C_i(1^n,x_<i,S_i-1). The following lemma justifies using only this state distribution, without reconstructing the preceding private states. Lemma 4.2 (Markov chain of sequential sampling states). Let (X1,S1),…,(Xn,Sn)(X_1,S_1),…,(X_n,S_n) be generated by a sequential sampler with private state. For i∈[n]i∈[n], define Ai≔(X≤i,Si)A_i (X_≤ i,S_i). Then A1−A2−⋯−AnA_1-A_2-·s-A_n is a Markov chain. Proof. Fix i∈2,…,ni∈\2,…,n\ and a1,…,ai−1a_1,…,a_i-1 such that Pr[A1=a1,…,Ai−1=ai−1]>0 [A_1=a_1,…,A_i-1=a_i-1]>0. Write ai−1=(x<i,si−1)a_i-1=(x_<i,s_i-1). For every xi∈x_i and si∈s_i , put ai=(x≤i,si)a_i=(x_≤ i,s_i). Since CiC_i uses fresh random coins, Pr[Ai=ai∣A1=a1,…,Ai−1=ai−1] [A_i=a_i A_1=a_1,…,A_i-1=a_i-1] =Pr[Ci(1n,x<i,si−1)=(xi,si)] = [C_i(1^n,x_<i,s_i-1)=(x_i,s_i)] =Pr[Ai=ai∣Ai−1=ai−1]. = [A_i=a_i A_i-1=a_i-1]. If the prefix in aia_i does not extend x<ix_<i, both conditional probabilities are zero. This proves the Markov property. ∎ 4.2 Sampling from an Empirical Distribution Before constructing a stateless sampler from a stateful one, we give a sampling circuit that reduces the circuit-size overhead. In the construction below, we run CiC_i m times to estimate the distribution of states supplied to Ci+1C_i+1. We use the Laplace estimate (Definition 2.10) to give every state positive probability and keep the KL error finite. Once these samples have been obtained, a direct implementation on a domain [K]=1,…,K[K]=\1,…,K\ uses O~(m) O(m) gates per sample, where the tilde hides polylogarithmic factors in m and K. Producing m independent samples separately therefore costs O~(m2) O(m^2) gates. By batching the table lookups for these draws, we reduce this cost to O~(m) O(m). Corollary 2.17 gives the circuit and bounds its additional KL error. We use it below with N=m≥KN=m≥ K, so its size is O~(m) O(m) when λ=O(log(m+K))λ=O( (m+K)). Theorem 4.3 (State elimination for sequential samplers (small KL)). Let n≥1n≥ 1 and k,ℓ≥0k, ≥ 0 be integers, and let 0<δ≤10<δ≤ 1. Let C=(C1,…,Cn)C=(C_1,…,C_n) be a sequential sampler with k bits of private state and size at most B per circuit, over alphabet =0,1ℓX=\0,1\ , and let =0,1kS=\0,1\^k. There is a stateless sequential sampler D=(D1,…,Dn)D=(D_1,…,D_n) such that D(C(1n)∥D(1n))≤δD_ KL (C(1^n)~\|~D(1^n) )≤δ and every DiD_i has Boolean circuit size at most O(n3||||δ[B+log3(n||||δ)]).O ( n^3|X||S|δ [B+ ^3\! ( n|X||S|δ ) ] ). The circuit construction is deterministic; all sampling and estimation randomness is internal to the circuits. The dependence on the number of states is linear up to logarithmic factors. The analysis estimates the joint distribution of a token and state before conditioning on the observed token. Applying the KL chain rule to its Laplace estimate bounds the average error after conditioning, even when some tokens are rare. At step j, the simulation estimates the joint distribution of (Xj,Sj)(X_j,S_j) conditioned on X<j=x<jX_<j=x_<j, using a fixed number of samples. Conditioning this estimate on its first component being xjx_j gives an estimate of the distribution of SjS_j conditioned on X≤j=x≤jX_≤ j=x_≤ j. The KL chain rule bounds the expected KL error of this state estimate, for xj∼Xj|X<j=x<jx_j X_j X_<j=x_<j, by the KL error of the joint estimate. Proof. Write X=C(1n)X=C(1^n). Let D1D_1 run C1(1n)C_1(1^n) and return the first component of its output. Thus D1(1n)≡X1D_1(1^n)≡ X_1, proving the case n=1n=1. Assume n≥2n≥ 2 and set m=⌈4n2||||δ⌉.m= 4n^2|X||S|δ . We use the circuit Sample from Corollary 2.17 with N=m,K=||,λ=⌈log(2m(m+||))⌉,N=m, K=|S|, λ= (2m(m+|S|) ) , identifying [||][|S|] with S. For a list L of at most m states, (L) Sample(L) receives states v1,…,vm∈v_1,…,v_m and selection bits b1,…,bmb_1,…,b_m such that L=(vt:bt=1)L=(v_t:b_t=1), in increasing order of t. Write π^L π^L for its Laplace estimate and π~L π^L for the common distribution of the m independent outputs. Since η=(m+||)2−λ≤1/(2m)η=(m+|S|)2^-λ≤ 1/(2m), the corollary gives, for every distribution P over S, D(P∥π~L)≤D(P∥π^L)+1m,D_ KL (P~\|~ π^L )≤ D_ KL (P~\|~ π^L )+ 1m, (4) where log(1/(1−1/(2m)))≤1/m (1/(1-1/(2m)))≤ 1/m follows from (1−1/(2m))m≥1/2(1-1/(2m))^m≥ 1/2. In the algorithm below, a list LjL_j formed from sampled pairs (Zt,Tt)t=1m(Z_t,T_t)_t=1^m is represented by the states (Tt)t=1m(T_t)_t=1^m and selection bits ([Zt=xj])t=1m(1[Z_t=x_j])_t=1^m. Each list preserves repetitions and sample order, and may be empty. All lists are computed inside DiD_i; no state is passed between the circuits D1,…,DnD_1,…,D_n. For i≥2i≥ 2, the circuit Di(1n,x<i)D_i(1^n,x_<i) runs the following algorithm, using fresh independent random bits in every call: 1. Draw m pairs from C1(1n)C_1(1^n). Form a list L1L_1 of states, consisting of the second components of those symbol-state pairs whose first component equals x1x_1. 2. For j=2,…,i−1j=2,…,i-1, run (Lj−1) Sample(L_j-1) to obtain m states s1,…,sms_1,…,s_m. For each t∈[m]t∈[m], run Cj(1n,x<j,st)C_j(1^n,x_<j,s_t). Form a list LjL_j from the second components of those symbol-state pairs whose first component equals xjx_j. 3. Run (Li−1) Sample(L_i-1), take its first output s, and return the first component of Ci(1n,x<i,s)C_i(1^n,x_<i,s). For Pr[X≤j=x≤j]>0 [X_≤ j=x_≤ j]>0, let πjx≤j(s)=Pr[Sj=s∣X≤j=x≤j] _j^x_≤ j(s)= [S_j=s X_≤ j=x_≤ j] denote the true state posterior distribution. In the following, [⋅]1[·]_1 denotes the first output component. Let εj=x≤j∼X≤jLj|x≤jD(πjx≤j∥π~Lj), _j= _x_≤ j X_≤ j _L_j x_≤ jD_ KL ( _j^x_≤ j~\|~ π^L_j ), where the expectation Lj|x≤j _L_j x_≤ j averages only over the algorithm’s random bits on input x≤jx_≤ j, independent of X. By the chain rule of KL (Fact 2.7), D(C(1n)∥D(1n)) D_ KL (C(1^n)~\|~D(1^n) ) =∑i=2nx<i∼X<iD(Xi∣X<i=x<i∥Di(1n,x<i)) = _i=2^n _x_<i X_<iD_ KL (X_i _X_<i=x_<i~\|~D_i(1^n,x_<i) ) ≤∑i=2nx<i∼X<iLi−1|x<iD(Xi∣X<i=x<i∥[Ci(1n,x<i,[(Li−1)]1)]1), ≤ _i=2^n _x_<i X_<i _L_i-1 x_<iD_ KL (X_i _X_<i=x_<i~\|~ [C_i(1^n,x_<i,[ Sample(L_i-1)]_1) ]_1 ), where the last inequality follows from the convexity of KL divergence, as DiD_i constructs Li−1L_i-1 using fresh randomness. Conditioned on X<i=x<iX_<i=x_<i, by Lemma 4.2, XiX_i is the first component of CiC_i when given as input the prefix x<ix_<i together with a state distributed according to πi−1x<iπ^x_<i_i-1. Thus, for any fixed list of states L, by DPI (fact 2.9), D(Xi∣X<i=x<i∥[Ci(1n,x<i,[(L)]1)]1)≤D(πi−1x<i∥π~L),D_ KL (X_i _X_<i=x_<i~\|~ [C_i(1^n,x_<i,[ Sample(L)]_1) ]_1 )≤ D_ KL ( _i-1^x_<i~\|~ π^L ), which together with the previous bound gives us D(C(1n)∥D(1n))≤∑j=1n−1εj.D_ KL (C(1^n)~\|~D(1^n) )≤ _j=1^n-1 _j. (5) For 2≤j≤n−12≤ j≤ n-1, fix x<jx_<j with Pr[X<j=x<j]>0 [X_<j=x_<j]>0 and a realization L of the computed list Lj−1L_j-1. Set Pj(x,s) P_j(x,s) =Pr[Xj=x,Sj=s∣X<j=x<j], = [X_j=x,S_j=s X_<j=x_<j], Qj(x,s) Q_j(x,s) =Pr[Cj(1n,x<j,[(L)]1)=(x,s)]. = [C_j(1^n,x_<j,[ Sample(L)]_1)=(x,s) ]. By Lemma 4.2, PjP_j and QjQ_j result from running Cj(1n,x<j,⋅)C_j(1^n,x_<j,·) on πj−1x<j _j-1^x_<j and π~L π^L, respectively. Thus, by DPI (Fact 2.9), D(Pj∥Qj)≤D(πj−1x<j∥π~L).D_ KL (P_j~\|~Q_j )≤ D_ KL ( _j-1^x_<j~\|~ π^L ). (6) Step 2 produces m i.i.d. pairs (Zt,Tt)t=1m(Z_t,T_t)_t=1^m from QjQ_j, and forms the next list of states Lj=(Tt:Zt=xj)L_j=(T_t:Z_t=x_j). Let Q^j Q_j denote the joint Laplace estimate from these pairs. That is, letting Nx,s=∑t=1m[(Zt,Tt)=(x,s)]N_x,s= _t=1^m1[(Z_t,T_t)=(x,s)], Q^j(x,s)=Nx,s+1m+||||. Q_j(x,s)= N_x,s+1m+|X||S|. The corresponding conditional Laplace estimate is exactly that of LjL_j: π^Lj(s)=Q^j(s∣xj)=Nxj,s+1Nxj+||,Nx=∑s∈Nx,s. π^L_j(s)= Q_j(s x_j)= N_x_j,s+1N_x_j+|S|, N_x= _s N_x,s. By (4), for every realization of LjL_j, D(πjx≤j∥π~Lj)≤D(πjx≤j∥Q^j(⋅∣xj))+1m.D_ KL ( _j^x_≤ j~\|~ π^L_j )≤ D_ KL ( _j^x_≤ j~\|~ Q_j(· x_j) )+ 1m. Conditional on X<j=x<jX_<j=x_<j and Lj−1=L_j-1=L, the sampled pairs are independent of XjX_j. Therefore, writing Pj,P_j,X for the token marginal of PjP_j, (Zt,Tt)t=1m∼Qj⊗mxj∼Pj,D(πjx≤j∥π~Lj) _(Z_t,T_t)_t=1^m Q_j m _x_j P_j,XD_ KL ( _j^x_≤ j~\|~ π^L_j ) ≤(Zt,Tt)t=1m∼Qj⊗mxj∼Pj,D(πjx≤j∥Q^j(⋅∣xj))+1m ≤ _(Z_t,T_t)_t=1^m Q_j m _x_j P_j,XD_ KL ( _j^x_≤ j~\|~ Q_j(· x_j) )+ 1m ≤D(Pj∥Qj)+(||||−1)logem+1+1m ≤ D_ KL (P_j~\|~Q_j )+ (|X||S|-1) em+1+ 1m ≤D(πj−1x<j∥π~L)+2||||m, ≤ D_ KL ( _j-1^x_<j~\|~ π^L )+ 2|X||S|m, where the second-last inequality follows from Lemma 2.12 and the last inequality from eq. 6 and loge<2 e<2. For j=1j=1, step 1 gives P1=Q1=C1(1n)P_1=Q_1=C_1(1^n), so the same calculation ends at 2||||/m2|X||S|/m. For j≥2j≥ 2, averaging over x<j∼X<jx_<j X_<j and the list Lj−1L_j-1 computed on that prefix gives ε1 _1 ≤2||||m, ≤ 2|X||S|m, εj _j ≤εj−1+2||||m ≤ _j-1+ 2|X||S|m (2≤j≤n−1), (2≤ j≤ n-1), εj _j ≤2j||||m ≤ 2j|X||S|m (1≤j≤n−1). (1≤ j≤ n-1). Therefore, by Equation 5, D(C(1n)∥D(1n)) D_ KL (C(1^n)~\|~D(1^n) ) ≤∑j=1n−1εj≤2||||m∑j=1n−1j ≤ _j=1^n-1 _j≤ 2|X||S|m _j=1^n-1j =n(n−1)||||m≤δ, = n(n-1)|X||S|m≤δ, as promised. Boolean circuit size. Since m≥||m≥|S| and λ=O(log(2m))λ=O( (2m)), Corollary 2.17 gives ||=O(mlog3(2m)).| Sample|=O(m ^3(2m)). Forming the input to (Lj) Sample(L_j) uses m copies of CjC_j, each of size at most B, and m comparisons with xjx_j, each costing O(ℓ)O( ) gates. The sorting and counting costs are included in ||| Sample|. There are i−1i-1 such lists, i−1i-1 calls to Sample, and one final call to CiC_i. Thus |Di| |D_i| =O(i⋅m⋅[B+ℓ+log3(2m)]) =O (i· m· [B+ + ^3(2m) ] ) =O(n3||||δ[B+log3(2n||||δ)]), =O ( n^3|X||S|δ [B+ ^3\! ( 2n|X||S|δ ) ] ), since i≤ni≤ n, m=O(n2||||/δ)m=O(n^2|X||S|/δ), and ℓ=log||=O(log(2m)) = |X|=O( (2m)). All calls and list representations have fixed size, so this construction gives a stateless randomized Boolean circuit. ∎ For polynomial-size alphabets and k=O(logn)k=O( n), the simulation has polynomial size at any specified inverse-polynomial KL accuracy. Thus every distribution generated efficiently with logarithmic private state can be approximated efficiently without it. Together with the known characterization by next-block pseudoentropy (Theorem 3.3), this extends sampling obstructions to logarithmic state; the cryptographic consequences below apply this connection. 4.3 Sample Complexity of Estimating the State Distribution The construction in Theorem 4.3 estimates the entire conditional state distribution before sampling a state from that estimate. We show that, when this distribution is unknown and the only access to it is through independent samples, expected KL divergence at most 1/41/4 requires Ω(||)=Ω(2k) ( )= (2^k) samples. This establishes the necessity of the linear dependence on || when estimating the state distribution from independent samples, but it does not by itself establish a matching circuit-size lower bound for Theorem 4.3. Proposition 4.4 (Sample lower bound for estimating the state distribution). Let k≥1k≥ 1 and N≥0N≥ 0 be integers, and let =0,1kS=\0,1\^k. Suppose that a randomized algorithm receives at most N independent samples from an unknown distribution P over S and outputs a vector of probabilities π π over S, with no subsequent access to the sampling oracle. The algorithm receives no other information about P. Then there is a distribution P for which [D(P∥π^)]≥1−2N||, [D_ KL (P~\|~ π ) ]≥ 1- 2N , where the expectation is over the samples and the algorithm’s internal randomness. Consequently, if [D(P∥π^)]≤1/4 [D_ KL (P~\|~ π )]≤ 1/4 for every P, then N≥3||/8=3⋅2k−3N≥ 3 /8=3· 2^k-3. Proof. We partition the states into pairs and choose one state from each pair using a hidden bit. Each sample reveals only the bit for its pair; every pair that is never sampled contributes to the expected KL error. Let m=2k−1m=2^k-1 and identify S with [m]×0,1[m]×\0,1\. For each θ=(θ1,…,θm)∈0,1mθ=( _1,…, _m)∈\0,1\^m, define Pθ(a,b)=1/m,b=θa,0,b≠θa.P_θ(a,b)= cases1/m,&b= _a,\\ 0,&b≠ _a. cases Choose Θ uniformly from 0,1m\0,1\^m. Conditional on Θ , a sample from PΘP_ is generated by choosing A uniformly from [m][m], independently of Θ , and returning (A,ΘA)(A, _A). We may generate N independent samples in advance and let the algorithm read as many as it requests, ignoring any unused samples. Let W consist of these N samples and the algorithm’s independent random coins. Fix W, so that the output π π is fixed, and let U⊆[m]U [m] contain the first coordinates absent from the samples. For each a∉Ua∉ U, the samples determine Θa _a; conditional on W, the bits (Θa)a∈U( _a)_a∈ U remain independent and uniform. Consequently, the distribution P¯=[PΘ∣W] P= [P_ W] satisfies P¯(a,b)=1/m,a∉U and b=Θa,0,a∉U and b≠Θa,1/(2m),a∈U. P(a,b)= cases1/m,&a∉ U and b= _a,\\ 0,&a∉ U and b≠ _a,\\ 1/(2m),&a∈ U. cases In particular, H(P¯)=m−|U|mlogm+|U|mlog(2m)=logm+|U|m,H(Pθ)=logm.H( P)= m-|U|m m+ |U|m (2m)= m+ |U|m, H(P_θ)= m. Expanding KL divergence gives [D(PΘ∥π^)∣W] [D_ KL (P_ ~\|~ π ) W ] =−logm−∑s∈P¯(s)logπ^(s) =- m- _s P(s) π(s) =D(P¯∥π^)+H(P¯)−logm≥|U|m. =D_ KL ( P~\|~ π )+H( P)- m≥ |U|m. At most N pairs appear among the samples, so |U|≥m−N|U|≥ m-N. Therefore [D(PΘ∥π^)]≥|U|m≥1−Nm=1−2N||. [D_ KL (P_ ~\|~ π ) ]≥ |U|m≥ 1- Nm=1- 2N|S|. Averaging over the uniform choice of Θ implies that some fixed θ satisfies the same lower bound, with expectation only over its samples and the algorithm’s coins. If this expectation is at most 1/41/4 for every PθP_θ, then 1−2N/||≤1/41-2N/|S|≤ 1/4, or N≥3||/8N≥ 3|S|/8. ∎ Every distribution PθP_θ used in the proof can occur as a conditional state distribution: the first circuit can output a fixed block x1x_1, choose A uniformly from [2k−1][2^k-1], and set S1=(A,θA)S_1=(A, _A). Then π1x1=Pθ _1^x_1=P_θ. Thus the lower bound applies even when independent samples from π1x1=Pθ _1^x_1=P_θ are supplied directly. The first circuit may encode θ in its description; the proposition assumes access only to samples, rather than to that description. 5 Insertional Sampling and Insertional Pseudoentropy An insertional sampler chooses both the next token and where to place it. This abstracts the insertion framework of Stern et al. [15], with one sampled insertion per step. The current string is the only information retained between steps; each circuit uses fresh independent coins. Definition 5.1 (Stateless Insertional Sampler). Let n,ℓ≥1n, ≥ 1 and let L be a distribution over (0,1ℓ)n(\0,1\ )^n. An insertional sampler C=(C1,…,Cn)C=(C_1,…,C_n) of L is a sequence of randomized (possibly unbounded) circuits, where • C(1n)≔Cn(Cn−1(⋯(C1(∅))))≡LC(1^n) C_n(C_n-1(·s(C_1( ))))≡ L, and • for every i∈[n]i∈[n] and x∈(0,1ℓ)i−1x∈(\0,1\ )^i-1, Ci(x)C_i(x) is a distribution over strings in (0,1ℓ)i(\0,1\ )^i for which x is a subsequence. We say that C has size B if for all i∈[n]i∈[n], CiC_i is of size at most B. Definition 5.2 (Insertional decomposition). Let n,ℓ≥1n, ≥ 1 and let L be a distribution over (0,1ℓ)n(\0,1\ )^n. An insertional decomposition (L0,…,Ln)(L_0,…,L_n) of L is a sequence of jointly distributed random variables, where • L0L_0 is the fixed distribution over the empty string ∅ , • Ln≡L_n≡ L, and • for every i∈[n]i∈[n] and x∈(0,1ℓ)i−1x∈(\0,1\ )^i-1 with Pr[Li−1=x]>0 [L_i-1=x]>0, Li|Li−1=xL_i L_i-1=x is a distribution over strings in (0,1ℓ)i(\0,1\ )^i for which x is a subsequence. For each insertional decomposition, we compare the apparent conditional entropy of each insertion with its actual conditional entropy. The randomness in choosing the insertion order therefore does not itself contribute to the pseudoentropy gap. Definition 5.3 (Insertional Pseudoentropy). Let n,ℓ≥1n, ≥ 1 and let L be distributed over (0,1ℓ)n(\0,1\ )^n. Let T≥1T≥ 1, k≥0k≥ 0, and 0<ε<10< <1; these quantities may depend on a security parameter λ. We say that L has (T,ε)(T, ) insertional pseudoentropy at least k if, for every insertional decomposition (L0,…,Ln)(L_0,…,L_n) of L, with I uniform on [n][n] independently of the decomposition, there exists a random variable Z, jointly distributed with (I,L0,…,Ln)(I,L_0,…,L_n) and satisfying Z∈(0,1ℓ)iZ∈(\0,1\ )^i whenever I=iI=i, such that 1. H(Z∣I,LI−1)−H(LI∣I,LI−1)≥k−H(L)nH(Z I,L_I-1)-H(L_I I,L_I-1)≥ k-H(L)n, and 2. (I,LI,LI−1)(I,L_I,L_I-1) and (I,Z,LI−1)(I,Z,L_I-1) are (T,ε)(T, ) nonuniformly indistinguishable. The insertional pseudoentropy is the supremum of the values k satisfying this definition. Remark 5.4 (Comparison with next-block pseudoentropy). Both definitions measure the increase in conditional entropy that can remain computationally undetectable. In next-block pseudoentropy, the entropy chain rule makes the subtraction of the actual conditional entropy implicit. For Y=(Y1,…,Yn)Y=(Y_1,…,Y_n) with Yi∈0,1ℓY_i∈\0,1\ , ℓ≥1 ≥ 1, and I uniform on [n][n] independently of Y, the length of Y<IY_<I determines I, so nH(YI∣Y<I)=∑i=1nH(Yi∣Y<i)=H(Y).nH(Y_I Y_<I)= _i=1^nH(Y_i Y_<i)=H(Y). Consequently, the condition H(Z∣Y<I)≥k/nH(Z Y_<I)≥ k/n in Definition 2.21 is equivalent to H(Z∣Y<I)−H(YI∣Y<I)≥k−H(Y)n.H(Z Y_<I)-H(Y_I Y_<I)≥ k-H(Y)n. This is the same entropy-gap form as in Definition 5.3. For an insertional decomposition, however, the entropy chain rule gives nH(LI∣I,LI−1) nH(L_I I,L_I-1) =∑i=1nH(Li∣Li−1) = _i=1^nH(L_i L_i-1) =∑i=1n(H(Li)−H(Li−1)+H(Li−1∣Li)) = _i=1^n (H(L_i)-H(L_i-1)+H(L_i-1 L_i) ) =H(L)+∑i=1nH(Li−1∣Li). =H(L)+ _i=1^nH(L_i-1 L_i). In next-block pseudoentropy, a prefix determines all prior information, whereas an in insertional pseudoentropy, a string given by LiL_i does not necessarily determine its preceding string Li−1L_i-1. For example, for even i, if LiL_i is 0101 repeated i/2i/2 times, then there are i distinct possibilities for Li−1L_i-1 and a random choice of Li−1L_i-1 among them would result in H(Li−1∣Li)=logiH(L_i-1 L_i)= i. Therefore, the sum ∑i∈[n]H(Li−1∣Li) _i∈[n]H(L_i-1 L_i) could be as large as log(n!) (n!). Subtracting the actual conditional entropy in Definition 5.3 ensures that the gap k−H(L)k-H(L) does not count randomness in the choice of insertion order. The quantification over every insertional decomposition accounts for the sampler’s freedom to choose this order. This is implicitly the case for next-block pseudoentropy since left-to-right generation has a single fixed prefix decomposition. The insertional pseudoentropy gap is the insertional pseudoentropy minus H(L)H(L). Taking Z=LIZ=L_I shows that this gap is nonnegative. The joint distribution of Z is chosen for each decomposition before the distinguishing circuit: the same Z must fool every Boolean circuit of size at most T. The guarantee also holds for randomized circuits with independent coins, by fixing their coins and averaging. The length of LI−1L_I-1 determines I, so conditioning on (I,LI−1)(I,L_I-1) is equivalent to conditioning on LI−1L_I-1. The variable Z need not be a valid one-symbol extension of LI−1L_I-1. Remark 5.5 (Equivalent formulation). Equivalently, every insertional decomposition (L0,…,Ln)(L_0,…,L_n) admits random variables Zi∈(0,1ℓ)iZ_i∈(\0,1\ )^i, jointly distributed with the decomposition and independently of I, satisfying ∑i=1n(H(Zi∣Li−1)−H(Li∣Li−1))≥k−H(L) _i=1^n (H(Z_i L_i-1)-H(L_i L_i-1) )≥ k-H(L) and making (I,ZI,LI−1)(I,Z_I,L_I-1) and (I,LI,LI−1)(I,L_I,L_I-1) (T,ε)(T, ) nonuniformly indistinguishable. The family is chosen once for all distinguishing circuits. Given Z, draw each ZiZ_i conditionally on the decomposition using the distribution of Z given I=iI=i and Li−1L_i-1, with fresh randomness independent of I. On zero-probability conditioning events, choose any distribution on (0,1ℓ)i(\0,1\ )^i. Conversely, given such a family, take Z=ZIZ=Z_I with I independent of the decomposition and the family. These constructions preserve the joint distributions being compared and give H(Z∣I,LI−1) H(Z I,L_I-1) =1n∑i=1nH(Zi∣Li−1), = 1n _i=1^nH(Z_i L_i-1), H(LI∣I,LI−1) H(L_I I,L_I-1) =1n∑i=1nH(Li∣Li−1). = 1n _i=1^nH(L_i L_i-1). Thus both formulations have the same entropy gap, circuit size, and distinguishing error. 5.1 Characterization of Insertional Samplability Theorem 5.6 (Characterization of stateless insertional sampling). There exist a universal constant c0∈(0,1]c_0∈(0,1] and a polynomial p with nonnegative coefficients and constant term at least one such that the following holds. Let n,ℓ≥1n, ≥ 1 and let L take values in (0,1ℓ)n(\0,1\ )^n. Let t≥1t≥ 1, 0<ϵ,η,σ<10<ε,η,σ<1, and δ≥ϵδ≥ε. 1. If L has (t,ϵ)(t,ε) insertional pseudoentropy at least H(L)+δH(L)+δ, then, for every B≥1B≥ 1 satisfying B≤mintc0,σ/(nϵ)p(n,2ℓ,1/η,log(n/σ)),B≤ \t^c_0,\,σ/(nε)\p(n,2 ,1/η, (n/σ)), every size-B stateless insertional sampler C over 0,1ℓ\0,1\ satisfies D(L∥C(1n))>δ−σ−nη.D_ KL (L~\|~C(1^n) )>δ-σ-nη. 2. If the (t,ϵ)(t,ε) insertional pseudoentropy of L is at most H(L)+δ−ϵH(L)+δ-ε, then there exists a size-B stateless insertional sampler C over 0,1ℓ\0,1\ with B≤p(t,n,2ℓ,1/ϵ),D(L∥C(1n))≤δ.B≤ p(t,n,2 ,1/ε), D_ KL (L~\|~C(1^n) )≤δ. Remark 5.7. If δ<ϵδ<ε and some B≥1B≥ 1 satisfies the size bound in item 1, then p≥1p≥ 1 forces σ≥nϵ>δσ≥ nε>δ, so the claimed lower bound is negative and the inequality follows from nonnegativity of KL-divergence. If no such B exists, item 1 is vacuous. Lemma 5.8 (Distinct one-symbol insertions). Let i,ℓ≥1i, ≥ 1 and w∈(0,1ℓ)i−1w∈(\0,1\ )^i-1. The set ℰi(w)=z∈(0,1ℓ)i:w is a subsequence of zE_i(w)=\z∈(\0,1\ )^i:w is a subsequence of z\ has exactly Ki=i(2ℓ−1)+1K_i=i(2 -1)+1 elements and admits a bijection i(w,⋅):[Ki]→ℰi(w) Ext_i(w,·):[K_i] _i(w). Given (i,ℓ,w,k)(i, ,w,k), one can compute i(w,k) Ext_i(w,k) in poly(i,2ℓ)poly(i,2 ) time. Given (i,ℓ,w,z)(i, ,w,z) with z∈ℰi(w)z _i(w), one can compute the unique k∈[Ki]k∈[K_i] satisfying i(w,k)=z Ext_i(w,k)=z in the same time bound. Proof. We count each resulting string once by choosing the rightmost position at which its inserted symbol can be placed. For a∈0,1ℓa∈\0,1\ and j∈[i]j∈[i], write (w,a,j)=(w1,…,wj−1,a,wj,…,wi−1). Ins(w,a,j)=(w_1,…,w_j-1,a,w_j,…,w_i-1). For a,b∈0,1ℓa,b∈\0,1\ and 1≤j<k≤i1≤ j<k≤ i, comparison of coordinates j,…,kj,…,k gives (w,a,j)=(w,b,k)⟺a=wj=⋯=wk−1=b. Ins(w,a,j)= Ins(w,b,k) a=w_j=·s=w_k-1=b. Retain all pairs (a,j)(a,j) with j=ij=i, and those with j<ij<i and a≠wja≠ w_j. By the displayed equivalence, these are exactly the rightmost representations, one for each output. Hence |ℰi(w)|=2ℓ+(i−1)(2ℓ−1)=i(2ℓ−1)+1.|E_i(w)|=2 +(i-1)(2 -1)=i(2 -1)+1. Order the retained pairs by increasing j, then lexicographically by a. Define i(w,k) Ext_i(w,k) by inserting the symbol at the position specified by the k-th pair. To invert this map given w and z, enumerate the retained pairs and return the index of the unique pair whose insertion produces z. Both algorithms examine at most i2ℓi2 pairs and use O(iℓ)O(i ) time per pair, giving the claimed poly(i,2ℓ)poly(i,2 ) bound. ∎ Lemma 5.9 (Conditional and final KL-divergence). Let n,ℓ≥1n, ≥ 1 and let L be distributed over (0,1ℓ)n(\0,1\ )^n. For every sequence C=(C1,…,Cn)C=(C_1,…,C_n) of valid insertion circuits, inf(L0,…,Ln)∑i=1nD((Li−1,Li)∥(Li−1,Ci(Li−1)))=D(L∥C(1n)), _(L_0,…,L_n) _i=1^nD_ KL ((L_i-1,L_i)~\|~(L_i-1,C_i(L_i-1)) )=D_ KL (L~\|~C(1^n) ), where the infimum is over insertional decompositions of L. Moreover, if D(L∥C(1n))<∞D_ KL (L~\|~C(1^n) )<∞, there exists an insertional decomposition (L0,…,Ln)(L_0,…,L_n) of L that forms a Markov chain and satisfies ∑i=1nD((Li−1,Li)∥(Li−1,Ci(Li−1)))=D(L∥C(1n)). _i=1^nD_ KL ((L_i-1,L_i)~\|~(L_i-1,C_i(L_i-1)) )=D_ KL (L~\|~C(1^n) ). Proof. Let (L0,…,Ln)(L_0,…,L_n) be any insertional decomposition of L, and X0=∅X_0= , Xi←Ci(Xi−1)X_i← C_i(X_i-1) with fresh independent coins, so Xn≡C(1n)X_n≡ C(1^n). Then, D(L∥C(1n)) D_ KL (L~\|~C(1^n) ) =D(Ln∥Xn) =D_ KL (L_n~\|~X_n ) ≤D((Ln−1,Ln)∥(Xn−1,Xn)) ≤ D_ KL ((L_n-1,L_n)~\|~(X_n-1,X_n) ) =D(Ln−1∥Xn−1)+x∼Ln−1D(Ln∣Ln−1=x∥Cn(x)) =D_ KL (L_n-1~\|~X_n-1 )+ _x L_n-1D_ KL (L_n _L_n-1=x~\|~C_n(x) ) ≤∑i=1nx∼Li−1D(Li∣Li−1=x∥Ci(x)) ≤ _i=1^n _x L_i-1D_ KL (L_i _L_i-1=x~\|~C_i(x) ) =∑i=1nD((Li−1,Li)∥(Li−1,Ci(Li−1))). = _i=1^nD_ KL ((L_i-1,L_i)~\|~(L_i-1,C_i(L_i-1)) ). The first inequality is Fact 2.9 applied to the map that keeps the second coordinate. The next equality is Fact 2.7: given Xn−1=xX_n-1=x, the distribution of XnX_n is Cn(x)C_n(x). Repeating these two steps down to i=1i=1 gives the sum, since D(L0∥X0)=0D_ KL (L_0~\|~X_0 )=0. The last equality applies the same chain rule to two pairs with the same first-coordinate distribution Li−1L_i-1. Since the decomposition was arbitrary, the final KL divergence is at most the infimum in the statement. Write Q(x0,…,xn)=Pr[X0=x0,…,Xn=xn]Q(x_0,…,x_n)= [X_0=x_0,…,X_n=x_n] and Qn(z)=Pr[Xn=z]Q_n(z)= [X_n=z]. For the reverse inequality, assume D(L∥Qn)<∞D_ KL (L~\|~Q_n )<∞ and define M(x0,…,xn)=Q(x0,…,xn)Pr[L=xn]Qn(xn),Qn(xn)>0,0,Qn(xn)=0.M(x_0,…,x_n)= casesQ(x_0,…,x_n) [L=x_n]Q_n(x_n),&Q_n(x_n)>0,\\ 0,&Q_n(x_n)=0. cases For Qn(z)>0Q_n(z)>0, ∑x0,…,xn−1M(x0,…,xn−1,z) _x_0,…,x_n-1M(x_0,…,x_n-1,z) =Pr[L=z]Qn(z)∑x0,…,xn−1Q(x0,…,xn−1,z) = [L=z]Q_n(z) _x_0,…,x_n-1Q(x_0,…,x_n-1,z) =Pr[L=z]. = [L=z]. Both sides are zero otherwise, since (L)⊆(Qn) supp(L) supp(Q_n). Thus (M0,…,Mn)∼M(M_0,…,M_n) M satisfies Mn≡LM_n≡ L. Since (M)⊆(Q) supp(M) supp(Q), M0=∅M_0= and every step inserts one symbol. To compute the conditional probabilities, for i∈0,…,ni∈\0,…,n\ set hi(w)=∑z:Qn(z)>0Pr[Xn=z∣Xi=w]Pr[L=z]Qn(z)(w∈(Xi)),h_i(w)= _z:\,Q_n(z)>0 [X_n=z X_i=w] [L=z]Q_n(z) (w∈ supp(X_i)), and set hi(w)=0h_i(w)=0 otherwise. The Markov property of (X0,…,Xn)(X_0,…,X_n) gives Pr[M0=x0,…,Mi=xi] [M_0=x_0,…,M_i=x_i] =∑z:Qn(z)>0Pr[X0=x0,…,Xi=xi,Xn=z]Pr[L=z]Qn(z) = _z:\,Q_n(z)>0 [X_0=x_0,…,X_i=x_i,X_n=z] [L=z]Q_n(z) =Pr[X0=x0,…,Xi=xi]hi(xi). = [X_0=x_0,…,X_i=x_i]h_i(x_i). For i∈[n]i∈[n] and every tuple with Pr[M0=x0,…,Mi−1=xi−1]>0 [M_0=x_0,…,M_i-1=x_i-1]>0, division gives Pr[Mi=z∣M0=x0,…,Mi−1=xi−1] [M_i=z M_0=x_0,…,M_i-1=x_i-1] =Pr[Ci(xi−1)=z]hi(z)hi−1(xi−1) = [C_i(x_i-1)=z] h_i(z)h_i-1(x_i-1) =Pr[Mi=z∣Mi−1=xi−1]. = [M_i=z M_i-1=x_i-1]. The ratio depends on the preceding tuple only through xi−1x_i-1, so the last equality holds and (M0,…,Mn)(M_0,…,M_n) is a Markov insertional decomposition of L. By Fact 2.8, ∑i=1nD((Mi−1,Mi)∥(Mi−1,Ci(Mi−1))) _i=1^nD_ KL ((M_i-1,M_i)~\|~(M_i-1,C_i(M_i-1)) ) =D(M∥Q) =D_ KL (M~\|~Q ) =∑(x0,…,xn)∈(M)M(x0,…,xn)logPr[L=xn]Qn(xn) = _(x_0,…,x_n)∈ supp(M)M(x_0,…,x_n) [L=x_n]Q_n(x_n) =∑z∈(L)Pr[L=z]logPr[L=z]Qn(z) = _z∈ supp(L) [L=z] [L=z]Q_n(z) =D(L∥C(1n)). =D_ KL (L~\|~C(1^n) ). This decomposition attains the infimum. ∎ Lemma 5.10 (Insertional pseudoentropy implies conditional sampling hardness). Under the hypotheses and size condition of the first part of Theorem 5.6, every insertional decomposition (L0,…,Ln)(L_0,…,L_n) of L and every size-B stateless insertional sampler C over 0,1ℓ\0,1\ satisfy i←[n]D((Li−1,Li)∥(Li−1,Ci(Li−1)))>δ−σn−η. _i←[n]D_ KL ((L_i-1,L_i)~\|~(L_i-1,C_i(L_i-1)) )> δ-σn-η. Proof. Fix an insertional decomposition (L0,…,Ln)(L_0,…,L_n) and a sampler C, and put di=D((Li−1,Li)∥(Li−1,Ci(Li−1))),d=∑i=1ndi.d_i=D_ KL ((L_i-1,L_i)~\|~(L_i-1,C_i(L_i-1)) ), d= _i=1^nd_i. If d=∞d=∞, the claim follows, so assume d<∞d<∞. By Definition 5.3 and Remark 5.5, choose a family Zi∈(0,1ℓ)iZ_i∈(\0,1\ )^i such that ∑i=1nH(Zi∣Li−1)≥∑i=1nH(Li∣Li−1)+δ _i=1^nH(Z_i L_i-1)≥ _i=1^nH(L_i L_i-1)+δ and (I,ZI,LI−1)(I,Z_I,L_I-1) and (I,LI,LI−1)(I,L_I,L_I-1) are (t,ϵ)(t,ε) nonuniformly indistinguishable, where I is uniform on [n][n] and independent of the family and decomposition. We estimate the sampler’s output probabilities and test their negative logarithms. The expected negative logarithm will be at least H(Zi∣Li−1)H(Z_i L_i-1) on ZiZ_i and at most H(Li∣Li−1)+di+η/4H(L_i L_i-1)+d_i+η/4 on LiL_i. Indistinguishability compares their averages over the uniform index I. Let ℰi(w)E_i(w) and Ki=i(2ℓ−1)+1K_i=i(2 -1)+1 be as in Lemma 5.8, and set q=n2ℓ,M=⌈32q/η⌉,θ=2−⌈log(32/η)⌉,Λ=nℓ+log(1/θ).q=n2 , M= 32q/η , θ=2^- (32/η) , =n + (1/θ). On input (i,z,w)(i,z,w), draw M samples from Ci(w)C_i(w) with independent coins, also independent of the decomposition and auxiliary family. Let NzN_z count the samples equal to z. Define P^w(z)=Nz+1M+Ki,z∈ℰi(w),0,z∉ℰi(w),Rw(z)=(1−θ)P^w(z)+θ2iℓ. P_w(z)= cases N_z+1M+K_i,&z _i(w),\\ 0,&z _i(w), cases R_w(z)=(1-θ) P_w(z)+ θ2^i . Since ∑z∈ℰi(w)Nz=M _z _i(w)N_z=M, both P^w P_w and RwR_w are probability distributions. The uniform term is needed because ZiZ_i need not belong to ℰi(Li−1)E_i(L_i-1). For every length-i string z, θ2iℓ≤Rw(z)≤1,0≤−logRw(z)≤Λ. θ2^i ≤ R_w(z)≤ 1, 0≤- R_w(z)≤ . Set b=⌈log(16Λ/η)⌉b= (16 /η) and ρ=2−bρ=2^-b. The circuit D accepts with probability ρ⌊−logRw(z)Λρ⌋.ρ - R_w(z) ρ . For each i, store the displayed floor for the M+1M+1 valid-extension counts Nz=0,…,MN_z=0,…,M and for the single invalid-extension case. This gives n(M+2)n(M+2) entries, each an integer in 0,…,2b\0,…,2^b\ stored using b+1b+1 bits. Draw a fresh uniform b-bit integer and accept exactly when it is smaller than the stored integer. The circuit contains M copies of each CjC_j; it selects the count from the branch j=ij=i, whose copies receive w; the other branches receive fixed strings of the required lengths. Membership in ℰi(w)E_i(w) is tested by deleting each position of z and comparing the resulting string with w. Selection, counting, these comparisons, and table lookup require poly(n,M,ℓ,b)poly(n,M, ,b) additional gates. Consequently, for a universal polynomial A, |D|≤nMB+poly(n,M,ℓ,b)≤BA(n,2ℓ,1/η),|D|≤ nMB+poly(n,M, ,b)≤ BA(n,2 ,1/η), where the last inequality uses B≥1B≥ 1 and the choices of M,bM,b. Choose the polynomial p in Theorem 5.6 large enough that p(n,2ℓ,1/η,log(n/σ))≥maxA(n,2ℓ,1/η),2Λp(n,2 ,1/η, (n/σ))≥ \A(n,2 ,1/η),2 \. The assumed size bound and c0≤1c_0≤ 1 give |D|≤BA(n,2ℓ,1/η)≤tc0≤t,nΛϵ≤σ/2,Λρ≤η/16.|D|≤ BA(n,2 ,1/η)≤ t^c_0≤ t, n ε≤σ/2, ρ≤η/16. We first bound the expected negative logarithm on LiL_i. For w∈(Li−1)w∈ supp(L_i-1), apply Claim 2.11 on ℰi(w)E_i(w) with P=Ci(w)P=C_i(w), Q=Li∣Li−1=wQ=L_i _L_i-1=w, and M samples. Since Rw(z)≥(1−θ)P^w(z)R_w(z)≥(1-θ) P_w(z), D(Li∣Li−1=w∥Rw) D_ KL (L_i _L_i-1=w~\|~R_w ) ≤D(Li∣Li−1=w∥P^w)−log(1−θ) ≤ D_ KL (L_i _L_i-1=w~\|~ P_w )- (1-θ) ≤D(Li∣Li−1=w∥Ci(w))+logM+KiM+1−log(1−θ). ≤ D_ KL (L_i _L_i-1=w~\|~C_i(w) )+ M+K_iM+1- (1-θ). Here expectations are over the M samples. Since Ki≤qK_i≤ q and θ≤η/32θ≤η/32, the parameter choices give logM+KiM+1−log(1−θ)<η/4. M+K_iM+1- (1-θ)<η/4. Drawing the samples independently of LiL_i conditional on Li−1L_i-1 and applying Fact 2.7 to did_i gives [−logRLi−1(Li)] [- R_L_i-1(L_i)] =H(Li∣Li−1)+w∼Li−1D(Li∣Li−1=w∥Rw) =H(L_i L_i-1)+ _w L_i-1 D_ KL (L_i _L_i-1=w~\|~R_w ) ≤H(Li∣Li−1)+di+η/4. ≤ H(L_i L_i-1)+d_i+η/4. The same samples are independent of ZiZ_i conditional on Li−1L_i-1. For every w∈(Li−1)w∈ supp(L_i-1) and every value of RwR_w, z∼Zi∣Li−1=w[−logRw(z)] _z Z_i _L_i-1=w[- R_w(z)] =H(Zi∣Li−1=w)+D(Zi∣Li−1=w∥Rw) =H(Z_i L_i-1=w)+D_ KL (Z_i _L_i-1=w~\|~R_w ) ≥H(Zi∣Li−1=w). ≥ H(Z_i L_i-1=w). For Vi=LiV_i=L_i or Vi=ZiV_i=Z_i, the rounding gives |ΛPr[D(i,Vi,Li−1)=1]−[−logRLi−1(Vi)]|≤Λρ. | [D(i,V_i,L_i-1)=1]- [- R_L_i-1(V_i)] |≤ ρ. Here the expectations include the fresh samples drawn by D. Since |D|≤t|D|≤ t, indistinguishability gives |∑iPr[D(i,Zi,Li−1)=1]−∑iPr[D(i,Li,Li−1)=1]|≤nϵ. | _i [D(i,Z_i,L_i-1)=1]- _i [D(i,L_i,L_i-1)=1] |≤ nε. Combining these inequalities, ∑iH(Li∣Li−1)+δ _iH(L_i L_i-1)+δ ≤∑iH(Zi∣Li−1) ≤ _iH(Z_i L_i-1) ≤∑i[−logRLi−1(Zi)] ≤ _i [- R_L_i-1(Z_i)] ≤Λ∑iPr[D(i,Zi,Li−1)=1]+nΛρ ≤ _i [D(i,Z_i,L_i-1)=1]+n ρ ≤Λ∑iPr[D(i,Li,Li−1)=1]+nΛϵ+nΛρ ≤ _i [D(i,L_i,L_i-1)=1]+n ε+n ρ ≤∑i[−logRLi−1(Li)]+nΛϵ+2nΛρ ≤ _i [- R_L_i-1(L_i)]+n ε+2n ρ ≤∑iH(Li∣Li−1)+d+nη/4+nΛϵ+2nΛρ ≤ _iH(L_i L_i-1)+d+nη/4+n ε+2n ρ ≤∑iH(Li∣Li−1)+d+σ/2+3nη/8. ≤ _iH(L_i L_i-1)+d+σ/2+3nη/8. Subtracting ∑iH(Li∣Li−1) _iH(L_i L_i-1) from both sides gives d>δ−σ−nηd>δ-σ-nη. Dividing by n proves the claim. ∎ Lemma 5.11 (Small insertional pseudoentropy gives conditional samplers). Under the hypotheses of the second part of Theorem 5.6, there are an insertional decomposition (L0,…,Ln)(L_0,…,L_n) of L and a size-B stateless insertional sampler C over 0,1ℓ\0,1\ , with B≤p(t,n,2ℓ,1/ϵ)B≤ p(t,n,2 ,1/ε), such that i←[n]D((Li−1,Li)∥(Li−1,Ci(Li−1)))≤δn. _i←[n]D_ KL ((L_i-1,L_i)~\|~(L_i-1,C_i(L_i-1)) )≤ δn. Proof. By assumption, the (t,ϵ)(t,ε) insertional pseudoentropy of L is at most H(L)+δ−ϵH(L)+δ-ε. Indexing the valid extensions in Lemma 5.8 gives alphabets of size at most n2ℓn2 for applying item 2 of Theorem 2.23. We bound the sum of the indices’ conditional pseudoentropy gaps by combining their maximizing auxiliary variables into one variable in Definition 5.3. Set k∗=H(L)+δ−ϵ/2,η′=ϵ/(4n),2nη′=ϵ/2.k_*=H(L)+δ-ε/2, η =ε/(4n), 2nη =ε/2. Since H(L)+δ−ϵ<k∗H(L)+δ-ε<k_*, Definition 5.3 gives an insertional decomposition (L0,…,Ln)(L_0,…,L_n) for which every Z satisfying the length and (t,ϵ)(t,ε)-indistinguishability conditions in that definition satisfies nH(Z∣I,LI−1)−∑i=1nH(Li∣Li−1)<k∗−H(L)=δ−ϵ/2.nH(Z I,L_I-1)- _i=1^nH(L_i L_i-1)<k_*-H(L)=δ-ε/2. Here I is uniform on [n][n] and independent of the decomposition. For each i, let Ki=i(2ℓ−1)+1K_i=i(2 -1)+1 and let i(w,⋅):[Ki]→ℰi(w) Ext_i(w,·):[K_i] _i(w) be the bijection in Lemma 5.8. Define Ai∈[Ki]A_i∈[K_i] by Li=i(Li−1,Ai)L_i= Ext_i(L_i-1,A_i). Since the map is a bijection for each fixed Li−1=wL_i-1=w, H(Ai∣Li−1)=H(Li∣Li−1).H(A_i L_i-1)=H(L_i L_i-1). Let R(n,2ℓ)R(n,2 ) be a fixed polynomial bounding the circuit size of each i Ext_i and the overhead for composing it with a circuit whose index input is fixed to i, and put t′=t+R(n,2ℓ)t =t+R(n,2 ). Such a polynomial exists by the algorithms in Lemma 5.8. Let hih_i be the maximum (t′,η′)(t ,η ) conditional pseudoentropy of AiA_i given Li−1L_i-1 over the alphabet [Ki][K_i], and put gi=hi−H(Ai∣Li−1)≥0.g_i=h_i-H(A_i L_i-1)≥ 0. Nonnegativity follows by using AiA_i itself as an auxiliary variable. We will show ∑igi<δ−ϵ/2 _ig_i<δ-ε/2. By the compactness observation after Definition 2.20, choose maximizing Ai′∈[Ki]A_i ∈[K_i] such that H(Ai′∣Li−1)=hiH(A_i L_i-1)=h_i and (Li−1,Ai′)(L_i-1,A_i ) and (Li−1,Ai)(L_i-1,A_i) are (t′,η′)(t ,η ) nonuniformly indistinguishable. Realize these pairs jointly with (L0,…,Ln)(L_0,…,L_n) by setting Pr[A1′=a1,…,An′=an∣L0=w0,…,Ln=wn] [A_1 =a_1,…,A_n =a_n L_0=w_0,…,L_n=w_n] =∏i=1nPr[Ai′=ai∣Li−1=wi−1] = _i=1^n [A_i =a_i L_i-1=w_i-1] for every tuple (w0,…,wn)(w_0,…,w_n) of positive probability, using the chosen pair distributions on the right. This preserves each distribution (Li−1,Ai′)(L_i-1,A_i ). Put Zi=i(Li−1,Ai′),H(Zi∣Li−1)=H(Ai′∣Li−1)=hi,Z_i= Ext_i(L_i-1,A_i ), H(Z_i L_i-1)=H(A_i L_i-1)=h_i, choose I independently of this family and the decomposition, and set Z=ZIZ=Z_I. Fix any Boolean circuit D of size at most t. For each fixed i, the circuit with inputs w∈(0,1ℓ)i−1w∈(\0,1\ )^i-1 and a∈[Ki]a∈[K_i] given by Di(w,a)=D(i,i(w,a),w)D_i(w,a)=D(i, Ext_i(w,a),w) has size at most t+R(n,2ℓ)=t′t+R(n,2 )=t . The defining indistinguishability of Ai′A_i gives |Pr[D(I,Z,LI−1)=1]−Pr[D(I,LI,LI−1)=1]| | [D(I,Z,L_I-1)=1]- [D(I,L_I,L_I-1)=1] | =|1n∑i=1n(Pr[Di(Li−1,Ai′)=1]−Pr[Di(Li−1,Ai)=1])| = | 1n _i=1^n ( [D_i(L_i-1,A_i )=1]- [D_i(L_i-1,A_i)=1] ) | ≤1n∑i=1n|Pr[Di(Li−1,Ai′)=1]−Pr[Di(Li−1,Ai)=1]| ≤ 1n _i=1^n | [D_i(L_i-1,A_i )=1]- [D_i(L_i-1,A_i)=1] | ≤η′≤ϵ. ≤η ≤ε. The family (Z1,…,Zn)(Z_1,…,Z_n) was fixed before D, and Z∈(0,1ℓ)iZ∈(\0,1\ )^i when I=iI=i. Thus Z satisfies the length and indistinguishability conditions for the chosen decomposition, so ∑i=1ngi _i=1^ng_i =∑i=1nhi−∑i=1nH(Ai∣Li−1) = _i=1^nh_i- _i=1^nH(A_i L_i-1) =∑i=1nH(Zi∣Li−1)−∑i=1nH(Li∣Li−1) = _i=1^nH(Z_i L_i-1)- _i=1^nH(L_i L_i-1) =nH(Z∣I,LI−1)−∑i=1nH(Li∣Li−1) =nH(Z I,L_I-1)- _i=1^nH(L_i L_i-1) <k∗−H(L)=δ−ϵ/2. <k_*-H(L)=δ-ε/2. Apply item 2 of Theorem 2.23 for each i with X=Li−1X=L_i-1, B=AiB=A_i, m=mi=(i−1)ℓ≥0m=m_i=(i-1) ≥ 0, q=Ki≥2q=K_i≥ 2, circuit-size parameter t′t , gap bound gig_i, and η=η′η=η . It gives a randomized circuit Si:0,1mi→[Ki]S_i:\0,1\^m_i→[K_i] satisfying |Si| |S_i| ≤p0(t′,mi,Ki,1/η′), ≤ p_0(t ,m_i,K_i,1/η ), D((Li−1,Ai)∥(Li−1,Si(Li−1))) D_ KL ((L_i-1,A_i)~\|~(L_i-1,S_i(L_i-1)) ) ≤gi+2η′. ≤ g_i+2η . Set Ci(w)=i(w,Si(w))C_i(w)= Ext_i(w,S_i(w)), with fresh independent coins at each step. Since Si(w)∈[Ki]S_i(w)∈[K_i], Ci(w)∈ℰi(w)C_i(w) _i(w) for every input w∈(0,1ℓ)i−1w∈(\0,1\ )^i-1. The bijection (w,a)↦(w,i(w,a))(w,a) (w, Ext_i(w,a)) gives D((Li−1,Li)∥(Li−1,Ci(Li−1))) D_ KL ((L_i-1,L_i)~\|~(L_i-1,C_i(L_i-1)) ) =D((Li−1,Ai)∥(Li−1,Si(Li−1))) =D_ KL ((L_i-1,A_i)~\|~(L_i-1,S_i(L_i-1)) ) ≤gi+2η′. ≤ g_i+2η . Hence ∑i=1nD((Li−1,Li)∥(Li−1,Ci(Li−1))) _i=1^nD_ KL ((L_i-1,L_i)~\|~(L_i-1,C_i(L_i-1)) ) ≤∑i=1ngi+2nη′ ≤ _i=1^ng_i+2nη <δ−ϵ/2+ϵ/2=δ. <δ-ε/2+ε/2=δ. Dividing by n gives the stated average bound. Finally, mi≤n2ℓm_i≤ n2 , Ki≤n2ℓK_i≤ n2 , and 1/η′=4n/ϵ1/η =4n/ε. Since p0p_0 has nonnegative coefficients, |Ci| |C_i| ≤|Si|+R(n,2ℓ) ≤|S_i|+R(n,2 ) ≤p0(t+R(n,2ℓ),n2ℓ,n2ℓ,4n/ϵ)+R(n,2ℓ). ≤ p_0(t+R(n,2 ),n2 ,n2 ,4n/ε)+R(n,2 ). Choose the polynomial p in Theorem 5.6 large enough to dominate this quantity at (t,n,2ℓ,1/ϵ)(t,n,2 ,1/ε) and the bound required in its first part. Then B:=maxi|Ci|≤p(t,n,2ℓ,1/ϵ)B:= _i|C_i|≤ p(t,n,2 ,1/ε). ∎ Proof of Theorem 5.6. For the first part, fix a sampler C satisfying the size bound. Write d=D(L∥C(1n))d=D_ KL (L~\|~C(1^n) ). If d=∞d=∞, the claim follows. Otherwise, Lemma 5.9 gives an insertional decomposition (L0,…,Ln)(L_0,…,L_n) of L whose sum of conditional KL-divergences from C equals d. Applying Lemma 5.10 to this decomposition gives D(L∥C(1n)) D_ KL (L~\|~C(1^n) ) =∑i=1nD((Li−1,Li)∥(Li−1,Ci(Li−1))) = _i=1^nD_ KL ((L_i-1,L_i)~\|~(L_i-1,C_i(L_i-1)) ) >δ−σ−nη. >δ-σ-nη. For the second part, take the decomposition and sampler from Lemma 5.11. The sampler has the required size, and Lemma 5.9 gives D(L∥C(1n))≤∑iD((Li−1,Li)∥(Li−1,Ci(Li−1)))≤δ.D_ KL (L~\|~C(1^n) )≤ _iD_ KL ((L_i-1,L_i)~\|~(L_i-1,C_i(L_i-1)) )≤δ. ∎ Finally, insertion does not recover all efficient sampling: Theorem 7.2 proves a separation under 2γλα2^γλ^α-secure one-way functions, for constants γ>0γ>0 and 1/2<α<11/2<α<1. This construction uses 2t2t tokens over an alphabet of size 2t⋅22t2t· 2^2t. 6 Insertionally-Samplable PRGs A pseudorandom generator (PRG) is a polynomial-time family G:0,1k→0,1mG:\0,1\^k→\0,1\^m, with m>km>k, whose output on a uniform seed is computationally indistinguishable from UmU_m. Here security is against nonuniform polynomial-size circuits: every such circuit has negligible distinguishing advantage. The following construction shows that an insertional sampler can generate pseudorandom bits without retaining the seed privately. Theorem 6.1 (Insertionally samplable pseudorandom generators). Let G:0,1t→0,12t2G:\0,1\^t→\0,1\^2t^2 be a polynomial-time pseudorandom generator secure against nonuniform polynomial-size circuits. There exists a polynomial-time pseudorandom generator H:0,13t2→0,14t2H:\0,1\^3t^2→\0,1\^4t^2 whose output distribution admits an exact polynomial-size stateless insertional bit sampler. Proof. The sampler first generates bits from which it can recover a seed. After using this seed, it inserts additional random bits so that the final string conceals which bits were originally generated. Define H by the following process, with its seed consisting of the 3t23t^2 independent uniform bits used below. 1. Append t2t^2 independent uniform bits, obtaining X=X1⋯Xt2X=X_1·s X_t^2. Partition X into t consecutive groups of t bits. Define sjs_j as the parity of the bits in group j, and put s=s1⋯sts=s_1·s s_t. 2. For a=1,…,2t2a=1,…,2t^2, read X from the first t2t^2 positions, recompute s, and append G(s)aG(s)_a. (Following this process, the resulting string is X|G(s)X\|G(s).) 3. For i=1,…,t2i=1,…,t^2, sample fresh independent uniform bits b,rb,r. Insert b immediately before XiX_i if r=0r=0, and immediately after it otherwise. Denote the resulting ordered pair by ZiZ_i, and put Z=Z1‖⋯‖Zt2Z=Z_1\|·s\|Z_t^2. The final output is Z|G(s)Z\|G(s). The process uses t2t^2 random bits in item 1 and 2t22t^2 in item 3, and outputs 4t24t^2 bits. It is stateless: throughout item 2, X occupies the first t2t^2 positions. After processing i−1i-1 bits in item 3, the current string is Z1∥⋯∥Zi−1∥Xi⋯Xt2∥G(s),Z_1\|·s\|Z_i-1\|X_i·s X_t^2\|G(s), so XiX_i occupies position 2i−12i-1. The current length determines the phase and index. Every transition therefore uses only the current string and fresh coins, and has polynomial-size circuits. It remains to prove pseudorandomness. The pairs ZiZ_i are independent and uniform over 00,01,10,11\00,01,10,11\, so Z is uniform. Conditioned on any Z=zZ=z, the original bits XiX_i remain independent: an equal pair determines its original bit, whereas an unequal pair leaves its original bit uniform. Hence, if a group contains an unequal pair, its parity is uniform given Z=zZ=z. The probability that all t pairs of a given group are equal is 2−t2^-t. Except on an event of probability at most t2−t2^-t, every group therefore has an unequal pair, making all seed bits independent and uniform given Z. Consequently, Δ((Z,s),(U2t2,Ut))≤t2−t, ((Z,s),(U_2t^2,U_t) )≤ t2^-t, where the uniforms on the right are independent. Applying (z,s)↦z|G(s)(z,s) z\|G(s) shows that H(U3t2)H(U_3t^2) is statistically close to U2t2|G(Ut)U_2t^2\|G(U_t). By security of G, the latter is computationally indistinguishable from U4t2U_4t^2, proving security of H. ∎ 7 Separations in Sampling and Pseudoentropy We separate insertional from sequential sampling over a binary alphabet in Section 7.1, and general from insertional sampling over a larger alphabet in Section 7.2. In Section 7.3, we derive the corresponding separations between pseudoentropy notions. 7.1 Separating Insertional Samplers from Sequential Samplers In this section formalize the intuition described in [17] who described a distribution that was hard for sequential samplers to derive. Moreover, we show that the same intuition does not apply to insertional samplers, thereby showing that insertional samplers cover a larger class of distributions compared to their sequential counterparts. Proposition 7.1 (Insertional sampling is stronger than sequential sampling). Let f:0,1n→0,1nf \0,1\^n→\0,1\^n be a one-way function secure against polynomial-size circuits. There exists a distribution L over 0,12n\0,1\^2n such that: 1. Every stateless sequential sampler of size (n) (n) satisfies D(L∥C(12n))>log(n)D_ KL (L~\|~C(1^2n) )> (n), and 2. There is a (n) (n)-size insertional sampler that samples L. Proof. We set L to be the distribution L=(f(X),X)L=(f(X),X) where X is uniform over 0,1n\0,1\^n. We now prove the first item. Suppose towards contradiction that for some constant c>0c>0 and infinitely many n, a size-ncn^c stateless sequential sampler C satisfies D(L∥C(12n))≤lognD_ KL (L~\|~C(1^2n) )≤ n. We show that this invalidates security of the one-way function. Given y=f(x)y=f(x) the inverter I runs C sequentially on prefix y and outputs the n-bit suffix generated by C. For X←UnX← U_n, put Y=f(X)Y=f(X) and write (V,W)←C(12n)(V,W)← C(1^2n), where V,W∈0,1nV,W∈\0,1\^n. Since C is stateless, W∣V=yW _V=y is distributed as I(y)I(y) for every y∈(V)y∈ supp(V). The assumed finite KL-divergence ensures that (Y)⊆(V) supp(Y) supp(V). Applying the KL chain rule (Fact 2.7) to both pairs gives D((Y,X)∥(Y,I(Y))) D_ KL ((Y,X)~\|~(Y,I(Y)) ) =y←Y[D(X∣Y=y∥I(y))] = _y← Y [D_ KL (X _Y=y~\|~I(y) ) ] =D(L∥C(12n))−D(Y∥V)≤logn, =D_ KL (L~\|~C(1^2n) )-D_ KL (Y~\|~V )≤ n, where the inequality uses nonnegativity of KL-divergence. Let p=Pr[f(I(Y))=Y]p= [f(I(Y))=Y] be the inverter’s success probability. The test T(y,x′)=[f(x′)=y]T(y,x )= 1[f(x )=y] maps (Y,X)(Y,X) to the constant 11 and (Y,I(Y))(Y,I(Y)) to a Bernoulli random variable with parameter p. Thus data processing (Fact 2.9) gives log(1/p) (1/p) =D(Ber(1)∥Ber(p)) =D_ KL (Ber(1)~\|~Ber(p) ) ≤D((Y,X)∥(Y,I(Y)))≤logn. ≤ D_ KL ((Y,X)~\|~(Y,I(Y)) )≤ n. Hence the polynomial-size inverter I succeeds with probability p≥1/np≥ 1/n for infinitely many n, contradicting one-wayness. We now show the second item by describing an insertional sampler for L: 1. For the first n steps, append independent uniform bits, obtaining x←Unx← U_n. 2. At step n+jn+j, for j∈[n]j∈[n], read x from the input, compute f(x)f(x) and output (j,f(x)j)(j,f(x)_j) (i.e., place the j-th bit of f(x)f(x) at index j. That this insertional sampler samples L exactly and is efficient is immediate by construction. ∎ 7.2 Separating General Samplers from Insertional Samplers We construct an efficiently samplable distribution that is hard for stateless insertional samplers. Theorem 7.2 (General sampling is stronger than insertional sampling). Let (fλ)λ≥1(f_λ)_λ≥ 1 be a length-preserving one-way function family with 2γλα2^γλ^α security against circuits, for constants γ>0γ>0 and 1/2<α<11/2<α<1. For t≥2t≥ 2, let ℓ=2t+⌈log(2t)⌉ =2t+ (2t) . There exists a distribution L=LtL=L_t over (0,1ℓ)2t(\0,1\ )^2t such that: 1. For every constant c>0c>0 and all sufficiently large t, every stateless insertional sampler C of size at most 2ct2^ct satisfies D(L∥C(12t))≥γt2α−2tD_ KL (L~\|~C(1^2t) )≥γ t^2α-2t. 2. There is a (t) (t)-size randomized circuit that samples L exactly. Proof. We first define L. Let q=2tq=2^t, fix distinct β1,…,β2t∈q _1,…, _2t _q, and identify qtF_q^t with 0,1t2\0,1\^t^2. For x,r,y∈qtx,r,y _q^t, put Px,r(z)=∑j<trjzj+∑j<txjzt+jP_x,r(z)= _j<tr_jz^j+ _j<tx_jz^t+j and Qy(z)=∑j<tyjzjQ_y(z)= _j<ty_jz^j. The distribution L is sampled as follows: 1. Sample independent uniform X,R←qtX,R _q^t and compute Y=ft2(X)Y=f_t^2(X). 2. Output ((,,,,,))i=12t((i,P_X,R( _i),Q_Y( _i)))_i=1^2t, treating each triple as one ℓ -bit token. The evaluations of PX,RP_X,R form a ramp secret-sharing of X: any fixed t shares are uniform and independent of X, since the Vandermonde matrix acting on R is invertible, while all 2t2t shares recover X,RX,R by interpolation. Intermediate numbers of shares may reveal partial information about X. In contrast, any t evaluations of QYQ_Y determine Y. Thus we can sample any fixed t tokens given only the image, but completing them to a valid output reveals a preimage. Observe that the description of the distribution defines a circuit for sampling from it. This sampler runs in (t) (t) time, proving the second item. Its alphabet is [2t]×q2[2t]×F_q^2, which has size 2t 22t2t\,2^2t. We now prove the first item. Suppose towards contradiction that for some constant c>0c>0 and infinitely many t, a stateless insertional sampler C of size at most 2ct2^ct has KL error d:=D(L∥C(12t))d:=D_ KL (L~\|~C(1^2t) ) smaller than γt2α−2tγ t^2α-2t. We show that this invalidates security of the one-way function. Let =(L)S= supp(L) and observe that membership in S can be efficiently tested by interpolating to derive X and then checking whether the third entries in the output are consistent with f(X)f(X). We now describe the inverter. Let b=⌈log(2t)⌉≤2tb= 2tt ≤ 2t. Given y=ft2(x)y=f_t^2(x), the inverter I proceeds as follows: 1. Choose a t-element subset J⊆[2t]J [2t] by reducing a uniform b-bit integer modulo (2t) 2tt and taking the corresponding subset in lexicographic order. 2. Sample independent uniform uj←qu_j _q for j∈Jj∈ J. Set Wt=((,,,,,))j∈JW_t=((j,u_j,Q_y( _j)))_j∈ J in increasing tag order. 3. For i=t+1,…,2ti=t+1,…,2t, sample Wi←Ci(Wi−1)W_i← C_i(W_i-1) using fresh coins. 4. If W2t∈W_2t , output the preimage recovered by interpolating the entries that encode x; otherwise output ⊥ . On acceptance, the preserved t evaluations of QyQ_y agree with those of Qft2(x′)Q_f_t^2(x ) for the recovered x′x . Both polynomials have degree less than t, so ft2(x′)=yf_t^2(x )=y. The inverter has size 2O(t)2^O(t): it makes t calls to C and otherwise uses (t) (t) computation. It remains to lower-bound its success probability. Below, the strings Wt,…,W2tW_t,…,W_2t are generated on a random challenge Y=ft2(X)Y=f_t^2(X) with X←Ut2X← U_t^2. By Lemma 5.9, there is a Markov insertional decomposition (L0,…,L2t)(L_0,…,L_2t) of L such that, writing di=D((Li−1,Li)∥(Li−1,Ci(Li−1)))d_i=D_ KL ((L_i-1,L_i)~\|~(L_i-1,C_i(L_i-1)) ), we have ∑i=12tdi=d _i=1^2td_i=d. For a fixed set J of t tags, write L|JL|_J for the restriction of L to those tags. The secret-sharing property implies that WtW_t, conditioned on choosing J, is distributed as L|JL|_J. Moreover, each J is chosen with probability at least 2−b2^-b. If w has tag set J, the event Lt=wL_t=w implies L|J=wL|_J=w. Consequently, for every w∈(Lt)w∈ supp(L_t), Pr[Lt=w]≤Pr[L|J=w]≤2bPr[Wt=w], [L_t=w]≤ [L|_J=w]≤ 2^b [W_t=w], and hence D(Lt∥Wt)≤bD_ KL (L_t~\|~W_t )≤ b. This comparison allows the indices in LtL_t to depend on the final string; it uses secrecy only for each fixed J. Since C is stateless, the inverter continues from WtW_t using only the current string. The KL chain rule (Fact 2.7) and nonnegativity of the did_i therefore give D((Lt,…,L2t)∥(Wt,…,W2t))=D(Lt∥Wt)+∑i=t+12tdi≤b+d.D_ KL ((L_t,…,L_2t)~\|~(W_t,…,W_2t) )=D_ KL (L_t~\|~W_t )+ _i=t+1^2td_i≤ b+d. Let p=Pr[W2t∈]p= [W_2t ] be the inverter’s success probability. The support test accepts L2tL_2t with probability one and W2tW_2t with probability p. Thus data processing (Fact 2.9) gives log(1/p)=D(Ber(1)∥Ber(p))≤b+d<γt2α. (1/p)=D_ KL (Ber(1)~\|~Ber(p) )≤ b+d<γ t^2α. Hence p>2−γt2αp>2^-γ t^2α. Since 2α>12α>1, the inverter’s size 2O(t)2^O(t) is at most 2γt2α2^γ t^2α for all sufficiently large t. This contradicts the assumed security at input length λ=t2λ=t^2 for infinitely many t, proving the second item. ∎ 7.3 Separating Pseudoentropy Notions We now combine the sampler separations with Theorems 3.3 and 5.6 to separate the corresponding pseudoentropy notions. For each notion, the pseudoentropy gap is its pseudoentropy minus the Shannon entropy of the distribution. Corollary 7.3 (Separating insertional from next-block pseudoentropy gaps). Let (fn)n≥1(f_n)_n≥ 1 be a length-preserving one-way function family secure against polynomial-size circuits. For X←UnX← U_n, let L=(fn(X),X)L=(f_n(X),X), viewed as 2n2n binary tokens. For every sufficiently large constant c and all sufficiently large n: 1. The (nc,n−c)(n^c,n^-c) insertional pseudoentropy gap of L is at most 1/n1/n. 2. The (nc,n−c)(n^c,n^-c) next-block pseudoentropy gap of L is at least 12logn 12 n. Proof. Since L includes the uniform preimage, H(L)=nH(L)=n. For the first item, use the fixed insertion order from the proof of Proposition 7.1, and let (L0,…,L2n)(L_0,…,L_2n) be its intermediate strings. Write Ai(w)A_i(w) for the possible successors of w: for i≤ni≤ n, these are w0,w1w0,w1; for i>ni>n, there is only the prescribed insertion of an image bit. A circuit of size T0(n)T_0(n) checks whether z∈Ai(w)z∈ A_i(w), for some polynomial T0T_0. Fix c≥4c≥ 4 large enough that T0(n)≤ncT_0(n)≤ n^c for all sufficiently large n, and set ε=n−c =n^-c. Let I be uniform on [2n][2n] and let Z be an auxiliary variable satisfying the (nc,ε)(n^c, ) indistinguishability condition in Definition 5.3 for this decomposition. Put a=Pr[Z∉AI(LI−1)]a= [Z∉ A_I(L_I-1)]. The test above gives a≤εa≤ . Conditioning on whether this event occurs gives H(Z∣I,LI−1) H(Z I,L_I-1) ≤h(a)+[log|AI(LI−1)|]+2na ≤ h(a)+ [ |A_I(L_I-1)|]+2na ≤h(ε)+12+2nε. ≤ h( )+ 12+2n . Since H(L)=nH(L)=n, the insertional pseudoentropy gap is at most 2nh(ε)+4n2ε2nh( )+4n^2 . Since h(ε)=O(εlog(1/ε))h( )=O( (1/ )), this is O(n2−c)≤1/nO(n^2-c)≤ 1/n for all sufficiently large n, proving the first item. For the second item, suppose that for some c>0c>0 and infinitely many n, the (nc,n−c)(n^c,n^-c) next-block pseudoentropy gap is less than the claimed bound. For all sufficiently large such n, 12logn≤logn−n−c 12 n≤ n-n^-c. Part 2 of Theorem 3.3, with δ=lognδ= n and ϵ=n−cε=n^-c, gives a stateless sequential sampler of size (nc,2n,2,nc)=(n) (n^c,2n,2,n^c)= (n) and KL error at most logn n, contradicting Proposition 7.1. ∎ Corollary 7.4 (Separating insertional from ordinary pseudoentropy gaps). Let (fλ)λ≥1(f_λ)_λ≥ 1 be a length-preserving one-way function family with 2γλα2^γλ^α security against circuits, for constants γ>0γ>0 and 1/2<α<11/2<α<1. For t≥2t≥ 2, let ℓ=2t+⌈log(2t)⌉ =2t+ (2t) . There is a distribution L=LtL=L_t over (0,1ℓ)2t(\0,1\ )^2t, samplable in (t) (t) time, such that for every sufficiently large constant c and all sufficiently large t: 1. The ordinary (tc,t−c)(t^c,t^-c) pseudoentropy gap of L is at most 1/t1/t. 2. The (tc,t−c)(t^c,t^-c) insertional pseudoentropy gap of L is at least γ2t2α γ2t^2α. Proof. Use the distribution constructed in Theorem 7.2. Every output determines the independent uniform X,RX,R, so L is uniform on its support S of size 22t22^2t^2 and H(L)=2t2H(L)=2t^2. Let T0(t)T_0(t) be a polynomial bound on the size of the support test in that proof. Fix c≥4c≥ 4 large enough that T0(t)≤tcT_0(t)≤ t^c for all sufficiently large t, and set ε=t−c =t^-c. If V is (tc,ε)(t^c, )-indistinguishable from L, then a=Pr[V∉]≤εa= [V ]≤ . Conditioning on membership in S gives H(V)≤h(a)+(1−a)2t2+a(2tℓ)≤H(L)+h(ε)+2tℓε,H(V)≤ h(a)+(1-a)2t^2+a(2t )≤ H(L)+h( )+2t , so the ordinary pseudoentropy gap is at most h(ε)+2tℓε=O(t2−c)≤1/th( )+2t =O(t^2-c)≤ 1/t for all sufficiently large t, proving the first item. For the second item, suppose towards contradiction that for some c>0c>0 and infinitely many t, the (tc,t−c)(t^c,t^-c) insertional pseudoentropy gap is less than γ2t2α γ2t^2α. Set δ=γ2t2α+t−cδ= γ2t^2α+t^-c, so the insertional pseudoentropy is at most H(L)+δ−t−cH(L)+δ-t^-c. Part 2 of Theorem 5.6 gives a stateless insertional sampler of size (tc,2t,2ℓ,tc)=2O(t) (t^c,2t,2 ,t^c)=2^O(t) and KL error at most δ. Since 2α>12α>1, for all sufficiently large t we have δ<γt2α−2tδ<γ t^2α-2t, contradicting Theorem 7.2. ∎ 8 Consequences This section explores consequences of our results. In Section 8.1, we derive limitations on sequential generation of cryptographic distributions with limited private state. In Section 8.2, we explain how our results motivate insertion-based models by showing the added expressive power of choosing where to generate each token. 8.1 Cryptographic hardness for sequential sampling Our results show that small-state sequential samplers cannot do many standard cryptographic tasks. We give two examples: (1) a small-state sequential sampler cannot sample a pseudorandom generator distribution, and (2) a small-state sequential sampler cannot sampler fresh public-key ciphertexts even given the public key. This shows that, in order to compute cryptographic primitives, autoregressive models require either external mechanisms or a large state. On the flip-side, we show that sequential samplers cannot invoke public-key steganography. Thus, agents with no pre-shared secrets and a small state cannot covertly communicate with each other. This may be useful for security and alignment, in cases where an autoregressive agent is not trusted. In order to describe consequences of our results to sequential generation of cryptographic primitives, we first derive a general consequence of Theorems 3.3 and 4.3 for negligible sampling error, allowing logarithmic private state. We use n as the asymptotic parameter throughout this subsection. Corollary 8.1 (General consequence for samplers with logarithmic state). Let (W,Y)(W,Y) be jointly distributed and indexed by n. Assume: 1. W has polynomial length, and Y consists of (n) (n) items over a (n) (n)-size alphabet. 2. Y has a noticeable nonuniform next-block pseudoentropy gap given W. Then no sequential sampler C with (n) (n)-size circuits and O(logn)O( n) private bits satisfies D((W,Y)∥(W,C(W)))=(n),D_ KL ((W,Y)~\|~(W,C(W)) )= negl(n), even given W and the entire visible prefix at every step. Proof. Suppose towards contradiction that such a sampler C exists, and write k=O(logn)k=O( n) for its state length. Let N≥1N≥ 1 be the number of tokens of Y, each of length ℓ . Put P=(W,Y)P=(W,Y), Q=(W,C(W))Q=(W,C(W)), and e=D(P∥Q)=(n)e=D_ KL (P~\|~Q )= negl(n). Choose d>0d>0 so that the pseudoentropy gap is at least n−dn^-d for all sufficiently large n, and set ρ=n−d/8ρ=n^-d/8. We remove the private state, control the resulting error, and then apply the stateless characterization. 1. Remove the private state. Apply Theorem 4.3 with accuracy ρ. Its construction allows visible input W: use the same w in every simulated invocation of C, and average the KL bound over W. The resulting stateless sampler D has polynomial size, since 2k,2ℓ,1/ρ,N,|W|2^k,2 ,1/ρ,N,|W| are polynomially bounded. Writing R=(W,D(W))R=(W,D(W)), we have D(Q∥R)≤ρD_ KL (Q~\|~R )≤ρ. 2. Compare with the target distribution. Both C and D use at most r=(n)r= (n) fair random bits over the entire run. Thus every positive conditional output probability, given W=wW=w, is at least 2−r2^-r. Finite KL-divergence gives (P)⊆(Q)⊆(R) supp(P) supp(Q) supp(R). On (Q) supp(Q), put F(w,y)=log(Pr[C(w)=y]/Pr[D(w)=y])F(w,y)= ( [C(w)=y]/ [D(w)=y]), and set F=0F=0 elsewhere. Then |F|≤r|F|≤ r. By Fact 2.5, ν:=Δ(P,Q)=(n)ν:= (P,Q)= negl(n). Since all three distributions have the same W marginal, D(P∥R) D_ KL (P~\|~R ) =e+D(Q∥R)+PF−QF =e+D_ KL (Q~\|~R )+ _PF- _QF ≤e+ρ+2rν=ρ+(n)≤2ρ ≤ e+ρ+2rν=ρ+ negl(n)≤ 2ρ for all sufficiently large n. 3. Apply the pseudoentropy lower bound. Part 1 of Theorem 3.3 allows visible input W: replace (I,Y<I)(I,Y_<I) by (W,I,Y<I)(W,I,Y_<I), condition the entropies on W, and include |W||W| in the polynomial size bound. Set δ=4ρδ=4ρ, σ=ρσ=ρ, η=ρ/Nη=ρ/N, t=nct=n^c, and ϵ=n−cε=n^-c. The denominator in the size bound is polynomial in n independently of c, while the numerator is minncc0,ρnc/N \n^c_0,ρ n^c/N\. Choose c large enough to cover the size of D and ensure n−c≤ρn^-c≤ρ. The pseudoentropy hypothesis then gives (nc,n−c)(n^c,n^-c) next-block pseudoentropy given W at least H(Y∣W)+8ρ−n−c≥H(Y∣W)+4ρH(Y W)+8ρ-n^-c≥ H(Y W)+4ρ. The theorem yields D(P∥R)>4ρ−ρ−N(ρ/N)=2ρD_ KL (P~\|~R )>4ρ-ρ-N(ρ/N)=2ρ, contradicting the preceding bound. ∎ We now describe several corollaries for various cryptographic consequences of the above corollary. Corollary 8.2 (Pseudorandom generation). Let G:0,1k(n)→0,1nG:\0,1\^k(n)→\0,1\^n be a pseudorandom generator secure against nonuniform polynomial-size circuits. No sequential bit sampler C with (n) (n)-size circuits and O(logn)O( n) private bits satisfies D(G(Uk(n))∥C(1n))=(n).D_ KL (G(U_k(n))~\|~C(1^n) )= negl(n). The same holds for any apriori fixed ordering, rather than just left-to-right. A public-key encryption scheme generates a public key pk and a secret key sk. Anyone can encrypt a message using pk; decryption using sk recovers it. IND-CPA security requires indistinguishable encryptions of any two equal-length messages chosen efficiently after seeing pk. Public-key steganography additionally requires encodings to be indistinguishable from a prescribed cover distribution, such as ordinary text. The following results concern this public-key setting, without a pre-shared secret between sender and receiver. Corollary 8.3 (Public-key encryption). Let a polynomial-time public-key encryption scheme have security parameter n. Assume: 1. IND-CPA security against nonuniform polynomial-size circuits and negligible correctness error. 2. Ciphertexts consist of a fixed polynomially bounded number of O(logn)O( n)-bit tokens. For any two distinct equal-length messages of polynomial length, their ciphertext distributions cannot both be sampled with negligible KL-divergence by sequential samplers with (n) (n)-size circuits and O(logn)O( n) private bits. The public key, message, and visible prefix are available at every step; divergence is measured jointly with the public key. Corollary 8.4 (Public-key steganography). Let a public-key steganography scheme run in polynomial time, with security parameter n. Fix two distinct messages of polynomial length. Assume: 1. Negligible decoding error; both encodings consist of the same fixed polynomially bounded number of O(logn)O( n)-bit tokens. 2. Both encodings are computationally indistinguishable from the same cover distribution, jointly with the public key, against nonuniform polynomial-size circuits. The two encoding distributions cannot both be sampled with negligible KL-divergence by sequential samplers with (n) (n)-size circuits and O(logn)O( n) private bits. The public key, message, and visible prefix are available at every step; divergence is measured jointly with the public key. Proof of the three corollaries. For the PRG, we describe it for left-to-right ordering, but the same argument holds for any fixed known ordering up to applying permutation. Put Y=G(Uk(n))Y=G(U_k(n)). For uniform I∈[n]I∈[n] and an independent uniform bit B, the distributions (I,Y<I,YI)(I,Y_<I,Y_I) and (I,Y<I,B)(I,Y_<I,B) are computationally indistinguishable: replacing Y by UnU_n on both sides makes them identical. Thus Y has next-bit pseudoentropy n, whereas H(Y)≤k(n)<nH(Y)≤ k(n)<n. Corollary 8.1 applies with constant visible input. For the remaining claims, let Pb=(W,Yb)P_b=(W,Y^b) be the two encoding distributions, including their common public key or setup W. Write N for the number of tokens and u=2ℓu=2 for the alphabet size, where ℓ is the token length. They are computationally indistinguishable and satisfy Δ(P0,P1)≥1−(n) (P_0,P_1)≥ 1- negl(n). For encryption and steganography, correctness gives the distance bound: appending the secret key preserves distance, since it is independent of the encoding given the public key. Steganographic security gives indistinguishability through the common cover. Suppose towards contradiction that both samplers exist. We distinguish P0P_0 from P1P_1 in three steps. 1. Remove the private state. Put α=1/(100N)α=1/(100N). Apply Theorem 4.3 with KL error α2/4α^2/4, keeping W visible. By Fact 2.5 and the assumed negligible sampling error, the resulting polynomial-size stateless samplers DbD^b satisfy Δ(Pb,Rb)≤α (P_b,R_b)≤α, where Rb=(W,Db(W))R_b=(W,D^b(W)). Hence Δ(R0,R1)≥1/3 (R_0,R_1)≥ 1/3 for all sufficiently large n. 2. Find a differing transition. Replacing the circuits of D0D^0 by those of D1D^1 one at a time gives an index i such that, for X=(W,D0(W)<i)X=(W,D^0(W)_<i) and Ab←Dib(X)A_b← D_i^b(X) with fresh coins, d:=Δ((X,A0),(X,A1))≥1/(3N)d:= ((X,A_0),(X,A_1))≥ 1/(3N). Each hybrid uses the message-00 prefix and a common message-11 suffix, which cannot increase distance. Yet every polynomial-size test distinguishes these pairs with advantage at most 4α+(n)4α+ negl(n): replacing the R0R_0 prefix by the R1R_1 prefix through P0,P1P_0,P_1 before invoking Di1D_i^1 costs 2α+(n)2α+ negl(n), and comparing the two honest prefixes including token i costs the same amount. 3. Test the transition probabilities. On input (x,a)(x,a), draw M=⌈576uN2⌉M= 576uN^2 samples from each Dib(x)D_i^b(x), and accept if a occurs more often in the first batch. Write pbp_b for the true token distribution and p^b p_b for its empirical distribution. By Cauchy–Schwarz, ‖p^b−pb‖1≤u/M≤1/(24N) \| p_b-p_b\|_1≤ u/M≤ 1/(24N). Choosing the larger empirical probability loses at most ‖p^0−p0‖1+‖p^1−p1‖1\| p_0-p_0\|_1+\| p_1-p_1\|_1 relative to the optimal token test. Averaging over X, our test therefore has advantage at least d−1/(12N)≥1/(4N)d-1/(12N)≥ 1/(4N), contradicting the preceding upper bound. The index i is nonuniform advice, and all circuits have polynomial size. The test’s random coins can be fixed by averaging. The transition-testing argument also gives an alternative proof of the PRG claim. Take W constant, N=nN=n, ℓ=1 =1, and u=2u=2, with P0=G(Uk(n))P_0=G(U_k(n)) and P1=UnP_1=U_n. These distributions are computationally indistinguishable, while the support-size bound gives Δ(P0,P1)≥1−2k(n)−n≥1/2. (P_0,P_1)≥ 1-2^k(n)-n≥ 1/2. The sampler for P1P_1 draws independent uniform bits exactly, so a hypothesized sampler for P0P_0 supplies both samplers needed above. With α=1/(100n)α=1/(100n), the first step gives Δ(R0,R1)≥1/2−2α≥1/3 (R_0,R_1)≥ 1/2-2α≥ 1/3 for all sufficiently large n. The remaining two steps, applied to this pair of distributions, yield the same contradiction. As above, any fixed known ordering is handled by permuting the coordinates. ∎ 8.2 Insertional versus Left-to-Right Token Generation Stern et al. [15] introduce an insertion framework and implement it with the Insertion Transformer. Given an input sequence x and the current partial output w, called the canvas, the model assigns a joint distribution p(a,j∣x,w)p(a,j x,w) to the next token a and its insertion position j. The decoder’s hidden states are recomputed after each insertion, so earlier computation leaves no private state beyond the canvas [15, Section 4.5]. To connect this framework to ours, fix the input x and the output length, and consider sampling one insertion per step with fresh coins. This is a sampling version of their framework; their decoding procedures choose maximum-probability actions, either serially or in parallel [15, Section 5]. Allowing arbitrary randomized circuits for these transitions gives exactly our stateless insertional samplers, up to polynomial overhead (Definition 5.1). Indeed, a token and position determine the next canvas; conversely, a one-token extension determines a valid insertion by locating a token whose deletion recovers the old canvas. Restricting every insertion to the rightmost position gives stateless sequential sampling. Our separation now gives a computational motivation for insertion-based models. Assuming one-way functions secure against polynomial-size circuits exist, Proposition 7.1 shows that efficient insertional generation can exactly sample distributions over binary strings that efficient left-to-right generation cannot sample even with small KL error. The advantage already appears with one insertion per step: the generator can produce information needed for later decisions before filling in earlier output positions. Thus choosing where to write can expand what is efficiently generatable without adding private memory or requiring parallel decoding. Indeed, as we have shown in Corollaries 8.2 and 6.1, while PRGs are hard to sample for sequential samplers (for any fixed ordering), even with O(log n) bits of state, this is not the case for insertional samplers. Moreover, the notion of insertional generation does not seem to be captured by the monotone compression notion of [12]. This gives further motivation to explore this model of computation (as well as models that allow deletions or substitutions). Acknowledgements G.A., A.R., and P.L. are supported by the European Research Council (ERC) under the EU’s Horizon 2020 research and innovation programme (Grant agreement No. 101019547) and by a Cariplo CRYPTONOMEX grant. The majority of this work was done while G.A. was a postdoctoral fellow at Bocconi University. G.M. is supported by the European Research Council through an ERC Starting Grant (Grant agreement No. 101077455, ObfusQation) and by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany’s Excellence Strategy - EXC 2092 CASA – 390781972. A.B. and L.T. are supported by an NSERC Discovery Grant. AI use statement The core research ideas are due to the authors. We used large language models, specifically ChatGPT 6 Astra, to assist with writing and revising the manuscript, including proofs, and to help check mathematical arguments for gaps and errors. The authors take full responsibility for the final content of the paper, including its claims, proofs, and references. References [1] R. Agrawal, Y. Chen, T. Horel, and S. P. Vadhan (2019) Unifying computational entropies via kullback-leibler divergence. In CRYPTO 2019, Part I, A. Boldyreva and D. Micciancio (Eds.), LNCS, Vol. 11693, , p. 831–858. External Links: Document Cited by: §1.1, §1.2, Theorem 1.1, §1, §1. [2] K. E. Batcher (1968) Sorting networks and their applications. In Proceedings of the Spring Joint Computer Conference, AFIPS ’68 (Spring), p. 307–314. External Links: Document Cited by: Theorem 2.14. [3] C. L. Canonne, Z. Sun, and A. T. Suresh (2023) Concentration bounds for discrete distribution estimation in kl divergence. In 2023 IEEE International Symposium on Information Theory (ISIT), p. 2093–2098. Cited by: Definition 2.10. [4] T. M. Cover and J. A. Thomas (2006) Elements of information theory. 2nd edition, Wiley-Interscience. Cited by: §2.1, Fact 2.4, Fact 2.5, Definition 2.6, Fact 2.7. [5] L. Fortnow (2026) How does machine learning manage complexity?. External Links: 2604.07233, Link Cited by: §1. [6] I. Haitner, O. Reingold, S. P. Vadhan, and H. Wee (2009) Inaccessible entropy. In 41stACM STOC, M. Mitzenmacher (Ed.), , p. 611–620. External Links: Document Cited by: §1.2. [7] R. Impagliazzo and L. A. Levin (1990) No better ways to generate hard NP instances than picking uniformly at random. In Proceedings of the 31st Annual Symposium on Foundations of Computer Science, Vol. 2, p. 812–821. External Links: Document Cited by: §1. [8] H. Jiang, N. Haghtalab, and L. Chen (2026) Diffusion language models are provably optimal parallel samplers. In The Fourteenth International Conference on Learning Representations, External Links: Link Cited by: §1.2. [9] J. Kim, K. Shah, V. Kontonis, S. M. Kakade, and S. Chen (2025) Train for the worst, plan for the best: understanding token ordering in masked diffusions. In Proceedings of the 42nd International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 267, p. 30749–30768. External Links: Link Cited by: §1.2. [10] L. A. Levin (1986) Average case complete problems. SIAM Journal on Computing 15 (1), p. 285–286. External Links: Document, Link Cited by: §1. [11] C. Lin, A. Jaech, X. Li, M. R. Gormley, and J. Eisner (2021) Limitations of autoregressive models and their alternatives. In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, p. 5147–5173. External Links: Document, Link Cited by: §1.2, §1. [12] N. Mazor, A. Morgan, and R. Pass (2026) Language modeling is monotone compression. External Links: 2610.11031, Link Cited by: §1.2, §8.2. [13] N. Mazor and R. Pass (2024) The non-uniform perebor conjecture for time-bounded kolmogorov complexity is false. In ITCS 2024, V. Guruswami (Ed.), Vol. 287, , p. 80:1–80:20. External Links: Document Cited by: §2.2. [14] J. Mourtada and S. Gaïffas (2022) An improper estimator with optimal excess risk in misspecified density estimation and logistic regression. Journal of Machine Learning Research 23 (31), p. 1–49. External Links: Link Cited by: §2.2. [15] M. Stern, W. Chan, J. Kiros, and J. Uszkoreit (2019) Insertion transformer: flexible sequence generation via insertion operations. In Proceedings of the 36th International Conference on Machine Learning, ICML 2019, 9-15 June 2019, Long Beach, California, USA, K. Chaudhuri and R. Salakhutdinov (Eds.), Proceedings of Machine Learning Research, Vol. 97, p. 5976–5985. External Links: Link Cited by: §1.1, §5, §8.2, §8.2. [16] S. P. Vadhan and C. J. Zheng (2012) Characterizing pseudoentropy and simplifying pseudorandom generator constructions. In Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012, H. J. Karloff and T. Pitassi (Eds.), p. 817–836. External Links: Link, Document Cited by: §1.1, Theorem 1.1, §1, §1, §2.4, Definition 2.19, Definition 2.20, Definition 2.21, Definition 2.22. [17] G. Wu (2023) Theoretical limitations of autoregressive models. Note: Blog post, May 28 External Links: Link Cited by: §1.2, §1, §7.1. [18] C. Yang, C. Zhou, D. Wipf, and Z. Li (2026) On powerful ways to generate: autoregression, diffusion, and beyond. In The Fourteenth International Conference on Learning Representations, External Links: Link Cited by: §1.2.