Improving LLM Code Reasoning via Semantic Equivalence Self-Play with Formal Verification

Antonio Valerio Miceli Barone; Poon Tsz Nok

cs.CLApr 18, 2026

Improving LLM Code Reasoning via Semantic Equivalence Self-Play with Formal Verification

Authors: Antonio Valerio Miceli Barone, Poon Tsz Nok

Organizations: School of Informatics, University of Edinburgh

Abstract

We introduce a self-play framework for semantic equivalence in Haskell, utilizing formal verification to guide adversarial training between a generator and an evaluator. The framework leverages Liquid Haskell proofs for validating equivalence and execution-based counterexamples for inequivalence, organized via a difficulty-aware curriculum. To facilitate this, we release \textbf{OpInstruct-HSx}, a synthetic dataset of $\approx$ 28k validated Haskell programs. Empirical experiments show that our evaluator transfers effectively to downstream tasks, achieving up to 13.3pp accuracy gain on EquiBench and consistent gains on PySecDB. Ablation studies on the SEQ-SINQ regimes indicate that while inequivalence supervision provides data volume, equivalence proofs are uniquely responsible for the model's reasoning capabilities. The entire training pipeline and dataset are publicly released on GitHub and Hugging Face respectively.

Explore similar work

AutoPyVerifier: Learning Compact Executable Verifiers for Large Language Model Outputs
Apr 24, 2026Pouya Pezeshkpour, Estevam HruschkaVerifier Large Language Model Output
An Execution-Verified Multi-Language Benchmark for Code Semantic Reasoning
May 10, 2026Yikun Li, Jinfeng Jiang, Ting Zhang +7Code Evaluation Multilingual Benchmark
Teaching Code LLMs to Reason with Intermediate Formal Specifications
Jul 5, 2026Minh Le-Anh, Cuong Chi Le, Tien N. Nguyen

Apr 24, 2026 · cs.CLJ/K move · Enter open · S save

AutoPyVerifier: Learning Compact Executable Verifiers for Large Language Model Outputs

Pouya Pezeshkpour, Estevam Hruschka

Megagon Labs

Verification is becoming central to both reinforcement-learning-based training and inference-time control of large language models (LLMs). Yet current verifiers face a fundamental trade-off: LLM-based verifiers are expressive but hard to control and prone to error, while deterministic executable verifiers are reliable and interpretable but often limited in capability. We study the following question: given a development set of LLM outputs and labels for a target objective, such as correctness, can we automatically induce a minimal set of Python verifiers whose joint satisfaction closely matches that objective? We propose AutoPyVerifier, a framework that uses an LLM to synthesize candidate verifier functions and then refines them through search over a directed acyclic graph (DAG). By navigating the DAG, AutoPyVerifier systematically explores the space of deterministic executable verifiers and selects a compact verifier set whose joint satisfaction best approximates the target objective. Across mathematical reasoning, coding, function calling, and instruction-following benchmarks for several state-of-the-art LLMs, AutoPyVerifier improves target-objective prediction by up to 55.0 F1 points over the initial LLM-generated verifier sets. Additional analyses show that the most useful verification targets vary by benchmark and model, and that the DAG-based search shifts the learned verifier sets toward more structural and semantically grounded checks. We further show that exposing the discovered verifier set to an LLM as an external tool improves downstream accuracy by up to 17.0 points. We release our code

Verifier Large Language Model Output

Open paper Ask about it PDF

Abstract

Explore similar work

AutoPyVerifier: Learning Compact Executable Verifiers for Large Language Model Outputs

An Execution-Verified Multi-Language Benchmark for Code Semantic Reasoning

Teaching Code LLMs to Reason with Intermediate Formal Specifications