Premise Selection in Large Formal Libraries

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 275 papers87 conceptsfrozen 2026-10-04

In formal mathematics, proving a new theorem is rarely a matter of starting from first principles. Instead, it is a process of assembly: a mathematician must identify and apply a handful of specific lemmas from a vast library of tens of thousands of existing results. For automated systems, this "needle in a haystack" problem—known as premise selection—is the primary bottleneck preventing AI from reaching human-level proficiency in formal verification.

The Search Space Explosion

The fundamental challenge in automated theorem proving (ATP) is not just the logic of the proof itself, but the combinatorial explosion of the search space. As noted by Cezary Kaliszyk and Josef Urban in Efficient Semantic Features for Automated Reasoning over Large Theories, including too many irrelevant axioms overwhelms a solver, while missing a single necessary lemma makes the proof impossible.

Traditional Large Language Models (LLMs) struggle with this because their internal memory is often insufficient to recall the exact naming conventions or locations of theorems within massive codebases like Lean's mathlib. Even when a model understands the underlying logic required to bridge a gap, Xiaowen Yang and colleagues show in FormalML that the model often fails simply because it cannot retrieve the precise formal identifier required by the theorem prover.

From Internal Memory to Retrieval-Augmented Proving

To solve this, researchers have moved toward Retrieval-Augmented Generation (RAG). Instead of forcing a model to memorize the entire library, systems like LeanDojo, developed by Aidan M. Swope and others, use a retriever to surface relevant premises from the library based on the current proof state. Their model, ReProver, demonstrates that a retrieval-augmented approach can outperform much larger models like GPT-4 by providing the necessary context on-demand.

This retrieval isn't just about keyword matching. Modern systems use sophisticated embeddings to capture the "meaning" of a mathematical goal:

  • Graph Embeddings: Mingzhe Wang and Yihe Tang introduced FormulaNet, which treats mathematical formulas as graphs to preserve the structural relationships between operators and variables.
  • Tree-Based Filtering: Zichen Wang and Anjie Dong argue in Tree-Based Premise Selection for Lean4 that modeling expressions as trees and using multi-stage filtering (like Tree Edit Distance) provides more precision than semantic embeddings alone.

The "Hammer" Mechanism

The most successful integration of these ideas is the "Hammer" tool. A hammer acts as a bridge between the high-level reasoning of an LLM (or a human) and the raw computational power of first-order logic solvers.

In Thor: Wielding Hammers to Integrate Language Models and Automated Theorem Provers, Albert Q. Jiang and Wenda Li show how an LLM can be trained to recognize when it needs to call a hammer. The hammer then performs premise selection to find a small, relevant subset of the library (typically 16 to 32 premises) and hands them to an external solver to discharge the goal.

This division of labor is crucial: the LLM handles the "vibe" and strategy of the proof, while the premise selector and solver handle the grueling task of logical verification. This approach has been further refined in LeanHammer, where Jeremy Avigad and Thomas Zhu demonstrate that a neural premise selector (LeanPremise) can adapt dynamically to a user's local code, solving significantly more goals than previous symbolic methods.

Why It Works: Reducing Search to Filtering

Premise selection works because it transforms an unbounded search problem into a ranking and filtering problem. By using contrastive learning—as seen in Magnushammer—models learn to map "proof states" and "useful lemmas" into the same vector space.

When the prover encounters a new goal, it simply looks for the nearest neighbors in that space. This allows the system to ignore 99.9% of the library and focus its computational energy on the few facts that actually matter. As Junqi Liu and the Numina-Lean-Agent team have shown, this capability allows AI to move beyond competition math and begin assisting in the formalization of complex, research-level mathematics.

Papers in this version

Showing 60 of 75 papers.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 40 papers
  2. Version 1 · 2026-10-04 · 75 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_premise_selection_bottleneck_6bfc7058,
  title = {premise selection bottleneck},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/premise-selection-bottleneck/rdr_6bfc705883f54da5b3f66fb80cd0b6d8},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 1, frozen text):

@misc{lacuna_premise_selection_in_large_formal_librar_6bfc7058_v1,
  title = {Premise Selection in Large Formal Libraries},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/premise-selection-in-large-formal-libraries/rdr_6bfc705883f54da5b3f66fb80cd0b6d8/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-21},
}