Language models match order-preserving compression algorithms closely
Language Modeling is Monotone Compression
Information TheoryArtificial IntelligenceCryptography and Security
Summary
This work explores a deep connection between how large language models (LLMs) predict words and how information can be compressed while keeping the order of data intact. The authors show that the tasks of next-word prediction by LLMs are fundamentally equivalent to a special kind of compression called monotone compression. They also connect this idea to cryptography, showing this equivalence depends on the existence of certain hard-to-reverse functions. Finally, they relate a cryptographic measure called pseudoentropy to how well something can be compressed without losing order.
What this means in practice
- •For language model engineers: Clarify the theoretical limits of language models as compressors to guide model optimization and error analysis.
- •For security system designers: Use the equivalence between monotone compression and pseudoentropy to better understand cryptographic security guarantees in data encoding.
A theory result. No direct application yet.
Authors
Noam Mazor, Andrew Morgan, Rafael Pass
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.)