Interestingness as an Inductive Heuristic for Future Compression Progress
Vincent Herrmann & Jürgen Schmidhuber · 2026
Read Interestingness as an Inductive Heuristic for Future Compression Progress by Vincent Herrmann & Jürgen Schmidhuber (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-14831.txt.
Introduction
Herrmann and team define interestingness as an inductive rule for future compression. The work tackles the block on the path to recursively self-improving systems. Using Kolmogorov complexity and algorithmic stats, they analyse profiles under Length, Algorithmic, and Speed priors. Past progress signals future discovery. Future gains depend exponentially on the recency of the last breakthrough. The Algorithmic Prior is far more hopeful than the Length Prior, yielding a quadratic rise in future discovery for the same profile. Results hold across three universal settings.
Catalog record
| CREATOR | Vincent Herrmann & Jürgen Schmidhuber |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 93042 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.14831
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Interestingness as an Inductive Heuristic for Future Compression Progress Vincent Herrmann & Jürgen Schmidhuber Abstract One of the bottlenecks on the way towards recursively self-improving systems is the challenge of interestingness : the ability to prospectively identify which tasks or data hold the potential for future progress. We formalize interestingness as an inductive heuristic for future compression progress and investigate its predictability using tools from Kolmogorov Complexity and Algorithmic Statistics. By analyzing complexity-runtime profiles under Length, Algorithmic, and Speed priors, we demonstrate that the inductive property of interestingness —the capacity for past progress to signal future discovery—is theoretically viable and empirically supported. We prove that expected future progress depends exponentially on the recency of the last observed breakthrough. Furthermore, we show that the Algorithmic Prior is significantly more optimistic than the Length Prior, yielding a quadratic increase in expected discovery for the same observed profile. These findings are experimentally confirmed across three diverse universal computational paradigms. 1 Introduction Figure 1: Minimalist depiction of a self-sustaining learning cycle. The Learning phase derives new skills or patterns from data, while the Generation phase creates novel artifacts. To sustain true open-endedness, the generation process must be guided by a criterion that distinguishes learnable structure from noise or already-acquired knowledge. A common notion of how a general recursively self-improving open-ended intelligence might be achieved is, in very simple terms, as a cycle between two alternating phases (see Figure 1 ): In the learning phase, a system uses a learning algorithm—e.g., gradient descent or Reinforcement Learning (RL) techniques—to extract patterns and regularities in the available data, or to gain the skills necessary to solve available problems and tasks. In the generation phase, the insights from the learning phase are used to produce novel artifacts (synthetic data, new tasks, hitherto unsolved problems). From these, the system can then again learn new capabilities, ideally leading to never-ending progress. To achieve true open-endedness, this cycle must be fully autonomous. It cannot rely on human-in-the-loop filtering, hand-crafted curricula, or synthetic data created by researchers. One example of such a system would be a Large Language Model (LLM) that is iteratively trained on self-generated data, see, for example 72 ; 74 . It is well known that a naive realization of such a setup leads to model collapse ( 60 ; 16 ) . However, there exist efforts to modify the generation process, or filter the generated data in such a way that continued learning is possible ( 34 ; 23 ; 22 ) . Another example would be an RL agent that pursues its own goals in an environment. The goals are chosen according to some intrinsic motivation criterion ( 56 ; 40 ; 13 ) . With the success of large-scale models trained with gradient descent and RL techniques, it can be argued that we have a good handle on the learning phase. Developing a generation phase that leads to continued progress, on the other hand, remains an open problem. In the framing of 24 , how can we generate artifacts that are both novel and learnable ? What criterion allows us to select the samples, problems, tasks from which the system can learn something meaningful? How can we distinguish between what is unlearnable, already learned, and so-far unknown but learnable? How can we tell if such an artifact is interesting ? In this paper, we argue that interestingness is a prospective inductive heuristic for future compression progress. Previous measures of interestingness often provide a post-hoc account of what was learned, while a self-improving system requires a way to predict what will be learned before committing significant computational resources. Our contributions are as follows: • We formalize the Inductive Property of Interestingness using Complexity and Runtime profiles, showing that future compression breakthroughs can be statistically predicted from the trajectory of past progress. • We prove that the primary predictor of future progress is stagnation length: the probability of a new compression ”drop” vanishes exponentially as the gap since the last progress increases. • We analyze how different priors over computable objects—Length, Algorithmic, and Speed—govern this predictability. We demonstrate that the Algorithmic Prior is significantly more “optimistic” than the Length Prior, yielding a quadratic increase in expected future progress for the same observed profile. • We provide empirical validation across three computationally universal paradigms (2-Tag systems, Rule 110 cellular automata, and Brainfuck), confirming that these theoretical trends hold in physically realizable regimes. We begin by discussing existing Interestingness measures, and arguing for the importance of prospective criteria. 2 Proposed Criteria of Interestingness In the following, we refer to the artifacts a cognitive system (the subject ) learns from as objects . This highlights the fact that interestingness is not necessarily an intrinsic property of an object in isolation, but rather a relational property between the object’s structure and the subject’s current internal state. Count-based, Space Coverage, and Maximum Entropy An object can be deemed interesting if it is uncommon —that is, if it has been encountered fewer times than other objects ( 66 ; 7 ; 67 ) . In high-dimensional spaces, this requires a density model to quantify novelty via smoothing. If an agent seeks to maximize the entropy of its state-visitation distribution, it will, in the limit, converge towards a policy that encounters all reachable objects with equal probability ( 21 ; 38 ) . In certain restricted settings, this is a reasonable measure: if it is possible for the cognitive system to encounter all reachable objects multiple times, uncommon objects yield the highest surprise in the Shannon sense. However, this does not naturally lead to open-ended learning; the system eventually converges towards a uniform occupancy and learning stagnates. Furthermore, if there are more possible objects than can ever be encountered, this measure of interestingness completely depends on the chosen form of coarse-graining or smoothing. In other words, it depends on a specific model . Prediction Error, Adversarial Criterion This notion moves beyond mere counting by introducing a predictive model. Here, interestingness is the inverse of the probability assigned by the model (the “adversarial” criterion). An object that is poorly predicted could be considered interesting ( 46 ; 47 ; 40 ) . However, this fails to distinguish between epistemic uncertainty (reducible through learning) and aleatoric uncertainty (irreducible randomness). This is the “Noisy TV” problem ( 53 ) : a subject using pure prediction error as a reward will get stuck observing a source of pure noise (like a static TV) because it is always unpredictable, yet provides zero learnable structure. Common approaches to tackle this problem share the insight that an object loses its interestingness once nothing new can be learned about it. Information Gain, Bayesian Surprise If our model is set up in a probabilistic way, for example as a belief distribution over a set of hypotheses, then we can measure the information gain an object yields. Concretely, this is quantified as the Kullback-Leibler divergence between the posterior distribution, given the object, and the prior distribution. In broader terms, an object is interesting to the extent it leads to new insights and changes the model’s “world view” ( 63 ; 26 ) . Once nothing new can be learned from an object, the information gain