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

> Discover how LeanAgent's best-first tree search algorithm proves 'sorry' theorems by prioritizing tactic states and expanding promising nodes to achieve ProofFinished.

- Repository: [LeanDojo/leanagent](https://github.com/lean-dojo/leanagent)
- Tags: deep-dive
- Published: 2026-03-05

---

**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`](https://github.com/lean-dojo/leanagent/blob/main/prover/proof_search.py) at lines 21–25, the `BestFirstSearchProver.search` method initializes this structure:

```python

# 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`:

```python
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`:

```python
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`:

```python
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`:

```python
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`](https://github.com/lean-dojo/leanagent/blob/main/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:

```python
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:

```python
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`](https://github.com/lean-dojo/leanagent/blob/main/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`](https://github.com/lean-dojo/leanagent/blob/main/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.