- Rating
- 3(+1)
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
This paper presents ProofLoom, an LLM-agent framework for autoformalizing research-level stochastic optimization algorithms and their convergence proofs in Lean. The central idea is proof-obligation-driven theory construction, where proof obligations arising from a target convergence theorem guide the incremental construction of supporting mathematical definitions and lemmas.
ProofLoom combines several mechanisms: (1) a Model–Construct–Learn workflow for constructing formalizations; (2) signature contracts and an independent Judge for reviewing changes to mathematical definitions and theorem statements; (3) a Planner–Audit mechanism for decomposing proofs, tracing dependencies and diagnosing proof failures; and (4) SOptLib, a reusable library of verified stochastic optimization results and natural-language construction records.
The paper evaluates ProofLoom against six baselines on 15 stochastic optimization tasks (ten textbook and five research-paper algorithms). It reports higher human and LLM-based evaluation scores than the baselines. The paper further reports 33 formalizations comprising approximately 490,000 lines of algorithm-local Lean code, together with 28 discrepancies identified in published mathematical sources. Ablation studies address the effects of removing Judge, Planner–Audit and SOptLib.
Critical strengths
- Interesting research problem
- The paper recognises that a Lean proof can be formally valid while proving a statement that differs from the original mathematical claim, and proposes various methods to address this issue
- Solid work: substantial implementation and extensive experimentation
Critical weaknesses
-
Low novelty. Many components of ProofLoom, e.g., proof decomposition, iterative proof repair, agent-based review, dependency analysis and reusable lemma libraries, have been proposed and widely used in previous work. It is unclear what is technically new in the current approach.
The paper seems to emphasize proof-obligation-driven construction as the main conceptual contribution, but it is unclear what the essential difference is between this approach and the existing top-down, dependency-guided or goal-directed proof construction. Similarly, signature contracts and Planner–Audit appear largely to be structured LLM-agent workflows with source-grounded prompting and validation.
-
Subjective evaluation. The evaluation lacks a direct success metrics. The primary comparison uses a seven-point human evaluation rubric and LLM-based evaluation scores. The human evaluation involves two internal Lean experts, with an LLM assessment used to determine when a second expert adjudicates disagreements. The independent external validation and inter-rater agreement statistics are not reported in the main results.
-
Fairness of comparison and experiments. ProofLoom benefits significantly from SOptLib, which contains verified stochastic optimization infrastructure accumulated during earlier developments, but the baselines do not appear to have the same access. Consequently, the main results compare complete system configurations with potentially different amounts of domain-specific knowledge and reusable code.
Moreover, the ablations of Judge and Planner-Audit are limited to some selected cases (rather than complete formalization tasks). The improvement in successful cases is relatively modest: 33/43 for the full system versus 29/43 for either ablation.
-
High computational and engineering cost. The system is allocated up to 48 hours per task, and the token counts are exceptionally large. For example, the NSMD development consumes approximately 365 million total tokens with SOptLib and 927 million without it, including cached input tokens.
Such resource consumption raises questions about scalability, affordability and practical applicability. The paper does not provide a comparison of wall-clock time, API cost, number of LLM calls or proof-completion efficiency across the competing systems. Moreover, the amount of generated Lean code is extremely large, and code volume alone should not be regarded as an indicator of formalization quality.
Questions for authors
Q1. What is the precise technical distinction between ProofLoom and the existing systems? Which specific components do the authors consider fundamentally new, beyond their integration into a domain-specific workflow?
Q2. In the main experiments, ProofLoom has access to SOptLib, whereas the baseline systems do not appear to have the same access. Can the authors clarify how this difference affects the comparison? In particular, can they provide a comparison where the baselines have access to the same mathematical infrastructure, or ProofLoom is evaluated without SOptLib across all 15 tasks?
Q3. The Judge and Planner-Audit ablations focus on 43 selected obstructions and evaluate repair directions rather than completed formalizations. Can the authors provide end-to-end ablation results showing the impact of these components on proof completion, source faithfulness and computational cost? How were the 43 cases selected, and how representative are they of the complete benchmark?
Q4. Computational efficiency. What are the computational costs of ProofLoom and the baselines in terms of wall-clock time, LLM calls, input/output tokens and API cost? How much of ProofLoom's computational budget is consumed by planning, auditing, semantic review and proof generation, respectively?
Update. I believe the authors have addressed most of my concerns. I hence raise the score.
5 comments
Response to Reviewer e5Br (2/4)
e5Br–Q2 (review: W1). How does proof-obligation-driven construction differ from existing top-down, dependency-guided or goal-directed proof construction? Are signature contracts and Planner–Audit more than structured agent workflows?
Goal-directed and dependency-guided systems decompose a goal inside a model whose meaning is fixed. ProofLoom also decomposes goals, but treats the model itself as something the proof may require to change, under the control described in Q1. This control is realized as an agent control flow, and its engineering implementation is standard; what matters is which decisions it controls and on what evidence. Each rule has a part enforced by code, not by prompting:
- Protected interface. Code restores the protected signatures after every round of proof work.
- Signature contracts. Contracts and open obligations persist in an append-only record. The audit fails if a contract is missing, if its evidence is a placeholder, or if a declaration has changed since its contract was recorded. The Judge decides premises against a source index in which stated assumptions and proved lemmas are separate entries.
- Planner–Audit. Code traces each open goal through the Lean dependency graph to the source step it blocks. Audit compares the Lean route with the source proof, and a route that re-derives a result the source cites must first attempt the source route. This enables self-correction in a long-horizon agent.
The ablations test the two sides of the difficulty. Without Planner–Audit, which locates where the model must change, more developments stall: partial repairs rise from 9 to 13 of 43 cases, 4 of 11 end-to-end artifacts keep sorry, and ratings fall on 7 of 11 tasks. Without the Judge, which controls what may change, more revisions are wrong: incorrect repairs rise from 1 to 6, and ratings fall on 8 of 11 tasks (Tables R4, R6).
Example (SBMD). The noise-cancellation step, Eq. (4.6.21), needs the block proximal update to be measurable with respect to past samples, which the book does not prove. Archon's scored artifact takes a measurable proximal selector as a hypothesis; since the book never states this as an assumption, the Judge would not accept it as a premise. ProofLoom's scored artifact instead proves measurability of the canonical selector, derives the cancellation from it, and completes Theorem 4.12 (anonymized supplement, StochasticBlockMirrorDescent.lean, lines 1692 and 3764). The measurability proof uses an SOptLib lemma, but the outcome does not depend on the library: SBMD scores 7/7 both with and without it (Table R5).
Example of a model revision (SAM; Appendices D.2.2 and D.4). SAM's PAC-Bayes proof needs a Gaussian KL identity. The available formula uses Euclidean coordinates, while the development represents the probability laws on a finite-dimensional inner-product space. Transporting the formula requires a measurable coordinate map, but the original bridge allowed an arbitrary measurable structure. Planner identified this mismatch, and Refactor made the source's Euclidean Borel structure explicit on the bridge and its consumers. Judge accepted this source-supported representation change; the KL identity remained a proof obligation. ProofLoom then constructed the measurable coordinate equivalence, proved KL transport, and used the resulting identity in the PAC-Bayes proof. The revision makes the source's parameter space precise while preserving the Gaussian laws and the identity to be proved.
Response to Reviewer e5Br (3/4)
e5Br–Q3 (review: W2). The evaluation relies on a human rubric and LLM scores, with internal experts and no reported agreement statistics. Is there a direct success metric?
Yes. "The proof compiles" is not sufficient here, because a Lean build also succeeds when the proved statement has drifted from the source, which is the failure we study. We set out the criteria for the human 1–7 ratings in the paper and also report a target-level outcome (Table R3-T): of 28 selected targets, 26 are proved (7 exactly as stated, 6 with an evidence-backed correction, 8 within a stated scope, 5 with both), and SAPD's Theorem 4.8(a)–(b) are open. A correction attributes a discrepancy to the source, with evidence in the discrepancy catalogue; a scope restriction records a narrower formal setting, such as a finite-dimensional realization, and makes no claim that the source is wrong. This classification does not rely on any rating and can be checked against the anonymized Lean code.
On SAPD, Archon and Trellis leave key supporting proofs incomplete. Archon leaves the measurable-selector construction in auxiliary_project_singleton_graph_selector_fallback as sorry (supplement: benchmark/tasks/SAPD/candidates/C2/Algorithms/Benchmark/StochasticAcceleratedPrimalDual/Auxiliary.lean, lines 629–639). Trellis leaves the passage from pointwise bounds to the supremum gap in SAPDGapSupremumPassage as sorry (benchmark/tasks/SAPD/candidates/C5/Tablet/SAPDGapSupremumPassage.lean, lines 5–14). Within the 48-hour scoring budget, ProofLoom completed the algorithm updates, proximal subproblems and several intermediate results. With continued development, the endpoint version proves corresponding expected-gap and high-probability bounds under explicit conditions, including a one-step tail-bound condition for the high-probability result. This demonstrates ProofLoom’s ability to advance long-horizon formalization. The endpoint version is included in the supplementary materials; the paper and Table R3-T continue to count the 48-hour scored artifact, so SAPD’s two source targets remain open in those statistics.
On agreement: a Lean expert and Codex scored the 105 main-comparison artifacts independently; they agreed on 89 (84.8%), every disagreement was one point apart, Cohen's κ is 0.80, and a second Lean expert's adjudication changed 10 initial human scores. The updated supplementary materials contain the adjudication details and all rating records. Both experts are internal to the project; we are arranging independent ratings by external Lean experts and will add them to the revised version.
e5Br–Q4 (review: W3, Q2). ProofLoom has SOptLib while the baselines do not. Can you compare with baselines given the same infrastructure, or evaluate ProofLoom without SOptLib?
In the main comparison the baselines ran without SOptLib. SOptLib is not external support: ProofLoom builds it from its own certified developments, so we regard it as part of the method, and the question is whether the advantage comes only from it. We tested this both ways.
Baselines with the library (Table R1, new): on five randomly drawn benchmark tasks, ProofLoom and Archon each ran with and without SOptLib, with GPT-5.6 Sol for all four arms and a library that contains none of these tasks' own results. The library changes each system's mean rating by 0.2 (Archon 4.6 → 4.8, ProofLoom 6.0 → 5.8), and ProofLoom without the library is at least as high as Archon with it on every task (6.0 vs. 4.8; G-Eval 95.8 vs. 71.3). Using a library well requires deciding which results an open goal needs and adapting them, which is what obligation-driven construction does: with the library, ProofLoom's output tokens fall by 12%, while Archon's rise by 42%.
ProofLoom without the library (Table R5): across six pairs, including the additional ADMM and RSGD tasks, ratings change by at most one point, while token use rises in every pair, to as much as 8.3 times the original total on RSGD. These two controls cover five and six tasks, respectively; we will extend them to all benchmark algorithms in the final version.
Response to Reviewer e5Br (1/4)
Thank you for the detailed review and for recognizing the problem, the distinction between a valid Lean proof and a faithful formalization, and the scale of the work. We appreciate your questions about the methodological novelty and its experimental support. We address each point below; the shared tables are in our general response. On presentation, we rewrote the contribution paragraph without changing the method, carefully revised Figures 1 and 2 to show more clearly how the formal model and the proof co-evolve, and added the SAM model-revision example in Appendix D.2.2 (see the general response).
e5Br–Q1 (review: W1, Q1). Many components, such as decomposition, repair, agent review, dependency analysis and lemma libraries, already exist. What is technically new?
Our methodological contribution is proof-obligation-driven theory construction: open proof obligations determine where and when the formal model is revised, while signature contracts and Judge review govern those revisions against the source. This allows the formal model and its supporting theory to evolve with the proof.
Setting: the model itself is hard. In many autoformalization targets, such as competition or algebraic statements, the objects are already available in Mathlib and the statement pins them down; the difficulty lies mainly in organizing dependencies in the proof. In stochastic optimization the statement leaves the model underdetermined. A convergence theorem implicitly fixes a probability space, the filtration the iterates are adapted to, the point at which each oracle call is made, which quantities are conditionally centered or independent of which others, and the measurability of every update, including set-valued ones such as proximal steps. Published proofs leave most of this implicit, and an LLM reading the text has to reconstruct it exactly. Our artifacts show how much rests on these choices: SBMD's noise cancellation needs a measurability property of the proximal update that the book never proves, and NSAGD's bounds need conditional centering at adaptive query points (Table R3). Mathlib provides measure-theoretic probability, but not the layer these proofs work in (oracle models, adapted filtrations, martingale-difference and variance bounds, Bregman and proximal machinery, tail arguments), so most of the model is built rather than looked up, about 15,000 lines per task. Because the text underdetermines the model, whether a given model supports a proof step often becomes clear only when the proof reaches that step, so the model must be revised during proving.
The difficulty is two-sided. If the model is held fixed, an obligation that needs a missing interface property cannot be met, and a long development stalls. If the model is revised freely, a single weakened definition, or a premise that assumes what the source proves, propagates to every lemma built on it; the proof still compiles and the target statement may look unchanged (Kim et al., 2026), so a check at the end may not see it. Prior long-horizon systems settle the model's meaning mainly before proving or check it mainly at the end. LeanMarathon (Zhang et al., 2026) reviews targets adversarially before proving and assumes that the related Lean library is "sufficient and complete"; Trellis (Pegden, 2026) has a human ratify the target closure; Beyond the Library (Soltani Moakhar et al., 2026) extends and validates new definitions before formalizing the main theorems; Archon (Ju et al., 2026) revises its plan freely and checks the final statement with a comparator.
Our contribution: proof-obligation-driven co-evolution. Open proof obligations decide where and when the model is revised, and each revision is checked against the source when it is made.
Our mechanism turns the challenge of faithfully modeling an entire algorithm into a sequence of reconstruction tasks, each governed by a signature contract. Each contract specifies the source correspondence to preserve and the proof obligations to discharge. Starting from the target proof, these obligations drive the construction of the required definitions, interfaces, and lemmas, progressively developing the theory from the top down.