🤖 machine learning

Interestingness as an Inductive Heuristic for Future Compression Progress

This paper formalizes "interestingness" as an inductive heuristic for future compression progress, demonstrating through theoretical analysis and empirical experiments that past breakthroughs exponentially predict future discovery, with the Algorithmic Prior offering significantly more optimistic projections than the Length Prior.

Original authors: Vincent Herrmann, Jürgen Schmidhuber

Published 2026-05-15

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Vincent Herrmann, Jürgen Schmidhuber

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 Problem: How to Keep Learning Forever

Imagine you have a robot that is supposed to learn forever, getting smarter and smarter on its own without a human teacher. This is called "open-ended intelligence."

The robot has two jobs:

Learning: It studies data to find patterns (like a student reading a textbook).
Generating: It creates new problems or data to study next (like a teacher making a new quiz).

The hard part is the Generation phase. If the robot just makes random noise, it learns nothing. If it makes things it already knows, it gets bored. It needs a way to pick the perfect new puzzle: something that isn't too easy (boring) and not too hard (impossible), but just right to teach it something new.

The paper asks: How does a robot know which new puzzle is "interesting" before it even tries to solve it?

The Core Idea: "Interestingness" is a Crystal Ball

The authors argue that "interestingness" isn't about how cool a thing looks. It's a prediction tool. It's a way to guess: "If I spend time studying this, will I get a 'Aha!' moment later?"

They call this Compression Progress.

Compression is like summarizing a long story into a short sentence. If you can summarize a lot of data with a simple rule, you have "compressed" it.
Progress happens when you find a new rule that makes your summary even shorter.

The paper suggests that a good "interestingness" detector should look at the robot's history and ask: "Based on how we've been learning so far, is there a good chance we'll find a new shortcut soon?"

The Experiment: The "Stagnation" Meter

To test this, the authors looked at the history of the robot's learning as a graph. Imagine a hiker climbing down a mountain (the mountain represents the difficulty of the data).

Every time the hiker finds a new, shorter path down, that's a "breakthrough" or a "drop" in the graph.
Stagnation Length: This is the distance the hiker has walked since the last time they found a shortcut.

The Main Discovery:
The paper proves mathematically that time matters more than size.

If the robot found a breakthrough yesterday, there is a high chance it will find another one today.
If the robot hasn't found a breakthrough in a long time, the chance of finding one soon drops off like a cliff.

It's like fishing. If you just caught a big fish, the water is likely full of them, so you should keep casting in that spot. If you've been casting in the same spot for three hours with no bites, the odds of catching a fish right now are almost zero. You should move to a new spot.

The Three "Worlds" (Priors)

The authors tested this idea in three different "universes" (mathematical models of how data is created) to see if the rule holds up.

The "Random Typing" World (Length Prior): Imagine a monkey typing on a keyboard. Short strings are more common than long ones. In this world, if you haven't found a shortcut in a while, it's very unlikely you will find one soon.
The "Simple Program" World (Algorithmic Prior): Imagine the universe is generated by the simplest possible computer programs. This is the most "optimistic" world. Here, even if you've been stuck for a while, there's still a decent chance a big breakthrough is coming, but it's still much more likely to happen soon after the last one.
The "Fast Execution" World (Speed Prior): This world hates slow programs. If a shortcut exists, it would have been found already. In this world, if you haven't found a shortcut, you probably never will. It's the most pessimistic view.

The Result: In all three worlds, the rule held true: The most recent breakthrough is the best predictor of the next one. The longer you wait without a win, the less likely a win is coming.

The "Optimistic" vs. "Pessimistic" Robot

The paper found something surprising about the "Simple Program" world (Algorithmic Prior). It is much more optimistic than the "Random Typing" world.

In the "Random" world, if you are stuck, you are probably stuck forever.
In the "Simple Program" world, if you are stuck, you might just be waiting for the next big discovery, and the potential reward is huge (quadratically higher).

This suggests that if our AI assumes the world is made of simple, discoverable patterns, it should keep trying to learn from things that recently taught it something, even if it's been a little while.

The Real-World Test

The authors didn't just do math; they ran actual computer simulations using three different types of "computers" (2-Tag systems, Rule 110 cellular automata, and Brainfuck code).

They generated millions of programs and watched how they "learned" (compressed data).
The Result: The real-world data matched the math perfectly. The "stagnation length" (time since the last win) was the strongest signal for whether a new win was coming.

The Bottom Line

For a robot to learn forever without a human boss, it needs a simple rule for choosing what to study next:
"Focus on the things that recently taught you something new."

If a task has been boring for a long time, stop wasting time on it. If it just gave you a new insight, stick with it, because the next big breakthrough is likely just around the corner. This "Inductive Property of Interestingness" is the compass that keeps self-improving systems moving forward.

Technical Summary: Interestingness as an Inductive Heuristic for Future Compression Progress

1. Problem Statement

The paper addresses a critical bottleneck in the development of recursively self-improving, open-ended intelligent systems: the challenge of interestingness. While current machine learning paradigms (e.g., Gradient Descent, RL) have achieved significant success in the learning phase (extracting patterns from data), the generation phase remains an open problem. Specifically, how can an autonomous system prospectively identify which tasks, data, or artifacts hold the potential for future progress without relying on human-in-the-loop filtering or hand-crafted curricula?

