acceptodds
Under review as a conference paper at ICLR 2027

An LLM-referenced C-test for Supraintelligence

Abstract

Under the accelerated pace of AI development, any benchmark whose difficulty is calibrated with humans or current AI systems becomes circular, or saturates soon. How can we then evaluate machines that may become more capable than the current machines and the people who write the tests? One answer to the question hinges on inverse problems, inductive inference questions for which difficulty depends on the complexity of the underlying mechanism, given the observations and the previous knowledge. Levin’s Kt, a computable variant of Kolmogorov complexity, puts a theoretical upper bound to that difficulty, balancing the simplest representation encoding for the mechanism and the logarithm of the time steps to run that mechanism. Previous tests derived from Levin’s Kt, such as the original C-test, are based on minimalistic Universal Turing Machines (UTM), capable of very limited representations and no previous knowledge. Reasoning large language models (LLM) are UTMs that capture a compendium of human culture as knowledge, using prompts as natural language programs. This paper presents the first test based on Levin’s Kt with LLMs as representational machines. Fresh test items can be produced at high difficulties, estimated in a ratio scale measured in bits, before any frontier model can solve them. We formalise the measure, devise a lightweight generation and certification pipeline, explore the effect of the power of the reference machine and the gap between examiner and examinee. We produce a first battery of certified items administered to twelve LLMs. The resulting agent characteristic curves decrease with difficulty, down to the uncharted high-difficulty region, the supra-intelligence window of items we can certify and chain across several reference machines.

Primary area:
datasets and benchmarks
Keywords:
AI Evaluation, Levin's Kt, Intrinsic Difficulty, Large Language Models, Program Representations, Inversion Problems

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_BpfqOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

The paper revives the C-test with an LLM as the reference machine. Items are sequences built from world-knowledge retrievals and transformations; difficulty is the conditional Levin complexity of a natural-language description of the rule, costed by a frozen 14B model. A composer generates items, a filter removes those with a cheap rival pattern, and the reference machine certifies an item by running the description. 71 items are administered to twelve LLMs and 51 certified ones carry the difficulty analysis. Difficulty correlates with accuracy (Spearman -0.79) and the induced ability correlates with Epoch's ECI. For the strongest examinee, items above about 190 bits form what the authors call the supra-intelligence window: the 14B machine certifies them and frontier models mostly fail them.

Critical strengths

The idea is good and the problem is real: benchmarks saturate, leak, and cannot grade items nobody has solved. Defining difficulty by construction with an LLM as the reference machine is, to my knowledge, new; the paper positions itself against the original C-test and SuperARC. The experiments are complete for a first demonstration, and the result that items costed and certified on a 4-bit 14B model have a difficulty that predicts the failure of much stronger models is worth having.

Critical weaknesses
  1. The supra-intelligence window is the headline result, but the main text gives the reader very little to judge it with. Table 4 gives its bounds and says the fitted curve falls below one third there. How many items are in the window, how often the frontier models actually solve them, and with what uncertainty, are all left to Appendix F, where the authors themselves write that the window "should be taken with care" and report an interval that does not exclude a success rate above one third. That belongs in Section 7. There is also an asymmetry the paper should be clearer about: certification means the reference machine can run a description it is handed, while the examinee has to find the rule. The authors treat this as the design, which is fine, but "a 14B model certifies what frontier models cannot solve" then compares two different tasks, and the window should be described accordingly.

  2. What the test measures. The items are sequence completion built from retrievals and transformations, which the paper maps onto crystallised and fluid intelligence, and the hard items are mostly the transformation-heavy ones (Figure 2). The only external check is the correlation with ECI over ten models, all of which sit below the window. That supports the scale in the range where models already succeed; at the top, where the paper puts its value, nothing shows that failing these items tracks any other capability. The claim to "quantify the pace of AI progress" is ahead of the evidence.

  3. Two papers missing from Section 2: Huang et al. (arxiv.org/abs/2404.09937), on a model's compression of external text predicting its benchmark scores, and Wan et al. (arxiv.org/abs/2505.15784), on LLMs as computable approximations to Solomonoff induction. The second bears on reading the reference machine as an inductive device.

Questions for authors
  1. Please bring the window's item count, the frontier models' success rate on those items and its interval from Appendix F into Section 7, and add intervals for the abilities in Figure 3.

  2. For the items in the window, how do the frontier models fail: a different rule that also fits the prefix, the intended rule executed wrongly, or something else?

Reviewer_fNUjOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes C-test ONE, a framework for generating and evaluating sequence-completion problems using LLMs as reference machines. Inspired by Levin's Kt complexity, the method estimates problem difficulty through the description cost and inference time required to reproduce a sequence continuation. The framework incorporates automatic problem generation, alternative-rule checking, and difficulty certification. Experiments with three reference models and twelve evaluated LLMs demonstrate correlations between estimated complexity and model accuracy, suggesting potential for evaluating models beyond the capabilities of the reference machine.

