As the pace of AI development accelerates, traditional benchmarks calibrated against human performance or current AI systems are rapidly saturating. A new research paper published on arXiv proposes a radical solution: utilizing Levin’s Kt complexity to generate tests that exceed the capabilities of both humans and today's frontier models.
The Theoretical Foundation of Complexity
The approach hinges on inverse problems and inductive inference questions, where difficulty is determined by the complexity of the underlying mechanism. Researchers utilize Levin’s Kt, a computable variant of Kolmogorov complexity, which balances the simplest representation encoding for a mechanism against the logarithm of the time steps required to run it.
LLMs as Reference Machines
Unlike previous tests derived from Levin’s Kt that relied on minimalistic Universal Turing Machines (UTM), this new method employs Large Language Models (LLMs) as representational machines. LLMs are viewed as UTMs that capture a compendium of human culture as knowledge, using natural language prompts as programs. This allows for the production of fresh test items at high difficulties, measured on a ratio scale in bits, before any human or frontier model can solve them.
The Supraintelligence Window
The study involved administering a first battery of certified items to twelve different LLMs. The resulting agent characteristic curves demonstrated a decrease in performance as difficulty increased, eventually reaching an uncharted high-difficulty region. The researchers have termed this the "supra-intelligence window"—a space containing items that can be formally certified yet remain beyond the reach of current frontier intelligence.
