Flex: A Foundational Proof-Producing Horn Solver

arXiv:2607.12226 · cs.PL, cs.LO, cs.SE · Submitted 2026-07-14 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: We're looking at the paper: "Flex: A Foundational Proof-Producing Horn Solver".

Jane: Here's the gist of the paper. Flex is a foundational Constrained Horn Clause (CHC) solver implemented in Lean that significantly reduces the trusted base to only the kernel, enabling verification of low-level systems code using Lean’s entire proof ecosystem.

Tom: Flex achieves this through three primary contributions: 1.

Jane: CHC Encoding and Tactic Implementation: Flex encodes CHCs as plain Lean propositions, treating Horn variables as existentially bound predicates.

Tom: It demonstrates how to implement CHC solvers as tactics (meta-programs) that compute kernel-checkable proofs of these propositions.

Paper summary: Tom: So looking at this paper "Flex: A Foundational Proof-Producing Horn Solver", the authors are really showing how to take a foundational logic like Lean and apply it to solving these complex constraints in a way that leverages the whole proof system > Page one — Flex: A Foundational Proof-Producing Horn Solver <ref:2607.12226#pg1>

Jane: It’s important to remember they weren't just adding another tool; they were fundamentally changing the trust model by reducing the trusted base down to just the kernel, which allows verification of low-level systems code > Page one — Flex: A Foundational Proof-Producing Horn Solver <ref:2607.12226#pg1>

Lu: The implication is that we can leapfrog some of the limitations you see with SMT solvers regarding expressiveness and trust because you implement a solver within a foundational prover as a meta-program to compute proofs > Page two — Flex: A Foundational Proof-Producing Horn Solver <ref:2607.12226#pg1>

Meng: For deployment, the key part is understanding that while they get near perfect results on acyclic variables, you have to account for those cyclic ones where the success rate drops to eighty-two point three percent > Page three — Flex: A Foundational Proof-Producing Horn Solver <ref:2607.12226#pg1>

Lalam: And they did this by creating two verified generators—one for imperative languages and one for functional calculus—which can then be composed with their solving tactics to build a complete verifier > Page one — Flex: A Foundational Proof-Producing Horn Solver <ref:2607.12226#pg1>

Tom: So overall, it’s about making the tool robust enough to handle both the exact solutions and the approximate ones without needing a massive amount of external verification > Page two — Flex: A Foundational Proof-Producing Horn Solver <ref:2607.12226#pg1>

Jane: It shows that by using Lean's entire proof machinery, we can discharge functional correctness properties for things like in-place sorting algorithms or secure memory isolation in systems like the Tock embedded kernel > Page three — Flex: A Foundational Proof-Producing Horn Solver <ref:2607.12226#pg1,using Lean's entire proof>

Conclusion: Tom: So, we’ve been talking about this Flex paper by some authors who built a solver that uses Lean to check these kinds of constraints > Page one — Flex: A Foundational Proof-Producing Horn Solver

Jane: Right, so what’s the big picture here? They're taking this logic system and making it solve things we used to think required super complex external math tools > Page two — Flex: A Foundational Proof-Producing Horn Solver

Lu: Basically, they've got this system that lets you verify low-level code using Lean’s whole proof ecosystem instead of just relying on some SMT solver that might be too limited > Page three — Flex: A Foundational Proof-Producing Horn Solver

Meng: But what does it actually *do*? It says they've got generators for both regular computer code and functional calculus, and those generators work with the solving tactics to make a complete verifier > Page one — Flex: A Foundational Proof-Producing Horn Solver

Tom: The results show that this approach automatically checks over ninety-five percent of the constraints we put into their benchmark suite for things like sorting or memory isolation in systems > Page three — Flex: A Foundational Proof-Producing Horn Solver

Jane: That sounds pretty impressive, but there's always a catch, right? They mentioned that the success rate drops to eighty-two point three percent when they have to deal with those tricky cyclic variables > Page three — Flex: A Foundational Proof-Producing Horn Solver

