acceptodds
Under review as a conference paper at ICLR 2027

Language Modeling is Monotone Compression

Abstract

A long-standing empirical observation spanning the domains of artificial intelligence and neuroscience asserts that intelligence is equivalent to compression—an entity that is able to compress information efficiently demonstrates intuitive notions of intelligence and learning, and vice versa. 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 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.)

Primary area:
learning theory
Keywords:
theory, learning theory, large language models, coding theory, compression, cryptography

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 2 reviews, above 85% of the others.
Reviewer_XTVGOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This is a theoretical paper showing the connection between compression algorithms and LLMs. In particular, the paper shows that monotone compression, i.e. compression algorithms that preserve the ordering when decoded like arithmetic coding, is equivalent to next token predictor LLMs. It is also shown that the monotonicity is a required condition for this result if and only if there exists infinitely-often one-way functions. Overall, the paper provides new theoretical results in establishing the connection between compression and LLMs, and in particular show that monotonicity is an important criteria to establish the equivalent the two, and the lack of this monotonicity criteria leads to the known differences between good performance of LLMs as a compression algorithm and the use of compression algorithms as an LLM like generative model.

Critical strengths
  • This paper provides important theoretical results showing the connection between LLMs and monotone compression algorithms like arithmetic coding.
  • The results provided also shows that the monotonicity criteria is important to establish the equivalence if and only if there exists infinitely-often one-way functions in the cryptographic sense.
  • The results also establish the current known difference between using an LLM for compression and using a compression algorithm like a generative model.
Critical weaknesses
  • I understand the paper is intended as a theoretical paper and does a good job in doing so. However, I would be curious to see some empirical benefits of the introduction of monotonicity in compression in the existing theory. Does this result help us use compression algorithms such as arithmetic codes better as LLMs? I might be misunderstanding this part.
Questions for authors
  • Please answer the questions in the weaknesses.
Reviewer_y5ZmOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper theoretically formalizes the relationship between language models and compressors. In particular, it shows that nxet-token predictors and compressors can be converted into each other in both directions with a loss difference of at most 2 bits, under the condition of monotone compression.

Critical strengths

The authors theoretically proves that monotonicity is an important condition for converting a compressor into a predictor

Critical weaknesses

Although the results are theoretically proven, the paper does not discuss how they could be applied in practice.

Questions for authors

Are there any practical benefits that could be obtained by leveraging the results of this paper?

Comments on the paper

2 comments
AuthorsOpenReview ↗

Response to Reviewers

We thank the reviewers for their feedback and consideration of our work. As both of the reviews we received primarily had the same question (regarding the practical implications of our work), we address both reviews simultaneously.

Our paper is indeed intended as a theoretical investigation into a connection that has previously been studied empirically and conceptually. As such, its primary purpose is to frame and explain existing practical results: specifically, through showing that learning is equivalent to a strengthening of compression, our work provides a formal explanation for why existing constructions of compression from LLMs (virtually all of which leverage arithmetic encoding, which is innately monotone) are very powerful while, in the other direction, constructing autoregressive models from compression is a much harder task because existing compression algorithms are not designed to be monotone.

That said, we wish to highlight two implications of our work that we feel are practically relevant:

First, our work establishes that monotonicity is a naturally desirable property of compression, not only because sufficiently powerful monotone compression could be used to construct a similarly powerful autoregressive model, but also because monotonicity implies a "searchability" property: as we show, monotonicity of a compression scheme implies the ability to both efficiently decompress by binary search and to efficiently find the CDF of any element with respect to the induced distribution. Furthermore, we know (from the properties of arithmetic encoding) that near-optimal monotone compression is achievable.

Second, by formally connecting cross-entropy to compression, which in turn has been linked to intuitive notions of intelligence by prior work, our work formally verifies the intuition underlying LLM training by demonstrating that cross-entropy is in essence a provably correct measure of intelligence.

Furthermore, we submit for consideration a revision to our paper that both improves the readability of our introduction and technical overview and updates our proofs to handle corner cases. We emphasize that all of our results are unchanged from the version that was originally submitted.

Thank you for clarifying how the theoretical results could be applied. The practical benefit remains unclear to me without empirical results on predictive performance and computational cost. I will maintain my score.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.