Language Modeling is Monotone Compression

The gist: LLMs are equivalent to monotone compression algorithms up to an additive gap of 2, and this equivalence requires the existence of infinitely-often one-way functions.

How it works

The main result establishes that autoregressive models and monotone compression schemes are equivalent in terms of performance, with an additive gap of 2 between their respective loss measures The paper shows that given a distribution D, an efficiently computable δ-optimal autoregressive model can construct a monotone compression scheme which is (δ + 2)-optimal with respect to D. Conversely, given a δ-optimal monotone compression scheme, one can construct a δ-optimal autoregressive model for D.

The Role of Monotonicity

The requirement of monotonicity is crucial for this equivalence to hold in the presence of cryptographic assumptions. Theorem 1.2 demonstrates that if one-way functions (or infinitely-often one-way functions) exist, then a non-monotone compression scheme can achieve an expected encoding length exactly equal to H(Dn), but every efficiently computable autoregressive model has excess cross-entropy loss at least linear in the output length. This disparity explains why constructions of autoregressive models from compression tend to exhibit relatively poor predictive ability compared to state-of-the-art LLMs.

Formal Equivalence and Construction

The equivalence is formalized through explicit efficient transformations. In the direction from autoregressive models to compression, arithmetic encoding connects the expected negative log-likelihood used for training an LLM directly to compression by assigning codewords such that len(Enc(x)) ≤ − log DM(x) + 2. This leads to the conclusion that δ-optimality of M implies (δ + 2)-optimality of the compression scheme. The construction involves an efficient monotone sampler and an autoregressive model whose output distribution DM is exactly the distribution of Sample(c) when c ← 0, 1l is uniform.

Connection to Cryptography

The necessity of monotonicity for this equivalence is tied to the existence of one-way functions. Theorem 1.2 states that if one-way functions exist, then monotonicity is necessary for any strong autoregressive model-compression equivalence. Conversely, if infinitely-often one-way functions do not exist, then given a δ-optimal compression scheme, one can construct an efficiently computable autoregressive model statistically close to a δ-optimal autoregressive model for D. This suggests that the intuitive connection between modeling and compression depends on the truth of this assumption.

Pseudoentropy and Incompressibility

The results extend to cryptographic notions by relating compressibility to next-bit pseudoentropy. Corollary 5.3 shows that if a distribution D cannot be efficiently monotonically compressed to length k(n) infinitely often, then D has next-bit pseudoentropy at least k(n) − 2. This is equivalent to the statement that for any polynomial p(·), for every efficiently computable autoregressive model family M = Mn n, Mn is not (δ(n) − 1/p(n))-optimal with respect to Dn.

Non-Monotone Compression and Approximate Equivalence

When one-way functions do not exist, the equivalence can be shown approximately. Theorem 4.8 shows that if infinitely-often one-way functions do not exist, then for any compression scheme (Enc, Dec) that is δ-optimal for D, there exists an efficiently computable autoregressive model family where Mn is ϵ(n)-approximately δ(n)-optimal with respect to Dn. This demonstrates that without the existence of infinitely-often one-way functions, next-bit prediction and non-monotone compression are approximately equivalent.

Conclusion on Separation

The existence of infinitely-often one-way functions implies a distinct separation between the results achievable with monotone compression compared to non-monotone compression. Theorem 4.3 shows that assuming the existence of one-way functions, there exists 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. Conversely, if infinitely-often one-way functions do not exist, classic results on next-bit prediction can be leveraged to show an analogue of Theorem 3.3 without the requirement for monotonicity.

The paper concludes by showing that the equivalence between next-bit prediction and monotone compression is precisely what has been shown in Section 3. The final result establishes a tight characterization of standard next-bit pseudoentropy by showing it is equivalent to monotone incompressibility up to a constant.

--- Page 1 ---

Language Modeling is Monotone Compression 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´etang 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 nextbit pseudoentropy (a computational analogue of entropy) of a distribution is equivalent to monotone incompressibility of the distribution.

--- Page 2 ---

It is well known that good compression schemes can be constructed from good autoregressive models by leveraging arithmetic encoding [Sha48,GM59]: 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 [SH94] (see also, e.g., [SH96,Mah00, SLM18]), 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., [DRD+24,ZZH+26,Tsa26]), but also that compression ability of LLMs is highly correlated with performance on benchmarks measuring knowledge, reasoning, and coding abilities. 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. 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-the-art LLMs.

--- Page 3 ---

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. 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-the-art LLMs. While there are certainly plausible intuitive explanations for this disparity—for instance, the difference in computational power between stateof-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).

1. textbfReal-time Next-Token Prediction via Monotone Compression Equivalence: The system can construct an efficiently computable autoregressive model from a monotone compression scheme which is (δ + 2)-optimal with respect to D. This means the AI can learn high-quality next-token predictors by leveraging the structure of monotone encodings, ensuring the constructed model is statistically close to a δ-optimal autoregressive model for D (Theorem 1.1).

2. textbfCryptographic Security Analysis: The system can distinguish between monotone and non-monotone compression capabilities based on one-way functions. Specifically, if one-way functions exist, the system can demonstrate a clear difference in terms of the empirical quality of results, showing that the requirement of monotonicity is necessary for any strong autoregressive model-compression equivalence (Theorem 1.2).

3. textbf Enhanced Compression Bounds: The system can achieve near-optimal compression rates by leveraging LLM training objectives, as it shows that near-optimal compression can be constructed from LLMs and that the expected compression length is bounded by H(D) + KL(D DM) + 2 (Section 1.2).

4. textbfAdaptive Sampling for Compressed Data: The system can perform efficient sampling of data from a distribution D with an oracle-aided sampling algorithm Sample such that the resulting distribution D∗n satisfies KL(Dn D∗n) ≤ δ(n) (Corollary 3.6). This allows for efficient generation of samples based on compressed representations, where the sampler can adapt its bit length based on the required encoding length.

5. textbf Model Approximation under No OWFs: If infinitely-often one-way functions do not exist, the system can construct an autoregressive model that is ϵ(n)-approximately δ(n)-optimal with respect to Dn (Theorem 4.8). This means for any compression scheme, a nearly optimal next-token predictor can be found, even without the full guarantee of monotonicity.

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.)