acceptodds
Under review as a conference paper at ICLR 2027

Certified but Not Useful: An Information-Theoretic Ceiling on LLM-Based Mathematical Discovery

Abstract

We prove an information-theoretic ceiling for verifier-mediated LLM agents: in any hidden-world, no-side-channel verifier model with disjoint success sets, no admissible policy—at any query budget—has equal-prior success probability above , where is the total-variation distance between the laws of the complete verifier signature. The ceiling depends on the interface and environment pair, not the agent; exact maxima meet it in all 423 finite worlds. It is vacuous precisely when , meaning that the complete signature distinguishes the environments almost surely; public input revealing the target is sufficient, but not necessary. A companion result gives a minimax checker-call separation between charged rebuilding and free frame restoration in an opaque marked-leaf model. A usefulness interpretation of the ceiling requires success sets that encode held-out utility. We define statistical discoverability as the probability that a research procedure returns an artifact that is both certified and useful on sealed theorems. Separately, we observe that installing a checker-certified library lowered held-out solve rate by (95% CI ; 10 of 12 paired cells negative, none positive; ), and every added failure was a completed proof the checker rejected, not truncation or timeout. The measured harm is a post-freeze utility contrast on four worlds with a fixed solver, not an estimate of discoverability or a test of the ceiling; is unmeasured in these runs. Together, the framework opens a principled path for analyzing what LLM-based agents can and cannot formally guarantee in automated mathematics.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Large Language Models

Reviews

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

For research agents that interact with the environment only through a proof checker, the paper shows (1) that, for two hidden environments, the equal-prior success probability of any policy is at most (1+δΓ)/2(1+\delta_\Gamma)/2, where δΓ\delta_\Gamma is the total-variation distance between the laws of the verifier's complete signature Γ\Gamma (Thm 4.1), and (2) that in an opaque marked-leaf tree model there is a Θ(d)\Theta(d) minimax separation in checker calls between a flat executor that cannot restore frames and a retained executor that can (Thm 4.2). It further distinguishes an artifact that the checker accepts (certified) from one that improves the held-out solve rate of a fixed solver by at least γ\gamma (useful), and defines statistical discoverability (SD) as the probability that both hold. Experimentally, on 4 finite Lean worlds ×\times 3 seeds, installing a Lean-certified library lowers the held-out solve rate relative to an empty library (−0.375-0.375 at b=16384b=16384, 95% CI [−0.50,−0.24][-0.50, -0.24]), and every failure is a completed proof rejected by the checker. The authors state explicitly that the experiments test neither theorem and do not estimate SD, that δΓ\delta_\Gamma is unmeasured, and that some runs were invalidated.

Critical strengths
  1. The evaluation protocol that separates certified from useful and evaluates frozen artifacts on sealed tests (Definitions 2.2, 2.4, Figure 4). This distinction tends to be neglected in work on self-improving mathematical agents, and the contribution to evaluation design is meaningful.

  2. A negative observation with a clear direction: installing a verified library lowers the performance of a fixed solver. The breakdown of failures (checker rejections rather than truncation or timeouts) is recorded, and within what is presented the observation is credible.

Critical weaknesses

The effort to state the limits of every claim honestly is appreciated, but as a result most of the main text is a list of what is not claimed, and the main result is hard to identify. Figure 1 packs a schematic, an analytical result, and measurements into one panel set. Labels defined only in the appendix (Results A–F / III / P, GX-1′/2/3, E2-CorF-K0, M1/M6, Family B, G-3) appear throughout the main text, and the statement of Thm 4.2 refers to a "Remark D.19 paragraph". The numbering (Definition 4.1 →\to Assumption 4.1 →\to Theorem 4.1) is confusing. Even a careful reading requires substantial effort to recover the structure.

The positioning relative to prior work is also incomplete. Berlot-Attwell et al. (2024), which the paper calls its starting point (the critique that the gains of LEGO-Prover and similar systems are not attributable to library reuse), appears only in Table 8 of App. F and is not discussed in the main-text related work. LeanAgent (ICLR 2025) and REFACTOR (ICLR 2024), which report positive library transfer, and Poesia et al. (NeurIPS 2024, 2025), which measure usefulness by how often a lemma is used in proofs of other theorems, bear directly on the definition of SD but are not cited.

