🔢 mathematics

The LZ78 Source

This paper characterizes the entropic and distributional properties of a family of non-stationary processes generated by the LZ78 universal compressor, demonstrating that while they exhibit "almost stationary" convergence properties similar to ergodic sources, their finite-state compressibility strictly exceeds their entropy rate due to a Jensen gap, thereby providing a novel benchmark for evaluating sequential probability models and in-context learning in transformers on non-Markovian data.

Original authors: Naomi Sagan, Amir Dembo, Matthew Ho, Tsachy Weissman

Published 2026-04-20

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Naomi Sagan, Amir Dembo, Matthew Ho, Tsachy Weissman

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: A New Kind of "Randomness"

Imagine you are trying to teach a robot to predict the next word in a sentence. Usually, we test robots on simple rules, like "if it's raining, the next word is 'umbrella'." But the real world is messy. Sometimes the rules change, and sometimes the rules depend on things that happened a long time ago.

This paper introduces a new "test track" for these robots. It's called the LZ78 Source. Think of it as a self-writing, self-editing story generator that creates data which is incredibly hard to predict because it keeps changing its own rules as it goes.

The authors ask two main questions:

How much "surprise" (entropy) does this story generator actually produce?
Can modern AI (specifically Transformers) learn to predict this story better than old-school math models?

Part 1: The "Story Tree" (How the Source Works)

To understand the LZ78 Source, imagine a giant, magical tree growing in a forest.

The Roots: Every time the story starts a new sentence, the tree sends a "seed" (a random number) to the root. This seed decides the mood of the story. If the seed is "0.9," the story will likely be full of the letter '1'. If it's "0.1," it will be mostly '0's.
The Branches: As the story writes itself, it walks down the tree.
- If it sees a pattern it has never seen before (like a new phrase "001"), it grows a new branch on the tree.
- On this new branch, it plants a new seed (a new random mood).
- If it sees a pattern it has seen before, it just walks down the existing branch.
The Loop: Every time the story finishes a "phrase" (a chunk of text), it jumps back to the root to pick a new seed for the next chunk.

The Analogy: Imagine a chef cooking a meal.

Every time they start a new dish, they roll a die to decide if the dish will be "Spicy" or "Sweet."
If they make a dish they've never made before, they write down the recipe on a new card and hang it on a wall (the tree).
Next time they make that specific dish, they look at the card to remember the recipe.
But here's the twist: The flavor (the probability of ingredients) changes every time they start a new dish, based on that random die roll.

Because the tree keeps growing new branches for new patterns, the "context" (what you need to remember to predict the next word) gets longer and longer. It's not just "if it rained yesterday, it will rain today." It's "if it rained on the day we invented the umbrella, and we used that umbrella on Tuesday, then it will rain today."

Part 2: The "Jensen Gap" (The Trap for Predictors)

The paper discovers a fascinating mathematical quirk called the Jensen Gap.

The Analogy: Imagine you are betting on the weather.

The "True" Weather: The weather is actually a mix of two different climates. Sometimes it's a hot desert (100% sun), sometimes it's a cold tundra (100% snow). You don't know which one it is until you see the day.
The "Average" Weather: If you just look at the long-term average, it looks like "50% sun, 50% snow."

The Trap:

If you use a simple model (like a finite-state machine or a basic Markov model) that only remembers the last few days, it will try to predict based on the "Average Weather." It will guess "50% sun."
But the true complexity of the weather is actually higher because it's constantly switching between two extreme states.
The paper proves that for this LZ78 Source, no matter how much memory you give a simple predictor, it will always be "off" by a specific amount. It can never perfectly match the true randomness of the source.

This gap is the "Jensen Gap." It's the difference between the average of the moods and the mood of the average. It means the source is fundamentally harder to compress than a standard random source.

Part 3: The AI Showdown (In-Context Learning)

The authors used this tricky "Story Tree" source to test Transformers (the AI behind models like ChatGPT).

The Setup:
They trained small AI models on data generated by this Source. They wanted to see if the AI could learn the "rules" of the tree just by reading the text, without being explicitly programmed with the rules. This is called In-Context Learning (ICL).

The Results:

