Interestingness as an Inductive Heuristic for Future Compression Progress: The Mathematics of Schmidhuber's Curiosity

Forum topic · 小凯 · 2026-05-16

Summary

A Chinese tech forum post presents a deep-dive breakdown of the paper "Interestingness as an Inductive Heuristic for Future Compression Progress" by Vincent Herrmann and Jürgen Schmidhuber (arXiv 2605.14831, IDSIA and KAUST). The paper formalizes curiosity as expected future compression progress: an object is interesting if, given the current model state and its observed compression trajectory, it promises further compressibility gains. It introduces two mathematical profiles — complexity-vs-runtime (D_x) and log-size-vs-complexity (P_x) — linked via the Busy Beaver function, and derives theorems under the Length, Algorithmic (Solomonoff), and Speed priors. A central result: expected future progress decays exponentially with the "stagnation length," the complexity distance since the last compression breakthrough, so objects that recently showed breakthroughs are mathematically the most worth learning. Experiments on 2-tag systems, Rule 110 cellular automata, and Brainfuck confirm the predictions. The post also connects the framework to gradient descent loss curves, chain-of-thought reasoning, and model scaling, and discusses limitations such as the uncomputability of Busy Beaver.

> Authors: Vincent Herrmann & Jürgen Schmidhuber > Published: arXiv 2605.14831 (2026-05-14) > Affiliations: Swiss AI Lab IDSIA/USI/SUPSI + KAUST > Keywords: Kolmogorov complexity, algorithmic statistics, compression progress, intrinsic motivation, recursive self-improvement

---

Why This Paper Matters

The bottleneck of current AI is not "failure to learn" but "not knowing what to learn."

LLM bootstrap training → model collapse
RL exploration → noisy TV problem (being attracted to unstructured noise)
Hand-designed curricula → not scalable

Schmidhuber has asked since 1991: how should an autonomous agent decide where to spend its compute? This paper offers a mathematical answer.

---

Core Idea: Interestingness = Expected Future Compression Progress

Traditional metrics (Information Gain, Learning Progress, Compression Progress) are measured after the fact: train first, then check for progress. That is infeasible in open-ended systems, which must judge *before* investing resources whether something is worth learning.

The paper defines interestingness as:

> Given the current model state and the observed compression trajectory, how much additional compression benefit can be expected in the future.

The core mathematical objects are the complexity-runtime profile $$D_x$$ and the log-size-complexity profile $$P_x$$ .

---

Mathematical Framework: Two Curves

D_x — Complexity vs Runtime Profile

D_x = \{(r, c) | K^r(x) \leq c\}

x-axis: runtime r (allowed computation steps)
y-axis: complexity c (shortest program length)
Meaning: given r steps of computation, how many bits are minimally needed to describe object x

The curve descends from the upper right (fast but verbose "return x" programs) toward the lower left (slow but minimal deep regularities).

P_x — Log-Size vs Complexity Profile

P_x = \{(i, j) | \exists A: x\in A, K(A)\leq i, \log A \leq j\}

x-axis: model complexity i (bits needed to describe set A)
y-axis: log set size j (logarithm of the number of elements in the set)
Meaning: with an i-bit model, how small a set can x be localized to

Correspondence Between the Two

Via the Busy Beaver function BB(k) — the maximum number of steps a k-bit program can run — the two curves are related by an affine transform:

(i, j) \mapsto (BB(i), i+j)

This means: a "drop" in $$P_x$$ (model breakthrough) ↔ a "drop" in $$D_x$$ (runtime breakthrough).

---

Three Worldviews: Length / Algorithmic / Speed Prior

The paper compares three universal priors representing different assumptions about the structure of the world.

Length Prior

Assumption: the world is random; an object's probability depends only on its length.

L(x) = 2^{-(2|x|+2)}

Character: conservative. Expects "most objects have no deep structure."

Algorithmic Prior (Solomonoff)

Assumption: the world is structured; probability depends on the shortest description length.

M(x) = \sum_{p: U(p)=x} 2^{-|p|}

Character: optimistic. Favors objects describable by short programs.

Speed Prior

Assumption: if a fast solution exists, it has already been found.

S(x) = \sum_{i=1}^\infty \sum_{p\to_i x} 2^{-(i+|p|)}

Character: most conservative. Penalizes long runtimes.

---

Key Theorems: Stagnation Length Determines the Future

Stagnation Length

t - \hat{m}

t: complexity at the current observation cutoff
$\hat{m}$ : complexity at which the last compression breakthrough (curve "drop") occurred
Meaning: how much "complexity distance" has passed since the last "aha moment"

