How the Best-First Tree Search Algorithm Proves 'Sorry' Theorems in LeanAgent

LeanAgent's best-first tree search algorithm proves 'sorry' theorems by maintaining a priority queue of tactic states ordered by cumulative log-probability, iteratively expanding the most promising nodes until it discovers a sequence of tactics that reaches a ProofFinished state.

LeanAgent is a neural theorem prover built on LeanDojo that automatically discovers proofs for Lean theorems, including those marked with sorry as proof placeholders. The best-first tree search algorithm treats proof construction as a heuristic search problem, using a language model's confidence scores to guide exploration toward valid proof paths while avoiding exhaustive enumeration.

How the Best-First Tree Search Works

The algorithm operates as an asynchronous best-first search over a tree of tactic states, where each node represents a partial proof attempt.

Step 1: Initialize the Search Tree

The search begins by creating a LeanDojo environment for the target theorem. The initial tactic state becomes the root InternalNode with a cumulative log-probability of 0.

In prover/proof_search.py at lines 21–25, the BestFirstSearchProver.search method initializes this structure:

# Root node initialization (conceptual)

root = InternalNode(state=init_state, cumulative_logprob=0.0)

This root represents the starting goal state derived from the theorem's type signature and context.

Step 2: Maintain a Priority Queue

Nodes are stored in an asyncio.PriorityQueue ordered by negative cumulative log-probability. Since Python's priority queue returns the smallest value first, negating the log-probability ensures that higher-probability nodes (more confident tactics) are expanded first.

As implemented at proof_search.py:L58–L60:

priority_queue.put_nowait((-self.root.priority, self.root))

Step 3: Expand the Highest-Priority Node

The main loop pops the node with the greatest priority from the queue. The node's tactic state is serialized to a string, and the tactic generator proposes candidate tactics with associated log-probabilities.

This expansion logic appears at proof_search.py:L94–L100:

search_node = priority_queue.get_nowait()

# ... state string conversion ...

tactics_with_scores = self._generate_tactics(state_str)

Step 4: Execute Tactics via Lean Environment

For each candidate tactic, the prover executes dojo.run_tac to validate the tactic against the current state. This occurs in the _run_tactic method at proof_search.py:L63–L91.

The execution yields one of three outcomes:

• ProofFinished – The tactic completes the proof
• Error (LeanError, TimeoutError, ProofGivenUp) – The tactic fails
• New TacticState – The tactic produces subgoals

Step 5: Create Child Nodes and Update Probabilities

Child nodes are instantiated based on the execution result at proof_search.py:L74–90:

• Success → ProofFinishedNode (terminal, status = PROVED)
• Error → ErrorNode (terminal, status = FAILED)
• New state → InternalNode with cumulative_logprob = parent.logprob + tactic.logprob

Step 6: Re-queue Open Nodes and Record Edges

Only nodes with status OPEN are pushed back into the priority queue, preserving the best-first ordering. This happens at proof_search.py:L92–94:

if result_node.status == Status.OPEN:
    priority_queue.put_nowait((-result_node.priority, result_node))

After processing all tactics for a node, the algorithm records the explored edges at proof_search.py:L26–28:

search_node.out_edges = results

This triggers recomputation of status and distance_to_proof metrics for ancestor nodes, allowing the tree to track how close each branch is to a complete proof.

Step 7: Termination and Proof Extraction

The search loop terminates when any of the following conditions are met (as checked at proof_search.py:L61–93):

• The priority queue is empty (exhausted search)
• The root status becomes PROVED (success)
• Resource limits exceeded (timeout or max_expansions)

When a proof is found, extract_proof in search_tree.py at lines 83–105 traverses the tree from root to the terminal ProofFinishedNode. At each step, it selects the child edge with the smallest distance_to_proof, collecting the tactics that form the final valid proof.

Why It Works for 'Sorry' Theorems

A theorem ending with sorry is a placeholder without an implemented proof body. The best-first tree search algorithm treats the initial tactic state of a sorry theorem exactly like any other open goal: it repeatedly expands promising tactics—those with high language model confidence—and explores the resulting states until a sequence reaches ProofFinished.

