Interestingness as an Inductive Heuristic for Future Compression Progress: The Math Behind Schmidhuber's Curiosity

Forum topic · 小凯 · 2026-05-16

Summary

A Chinese forum post dissects the paper "Interestingness as an Inductive Heuristic for Future Compression Progress" by Vincent Herrmann and Jürgen Schmidhuber (arXiv:2605.14831, IDSIA/KAUST). The paper formalizes "interestingness" as expected future compression progress, evaluated before spending resources—an answer to how autonomous systems decide what to learn. It introduces two mathematical profiles: D_x (complexity vs. runtime) and P_x (log-size vs. complexity), unified via the Busy Beaver function. Theorems show that under a Length Prior, probability of a future compression breakthrough decays as 2^-(t-m̂) with stagnation length, while an Algorithmic (Solomonoff) Prior yields larger expected discoveries, and the Speed Prior predicts near-zero progress. Experiments on 2-tag systems, Rule 110, and Brainfuck confirm the negative correlation between stagnation length and expected progress. The framework also maps to SGD training curves, chain-of-thought reasoning, and model scaling as projections of the same structure. Key takeaway: systems should remember only what recently showed compression breakthroughs.

This post is a deep-dive analysis of "Interestingness as an Inductive Heuristic for Future Compression Progress" by Vincent Herrmann & Jürgen Schmidhuber (arXiv:2605.14831, Swiss AI Lab IDSIA/USI/SUPSI + KAUST). Full translation/summary follows.

Why this paper matters

The bottleneck of current AI is not learning ability, but not knowing what to learn:

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

Schmidhuber has asked since 1991: *how does an autonomous system 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 post-hoc. An open-ended system 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 gain can be expected in the future.

Mathematical framework: two curves

D_x — Complexity vs. Runtime Profile:

D_x = \{(r, c) \mid K^r(x) \le c\}

x-axis: runtime r (allowed compute steps); y-axis: complexity c (shortest program length). The curve descends from fast-but-verbose programs toward slow-but-minimal deep regularities.

P_x — Log-Size vs. Complexity Profile:

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

x-axis: model complexity i; y-axis: log set size j — how large a set an i-bit model can localize x within.

Via the Busy Beaver function BB(k), the two profiles are related by the affine map $(i, j) \mapsto (BB(i), i+j)$ : a "drop" in P_x (model breakthrough) corresponds to a "drop" in D_x (runtime breakthrough).

Three worldviews: Length / Algorithmic / Speed Prior

Length Prior: world is random; $L(x) = 2^{-(2|x|+2)}$ . Conservative.
Algorithmic Prior (Solomonoff): world is structured; $M(x) = \sum_{p: U(p)=x} 2^{-|p|}$ . Optimistic, favors short-program-describable objects.
Speed Prior: if a fast solution exists, it has been found already; $S(x) = \sum_{i=1}^{\infty} \sum_{p \to_i x} 2^{-(i+|p|)}$ . Most conservative; penalizes long runtimes.

Key results: stagnation length predicts the future

Stagnation length $t - \hat{m}$ : distance in complexity from the last compression breakthrough.

Theorem 1 (Length Prior): P(further breakthrough) ≈ $2^{-(t-\hat{m})}$ ; expected progress ≈ $\hat{k} - 2$
Theorem 2 (Algorithmic Prior): same decay in probability, but expected progress ≈ $(\hat{k} + t)/2$
Theorem 3: Algorithmic Prior's expected discovery is ~ $\frac{1}{4}(\hat{k}-t)^2$ times that of the Length Prior
Theorem 4 (Speed Prior): P(further breakthrough) ≈ 0; expected progress ≈ 0

Core insight: *interesting things are those that recently exhibited a compression breakthrough.* Small stagnation length → large expected future progress; long stagnation → exponential decay. This is a mathematical consequence of algorithmic information theory, not a matter of taste.

Experimental validation

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

1. 2-Tag systems (Post, 1943): alphabet {a, b, c, H}, ~120M programs, 100k steps 2. Rule 110 cellular automaton (Wolfram, 1983): state size 512, cyclic boundary, ~34M simulations 3. Brainfuck (Müller, 1993): 7 instructions, programs ≤ length 11, ~2.3B programs

Findings: the Algorithmic Prior indeed shows higher expected discovery rate than the Length Prior; the Speed Prior's conservative prediction is weakened by physically realizable runtimes (Rule 110 needs a "warm-up" period); the negative correlation between stagnation length and expected progress holds in all systems.

Connections to modern AI

Neural networks & SGD: SGD trajectories move through P_x (weight complexity on x-axis, NLL on y-axis). Moving along the slope-−1 line = pure memorization; a "drop" below it = genuine structural discovery. This explains the plateau → drop pattern in training loss curves.
Chain-of-Thought: CoT maps to D_x (reasoning steps = runtime, answer description length = complexity). Significant y-axis decrease = reasoning breakthrough; no decrease = the chain is idling. Reasoning-time compute in o1/o3/R1 is essentially *spending runtime to find compression breakthroughs*.
Model scaling: training larger models maps to P_x (parameter count vs. training NLL). Breaking the −1 slope = discovering new structure; otherwise just added memorization capacity.

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

Limitations and open problems

Busy Beaver incomputability: BB unifies time scales but grows faster than any computable function — the price of "abstract machine independence."
Choice of prior: real AI systems must pick a prior; the paper calls this "choosing a worldview" but offers no selection method.
Scale-free emergence: natural phenomena (biology, climate) and some artificial structures (Mandelbrot set, Game of Life) show compression breakthroughs at all scales — a key future direction.
Cross-domain transfer: whether progress in one domain (vision) predicts potential in another (language) is left unaddressed by the content-agnostic framework.

Conclusion

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

> Don't try to remember everything. Remember only what 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*.