Lu: That makes sense because approximating solutions for cyclic variables is where the complexity comes in; it's like, you get almost everything right unless the problem loops back on itself > Page two — Flex: A Foundational Proof-Producing Horn Solver

Meng: And from a deployment standpoint, that eighty-two percent success rate means you still have to manually check those tricky parts or use a different approach for those specific kinds of problems > Page one — Flex: A Foundational Proof-Producing Horn Solver

Tom: So, the implication is that we might be able to verify much more complex low-level systems with this method because it uses the full power of Lean’s proof engine > Page three — Flex: A Foundational Proof-Producing Horn Solver

Jane: It shifts the trust model, moving away from relying on a black box solver to having a formal mathematical proof that the system is safe > Page two — Flex: A Foundational Proof-Producing Horn Solver

Lu: And it's foundational because they built generators for both imperative and functional stuff, which means this isn't just a niche tool for one type of problem > Page one — Flex: A Foundational Proof-Producing Horn Solver

Meng: For the practical folks here, it’s about speed, though they admit their Lean backend is slower than some existing SMT methods they compared against > Page three — Flex: A Foundational Proof-Producing Horn Solver

Tom: So it’s a trade-off between absolute power and raw execution time, but the coverage of ninety-five percent of those constraints is significant > Page two — Flex: A Foundational Proof-Producing Horn Solver

Jane: It’s definitely a tool that pushes the boundaries on what we can formally verify in software, and it opens up new avenues for security research > Page one — Flex: A Foundational Proof-Producing Horn Solver

University of California San Diego · University of Chile

cs.PL, cs.LO, cs.SE

Submitted: 2026-07-14

Updated: 2026-11-16

Comments: 21 pages

Code: https://github.com/jam-khan/Flex

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 88/100

The gist: Flex is a foundational Constrained Horn Clause (CHC) solver implemented in Lean that significantly reduces the trusted base to only the kernel…

Key concepts

CHC Encoding
Flex treats Constrained Horn Clauses as plain Lean propositions where Horn variables are existentially bound predicates. This allows the solver to use Lean's entire proof system to compute proofs for these clauses, rather than relying solely on external SMT solvers.
Solving Tactics ('zap' and 'fix')
The solver partitions variables into acyclic and cyclic sets. The 'zap' tactic solves acyclic variables to find the strongest solutions. The 'fix' tactic uses predicate abstraction to approximate solutions for cyclic variables, enabling a complete solution process.
Expressive Verification
Flex liberates verification from SMT solvers by using Lean's proof machinery to discharge functional correctness properties. It automatically discharges over 95% of constraints in Flux benchmarks, verifying complex Rust code properties like sorting and memory isolation.

Terminology

Summary

Flex is a foundational Constrained Horn Clause (CHC) solver implemented in Lean that significantly reduces the trusted base to only the kernel, enabling verification of low-level systems code using Lean’s entire proof ecosystem. p. 0

Where the paper says it

Foundational Constraint Solving for Expressive Refinement Typing JAM KABEER ALI KHAN, Independent, Hong Kong SAR PETROS MARKOPOULOS, University of California San Diego, USA NICO LEHMANN, University of Chile, Chile RANJIT JHALA∗ , University of California San Diego, USA SMT-based program verifiers are hamstrung by two problems: expressiveness, because predictable verification restricts to the boundaries of SMT decidability, and trust, because the solver is a large, unverified artifact whose soundness bugs may quietly compromise every tool built on it. We present Flex, a foundational Constrained Horn Clause (CHC) solver implemented in Lean, that reduces the trusted base to the kernel alone, and allows using Lean’s entire proof ecosystem to verify low-level systems code, via three contributions.