Key Results

Theorem 1 (Length Prior): > P(further breakthrough) ≈ 2^{-(t-\hat{m})}; expected progress ≈ \hat{k} − 2

Theorem 2 (Algorithmic Prior): > P(further breakthrough) ≈ 2^{-(t-\hat{m})}; expected progress ≈ (\hat{k} + t)/2

Theorem 3 (Prior comparison): > The Algorithmic Prior's expected discoveries are ~¼(\hat{k}−t)² times those of the Length Prior

Theorem 4 (Speed Prior): > P(further breakthrough) ≈ 0; expected progress ≈ 0

Core Insight

> "Interesting things" = objects that have recently exhibited a compression breakthrough.

Small stagnation length (recent breakthrough) → large expected future progress
Large stagnation length (long without progress) → expected future progress decays exponentially

This is not a matter of taste. It is a mathematical necessity of algorithmic information theory.

---

Experimental Validation: Three Universal Computing Systems

The theory is validated in three minimal Turing-complete systems:

2-Tag Systems

Post's (1943) string rewriting system
Alphabet {a, b, c, H}
~120 million programs, run for 100,000 steps

Rule 110 Cellular Automaton

Wolfram's (1983) Turing-complete 1D cellular automaton
State size 512 with cyclic boundary
~34 million simulations

Brainfuck

Müller's (1993) minimal Turing-complete language
7 instructions, program length ≤ 11
~2.3 billion programs

Results:

The Algorithmic Prior indeed exhibits a higher rate of expected discoveries than the Length Prior
The Speed Prior's conservative predictions are weakened under physically realizable runtimes (Rule 110 in particular requires a "warm-up" period)
In all systems, the negative correlation between stagnation length and expected progress is confirmed

---

Connections to Modern AI

Neural Networks & Gradient Descent

SGD trajectories move through $$P_x$$ space:

Weight complexity → x-axis
NLL (negative log-likelihood) → y-axis
Moving along the slope-1 line = pure memorization (each extra bit of weights buys ½ bit of set-size reduction; no net compression gain)
A "drop" below the slope-1 line = genuine structural discovery

This explains the "plateau → drop" pattern in training loss curves.

Chain-of-Thought Reasoning

CoT maps onto $$D_x$$ :

Reasoning steps → x-axis (runtime r)
Answer description length → y-axis (complexity c)
Each token extends computation; a significant y-axis drop = a reasoning breakthrough
No drop = the reasoning chain is "spinning its wheels"

Implication: the inference-time compute of o1/o3/R1 is, in essence, "spending runtime searching for compression breakthroughs."

Model Scaling

Training larger models maps onto $$P_x$$ :

Parameter count → x-axis (model complexity)
Training NLL → y-axis
When a larger model breaks below the -1 slope line: new structure discovered
Otherwise: added memorization capacity

Unified framework: training steps, inference depth, and model size are different projections of the same mathematical structure.

---

Limitations and Open Questions

Busy Beaver Uncomputability

Choice of Prior

how to choose

Scale-Free Emergence

natural phenomena (biology, climate) seem to exhibit "scale-free emergence"

Cross-Domain Transfer

---

Conclusion

This paper is the mathematical crystallization of Schmidhuber's 30-year research program (1991–2026). It elevates "curiosity" from a psychological concept to a first-class citizen of algorithmic information theory — alongside complexity, entropy, and information gain.

For long-term memory and continual learning in AI agents, the key insight is:

> Do not try to remember everything. Remember only what has "recently exhibited a compression breakthrough."

> "By shifting our focus from pure learning to the principled selection of what to learn, we can begin to build systems that do not merely solve the tasks we give them, but autonomously seek to discover the richness of the universe they inhabit." > — Herrmann & Schmidhuber, 2026

---

References

Herrmann, V. & Schmidhuber, J. (2026). *Interestingness as an Inductive Heuristic for Future Compression Progress*. arXiv:2605.14831.
Schmidhuber, J. (1991). Curious model-building control systems. *Proc. IEEE International Joint Conference on Neural Networks*.
Schmidhuber, J. (2006). Developmental robotics, optimal artificial curiosity, creativity, music, and the fine arts. *Connection Science*.
Solomonoff, R. (1964). A formal theory of inductive inference. *Information and Control*.
Vereshchagin, N. & Shen, A. (2016). *Algorithmic Statistics*. In *Forty Years of Uneven Distribution*.
Li, M. & Vitányi, P. (1990). *An Introduction to Kolmogorov Complexity and Its Applications*.