AUXSPEC: Learning to Autoformalize Program Specifications via Executable Postconditions

Summary (Overview)

  • Core contribution: AUXSPEC introduces a Lean 4 framework that pairs declarative postconditions with executable counterparts, enabling test-case-based evaluation of formal specifications without proving each test case individually. This provides scalable feedback for training specification-generation models.

  • Key innovation: A postcondition equivalence theorem proves that the executable postcondition agrees with the declarative one on all valid inputs, allowing direct execution of test cases via #guard commands as a reinforcement learning reward signal.

  • Dataset: The authors synthesize 3,037 LeetCode problems with specifications, implementations, and frozen test cases, including AUXSPEC-Test—a held-out benchmark of 300 expert-reviewed problems with correctness proofs.

  • Results: Training Qwen3.5-9B and Qwen3.8-27B with execution-based RL improves SpecGen pass@4 on AUXSPEC-Test from 0.7% → 82.7% and 14.3% → 84.3%, respectively. Both models surpass the prior state-of-the-art open-source specification model (VeriSpecGen-30B-A3B) on the out-of-domain Verina benchmark.

  • Release: Model weights for 9B and 27B models, along with the 3,037 problems with test cases, are publicly released.

Introduction and Theoretical Foundation

The paper addresses a fundamental bottleneck in formal verification: writing formal specifications in interactive theorem provers like Lean requires substantial expertise and effort. While large language models (LLMs) can generate code from natural-language descriptions, evaluating whether generated formal specifications faithfully capture intended behavior remains challenging.

Key challenges identified:

  • Test cases provide scalable rewards for code generation but cannot directly evaluate specifications in Lean
  • Prior approaches require either explicit proofs for each test case (expensive) or LLM judges (unreliable)
  • Manual curation of specifications is limited in scale (e.g., Clever and Verina contain only 161 and 189 problems)

Theoretical basis: The work draws on the long history of executable specifications in formal methods (Kemmerer, 1985; Fuchs, 1992), where executable specifications can be validated by execution, while declarative specifications are more expressive and independent of any algorithm (Hayes & Jones, 1989). The approach also builds on Boolean reflection (Gonthier & Mahboubi, 2010), which pairs a proposition with a Boolean function and a proof that the two agree.

Key insight: Rather than proving each test case separately (symbolic specification testing), AUXSPEC proves a single equivalence theorem between the declarative and executable postconditions, after which any number of test cases can be evaluated by direct execution.

Methodology

Specification Format

Each problem is represented as a Lean file containing:

  • Precondition: Defines valid inputs
  • Declarative postcondition: Characterizes correct outputs independently of computation method
  • Executable postcondition: Expresses the same condition in directly evaluable form
  • Implementation: An algorithm computing output from input
  • Two theorems: Postcondition equivalence and correctness theorems
  • Test cases: As #guard commands checking precondition, executable postcondition, and implementation

Tasks

Four tasks are defined for training:

TaskInputOutput
SpecGenDescription, Constraints, CasesSpecification
SpecGen-RepairDescription, Constraints, Cases, Broken, DiagnosticsRepaired specification
CodeGenDescription, CasesImplementation
CodeGen-RepairDescription, Cases, Broken, DiagnosticsRepaired implementation

Synthesis Pipeline

  1. Input collection: 3,109 LeetCode problems with typed function signatures, reference solutions, and test cases
  2. Three-stage generation: Problem-level plan → declarative specification → executable postcondition → implementation
  3. Validation: Each component validated against acceptance criteria with up to 18 repair rounds
  4. Post-synthesis proofs: Postcondition equivalence theorems proved for all 3,037 problems (99.0% provable without modification)

Training

Supervised Fine-Tuning: 19.5K samples from LeetCode and Codeforces (via expert iteration over 3 rounds)

Reinforcement Learning: Applied to 13,637 tasks over 8,579 problems with a progressive reward:

r(y)={1if y passes all stages,vkif k is the first stage that y fails.(1)r(y) = \begin{cases} 1 & \text{if } y \text{ passes all stages,} \\ v_k & \text{if } k \text{ is the first stage that } y \text{ fails.} \end{cases} \tag{1}

The 6-stage progressive reward follows: format (0), compilation (0.1), test execution (0.2), test case alignment (0.1), non-tautology (0.1), overall quality (0.4).

Policy Optimization: Extends DAPO with batch-level advantage normalization and repetition masking:

J(θ)=E[∑i,tmi,tℓi,t(θ)∑i,tmi,t](2)\mathcal{J}(\theta) = \mathbb{E}\left[\frac{\sum_{i,t} m_{i,t} \ell_{i,t}(\theta)}{\sum_{i,t} m_{i,t}}\right] \tag{2}

Empirical Validation / Results

Main Results on AUXSPEC-Test (In-Domain)

ModelSpecGen pass@1SpecGen pass@4CodeGen pass@1CodeGen pass@4
Qwen3.5-9B (backbone)0.20.78.218.0
Qwen3.8-27B (backbone)4.514.38.922.0
AUXSPEC-9B-RL58.682.777.196.0
AUXSPEC-27B-RL65.784.394.899.7
Claude-Opus-5 (best frontier)57.781.393.098.3

The 27B model surpasses all frontier models on both SpecGen and CodeGen pass@1 and pass@4.

Out-of-Domain Evaluation (Verina)

ModelSpecGen pass@1SpecGen pass@4CodeGen pass@1CodeGen pass@4
VeriSpecGen-30B-A3B (prior SOTA)47.6†63.9†58.7†84.0†
AUXSPEC-9B-RL73.790.589.897.4
AUXSPEC-27B-RL84.590.589.793.7

†Reported at pass@10

Key Findings

  • RL > SFT: RL improves SpecGen pass@1 over SFT alone by 48.5 points (9B) and 47.0 points (27B) on AUXSPEC-Test
  • Sample efficiency: AUXSPEC-27B-RL achieves SpecGen pass@8 (88.2%) that the SFT model requires pass@256 (85.7%) to approach—over 32× more samples needed
  • Token efficiency: RL model uses only 20.3% of the output tokens per solved SpecGen sample compared to the most economical frontier model
  • Proof validation: Postcondition equivalence theorems hold for 99.2% of accepted RL outputs; expert review confirms 90 of 100 sampled outputs
  • Generalization: Gains on Verina (where test cases are absent from prompts) suggest the policy learns faithfulness to descriptions beyond the reward's test cases

Theoretical and Practical Implications

Theoretical implications:

  • Demonstrates that executable postconditions paired with equivalence proofs offer a scalable middle ground between purely declarative specifications (expressive but hard to evaluate) and purely executable ones (limited expressiveness but testable)
  • The progressive reward design shows how fine-grained credit assignment enables RL for specification generation where binary rewards fail due to low variance
  • Provides evidence that execution-based feedback can drive learning of semantic faithfulness, not just test-case overfitting

Practical implications:

  • Reduces the cost of specification validation from per-test-case proofs to a single equivalence proof plus direct execution
  • Enables training of open-weight models (9B and 27B) that outperform much larger frontier models on specification generation
  • The released dataset (3,037 problems) and benchmark (300 expert-reviewed problems with correctness proofs) provide resources for future research
  • The repair capabilities enable iterative refinement at test time, improving ICPC-Eval performance from pass@16 (61.3%) to refine@16 (82.7%)

Conclusion

AUXSPEC introduces an executable specification format that enables scalable, execution-based feedback for training specification-generation models in Lean. The framework pairs declarative postconditions with executable counterparts, proved equivalent via a postcondition equivalence theorem, allowing test cases to serve as cheap reward signals.

The authors synthesize and release 3,037 LeetCode problems with proved postcondition equivalence theorems, including AUXSPEC-Test (300 expert-reviewed problems with correctness proofs). Training 9B and 27B models with execution-based RL yields substantial improvements: the 27B model surpasses all frontier models on in-domain evaluation, and both models outperform the prior state-of-the-art open-source specification model on the out-of-domain Verina benchmark.

Future directions (implied by limitations discussed in Appendix J):

  • The approach relies on test cases and LLM judges for semantic validation; expert review still finds errors in validity predicates
  • Correctness proofs for implementations remain expensive (median ~160 lines on AUXSPEC-Test) and are not yet automated
  • The 1.0% of synthesized problems where equivalence proofs expose errors beyond tests/judges suggests the need for stronger validation methods
  • Scaling beyond competitive programming problems to more diverse specification domains remains open

Related papers