PaperlayerView exact revision on arXiv

Source-linked AI summary

Language Modeling is Monotone Compression

Noam Mazor, Andrew Morgan, Rafael Pass

arXiv:2610.11031v1cs.ITcs.AIcs.CRmath.IT

TL;DR

The paper asks whether next-token prediction and compression are formally connected, given empirical differences between the two conversion directions. It develops efficient transformations between autoregressive models and monotone compressors, and shows that the transformations preserve accuracy up to an additive gap of 2; whether monotonicity is necessary depends on infinitely-often one-way functions.

  • Problem

    The proposed connection between intelligence and compression motivates asking whether autoregressive prediction and compression are formally equivalent, especially given the reported empirical disparity between conversions in the two directions.

    Source: §1 · pp. 1–2

  • Method

    The paper proves efficient transformations between autoregressive models and prefix-free monotone compression schemes, using arithmetic encoding and a monotone sampler.

    Source: §1 · p. 2, §1.1 · p. 2, §1.2 · p. 5

  • Results

    The transformations give an additive accuracy gap of 2, and infinitely-often one-way functions make monotonicity necessary for a strong equivalence.

    Source: §1 · p. 2, §1.1 · p. 3, §1.2 · p. 4

  • Takeaways & Limitations

    The empirical mismatch between the two conversion directions is consistent with the result that non-monotone compression need not support the same strong equivalence when infinitely-often one-way functions exist.

    Source: §1 · p. 2, §1.1 · p. 3

    The 2-bit loss is partly unavoidable: even non-monotone compression cannot attain zero loss for an arbitrary family of distributions.

    Source: §3.1 · p. 13

Abstract

from arXiv · show

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

1 Introduction

The paper turns the proposed link between intelligence and compression into a formal question: can next-token prediction and compression be constructed from one another with comparable accuracy? It shows an equivalence for monotone compression, identifies a cryptographic condition governing whether monotonicity is necessary, and applies the result to next-bit pseudoentropy.

1 Introduction

  • The paper asks whether predictive modeling and compression are formally connected, motivated by the intuitive link between intelligence and succinctly describing information and by an empirical gap between the two conversion directions.Prior work reports competitive compression from LLMs, while models constructed from compression have relatively poor predictive ability compared with state-of-the-art LLMs.Source: §1 · pp. 1–2

1.1 Our Results

  • Autoregressive models and monotone compressors can be efficiently constructed from one another with an additive accuracy gap of 2.The two directions are: a δ-optimal model yields a (δ + 2)-optimal monotone compressor, while a δ-optimal monotone compressor yields a δ-optimal model.Source: §1.1 · p. 3, §1.2 · p. 4
  • If infinitely-often one-way functions exist, non-monotone compression can be optimal while every efficient autoregressive model has linear excess loss; if they do not, an efficient non-monotone compressor can yield a statistically close near-optimal model.The separation under one-way functions holds for all sufficiently large lengths, or infinitely many lengths under the infinitely-often variant.Source: §1.1 · pp. 3–4
  • Next-bit pseudoentropy is equivalent, up to an additive gap of 2, to the inability to efficiently monotonically compress a distribution.Earlier work established that incompressibility implies next-bit pseudoentropy, but the converse does not hold without the monotonicity condition.Source: §1.1 · p. 4

1.2 Technical Overview

  • Arithmetic encoding converts an autoregressive model’s output distribution into a monotone compressor, with an overhead of 2 bits beyond the model’s excess prediction loss.The expected compression length is bounded by the data entropy, the model’s KL-divergence, and the arithmetic-encoding overhead.Source: §1.2 · pp. 4–5
  • A monotone compressor yields an autoregressive model by decoding uniformly random seeds with a weakly monotone sampler, then using binary search to compute its CDF and next-token probabilities.Prefix probabilities are obtained from CDF values because outputs sharing a prefix form a contiguous lexicographic interval.Source: §1.2 · pp. 5–6

2 Definitions

This section defines the compression and language-modeling concepts used in the paper, including monotone encodings, arithmetic coding, compression loss, cross-entropy, and autoregressive training objectives. It also states that for autoregressive models, efficiently computing next-token probabilities on positive-probability prefixes is equivalent to efficiently computing the distribution’s cumulative probability through any string.

2 Definitions

  • Algorithms use polynomial advice and are efficient when their running time is polynomial in the parameter; oracle-aided efficiency also requires polynomially many calls to an efficient oracle.The section also defines negligible functions and standard notation for strings and distributions.Source: §2 · p. 7

2.1 Compression

  • Compression seeks uniquely decodable encodings with minimum expected length; monotone encodings preserve lexicographic order, and efficiently encodable monotone schemes are efficiently decodable.The section also defines prefix-free encodings and assumes binary outputs unless stated otherwise.Source: §2.1 · pp. 7–8

2.1.1 Arithmetic Encoding

  • Arithmetic encoding is one-to-one and monotone, is prefix-free on the distribution support, and compresses to expected length H(Dn) + 2.With a polynomial bound on codeword length and an efficiently computable CDF, it can be extended to a prefix-free, monotone, efficiently computable encoding over the full input space while retaining H(Dn) + 2 compression.Source: §2.1.1 · p. 9