Flex achieves this through three primary contributions:

  1. CHC Encoding and Tactic Implementation: Flex encodes CHCs as plain Lean propositions, treating Horn variables as existentially bound predicates. It demonstrates how to implement CHC solvers as tactics (meta-programs) that compute kernel-checkable proofs of these propositions. p. 0

    Where the paper says it

    We present Flex, a foundational Constrained Horn Clause (CHC) solver implemented in Lean, that reduces the trusted base to the kernel alone, and allows using Lean’s entire proof ecosystem to verify low-level systems code, via three contributions. First, Flex encodes CHCs as plain Lean propositions where the Horn variables are existentially bound predicates, and shows how to implement CHC solvers as tactics (meta-programs) that compute kernel-checkable proofs of the CHC propositions.

    This involves using existing SMT-based techniques reimagined as tactics: the 'zap' tactic solves acyclic variables to compute strongest solutions, and predicate abstraction via the 'fix' tactic computes overapproximate solutions for cyclic variables.

  2. Foundational CHC Generation: Flex implements two verified CHC generators in Lean: a Floyd-Hoare style generator for imperative languages and a refinement-type-based generator for functional calculus. These generators can be composed with the solving tactics to yield end-to-end, foundational CHC-based verifiers. p. 0

    Where the paper says it

    First, Flex encodes CHCs as plain Lean propositions where the Horn variables are existentially bound predicates, and shows how to implement CHC solvers as tactics (meta-programs) that compute kernel-checkable proofs of the CHC propositions. Second, we show how to implement two verified CHC generators in Lean: a Floyd-Hoare style generator for an imperative language, and a refinement-type-based generator for a functional calculus, which can be composed with the solving tactics to yield the first end-to-end foundational CHC-based verifiers.

  3. Expressive Verification: Flex liberates verification from the expressiveness and trust limitations of SMT solvers by leveraging Lean’s entire proof machinery to discharge arbitrary functional correctness properties of low-level Rust libraries using the Flux refinement type checker. This approach automatically discharges over 95. p. 0

    Where the paper says it

    Second, we show how to implement two verified CHC generators in Lean: a Floyd-Hoare style generator for an imperative language, and a refinement-type-based generator for a functional calculus, which can be composed with the solving tactics to yield the first end-to-end foundational CHC-based verifiers. Finally, we show how Flex allows us to leapfrog the expressiveness limitations of SMT by unleashing Lean’s entire ecosystem of proof machinery to prove arbitrary functional correctness properties of various low-level Rust libraries using the Flux refinement type checker, and demonstrate the viability of Flex as a trustworthy CHC backend, by showing it automatically discharges 95.

    7% of the CHCs arising in Flux’s benchmark suite, including correctness proofs for in-place sorting algorithms, hash tables with chaining, and properties required for secure memory isolation in the Tock embedded kernel. p. 1
    Where the paper says it

    Flex tears down this wall, by using Lean as a backend to discharge functional correctness specifications, as illustrated by a variety of case studies: correctness of in-place sorting algorithms; correctness of a hash table with chaining for collision resolution; modular arithmetic and bit-vector properties required for secure memory isolation in the Tock embedded kernel [61]; and proving that a ring-buffer-backed dequeue from the embedded kernel [64] never reads from uninitialized memory. Further, we show that Flex is viable as a trustworthy back-end CHC solver that is able to automatically discharge more than 95% of the 880 CHCs that arise in Flux’s existing benchmark suite spanning 20K lines of Rust source.

The core mechanism involves a constraint structure defined using Lean terms of type Prop. Solving entails finding an interpretation (solution) for the existentially quantified Horn variables. p. 3

Where the paper says it

Each constraint is a Constrained Horn Clause (CHC) that comprises the following elements. At the top, a CHC has some number of existentially quantified Horn variables (denoted by 𝜅) which represent unknown refinements or invariants.

The solver emits proof terms to justify rewrites, ensuring soundness by constructing certificates that prove rewrites are legitimate and can be checked by the Lean kernel. p. 8
Where the paper says it

omega, bv_decide, decide, grind or lemmas [70] — to simplify verification, and, we do not need to maintain a deeply embedded AST for each theory, re-using Expr allows for inheriting theories of Lean, keeping the solver simple, but expressive. Second, it provides soundness for free, by letting us implement CHC solvers (§4) that emit proof terms which can then be checked by the kernel, guaranteeing the soundness of verification without trusting any code beyond the kernel itself.

