AuXSpec turns Lean spec generation into an executable score: its 27B model lifts pass@4 from 14.3% to 84.3% on a 300-problem test set
Synopsis
AuXSpec splits a Lean program specification into a declarative postcondition and an executable postcondition, tied by a postcondition equivalence theorem that guarantees the two agree on valid inputs, so test cases can be executed directly to score a generated specification instead of proving each case separately. Using that execution feedback as a reinforcement-learning reward, Qwen3.5-9B and Qwen3.8-27B raise specification-generation pass@4 on the 300-problem AuXSpec-Test from 0.7% to 82.7% and from 14.3% to 84.3%, and the 27B model surpasses every frontier model compared on that test set.
Interpretation
Autoformalizing program specifications now has an executable way to score them: a generated Lean specification can be checked against test cases without first proving each case, so it can be tested for whether it captures the source problem. Previously, checking a generated specification in Lean turned each test case into a theorem to be proved; with unbounded quantifiers such proofs are nontrivial, and an unproved case was left unresolved or handed to an LLM judge, so test cases could not supply the cheap reward that code generation enjoys. On the 300-problem AuXSpec-Test, training with the execution-based reward raises specification-generation pass@4 from 0.7% to 82.7% for Qwen3.5-9B and from 14.3% to 84.3% for Qwen3.8-27B.
The construction pairs each declarative postcondition with an executable postcondition, so test cases evaluate to true or false directly inside Lean. The executable form is obtained first through type class resolution, which lets Lean find a decidability instance automatically; when that fails, a separate executable postcondition is defined and a postcondition equivalence theorem is added for the pair. Of the 3,037 synthesized problems, 35.5% get their executable postcondition directly from a decidability instance and the rest use a separate definition; after synthesis the equivalence theorem is attempted for all 3,037 problems and 99.0% are provable without modifying their definitions.
Training data comes from 3,037 LeetCode problems, expanded through expert iteration to 19.5K supervised fine-tuning samples. Specifications, executable postconditions and implementations are generated in three stages, each accepted against compilation, test layers and LLM judges, and repaired on failure for up to 18 rounds. Of 3,109 seed problems, 3,037 are synthesized, or 97.7%; only 34.8% pass all stages at the first attempt, and repair recovers most of the others within two rounds.
Perspective
The demonstrated scope is specification generation for competitive-programming problems in Lean 4: 3,037 LeetCode problems, the 300-problem expert-reviewed AuXSpec-Test, and the 189-problem out-of-domain Verina evaluation; the intended readers are researchers and engineers in formal methods and code generation.
The equivalence theorem shows only that the two postconditions agree, and both may encode the same misunderstanding, which expert review found in 9 of the 300 problems; in the expert review of accepted outputs, all 10 errors were input constraints missing from the validity predicate, and that review covers only 100 outputs.