The proof of Thm 4.1 (data processing and disjointness of the success sets) and the counting argument of Thm 4.2 (a flat executor needs dd extensions per leaf over mdm^d leaves, whereas DFS with retained frames needs ∑k=1dmk\sum_{k=1}^d m^k) are correct. My concerns are about the match between claims and results.

  1. Thm 4.1 is Le Cam's two-point lemma (as the authors acknowledge in Remark D.4) and contains nothing specific to LLMs or mathematics. Moreover, in the usual theorem-proving setting where the public theorem statement determines the target, δΓ=1\delta_\Gamma = 1 and the bound is vacuous (App. D.1 (A3)). The title "An Information Theoretic Ceiling on LLM-based Mathematical Discovery" is too strong for this range of applicability. The reduction itself, viewing the sequence of verifier responses as a garbling, also has precedent. Botta et al. (ICML 2025), which the paper cites in Table 8, already treats how verifier access changes information-theoretic tractability and should be contrasted where Thm 4.1 is positioned in the main text (NL-PAC, arXiv 2607.08961, applies the same two-point method to LLM-mediated supervision; it is contemporaneous and I mention it only for reference).

  2. The authors themselves state that the experiments test neither Thm 4.1 nor Thm 4.2, do not estimate SD, and do not measure δΓ\delta_\Gamma. The three components, theory, definition, and experiments, are therefore mutually independent and do not form a coherent claim.

  3. The observed harm is that the solver writes incorrect proofs when the prompt is roughly three times longer; the effect of the library content is not separated from the effect of prompt length (as acknowledged). The worlds are four toy worlds (aggregation over List Nat and the like), and the empty-library solve rate itself varies between 0.2 and 0.6 within a world (around Table 7). The cell-bootstrap CIs are, as the authors say, descriptive, so the evidence for the generality of the effect is weak.

Questions for authors
  1. Please give one concrete example of a mathematical environment in a realistic setting where δΓ<1\delta_\Gamma < 1, i.e., where Thm 4.1 is non-vacuous (the public information does not determine the target). Without it, my assessment of the theorem's applicability will not change.

  2. On isolating the cause of the harm: do you have a control condition that replaces the library content with unrelated Lean code of the same token count, or a condition that presents the library selectively via retrieval? If the degradation is due to prompt length, the issue is prompt design rather than certified-versus-useful.

  3. Ota et al. (2026), which the paper cites, report that discovered verified theorems improve LLM proving performance when supplied as prompt lemmas, and the Conjecturing-Proving Loop (arXiv 2509.14274) reports that feeding verified self-generated theorems back into the context consistently improves subsequent proof success. The harm observed here points in the opposite direction. Which factor do you believe accounts for the difference: the way the library is presented (installed versus retrieved), the toy nature of the worlds, or prompt length? Clarifying this bears directly on the assessment.

1 comment

Thank you for your careful review and constructive comments.

Points follow your weaknesses in order, subdividing paragraphs; the last three answer Q1–Q3.

  1. The finding is assembly sensitivity (§1); broader contribution remains limited.
  2. Figure 1 now shows only the pipeline.
  3. Definitions and proofs are self-contained (§§2–4).
  4. Berlot-Attwell's alternatives are discussed (§6).
  5. LeanAgent/REFACTOR's transfer is distinguished (§6).
  6. Minimo/UseFor/TacMiner: reuse differs from frozen-solver utility (§6).
  7. The bound is standard; novelty remains limited (§4).
  8. Title unchanged; public targets can make the bound trivial (§§4, 7).
  9. Botta's process-verifier access differs from ours (§6).
  10. Theory and experiments remain unconnected (§7).
  11. Length/content remain confounded (§§5.2, 7).
  12. Four domains and cell-bootstrap intervals do not establish generality (§§3, 7; Appendix B).
  13. Q1: no validated realistic instance; the endpoint example is stipulated (§4).
  14. Q2: A3 was not run; no token-matched or retrieval results; raw outputs/sources are missing for 864 records (§7; Appendix C).
  15. Q3: no cross-system ablation explains the difference from Ota/CPL; its cause remains unknown (§5.3).
Reviewer_io5iOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

