Language Modeling is Monotone Compression

What it claims

Mazor, Morgan and Pass (Cornell) give a formal equivalence between next-token predictors and monotone compression. A monotone (order-preserving) compressor is one whose encoding preserves the ordering of its inputs. Each object can be built from the other, and the error is preserved up to an additive gap of 2.

The cryptographic side carries most of the new content:

• Whether monotonicity can be dropped depends on one-way functions. Monotonicity is required for the equivalence if and only if infinitely-often one-way functions exist. So "a good LLM is just a good compressor" holds without qualification only in a world without such cryptography. Under standard cryptographic assumptions, an arbitrary compressor need not yield a predictor.
• The paper proves the missing direction of a known result. It shows next-bit pseudoentropy is equivalent to monotone incompressibility. Haitner et al. (ITCS'23) had previously shown only one direction, that incompressibility implies next-bit pseudoentropy. The converse is the new part, and the authors present it as of independent interest to cryptographers.

Evidence

The work is purely theoretical. The abstract uses two empirical papers as motivation; it does not test them:

• Deletang et al. (ICLR'24) used LLMs as strong compressors.
• Huang et al. (COLM'24) found that LLM compression ability is highly correlated with performance on knowledge and reasoning benchmarks.

The paper offers a theoretical account of why those correlations should exist. It reports no experiments, models, datasets or benchmarks of its own.

Limits

• Abstract only. The fetched page contains just the abstract and metadata. These details are not stated:
• the precise error measure behind the "additive gap of 2"
• the computational-efficiency terms of the reductions, such as how much running time each construction costs
• whether the results hold for non-binary token alphabets
• Formal model, not real systems. LLMs are modelled abstractly as next-token predictors. Nothing in the abstract addresses training, architecture or practical compressor implementations.
• Not peer reviewed. It is a preprint on the Cryptology ePrint Archive (category: Foundations), received 2026-10-08 and approved 2026-10-11.
• Licence. CC BY, so reuse with attribution is permitted.
• Who should read it. Engineers looking for a usable compression method or evaluation recipe will not find one here. The paper is mainly relevant to readers who want to justify compression-based evaluation of LLMs (for example, bits-per-token as a capability proxy) on theoretical grounds. Those readers should check that their compression scheme is monotone, as arithmetic coding driven by a model's predictions typically is. The equivalence is stated for monotone compressors, not compressors in general.