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.

Declarative postcondition (Ideal specification)
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.ofNat

PropStates what a correct output is. It can be proved but not run.

By the theorem
plusOne_spec [9] [1, 0]holds
plusOne_spec [9] [1, 1]does not hold
Equivalence theoremproved
theorem plusOne_check_iff_spec(input : Input) (result : Output)(h : isValidInput input) :plusOne_check input result ↔plusOne_spec input result
Executable postcondition (Decidable specification)
def 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.

Executed by the compiler
plusOne_check [9] [1, 0]true
plusOne_check [9] [1, 1]false

Figure 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

Verina (out of domain)

Figure 2. Pass@1 (%) on AuXSpec-Test and on Verina with the test cases in the prompt. The four bars on the right are baselines, one model per family, and Table 1 lists all seven. Source: paper, Tables 4 and 5.
An example run

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 format

The 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.

Remove Nth Node From End of Listlines 33 to 48Open in the file
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.length

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.

Data synthesis pipelineA problem description and test cases are frozen as inputs. A problem-level plan guides three generation stages: the declarative specification, the executable postcondition, and the implementation. Each stage plans, generates, validates, and repairs its component, and an accepted component is frozen. Assembly combines the accepted components into a Lean file.InputsProblem descriptionwith input constraintsTest casespositive and negativeProblem-levelplanGenerationDeclarativespecificationExecutablepostconditionImplementationEach stage: Plan → Generate → Validate ⇄ Repairvalidated by the Lean compiler, the test cases, and LLM judgesAssemblyadds two theoremsLean file
Figure 3. The synthesis pipeline. A problem-level plan guides three generation stages, and each stage plans, generates, validates, and repairs its component before the next stage starts. A lock marks what stays frozen during synthesis: the inputs and every accepted component. Assembly combines the accepted components with the two theorem statements into a Lean file. Source: paper, Figure 1.

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.

Reinforcement learning with a progressive reward and self-repair
ScoringRolloutsRewards of all rolloutsUpdatePolicy updateRepair tasks, 40% per batchSpecGen,CodeGentasks∀SFT modelRollouts∀AuXSpec-RLFileExecutionLLM judgesFormat0Compilation0.1Testexecution0.2Test casealignment0.1Non-tautology0.1Overallquality0.4All stagespass1The executable postcondition runs in LeanRepair bufferFailed rollouts, with compilermessages or judge feedback10.2110.4
Figure 4. Reinforcement learning with the progressive reward. A rollout receives the value of the first stage it fails, in the order of the acceptance criteria, and 1 when it passes all six. Every reward enters the policy update. Failed rollouts return as repair tasks, 40% per batch, and an amber ring marks the feedback they carry. A darker green is a higher reward. Training starts from the SFT model and ends with AuXSpec-RL.

Token efficiency

02040602K5K10K20K50KOutput tokens per response, log scaleSpecGen pass@1 (%)DeepSeek-V4-FlashDeepSeek-V4-ProQwen3.8-27B (base)Kimi-K3Claude-Sonnet-5Claude-Opus-5GPT-5.6-SolGPT-5.6-LunaQwen3.5-9B (base)AuXSpec-9B-RL58.6% with 6.4K tokensAuXSpec-27B-RL65.7% with 1.8K tokens
Figure 5. SpecGen pass@1 (%) on AuXSpec-Test against the average output tokens per response. Up and to the left is better. Source: paper, Tables 4 and 15.

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.

AuXSpec-27B-RL against two baselines on SpecGen
BaselineFewer tokens per responseFewer tokens per solved sampleHigher pass@1
Claude-Opus-5best baseline5.5×6.2×+8.0
GPT-5.6-Solmost economical baseline2.2×4.9×+35.9

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}
}