Old Models Fail: Traditional math models (like Markov models) hit a wall. Because the "context" needed to predict the next letter keeps growing forever, these models get stuck. They can't remember enough history.
AI Gets Better with Depth: The Transformers did surprisingly well.
- Shallow AIs (1-2 layers): They were like toddlers. They could only remember the last few words. They performed poorly.
- Deep AIs (4-5 layers): They were like detectives. As they got deeper, they learned to look further back in the text. They started to mimic the behavior of the "Tree."
The "Genomic" Test: The authors even tested these AIs on real DNA data (which is also complex and non-random). The AIs trained on the fake "Story Tree" data were able to predict DNA patterns better than expected. This suggests the AI learned a general strategy for handling complex, changing rules, not just memorized the specific data.

The Takeaway:
The LZ78 Source is a "stress test." It's harder than anything we've used before. It shows that while AI is getting better at learning complex patterns, there is still a gap between what the AI can do and the theoretical limit of what is possible.

Summary in One Sentence

This paper built a self-growing, rule-shifting puzzle (the LZ78 Source) to prove that simple math models will always fail to predict it perfectly, but it also showed that deep learning AI is smart enough to learn how to solve these puzzles by looking further back in the story than ever before.

1. Problem Statement

The paper addresses a gap in information theory and machine learning: while the LZ78 compression algorithm is a celebrated tool for universal compression and has been used in gambling, prediction, and filtering, it has not been thoroughly investigated as a probability source (i.e., a generative model for data).

Existing studies on in-context learning (ICL) in Transformers often rely on stationary, Markovian, or variable-order Markov data. These models have fixed or bounded context depths. The authors propose a new class of non-stationary, non-Markovian sources derived from LZ78 Sequential Probability Assignments (SPAs). These sources are designed to:

Possess known fundamental entropic limits.
Exhibit complex, growing context dependencies (non-Markovian).
Create a "Jensen gap" between the true entropy rate and the performance of finite-state models, making them a rigorous benchmark for testing the limits of sequential prediction and ICL.

2. Methodology

A. Definition of the LZ78 Source

The authors define a stochastic process $X = (X_1, X_2, \dots)$ over a finite alphabet $\mathcal{A}$ , driven by an auxiliary process $B$ (parameters) and an LZ78 prefix tree structure.

Initialization: A prior distribution $\Pi$ is defined over the simplex of probability mass functions (PMFs) on $\mathcal{A}$ .
Generation Process:
1. A sequence of i.i.d. parameters $(\Theta_0, \Theta_1, \dots)$ is drawn from $\Pi$ .
2. An LZ78 prefix tree is grown incrementally.
3. At each step $t$ , the current node in the tree is assigned a parameter $\Theta$ (if not already assigned). Let this be $B_t$ .
4. The next symbol $X_t$ is generated according to the distribution $B_t$ (i.e., $X_t \sim B_t$ ).
5. The tree is traversed/expanded based on $X_t$ . If a new leaf is created, the process returns to the root.
Key Characteristic: The process is non-stationary. The distribution of the generating parameter $B_t$ changes over time depending on the tree's growth history, even though the underlying $\Theta$ values are i.i.d.

B. Theoretical Framework

The authors analyze the source using tools from ergodic theory and large deviations:

Empirical Measures: They study the convergence of the empirical distribution of $r$ -tuples of $(B, X)$ pairs.
Tree Recursion: They utilize the recursive structure of the LZ78 tree to derive moment bounds on the number of symbols generated per phrase (node visit).
Convergence Proofs: They employ Chebyshev's inequality, the Borel-Cantelli lemma, and martingale arguments to establish almost sure convergence results.

3. Key Contributions and Theoretical Results

The paper establishes four main theoretical properties of the LZ78 source:

A. Entropy Rate and Shannon-McMillan-Breiman (SMB) Property

Result: The entropy rate of the LZ78 source is $E[H(\Theta)]$ , where $\Theta \sim \Pi$ and $H$ is the Shannon entropy.
SMB Property: Despite being non-stationary, the normalized log-probability of a realization converges almost surely to the entropy rate:
$\lim_{n \to \infty} -\frac{1}{n} \log Q_{LZ, \Pi}(X^n) = E[H(\Theta)] \quad \text{a.s.}$
This confirms the source behaves "almost" like a stationary ergodic process regarding its log-probability convergence.

