# Interestingness as an Inductive Heuristic for Future Compression Progress

arXiv: https://arxiv.org/abs/2605.14831 · HTML: https://mlsanity.com/paper/2605.14831/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 28 of its 73 references that are in the map.
- First posted on arXiv 14 May 2026.

## Builds on (most cited first, 28 of 28)

- [Self-Instruct: Aligning Language Models with Self-Generated Instructions](https://mlsanity.com/paper/2212.10560/) (2022)
- [Curiosity-driven Exploration by Self-supervised Prediction](https://mlsanity.com/paper/1705.05363/) (2017)
- [Deep Learning and the Information Bottleneck Principle](https://mlsanity.com/paper/1503.02406/) (2015)
- [Recurrent World Models Facilitate Policy Evolution](https://mlsanity.com/paper/1809.01999/) (2018)
- [Genie: Generative Interactive Environments](https://mlsanity.com/paper/2402.15391/) (2024)
- [Unifying Count-Based Exploration and Intrinsic Motivation](https://mlsanity.com/paper/1606.01868/) (2016)
- [Planning to Explore via Self-Supervised World Models](https://mlsanity.com/paper/2005.05960/) (2020)
- [#Exploration: A Study of Count-Based Exploration for Deep Reinforcement Learning](https://mlsanity.com/paper/1611.04717/) (2016)
- [Self-Supervised Exploration via Disagreement](https://mlsanity.com/paper/1906.04161/) (2019)
- [Provably Efficient Maximum Entropy Exploration](https://mlsanity.com/paper/1812.02690/) (2018)
- [Language Modeling Is Compression](https://mlsanity.com/paper/2309.10668/) (2023)
- [Model-Based Active Exploration](https://mlsanity.com/paper/1810.12162/) (2018)
- [Autotelic Agents with Intrinsically Motivated Goal-Conditioned Reinforcement Learning: a Short Survey](https://mlsanity.com/paper/2012.09830/) (2020)
- [Model Collapse Demystified: The Case of Regression](https://mlsanity.com/paper/2402.07712/) (2024)
- [Open-Endedness is Essential for Artificial Superhuman Intelligence](https://mlsanity.com/paper/2406.04268/) (2024)
- [OMNI-EPIC: Open-endedness via Models of human Notions of Interestingness with Environments Programmed in Code](https://mlsanity.com/paper/2405.15568/) (2024)
- [The Description Length of Deep Learning Models](https://mlsanity.com/paper/1802.07044/) (2018)
- [OMNI: Open-endedness via Models of human Notions of Interestingness](https://mlsanity.com/paper/2306.01711/) (2023)
- [Active Learning of Inverse Models with Intrinsically Motivated Goal Exploration in Robots](https://mlsanity.com/paper/1301.4862/) (2013)
- [On Learning to Think: Algorithmic Information Theory for Novel Combinations of Reinforcement Learning Controllers and Recurrent Neural World Models](https://mlsanity.com/paper/1511.09249/) (2015)
- [From Entropy to Epiplexity: Rethinking Information for Computationally Bounded Intelligence](https://mlsanity.com/paper/2601.03220/) (2026)
- [Multi-task curriculum learning in a complex, visual, hard-exploration domain: Minecraft](https://mlsanity.com/paper/2106.14876/) (2021)
- [Curious Exploration via Structured World Models Yields Zero-Shot Object Manipulation](https://mlsanity.com/paper/2206.11403/) (2022)
- [Embedded Universal Predictive Intelligence: a coherent framework for multi-agent learning](https://mlsanity.com/paper/2511.22226/) (2025)
- [MAGELLAN: Metacognitive predictions of learning progress guide autotelic LLM agents in large goal spaces](https://mlsanity.com/paper/2502.07709/) (2025)
- [Measuring In-Context Computation Complexity via Hidden State Prediction](https://mlsanity.com/paper/2503.13431/) (2025)
- [An Algorithmic Approach to Emergence](https://mlsanity.com/paper/2205.12997/) (2022)
- [Multiple Token Divergence: Measuring and Steering In-Context Computation Density](https://mlsanity.com/paper/2512.22944/) (2025)

## Built on by (most cited first, 3 of 3)

- [Recursive Self-Improvement in AI: From Bounded Self-Refinement to Autonomous Research Loops](https://mlsanity.com/paper/2607.07663/) (2026)
- [Self-Improvements in Modern Agentic Systems: A Survey](https://mlsanity.com/paper/2607.13104/) (2026)
- [Flood and Harvest: The Provable Necessity of Trivia for Generating Valuable Mathematics via the Lens of Language Generation in the Limit](https://mlsanity.com/paper/2606.14688/) (2026)

## Abstract (arXiv)

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.