← Back to all news
arXiv AI

Language Modeling is Monotone Compression

The paper investigates the relationship between large language models (LLMs) and compression, showing that LLMs, modeled as next‑token predictors, are equivalent to monotone (order‑preserving) compression algorithms with an error gap of at most 2. It further proves that this monotonicity is necessary for the equivalence only if cryptographic one‑way functions exist, and derives a cryptographic corollary linking next‑bit pseudoentropy to monotone incompressibility.

Related stories

arXiv AI
Sep 21

Large Language Models As Shannon Lossy Compressors Not Solomonoff Induction Estimators: The Singularity Is Not Near Without Symbolic Model Synthesis

The paper argues that Large Language Models (LLMs) do not function as Solomonoff induction estimators because their training objectives—cross‑entropy, negative log‑likelihood, and next‑token prediction—optimize fit to a supplied conditional distribution rather than a program‑weighted universal mixture. It further contends that additional computation alone does not transform these models into optimal predictors without external hyper‑parameter or architectural changes. The authors suggest that neurosymbolic machine learning, exemplified by models such as Fable and Astra, represents a shift toward symbolic model synthesis, moving beyond purely statistical LLMs.

By Hector Zenil, Abicumaran Uthamacumaran, Luan Ozelim
llms
More like this →
arXiv AI
Aug 12

On Solomonoff Induction in Large Language Models and the Limits of Self-Improving: The Singularity Is Not Near Without Symbolic Model Synthesis

arXiv:2601. 05280v3 Announce Type: replace-cross Abstract: On the one hand, the question of whether large language models (LLMs) are Solomonoff induction estimators has become an explicit question at the intersection of Algorithmic Information Theory (AIT) and Machine Learning (ML) of great interest.

By Hector Zenil
llms
More like this →
arXiv Machine Learning
Oct 16

Does Compression Imply Generalization? A Minimum Description Length Perspective

The paper investigates whether compression explains why over‑parameterized neural networks generalize, using the minimum description length (MDL) principle. It introduces prequential regret, a computable metric from the training trajectory, and shows that in the nearly interpolating regime it upper‑bounds the description length of the trained parameters, leading to a high‑probability generalization bound in the PAC‑MDL setting. The study also connects MDL with the algorithm‑level information bottleneck by bounding encoder‑complexity correction with MDL parameter description length, and demonstrates that prequential regret correlates strongly (Pearson > 0.9) with generalization error on CIFAR‑10 and CIFAR‑100.

By Lincen Yang, Jiayang Shi, Nan Pu, Dani\"el M. Pelt, Matthijs van Leeuwen, Zhong Li, Shujian Yu
More like this →
arXiv Machine Learning
Sep 10

Length Generalization for Transformers via Compression

arXiv:2609.08851v1 Announce Type: new Abstract: Recent advancements in transformer length generalization theory enable us to reliably predict when a transformer can learn to solve a task. In particul...

By Georg Zetzsche, Hongjian Jiang, Andy Yang, Pascal Bergstr\"a{\ss}er, Marco S\"alzer, David Chiang, Anthony W. Lin
llms
More like this →