Language Modeling is Monotone Compression

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