Beyond Type-checking: Towards Holistic Evaluation of Formal Specification Generation
cs.SE, cs.AI
Submitted: 2026-10-07
Updated: 2026-10-07
Comments: Accepted at NeurIPS 2026 Workshop on AI for Verifiable Coding (20 pages, 7 figures)
License: http://creativecommons.org/licenses/by/4.0/
The gist: When generating verifiable code, natural language requirements are mapped to machine checked code using LLMs and agentic workflows.
Abstract
When generating verifiable code, natural language requirements are mapped to machine checked code using LLMs and agentic workflows. A crucial component of this pipeline is specification generation (SpecGen), which produces a formal contract against which an agent can prove implementation correctness. Proof generation can obtain deterministic feedback from a theorem prover, but SpecGen lacks a definitive check that a generated specification captures the user's intent. A checked proof can therefore establish correctness against a specification that misrepresents the intended behaviour. We take a step towards holistic SpecGen evaluation with a unified dataset assembled from 350 existing Lean tasks, including 189 from VERINA and 161 from CLEVER, and a framework covering formal validity, reference similarity and equivalence, and behavioural adequacy. We distinguish acceptance of required inputs from acceptance of valid outputs and rejection of invalid outputs, while making each metric's evidence scope explicit. Across four SpecGen configurations, restricting the generalized tree edit distance (GTED) comparison, a reference similarity measure, to 32 jointly measurable VERINA tasks changes the VERINA configuration's position from second to fourth in mean similarity, showing the importance of measurement coverage. In an authored control, a specification achieves 100% positive test recall and negative test rejection while accepting 0% of required inputs. This demonstrates that perfect postcondition scores can miss an unusable input contract, motivating separate feedback on input coverage and output constraints.
Sources
- Inductive Deductive Synthesis: Enabling AI to Generate Formally Verified Systems
- A benchmark for vericoding: formally verified program synthesis
- Evaluating Large Language Models Trained on Code
- Generalized Tree Edit Distance (GTED): A Faithful Evaluation Metric for Statement Autoformalization
- Autoformalizing Euclidean Geometry
- VeriContest: A Competitive-Programming Benchmark for Verifiable Code Generation
- Mathesis: Towards Formal Theorem Proving from Natural Languages
- Intent-aligned Formal Specification Synthesis via Traceable Refinement
- AlgoVeri: An Aligned Benchmark for Verified Code Generation on Classical Algorithms
Related papers
- Falsification-Based Verification of LLM-Generated Optimization Models: Sound Test Batteries and Their Detection Limits
- GitSkills: A Dataset of Agent Skills on GitHub
- SABER: Benchmarking Operational Safety of LLM Coding Agents in Stateful Project Workspaces
- PackMonitor: Enabling Zero Package Hallucinations Through Decoding-Time Monitoring
- IntentCoding: Amplifying User Intent in Code Generation
- Incentives and Outcomes in Bug Bounties