It is hard for me to describe the paper, since it is very unclear and hard to follow (most likely entirely AI generated). From what I can get, the authors seem to study a setup of a hidden mathematical world with which we can interact only through the verifier (that tells us "this is correct" or "this is wrong"). Assuming two distinct distributions over hidden worlds, the authors prove that a model has only a bounded probability of outputting a statement that is correct in the hidden world. The bound depends on how close the two distributions are. Then they expand these results to quantify the probability of getting a useful theorem or result.

Critical strengths

-Maybe the starting idea can be turned into an interesting research direction. Studying how far can AI theoretically go in maths is very interesting, but I do not think the current framework is the correct one.

Critical weaknesses

-No AI use statement

-The paper assumes hidden worlds and hidden theorems to prove. This is not realistic, in current mathematical research, we have one world that everybody knows, and the theorems to prove are not hidden.

-The paper is very hard to follow, it would help a lot if the authors could give one running example of two hidden worlds to distinguish early in introduction, in order to help understanding what this is about.

Questions for authors

-see weaknesses section above

1 comment

Thank you for your careful review and constructive comments.

  1. The AI Use Statement (p.10) discloses substantial research/drafting assistance and human-author responsibility; automated checks are not independent human replication.
  2. We agree that theorem statements are public to the solver: only earlier library selection is sealed (§§1–2). The endpoint example assumes a single intended predicate and no side channel, not different arithmetics (§4); no validated deployed library-utility instance is supplied (§7), and A3 was not run and has no results.
  3. The Introduction now gives both the assembly example and endpoint ambiguity (p.1); §4 specifies the latter's assumptions, while Appendix A proves the general bound.
  4. Sections 1–2 separate certification, public-target proving and held-out utility; figures and consolidated limitations aid readability, but neither realistic applicability nor empirical validation of the bound is established (§7; see general response).
Reviewer_xLVLOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

This paper makes the point that a proof checker (e.g., Lean) can check that a proof is correct but not that it is “useful.” The paper studies what an LLM agent can learn about usefulness via interacting with a proof checker. It defines a notion of “statistical discoverability” as the “probability that a research procedure returns an artifact that is both certified and useful on sealed theorems.” The paper gives two theoretical results studying limitations on what an agent can learn by interacting with a proof checker and a small experimental result on four toy Lean problem sets.

Critical strengths

None

Critical weaknesses

-- The paper is extremely hard to read. The writing is very dense, and many paragraphs end with a sentence saying something like "this result does not establish...", so it is hard to tell what results the paper is claiming. There is no AI use statement.

-- As far as I can tell, the content is thin. The main theorem follows from a standard result of Blackwell (as the authors note on page 5). The authors state that neither theoretical result is tested by the experiment (page 3). The experiment is small and "exploratory."

Questions for authors

None

1 comment

Thank you for your careful review and constructive comments.

  1. The finding is assembly-sensitive library utility, not universal harm; §1 states it directly, but broader contribution remains limited (see general response, points 1–3).
  2. We consolidated general caveats in §7 and made §§2–4 self-contained; this clarifies scope, not scientific completeness.
  3. The AI Use Statement (p.10) discloses substantial assistance in research and writing, distinguishes automated checks from independent human replication, and retains human-author responsibility.
  4. The Blackwell/Le Cam bound is standard; rewriting does not resolve the substantive-novelty objection (§§4,7).
  5. Neither theoretical result is tested by the experiments (§7).
  6. Four synthetic domains remain exploratory; A3 was not run and has no results, so broad prospective evidence is still missing (§7; Appendix C).

Comments on the paper

1 comment

We thank all reviewers for their careful and constructive reviews.

Corrected scope

  1. We withdraw the mathematical-error attribution: 92/108 added failures have parsing/layout diagnostics, not established causes (§5.1).
  2. Same-output reassembly changes the library contrast (Table 2), but has nine regressions and ten header defects; original-environment proof authentication remains incomplete (§7).
  3. The bound is standard, not empirically validated; the 423-world tightness claim is withdrawn (§4). The unchanged title is conditional, not universal.
  4. A3 was not run; no results are available (§7; Appendix C).
  5. Blue marks substantive changes; minor wording edits are unmarked and visible in OpenReview's diff.

This reanalysis predates our previous revision and should have been included there; we apologise.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.