# AuXSpec: Learning to Autoformalize Program Specifications via Executable Postconditions

> AUXSPEC pairs declarative postconditions with executable counterparts in Lean, enabling test-case-based rewards that boost specification generation pass@4 from 0.7% to 82.7% and surpass frontier models.

- **Source:** [arXiv](https://arxiv.org/abs/2611.21421)
- **Published:** 2026-11-21
- **Permalink:** https://picx.dev/p/Riva6S
- **Whiteboard:** https://picx.dev/p/Riva6S/image

## Summary

# 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:

| 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

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) = \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:

$$
\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)

| 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

---

_Markdown view of https://picx.dev/p/Riva6S, served by PicX — AI-generated visual whiteboard summaries of research papers._
