Maestro: Global Coordination Solves Lean Proof Failure

Title

Maestro: Global Coordination Solves the Lean Proof Failure Problem

Meta Description

Maestro is a formal proof framework for Lean that uses a global coordinator to distinguish why proofs fail and replan accordingly, outperforming existing provers and native coding agents on benchmarks like PutnamBench and Lean-IMO-Bench.

Article Content

Formal proof is becoming an important means of verifying LLM-generated mathematical proofs and code, but writing proofs in Lean remains notoriously difficult. Traditional provers adopt a divide-and-conquer strategy, recursively breaking complex proof obligations into simpler lemmas and continuing to split whenever a lemma gets stuck. The problem is that a lemma can fail for very different reasons—missing guidance, the proposition itself being false, or a flawed decomposition—yet existing systems only see the single outcome "failure" and cannot distinguish the causes, let alone step outside the failed node to examine the entire proof plan. Maestro was proposed precisely to address this fundamental flaw.

Impoverished Failure Information Leads Proofs Astray

The core pain point of existing provers is not insufficient compute, but overly thin failure feedback. When a lemma cannot be proved, the system only receives a "failure" signal and knows neither whether the prover needs more specific hints, whether the lemma itself is wrong, nor whether the upstream decomposition is flawed. Because its response is confined to the failed node, the system cannot go back and revise the higher-level plan, and can only continue decomposing along a possibly flawed proof direction until the budget is exhausted and the entire proof attempt collapses. This pattern of "local response, global blindness" is especially fatal on hard problems.

Maestro's idea is to have the prover report "why it failed" rather than merely "it failed." This change looks simple, yet it turns a previously closed failure signal into an information source that the coordinator can use for decision-making.

Basic Concepts of Lean and Formal Proof

Lean is an interactive theorem prover and also a programming language based on dependent type theory. In Lean, a mathematical proposition is expressed as a type, and a proof of that proposition is a term of that type. The prover's job is to construct this term; once constructed successfully, the kernel independently checks its correctness, so formal proofs carry very high credibility. Lean 4 and its companion math library Mathlib have become the de facto standard for formal mathematics, and benchmarks such as arXivLean and PutnamBench are built on top of them.

Divide-and-Conquer Proof Strategy

When facing a complex goal, traditional automated provers typically use a decomposition strategy: splitting a large proof obligation into several smaller lemmas, proving these sub-lemmas first, and then combining them. This strategy mirrors the common "lemma–theorem" structure in mathematics, but when a sub-lemma cannot be proved, the system lacks the ability to diagnose the cause of failure. Because each prover instance only sees its own local goal, it cannot determine whether the failure stems from its own lack of capability or from an upstream decomposition that is itself unreasonable—this is the root of "local response, global blindness."

Agentic Proof and the Coordinator

Agentic proof refers to having an LLM act as an autonomous agent that invokes tools such as tactics and lemma search within the proof environment to iteratively advance the proof. Unlike single-shot generation, the agentic approach allows the model to observe environment feedback and adjust its strategy. Maestro's coordinator is a meta-level agent: it does not write proofs directly but maintains a structured representation of the entire proof tree, receives failure reports from the various sub-provers, and decides the next action accordingly. This layered "coordinator–prover" architecture decouples global planning from local search, allowing failure information to flow across levels.

How the Coordinator Globally Schedules the Proof Process

Maestro is a Lean prover framework whose core is a coordinator that can see the full proof tree. When a prover reports a failure cause, the coordinator chooses a response based on the global state: supplying additional guidance to the stuck prover, correcting an erroneous lemma, or retracting a flawed subtree and replanning. These three responses correspond respectively to the three root causes of failure, avoiding the blindness of the past approach of "continuing to decompose across the board."

This mechanism also extends to verified code synthesis. When the checker produces a counterexample, the code is sent back for repair rather than repeatedly attempting along the wrong path. The coordinator's role here is essentially a scheduling hub with global information, allowing every local failure to be re-evaluated within the overall plan.

Benchmarks: Largest Gains on Research-Level Mathematics

The research team evaluated Maestro with four frontier LLMs across seven mathematics and three software verification benchmarks. On every benchmark where native coding agents (Claude Code or Codex) had not yet saturated, Maestro proved more targets, with the largest improvement on research-level mathematics.

The specific numbers are quite convincing. Using Claude Opus 5, Maestro autonomously discovered proofs for 34 of 48 theorems in the June 2026 version of arXivLean, whereas the native agent managed only 19. On benchmarks shared with published prover systems, Maestro won across the board: solving 669/672 on PutnamBench, 59/60 on Lean-IMO-Bench, and 6/6 on IMO 2026. These results show that the gains from global coordination are not confined to one type of problem but hold in both mathematics and software verification.

What These Benchmarks Mean

PutnamBench collects problems from the William Lowell Putnam Mathematical Competition, which is known for its difficulty and its need for clever constructions, making it a classic benchmark for measuring automated theorem proving capability. Lean-IMO-Bench comes from formalized versions of International Mathematical Olympiad (IMO) problems, emphasizing elementary but creatively insightful proofs. arXivLean is a benchmark built by extracting and formalizing theorems from arXiv mathematics papers; as research-level mathematics, its difficulty and background knowledge requirements far exceed those of competition problems, so improvements on this benchmark best demonstrate the method's generalization ability. IMO 2026 refers to a formalized set of the 2026 International Mathematical Olympiad problems.

Pass@k and the Autonomous Proof Rate

Such benchmarks typically report "how many problems were solved," i.e., the number of targets a prover successfully completes a formal proof for within a given budget. "Autonomously discovering proofs" means the system independently searches out a complete proof without human-provided proof sketches or key lemmas. Comparisons on benchmarks shared with published prover systems rule out bias from problem selection, making Maestro's advantage more convincing.

Implications of Coordinated Proving

Maestro's value goes beyond refreshing benchmark numbers. It reveals a more general design principle: when failure causes can be expressed in a structured way, a system can move from "blind search" to "evidence-based scheduling." This idea has direct relevance for workflows that rely on LLMs for formal verification—whether mathematical theorem proving or verified code synthesis, failure should not be merely a termination signal but an information entry point that triggers global replanning.

From an engineering perspective, Maestro does not reinvent the prover; it adds a layer of coordination logic on top of existing provers, trading improved information flow for greater search efficiency. This path of "changing collaboration rather than the kernel" may be more sustainable for building more reliable AI-assisted formal toolchains than simply stacking up model capability.

One-line Summary

Maestro uses a global coordinator to make Lean provers report failure causes, enabling global replanning and significantly raising the success rate of formal proofs.

Paragraph Summary

The article introduces Maestro, a formal prover framework for Lean. Existing provers use a divide-and-conquer strategy but return only a "failure" signal when a lemma fails, unable to distinguish missing guidance, a false proposition, or a flawed decomposition, so the system can only respond locally within the failed node and exhaust its budget along the wrong direction. Maestro's core is to have provers report failure causes and to have a coordinator that sees the full proof tree schedule them: supplying guidance, correcting erroneous lemmas, or retracting flawed subtrees to replan; the same mechanism also applies to verified code synthesis. Evaluations across four frontier LLMs and ten benchmarks show Maestro outperforms native coding agents on all unsaturated benchmarks, with the largest gains on research-level mathematics—for example, under Claude Opus 5 it autonomously proves 34/48 on arXivLean versus only 19/48 for the native agent.