Can LLM Aid in Solving Constraints with Inductive Definitions?

Weizhi Feng, Shidong Shen, Jiaxiang Liu, Taolue Chen, Fu Song, Zhilin Wu (🖂) · 2026

Read Can LLM Aid in Solving Constraints with Inductive Definitions? by Weizhi Feng, Shidong Shen, Jiaxiang Liu, Taolue Chen, Fu Song, Zhilin Wu (🖂) (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2603-03668.txt.

Introduction

Weizhi Feng and five colleagues recruit language models to help theorem provers with their hardest bottleneck. Constraints involving inductive definitions, recursive data types and functions, resist today's best solvers, which offer only limited support for them. Proofs stall for want of auxiliary lemmas, the small helper claims human experts invent. Their 2026 approach uses structured prompts to make a language model propose exactly those lemmas.

The full method is neuro-symbolic. The model iteratively conjectures lemmas, and a constraint solver checks each one for validity and usefulness toward the goal, so bad guesses die fast. Benchmarks span algebraic data types and recurrence relations. The hybrid improves on state-of-the-art SMT and CHC solvers, solving about a quarter more proof tasks involving inductive definitions than the solvers manage alone.

Catalog record

CREATORWeizhi Feng, Shidong Shen, Jiaxiang Liu, Taolue Chen, Fu Song, Zhilin Wu (🖂)
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE60167
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2603.03668

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Can LLM Aid in Solving Constraints with Inductive Definitions? Weizhi Feng, Shidong Shen, Jiaxiang Liu, Taolue Chen, Fu Song, Zhilin Wu (🖂) Abstract Solving constraints involving inductive (aka recursive) definitions is challenging. State-of-the-art SMT/CHC solvers and first-order logic provers provide only limited support for solving such constraints, especially when they involve, e.g., abstract data types. In this work, we leverage structured prompts to elicit Large Language Models (LLMs) to generate auxiliary lemmas that are necessary for reasoning about these inductive definitions. We further propose a neuro-symbolic approach, which synergistically integrates LLMs with constraint solvers: the LLM iteratively generates conjectures, while the solver checks their validity and usefulness for proving the goal. We evaluate our approach on a diverse benchmark suite comprising constraints originating from algebraic data types and recurrence relations. The experimental results show that our approach can improve the state-of-the-art SMT and CHC solvers, solving considerably more (around 25%) proof tasks involving inductive definitions, demonstrating its efficacy. 1 Introduction Inductive definitions are prevalent in program verification. Typically, they exhibit in two forms, i.e., algebraic data types (ADTs) and recursively defined functions (RDFs). An ADT defines a type whose elements are constructed by a finite number of applications of a given set of rules. ⬇ 1 datatypes Nat := zero | succ ( n : Nat ) 2 fun plus ( Nat , Nat ): Nat { 3 \forall y \in Nat . plus ( zero , y ) = y 4 \forall x \in Nat , y \in Nat . plus ( succ ( x ), y ) = succ ( plus ( x , y )) 5 } 6 fun mult ( Nat , Nat ): Nat { 7 \forall y \in Nat . mult ( zero , y ) = zero 8 \forall x \in Nat , y \in Nat . mult ( succ ( x ), y ) = plus ( mult ( x , y ), y ) 9 } 10 property : \forall x \in Nat , y \in Nat . mult ( x , y ) = mult ( y , x ) Listing 1: A pseudocode program: the running example As an example, Listing 1 defines natural numbers ( Nat ) as an ADT, and two operations on natural numbers as RDFs. Nat is defined as either zero ( zero ) or the successor of another Nat , given by succ ( n ) . Both RDFs plus and mult are specified through assertions with universal quantifiers, serving as axioms. • The addition operation ( plus ) (lines 2 – 5 ) is recursively defined by two cases: (i) adding zero to any natural number y yields y , and (ii) adding the successor of any natural number x to y yields the successor of plus ( x , y ) . • The multiplication operation ( mult ) (lines 6 – 9 ) is recursively defined by two cases as well: (i) multiplying zero by any natural number y results in zero , and (ii) multiplying the successor of any natural number x by y is the addition of mult ( x , y ) and y . In this example, the proof goal is the commutativity of the multiplication operation mult , formulated as property at line 10 in Listing 1 . Such ADTs are ubiquitous in functional programming languages (e.g., Gallina) for interactive theorem provers (ITPs, e.g., Rocq [ 3 ] ), and are increasingly being supported by other languages such as TypeScript and Rust. Inductive Reasoning. Program verification requires reasoning about properties of inductive definitions, including ADTs and RDFs. The standard reasoning process typically consists of two steps: first proving the base case(s) and then proving the inductive case(s) with inductive hypotheses as premises. For example, in Listing 1 , one may apply induction on the natural number x , leading to the base case where x is zero and an inductive case where x is succ ( x ’) in which the property is assumed to hold for x ’ . These two cases yield two verification conditions (VCs): \displaystyle\forall\ y\in\texttt{Nat}.\ \texttt{mult}(\texttt{zero},y) \displaystyle=\texttt{mult}(y,\texttt{zero}), (1) \displaystyle\forall\ x^{\prime},y\in\texttt{Nat}.\ \texttt{mult}(x^{\prime},y) \displaystyle=\texttt{mult}(y,x^{\prime})\rightarrow \displaystyle\texttt{mult}(\texttt{succ}(x^{\prime}),y)=\texttt{mult}(y,\texttt{succ}(x^{\prime})). Different techniques can be applied for inductive reasoning, ranging from manual to fully automated. In general, ITPs such as Rocq [ 3 ] , Isabelle [ 35 ] and Lean [ 13 ] , and semi-automated verifiers (aka deductive verifiers) such as Dafny [ 31 ] , Stainless [ 22 ] and Verus [ 30 ] , require user intervention. In contrast, automated constraint solving, including SMT solving and first-order logic theorem proving, is designed to operate without user intervention. Typically, induction schemas are incorporated into SMT solvers [ 41 ] or into superposition-based first-order logic theorem provers [ 8 , 39 , 16 , 19 , 20 , 23 , 21 ] , enabling automatic generation of base and inductive cases as verification conditions with inductive hypotheses as premises. However, many proof goals with inductive definitions cannot be solved by solely applying the inductive hypotheses and axioms. Consequently, additional auxiliary lemmas are required to complete the proof. Namely, to prove A\rightarrow P where A and P are the premise and the conclusion, respectively, we may introduce a set of auxiliary lemmas \{L_{i}\}_{i\in I} such that A\rightarrow L_{i} holds for each i\in I , and A\wedge\bigwedge_{i\in I}L_{i}\rightarrow P holds. Lemma Generation Methods and Limitations. This paper tackles automated generation of auxiliary lemmas in constraint solving. The existing methods can roughly be classified into three main categories. First, theory exploration method, implemented in solvers such as cvc5 [ 2 ] , iteratively enumerates conjectures starting from small terms and applies heuristic checks to quickly filter out invalid ones before verifying their validity and usefulness for assisting in proving the goal [ 7 , 41 , 43 ] . Second, the generalization method, implemented in solvers such as Vampire [ 28 ] , identifies common sub-terms in the proof goal and replaces them with new variables to find auxiliary lemmas that are simpler and can generalize the goal [ 19 ] . Third, Constrained Horn Clauses (CHCs) based method [ 25 ] treats inductive definitions as transition systems and solves the verification problem by synthesizing inductive invariants. (Cf. Section 5 for a brief review of the related work.) Despite their effectiveness in certain scenarios, these methods have significant limitations. Theory exploration is effective for generating simple lemmas but often struggles with discovering more complicated lemmas required for inductive proofs. Indeed, the representative state-of-the-art SMT solver, cvc5, fails to prove the property given in Listing 1 (cf. Appendix 0.A for details). Generalization methods have limited expressiveness and cannot handle more general problems. CHC-based methods have limited capability to handle inductive definitions, particularly RDFs. Overall, these traditional logic-based methods mostly rely on fixed mechanisms and heuristic strategies, which often suffer from limited scalability or expressiveness, restricting the usability and applicability of automated constraint solving in program verification. LLM-aided Solving. LLMs have demonstrated remarkable capabilities in code generation [ 18 , 47 , 46 , 53 ] , program specification inference [ 50 , 34 ] , loop-invariant generation [ 5 , 51 , 37 ] , and interactive theorem proving [ 40

Read the complete text