Soundness is formally established through theorems like Theorem B. p. 5
Where the paper says it

This CHC has a single cyclic Horn variable 𝜅 that represents the unknown loop invariant. The classical weakest-precondition based VC generation [18] yields a CHC with constraints that check (1) the invariant holds upon loop entry; (2) the invariant is inductive (re-established by the body) and (3) the specified postcondition holds on exit.

4, which shows that if a fixpoint computation yields a result (c', q), then c' is a VC (Verifier Constraint) and q: c' to c, with q being closed.

The system operates via several key components:

  • Solving Approach: A three-step process partitions horn variables into a cut set and an acyclic set. A 'zap' tactic handles the acyclic variables, while 'fix' uses predicate abstraction to approximate solutions for cyclic ones.

  • Constraint Generation: Constraint generation is described by a bidirectional typechecking procedure involving judgments: synthesis (gamma e so tau so c), checking (gamma e tau so c), and subtyping (gamma s <: t so c). Constraint synthesis produces CHCs where function application mirrors T-App, generating constraints for each subexpression. p. 8

    Where the paper says it

    Foundational Constraint Solving for Expressive Refinement Typing 1:9 Lean Term 𝑡, 𝜑 ∈ T Variables 𝑥, ℎ ∈ V 𝜅-variable 𝜅 ∈ K ⊂ V Sort 𝑏 ::= Prop | Int | Nat | Bool | BitVec 𝑛 | · · · Atoms 𝑝 ::= 𝜑 𝜅-free atom | 𝜅(𝑡) horn application Constraints 𝑐 ::= 𝑝 head | 𝑐 ∧ 𝑐 conjunction | 𝑝 → 𝑐 implication | ∀𝑥 :𝑏. 𝑐 quantification Closed Constraint 𝐶 ::= ∃𝜅.

  • Soundness and Completeness: Soundness is formalized by showing that the generated CHC implies safety (Theorem C.7). Completeness is established by Lemma B. p. 5

    Where the paper says it

    This CHC has a single cyclic Horn variable 𝜅 that represents the unknown loop invariant. The classical weakest-precondition based VC generation [18] yields a CHC with constraints that check (1) the invariant holds upon loop entry; (2) the invariant is inductive (re-established by the body) and (3) the specified postcondition holds on exit.

    2(c), which shows that if theta* is derived via predicate abstraction, it satisfies all Q-assignments theta' where theta' = c.

Flex is implemented in approximately 2700 lines of Lean and extends Flux with an 1800-line Rust backend. p. 1

Where the paper says it

Flex tears down this wall, by using Lean as a backend to discharge functional correctness specifications, as illustrated by a variety of case studies: correctness of in-place sorting algorithms; correctness of a hash table with chaining for collision resolution; modular arithmetic and bit-vector properties required for secure memory isolation in the Tock embedded kernel [61]; and proving that a ring-buffer-backed dequeue from the embedded kernel [64] never reads from uninitialized memory. Further, we show that Flex is viable as a trustworthy back-end CHC solver that is able to automatically discharge more than 95% of the 880 CHCs that arise in Flux’s existing benchmark suite spanning 20K lines of Rust source.

Benchmarking shows that Flex achieves a total wall-clock time of 31 seconds for the full solver pipeline, automatically discharging 95. p. 1
Where the paper says it

Flex tears down this wall, by using Lean as a backend to discharge functional correctness specifications, as illustrated by a variety of case studies: correctness of in-place sorting algorithms; correctness of a hash table with chaining for collision resolution; modular arithmetic and bit-vector properties required for secure memory isolation in the Tock embedded kernel [61]; and proving that a ring-buffer-backed dequeue from the embedded kernel [64] never reads from uninitialized memory. Further, we show that Flex is viable as a trustworthy back-end CHC solver that is able to automatically discharge more than 95% of the 880 CHCs that arise in Flux’s existing benchmark suite spanning 20K lines of Rust source.

7% of all constraints across the benchmark suite, although success drops to 82. p. 0
Where the paper says it

Finally, we show how Flex allows us to leapfrog the expressiveness limitations of SMT by unleashing Lean’s entire ecosystem of proof machinery to prove arbitrary functional correctness properties of various low-level Rust libraries using the Flux refinement type checker, and demonstrate the viability of Flex as a trustworthy CHC backend, by showing it automatically discharges 95. 7% of the CHCs from Flux’s benchmark suite.

3% on constraints involving cyclic horn variables. p. 5
Where the paper says it

This CHC has a single cyclic Horn variable 𝜅 that represents the unknown loop invariant. The classical weakest-precondition based VC generation [18] yields a CHC with constraints that check (1) the invariant holds upon loop entry; (2) the invariant is inductive (re-established by the body) and (3) the specified postcondition holds on exit.

The expected cost is speed, as the Lean backend is roughly two orders of magnitude slower than the LiquidFixpoint SMT-based backend Flux currently uses. p. 0
Where the paper says it

Second, we show how to implement two verified CHC generators in Lean: a Floyd-Hoare style generator for an imperative language, and a refinement-type-based generator for a functional calculus, which can be composed with the solving tactics to yield the first end-to-end foundational CHC-based verifiers. Finally, we show how Flex allows us to leapfrog the expressiveness limitations of SMT by unleashing Lean’s entire ecosystem of proof machinery to prove arbitrary functional correctness properties of various low-level Rust libraries using the Flux refinement type checker, and demonstrate the viability of Flex as a trustworthy CHC backend, by showing it automatically discharges 95.

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Foundational Solving for Expressive Refinement Typing allows AI systems to verify arbitrary functional correctness properties of low-level Rust libraries by using Lean's entire ecosystem of proof machinery instead of being limited by SMT decidability.

  2. The system can generate and discharge constraints from refinement type checkers, such as Flux, which previously restricted specifications to avoid SMT undecidability issues.

  3. It can handle complex program properties like sorting correctness and memory safety in ring buffers by utilizing the solver's ability to compute proofs for more expressive specifications than SMT solvers alone.

  4. The system offers a mechanism to leapfrog expressiveness limitations of SMT by implementing a Constrained Horn Clause (CHC) solver within a foundational prover as a meta-program that computes proofs of CHC propositions.

  5. It provides robust solvers for cyclic variables using predicate abstraction, allowing the system to handle complex invariants that were previously difficult or impossible to verify automatically.

Abstract

Constrained Horn Clauses (CHCs) are a versatile intermediate representation for program verification, but leading CHC solvers rely on SMT-based reasoning over supported background theories. Specifications involving user-defined recursive functions or bespoke operators can require additional semantic encodings and reasoning beyond these theories. We observe that CHCs are existentially quantified propositions in a foundational logic, and so can be proved within an interactive theorem prover, where specifications can use native definitions, and users can complete proofs when automation stalls. However, in a foundational setting, every Horn variable solution must be justified by a kernel-checked proof. We present Flex, a proof-producing CHC solver implemented as a Lean metaprogram, that combines predicate synthesis with proof construction. Flex comprises a suite of tactics: Zap, which synthesizes strongest predicates for acyclic Horn variables and exploits their structure to construct elimination proofs without any proof search; Fix, which uses predicate abstraction over templates built from arbitrary Lean terms, discovered by scraping the CHCs and associated definitions, to infer inductive invariants for cyclic Horn variables; and a certifying pipeline that keeps external SMT-based solvers like Spacer and Eldarica outside the trusted computing base. We use Flex to verify the functional correctness of sorting algorithms, hash tables, ring buffers from the Tock OS kernel, and Rust std library challenges. We show that Zap constructs elimination proofs 28.2x and 44.6x faster than grind and aesop, respectively. With Zap and Fix, Flex automatically proves 98.0% of the refinement-typechecker CHCs in our evaluation.

Sources

Related papers