- 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 , where is the total-variation distance between the laws of the verifier's complete signature (Thm 4.1), and (2) that in an opaque marked-leaf tree model there is a 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 (useful), and defines statistical discoverability (SD) as the probability that both hold. Experimentally, on 4 finite Lean worlds 3 seeds, installing a Lean-certified library lowers the held-out solve rate relative to an empty library ( at , 95% CI ), 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 is unmeasured, and that some runs were invalidated.
Critical strengths
-
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.
-
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 Assumption 4.1 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 extensions per leaf over leaves, whereas DFS with retained frames needs ) are correct. My concerns are about the match between claims and results.
-
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, 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).
-
The authors themselves state that the experiments test neither Thm 4.1 nor Thm 4.2, do not estimate SD, and do not measure . The three components, theory, definition, and experiments, are therefore mutually independent and do not form a coherent claim.
-
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 Natand 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
-
Please give one concrete example of a mathematical environment in a realistic setting where , 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.
-
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.
-
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.
Thank you for your careful review and constructive comments.
Points follow your weaknesses in order, subdividing paragraphs; the last three answer Q1–Q3.