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