CoChat
Sign Up
PreprintCited by 1Computability, Logic, AI AlgorithmsAlgorithms and Data CompressionEvolutionary Algorithms and Applications

Interestingness as an Inductive Heuristic for Future Compression Progress

Open access
Herrmann, Vincent, Schmidhuber, Jürgen·2026·arXiv
DOI 10.48550/arxiv.2605.14831arXiv 2605.14831
Open this paper in CoChat — free accountOpen PDF

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.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.2605.14831

Cites

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Framing 'interestingness' as an inductive heuristic for future compression progress is analyzable with algorithmic information theory and identifies it as a bottleneck on the way to recursively self-improving systems.

    “framing 'interestingness' - the prospective identification of which tasks hold potential for future progress - as an inductive heuristic for future compression progress, analyzable with the tools of algorithmic information theory, and identifying it explicitly as a bottleneck on the way to recursively self-improving systems [155].”

    From Recursive Self-Improvement in AI: From Bounded Self-Refinement to Autonomous Research Loops (2026) · cites this paper as [155]

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

No references could be resolved yet.

Research works printed but not linked: 68

  1. Antunes, L., Bauwens, B., Souto, A., and Teixeira, A. Sophistication vs logical depth. Theory of Computing Systems, 60(2):280-298, 2017.
  2. Barabási, A.-L. and Albert, R. Emergence of scaling in random networks. science, 286(5439): 509-512, 1999.
  3. Baranes, A. and Oudeyer, P.-Y. Active learning of inverse models with intrinsically motivated goal exploration in robots. Robotics and Autonomous Systems, 61(1):49-73, 2013.
  4. Bauwens, B. Computability in statistical hypotheses testing, and characterizations of independence and directed influences in time series using Kolmogorov complexity. PhD thesis, Ghent University, 2010.
  5. Bédard, C. A. and Bergeron, G. An algorithmic approach to emergence. Entropy, 24(7):985, 2022.
  6. Bellemare, M., Srinivasan, S., Ostrovski, G., Schaul, T., Saxton, D., and Munos, R. Unifying count- based exploration and intrinsic motivation. Advances in neural information processing systems, 29, 2016.
  7. Bennett, C. H. Logical depth and physical complexity. In The Universal Turing Machine: A Half Century Survey, volume 1, pp. 227-258. Oxford University Press, Oxford and Kammerer & Un- verzagt, Hamburg, 1988.
  8. Blier, L. and Ollivier, Y. The description length of deep learning models. Advances in Neural Information Processing Systems, 31, 2018.
  9. Brant, J. C. and Stanley, K. O. Minimal criterion coevolution: a new approach to open-ended search. In Proceedings of the Genetic and Evolutionary Computation Conference, pp. 67-74, 2017.
  10. Bruce, J., Dennis, M. D., Edwards, A., Parker-Holder, J., Shi, Y., Hughes, E., Lai, M., Mavalankar, A., Steigerwald, R., Apps, C., et al. Genie: Generative interactive environments. In Forty-first International Conference on Machine Learning, 2024.
  11. Cocke, J. and Minsky, M. Universality of tag systems with p= 2. Journal of the ACM (JACM), 11 (1):15-20, 1964.
  12. Colas, C., Karch, T., Sigaud, O., and Oudeyer, P.-Y. Autotelic agents with intrinsically motivated goal-conditioned reinforcement learning: a short survey. Journal of Artificial Intelligence Re- search, 74:1159-1199, 2022.
  13. Cook, M. et al. Universality in elementary cellular automata. Complex systems, 15(1):1-40, 2004.
  14. Delétang, G., Ruoss, A., Duquenne, P.-A., Catt, E., Genewein, T., Mattern, C., Grau-Moya, J., Wenliang, L. K., Aitchison, M., Orseau, L., et al. Language modeling is compression. arXiv preprint arXiv:2309.10668, 2023. · arXiv
  15. Dohmatob, E., Feng, Y., and Kempe, J. Model collapse demystified: The case of regression. Ad- vances in Neural Information Processing Systems, 37:46979-47013, 2024.
  16. Faldor, M., Zhang, J., Cully, A., and Clune, J. Omni-epic: Open-endedness via models of human notions of interestingness with environments programmed in code. arXiv preprint arXiv:2405.15568, 2024. · arXiv
  17. Finzi, M., Qiu, S., Jiang, Y., Izmailov, P., Kolter, J. Z., and Wilson, A. G. From entropy to epiplexity: Rethinking information for computationally bounded intelligence. arXiv preprint arXiv:2601.03220, 2026. · arXiv
  18. Gaven, L., Carta, T., Romac, C., Colas, C., Lamprier, S., Sigaud, O., and Oudeyer, P.-Y. Magellan: Metacognitive predictions of learning progress guide autotelic llm agents in large goal spaces. In International Conference on Machine Learning, pp. 18920-18953. PMLR, 2025.
  19. Ha, D. and Schmidhuber, J. Recurrent world models facilitate policy evolution. Advances in neural information processing systems, 31, 2018.
  20. Hazan, E., Kakade, S., Singh, K., and Van Soest, A. Provably efficient maximum entropy explo- ration. In International Conference on Machine Learning, pp. 2681-2691. PMLR, 2019.
  21. Herrmann, V., Alcaide, E., Wand, M., and Schmidhuber, J. Multiple token divergence: Measuring and steering in-context computation density. arXiv preprint arXiv:2512.22944, 2025a. · arXiv
  22. Herrmann, V., Csordás, R., and Schmidhuber, J. Measuring in-context computation complexity via hidden state prediction. In Proceedings of the 42nd International Conference on Machine Learning, volume 267 of Proceedings of Machine Learning Research. PMLR, 13-19 Jul 2025b.
  23. Hughes, E., Dennis, M., Parker-Holder, J., Behbahani, F., Mavalankar, A., Shi, Y., Schaul, T., and Rocktäschel, T. Position: open-endedness is essential for artificial superhuman intelligence. In Proceedings of the 41st International Conference on Machine Learning, pp. 20597-20616, 2024.
  24. Hutter, M. Universal artificial intelligence: Sequential decisions based on algorithmic probability. Springer Science & Business Media, 2005.
  25. Itti, L. and Baldi, P. F. Bayesian surprise attracts human attention. In Advances in Neural Information Processing Systems (NIPS) 19, pp. 547-554. MIT Press, Cambridge, MA, 2005.
  26. Jansma, A. and Hoel, E. Engineering emergence. arXiv preprint arXiv:2510.02649, 2025. · arXiv
  27. Kanitscheider, I., Huizinga, J., Farhi, D., Guss, W. H., Houghton, B., Sampedro, R., Zhokhov, P., Baker, B., Ecoffet, A., Tang, J., et al. Multi-task curriculum learning in a complex, visual, hard- exploration domain: Minecraft. arXiv preprint arXiv:2106.14876, 2021. · arXiv
  28. Koppel, M. Complexity, depth, and sophistication. Complex Systems, 1(6):1087-1091, 1987.
  29. Lehman, J. and Stanley, K. O. Beyond open-endedness: Quantifying impressiveness. In Artificial Life Conference Proceedings, pp. 75-82. MIT Press, 2012.
  30. Levin, L. A. Randomness conservation inequalities; information and independence in mathematical theories. Information and Control, 61(1):15-37, 1984.
  31. Li, M. and Vitányi, P. M. B. An introduction to Kolmogorov complexity and its applications. In van Leeuwen, J. (ed.), Handbook of Theoretical Computer Science, pp. 188-254. Elsevier Science Publishers B.V., 1990.
  32. Lin, Z., Gou, Z., Gong, Y., Liu, X., Xu, R., Lin, C., Yang, Y., Jiao, J., Duan, N., Chen, W., et al. Not all tokens are what you need for pretraining. Advances in Neural Information Processing Systems, 37:29029-29063, 2024.
  33. Meulemans, A., Nasser, R., Wołczyk, M., Weis, M. A., Kobayashi, S., Richards, B., Lajoie, G., Steger, A., Hutter, M., Manyika, J., et al. Embedded universal predictive intelligence: a coherent framework for multi-agent learning. arXiv preprint arXiv:2511.22226, 2025. · arXiv
  34. Müller, M. Stationary algorithmic probability. Theoretical Computer Science, 411(1):113-130, 2010.
  35. Mutti, M. Unsupervised reinforcement learning via state entropy maximization. PhD thesis, alma, Marzo 2023.
  36. Oudeyer, P.-Y., Kaplan, F., and Hafner, V. F. Intrinsic motivation systems for autonomous mental development. IEEE Transactions on Evolutionary Computation, 11(2):265-286, 2007.
  37. Pathak, D., Agrawal, P., Efros, A. A., and Darrell, T. Curiosity-driven exploration by self-supervised prediction. In International conference on machine learning, pp. 2778-2787. PMLR, 2017.
  38. Pathak, D., Gandhi, D., and Gupta, A. Self-supervised exploration via disagreement. In Chaudhuri, K. and Salakhutdinov, R. (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 5062-5071. PMLR, 09-15 Jun 2019. URL https://proceedings.mlr.press/v97/pathak19a.html.
  39. Post, E. L. Formal reductions of the general combinatorial decision problem. American journal of mathematics, 65(2):197-215, 1943.
  40. Rissanen, J. Modeling by shortest data description. Automatica, 14(5):465-471, 1978.
  41. Sancaktar, C., Blaes, S., and Martius, G. Curious exploration via structured world models yields zero-shot object manipulation. Advances in Neural Information Processing Systems, 35:24170- 24183, 2022.
  42. Schmidhuber, J. A possibility for implementing curiosity and boredom in model-building neural controllers. In Meyer, J. A. and Wilson, S. W. (eds.), Proc. of the International Conference on Simulation of Adaptive Behavior: From Animals to Animats, pp. 222-227. MIT Press/Bradford Books, 1991a.
  43. Schmidhuber, J. Curious model-building control systems. In Proceedings of the International Joint Conference on Neural Networks, Singapore, volume 2, pp. 1458-1463. IEEE press, 1991b.
  44. Schmidhuber, J. What's interesting? Technical Report IDSIA-35-97, IDSIA, 1997. ftp://ftp.idsia.ch/pub/juergen/interest.ps.gz; extended abstract in Proc. Snowbird'98, Utah, 1998;
  45. Schmidhuber, J. Artificial curiosity based on discovering novel algorithmic predictability through coevolution. In Proceedings of the 1999 congress on evolutionary computation-cec99 (cat. no. 99th8406), volume 3, pp. 1612-1618. IEEE, 1999.
  46. Schmidhuber, J. The speed prior: a new simplicity measure yielding near-optimal computable predictions. In International conference on computational learning theory, pp. 216-228. Springer, 2002.
  47. Schmidhuber, J. Exploring the predictable. In Advances in evolutionary computing: theory and applications, pp. 579-612. Springer, 2003.
  48. Schmidhuber, J. Developmental robotics, optimal artificial curiosity, creativity, music, and the fine arts. Connection Science, 18(2):173-187, 2006.
  49. Pezzulo, G., Butz, M. V., Sigaud, O., and Baldassarre, G. (eds.), Anticipatory Behavior in Adaptive Learning Systems. From Psychological Theories to Artificial Cognitive Sys- tems, volume 5499 of LNCS, pp. 48-76. Springer, 2009.
  50. Schmidhuber, J. Formal theory of creativity, fun, and intrinsic motivation (1990-2010). IEEE Transactions on Autonomous Mental Development, 2(3):230-247, 2010. ISSN 1943-0604. doi: 10.1109/TAMD.2010.2056368. · DOI · Paper page
  51. Schmidhuber, J. On learning to think: Algorithmic information theory for novel combinations of re- inforcement learning controllers and recurrent neural world models. Preprint arXiv:1511.09249, 2015. · arXiv
  52. Sekar, R., Rybkin, O., Daniilidis, K., Abbeel, P., Hafner, D., and Pathak, D. Planning to explore via self-supervised world models. In III, H. D. and Singh, A. (eds.), Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pp. 8583-8592. PMLR, 13-18 Jul 2020. URL https://proceedings.mlr. press/v119/sekar20a.html.
  53. Shumailov, I., Shumaylov, Z., Zhao, Y., Papernot, N., Anderson, R., and Gal, Y. Ai models collapse when trained on recursively generated data. Nature, 631(8022):755-759, 2024.
  54. Shyam, P., Jaśkowski, W., and Gomez, F. Model-based active exploration. In International confer- ence on machine learning, pp. 5779-5788. PMLR, 2019.
  55. Solomonoff, R. J. A formal theory of inductive inference. part i. Information and control, 7(1): 1-22, 1964.
  56. Storck, J., Hochreiter, S., and Schmidhuber, J. Reinforcement driven information acquisition in non- deterministic environments. In Proceedings of the International Conference on Artificial Neural Networks, Paris, volume 2, pp. 159-164. EC2 & Cie, 1995.
  57. Stout, A. and Barto, A. G. Competence progress intrinsic motivation. In 2010 IEEE 9th International Conference on Development and Learning, pp. 257-262. IEEE, 2010.
  58. Sun, Y., Gomez, F., and Schmidhuber, J. Planning to be surprised: Optimal bayesian exploration in dynamic environments. In International conference on artificial general intelligence, pp. 41-51. Springer, 2011.
  59. Sutton, R. S. Integrated modeling and control based on reinforcement learning and dynamic programming. In Neural Information Processing Systems, 1990. URL https://api. semanticscholar.org/CorpusID:62620110.
  60. Tang, H., Houthooft, R., Foote, D., Stooke, A., Xi Chen, O., Duan, Y., Schulman, J., DeTurck, F., and Abbeel, P. # exploration: A study of count-based exploration for deep reinforcement learning. Advances in neural information processing systems, 30, 2017.
  61. Tishby, N. and Zaslavsky, N. Deep learning and the information bottleneck principle. 2015 IEEE Information Theory Workshop (ITW), 2015.
  62. Vereshchagin, N. and Shen, A. Algorithmic statistics: forty years later. In Computability and Complexity: Essays Dedicated to Rodney G. Downey on the Occasion of His 60th Birthday, pp. 669-737. Springer, 2016.
  63. Wallace, C. S. and Boulton, D. M. An information measure for classification. The Computer Journal, 11(2):185-194, 1968.
  64. Wang, H. Tag systems and lag systems. Mathematische Annalen, 152(1):65-74, 1963.
  65. Wang, Y., Kordi, Y., Mishra, S., Liu, A., Smith, N. A., Khashabi, D., and Hajishirzi, H. Self- instruct: Aligning language models with self-generated instructions. In Proceedings of the 61st annual meeting of the association for computational linguistics (volume 1: long papers), pp. 13484-13508, 2023.
  66. Wolfram, S. Statistical mechanics of cellular automata. Reviews of modern physics, 55(3):601, 1983.
  67. Zelikman, E., Wu, Y., Mu, J., and Goodman, N. D. Star: Self-taught reasoner bootstrapping reason- ing with reasoning. In Proc. the 36th International Conference on Neural Information Processing Systems, volume 1126, 2024.
  68. Zhang, J., Lehman, J., Stanley, K. O., and Clune, J. Omni: Open-endedness via models of human notions of interestingness. ArXiv, abs/2306.01711, 2023. URL https://api. semanticscholar.org/CorpusID:259064135. · arXiv

Cited by

Sorted by citations

Authors
Herrmann, V., & Schmidhuber, J.
Affiliations
Dalle Molle Institute for Artificial Intelligence Research (CH)
ORCID
Herrmann, Vincent
Venue
arXiv
Publisher
arXiv
Published
2026
ISSN
2331-8422 (ISSN-L)
DOI
10.48550/arxiv.2605.14831
arXiv
2605.14831
OpenAlex
W7161309438
Cited by
0
References
0
Type
posted content
Language
en
Open access
Licence
Locations
  • arXiv (Cornell University) (submittedVersion, cc-by)
  • arXiv (Cornell University) (cc-by)
Topics
  • Physical Sciences › Computer Science › Computational Theory and Mathematics › Computability, Logic, AI Algorithms
  • Physical Sciences › Computer Science › Artificial Intelligence › Algorithms and Data Compression
  • Physical Sciences › Computer Science › Artificial Intelligence › Evolutionary Algorithms and Applications
Keywords
interestingness, Kolmogorov complexity, self-improving systems

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review