2.1.2 KL-divergence and Compression Loss

  • For encodings close to optimal under a reference distribution, the paper uses KL-divergence to characterize the additional compression loss when encoding samples from another distribution.Arithmetic encoding relative to D has the stated near-optimality property with additive parameter α = 2.Source: §2.1.2 · p. 10

2.2 Cross Entropy and LLM Training Objectives

2.2.1 Autoregressive Models

  • An autoregressive model assigns next-token distributions to prefixes and induces a distribution over complete outputs; minimizing expected cross-entropy loss on D is equivalent to minimizing KL(D||DM).The training loss is negative log-likelihood, and δ-optimality means expected loss is at most δ above the minimum achievable by any autoregressive model.Source: §2.2.1 · pp. 11–12
  • Efficient next-token probabilities on positive-probability prefixes and efficient computation of the cumulative distribution function are equivalent.The two conditions apply to all relevant prefixes and strings, respectively.Source: §2.2.1 · p. 12
  • The proof computes the cumulative probability by iterating over token positions and summing probabilities for strings that first differ at that position, plus the probability of equality.With a polynomial-size alphabet and polynomially many positions, the procedure makes only polynomially many next-token probability computations.Source: §2.2.1 · p. 12

3 Autoregressive Models and Compression

The section proves both directions of the connection between autoregressive prediction and monotone compression. Accurate predictors yield near-optimal compression, while monotone near-optimal compression yields an accurate autoregressive model.

3.1 Accurate Autoregressive Models Imply Near-Optimal Compression

  • An autoregressive model with loss within δ of optimum yields efficient, prefix-free monotone compression within δ+2 bits of optimal expected length.The forward construction uses a near-optimal encoding scheme such as arithmetic encoding.Source: §3.1 · p. 13, §3 · p. 13

3.2 Near-Optimal Compression Implies Accurate Autoregressive Models

  • A prefix-free, efficiently encodable monotone scheme that is δ-optimal yields an efficiently computable δ-optimal autoregressive model.The construction samples from codeword prefixes and uses the resulting distribution to define next-token probabilities.Source: §3.2 · p. 14
  • Weak monotonicity of the sampler lets the construction efficiently compute prefix probabilities by binary search.The search takes polynomially many iterations when the code-length bound is polynomial; the paper also describes removing the need to know that bound in advance.Source: §3.2 · p. 15
  • The sampler induced by a monotone near-optimal encoding also provides an efficient approximate sampler for the distribution.The section states this as Corollary 3.6.Source: §3.2 · p. 16

4 One-Way Functions and the Monotonicity Requirement

The section identifies when monotonicity matters for connecting compression to next-token prediction. One-way functions imply a separation for non-monotone compression, whereas their nonexistence gives an approximate equivalence.

4 One-Way Functions and the Monotonicity Requirement

  • The comparison is conditional: one-way functions imply a separation for non-monotone compression, while their nonexistence permits approximate equivalence.The nonexistence direction allows a small amount of additional statistical-distance loss.Source: §4 · p. 16

4.1 Preliminaries

  • Infinitely-often one-way functions require failure of inversion on infinitely many input lengths rather than all sufficiently large lengths.The paper describes one-way functions as efficiently computable but hard for polynomial-time inverters to invert.Source: §4.1 · p. 17

4.2 One-Way Functions Imply Separation

  • Assuming one-way functions, an optimal non-monotone compressor can coexist with autoregressive models whose excess cross-entropy is linear in output length.The construction's encoding length equals the distribution's entropy, while the lower bound holds for all sufficiently large lengths, or infinitely many lengths under infinitely-often one-way functions.Source: §4.2 · p. 17

4.3 Nonexistence of One-Way Functions Implies (Approximate) Equivalence

  • If infinitely-often one-way functions do not exist, efficient compression yields an efficiently computable autoregressive model statistically close to a δ-optimal model.The result applies to efficiently encodable and decodable δ-optimal compression for efficiently samplable distributions, with inverse-polynomial approximation error.Source: §4.3 · pp. 18–19

5 Next-Bit Pseudoentropy and Monotone Incompressibility

The paper completes a characterization linking next-bit pseudoentropy to monotone incompressibility. Its corollaries give both directions, up to constant or inverse-polynomial gaps.

5 Next-Bit Pseudoentropy and Monotone Incompressibility

  • Next-bit pseudoentropy at least H(Dn)+δ(n) is equivalent to every efficient autoregressive model failing to be (δ(n)−1/p(n))-optimal for sufficiently large n.This equivalence holds for every polynomial p.Source: §5 · p. 20
  • If D cannot be monotonically compressed to length k(n) infinitely often, it has next-bit pseudoentropy at least k(n)−2.The incompressibility condition ranges over efficient, monotone, prefix-free encodings.Source: §5 · p. 20
  • Next-bit pseudoentropy at least k(n) rules out monotone compression to length k(n)−1/p(n) for any polynomial p.Together with the converse corollary, this completes the characterization up to a constant.Source: §5 · pp. 20–21
Loading 2610.11031v1…