AuXSpec: Learning to Autoformalize Program Specifications via Executable Postconditions
Training a specification model requires scalable feedback on whether a generated specification captures the intended behavior. Prior approaches obtain this feedback through explicit proofs or separately implemented code with formal correspondence proofs, both expensive since each specification needs new proofs. We introduce AuXSpec, a Lean framework that pairs each declarative postcondition with an executable counterpart, related by an equivalence theorem. Test cases then evaluate the declarative postcondition by execution, and agreement with the test cases is the reward for reinforcement learning.
def plusOne_spec (input : Input) (result : Output) : Prop :=Represents (result.map Int.ofNat)((decimalValue input).toNat + 1) ∧∀ l : List Int,Represents l ((decimalValue input).toNat + 1) →l = result.map Int.ofNatPropStates what a correct output is. It can be proved but not run.
plusOne_spec [9] [1, 0]holdsplusOne_spec [9] [1, 1]does not holdtheorem plusOne_check_iff_spec(input : Input) (result : Output)(h : isValidInput input) :plusOne_check input result ↔plusOne_spec input resultdef plusOne_check (input : Input) (result : Output) : Bool :=let m := (decimalValue input).toNat + 1decide (Represents (result.map Int.ofNat) m) &&(List.range 102).all fun k =>decide (Represents (digitsOfLen m k) m →digitsOfLen m k = result.map Int.ofNat)BoolDecidable. It decides the same property, so the Lean compiler can run it on test cases.
plusOne_check [9] [1, 0]trueplusOne_check [9] [1, 1]falseFigure 1. Plus One from AuXSpec-Test. The theorem plusOne_check_iff_spec says that on valid inputs the executable postcondition returns true exactly when the declarative postcondition holds. Each test verdict on the right therefore decides the matching statement on the left. The theorem is stated with the specification and proved in a separate step, for all 3,037 dataset problems and for 99.2% of accepted outputs of the RL models. Open the file
Results
Executable postconditions turn test cases into a reward for specification generation. With this reward, RL improves SpecGen pass@1 by 48.5 points (9B) and 47.0 points (27B), and both RL models outperform all baselines on SpecGen, in domain and on Verina.
AuXSpec-Test
SpecGen
CodeGen
Verina (out of domain)
SpecGen
CodeGen
| Model | AuXSpec-Test | Verina | ||||||
|---|---|---|---|---|---|---|---|---|
| SpecGen | CodeGen | SpecGen | CodeGen | |||||
| pass@1 | pass@4 | pass@1 | pass@4 | pass@1 | pass@4 | pass@1 | pass@4 | |
| Frontier models | ||||||||
| Claude-Opus-5 | 57.7 | 81.3 | 93.0 | 98.3 | 86.2 | 95.2 | 56.6 | 79.4 |
| Claude-Sonnet-5 | 13.8 | 39.3 | 54.8 | 73.0 | 64.8 | 90.5 | 17.9 | 41.8 |
| GPT-5.6-Sol | 29.8 | 59.7 | 80.0 | 96.3 | 85.1 | 97.9 | 20.8 | 40.7 |
| GPT-5.6-Luna | 9.5 | 28.7 | 39.9 | 71.3 | 67.3 | 94.7 | 24.5 | 58.2 |
| Kimi-K3 | 43.8 | 83.7 | 67.2 | 94.3 | 77.6 | 96.3 | 34.9 | 72.5 |
| DeepSeek-V4-Pro | 21.2 | 54.3 | 48.6 | 72.3 | 53.8 | 82.5 | 37.6 | 70.4 |
| DeepSeek-V4-Flash | 38.4 | 76.7 | 45.0 | 69.7 | 60.2 | 92.6 | 5.8 | 18.5 |
| Instruct models | ||||||||
| Qwen3.5-9B | 0.2 | 0.7 | 8.2 | 18.0 | 7.0 | 18.5 | 23.4 | 49.2 |
| Qwen3.8-27B | 4.5 | 14.3 | 8.9 | 22.0 | 28.8 | 55.0 | 3.3 | 13.2 |
| AuXSpec | ||||||||
| AuXSpec-9B-SFT | 10.1 | 24.3 | 13.1 | 28.3 | 37.3 | 69.8 | 38.0 | 70.4 |
| AuXSpec-9B-RL | 58.6 | 82.7 | 77.1 | 96.0 | 87.0 | 96.8 | 92.6 | 98.4 |
| AuXSpec-27B-SFT | 18.7 | 40.7 | 27.6 | 52.7 | 57.3 | 82.5 | 57.8 | 86.8 |
| AuXSpec-27B-RL | 65.7 | 84.3 | 94.8 | 99.7 | 91.9 | 96.8 | 91.8 | 93.7 |
Method
The executable postcondition makes every test case checkable by execution, so one automatic check serves the whole method. The same acceptance criteria filter the synthesized data, select samples in expert iteration, score rollouts in reinforcement learning, and decide the evaluation.
File format
From a problem description, input constraints, and test cases, a file holds a specification, an implementation, two theorem statements, and executable tests. The specification consists of a precondition, a declarative postcondition, and an executable postcondition.
A generated output is accepted only if the assembled file compiles, the test cases pass, and LLM judges approve.
The example is Remove Nth Node From End of List from AuXSpec-Test, a file of 147 lines.
Lean file formatThe precondition defines the valid inputs, following the input constraints of the problem. It returns a Bool, so it is evaluated on test inputs in Lean. Each constraint is one conjunct, joined with &&: here the list length, the node values, and the range of n.
abbrev Input := (List Int) × (Nat)abbrev Output := List Nat/-! ### Validity predicate (V) -/ /-- Valid input: 1 to 30 nodes, every value between 0 and 100 inclusive,and `1 ≤ n ≤ length`. -/def isValidInput (input : Input) : Bool :=1 ≤ input.1.length && input.1.length ≤ 30 &&input.1.all (fun v => 0 ≤ v && v ≤ 100) &&1 ≤ input.2 && input.2 ≤ input.1.lengthThe declarative postcondition, the ideal specification of the file, characterizes the correct outputs independently of how they are computed. It is a Prop and can quantify over unbounded domains. Here it states that some index k exists such that the result is the list without the node at k.
/-- `k` is the index of the node to remove:the nth node from the end sits at position `k`. -/def IsRemovalIndex (head : List Int) (n k : Nat) : Prop :=k + n = head.length/-! ### Ideal specification (P_spec) -/ /-- `result` is `head` with the nth node from the end removed: for the index `k`with `k + n = head.length`, `result` has one fewer element and each position `j`copies `head[j]` below `k` and `head[j + 1]` at or past `k`, coerced to `Nat`. -/def removeNthFromEnd_spec (input : Input) (result : Output) : Prop :=∃ k : Nat, IsRemovalIndex input.1 input.2 k ∧result.length + 1 = input.1.length ∧∀ j : Nat, j < result.length →result[j]? = (if j < k then input.1[j]? else input.1[j + 1]?).map Int.toNatThe executable postcondition, the decidable specification of the file, expresses the same condition in a form that is evaluated directly on test cases in Lean. Here each quantifier becomes a search over a finite range: any for ∃ and all for ∀.
/-! ### Decidable specification (P_check) -/ /-- Executable checker for `removeNthFromEnd_spec`,scanning the removal index over `0 … head.length`. -/def removeNthFromEnd_check (input : Input) (result : Output) : Bool :=(List.range (input.1.length + 1)).any fun k =>k + input.2 == input.1.length &&result.length + 1 == input.1.length &&(List.range result.length).all fun j =>result[j]? == (if j < k then input.1[j]? else input.1[j + 1]?).map Int.toNatThe equivalence theorem asserts that the two postconditions agree on valid inputs. With its proof, every outcome of a test case on the executable postcondition also holds for the declarative postcondition. The proof is written in a separate step, after the definitions are accepted.
/-- On valid input the checker accepts exactly the specified outputs. -/theorem removeNthFromEnd_check_iff_spec (input : Input) (result : Output)(h : isValidInput input) :removeNthFromEnd_check input result ↔ removeNthFromEnd_spec input result := bysimp only [removeNthFromEnd_check, removeNthFromEnd_spec, IsRemovalIndex,List.any_eq_true, List.all_eq_true, List.mem_range, Bool.and_eq_true,beq_iff_eq, decide_eq_true_eq]constructor· rintro ⟨k, _hkw, ⟨⟨hkn, hlen⟩, hall⟩⟩exact ⟨k, hkn, hlen, fun j hj => hall j hj⟩· rintro ⟨k, hkn, hlen, hall⟩exact ⟨k, by omega, ⟨⟨hkn, hlen⟩, fun j hj => hall j hj⟩⟩The implementation is an algorithm that computes an output from a given input. The test cases are executed against it in Lean, and LLM judges check that it (1) terminates on all valid inputs and (2) is fast enough for the stated constraints. Here it joins the nodes before the removed index with the nodes after it.
/-! ### Implementation helpers -/ /-- Rebuilds `head` without the node at index `head.length - n`,coercing values to `Nat`. -/def removeAtFromEnd (head : List Int) (n : Nat) : List Nat :=let k := head.length - n(head.take k ++ head.drop (k + 1)).map Int.toNat /-! ### Main algorithm (impl) -/ /-- Removes the nth node from the end in O(sz)by concatenating the prefix before index `head.length - n`with the suffix after it. -/def removeNthFromEndImpl (input : Input) : Output :=removeAtFromEnd input.1 input.2The correctness theorem asserts that the implementation satisfies the declarative postcondition on every valid input. It refers to the declarative postcondition so that the specification cannot restate the implementation, which would reduce the proof to unfolding definitions.
/-- On valid input the algorithm meets the specification. -/theorem removeNthFromEndImpl_correct (input : Input) (h : isValidInput input) :removeNthFromEnd_spec input (removeNthFromEndImpl input) := bysimp only [isValidInput, Bool.and_eq_true, decide_eq_true_eq, List.all_eq_true] at hrefine ⟨input.1.length - input.2, ?_, ?_, ?_⟩· unfold IsRemovalIndexomega· simp [removeNthFromEndImpl, removeAtFromEnd, List.length_take, List.length_drop]omega· intro j hjsimp only [removeNthFromEndImpl, removeAtFromEnd, List.getElem?_map,List.getElem?_append, List.length_take, List.getElem?_take, List.getElem?_drop]have hk : input.1.length - input.2 ≤ input.1.length := Nat.sub_le _ _rw [Nat.min_eq_left hk]split <;> simp_all <;> congr 2 <;> omegaEach test case is a #guard command, which fails at compilation when its expression is false. Layers L1 and L2 test the precondition and the executable postcondition, each with a second layer of negative cases. Layer L3 tests the implementation, and layer L4 checks its output with the executable postcondition.
/-! ### L1 — Validity guard (V accepts the provided examples) -/#guard isValidInput ([1, 2, 3, 4, 5], 2)#guard isValidInput ([1], 1)#guard isValidInput ([1, 2], 1) /-! ### L1b — Negative validity (V rejects invalid input) -/#guard !(isValidInput ([(-1)], 1))#guard !(isValidInput ([101], 1))#guard !(isValidInput ([1], 2)) /-! ### L2 — Specification guard (P_check accepts the correct output) -/#guard removeNthFromEnd_check ([1, 2, 3, 4, 5], 2) [1, 2, 3, 5]#guard removeNthFromEnd_check ([1], 1) []#guard removeNthFromEnd_check ([1, 2], 1) [1] /-! ### L2b — Negative specification (P_check rejects a wrong output) -/#guard !(removeNthFromEnd_check ([1, 2, 3, 4, 5], 2) [1, 2, 3, 4])#guard !(removeNthFromEnd_check ([1], 1) [1])#guard !(removeNthFromEnd_check ([1, 2], 1) [1, 3]) /-! ### L3 — Algorithm output (impl matches the expected output) -/#guard removeNthFromEndImpl ([1, 2, 3, 4, 5], 2) == [1, 2, 3, 5]#guard removeNthFromEndImpl ([1], 1) == []#guard removeNthFromEndImpl ([1, 2], 1) == [1] /-! ### L4 — Integration (P_check certifies the output of impl) -/#guard removeNthFromEnd_check ([1, 2, 3, 4, 5], 2)(removeNthFromEndImpl ([1, 2, 3, 4, 5], 2))#guard removeNthFromEnd_check ([1], 1) (removeNthFromEndImpl ([1], 1))#guard removeNthFromEnd_check ([1, 2], 1) (removeNthFromEndImpl ([1, 2], 1))Data synthesis
The synthesis pipeline generates the components in separate, ordered stages, which prevents a component from overfitting the test cases or weakening a specification that is already accepted. Each stage plans and generates a component, validates it, and repairs it if validation fails.
A rejected component is repaired from the compiler errors, the failed test cases, and the judge feedback for up to 18 rounds, and only the faulty code block is modified.
Synthesis outcomes
- 3,037 of 3,109
- problems synthesized (97.7%)
- 34.8%
- of problems pass all stages at the first attempt
- 99.0%
- of equivalence theorems are provable as synthesized
Training and evaluation data
- Supervised fine-tuningSynthesis pipeline and expert iteration
- 19,492 samples
- Reinforcement learningSpecGen and CodeGen, over 8,579 problems
- 13,637 tasks
- AuXSpec-TestHeld out and reviewed by experts
- 300 problems
Training
Supervised fine-tuning trains on 19,492 samples, collected over 3 rounds of expert iteration. Reinforcement learning then runs for 1 epoch on 13,637 SpecGen and CodeGen tasks over 8,579 problems, which are disjoint from the SFT data and AuXSpec-Test.
The reward follows the acceptance criteria stage by stage, so a rollout that fails still receives a graded signal. Repair tasks are built during training from failed rollouts of the current policy.
Token efficiency
The plot shows SpecGen pass@1 and output tokens per response jointly, so a token-efficient model lies in the upper left.
AuXSpec-27B-RL attains the highest pass@1 (65.7%) with the fewest output tokens, both per response (1.8K) and per solved sample (2.7K). Against the best and the most economical baseline, it requires several times fewer tokens and scores higher.
| Baseline | Fewer tokens per response | Fewer tokens per solved sample | Higher pass@1 |
|---|---|---|---|
| Claude-Opus-5best baseline | 5.5× | 6.2× | +8.0 |
| GPT-5.6-Solmost economical baseline | 2.2× | 4.9× | +35.9 |
| Model | AuXSpec-Test | Verina | ||||||
|---|---|---|---|---|---|---|---|---|
| SpecGen | CodeGen | SpecGen | CodeGen | |||||
| Response | Solved | Response | Solved | Response | Solved | Response | Solved | |
| Frontier models | ||||||||
| Claude-Opus-5 | 9.7 | 16.8 | 4.8 | 5.2 | 5.2 | 6.0 | 3.9 | 6.9 |
| Claude-Sonnet-5 | 10.2 | 74.4 | 7.3 | 13.4 | 4.4 | 6.9 | 9.6 | 53.7 |
| GPT-5.6-Sol | 3.9 | 13.2 | 2.8 | 3.5 | 2.6 | 3.0 | 3.1 | 14.7 |
| GPT-5.6-Luna | 3.4 | 36.0 | 2.8 | 7.0 | 2.7 | 4.0 | 2.5 | 10.1 |
| Kimi-K3 | 10.7 | 24.4 | 6.7 | 10.0 | 5.2 | 6.7 | 9.0 | 25.7 |
| DeepSeek-V4-Pro | 27.0 | 126.9 | 24.1 | 49.5 | 17.1 | 31.8 | 20.8 | 55.2 |
| DeepSeek-V4-Flash | 49.6 | 129.2 | 49.0 | 109.0 | 37.8 | 62.9 | 43.2 | 741.4 |
| Instruct models | ||||||||
| Qwen3.5-9B | 3.2 | 1,912.1 | 6.8 | 82.9 | 2.6 | 37.6 | 2.3 | 9.7 |
| Qwen3.8-27B | 13.4 | 296.8 | 15.9 | 178.6 | 8.1 | 28.0 | 15.5 | 469.8 |
| AuXSpec | ||||||||
| AuXSpec-9B-SFT | 3.6 | 36.0 | 2.2 | 16.6 | 4.0 | 10.6 | 1.5 | 4.0 |
| AuXSpec-9B-RL | 6.4 | 11.0 | 4.1 | 5.3 | 3.9 | 4.5 | 1.9 | 2.0 |
| AuXSpec-27B-SFT | 3.6 | 19.3 | 1.9 | 7.0 | 3.8 | 6.7 | 1.4 | 2.5 |
| AuXSpec-27B-RL | 1.8 | 2.7 | 1.7 | 1.8 | 1.6 | 1.7 | 1.1 | 1.2 |
Dataset
AuXSpec holds 3,037 LeetCode problems in the Lean format, each with a specification, an implementation, test cases, and a proved equivalence theorem.
AuXSpec-Test is a held-out set of 300 of these problems. Every component is reviewed by experts against the problem description, and the correctness theorem is proved for all 300.
Citation
@misc{auxspec2026,
title = {AuXSpec: Learning to Autoformalize Program Specifications via Executable Postconditions},
author = {Haocheng Wang and Weixuan Yuan and Florian H{\"u}bler and Yinya Huang and Zhijiang Guo and Sorrachai Yingchareonthawornchai and Rasmus Kyng},
year = {2026},
eprint = {2611.21421},
archivePrefix = {arXiv},
primaryClass = {cs.SE},
url = {https://arxiv.org/abs/2611.21421}
}