- Rating
- 1
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The paper presents a framework for reducing the inference cost of LLM-based formal theorem proving through proof decomposition and online model selection. The central observation is that proof obligations differ in difficulty, and many subgoals can be solved by cheaper language models without invoking an expensive frontier model.
METIS consists of two main phases. First, a powerful base model constructs a Lean proof skeleton containing independently solvable helper lemmas, which is checked for structural correctness using the Lean compiler. Second, a cost-aware discounted upper confidence bound algorithm (CAD-UCB) selects among several cheaper models to discharge individual proof obligations. The algorithm uses compiler-verified proof success and inference cost as feedback, with exponential discounting to adapt to changes in model performance, pricing and availability. The resulting proofs are assembled and verified in Lean. The authors also introduce METIS-DS, a dataset containing 290 decomposed Lean sub-lemmas and proof trajectories generated by four language models.
METIS is evaluated on FATE-M, miniF2F-v2s, Putnam 2025 and a subset of DeepSeek-ProverBench, with comparisons against fixed-model, random and learned routing baselines. The paper reports substantial reductions in inference cost while maintaining competitive proof success. Additional experiments investigate online adaptation to model-pricing changes, model availability and provider uptime, while case studies illustrate how inexpensive sub-agents can contribute to solving difficult Putnam problems.
Critical strengths
-
A practically motivated research problem.
-
Empirical evidence of a substantial reduction in inference cost.
-
Concrete end-to-end case studies.
Critical weaknesses
-
Very limited novelty is relatively limited.
The two principal components of METIS are based on established techniques. Decomposing complex mathematical proofs into smaller obligations has been explored by many systems (e.g., DeepSeek-Prover-V2, Seed-Prover and LEAP, just to name a few). Similarly, multi-model routing and cascading are well-established approaches to reducing LLM inference costs.
The proposed CAD-UCB algorithm applies the existing Discounted UCB algorithm to a cost-aware reward function. The paper does not introduce a new bandit selection rule, a new approach to non-stationary learning or a new method for generating proof decompositions. The main work is basically an integration of existing techniques into a Lean-based proof workflow.
-
Weakness in the design of the approach
The main motivation is the observation that different proof obligations vary in difficulty and that different models possess different mathematical capabilities. However, CAD-UCB is formulated as a conventional multi-armed bandit in which each model is an arm and its selection depends on its accumulated reward history. The algorithm does not incorporate the mathematical statement of the current lemma, its domain, syntactic complexity, proof dependencies, expected proof length or any representation of its difficulty. Consequently, it learns a global preference among models rather than which model is most suitable for a particular proof obligation.
-
Mismatch between theory and proposed system, and its assumptions are inconsistent with the experimental configuration.
Prop. 1 establishes a regret bound of order under independence, piecewise-stationary mean rewards, a positive minimum reward gap and an appropriate discount factor. However, these assumptions are not justified for the actual online theorem-proving process. In particular, successive proof obligations may have very different difficulty levels and characteristics, so their reward distributions can vary from one task to the next. Such variation is not necessarily piecewise stationary or adequately represented by a small number of environmental change points.
There is also a concrete mismatch between the theoretical and experimental settings. Prop. 1 requires the exploration coefficient , whereas Appendix C specifies for the main experiments, and the ablation studies consider .
Furthermore, the theoretically prescribed discount factor depends on and , whereas the implementation uses a fixed 0.99.
-
Experiments
Some experimental comparisons have inconsistent budget settings or do not compare equivalent workflows. In the main experiments, the base model and routing systems do not always operate under the same per-problem budget. In particular, Appendix F reports that on miniF2F-v2s the base-model budget was increased from $20 to $50 because its proof success was substantially lower under the original cap, while routing methods retained the $20 limit. Comparing performance under different budget caps does not directly establish superiority at a fixed resource level.
For the query-level experiments: Table 2 reports that query-level CAD-UCB achieves 85% accuracy at a total cost of only $3.96 on miniF2F-v2s, whereas the full METIS also achieves 85% accuracy but costs $75.18. This suggests that, at least in some cases, using cheaper models directly without the expensive strong-model drafting phase may offer a substantially better accuracy-cost trade-off.
-
Insufficient evidence of the benefit of proof decomposition itself.
METIS relies on a strong model to construct proof skeletons, but the paper does not systematically evaluate the quality, granularity or computational overhead of these decompositions. The routing comparisons on decomposed tasks use the same fixed drafting outputs, which does not demonstrate that the particular decomposition strategy is more effective than alternative proof decomposition mechanisms.
Questions for authors
Q1 How does the algorithm account for differences in the mathematical domain, difficulty and structure of individual proof obligations? Would a contextual bandit using features of the current subgoal be more appropriate?
Q2 Can the author exaplian the mismatch between theory and proposed system, and its assumptions are inconsistent with the experimental configuration.
Q3 Can the authors provide ablations separating the benefits of proof decomposition, cheaper model substitution and online routing? In particular, how often does the base model generate a valid and useful proof skeleton, how much does drafting cost and does decomposition demonstrably improve the convergence or sample efficiency of the online learner?
Q4 Why are different budget caps and numbers of proving attempts used in some comparisons? Can the authors provide accuracy–cost Pareto curves under identical per-problem budgets and comparable attempt limits?