Proof-Gap Retrieval: Letting a Theorem Prover Decide What to Look Up

Systems that turn a natural-language question into formal logic and hand it to a theorem prover (a program that mechanically checks whether a conclusion follows from premises) give reliable answers, but only when every needed premise is already written in the question. Real questions omit facts. Retrieval-augmented generation, where a model fetches passages from a document store before answering, is the usual fix. It fits poorly with formal reasoning, though. It retrieves by surface similarity to the question, so it misses facts that are several inferential steps away. It also floods problems that were already complete with distracting text. We propose to let the prover direct retrieval. When the prover can neither prove nor refute the conclusion, the unfinished proof shows exactly which statements are missing. Those statements become the search queries. When the prover succeeds on the given premises, nothing is retrieved at all.

Put briefly, the idea is to translate what you have into logic, ask the prover what is missing, search only for that, and admit a retrieved fact into the theory only after it has been translated into the theory's existing vocabulary and checked. A small number of separated agents carry out the loop. One translates the original problem. One proposes candidate missing premises in formal terms. A third, working in a separate context, translates each retrieved passage. The separation keeps retrieved text from contaminating the main translation. The claim to test is that queries derived from the prover's gaps find missing premises more reliably than queries written by a language model, especially as the number of missing premises grows. A second claim is that gating retrieval on prover failure removes the harm retrieval does on complete problems.

What prior work does and does not do

The prover-as-back-end pattern comes from Logic-LM. It translates problems into Prolog, first-order logic, or constraint programs and runs Pyke, Prover9, or Z3. Its self-refiner reacts only to syntax errors. LOGIC-LM++ adds pairwise comparison of candidate refinements and a backtracking step to catch semantic errors. LINC samples several translations and votes over the prover's answers. We reuse this translation-plus-prover machinery. All three systems, however, assume a self-contained problem, and LINC names rediscovering implicit premises as unsolved. Our work begins where they stop. It treats a prover result of "neither provable nor refutable" as information to act on, not as a final answer.

Two papers connect formal translation to retrieval, and both motivate our design and constrain it. DRIFT breaks a math statement into sub-concepts, retrieves Lean library definitions and examples of their use, and then formalizes. It raises GPT-4.1 on ConNF from 6.76% to 62.33% on a logical-equivalence metric. On self-contained miniF2F problems, though, retrieval hurts, and the authors name dynamic, prover-driven re-retrieval as the open next step. Improving Autoformalization Using Direct Dependency Retrieval shows that embedding search recovers exact formal dependencies poorly and that predicting names and then checking them works better. Both retrieve once, before any proof is attempted, and both retrieve library entries rather than facts stated in ordinary text. We retrieve after a failed proof, from natural-language documents. The DRIFT noise result is a direct target: our gate should produce zero regression on complete problems.

Multi-agent work supplies roles but not the prover-driven signal. MASA splits autoformalization into six agents, including prover-based and LLM-based critics and an agent that retrieves imports. The authors note it lacks central control and that its semantic critique is subjective. MAD-Logic has agents debate translations across three formalisms. It reports that quality falls after two or three rounds and that the system does no retrieval. LoCal is the closest in spirit on the retrieval side. Its agents decompose multi-hop claims, retrieve web evidence, and check logical consistency, and 37% of the errors it corrected came from bad decomposition. Its consistency checks are LLM judgments, however, and its sub-queries are written by the model. ProgramFC turns claims into Boolean programs over retrieved evidence but generates the program once. We take from this line the lesson of MAD-Logic and MASA: open-ended agent discussion drifts. In our design every agent's output must pass through the prover, and the loop's control is set by prover states rather than by agent consensus. ProofWriter and Theorem-of-Thought both generate abductive hypotheses (guesses at missing premises), but only from model weights inside a closed theory. We keep the guessing and add verification against an external corpus.

Core Claim

Let $T$ be the formal theory translated from the given premises and $C$ the translated conclusion. If the prover establishes neither $T \vdash C$ nor $T \vdash \neg C$, we look for small hypothesis sets $H$ over the predicates already in $T$ such that

$$T \cup H \vdash C \quad \text{(or } \neg C\text{)}, \qquad T \cup H \not\vdash \bot,$$

where $\bot$ denotes contradiction. Each hypothesis is then a precise description of a missing fact. Our claim is that searching for these hypotheses, rendered back into short English, beats searching with the question or with model-written sub-questions. The advantage should widen with the number of missing premises. The reason is that the gap names the intermediate entity or relation that a multi-hop chain needs, and the question itself does not contain it. HoVer shows how badly query-based retrieval degrades: TF-IDF recall falls from 80% on 2-hop to 15% on 4-hop claims.

Research Program

The system has four roles and one controller. The theory translator converts the given text into $T$ and $C$ with a fixed predicate vocabulary, using Logic-LM++-style refinement. The controller runs Prover9 in both directions. If either direction succeeds, it answers immediately; this is the gate. Otherwise the abducer receives $T$, $C$, and the prover's open goals. The open goals are unresolved subgoals from bounded backward chaining over Horn-like fragments, supplemented by Z3 countermodels for the general case. From these the abducer proposes up to $m$ formal hypotheses, and the prover filters them for consistency and sufficiency before any search. Each surviving hypothesis is rendered as a short query and sent to a BM25-plus-dense retriever.

