mlsanityData to 14 Oct 2026

Interestingness as an Inductive Heuristic for Future Compression Progress

arXiv 2605.14831 ↗First posted 14 May 2026cs.AI cs.LGcited by 3

Not on the map. Why?

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.

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

28 of 73 references.

References · 28

  1. 2022Self-Instruct: Aligning Language Models with Self-Generated Instructionscited by 2,724
  2. 2017Curiosity-driven Exploration by Self-supervised Predictioncited by 1,194
  3. 2015Deep Learning and the Information Bottleneck Principlecited by 802
  4. 2018Recurrent World Models Facilitate Policy Evolutioncited by 785
  5. 2024Genie: Generative Interactive Environmentscited by 747
  6. 2016Unifying Count-Based Exploration and Intrinsic Motivationcited by 639
  7. 2020Planning to Explore via Self-Supervised World Modelscited by 368
  8. 2016#Exploration: A Study of Count-Based Exploration for Deep Reinforcement Learningcited by 309
  9. 2019Self-Supervised Exploration via Disagreementcited by 265
  10. 2018Provably Efficient Maximum Entropy Explorationcited by 242
  11. 2023Language Modeling Is Compressioncited by 225
  12. 2018Model-Based Active Explorationcited by 105
16 more
  1. 2020Autotelic Agents with Intrinsically Motivated Goal-Conditioned Reinforcement Learning: a Short Surveycited by 85
  2. 2024Model Collapse Demystified: The Case of Regressioncited by 82
  3. 2024Open-Endedness is Essential for Artificial Superhuman Intelligencecited by 80
  4. 2024OMNI-EPIC: Open-endedness via Models of human Notions of Interestingness with Environments Programmed in Codecited by 74
  5. 2018The Description Length of Deep Learning Modelscited by 72
  6. 2023OMNI: Open-endedness via Models of human Notions of Interestingnesscited by 70
  7. 2013Active Learning of Inverse Models with Intrinsically Motivated Goal Exploration in Robotscited by 58
  8. 2015On Learning to Think: Algorithmic Information Theory for Novel Combinations of Reinforcement Learning Controllers and Recurrent Neural World Modelscited by 55
  9. 2026From Entropy to Epiplexity: Rethinking Information for Computationally Bounded Intelligencecited by 41
  10. 2021Multi-task curriculum learning in a complex, visual, hard-exploration domain: Minecraftcited by 35
  11. 2022Curious Exploration via Structured World Models Yields Zero-Shot Object Manipulationcited by 31
  12. 2025Embedded Universal Predictive Intelligence: a coherent framework for multi-agent learningcited by 9
  13. 2025MAGELLAN: Metacognitive predictions of learning progress guide autotelic LLM agents in large goal spacescited by 7
  14. 2025Measuring In-Context Computation Complexity via Hidden State Predictioncited by 3
  15. 2022An Algorithmic Approach to Emergencecited by 1
  16. 2025Multiple Token Divergence: Measuring and Steering In-Context Computation Densitycited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 3.

3 papers.

  1. 2026Recursive Self-Improvement in AI: From Bounded Self-Refinement to Autonomous Research Loopscited by 35
  2. 2026Self-Improvements in Modern Agentic Systems: A Surveycited by 19
  3. 2026Flood and Harvest: The Provable Necessity of Trivia for Generating Valuable Mathematics via the Lens of Language Generation in the Limitcited by 2