B. The "Jensen Gap" and Finite-State Compressibility

Result: The optimal log-loss achievable by any finite-state model (or $k$ -th order Markov model) on the LZ78 source converges almost surely to $H(E[\Theta])$ .
The Gap: Due to the concavity of entropy, $H(E[\Theta]) \geq E[H(\Theta)]$ . The difference is the Jensen gap, which equals the mutual information $I(\Theta; Y)$ .
Implication: Unlike stationary ergodic sources where finite-state compressibility equals the entropy rate, for the LZ78 source, finite-state models are fundamentally suboptimal. They cannot capture the growing context depth required to predict the source perfectly.

C. Local "Almost i.i.d." Behavior

Result: While the source is highly dependent globally, the finite-dimensional empirical distributions of its realizations converge almost surely to a deterministic i.i.d. law with parameter $E[\Theta]$ .
Significance: This property is reminiscent of good channel codes. It implies that locally, the source looks like a simple i.i.d. process with the average parameter, masking the complex global dependencies.

D. Divergence from Markov Laws

Result: The paper derives the relative entropy (divergence) rate between the LZ78 source and any $k$ -th order Markov law. It shows that higher-order Markov models do not asymptotically approximate the LZ78 source better than the constant i.i.d. model $E[\Theta]$ ; the gap remains dominated by the Jensen gap.

4. Experimental Results

The authors validate their theory and apply the source to study In-Context Learning (ICL) in Transformer models.

A. Simulation of Theoretical Properties

Convergence: Simulations using Dirichlet and Dirac-Dirichlet mixture priors confirm that the normalized log-probability of realizations converges to the theoretical entropy rate $E[H(\Theta)]$ .
Markov Loss: The log-loss of $k$ -th order Markov models converges to $H(E[\Theta])$ , demonstrating the Jensen gap. The gap is visible even for large $k$ , confirming the non-Markovian nature.

B. In-Context Learning in Transformers

The authors train Transformers (1–5 layers) on LZ78 source realizations and test them on:

Synthetic LZ78 Data:
- Transformers with sufficient depth (3–5 layers) and training time exhibit decreasing log-loss over the context, a hallmark of ICL.
- They outperform Context Tree Weighting (CTW) and fixed-order Markov models.
- However, a significant gap remains between the Transformer's performance and the true log-probability (the entropy rate), consistent with the theoretical limits.
Genomic Data (Out-of-Distribution):
- Models trained on LZ78 sources were tested on human genomic data (promoter/enhancer regions).
- Transfer Learning: The Transformers maintained decreasing log-loss curves on genomic data, suggesting they learned a general prediction algorithm (similar to CTW) rather than just memorizing the training distribution.
- Depth vs. Generalization: Deeper models (4–5 layers) performed well on training data but sometimes overfit, while 3-layer models showed better generalization to genomic data, acting as a form of regularization.

5. Significance and Impact

New Benchmark for ICL: The LZ78 source provides a "harder" and more discriminative benchmark than previous Markov-based datasets. Its context depth grows with sequence length, and the Jensen gap prevents finite-state models from achieving the entropy rate, forcing models to learn complex, non-Markovian dependencies.
Theoretical Insight into Non-Stationarity: The paper rigorously characterizes a non-stationary source that satisfies an SMB-type property, bridging the gap between universal compression theory and probabilistic modeling.
Understanding Transformer Capabilities: The experiments suggest that Transformers can learn to apply sequential prediction algorithms (like CTW) in-context, even on data with growing context requirements. However, they also highlight the limitations: even deep Transformers struggle to close the gap to the true entropy rate on these sources, likely due to the infinite context depth required.
Future Directions: The work opens avenues for studying sources based on other universal compressors, refining finite-sample bounds, and exploring sliding-window universal lossy compression.

In summary, this paper defines a novel probabilistic source rooted in the LZ78 algorithm, proves its unique entropic properties (specifically the Jensen gap between entropy rate and finite-state predictability), and leverages these properties to rigorously evaluate and understand the in-context learning capabilities of modern Transformer models.