The best-first nature guarantees that the most promising branches are explored first, dramatically reducing the search space compared to breadth-first or depth-first approaches. This is critical for sorry theorems, where no prior proof structure exists to guide the search.

Implementation Example: Single Theorem Proof

The following example demonstrates how to configure BestFirstSearchProver to search for a proof:

from lean_dojo import LeanGitRepo, Theorem
from prover.proof_search import BestFirstSearchProver
from generator.model import FixedTacticGenerator

# Load repository and target theorem

repo = LeanGitRepo(path="/path/to/mathlib")
theorem = repo.get_theorem("Nat.add_comm")
pos = theorem.positions[0]

# Configure tactic generator and prover

tac_gen = FixedTacticGenerator(tactic="simp", module=None)
prover = BestFirstSearchProver(
    tac_gen=tac_gen,
    timeout=30,
    max_expansions=500,
    num_sampled_tactics=5,
    debug=False,
)

# Execute search

result = prover.search(repo, theorem, pos)

if result and result.status == result.status.PROVED:
    print("Proof found:", result.proof)

This configures a 30-second timeout with a maximum of 500 node expansions, sampling 5 tactics at each step.

Distributed Search Across Multiple Workers

For large-scale proving, DistributedProver parallelizes the search across multiple Ray workers:

from prover.proof_search import DistributedProver
from lean_dojo import LeanGitRepo

repo = LeanGitRepo(path="/path/to/mathlib")
theorems = [repo.get_theorem("Nat.add_comm"), repo.get_theorem("Nat.mul_comm")]
positions = [thm.positions[0] for thm in theorems]

distributed = DistributedProver(
    use_vllm=False,
    ckpt_path="checkpoints/leanagent.ckpt",
    num_workers=4,
    num_gpus=0,
    timeout=60,
    max_expansions=2000,
    num_sampled_tactics=8,
    raid_dir="/tmp/raid",
    checkpoint_dir="checkpoints",
    debug=False,
)

results = distributed.search_unordered(repo, theorems, positions)

This configuration uses 4 CPU workers with retrieval-augmented generation (RAG) to prove multiple theorems in parallel.

Summary

• Best-first search uses a priority queue ordered by negative cumulative log-probability to explore the most promising proof branches first.
• Node expansion in BestFirstSearchProver generates tactics via a language model, validates them through LeanDojo, and creates child nodes with updated probability scores.
• Proof extraction walks the completed tree from root to terminal node, selecting edges with minimal distance_to_proof to construct the tactic sequence.
• The algorithm handles sorry theorems by treating them as standard open goals with no initial proof structure, searching until a valid tactic sequence reaches ProofFinished.
• Distributed execution via DistributedProver and Ray enables parallel proof search across multiple theorems and workers.

Frequently Asked Questions

How does the priority queue determine which node to expand next?

The priority queue orders nodes by negative cumulative log-probability (higher probability = higher priority). As implemented in prover/proof_search.py, each node's cumulative_logprob aggregates the log-probabilities of all tactics taken from the root to that node. This ensures the search prioritizes branches where the language model is most confident.

What happens when a tactic times out or produces an error?

When dojo.run_tac encounters a TimeoutError, LeanError, or ProofGivenUp signal, the _run_tactic method creates an ErrorNode marked with status FAILED. This terminal node is not re-queued, but its parent records the failure via out_edges, allowing the search to backtrack and try alternative tactics.

Can this algorithm prove theorems that don't contain 'sorry'?

Yes. The best-first tree search algorithm works with any Lean theorem that has a goal state requiring proof. While sorry theorems represent incomplete proofs, the algorithm can also discover alternative proofs for existing theorems or fill in explicit proof terms where none exist. The search process treats all initial states identically, regardless of whether the source code contains a sorry placeholder.

How does the proof extraction mechanism ensure the shortest or best proof?

The extract_proof method in prover/search_tree.py selects child edges based on the distance_to_proof metric rather than raw probability. This metric estimates the minimal number of steps remaining to reach a ProofFinished state. By always choosing the child with the smallest distance_to_proof, the extraction yields the most direct path found during search, not necessarily the highest-probability path.

{
  "mcpServers": {
    "instagit": {
      "command": "npx",
      "args": ["-y", "instagit@latest"]
    }
  }
}