The grounding translator works in its own context. It sees one retrieved passage and the vocabulary of $T$, but not the problem story. It must either express the passage as formulas over that vocabulary or decline. A retrieved axiom enters $T$ only if it keeps $T$ consistent and the prover confirms that it entails, or partially discharges, a hypothesis. The loop repeats until the prover succeeds or a budget of retrieval calls is spent. At that point the answer is "Unknown."

The main technical risk is vocabulary alignment. Retrieved text will say "is a kind of bird" where $T$ has Avian(x). We will measure this failure directly and examine it through error analysis. We will also test whether the grounding translator may introduce linking axioms, such as synonym definitions, which the prover accepts only when they are supported by the passage.

Benchmarks

Existing logic benchmarks are self-contained, so we build missing-premise versions. For ProofWriter under the open-world assumption at depths 3 to 5, including the paraphrased ParaRules variants, the gold proofs identify the necessary premises. We delete $k \in \{1,2,3\}$ of them and place them in a corpus alongside distractor rules from other theories that reuse the same entity names. For FOLIO (FOLIO), we use the expert first-order annotations and Prover9 to find minimal necessary premise subsets, then delete them the same way. Every item's gold label is its label under the full premise set. We check with the prover that the distractors cannot change that label. The original, complete ProofWriter and FOLIO items serve as the no-retrieval control. HOVER serves as an open-domain transfer test on real Wikipedia text with the standard retrieval setup. There, translation into logic is harder, and we expect smaller gains.

Baselines

The naive reference point is Logic-LM++ run on the incomplete problems with no retrieval. It should mostly answer "Unknown," and it sets the floor. The ceiling is the same system given the deleted premises, the oracle, which bounds what any retrieval method can recover.

The strongest existing method on the complete problems is Logic-LM++. The file reports "up to 84.80% accuracy on FOLIO" with GPT-4 (LOGIC-LM++). On complete items we count success as matching this system within noise with the same backbone. We make no claim to beat it, because the gate should simply not fire.

On the missing-premise benchmarks, which we construct, there is by definition no reported result on Lacuna. Two competitors are the real threats. The first is retrieve-then-formalize, the DRIFT pattern transplanted: the question and premises retrieve top-$k$ passages up front, and Logic-LM++ formalizes everything together. The second is model-directed iterative retrieval in the style of LoCal. The model writes sub-questions, retrieves, and repeats. Its evidence is then formalized and proved, so the only difference from our system is who writes the queries. For HOVER the reference results are ProgramFC and LoCal. The file reports LoCal's open-book Macro-F1 gain as an average of 1.78% over ProgramFC but no absolute Macro-F1, so no reported absolute number was found on Lacuna for either system. We will rerun both under our retriever.

Two ablations isolate the proposal's key ingredients. The first keeps our full loop but has the abducer write queries from the story, without the prover's open goals. This removes the prover-derived query. The second runs the whole loop in one model context, with the story and all retrieved passages together. This removes compartmentalization.

All systems use the same backbone models (GPT-4-class and an open 7B–8B model), the same corpus and retriever, the same cap on retrieval calls and total tokens, and the same prompt-tuning budget on a held-out development split. Our method counts as beating a competitor if it achieves higher label accuracy on the missing-premise sets at equal budget, with the margin growing in $k$. It must also show a false-proof rate no higher than the competitor's. The false-proof rate is the share of items proved with the wrong label because of a spurious retrieved axiom.

Why not just…?

Why not just retrieve top-k passages first and let Logic-LM++ translate everything? DRIFT shows the cost on complete problems: retrieval noise pushes miniF2F results below zero-shot. HoVer's recall collapse shows why single-shot retrieval misses premises several hops away. Our main comparison runs exactly this baseline at matched budget, broken down by $k$ and by paraphrase distance. If it matches us at $k=1$, that is expected. The claim fails only if it also matches at $k=3$.

Why not just let the model decide what to search for, as LoCal does? This is the most serious alternative. Model-written sub-questions may already name the missing intermediate facts. The first ablation above answers this directly, with everything held fixed except where the queries come from. If model-written queries recall premises as well as prover-derived ones, the contribution shrinks to the gate and the admission check. We would report it that way.

Why not just use one agent with the prover loop, skipping multi-agent roles? Evidence that separation helps comes from other settings: code testing in Self-collaboration Code Generation via ChatGPT and the context-isolation argument surveyed in A survey on LLM-based multi-agent systems. None of that evidence concerns retrieval of logical premises, so this is a real threat. The single-context ablation settles it. We specifically predict that a single context will more often translate retrieved distractors into axioms, raising the false-proof rate. If it does not, we drop the multi-agent claim and present the method as a single agent.

Why not just sample many translations and vote? Voting cannot recover a premise that no sample contains. Theorem-of-Thought also reports that self-consistency underperformed on structured dependencies. We include LINC-style voting over the oracle-free incomplete problems to confirm that it stays near the no-retrieval floor.

Decisive Checks

Three results would confirm the idea. First, on missing-premise ProofWriter and FOLIO, the accuracy gap between prover-derived and model-written queries should grow from $k=1$ to $k=3$, with premise recall measured directly. Second, on the complete originals, the gated system should retrieve on almost no items and stay within noise of Logic-LM++, whereas retrieve-then-formalize degrades. Third, the admission check should hold false proofs to a small fraction of what ungated baselines produce.

Two results would refute the central claim. If the first check shows no widening gap, the central claim is wrong. If HOVER shows gains on synthetic data that vanish on real text, the bottleneck is vocabulary alignment rather than query formation, and the next paper should be about that.