Data-driven lemma synthesis for interactive proofs
Aishwarya Sivaraman, Alex Sanchez-Stern, Bretton Chen, Sorin Lerner, Todd D. Millstein
Abstract
Interactive proofs of theorems often require auxiliary helper lemmas to prove the desired theorem. Existing approaches for automatically synthesizing helper lemmas fall into two broad categories. Some approaches are goal-directed, producing lemmas specifically to help a user make progress from a given proof state, but they have limited expressiveness in terms of the lemmas that can be produced. Other approaches are highly expressive, able to generate arbitrary lemmas from a given grammar, but they are completely undirected and hence not amenable to interactive usage.
In this paper, we develop an approach to lemma synthesis that is both goal-directed and expressive. The key novelty is a technique for reducing lemma synthesis to a data-driven program synthesis problem, whereby examples for synthesis are generated from the current proof state. We also describe a technique to systematically introduce new variables for lemma synthesis, as well as techniques for filtering and ranking candidate lemmas for presentation to the user. We implement these ideas in a tool called lfind, which can be run as a Coq tactic. In an evaluation on four benchmark suites, lfind produces useful lemmas in 68% of the cases where a human prover used a lemma to make progress. In these cases lfind synthesizes a lemma that either enables a fully automated proof of the original goal or that matches the human-provided lemma.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
4 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- Synthesizing Implication Lemmas for Interactive Theorem Proving cites Data-driven inference of representation invariants
- Synthesizing Implication Lemmas for Interactive Theorem Proving cites Graph Representations for Higher-Order Logic and Theorem Proving
- Synthesizing Implication Lemmas for Interactive Theorem Proving cites TacTok: semantics-aware proof synthesis
- FO-Complete Program Verification for Heap Logics cites Complete First-Order Reasoning for Properties of Functional Programs
Cited by top-tier papers4
- Complete First-Order Reasoning for Properties of Functional ProgramsAdithya Murali, Lucas Peña, Ranjit Jhala, P. MadhusudanOOPSLA 2023 · 3 citations
- MathlibLemma: Folklore Lemma Generation and Benchmark for Formal MathematicsXinyu Liu, Zixuan Xie, Amir Moeini, Claire Chen et al.ICML 2026 · 2 citations
- Synthesizing Implication Lemmas for Interactive Theorem ProvingAna Brendel, Aishwarya Sivaraman, Todd D. MillsteinOOPSLA 2025
- FO-Complete Program Verification for Heap LogicsAdithya Murali, Hrishikesh Balakrishnan, Aaron Councilman, P. MadhusudanOOPSLA 2025
Builds on5
- Graph Representations for Higher-Order Logic and Theorem ProvingAditya Paliwal, Sarah M. Loos, Markus N. Rabe, Kshitij Bansal et al.AAAI 2020 · 110 citations
- TacTok: semantics-aware proof synthesisEmily First, Yuriy Brun, Arjun GuhaOOPSLA 2020 · 39 citations
- Bottom-up synthesis of recursive functional programs using angelic executionAnders Miltner, Adrian Trejo Nuñez, Ana Brendel, Swarat Chaudhuri et al.POPL 2022 · 38 citations
- Data-driven inference of representation invariantsAnders Miltner, Saswat Padhi, Todd D. Millstein, David WalkerPLDI 2020 · 33 citations
- Computing correctly with inductive relationsZoe Paraskevopoulou, Aaron Eline, Leonidas LampropoulosPLDI 2022 · 16 citations
Related papers
- Proving Functional Program Equivalence via Directed Lemma SynthesisYican Sun, Ruyi Ji, Jian Fang, Xuanlin Jiang et al.FM 2024 · 2 citations
- Theory Exploration Powered by Deductive SynthesisEytan Singher, Shachar ItzhakyCAV 2021 · 19 citations
- Rango: Adaptive Retrieval-Augmented Proving for Automated Software VerificationKyle Thompson, Nuno Saavedra, Pedro Carrott, Kevin Fisher et al.ICSE 2025 · 4 citations
- Laurel: Unblocking Automated Verification with Large Language ModelsEric Mugnier, Emmanuel Anaya Gonzalez, Nadia Polikarpova, Ranjit Jhala et al.OOPSLA 2025 · 12 citations
- Cobblestone: A Divide-and-Conquer Approach for Automating Formal VerificationSaketh Ram Kasibatla, Arpan Agrawal, Yuriy Brun, Sorin Lerner et al.ICSE 2026 · 3 citations
