Language Modeling is Monotone Compression
The paper investigates the relationship between Language Models (LLMs), which predict next tokens, and monotone compression algorithms. The main finding is that LLMs are equivalent to monotone compression schemes, meaning one can be constructed from the other with a small error gap of 2. This equivalence depends on whether infinitely-often one-way functions exist in cryptography.