Paper deep dive
Language Modeling is Monotone Compression
Noam Mazor, Andrew Morgan, Rafael Pass
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 91%
Last extracted: 10/9/2026, 8:13:50 AM
Summary
This paper establishes a theoretical equivalence between Large Language Models (LLMs), modeled as autoregressive next-token predictors, and monotone (order-preserving) compression algorithms. The authors prove that these two concepts are equivalent up to an additive error gap of 2 bits, provided the compression is monotone. They further demonstrate that this monotonicity requirement is necessary if and only if cryptographic one-way functions exist. A key corollary links next-bit pseudoentropy in cryptography to monotone incompressibility.
Entities (8)
Relation Signals (5)
Large Language Models → isequivalentto → Monotone Compression
confidence 95% · Our main result is that LLMs ... are equivalent to monotone ... compression algorithms
Arithmetic Encoding → isusedby → Large Language Models
confidence 95% · good compression schemes can be constructed from good autoregressive models by leveraging arithmetic encoding
Next-Bit Pseudoentropy → isequivalentto → Monotone Incompressibility
confidence 92% · the notion of next-bit pseudoentropy ... is equivalent to monotone incompressibility of the distribution
Monotone Compression → requires → One-Way Functions
confidence 90% · the monotonicity is required for this equivalence to hold if and only if cryptographic (infinitely-often) one-way functions exist
Deletang et al. → demonstrated → LLMs as Compressors
confidence 85% · Deletang et al. (ICLR'24) demonstrate that LLMs can be used as powerful compressors
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:A long-standing hypothesis in artificial intelligence and neuroscience posits that intelligence is closely related to compression: the ability to compress information efficiently intuitively reflects capacities associated with intelligence and learning. Indeed, recent experimental works verify this intuition by showing connections between the capabilities of large language models (LLMs) and their ability as compressors: for instance, Deletang et al. (ICLR'24) demonstrate that LLMs can be used as powerful compressors, and Huang et al. (COLM'24) show that the compression ability of LLMs is highly correlated with their performance on benchmarks for knowledge and reasoning. In this work, we initiate a theoretical study of this connection. Our main result is that LLMs (formally modeled as next-token predictors) are equivalent to monotone (a.k.a. order-preserving) compression algorithms---namely, compression algorithms where the encoding process preserves the ordering of the inputs---in the sense that the one can be constructed from the other while preserving the same error up to an additive gap of 2. We next show that the monotonicity is required for this equivalence to hold if and only if cryptographic (infinitely-often) one-way functions exist. As a direct corollary, we get a cryptographic result of independent interest: the notion of next-bit pseudoentropy (a computational analogue of entropy) of a distribution is equivalent to monotone incompressibility of the distribution. (Previously, it was only known (Haitner et al., ITCS'23) that incompressibility implies next-bit pseudoentropy.)
Tags
Links
- Source: https://arxiv.org/abs/2610.11031v1
- Canonical: https://arxiv.org/abs/2610.11031v1
Trouble viewing inline? Open PDF directly →
Full Text
101,639 characters extracted from source content.
Expand or collapse full text
Language Modeling is Monotone Compression Noam Mazor †thanks: New York University. Research supported by the Simons Foundation. Andrew Morgan †thanks: Cornell Tech. Supported by AFOSR Award FA9550-24-1-0267. Rafael Pass †thanks: Cornell Tech, Technion and Tel-Aviv University. Supported in part by AFOSR Award FA9550-24-1-0267, ISF Award 2338/23 and ERC Advanced Grant KolmoCrypt - 101142322. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the United States Government, the AFOSR, the European Union or the European Research Council Executive Agency. Abstract A long-standing hypothesis in artificial intelligence and neuroscience posits that intelligence is closely related to compression: the ability to compress information efficiently intuitively reflects capacities associated with intelligence and learning. Indeed, recent experimental works verify this intuition by showing connections between the capabilities of large language models (LLMs) and their ability as compressors: for instance, Delétang et al. (ICLR’24) demonstrate that LLMs can be used as powerful compressors, and Huang et al. (COLM’24) show that the compression ability of LLMs is highly correlated with their performance on benchmarks for knowledge and reasoning. In this work, we initiate a theoretical study of this connection. Our main result is that LLMs (formally modeled as next-token predictors) are equivalent to monotone (a.k.a. order-preserving) compression algorithms—namely, compression algorithms where the encoding process preserves the ordering of the inputs—in the sense that the one can be constructed from the other while preserving the same error up to an additive gap of 2. We next show that the monotonicity is required for this equivalence to hold if and only if cryptographic (infinitely-often) one-way functions exist. As a direct corollary, we get a cryptographic result of independent interest: the notion of next-bit pseudoentropy (a computational analogue of entropy) of a distribution is equivalent to monotone incompressibility of the distribution. (Previously, it was only known (Haitner et al., ITCS’23) that incompressibility implies next-bit pseudoentropy.) 1 Introduction A central question in the study of artificial intelligence is: can “intelligence” be defined? Turing’s classic “imitation game” [20], which posits that a machine should be considered intelligent if a human is unable to distinguish it from another human given a transcript of a conversation, gives an elegant answer, but one that depends on human judgment. Towards a more mathematical and quantitative definition of intelligence, the work of Shannon [17, 16] laid the groundwork for a line of research suggesting that learning or understanding something is closely related to being able to process and describe it in a simple way [11, 7]—that is, intelligence, intuitively, corresponds to the ability to succinctly compress information. Recently, autoregressive models such as large language models (LLMs) have made this suggested connection more explicit. Such models are trained on data sampled from a distribution D to predict the next token in a sequence: given a prefix of tokens t1,t2,…,tkt_1,t_2,…,t_k, they output a probability distribution that is supposed to approximate the conditional distribution tk+1∣t1,…,tk\t_k+1 t_1,…,t_k\. A model is considered “good” if its loss, measured as the expected negative log-likelihood on data drawn from D, or equivalently, the cross-entropy between D and the model’s predicted distribution, is close to minimal. It is well known that good compression schemes can be constructed from good autoregressive models by leveraging arithmetic encoding [17, 3]: arithmetic encoding is known to produce a near-optimal compression rate for a given distribution, so, intuitively, applying it to the distribution of a model’s autoregressively sampled outputs should likewise give a near-optimal compression rate for D if the model is good. This was first empirically studied using neural network predictors [14] (see also, e.g., [15, 12, 13]), but subsequently has been applied to LLMs, with recent research suggesting not only that compression rivaling state-of-the-art algorithms can be constructed from LLMs (e.g., [1, 23, 19]), but also that compression ability of LLMs is highly correlated with performance on benchmarks measuring knowledge, reasoning, and coding abilities [9]. Given that compression can be constructed from LLMs, a natural question is whether the converse may also hold—that is, whether one can construct accurate next-token predictors from good compression algorithms. This idea was originally empirically explored in the work of [2] constructing models for text categorization from compression algorithms, and is of particular interest because it would imply an intuitive equivalence between predictive modeling and compression. More recently, Delétang et al. [1] suggest and evaluate a heuristic construction of an autoregressive next-token prediction model from compression, leading them to their titular assertion that “language modeling is compression”. However, when one compares the results in each direction of this proposed empirical equivalence, there is a clear difference in terms of the empirical quality of results: compression algorithms constructed from LLMs exhibit competitive compression ratios, whereas works constructing autoregressive models from compression exhibit relatively poor predictive ability compared to state-of-art LLMs. While there are certainly plausible intuitive explanations for this disparity—for instance, the difference in computational power between state-of-the-art LLMs and state-of-the-art compression algorithms—it nonetheless raises a fundamental question: Is there a formal connection between autoregressive models (i.e., LLMs) and compression? In this work, we address this question, initiating a theoretical study of the intuitive connection between autoregressive models and compression. Our main result shows that, intuitively, “good” autoregressive models are equivalent to “good” monotone compression schemes. (Furthermore, this equivalence holds quantitatively up to a constant additive accuracy gap between the cross-entropy loss of the autoregressive model and the compression loss of the monotone compressor.) We additionally show that the monotonicity condition is necessary if and only if cryptographic (infinitely-often) one-way function (ioOWFs) exist; this explains the disparity observed above. 1.1 Our Results We formalize LLMs as autoregressive models which, given a string of tokens as a prefix, output a probability distribution over possible next tokens. We consider a setting where the objective of an LLM is, given a “training” distribution D (e.g., random files selected from the Internet), to learn a model ℳM that minimizes the expected negative log-likelihood t←D[−∑i∈[len(t)]logℳ(ti|t<i)]E_t← D[- _i∈[len(t)] (t_i\;|\;t_<i)], which is in fact equivalent to the cross-entropy H(D,Dℳ)=H(D)+KL(D||Dℳ)H(D,D_M)=H(D)+KL(D\;||\;D_M) (where H(D)H(D) is Shannon entropy and KLKL represents Kullback-Leibler divergence) between D and the distribution DℳD_M of outputs autoregressively sampled from ℳM. As the minimum achievable cross-entropy is H(D)H(D), we say that a model ℳM is δ-optimal with respect to D if its cross-entropy is at most H(D)+δH(D)+δ. A compression scheme is specified by a pair of algorithms (,)( Enc, Dec) where Enc encodes an input from a distribution D into its compressed form (which we assume throughout to be binary), and Dec is the respective inverse. We assume throughout that Enc is prefix-free with respect to D: for any x in the support of D, no codeword for a different input is a prefix of (x) Enc(x). The goal of compression is to minimize the expected compression length x←D[len((x))]E_x← D[len( Enc(x))]; by Shannon’s source coding theorem [17], this is lower-bounded by H(D)H(D), and so we say that compression is δ-optimal with respect to D if its expected compression length is at most H(D)+δH(D)+δ (in other words, the compression loss is at most δ). Finally, compression is monotone if it preserves a lexicographic ordering ≺ over inputs, induced by an efficiently computable ordering of the tokens: that is, given inputs x,yx,y, (x)<(y) Enc(x)< Enc(y) if and only if x≺yx y, where << is the lexicographic ordering of binary codewords. For all of our results, we require autoregressive models and compression schemes to be efficiently computable: encoding, decoding, and computing next-token probabilities must run in polynomial time. Furthermore, when discussing cross-entropy and expected compression length, we consider them over complete samples from the distribution D. Autoregressive modeling is monotone compression. We first present our main result, showing the equivalence between autoregressive modeling and monotone compression: Theorem 1.1 (Theorem 3.2 and Theorem 3.3, informal). Given a distribution D consisting of strings of tokens from an alphabet Σ , for any δ: • Given an efficiently computable δ-optimal autoregressive model for D, one can construct an efficiently computable monotone compression scheme which is (δ+2)(δ+2)-optimal with respect to D.11 1 The additive gap of 2 in this result, and later Corollary 1.3, arises from the use of arithmetic encoding in the transformation from autoregressive modeling to compression; some additive loss is inevitable as no compression scheme can achieve zero compression loss without strict conditions on the distribution D. • Given an efficiently computable monotone compression scheme which is δ-optimal with respect to D, one can construct a δ-optimal autoregressive model for D. In other words, autoregressive models and monotone compressors are equivalent up to an additive gap of 2; we additionally demonstrate this equivalence through an explicit efficient transformation in both directions. The monotonicity requirement. While the added condition of monotonicity may seem surprising at first glance, it sheds light on the discrepancy we noted earlier between empirical results converting autoregressive models to compression and vice versa. Known constructions of compression from autoregressive models use arithmetic encoding, which is monotone; meanwhile, as monotonicity is not necessarily inherent in compression algorithms, it explains why constructions of autoregressive models from compression tend to have worse empirical performance. Indeed, our next result formally demonstrates that the requirement of monotonicity is not merely coincidental: given a fundamental and widely conjectured cryptographic assumption, the existence of infinitely-often one-way functions (ioOWFs)22 2 Infinitely-often OWFs are a relaxation of the standard concept of a OWF: namely, OWFs which are only uninvertible for infinitely many input lengths n rather than all sufficiently large n., monotonicity is necessary for any strong autoregressive model-compression equivalence: Theorem 1.2 (Theorem 4.3 and Theorem 4.8, informal). The following are true: • If one-way functions (respectively, infinitely-often one-way functions) exist, then there exists an efficiently samplable distribution family D=DnD=\D_n\ and a non-monotone compression scheme (,)( Enc, Dec) with efficient encoding and decoding whose expected encoding length on DnD_n is exactly H(Dn)H(D_n), but for which every efficiently computable autoregressive model has excess cross-entropy loss at least linear in the output length. This lower bound holds for all sufficiently large lengths (respectively, infinitely many lengths). • If infinitely-often one-way functions do not exist, then, given a δ-optimal compression scheme (,)( Enc, Dec) with efficient encoding and decoding for an efficiently samplable distribution family D=DnD=\D_n\, one can construct an efficiently computable autoregressive model which is statistically close to a δ-optimal autoregressive model for D. That is, given ioOWFs, one could not hope to prove Theorem 1.1, or even any weaker analogue with an additive gap constant sublinear in the length of a sample from the distribution D, without requiring monotonic compression. Interestingly, the same is not true if ioOWFs do not exist: in that case, using a classic result from [10], we show that one can drop the monotonicity condition from Theorem 1.1 at a cost of a small amount of statistical error. Thus, in essence, whether modeling is equivalent to monotone compression or (approximately) equivalent to all compression depends on the truth of this assumption; that said, one-way functions (which in turn imply ioOWFs) are widely conjectured to exist, implying the former equivalence and a corresponding separation between monotone and non-monotone compression. Pseudoentropy and incompressibility. Lastly, we show a corollary of Theorem 1.1 that provides interesting implications to cryptography. There has been a considerable line of research relating the compressibility of a distribution to its pseudoentropy [6], a computational analogue of entropy. In particular, Haitner et al. [5] demonstrate that, if a family of distributions D is incompressible [22] to some length k(n)k(n), then it has next-bit pseudoentropy at least (k(n)−2)(k(n)-2)—that is, the total pseudoentropy of the conditional next-bit distributions of each bit of D is at least (k(n)−2)(k(n)-2).33 3 We note that [8] demonstrates an analogue of this result for uniform algorithms; we, however, focus on non-uniform algorithms, following [5]. However, the converse is false: if one-way functions exist, then pseudoentropy cannot imply incompressibility. As our final result, we obtain a tight version of this characterization by combining Theorem 1.1 with a corollary from [21] to show that, similarly to the equivalence between autoregressive models and compression, both directions are true if we specifically require monotone incompressibility, or inability to be compressed through specifically monotone schemes: Corollary 1.3 (Corollary 5.3 and Corollary 5.4, informal). Given a family of distributions D, the following are equivalent for any function k(n)k(n) (to within an additive gap of 2): • D cannot be efficiently monotonically compressed to length k(n)k(n). • D has next-bit pseudoentropy at least k(n)k(n). 1.2 Technical Overview Monotone Compression from Autoregressive Models. To construct monotone compression for a distribution D from an autoregressive model ℳM, we can use arithmetic encoding relative to the model’s output distribution DℳD_M. As discussed above, the expected negative log-likelihood used to train ℳM is exactly the cross-entropy H(D,Dℳ)H(D,D_M): multiplying the next-token probabilities gives the probability of a complete output, and taking its negative logarithm gives the sum of the next-token losses. Arithmetic encoding connects this same quantity to compression by assigning each output x a codeword (x) Enc(x) such that len((x))≤−logDℳ(x)+2.len( Enc(x))≤- D_M(x)+2. Since this bound holds for each x, we can average it over the correct distribution D, even though the code is constructed using the approximation given by DℳD_M: x←D[len((x))]≤x←D[−logDℳ(x)]+2=H(D,Dℳ)+2.E_x← D[len( Enc(x))] _x← D[- D_M(x)]+2=H(D,D_M)+2. Furthermore, as mentioned above, KL(D||Dℳ)=x←D[logD(x)Dℳ(x)]=H(D,Dℳ)−H(D),KL(D\;||\;D_M)=E_x← D [ D(x)D_M(x) ]=H(D,D_M)-H(D), so x←D[len((x))]≤H(D)+KL(D||Dℳ)+2.E_x← D[len( Enc(x))]≤ H(D)+KL(D\;||\;D_M)+2. In other words, the expected compression length is at most the entropy of D, plus the same KL-divergence that measures the model’s excess prediction loss, plus the overhead of 2 bits from arithmetic encoding. δ-optimality of ℳM thus implies (δ+2)(δ+2)-optimality of the compression scheme. Arithmetic encoding is monotone by definition: it arranges the probability intervals associated with outputs in lexicographic order and assigns codewords in that same order. Efficiency of arithmetic encoding, however, requires that the cumulative distribution function (CDF) of the model’s output distribution can be computed efficiently. For a polynomial-size alphabet, this is possible using a standard recursive algorithm (see, e.g., [5, 1]). Specifically, to determine the probability Prx←Dℳ[x≺y] _x← D_M[x y] of an output being lexicographically smaller than a given string y, one can decompose this into Prx←Dℳ[x≺y]=∑i(Prx←Dm[x<i=y<i]Prx←Dm[xi≺yi∣x<i=y<i]) _x← D_M[x y]= _i ( _x← D_m[x_<i=y_<i] _x← D_m[x_i y_i x_<i=y_<i] ) =∑i(Prx←Dm[x<i=y<i]∑z≺yiPrx←Dm[xi=z∣x<i=y<i])= _i ( _x← D_m[x_<i=y_<i] _z y_i _x← D_m[x_i=z x_<i=y_<i] ) and thus recursively determine the overall probability by, for each possible prefix length where x might first diverge from y, multiplying the probability of matching the preceding prefix by the conditional probability of choosing a smaller token at that position, and summing these disjoint possibilities. Adding Dℳ(y)D_M(y) then gives the CDF Prx←Dℳ[x⪯y] _x← D_M[x y]. This process requires only polynomially many next-token probability evaluations; thus, as long as the next-token probabilities of ℳM are efficiently computable, arithmetic encoding with respect to DℳD_M is as well. Autoregressive Models From Monotone Compression. For the converse, given a prefix-free, monotone encoding Enc over a distribution D, we demonstrate a construction of an autoregressive model ℳM whose output distribution satisfies Dℳ(x)≥2−len((x))D_M(x)≥ 2^-len( Enc(x)) for every x in the support of D. This probability bound suffices because taking negative logarithms gives −logDℳ(x)≤len((x)).- D_M(x) ( Enc(x)). Thus, the model’s loss on each output is at most its encoding length, and taking the expectation over D gives a bound on the cross-entropy: H(D,Dℳ)=x←D[−logDℳ(x)]≤x←D[len((x))].H(D,D_M)=E_x← D[- D_M(x)] _x← D[len( Enc(x))]. In particular, if Enc is δ-optimal, the right-hand side is at most H(D)+δH(D)+δ, so ℳM is also δ-optimal. We proceed in two steps. First, we construct an efficient monotone sampler Sample for the desired output distribution which, at a high level, samples outputs by decoding uniformly random bits. Let ℓ be a polynomial upper bound44 4 For any Enc, there must exist such an ℓ due to efficiency; here, we make the simplifying assumption that ℓ is known a priori, but we show in the complete proof that this assumption can be discarded. on the output length of Enc: Sample will draw a uniformly random string c∈0,1ℓc∈\0,1\ , examine the prefixes of c in increasing order of length, and decode the first one that is a valid codeword. Since Enc is monotone, we can always decode efficiently through binary search, and, as there are only polynomially many prefixes to examine, this step is efficient. If no prefix of c is a valid codeword, Sample instead returns the smallest input x with (x)≤c Enc(x)≤ c (or the smallest possible input x if no such x exists); monotonicity of Enc allows us to again find such an input efficiently by binary search. We observe that this process assigns an output to every random string and, importantly, is weakly monotone: if c<c′c<c , then (c)⪯(c′) Sample(c) Sample(c ). Next, we construct an efficiently computable autoregressive model ℳM whose output distribution DℳD_M is exactly the distribution of (c) Sample(c) when c←0,1ℓc←\0,1\ is uniform. To show that ℳM satisfies the necessary probability bound, fix any x in the support of D; whenever the random string c begins with (x) Enc(x), the sampler must return exactly x, since prefix-freeness ensures that no shorter prefix of c can be a valid codeword. This event has probability exactly 2−len((x))2^-len( Enc(x)), so Dℳ(x)=Prc←0,1ℓ[(c)=x]≥2−len((x)).D_M(x)= _c←\0,1\ [ Sample(c)=x]≥ 2^-len( Enc(x)). Thus, by our original argument, ℳM is δ-optimal as long as Enc is. However, we must still show that ℳM’s next-token probabilities can be computed efficiently. Towards this, the key observation is that it suffices to show that the CDF of DℳD_M can be computed efficiently, which, leveraging weak monotonicity of Sample, can once again be done by binary search. Specifically, fix an output y and identify the ℓ -bit random strings with the integers 0,…,2ℓ−10,…,2 -1. By weak monotonicity, the random strings c satisfying (c)⪯y Sample(c) y correspond to a subset c<k(y)c<k(y) of this set, and we can determine k(y)k(y) using binary search by finding the smallest c with (c)≻y Sample(c) y. Since the corresponding subset contains k(y)k(y) elements, each of which is chosen with probability exactly 2−ℓ2^- , the CDF is exactly F(y):=Prx←Dℳ[x⪯y]=k(y)2ℓ.F(y):= _x← D_M[x y]= k(y)2 . Finally, to recover next-token probabilities from the CDF, we use the standard observation that strings sharing a prefix form a contiguous interval in a lexicographic ordering; thus, prefix probabilities can be computed by subtracting two CDF values (see Figure 1 for a visualization), and next-token probabilities can be computed by taking ratios of prefix probabilities. We have thus demonstrated that the model ℳM we constructed has both efficiently computable next-token probabilities and δ-optimality with respect to D, as desired. Outputs (lexicographic order)Random strings c (binary order)(c) Sample(c)t<i||σ1…t_<i|| _1…t<i||σ2…t_<i|| _2…t<i||σ3…t_<i|| _3…outputs beginningwith prefix t<it_<istrings c producing prefix t<it_<iendpoints found by binary search Figure 1: Computing prefix probabilities from a monotone sampler. Outputs beginning with a fixed prefix t<it_<i form an interval in lexicographic order (horizontal band). The labels t<i||σ1…t_<i|| _1…, t<i||σ2…t_<i|| _2…, and t<i||σ3…t_<i|| _3… illustrate outputs with this common prefix, where σ1≺σ2≺σ3 _1 _2 _3 are possible next tokens. By weak monotonicity of Sample, the random strings producing these outputs also form an interval (highlighted on the horizontal axis). Two binary searches locate its endpoints. The prefix probability is the number of seeds in this interval divided by 2ℓ2 . The staircase is schematic; the vertical axis represents output order. Comparison with [1]. Delétang et al. [1] present a heuristic construction of next-token prediction from compression; however, in contrast to our construction, which “looks ahead” and retrieves next-token probabilities relative to the complete output distribution reconstructed from the compression, they instead compute next-token probabilities myopically by examining the difference in length between the compression of the prefix and the compression of the prefix with each possible subsequent token appended.55 5 That is, given some partial output x, they assign each possible next token σ a weight of 2−(len((x||σ))−len((x)))2^-(len( Enc(x||σ))-len( Enc(x))) and sample according to the distribution over all possible next tokens σ with the respective weights. The advantage of this construction is that, unlike ours, monotonicity of the compression scheme Enc is not needed. However (as the authors themselves acknowledge in their work), because their approach approximates the next-token distribution using partial compressions every time they sample a next token, it risks introducing a constant amount of error to the sampling process every time a token is generated, whereas, with our construction, using a consistent distribution over complete outputs allows us to sample all tokens relative to that output distribution and only incur the error once.66 6 As an illustrative example, consider a binary distribution D with constant next-token probabilities skewed away from powers of 2: e.g., every token is drawn as 0 with probability 0.6 and 1 with probability 0.4. Since every token is drawn with probabilities weighted by powers of 2 in the sampling method of [1], this introduces a constant amount of KL-divergence to the respective next-token distribution every time a token is sampled; as these errors are additive by the chain rule, the resulting cross-entropy loss is linear in the output length. 2 Definitions Let ℕ=1,2,3,…N=\1,2,3,…\ and [n]=m∈ℕ∣m≤n=1,2,…,n[n]=\m m≤ n\=\1,2,…,n\. For some symbol σ in an alphabet Σ , take σnσ^n to be the string consisting of n copies of σ. Let 1P1_P be the indicator function of a logical statement P, defined as being 1 when P is true and 0 otherwise. Given a set X, we define Δ(X) (X) to be the set of probability distributions over elements in X. Given some string x∈Σ∗x∈ ^* over a vocabulary Σ , we will denote substrings with notation such as x≤ix_≤ i (representing the prefix consisting of the first i symbols), and the length of a string x∈Σ∗x∈ ^* by len(x)len(x). We use similar notation to denote, e.g., Σ≤n=⋃i=0nΣi ^≤ n= _i=0^n ^i as the set of strings of tokens from an alphabet Σ with at most length n. We say a statement is true for “sufficiently large n∈ℕn ” if there exists N∈ℕN such that the statement holds for all n≥Nn≥ N. We shall call a function ϵ(⋅)ε(·) negligible if, for any polynomial p(⋅)p(·), ϵ(n)<1/p(n)ε(n)<1/p(n) for sufficiently large n∈Nn∈ N; conversely, a function is non-negligible or polynomial if the above is not true. In this work, we assume that algorithms are non-uniform: to enable computation for arbitrary input sizes parameterized by some n∈ℕn , they receive an additional “advice” string of size polynomial in n (which, unless otherwise specified, can be taken to be the string 1n1^n of n ones to specify n). We refer to a non-uniform algorithm as efficient if its running time is polynomial in the parameter n. We define an oracle-aided algorithm Π ^O as an algorithm Π that is given access to another algorithm O as a black box, and may make many calls to its oracle O on potentially many different inputs before determining its own output. We say that such an algorithm is efficient if its running time (excepting calls made to O) and the number of calls it makes to the oracle O are both polynomial in its input size—that is, as long as O is efficient, the total running time of Π , including that taken by calls made to O, is polynomial in its input size. Unless otherwise indicated, any logarithm denoted by log will be base 2 (as opposed to the base-e natural logarithm ln ). Given a discrete distribution D, we denote by sup(D) (D) its support and define the (Shannon) entropy of D to be the quantity H(D)=∑x∈sup(D)−D(x)logD(x)H(D)= _x∈ (D)-D(x) D(x) Given two discrete distributions D,D′D,D , we denote the statistical distance (or total variation distance) between D and D′D by Δ(D,D′) (D,D ) and the Kullback-Leibler (KL) divergence between the two distributions by KL(D||D′)=∑x∈sup(D)D(x)logD(x)D′(x)KL(D||D )= _x∈ (D)D(x) D(x)D (x) 2.1 Compression We consider the problem of (lossless) data compression from a particular source distribution, where the goal is to achieve a uniquely decodable encoding over samples from the source distribution with the property that the expected encoding length of a sample drawn from the distribution is as small as possible. Formally: Definition 2.1 ([4, 18]). Given finite families of alphabets Σ=Σnn∈ℕ =\ _n\_n and Σ′=Σn′n∈ℕ =\ _n\_n where |Σn|| _n| and |Σn′|| _n| are polynomial in n, functions m(⋅),ℓ(⋅)m(·), (·) where m(n)m(n) is polynomial in n, and an ensemble of distributions =Dnn∈ℕD=\D_n\_n , where sup(Dn)⊆Σnm(n) (D_n) _n^m(n), we say that a family of injective functions =nn∈ℕ Enc=\ Enc_n\_n is an encoding, or compression scheme77 7 Oftentimes the term “compression” is used to indicate strictly prefix-free encodings; however, we consider only prefix-free encodings anyway in our results.. Enc compresses D to length ℓ(⋅) (·) if, for any n∈ℕn , n:Σnm(n)→Σn′∗ Enc_n: _n^m(n)→ *_n is such that x←Dn[len(n(x))]≤ℓ(n)E_x← D_n[len( Enc_n(x))]≤ (n) Unless otherwise specified, we shall assume that the output of the compression is binary (Σn′=0,1 _n=\0,1\ for all n∈ℕn ). We also define some useful properties of compression functions: Definition 2.2 (Properties of compression). Given finite alphabets Σ and Σ′ , let :Σ∗→Σ′∗ Enc: ^*→ * be a function defined with respect to some distribution D with sup(D)⊆Σ∗ (D) ^*. We refer to Enc as prefix-free if there do not exist elements x≠yx≠ y and i∈ℕi such that x∈Σ∗x∈ ^*, y∈sup(D)y∈ (D), and (x)=((y))<i Enc(x)=( Enc(y))_<i (i.e., (x) Enc(x) is a prefix of (y) Enc(y); we note, however, that this definition does allow an encoding of y∈sup(D)y∈ (D) to be a prefix of an encoding of x∉sup(D)x ∈ (D)). We refer to Enc as monotone if there exist efficiently computable orderings ≺Σ _ over Σ and ≺Σ′ _ over Σ′ such that, for any x,y∈Σ∗x,y∈ ^*, x≺Σ∗yx _ ^*y if and only if (x)≺Σ′∗(y) Enc(x) _ * Enc(y), where ≺Σ∗ _ ^* is the lexicographic ordering88 8 i.e., x≺Σ∗yx _ ^*y when there exists i∈ℕi for which x<i=y<ix_<i=y_<i and either len(y)>len(x)=i−1len(y)>len(x)=i-1 or xi≺Σyix_i _ y_i. induced by ≺Σ _ on Σ∗ ^* and respectively for ≺Σ′∗ _ *. We consider any of the above properties to apply to a family of functions =nn∈ℕ Enc=\ Enc_n\_n as defined in Definition 2.1, where n Enc_n is defined with respect to a distribution DnD_n for which sup(Dn)⊆Σnm(n) (D_n) _n^m(n), if they apply to n Enc_n and DnD_n for each n∈ℕn . Furthermore, we say that such a family of functions has efficient encoding if there exists a polynomial p(⋅)p(·) such that n Enc_n runs in time at most p(n)p(n) for any n∈ℕn , and efficient decoding if there exists a polynomial p′(⋅)p (·) and a function family =nn∈ℕ Dec=\ Dec_n\_n such that, for each n∈ℕn , n Dec_n computes the inverse n−1(c) Enc_n^-1(c) of n Enc_n for any codeword in its image (or returns ⊥ if the input is not in the image) and additionally runs in time at most p′(n)p (n). We also note the following useful fact about efficient encoding and decoding: Fact 2.3. Any monotone and efficiently encodable family of encodings =nn∈ℕ Enc=\ Enc_n\_n is also efficiently decodable. Proof. Consider a decoding algorithm that, given a codeword, performs binary search over the possible inputs in Σnm(n) _n^m(n). This is possible due to monotonicity—it can be determined whether the correct decoding is lower or higher than a given input by comparing the respective codewords. Additionally, since there are |Σn|m(n)| _n|^m(n) possible inputs in Σnm(n) _n^m(n), binary search requires at most O(m(n)log|Σn|)O(m(n) | _n|) iterations of n Enc_n. Since by definition m(n)m(n) and |Σn|| _n| are polynomial in n, and since Enc is itself efficient, this decoding process must likewise be efficient. ∎ We shall generally restrict our focus to monotone and prefix-free encodings. Shannon’s source coding theorem [17] implies a lower bound for the expected length of any prefix-free encoding Enc over a source distribution D in terms of its Shannon entropy H(D)H(D): Corollary 2.4 ([17]). Given finite alphabets Σ and Σ′ and distribution D over Σ , let ℓ∗(D) ^*(D) be the minimal expected length x←D[len((x))]E_x← D[len( Enc(x))] over any prefix-free encoding :Σ→Σ′ Enc: → . Then: H(D)log|Σ′|≤ℓ∗(D) H(D) | |≤ ^*(D) For binary encodings (Σ′=0,1 =\0,1\), this bound simply becomes ℓ∗(D)≥H(D) ^*(D)≥ H(D). 2.1.1 Arithmetic Encoding Towards constructing compression with the properties that are necessary for our results, we start with the classical notion of arithmetic encoding, which essentially maps each element of a distribution D to a binary representation of the element’s cumulative distribution function with respect to D with sufficient precision to be unique. Definition 2.5 (Arithmetic encoding [17, 3]). Let D be a discrete distribution and let ≺ be a total order over sup(D) (D). Let F:sup(D)→[0,1]F: (D)→[0,1] by F(x)=(∑a≺xD(a))+1/2⋅D(x)F(x)=( _a xD(a))+1/2· D(x). Then the arithmetic encoding :sup(D)→0,1∗ Enc: (D)→\0,1\^* is defined such that, for x∈sup(D)x∈ (D), (x) Enc(x) is the first (⌈−logD(x)⌉+1)( - D(x) +1) bits of F(x)F(x). We note the following fact that shows that, when restricted to the support of the distribution D, arithmetic encoding is prefix-free and monotone, and additionally provides near-optimal data compression: Fact 2.6 (Properties of arithmetic encoding, lemma 2.8 in [18]). For every distribution family =Dnn∈ℕD=\D_n\_n and ordering ≺ over the corresponding input alphabet Σn _n, the functions n Enc_n given by applying Definition 2.5 to DnD_n and ≺ (for any n∈ℕn ) are one-to-one and monotone, and the scheme =nn∈ℕ Enc=\ Enc_n\_n is prefix-free and compresses D to length H(Dn)+2H(D_n)+2. This is not quite what we need to show monotonicity and prefix-freeness with respect to the entire input space Σnm(n) ^m(n)_n—in fact, it is not necessarily clear how to define Enc outside the support of D since (⌈−logDn(x)⌉+1)( - D_n(x) +1) (the number of bits in n(x) Enc_n(x)) is undefined when Dn(x)=0D_n(x)=0. However, we show that one can transform arithmetic encoding to guarantee the stronger versions of these properties, and additionally show that arithmetic encoding, including our augmented version, is efficiently computable as long as the cumulative distribution function (CDF) ∑a⪯xDn(a) _a xD_n(a) is likewise efficiently computable for any x∈Σnm(n)x∈ ^m(n)_n: Claim 2.7. For any alphabet Σnn∈ℕ\ _n\_n , any distribution family =Dnn∈ℕD=\D_n\_n where sup(Dn)⊆Σnm(n) (D_n) _n^m(n) and −log(Dn(x))≤ℓ(n)- (D_n(x))≤ (n) for any x∈sup(Dn)x∈ (D_n) and some polynomial ℓ(⋅) (·), and any ordering ≺n _n over Σn _n, if the cumulative distribution function ∑a⪯xDn(a) _a xD_n(a) can be efficiently computed for any x∈Σnm(n)x∈ ^m(n)_n, then there exists a prefix-free, monotone, and efficiently computable encoding =nn∈ℕ Enc=\ Enc_n\_n that additionally compresses D to length H(Dn)+2H(D_n)+2. Proof. Let n′ Enc _n be the arithmetic encoding given in Definition 2.5. Define n(x)=n′(x) Enc_n(x)= Enc _n(x) for all x∈sup(Dn)x∈ (D_n); for x∈Σnm(n)∖sup(Dn)x∈ ^m(n)_n (D_n), let n(x) Enc_n(x) be the first (ℓ(n)+2)( (n)+2) bits of the CDF ∑a≺xD(a) _a xD(a) (or 1ℓ(n)+21 (n)+2 if the CDF is 1, i.e., x≻yx y for all y∈sup(Dn)y∈ (D_n)) with the binary representation of x ordered by ≺n _n appended. Prefix-freeness holds because, by Fact 2.6, n Enc_n is prefix-free when restricted to sup(Dn) (D_n), and furthermore there cannot exist x∈Σnm(n)∖sup(Dn)x∈ ^m(n)_n (D_n) and y∈sup(Dn)y∈ (D_n) where n(x) Enc_n(x) is a prefix of n(y) Enc_n(y) because, by definition, n(x) Enc_n(x) must be strictly longer than n(y) Enc_n(y). To show monotonicity, consider some x,y∈Σnm(n)x,y∈ ^m(n)_n with x≺nyx _ny. If x,y∈sup(Dn)x,y∈ (D_n), we conclude that n(x)<n(y) Enc_n(x)< Enc_n(y) by Fact 2.6. If the first (ℓ(n)+2)( (n)+2) bits of n(x) Enc_n(x) and n(y) Enc_n(y) are identical (which can only happen when x,y∉sup(Dn)x,y ∈ (D_n) and furthermore there is no z∈Dnz∈ D_n with x≺nz≺nyx _nz _ny), we conclude that n(x)<n(y) Enc_n(x)< Enc_n(y) by the definition of n Enc_n (since the following part of each of n(x) Enc_n(x) and n(y) Enc_n(y) is the binary representation of x and y, respectively). Otherwise, it must be the case that x and y do not have the same CDF with respect to DnD_n, and so we conclude that n(x)<n(y) Enc_n(x)< Enc_n(y) because the respective prefixes of the encodings (which are prefixes of the respective CDFs) must be strictly ordered. To show that n Enc_n can be efficiently computed: if ∑a⪯xDn(a) _a xD_n(a) can be efficiently computed, then so can Dn(x)=∑a⪯xDn(a)−∑a⪯x−Dn(a)D_n(x)= _a xD_n(a)- _a x^-D_n(a) (where x−x^- is the predecessor of x under ≺ ) and consequently ∑a≺xDn(a)=∑a⪯xDn(a)−D(x) _a xD_n(a)= _a xD_n(a)-D(x) and thus n′(x) Enc _n(x) must be efficiently computable as well, which demonstrates efficient computability of n Enc_n for x∈sup(Dn)x∈ (D_n). For x∉sup(Dn)x ∈ (D_n), it suffices that the CDF ∑a≺xD(a) _a xD(a) is efficiently computable. Finally, we remark that the encoding length of every x∈sup(Dn)x∈ (D_n) is identical between n′ Enc _n and n Enc_n; therefore, the expected encoding length with respect to DnD_n must remain unchanged. ∎ Remark. We note the assumption in the above claim that we have an effective a priori bound of p(n)+1p(n)+1 on the length of the arithmetic encoding n′(x) Enc _n(x). Without such a bound, one can still prove a similar result by truncating the arithmetic encoding to a suitably large polynomial length ℓ(n) (n) and appending the binary representation of x to any truncated encoding, even for x∈sup(Dn)x∈ (D_n) with non-zero Dn(x)D_n(x). Since any x∈sup(Dn)x∈ (D_n) must have Dn(x)≤2−ℓ(n)D_n(x)≤ 2^- (n) for its encoding to be affected, and there are at most |Σn|m(n)| _n|^m(n) possible codewords, as long as ℓ(n) (n) is selected so that 2ℓ(n)≫|Σn|m(n)2 (n) | _n|^m(n), this will lose at most an exponentially small fraction of a bit in the output length. We, however, choose instead to assume an a priori bound ℓ(n) (n) since, in the setting we consider, any efficiently computable family of autoregressive models must produce a distribution family =Dnn∈ℕD=\D_n\_n where the arithmetic encoding length is polynomially bounded anyway. 2.1.2 KL-divergence and Compression Loss One intuitive interpretation of the KL-divergence KL(D||D′)KL(D\;||\;D ) between two distributions is as the expected number of additional bits that would be needed to encode samples from D using compression optimized for the distribution D′D as opposed to using compression optimized for D. We restate this for schemes, such as arithmetic encoding, which are “close to optimal” in the sense that the encoding length of a sample is additively close to the empirical entropy of that sample: Claim 2.8. Let D,D′D,D be distributions on Σm ^m and Enc be an encoding such that, for any element x∈sup(D′)x∈ (D ): len((x))≤log(1/D′(x))+αlen( Enc(x))≤ (1/D (x))+α Then, for any distribution D (with sup(D)⊆sup(D′) (D) (D )): x←D[len((x))]≤H(D)+KL(D||D′)+αE_x← D[len( Enc(x))]≤ H(D)+KL(D\;||\;D )+α Proof. By the definition of KL-divergence: KL(D||D′) KL(D\;||\;D ) =x←D[log(1/D′(x))]−x←D[log(1/D(x))] \;=E_x← D[ (1/D (x))]-E_x← D[ (1/D(x))] ≥(x←D[len((x))]−α)−H(D) \;≥(E_x← D[len( Enc(x))]-α)-H(D) which directly implies the conclusion. ∎ By definition, the family =D Enc=\ Enc_D\ where D Enc_D is the arithmetic encoding relative to D has this property for α=2α=2 and thus satisfies: x←D[len(D′(x))]≤H(D)+KL(D||D′)+2E_x← D[len( Enc_D (x))]≤ H(D)+KL(D\;||\;D )+2 2.2 Cross Entropy and LLM Training Objectives We recall the definition of cross-entropy: Definition 2.9. The cross-entropy of a distribution D2D_2 relative to a distribution D1D_1 is given by: H(D1,D2)=−x←D1[logD2(x)]=−∑x∈sup(D1)D1(x)logD2(x)H(D_1,D_2)=-E_x← D_1[ D_2(x)]=- _x∈ (D_1)D_1(x) D_2(x) Cross-entropy is closely related to KL-divergence by the following fact: Fact 2.10. For any distributions D1,D2D_1,D_2: H(D1,D2)=KL(D1||D2)+H(D1)H(D_1,D_2)=KL(D_1||D_2)+H(D_1) Proof. H(D1,D2) H(D_1,D_2) =−∑x∈sup(D1)D1(x)logD2(x)=∑x∈sup(D1)D1(x)logD1(x)D2(x)−∑x∈sup(D1)D1(x)logD1(x) =- _x∈ (D_1)D_1(x) D_2(x)= _x∈ (D_1)D_1(x) D_1(x)D_2(x)- _x∈ (D_1)D_1(x) D_1(x) =KL(D1||D2)+H(D1). =KL(D_1||D_2)+H(D_1). ∎ 2.2.1 Autoregressive Models We shall generally treat LLMs in a black-box way and consider the process of training an LLM in terms of the objective function that it attempts to optimize. Let us assume that an LLM is being trained on some distribution D over sequences of tokens t∈Σ∗t∈ ^* from a vocabulary Σ . During pretraining, the majority of the training process, an LLM is given samples from the distribution D and attempts to “learn” the distribution D by building an autoregressive model ℳM that maps any sequence of tokens t<i∈Σ∗t_<i∈ ^* to a distribution ℳt<iM_t_<i over next tokens that assigns each possible next token tit_i some probability ℳ(ti|t<i)M(t_i\;|\;t_<i). Formally: Definition 2.11. Given an alphabet Σ and a maximum output length m,99 9 We can assume without loss of generality that outputs of length less than m are padded to length m by a special End token. we define an autoregressive model ℳM over Σm ^m to be a collection of distributions ℳtt∈Σ<m\M_t\_t∈ ^<m where every distribution ℳtM_t has support sup(ℳt)⊆Σ (M_t) . We define the induced distribution DℳD_M to be the distribution of complete outputs resulting from the process of starting with an empty string t and iteratively appending a sample from ℳtM_t to t m times to construct a length-m string t∈Σmt∈ ^m. The objective of this training process, then, is to minimize the expectation over samples t←Dt← D of the loss function L(ℳ,t)=−∑i∈[len(t)]logℳ(ti|t<i)L(M,t)=- _i∈[len(t)] (t_i\;|\;t_<i) (1) which is known as cross-entropy loss or negative log-likelihood. We refer to an autoregressive model as δ-optimal with respect to a distribution D if, for any autoregressive model ℳ∗M^* defined over the same alphabet: t←D[L(ℳ,t)]−t←D[L(ℳ∗,t)]≤δE_t← D[L(M,t)]-E_t← D[L(M^*,t)]≤δ that is, the expected loss of ℳM over D is no more than δ worse than the minimum achievable loss. An important observation about this loss function is the following: Claim 2.12. For alphabet Σ , maximum length m, and a fixed training distribution D with support sup(D)⊆Σm (D) ^m, if there exist an autoregressive model ℳM over Σm ^m and constant δ such that ℳM is δ-optimal with respect to D, then, for any autoregressive model ℳ∗M^* defined over Σm ^m: KL(D||Dℳ)−KL(D||Dℳ∗)≤δKL(D\;||\;D_M)-KL(D\;||\;D_M^*)≤δ Proof. Let m be the maximum output length of a sample from D. We can apply the chain rule and Fact 2.10 to show: KL(D||Dℳ) KL(D\;||\;D_M) =∑i∈[m]t<i:t←D[KL(Dt<i||ℳt<i)] \;= _i∈[m]E_t_<i:t← D[KL(D_t_<i\;||\;M_t_<i)] =∑i∈[m]t<i:t←D[H(Dt<i,ℳt<i)−H(Dt<i)] \;= _i∈[m]E_t_<i:t← D[H(D_t_<i,M_t_<i)-H(D_t_<i)] where Dt<iD_t_<i is defined analogously to ℳt<iM_t_<i (i.e., the next-token distribution given prefix t<it_<i) for the training distribution D. Furthermore: ∑i∈[m]t<i:t←D[H(Dt<i,ℳt<i)] \; _i∈[m]E_t_<i:t← D[H(D_t_<i,M_t_<i)] = = −∑i∈[m]t<i:t←D[ti←Dt<i[logℳ(ti|t<i)]] \;- _i∈[m]E_t_<i:t← D[E_t_i← D_t_<i[ (t_i\;|\;t_<i)]] = = −∑i∈[m]t≤i:t←D[logℳ(ti|t<i)] \;- _i∈[m]E_t_≤ i:t← D[ (t_i\;|\;t_<i)] = = t←D[−∑i∈[m]logℳ(ti|t<i)]=t←D[−∑i∈[len(t)]logℳ(ti|t<i)]=t←D[L(ℳ,t)] \;E_t← D [- _i∈[m] (t_i\;|\;t_<i) ]=E_t← D [- _i∈[len(t)] (t_i\;|\;t_<i) ]=E_t← D[L(M,t)] Importantly, since the training distribution D is fixed, the entropy H(Dt<i)H(D_t_<i) is constant, as is its expectation over t←Dt← D, which provides that KL(D||Dℳ)KL(D\;||\;D_M) and t←D[L(ℳ,t)]E_t← D[L(M,t)] are separated by the same additive constant for any model ℳM, implying the conclusion since we have t←D[L(ℳ,t)]−t←D[L(ℳ∗,t)]≤δE_t← D[L(M,t)]-E_t← D[L(M^*,t)]≤δ by assumption of δ-optimality. ∎ This intuitively means that training an LLM by attempting to minimize the expected loss t←D[L(ℳ,t)]E_t← D[L(M,t)] is equivalent to minimizing the KL-divergence KL(D||Dℳ)KL(D\;||\;D_M). One final result that will be useful to us is demonstrating that the cumulative distribution function of a distribution DℳD_M induced by an autoregressive model ℳM can be efficiently computed: Claim 2.13. Given a polynomial-sized alphabet family Σ=Σnn∈ℕ =\ _n\_n with lexicographical ordering ≺ , polynomial maximum length m(⋅)m(·), and family of autoregressive models ℳ=ℳnn∈ℕM=\M_n\_n over Σnm(n) _n^m(n), the following statements are equivalent: 1. For any t∈Σnm(n)t∈ _n^m(n), ℳn(ti|t<i)M_n(t_i\;|\;t_<i) is efficiently computable on all prefixes with Prx←Dℳn[x<i=t<i]>0 _x← D_M_n[x_<i=t_<i]>0. 2. For any n∈ℕn and a∈Σnm(n)a∈ _n^m(n), the cumulative distribution function Prx←Dℳn[x⪯a] _x← D_M_n[x a] is efficiently computable. Proof. (1) → (2). Consider the following procedure for computing Prx←Dℳn[x⪯a] _x← D_M_n[x a]: • Let p=0p=0, p′=1p =1, and i=1i=1. • Let M=(ℳn)a<iM=(M_n)_a_<i, the next-token distribution for the ithi^th token of a. • Set p←p+p′(∑t∈sup(M):t≺aiM(t))p← p+p ( _t (M):t a_iM(t)) and set p′=p′⋅M(ai)p =p · M(a_i). • Repeat the previous two steps incrementing i until i=m(n)i=m(n) or p′=0p =0, then take p←p+p′p← p+p , terminate and return p. Correctness holds because each iteration adds the probability that x←Dℳnx← D_M_n has x<i=a<ix_<i=a_<i but xi≺aix_i a_i (and the final step p←p+p′p← p+p adds the probability that x=ax=a), and the sum of those probabilities is precisely Prx←Dℳn[x⪯a] _x← D_M_n[x a]. Efficiency holds because, since |Σ|| | is polynomial, we compute M(t)=ℳn(t|a<i)M(t)=M_n(t\;|\;a_<i) at most a polynomial number of times in each iteration of the loop, which itself iterates a polynomial number p(n)p(n) of times. (2) → (1). This follows since ℳn(ti|t<i)=Prx←Dℳn[x≤i=t≤i]Prx←Dℳn[x<i=t<i]=Prx←Dℳn[x⪯t≤i⊤]−Prx←Dℳn[x⪯t≤i⊥]Prx←Dℳn[x⪯t<i⊤]−Prx←Dℳn[x⪯t<i⊥]M_n(t_i\;|\;t_<i)= _x← D_M_n[x_≤ i=t_≤ i] _x← D_M_n[x_<i=t_<i]= _x← D_M_n[x t_≤ i ]- _x← D_M_n[x t_≤ i ] _x← D_M_n[x t_<i ]- _x← D_M_n[x t_<i ] where t<i⊤t_<i is the ≺ -greatest element of Σnm(n) _n^m(n) with t<it_<i as a prefix and t<i⊥t_<i is the ≺ -greatest element of Σnm(n) _n^m(n) with a prefix (t⊥)<i≺t<i(t )_<i t_<i, and respectively for t≤i⊤t_≤ i and t≤i⊥t_≤ i . ∎ 3 Autoregressive Models and Compression In this section, we formally prove the equivalence (up to an additive constant) that we informally stated in Theorem 1.1 between the notions of optimal compression of a distribution and learning an accurate autoregressive model for that distribution. Using the facts about compression and cross entropy stated in the previous section, we demonstrate that near-optimal compression can be constructed from a nearly-accurate autoregressive model of a distribution, and subsequently that a nearly-accurate autoregressive model can be constructed from near-optimal compression. Intuitively, this means that training a model such as an LLM to learn a model that minimizes the loss function L(ℳ,t)L(M,t) given in Equation 1 (i.e., pretraining) is equivalent to training it to learn near-optimal compression via an encoding scheme (such as arithmetic encoding) meeting the requirements of Claim 2.8. 3.1 Accurate Autoregressive Models Imply Near-Optimal Compression We begin with the first direction: given an autoregressive model ℳM for a given distribution such that the expectation of L(ℳ,t)L(M,t) over samples from the distribution is close to its optimum, one can use a near-optimal encoding scheme (e.g., arithmetic encoding) to construct efficient compression that is similarly near-optimal with respect to coding length. Lemma 3.1. Let D be a distribution over Σm ^m, ℳM be an autoregressive model with induced distribution DℳD_M, and Enc be a prefix-free encoding scheme such that there exists constant α for which, for any x∈sup()x∈ (D), len((x))≤log(1/Dℳ(x))+αlen( Enc(x))≤ (1/D_M(x))+α. Then, if ℳM is δ-optimal with respect to D, Enc satisfies: x←D[len((x))]≤H(D)+δ+αE_x← D[len( Enc(x))]≤ H(D)+δ+α Proving this lemma is in fact immediate, since we have already demonstrated the necessary groundwork as part of our discussion of compression and KL-divergence in Section 2: Proof. By Claim 2.12, we have KL(D||Dℳ)≤δKL(D\;||\;D_M)≤δ (as the optimum is attained at D=DℳD=D_M which results in a divergence of 0). By Claim 2.8: x←D[len((x))]≤H(D)+KL(D||Dℳ)+α≤H(D)+δ+αE_x← D[len( Enc(x))]≤ H(D)+KL(D\;||\;D_M)+α≤ H(D)+δ+α ∎ Note that, due to Shannon’s lower bound from Corollary 2.4, we know that this bound on the expected encoding length must be no greater than δ+αδ+α away from the optimal expected encoding length over all prefix-free encodings. We can instantiate this using Claim 2.7, which gives α=2α=2, for the following theorem as a direct corollary, noting that Claim 2.13 gives the requisite property that the cumulative distribution function is efficiently computable1010 10 While our result does lose a constant number of bits compared to a “perfect” equivalence, we note that this is in part inevitable, as α=1α=1 is the smallest attainable even by non-monotone compression for an arbitrary family of distributions D.: Theorem 3.2. Given a polynomial-sized alphabet family Σ=Σnn∈ℕ =\ _n\_n with respective ordering ≺nn∈ℕ\ _n\_n and polynomial maximum length m(⋅)m(·), there exists an oracle-aided algorithm (⋅) Enc^(·) so that, for any family of distributions =Dnn∈ℕD=\D_n\_n , family of autoregressive models ℳ=ℳnn∈ℕM=\M_n\_n over Σnm(n) _n^m(n) where ℳn(ti|t<i)M_n(t_i\;|\;t_<i) is efficiently computable for any t∈Σn≤m(n)t∈ _n^≤ m(n) and induces a distribution DℳnD_M_n such that there exists polynomial1111 11 We note that there must exist such a polynomial ℓ(⋅) (·) for any efficiently computable autoregressive model family ℳM, since all next token probabilities must be polynomial-length representable for efficient computability. As noted in the remark following Claim 2.7, one can remove the requirement for such an a priori bound, but at the cost of an exponentially small ϵ(n)ε(n) to the encoding length. ℓ(⋅) (·) for which −log(Dℳn(x))≤ℓ(n)- (D_M_n(x))≤ (n) for all x∈sup(Dℳn)x∈ (D_M_n), and function δ(⋅)δ(·) so that, for any n∈ℕn , ℳnM_n is δ(n)δ(n)-optimal with respect to DnD_n, the family of encodings =ℳn,≺n(1n,ℓ(n),⋅)n∈ℕ Enc=\ Enc^M_n, _n(1^n, (n),·)\_n is prefix-free, monotone (with respect to ≺ ), and efficient, and additionally, for any n∈ℕn : x←Dn[len(n(x))]≤H(Dn)+δ(n)+2E_x← D_n[len( Enc_n(x))]≤ H(D_n)+δ(n)+2 3.2 Near-Optimal Compression Implies Accurate Autoregressive Models Next, we show the other direction: if one has an encoding that compresses a given distribution near-optimally, it is possible to create an autoregressive model that is close to optimal in terms of the expected next-token cross entropy loss t←D[L(ℳ,t)]E_t← D[L(M,t)]. Formally: Theorem 3.3. Given a polynomial-sized alphabet family Σ=Σnn∈ℕ =\ _n\_n and polynomial maximum length m(⋅)m(·), there exists an oracle-aided algorithm ℳ(⋅)M^(·) such that, for any family of distributions =Dnn∈ℕD=\D_n\_n , any function δ(⋅)δ(·), and any prefix-free, monotone (with respect to an ordering ≺nn∈ℕ\ _n\_n ) and efficiently encodable family of encodings =nn∈ℕ Enc=\ Enc_n\_n such that, for any n∈ℕn , x←Dn[len(n(x))]≤H(Dn)+δ(n)E_x← D_n[len( Enc_n(x))]≤ H(D_n)+δ(n) ℳ(⋅)M^(·) defines a family of autoregressive models ℳnn∈ℕ\M_n\_n where, for any n∈ℕn and t∈Σn≤m(n)t∈ _n^≤ m(n), ℳn(ti|t<i)M_n(t_i\;|\;t_<i) is given by ℳn,≺n(1n,ti,t<i)M Enc_n, _n(1^n,t_i,t_<i), ℳ(⋅)M^(·) is efficiently computable, and the respective model ℳnM_n is δ(n)δ(n)-optimal with respect to DnD_n. Proof. (For ease of notation, we omit the parameter n and demonstrate the following for any n∈ℕn .) We wish to define a model ℳM Enc that induces a distribution DℳD_M with a corresponding efficient random sampler :0,1∗→Σm(n) Sample:\0,1\^*→ ^m(n) to be defined subsequently (that is, Dℳ=c←0,1∗:(c)D_M=\c←\0,1\^*: Sample(c)\). We will start by making the simplifying assumption that we know a bound ℓ(⋅) (·) such that len(n(x))≤ℓ(n)len( Enc_n(x))≤ (n) for all x∈Σm(n)x∈ ^m(n) (note that such a polynomial ℓ exists since Enc is efficient). Sample, given a string c∈0,1ℓ(n)c∈\0,1\ (n), does as follows: • Find the largest x∈Σm(n)x∈ ^m(n) with (x)≤c Enc(x)≤ c. (findable by binary search over Σm(n) ^m(n)).1212 12 If no such x exists, output the smallest element of Σm(n) ^m(n). • Find the smallest i such that (c≤i)≠⊥ Dec(c_≤ i)≠ (where, leveraging monotonicity of Enc, we define Dec per Fact 2.3). • If there is no such i, output x. Otherwise output (c≤i) Dec(c_≤ i). By Fact 2.3 and monotonicity of Enc, Dec is efficiently computable, and thus Sample is as well. Furthermore, we make the following claim that Sample is weakly monotone (which nonetheless is sufficient for our proof): Claim 3.4. Sample is weakly monotone: for any c1,c2∈0,1ℓ(n)c_1,c_2∈\0,1\ (n), if c1<c2c_1<c_2, then (c1)⪯(c2) Sample(c_1) Sample(c_2). Proof. This follows from the fact that, since Enc is monotonic and Dec inverts Enc on its domain, Dec must also be monotonic. If both c1c_1 and c2c_2 have prefixes (c1)≤i1(c_1)_≤ i_1 and (c2)≤i2(c_2)_≤ i_2 with valid decodings, then (c1)≤i1≤(c2)≤i2(c_1)_≤ i_1≤(c_2)_≤ i_2, and the same is true of the respective decodings by monotonicity. In the case where no prefix of c1c_1 has a valid decoding, Sample returns the last valid input whose encoding is smaller than c1c_1, which by monotonicity cannot be larger than (c2) Dec(c_2) (or, in the case that c2c_2 also has no prefix with a valid decoding, the last valid input whose encoding is smaller than c2c_2) without contradicting the assumption that c1<c2c_1<c_2. Finally, if no prefix of c2c_2 has a valid decoding but there is such a prefix for c1c_1, then ((c1))≤c1<c2 Enc( Sample(c_1))≤ c_1<c_2. Thus (c1) Sample(c_1) is a candidate in the search for the largest x satisfying (x)≤c2 Enc(x)≤ c_2. Since (c2) Sample(c_2) returns that largest candidate, we obtain (c1)⪯(c2) Sample(c_1) Sample(c_2). ∎ We first need to argue that KL(D||Dℳ)≤δKL(D\;||\;D_M)≤δ; towards that, we first observe that, for any x∈sup(D)x∈ (D), Dℳ(x)≥2−len((x))D_M(x)≥ 2^-len( Enc(x)). This is true because, whenever c is drawn such that it has (x) Enc(x) as a prefix (which happens with precisely probability 2−len((x))2^-len( Enc(x))), that prefix is shorter than the maximum length ℓ(n) (n) by assumption, and it is also the shortest correctly decodable prefix by prefix-freeness of Enc, and thus x will be sampled. From here, Fact 2.10 implies: KL(D||Dℳ)=H(D,Dℳ)−H(D)KL(D\;||\;D_M)=H(D,D_M)-H(D) But for any x∈sup(D)x∈ (D), since Dℳ(x)≥2−len((x))D_M(x)≥ 2^-len( Enc(x)): −logDℳ(x)≤len((x))- D_M(x) ( Enc(x)) and thus, by our original assumption about the compression loss of Enc: −x←D[logDℳ(x)]≤x←D[len((x))]≤H(D)+δ-E_x← D[ D_M(x)] _x← D[len( Enc(x))]≤ H(D)+δ But −x←D[logDℳ(x)]-E_x← D[ D_M(x)] is exactly the cross-entropy H(D,Dℳ)H(D,D_M), so: KL(D||Dℳ)≤(H(D)+δ)−H(D)=δKL(D\;||\;D_M)≤(H(D)+δ)-H(D)=δ as desired. Thus far, we have given a description of the induced distribution DℳD_M in terms of the random sampler Sample, but not constructed the actual model ℳM Enc nor shown that it is efficiently computable. Fortunately, Claim 2.13 provides both of these as long as we can efficiently compute Prx←Dℳ[x⪯y] _x← D_M[x y] for any y∈Σm(n)y∈ ^m(n).1313 13 While Claim 2.13 technically only provides efficient computability on prefixes with non-zero probability of occurrence, we note that we can trivially assign an arbitrary next-token distribution to prefixes with zero probability without changing DℳD_M. However, we claim that, using the efficiency of Sample and Claim 3.4, we can do precisely this: Claim 3.5. For any y∈Σm(n)y∈ ^m(n), Prx←Dℳ[x⪯y] _x← D_M[x y] can be efficiently computed. Proof. If we can efficiently determine the largest c∈0,1ℓ(n)c∈\0,1\ (n) such that (c)≤y Sample(c)≤ y (taking c=0ℓ(n)c=0 (n) if there is no such c), then we can immediately determine that (taking c as an integer) Prx←Dℳ[x⪯y]=(c+1)/2ℓ(n) _x← D_M[x y]=(c+1)/2 (n), as sampling from DℳD_M is by definition equivalent to sampling (c) Sample(c) for uniformly random c∈0,1ℓ(n)c∈\0,1\ (n). And weak monotonicity from Claim 3.4 is sufficient to show that we can find such a c using binary search over 0,1ℓ(n)\0,1\ (n), which must run in time polynomial in n since it requires at most ℓ(n) (n) iterations (which we know is polynomial) and each iteration requires computing Sample and comparing elements of Σm(n) ^m(n), both of which are efficient. ∎ Thus, by Claim 2.13, we have constructed an efficiently computable autoregressive model ℳM with induced distribution DℳD_M that, as we have argued, suffices to complete the argument given an a priori bound of ℓ on the length of (x) Enc(x). Removing ℓ . Next, we explain how to remove the assumption that ℓ is known. First, we modify Sample to, rather than sampling c←0,1ℓ(n)c←\0,1\ (n), instead lazily sample c←0,1∗c←\0,1\^*: specifically, during the binary search, each time Sample compares c to some output (y) Enc(y) for y∈Σmy∈ ^m, if the length of the sampled c is shorter than len((y))len( Enc(y)), Sample draws new uniformly random bits of c up to length |(y)|| Enc(y)|. We argue that the output of Sample is identical. Letting x be the largest x∈Σmx∈ ^m such that (x)≤c Enc(x)≤ c, we notice that number of bits of c sampled by Sample is at least |(x)|| Enc(x)| by construction. Moreover, if (the ℓ -bit long) c has a prefix c≤ic_≤ i which is a valid codeword, then by monotonicity c≤ic_≤ i is a prefix of (x) Enc(x) (otherwise, (x)<c≤i≤c Enc(x)<c_≤ i≤ c, contradicting x being the largest x∈Σmx∈ ^m such that (x)≤c Enc(x)≤ c). Thus, in this case, Sample must return (c≤i) Dec(c_≤ i) as before; if there is no such prefix, then Sample by construction finds and returns x, as desired. Similarly, when computing the CDF in Claim 3.5, finding the largest c such that (c)≤y Sample(c)≤ y is done by binary search where the length of the string c determined by the number of random bits Sample reads during its execution on c. In the ithi^th step of the binary search, we know the prefix c<ic_<i, and we learn the ithi^th bit by comparing the output of (c<i||10∗) Sample(c_<i||10^*) to y (if y is smaller, the next bit is 00, where if y is larger or equal the next bit is 11). We terminate the search when, on the current prefix of c, the execution of Sample halts on the prefix without drawing any additional random bits. After |c||c| steps, we learn the entire string c, and can then compute the CDF Prx←Dℳ[x⪯y] _x← D_M[x y] as before by setting ℓ=|c| =|c|. ∎ As a final note, the random sampler Sample we constructed gives the following corollary, which intuitively states that, given δ-optimal compression Enc for a distribution, it can be efficiently and δ-approximately sampled: Corollary 3.6. Given a polynomial-sized alphabet family Σ=Σnn∈ℕ =\ _n\_n and polynomial maximum length m(⋅)m(·), there exists an oracle-aided sampling algorithm (⋅) Sample^(·) such that, for any family of distributions =Dnn∈ℕD=\D_n\_n , function δ(⋅)δ(·), and prefix-free, monotone, and efficiently encodable family of encodings =nn∈ℕ Enc=\ Enc_n\_n where, for any n∈ℕn , x←Dn[len(n(x))]≤H(Dn)+δ(n)E_x← D_n[len( Enc_n(x))]≤ H(D_n)+δ(n) (⋅) Sample^(·) defines an efficiently computable family of randomized algorithms nn∈ℕ\ Sample_n\_n such that there exists a family of distributions Dn∗n∈ℕ\D^*_n\_n where, for any n∈ℕn , n Sample_n samples from Dn∗D^*_n and KL(Dn||Dn∗)≤δ(n)KL(D_n\;||\;D^*_n)≤δ(n). 4 One-Way Functions and the Monotonicity Requirement Given that our results in the previous section show equivalence between next-token prediction and specifically monotone compression, the question arises of whether one can show a similar equivalence for non-monotone compression, or more specifically whether there are certain conditions under which one can (or cannot) show such an equivalence. In this section, we demonstrate such conditions based on a standard cryptographic assumption: the existence of one-way functions. Whereas Theorem 3.3 shows that monotone compression can be used to construct an autoregressive model with the same loss, we show in Section 4.2 that, given the existence of one-way functions, there exists a family of distributions with non-monotone compression where no efficiently computable autoregressive model can even achieve a cross-entropy loss within an arbitrary constant of the compression loss; the transformation necessarily incurs a loss linear in the input length n. Thus, if one-way functions exist, there is a distinct separation between the results that can be achieved with monotone compression compared to non-monotone compression. Conversely, we show in Section 4.3 that, if one-way functions do not exist, classic results on next-bit prediction [10] can be leveraged to show an analogue of Theorem 3.3 without the requirement for monotonicity. At a high level, if one-way functions do not exist, [10] shows that any (binary) distribution must admit an approximately accurate next-bit predictor. The transformation is not a perfect equivalence, as it creates a small amount of additional statistical distance loss in contrast to Theorem 3.3 (where there is only cross-entropy loss equal to the compression loss); nonetheless, it still constitutes a significant difference compared to what is attainable if one-way functions exist. 4.1 Preliminaries In order to formally state our results, we first precisely define one-way functions. Definition 4.1. A family of functions ℱ=fnn∈ℕF=\f_n\_n , where fn:0,1n→0,1nf_n:\0,1\^n→\0,1\^n, is one-way if ℱF is efficiently computable but, for any non-uniform polynomial-time inverter A, there is a negligible function ϵ(⋅)ε(·) such that for any n∈ℕn : Pr[x←0,1n:f((1n,f(x)))=f(x)]≤ϵ(n)Pr [x←\0,1\^n:f(A(1^n,f(x)))=f(x) ]≤ε(n) If the above instead holds for only infinitely many n∈ℕn for any non-uniform polynomial-time inverter A, we say that ℱF is infinitely-often one-way. That is, one-way functions are efficiently computable, but “hard to invert” in the sense that no computationally efficient algorithm, given the image of a uniformly selected input, can find any inverse of that image with probability significantly better than brute force. The existence of one-way functions is a long-standing open conjecture as it would imply ≠ P≠ NP, but they are nonetheless widely used as a fundamental building block of modern cryptography. The existence of one-way functions is also well-known to imply the existence of pseudorandom generators: Definition 4.2. For some output length ℓ(n)>n (n)>n, a family of efficiently computable functions =gnn∈ℕG=\g_n\_n is referred to as a family of pseudorandom generators (PRGs) if, for any polynomial-time distinguisher D with output in 0,1\0,1\, there exists a negligible function ϵ(⋅)ε(·) such that for any n∈ℕn : |Pr[x←Un:D(1n,gn(x))=1]−Pr[y←Uℓ(n):D(1n,y)=1]|≤ϵ(n) |Pr [x← U_n:D(1^n,g_n(x))=1 ]-Pr [y← U_ (n):D(1^n,y)=1 ] |≤ε(n) where UkU_k represents the uniform distribution over 0,1k\0,1\^k. That is, the output of a PRG on a uniform input should be computationally indistinguishable from uniform randomness. 4.2 One-Way Functions Imply Separation We can, in fact, use PRGs to show a separation between monotone and non-monotone compression: in contrast to Theorem 3.3, which shows that any monotone compression scheme for a distribution can be transformed into a next-bit predictor for that distribution whose negative log-likelihood is identical to the compression loss, we can show that, assuming the existence of infinitely-often one-way functions (and thus PRGs), there is a family of distributions D and a non-monotone compression scheme that is optimal for D but is such that no efficiently computable autoregressive model exists that can predict D with even an arbitrary constant negative log-likelihood: Theorem 4.3. Assuming the existence of one-way functions (respectively, infinitely-often one-way functions), there exists a family of efficiently samplable distributions =Dnn∈ℕD=\D_n\_n and a prefix-free family of encodings =nn∈ℕ Enc=\ Enc_n\_n with efficient encoding and decoding such that x←Dn[len(n(x))]=H(Dn)E_x← D_n[len( Enc_n(x))]=H(D_n) for any n∈ℕn , but, given any efficiently computable family of autoregressive models ℳnn∈ℕ\M_n\_n , for any constant ϵ>0ε>0 and all sufficiently large (resp., infinitely many) n∈ℕn , the respective output distribution DℳnD_M_n is such that KL(Dn||Dℳn)≥(1−ϵ)nKL(D_n\;||\;D_M_n)≥(1-ε)n.1414 14 This implies that, for any constant δ, ℳM cannot be δ-optimal with respect to D. Below we prove the theorem assuming the existence of one-way functions. We note that the proof holds nearly identically for the case of infinitely-often OWFs, with the exception that it applies only to infinitely many n∈ℕn rather than all sufficiently large n; we note the distinctions during the proof. Proof. As the existence of one-way functions implies the existence of PRGs (respectively, infinitely-often OWFs imply infinitely-often PRGs, or PRGs where the condition holds for only infinitely many n∈ℕn ), let =gnn∈ℕG=\g_n\_n be a PRG with output length ℓ(n)=2n (n)=2n. Take our alphabet of tokens to be Σ=0,1 =\0,1\. Let D be given by Dn=x←Un:(gn(x),x)D_n=\x← U_n:(g_n(x),x)\. Let Enc be given by n(gn(x),x)=x Enc_n(g_n(x),x)=x.1515 15 That is, simply take the last n bits of the input. This can be efficiently decoded as well by simply computing gn(x)g_n(x); one can extend it to the full domain of arbitrary 3n3n-bit inputs by letting n(y,x)=y||x Enc_n(y,x)=y||x if y≠gn(x)y≠ g_n(x). Clearly, Enc satisfies prefix-freeness (since every codeword has the same length), efficient encoding and decoding, and has x←Dn[len(n(x))]=H(Dn)=nE_x← D_n[len( Enc_n(x))]=H(D_n)=n. Now fix ϵ>0ε>0 and assume for the sake of contradiction that there exists a family of autoregressive models ℳnn∈ℕ\M_n\_n such that KL(Dn||Dℳn)<(1−ϵ)nKL(D_n\;||\;D_M_n)<(1-ε)n for infinitely many (resp., all sufficiently large) n∈ℕn . We use this to construct a distinguisher A as follows: Take constant c>log(2/ϵ)c> (2/ε), and, given an input y (which will either be drawn as U2nU_2n or as gn(Un)g_n(U_n)), define Dℳn(y,∗)D_M_n(y,*)as the probability for the first 2n2n bits of an output from ℳnM_n to be equal to y, and let A output 11 when Dℳn(y,∗)≥2c−2nD_M_n(y,*)≥ 2^c-2n and 00 otherwise. We make the following claims to complete the proof by contradiction: Claim 4.4. Pr[y←U2n:(y)=1]≤2−cPr [y← U_2n:A(y)=1 ]≤ 2^-c. Proof. y←U2n[Dℳn(y,∗)]=2−2nE_y← U_2n[D_M_n(y,*)]=2^-2n, so this follows from Markov’s inequality. ∎ Claim 4.5. For any constant ϵ′>0ε >0, Pr[x←Un:(gn(x))=1]>ϵ/2−ϵ′Pr [x← U_n:A(g_n(x))=1 ]>ε/2-ε for all sufficiently large n∈ℕn where KL(Dn||Dℳn)<(1−ϵ)nKL(D_n\;||\;D_M_n)<(1-ε)n. Proof. This follows from the assumption that KL(Dn||Dℳn)<(1−ϵ)nKL(D_n\;||\;D_M_n)<(1-ε)n, and thus, by data processing, that KL((Dn)≤2n||(Dℳn)≤2n)<(1−ϵ)nKL((D_n)_≤ 2n\;||\;(D_M_n)_≤ 2n)<(1-ε)n (where (Dn)≤2n(D_n)_≤ 2n represents the distribution of the first 2n2n bits of DnD_n, and respectively for DℳnD_M_n). Thus: KL((Dn)≤2n||(Dℳn)≤2n)=y←Dn[log(1/Dℳn(y,∗))]−H((Dn)≤2n)<(1−ϵ)nKL((D_n)_≤ 2n\;||\;(D_M_n)_≤ 2n)=E_y← D_n[ (1/D_M_n(y,*))]-H((D_n)_≤ 2n)<(1-ε)n and so x←Un[log(1/Dℳn(gn(x),∗))]=y←Dn[log(1/Dℳn(y,∗))]<(1−ϵ)n+H((Dn)≤2n)≤(2−ϵ)nE_x← U_n[ (1/D_M_n(g_n(x),*))]=E_y← D_n[ (1/D_M_n(y,*))]<(1-ε)n+H((D_n)_≤ 2n)≤(2-ε)n since H((Dn)≤2n)≤H(Dn)=nH((D_n)_≤ 2n)≤ H(D_n)=n. Now, by construction of A, A outputs 11 whenever log(1/Dℳn(y,∗))<2n−c (1/D_M_n(y,*))<2n-c; by Markov’s inequality and the above bound on the expectation, the probability that this is not true (i.e., that A outputs 00) when y is given by gn(x)g_n(x) for x←Unx← U_n can be at most (2−ϵ)n2n−c (2-ε)n2n-c, so the probability that A outputs 11, then, must be at least 1−(2−ϵ)n2n−c=ϵn−c2n−c1- (2-ε)n2n-c= ε n-c2n-c which asymptotically approaches ϵ/2ε/2 as n→∞n→∞, implying the conclusion. ∎ Given these, since we assumed by construction that 2−c2^-c is a constant smaller than ϵ/2ε/2, there is a non-negligible (constant) separation between the two probabilities for infinitely many (resp., any sufficiently large) n, which contradicts the assumption that G is a PRG (resp., infinitely-often PRG) and completes the proof. ∎ 4.3 Nonexistence of One-Way Functions Implies (Approximate) Equivalence In contrast to the above, we show that, if infinitely-often one-way functions do not exist, then given any compression scheme for a distribution over a binary support, one can construct an autoregressive model (i.e., a next-bit predictor) for that distribution which is “approximately” as good. This follows from a theorem proven in [10], and in fact we observe that it does not require full non-existence of one-way functions, only that a specific function relative to the given distribution is easy to invert. First, we must define what we mean by a model being “approximately as good” in this case—unlike our previous results, this will involve a loss of statistical distance in addition to the inherent loss of negative log-likelihood resulting from the underlying compression scheme’s loss: Definition 4.6. For alphabet Σ and distribution D over Σm ^m, we say that an autoregressive model ℳM is ϵε-approximately δ-optimal with respect to D if there exists a model ℳ′M that is δ-optimal with respect to D and, Δ(ℳ,ℳ′)≤ϵ (D_M,D_M )≤ε. We can then leverage the following theorem from [10]: Theorem 4.7 (Infinitely-often one-way functions and next-bit predictors [10]). Let =Dnn∈ℕD=\D_n\_n be a family of efficiently samplable distributions where each DnD_n distributed over 0,1m(n)\0,1\^m(n) for some polynomial m(n)m(n). Then, for any function ϵ(n)∈1/(n)ε(n)∈ 1/ poly(n), there exists a function f such that, if f is not an infinitely-often one-way function, then there exists an ϵ(n)ε(n)-approximate (00-optimal) efficiently computable autoregressive model for D. Proof. [10] showed that for every family of efficiently samplable distributions D and for any ϵ′(n)∈1/(n)ε (n)∈ 1/ poly(n), there exists a function f such that, if f is not an infinitely-often one-way function, then there exists a (non-uniform) efficient randomized next bit-predictor Pred with Prt←Dn[(ti|t<i)∈Dn(ti|t<i)(1−ϵ′,1+ϵ′)]≥1−ϵ′ _t← D_n[ Pred(t_i\;|\;t_<i)∈ D_n(t_i\;|\;t_<i)(1-ε ,1+ε )]≥ 1-ε for every sufficiently large n∈ℕn . We first notice that Pred can be made deterministic by fixing the randomness to the best possible string for each index i as part of the non-uniform advice. Next, we notice that Pred is already an ϵ=O(ϵ′⋅m(n))ε=O(ε · m(n))-approximate model for D, as the above promise on Pred implies that its output is close in statistical distance to the distribution DnD_n. ∎ Remark. In fact, Theorem 4.7 can be made stronger: one can show the existence of such a model based on an inverter to a specific function (as opposed to complete non-existence of infinitely-often one-way functions, which would imply the existence of an inverter for every function). In particular, [10] showed that for any ϵ(n)∈1/(n)ε(n)∈ 1/ poly(n), there exists a pair of efficient oracle-aided algorithms (f(⋅),(⋅))(f^(·), Pred^(·)) such that, given a sampler Sample for an ensemble of samplable distributions D, if there exists a polynomial-time algorithm A that, for all sufficiently large n∈ℕn , inverts f Sample with probability 1/21/2, then A Pred^A is an ϵε-approximate next-bit predictor for D. (In particular, f(x1,…,xt)=g(x1),…,g(xt)f Sample(x_1,…,x_t)=g Sample(x_1),…,g Sample(x_t), where g(r,h,i,j)=(i,j,h,(r)≤i,h(r)≤j)g Sample(r,h,i,j)=(i,j,h, Sample(r)_≤ i,h(r)_≤ j), h is a 2-universal hash function, and t∈O(n/ϵ)t∈ O(n/ε).) With the above theorem, given a non-monotone compression scheme Enc which is δ-optimal for some distribution family D, we can leverage part of the construction from Theorem 3.3 even though Enc is not monotone. We prove the following theorem. Theorem 4.8. If infinitely-often one-way functions do not exist, then the following is true for any ϵ(n)∈1/(n)ε(n)∈ 1/ poly(n): For every family =Dnn∈ℕD=\D_n\_n distributions and a compression scheme (,)( Enc, Dec) with efficient encoding and decoding that is δ-optimal for D, there exists an efficiently computable autoregressive models ℳnn∈ℕ\M_n\_n where, for any n∈ℕn the respective model ℳnM_n is ϵ(n)ε(n)-approximately δ(n)δ(n)-optimal with respect to DnD_n. Proof. We first notice that, for any n we can construct a distribution n′D _n such that KL(Dn,Dn′)≤δ(n)KL(D_n,D _n)≤δ(n). Specifically, we showed in the proof of Theorem 3.3 that the distribution DℳD_M, which can be thought of as sampling a uniformly random string and decoding the (unique) codeword that is a prefix of that string, is not only efficiently samplable even when Enc is non-monotone (it requires only that Enc has an efficient decoding algorithm Dec), but induces a model ℳ∗M^* which is δ-optimal with respect to D. (We note that Sample as written requires binary search and thus monotonicity to be efficient, but, if weak monotonicity is not needed, one can replace this step while preserving δ-optimality by returning an arbitrary output if the given random string has no validly decodable prefix.) Next, while ℳ∗M^* is not necessarily efficiently computable if Enc (and thus Sample) is non-monotone, Theorem 4.7 shows directly that, if infinitely-often one-way functions do not exist, then for any function ϵ(n)∈1/(n)ε(n)∈ 1/ poly(n) there is a model ℳM that is ϵ(n)ε(n)-approximate with respect to DℳD_M and thus an ϵ(n)ε(n)-approximate δ-optimal model for D. ∎ 5 Next-Bit Pseudoentropy and Monotone Incompressibility In this section, we discuss an interesting application of our results to cryptography—specifically, the relation between the compressibility of a distribution and its pseudoentropy [6], which can be thought of as a computational analogue of entropy. Informally, a distribution D has pseudoentropy at least h if it is computationally indistinguishable from some distribution D′D with Shannon entropy H(D′)≥hH(D )≥ h. Restricting to the case of binary distributions (Σ=0,1 =\0,1\), we will formally consider a related notion of next-bit pseudoentropy, or pseudoentropy with respect to next-bit prediction: Definition 5.1 ([21]). Given jointly distributed families of random variables =Xnn∈ℕX=\X_n\_n and ℬ=Bnn∈ℕB=\B_n\_n , where ℬB takes values in 0,1\0,1\, we say that ℬB has (non-uniform) conditional pseudoentropy at least h(⋅)h(·) given X if, for any polynomial p(⋅)p(·), there exists a 0,1\0,1\-valued family =Cnn∈ℕC=\C_n\_n of random variables jointly distributed with (,ℬ)(X,B) such that: 1. For all sufficiently large n∈ℕn , H(Cn|Xn)≥h(n)−1/p(n)H(C_n|X_n)≥ h(n)-1/p(n) 2. The families (,ℬ)(X,B) and (,)(X,C) are computationally indistinguishable.1616 16 That is, for any efficient non-uniform distinguisher D, there exists negligible ϵ(⋅)ε(·) such that, for all sufficiently large n∈ℕn , Pr[(x,b)←(Xn,Bn):D(1n,x,b)=1]Pr [(x,b)←(X_n,B_n):D(1^n,x,b)=1 ] and Pr[(x,c)←(Xn,Cn):D(1n,x,c)=1]Pr [(x,c)←(X_n,C_n):D(1^n,x,c)=1 ] differ by no more than ϵ(n)ε(n). Given a polynomial m(⋅)m(·) and family of random variables ℬ=Bnn∈ℕB=\B_n\_n where BnB_n takes values in 0,1m(n)\0,1\^m(n), we say that ℬB has (non-uniform) next-bit pseudoentropy at least h(⋅)h(·) if, letting family ℐ=Inn∈ℕI=\I_n\_n be such that InI_n is uniformly distributed over [m(n)][m(n)], then the conditional pseudoentropy of the family (Bn)Inn∈ℕ\(B_n)_I_n\_n given (Bn)<Inn∈ℕ\(B_n)_<I_n\_n is at least h(n)/m(n)h(n)/m(n). [5] shows a partial characterization of the relation between next-bit pseudoentropy and compressibility of a family of distributions (a notion originally proposed by [22]). Specifically, they show that incompressibility implies pseudoentropy ([5], Lemma 36): if a family of distributions ℬ=Bnn∈ℕB=\B_n\_n over 0,1m(n)\0,1\^m(n) cannot be compressed with some length k(n)k(n), then it must have next-bit pseudoentropy at least k(n)−2k(n)-2. However, they also show that the converse is not true; in fact, there exists a separation ([5], Prop. 39, Lemma 42) showing that, assuming the existence of one-way functions, next-bit pseudoentropy cannot imply incompressibility unless it is strengthened to a notion of “strong” next-bit pseudoentropy which requires next-bit pseudoentropy of (Bn)n∈ℕ\ Enc(B_n)\_n for any efficient encoding (⋅) Enc(·). Our results, in fact, complete the characterization of standard next-bit pseudoentropy by showing that, up to a constant, it is equivalent to monotone incompressibility. This is illustrated by the following corollary of Corollary 3.9 of [21]: Corollary 5.2 ([21, 5]). Given polynomial maximum length m(⋅)m(·) and family of distributions =Dnn∈ℕD=\D_n\_n where DnD_n is a distribution over 0,1m(n)\0,1\^m(n), for some function δ(⋅)δ(·), D has next-bit pseudoentropy at least H(Dn)+δ(n)H(D_n)+δ(n) if and only if, for any polynomial p(⋅)p(·), for every efficiently computable autoregressive model family ℳ=Mnn∈ℕM=\M_n\_n and every sufficiently large n∈ℕn , MnM_n is not (δ(n)−1/p(n))(δ(n)-1/p(n))-optimal with respect to DnD_n. The original corollary in [21] shows an equivalence between ℬB given X (as given in Definition 5.1) having conditional pseudoentropy H(Bn|Xn)+δ(n)H(B_n|X_n)+δ(n) and ℬB being δ(n)δ(n)-KL-hard given X—that is, that there exists no efficient predictor P(x)P(x) that attempts to predict B given X and has KL((X,B)||(X,P(X)))≤δ(n)KL((X,B)\;||\;(X,P(X)))≤δ(n). [5] observed that, given a family D of distributions, one can apply this to a uniformly random bit in a distribution DnD_n (as in the definition of next-bit entropy) and use the additivity of entropy and KL-divergence chain rule to immediately imply that D not having “non-trivial” next-bit entropy H(Dn)+δ(n)H(D_n)+δ(n) implies a next-bit predictor ℳM for any bit of the distribution DnD_n (i.e., an autoregressive model, using our terminology) for which KL(Dn||Dℳn)≤δ(n)KL(D_n\;||\;D_M_n)≤δ(n), or, in other words, ℳM is δ(n)δ(n)-optimal with respect to D. Returning to the equivalence between next-bit pseudoentropy and monotone compression and applying Corollary 5.2, we can now observe that this equivalence is intuitively the same as equivalence between next-bit prediction and monotone compression, which, in fact, is precisely what we have shown in Section 3. The first direction is immediate from (the contrapositive of) Theorem 3.2 and Corollary 5.2, though we note that it is also already proven implicitly in Lemma 36 of [5] because their construction of a compression scheme is monotone. Corollary 5.3. Given polynomial maximum length m(⋅)m(·) and family of distributions =Dnn∈ℕD=\D_n\_n where DnD_n is a distribution over 0,1m(n)\0,1\^m(n), if, for some function k(⋅)k(·), D cannot be monotonically compressed to length k(n)k(n) infinitely often (namely, for any efficient, monotone, prefix-free encoding Enc, Ex←n[len((x))]≥k(n)E_x _n[len( Enc(x))]≥ k(n) for all but finitely many n∈ℕn ), then D has next-bit pseudoentropy at least k(n)−2k(n)-2. Specifically, if D has insufficient pseudoentropy, then by Corollary 5.2 it must have a (k(n)−2−H(Dn)−1/(n))(k(n)-2-H(D_n)-1/ poly(n))-optimal efficiently computable autoregressive model family ℳM, and Theorem 3.2 demonstrates that arithmetic encoding gives efficient and length-(k(n)−1/(n))(k(n)-1/ poly(n)) compression. The other direction is also immediate from our Theorem 3.3 and Corollary 5.2: Corollary 5.4. Given polynomial maximum length m(⋅)m(·) and family of distributions =Dnn∈ℕD=\D_n\_n where DnD_n is a distribution over 0,1m(n)\0,1\^m(n), if, for some function k(⋅)k(·), D has next-bit pseudoentropy at least k(n)k(n), then, for any polynomial p(⋅)p(·), D cannot be monotonically compressed to length k(n)−1/p(n)k(n)-1/p(n). Since Theorem 3.3 shows that D having length-(k(n)−1/(n))(k(n)-1/ poly(n)) compression implies a (k(n)−H(Dn)−1/(n))(k(n)-H(D_n)-1/ poly(n))-optimal autoregressive model family ℳM, the other direction of Corollary 5.2 implies that D cannot have next-bit pseudoentropy at least k(n)k(n) in this case. Generative AI Use Disclosure While finalizing this paper for submission, we used generative AI tools to review our draft in order to fix typographical errors, evaluate technical correctness of our proofs and suggest fixes where applicable, and suggest improvements to the structure and readability of our introduction. We emphasize that all results and writing presented in this paper were produced by the authors, except parts of the technical overview (Section 1.2), which were rewritten using AI tools and subsequently reviewed and edited by the authors. References [DRD+24] G. Delétang, A. Ruoss, P. Duquenne, E. Catt, T. Genewein, C. Mattern, J. Grau-Moya, L. K. Wenliang, M. Aitchison, L. Orseau, M. Hutter, and J. Veness (2024) Language modeling is compression. In The Twelfth International Conference on Learning Representations, External Links: Link Cited by: §1.2, §1.2, §1.2, §1, §1, footnote 6. [FCW00] E. Frank, C. Chui, and I. H. Witten (2000) Text categorization using compression models. In Proceedings DCC 2000. Data Compression Conference, Vol. , p. 555–. External Links: Document Cited by: §1. [GM59] E. N. Gilbert and E. F. Moore (1959) Variable-Length Binary Encodings. The Bell System Technical Journal 38 (4), p. 933–967. External Links: Document Cited by: §1, Definition 2.5. [GS85] A. V. Goldberg and M. Sipser (1985) Compression and Ranking. In Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing, STOC ’85, New York, NY, USA, p. 440–448. External Links: ISBN 0897911512, Link, Document Cited by: Definition 2.1. [HMS23] I. Haitner, N. Mazor, and J. Silbak (2023) Incompressiblity and Next-Block Pseudoentropy. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023), Y. Tauman Kalai (Ed.), Leibniz International Proceedings in Informatics (LIPIcs), Vol. 251, Dagstuhl, Germany, p. 66:1–66:18. Note: Keywords: incompressibility, next-block pseudoentropy, sparse languages External Links: ISBN 978-3-95977-263-1, ISSN 1868-8969, Link, Document Cited by: §1.1, §1.2, Corollary 5.2, §5, §5, §5, footnote 3. [HIL+99] J. Håstad, R. Impagliazzo, L. A. Levin, and M. Luby (1999) A Pseudorandom Generator from any One-way Function. SIAM Journal on Computing 28 (4), p. 1364–1396. External Links: Document Cited by: §1.1, §5. [HER98] J. Hernandez-Orallo (1998) A Formal Definition of Intelligence Based on an Intensional Variant of Algorithmic Complexity. In Proceedings of International Symposium of Engineering of Intelligent Systems (EIS’98), p. 146–163. Cited by: §1. [HLN24] S. Hirahara, Z. Lu, and M. Nanashima (2024) Optimal Coding for Randomized Kolmogorov Complexity and Its Applications. In 2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), Vol. , p. 369–378. External Links: Document Cited by: footnote 3. [HZS+24] Y. Huang, J. Zhang, Z. Shan, and J. He (2024) Compression represents intelligence linearly. In First Conference on Language Modeling, External Links: Link Cited by: §1. [IL89] R. Impagliazzo and M. Luby (1989) One-way functions are essential for complexity based cryptography. In 30th Annual Symposium on Foundations of Computer Science, p. 230–235. Cited by: §1.1, §4.3, §4.3, §4.3, Theorem 4.7, §4, Remark. [MAH99] M. V. Mahoney (1999) Text compression as a Test for Artificial Intelligence. In Proceedings of the Sixteenth National Conference on Artificial Intelligence and the Eleventh Innovative Applications of Artificial Intelligence Conference Innovative Applications of Artificial Intelligence, AAAI ’99/IAAI ’99, USA, p. 970. External Links: ISBN 0262511061 Cited by: §1. [MAH00] M. V. Mahoney (2000) Fast Text Compression with Neural Networks. In Proceedings of the Thirteenth International Florida Artificial Intelligence Research Society Conference, p. 230–234. External Links: ISBN 1577351134 Cited by: §1. [SLM18] I. Schiopu, Y. Liu, and A. Munteanu (2018) CNN-based Prediction for Lossless Coding of Photographic Images. In 2018 Picture Coding Symposium (PCS), Vol. , p. 16–20. External Links: Document Cited by: §1. [SH94] J. Schmidhuber and S. Heil (1994) Predictive Coding with Neural Nets: Application to Text Compression. In Proceedings of the 8th International Conference on Neural Information Processing Systems, NIPS’94, Cambridge, MA, USA, p. 1047–1054. Cited by: §1. [SH96] J. Schmidhuber and S. Heil (1996) Sequential Neural Text Compression. IEEE Transactions on Neural Networks 7 (1), p. 142–146. External Links: Document Cited by: §1. [SHA51] C. E. Shannon (1951) Prediction and entropy of printed English. The Bell System Technical Journal 30 (1), p. 50–64. External Links: Document Cited by: §1. [SHA48] C. E. Shannon (1948) A Mathematical Theory of Communication. The Bell System Technical Journal 27 (3), p. 379–423. External Links: Document Cited by: §1.1, §1, §1, §2.1, Corollary 2.4, Definition 2.5. [TVZ05] L. Trevisan, S. Vadhan, and D. Zuckerman (2005) Compression of Samplable Sources. jcomplexity 14 (3), p. 186–227. Cited by: Definition 2.1, Fact 2.6. [TSA26] C. Tsai (2026) Revisiting Data Compression with Language Modeling. arXiv preprint, p. . External Links: Document Cited by: §1. [TUR50] A. M. Turing (1950) Computing Machinery and Intelligence. Mind LIX (236), p. 433–460. External Links: ISSN 0026-4423, Document, Link, https://academic.oup.com/mind/article-pdf/LIX/236/433/61209000/mind_lix_236_433.pdf Cited by: §1. [VZ12] S. Vadhan and C. J. Zheng (2012) Characterizing pseudoentropy and simplifying pseudorandom generator constructions. In Proceedings of the Forty-Fourth Annual ACM Symposium on Theory of Computing, STOC ’12, New York, NY, USA, p. 817–836. External Links: ISBN 9781450312455, Link, Document Cited by: §1.1, Definition 5.1, Corollary 5.2, §5, §5. [YAO82] A. C. Yao (1982) Theory and Application of Trapdoor Functions. In 23rd Annual Symposium on Foundations of Computer Science (FOCS 1982), Vol. , p. 80–91. External Links: Document Cited by: §1.1, §5. [ZZH+26] Y. Zhang, Y. Zhao, C. Hu, B. Jiao, D. Jiang, R. Miao, and C. T. Nguyen (2026) Learning to Compress: Unlocking the Potential of Large Language Models for Text Representation. In Proceedings of the Fortieth Annual AAAI Conference on Artificial Intelligence, p. . External Links: Document Cited by: §1.