Critical strengths
  1. Novel perspective on scalable AI evaluation. The paper presents an interesting connection between algorithmic information theory and LLM-based evaluation. Using reference-model-relative complexity to generate and characterize challenging problems is a potentially valuable direction for reducing reliance on human-calibrated benchmarks.

  2. Extensive analysis across models and complexity measures. The experiments cover multiple reference machines and twelve examinee models. The reported correlations between estimated complexity and accuracy, along with comparisons against other complexity metrics and psychometric indicators, provide encouraging evidence for the proposed framework.

Critical weaknesses
  1. Approximate certification does not guarantee unquestionability. The theoretical definition of unquestionability requires excluding all competing low-cost programs. However, the implementation checks only a limited number of LLM-generated and structural rivals. Consequently, the absence of a discovered rival does not establish that the sequence has a unique preferred continuation. This weakens the validity guarantees underlying the benchmark.

  2. Difficulty estimates depend heavily on reference-model capabilities and incomplete search. The proposed Kt estimates are upper bounds obtained through limited prompt search rather than exact complexity measurements. Different reference machines can assign substantially different costs to the same problem, and the estimated difficulty may reflect limitations in the reference model's knowledge or search process. This raises concerns about interpreting the resulting scores as a stable, intrinsic difficulty scale.

  3. Insufficient evidence for the claimed supraintelligence evaluation window. The main analysis relies on only 51 certified items under Qwen3-14B, including just 10 above 190 bits. Moreover, the characteristic curves and ability estimates rely on fitted extrapolations in sparsely populated high-difficulty regions. The current evidence is insufficient to establish reliable discrimination between frontier models at difficulty levels beyond their demonstrated capabilities.

Questions for authors

Q1. How robust is the unquestionability certification when substantially more rival programs or independent generators are used?

Q2. How stable are the estimated Kt values under larger search budgets and different reference models?

Q3. Can the authors validate the supraintelligence window with more high-difficulty items and provide uncertainty estimates for the fitted ability thresholds?

Reviewer_V2QnOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes C-test ONE, which uses frozen large language models as reference machines to extend the algorithmic-information-theoretic C-test to sequence induction tasks involving natural-language knowledge retrieval and rule transformations. The paper defines LLM-relative Levin complexity as the minimum, over all prompts that make the reference model produce the intended suffix given a sequence prefix, of the prompt’s coding cost plus the logarithm of the number of reasoning tokens required for execution. The implementation estimates an upper bound on this quantity through finite candidate search and integrates item generation, validity checks, screening of competing interpretations, conditional certification, and model evaluation.

Critical strengths
  1. The paper addresses an important evaluation problem. It explores how challenging items can be generated and certified using weaker reference models, offering a meaningful direction for addressing benchmark saturation and reducing dependence on retrospective calibration based on existing models’ performance.
  2. The framework is structured and operational. It combines item generation, validity checks, screening of competing interpretations, certification, and evaluation. Organizing items through retrieval and transformation dimensions provides a concrete implementation of complexity concepts from algorithmic information theory.
  3. The appendix provides extensive and transparent analyses. The authors report confidence intervals, sensitivity analyses, reference-model biases, and the complete item collection. They also disclose problematic items and results after their removal, helping assess robustness and scope.
Critical weaknesses
  1. The stability of the difficulty calibration is insufficiently validated. Finite search can yield loose complexity upper bounds, so high scores may partly reflect search limitations. Appendix L.1 shows that additional search lowers some estimates, but systematic analysis of how search budgets and candidate-generation strategies affect item scores, difficulty rankings, and high-difficulty window boundaries remains lacking.
  2. Empirical support for the "supraintelligence window" is limited. The main Qwen3-14B analysis contains 51 certified items, with only ten above 190 bits, all certified exclusively by this model. The high-difficulty region therefore has limited sample coverage and validation across reference models. Larger independent item sets and uncertainty estimates for the window boundary are needed to support its stability and generalizability.
  3. The certification pipeline still has quality-control gaps. Appendix P identifies simpler prefix interpretations for three of the 51 Qwen3-14B-certified items and an arithmetic error in an item certified only under Phi-4. Removing these items improves the Qwen3-14B Spearman correlation from −0.79 to −0.84, and the affected Qwen3-14B items lie outside the highest-difficulty region. Nevertheless, these cases motivate stronger checks of competing interpretations and independent rule verification before evaluation.
Questions for authors

See weaknesses.

Comments on the paper

1 comment
AuthorsOpenReview ↗

New PDF version

We have uploaded a new version of the PDF file. It adds the two references suggested by Reviewer fNUj, discussed in Appendix L and in the extended related work (Appendix S). As before, all changes are in blue.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.