aiqbench analysis
This paper gives a theoretical lower bound on the cost of finding short generating programs by score-based search, such as Levin search, evolutionary methods, and simulated annealing. It frames a "conservation law" in which each bit of structural knowledge injected into a search removes at most about one bit of search, and argues that structural shortcuts sacrifice completeness. For AI readers, the practical takeaway is that program induction via score feedback faces fundamental limits, while the claimed deterministic engine's results (2,383 of 3,914 sequences) are reported on a specific benchmark and need independent scrutiny.
The program is still there, and searching for it obeys a conservation law
arXiv:2606.13799v2 Announce Type: replace-cross Abstract: The length of the shortest program that generates a sequence, its Kolmogorov complexity, is uncomputable, so we ask what finding a short program costs when one exists. Many search algorithms, including Levin search, evolutionary methods, simulated annealing and the cross-entropy method, learn about a candidate program only through its score, how much of the sequence it reproduces. For such algorithms we define the coupling width of a search problem, the largest number of program fields that must change together before the score moves. We prove an unconditional worst-case lower bound on the number of candidates scored, exponential in that width. Under stated conditions, a conservation law follows, in which each bit of structural knowledge injected into a search removes at most one bit of search. The structure plus the logarithm of the remaining search is at least a fixed fraction of the sequence's Kolmogorov complexity. That fraction tends to one as the instruction set grows, so the lower bound approaches Levin's 1973 upper bound, apart from the program's running time. Search by score must pay this cost to be complete. We prove that our engine's structural inference avoids it only by giving up coverage, as does, if one-way functions exist, every method that runs in polynomial time. Our deterministic engine, built on this theory, recovers a generating program, certified by compressing its data and predicting an unseen continuation, for 2,383 of 3,914 candidate sequences in four populations of integer sequences and cellular automata, including the chaotic Rule 30.
Abstract:The length of the shortest program that generates a sequence, its Kolmogorov complexity, is uncomputable, so we ask what finding a short program costs when one exists. Many search algorithms, including Levin search, evolutionary methods, simulated annealing and the cross-entropy method, learn about a candidate program only through its score, how much of the sequence it reproduces. For such algorithms we define the coupling width of a search problem, the largest number of program fields that must change together before the score moves. We prove an unconditional worst-case lower bound on the number of candidates scored, exponential in that width. Under stated conditions, a conservation law follows, in which each bit of structural knowledge injected into a search removes at most one bit of search. The structure plus the logarithm of the remaining search is at least a fixed fraction of the sequence's Kolmogorov complexity. That fraction tends to one as the instruction set grows, so the lower bound approaches Levin's 1973 upper bound, apart from the program's running time. Search by score must pay this cost to be complete. We prove that our engine's structural inference avoids it only by giving up coverage, as does, if one-way functions exist, every method that runs in polynomial time. Our deterministic engine, built on this theory, recovers a generating program, certified by compressing its data and predicting an unseen continuation, for 2,383 of 3,914 candidate sequences in four populations of integer sequences and cellular automata, including the chaotic Rule 30.
v2 revised throughout and retitled. 8 pages and 3 figures, with the SI Appendix (40 pages) appended. Code and data at this https URL, archived at this https URL
Computational Complexity (cs.CC); Machine Learning (cs.LG)
F.1.3; F.2.2; I.2.6
arXiv:2606.13799 [cs.CC]
(or arXiv:2606.13799v2 [cs.CC] for this version)
Full text under the publisher's open licence · 294 words
Related coverage
Conservative Meta-Agent Search: Architecture Adaptation under Non-Stationarity
arXiv · Oct 23, 2026
Correcting a learned physical invariant improves world-model rollouts
arXiv · Aug 25, 2026
A Particle-Swarm-Assisted Gradient Meta-Learning Algorithm for Joint Transmit Precoding and STAR-RIS Coefficient Optimization
arXiv · Sep 26, 2026
Deeper is Not Always Better: Mitigating the Alignment Tax via Confident Layer Decoding
arXiv · Oct 6, 2026