acceptodds
Withdrawn from ICLR 2027

Decomposed Online Learning for Adaptive LLM Inference in Formal Mathematics

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Recent advances in agentic mathematical reasoning show that frontier Large Language Models (LLMs) can solve highly challenging mathematical problems. However, these successes often require substantial inference-time compute, making them prohibitively expensive for routine theorem proving. Crucially, subgoals within a proof vary significantly in difficulty, and many can be solved by smaller, more efficient models. We present _METIS_, a budget-aware agentic framework that uses online learning to reduce inference cost while preserving overall capability. Rather than relying on a fixed model, we use feedback from the Lean compiler to (1) decompose the problem into sub-lemmas, (2) adaptively assign budget-efficient, capable models to individual sub-lemmas using a non-stationary online algorithm, and (3) reassemble the complete proof. The decomposition improves sample complexity by generating more tasks for the online learner, and improves predictive power since sub-lemmas are simpler than the original problem. Comprehensive evaluation across four benchmarks demonstrates that _METIS_ improves the trade-off between inference cost and proof resolution rate. Specifically, _METIS_ achieves an accuracy comparable to the base Claude-Opus-4.8 model while requiring 68.3% less budget on average. Furthermore, _METIS_ matches the strongest model selection baseline accuracy while reducing total budget expenditure by an absolute 13.6%. Furthermore, under unstable inference environments, our framework maintains robust performance, with up to twofold lower standard deviation in both inference accuracy and budget than static methods.

Primary area:
generative models
Keywords:
formal mathematics, online learning, ai for math

Reviews

Among:
Shape:
1234this paper, Bottom 2%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.33 over 3 reviews, above 2% of the others.
Reviewer_z3gTOpenReview ↗
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 O(TΥTlog⁡T)O(\sqrt{T \Upsilon_T} \log T) 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 ξ>1/2\xi > 1/2, whereas Appendix C specifies ξ=0.05\xi = 0.05 for the main experiments, and the ablation studies consider 0.01≤ξ≤0.250.01 \leq \xi \leq 0.25.

    Furthermore, the theoretically prescribed discount factor depends on ΥT\Upsilon_T and TT, 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?

Reviewer_7h7SOpenReview ↗
Rating
1
Confidence
4
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

METIS uses a strong model to draft Lean proof skeletons, routes unresolved lemmas to cheaper models with cost-aware discounted UCB, and repairs and verifies the assembled proof. The paper contributes an integrated proving workflow, a 290-lemma routing dataset, and experiments on four benchmarks plus simulated price and availability changes.

Critical strengths

S1. The workflow addresses a practical problem: reserve the expensive model for planning and repair, and use Lean checks to delegate proof work.

S2. There is meaningful evidence of lower dollar cost. The case studies explain how cheaper workers make broader search affordable.

S3. Appendix H compares against baselines like ordinary UCB and epsilon-greedy. Its price and availability replays provide substantive evidence that adaptation can improve cost and stability.

Critical weaknesses

W1. On the IMO subset, whole-problem CAD-UCB and METIS both reach 85%, at reported costs of $3.96 versus $75.18 (Tables 1-2). Whole-problem routing gets five attempts rather than one, preventing a controlled attribution to decomposition. Putnam provides important counterevidence, but lacks this comparison, leaving unclear when the extra drafting stage improves the attainable cost-accuracy trade-off.

W2. Appendix H's replay comparisons support adaptation, but do not test complete proof runs under disruptions. Whether the replay advantage translates into better final proof success per dollar remains open.

Questions for authors
  1. At matched total dollar budgets, how do whole-problem routing and METIS compare, especially on Putnam, with all retries charged?
  2. Does existing evidence connect the replay gains to complete-proof savings over ordinary UCB, including coordinator work?
Reviewer_EJ9oOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper proposes METIS, a cost-aware agentic pipeline for Lean theorem proving. A strong base model first drafts a compiling proof skeleton whose hard steps are extracted as standalone sorry helper lemmas. Each helper lemma is then routed to one of four cheaper models (DeepSeek-V4-Flash/Pro, GPT-5.6-Luna, GLM-4.7-Flash) by CAD-UCB, i.e., Proposition 1 gives an O(√(TΥ_T log T)) regret bound for this setting. The authors also release METIS-DS (290 decomposed sub-lemmas from DeepSeek-ProverBench. Experiments on FATE-M, the miniF2F-v2s IMO subset, Putnam 2025 and DeepSeek-ProverBench against baselines show accuracy comparable to Opus at 68.3% lower cost, and lower cost than the strongest router at matched accuracy.

Critical strengths
  1. Lean helper lemmas are natural, independently checkable routing units, and compiler-verified success plus measured cost yields a bandit reward with no learned judge.
  2. The method is training-free and harness-agnostic. Compared with an Opus-only agent it gives large cost reductions. This is a practically relevant direction for making agentic formal proving affordable.
  3. The paper releases METIS-DS with a datasheet, full prompts, per-provider prices and detailed case studies
Critical weaknesses
  1. In Table 2, query-level CAD-UCB (no decomposition, no Opus) matches METIS's accuracy at 13–19× lower cost: FATE-M 88.7% / $7.49 vs. 89.3% / $98.24, and miniF2F-v2s 85.0% / $3.96 vs. 85.0% / $75.18. This contradicts the claim in Sec. 5.2.
  2. METIS routes 71–93% of lemmas to DeepSeek-V4-Flash. CausalLM, which routes 96–100% to that model, matches its accuracy, so a "decomposition + fixed DeepSeek-V4-Flash" baseline is missing.
  3. In App. I, routed workers account for only $1.18 of $43.72 and $1.67 of $19.87, so the bandit controls a small share of spend.
  4. Twofold lower std than static methods contradicts Figs. 5/7/8, where CAD-UCB has the largest std.
  5. Proposition 1 requires ξ > 1/2, but the experiments use ξ = 0.05.
Questions for authors
  1. Given Table 2, why prefer METIS over query-level CAD-UCB? Please add decomposition + fixed DeepSeek-V4-Flash, and query-level CAD-UCB on Putnam.
  2. What exactly does "No Routing" run (an end-to-end Opus agent, or the same draft with Opus workers)? What fraction of METIS's cost goes to routed sub-models?

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

Related papers

Discussion (0)

Sign in to comment.