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
#guardcommands 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
#guardcommands checking precondition, executable postcondition, and implementation
Tasks
Four tasks are defined for training:
| Task | Input | Output |
|---|---|---|
| SpecGen | Description, Constraints, Cases | Specification |
| SpecGen-Repair | Description, Constraints, Cases, Broken, Diagnostics | Repaired specification |
| CodeGen | Description, Cases | Implementation |
| CodeGen-Repair | Description, Cases, Broken, Diagnostics | Repaired implementation |
Synthesis Pipeline
- Input collection: 3,109 LeetCode problems with typed function signatures, reference solutions, and test cases
- Three-stage generation: Problem-level plan → declarative specification → executable postcondition → implementation
- Validation: Each component validated against acceptance criteria with up to 18 repair rounds
- 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:
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:
Empirical Validation / Results
Main Results on AUXSPEC-Test (In-Domain)
| Model | SpecGen pass@1 | SpecGen pass@4 | CodeGen pass@1 | CodeGen pass@4 |
|---|---|---|---|---|
| Qwen3.5-9B (backbone) | 0.2 | 0.7 | 8.2 | 18.0 |
| Qwen3.8-27B (backbone) | 4.5 | 14.3 | 8.9 | 22.0 |
| AUXSPEC-9B-RL | 58.6 | 82.7 | 77.1 | 96.0 |
| AUXSPEC-27B-RL | 65.7 | 84.3 | 94.8 | 99.7 |
| Claude-Opus-5 (best frontier) | 57.7 | 81.3 | 93.0 | 98.3 |
The 27B model surpasses all frontier models on both SpecGen and CodeGen pass@1 and pass@4.
Out-of-Domain Evaluation (Verina)
| Model | SpecGen pass@1 | SpecGen pass@4 | CodeGen pass@1 | CodeGen pass@4 |
|---|---|---|---|---|
| VeriSpecGen-30B-A3B (prior SOTA) | 47.6† | 63.9† | 58.7† | 84.0† |
| AUXSPEC-9B-RL | 73.7 | 90.5 | 89.8 | 97.4 |
| AUXSPEC-27B-RL | 84.5 | 90.5 | 89.7 | 93.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
- Late Entry in Looped Language Models
Late entry into deep context caches outperforms early exit in looped language models, yielding up to 8.4x exact and 12.5x lossy decoding speedups.
- Language Models Can Rewrite Their Own Weights
A 27B language model improved its own accuracy by 6.6 points and repaired a damaged copy of itself using only forward passes, with no gradients or training.
- Rethinking Fixed-Horizon Latent Reasoning
Adaptive latent inference that stops reasoning when progress stalls improves accuracy by up to 7.2 points while cutting computation by 29%, as completing fixed latent horizons can degrade performance.