Existing measures of interestingness (e.g., prediction error, information gain, learning progress) are largely post-hoc: they quantify what has already been learned after computational resources have been expended. A self-improving system requires a prospective heuristic to predict future learnability before committing significant resources, distinguishing between the unlearnable, the already learned, and the unknown-but-learnable.

2. Methodology

The authors formalize "interestingness" as an inductive heuristic for future compression progress. They utilize tools from Algorithmic Information Theory (AIT) and Algorithmic Statistics to analyze the relationship between past progress and future discovery.

Core Concepts

Compression Progress: Interestingness is defined as the expected reduction in the total description length (model complexity + data residual) when a new object is incorporated. This aligns with the Minimum Description Length (MDL) principle.
Complexity vs. Runtime Profiles ( $D_x$ ): The authors analyze the trajectory of the shortest program length $K_r(x)$ required to compute a string $x$ within a runtime budget $r$ . A "drop" in this profile represents a compression breakthrough.
Log-Size vs. Complexity Profiles ( $P_x$ ): To leverage algorithmic statistics, they utilize the profile describing the log-size of the smallest set containing $x$ for a given model complexity.
The $P_x \leftrightarrow D_x$ Correspondence: Using the Busy Beaver function ($BB$), the authors establish an affine transformation between the log-size/complexity profile and the complexity/runtime profile. This allows theoretical results derived from $P_x$ to be mapped to the computationally relevant $D_x$ domain.
Inductive Property: The central inquiry is whether the shape of a profile observed up to a cutoff $t$ (the "stagnation length" $t - \hat{m}$ , where $\hat{m}$ is the last observed drop) can statistically predict the existence and magnitude of future drops (further compression).

Priors Investigated

The study evaluates the inductive properties under three distinct priors over computable strings:

Length Prior ( $L$ ): Uniform probability over string lengths.
Algorithmic Prior ( $M$ ): Solomonoff's prior, favoring strings with short descriptions (programs).
Speed Prior ( $S$ ): Penalizes both program length and runtime, favoring fast-computable strings.

3. Key Contributions

The paper makes the following theoretical and empirical contributions:

Formalization of Inductive Interestingness: The authors prove that the inductive property of interestingness is theoretically viable. They demonstrate that the stagnation length (the gap since the last observed compression breakthrough) is the primary predictor of future progress.
Exponential Decay of Discovery Probability: They prove that the probability of a new compression "drop" vanishes exponentially as the stagnation length increases. This implies that the most promising objects for further engagement are those exhibiting the most recent progress.
Comparison of Priors:
- The Algorithmic Prior is shown to be significantly more "optimistic" than the Length Prior. For the same observed profile, the Algorithmic Prior yields a quadratic increase in expected future compression progress compared to the Length Prior.
- The Speed Prior is the most "conservative," assuming that if a faster compression method existed, it would have already been found, leading to near-zero expected future progress in many cases.
Empirical Validation: The theoretical trends are confirmed across three computationally universal paradigms: 2-Tag systems, Rule 110 cellular automata, and Brainfuck (BF). In all cases, the data supports the finding that recent progress is a strong indicator of future compressibility, particularly under the Algorithmic Prior.

4. Results

Theoretical Bounds: Under the Length and Algorithmic Priors, the probability of a future drop $p(m_x \ge t | \hat{P})$ is approximately $2^{-(t-\hat{m})}$ . The expected future compression progress also decays exponentially with the stagnation length.
Prior Sensitivity: While the exponential decay holds for all priors, the magnitude of expected progress differs. The Algorithmic Prior predicts significantly higher potential for discovery than the Length Prior, while the Speed Prior predicts minimal additional progress.
Empirical Confirmation: Experiments on 2-Tag, Rule 110, and Brainfuck systems mirror the theoretical curves. As the number of steps since the last observed progress increases, the average remaining compression progress vanishes. The results for the Speed Prior in empirical settings are less pronounced than in the theoretical limit (due to the lack of extremely short runtimes in the specific experimental setups), but the general trend of stagnation reducing expected progress holds.

5. Significance and Claims

The paper argues that interestingness should be viewed not as an intrinsic property of an object, but as a relational, prospective heuristic based on the trajectory of compression progress.

Autonomy: By formalizing interestingness as a prospective assessment, the paper provides a principled basis for autonomous systems to select tasks without human intervention. It suggests that systems should prioritize objects where the "stagnation length" is short.
Theoretical Grounding: The work grounds the intuitive concept of "curiosity" or "interestingness" in the rigorous framework of Algorithmic Information Theory, moving beyond heuristic definitions to provable inductive properties.
Limitations and Future Directions: The authors modestly note that their theoretical results rely on the Busy Beaver function, which involves runtimes that are physically unrealizable. However, they argue that the machine-independent nature of these results reflects the intrinsic algorithmic properties of objects. They acknowledge that in structured domains (e.g., biological systems, fractals), the history of progress might matter more than just the recency of the last drop (scale-free emergence), a property not fully captured by the current priors. They conclude that future work must focus on developing introspective models capable of explicitly modeling their own "compression frontiers" to achieve true open-endedness.