acceptodds
Under review as a conference paper at ICLR 2027

Specat: Assessing and Categorizing Formal Specifications from Natural Language

Abstract

As AI systems generate code at increasing scale, providing strong assurance such as formal verification becomes increasingly important. However, formal verification is only as good as the specification it verifies. In this work, we study formal specification synthesis and evaluation, a standalone but equally important problem. We first formulate spec-evaluation in the real-world setting: assessing a synthesized formal specification against a brief natural-language(NL) description and a few behavioral examples indicating user intent. We introduce the Spec-Evaluation Methodology, which assesses the relations among an NL description, behavioral examples, a candidate formal specification, and formal test artifacts. It interprets verifier or execution outcomes with critic assessments. We further propose SPECAT, an agentic workflow that synthesizes formal specifications and refines them through two complementary loops. Behavioral-oracle refinement uses user-supplied examples and verifier feedback, while counterexample-guided refinement uses an LLM-based Spec Critic to seek description–specification mismatches beyond those examples. Proposed challenges are formally evaluated, while ultimately under-specified or unresolved cases are left for human clarification. We evaluate SPECAT on 704 benchmark-backend units spanning Dafny, Verus, Why3, and Frama-C. Rather than returning a specification alone, SPECAT categorizes each candidate with an evidence-backed disposition: 391 are Endorsed, 77 are Repaired following a machine-supported challenge, 70 retain an unrepaired challenge (Defect), and 86 are deferred because the available evidence is Unadjudicated or Inconclusive. The remaining 80 fail behavioral-oracle refinement. Together, these results show that SPECAT turns specification generation into a testable assurance step: it produces not only a candidate contract, but also machine-grounded evidence and an explicit disposition for that contract.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
Large language models (LLMs), Formal verification, Specification Evaluation and Synthesis, Counterexample-guided refinement

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_XVxMOpenReview ↗
Rating
3
Confidence
4
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

The paper introduces SPECAT, a framework for generating and evaluating formal specifications from natural-language descriptions and behavioral examples. The main motivation is that formal verification can establish whether code satisfies a specification, but not whether the specification itself captures the user's intent.

SPECAT uses multiple agents to evaluate the relationships between descriptions, specifications, examples, and formal tests. It has two refinement loops: one that uses existing behavioral examples and verifier feedback, and another that generates counterexamples to identify specification errors missed by the initial examples.

The authors evaluate the framework on 704 benchmark-backend units across four verification tools. The results show that 391 specifications are endorsed and 77 are repaired. On Codeforces, counterexample-guided refinement improves the number of clean specifications from 46 to 54 out of 88, with hidden-test violations decreasing from 5.5% to 1.1%.

Critical strengths
  1. Important problem and useful methodology. The paper addresses an important gap in formal verification: ensuring that generated specifications actually represent natural-language requirements. I like the idea of treating specification evaluation as a separate problem rather than assuming that a verified specification is correct. The distinction between specification errors, test-translation errors, and verifier limitations is particularly useful.

  2. Good experimental coverage and evidence of improvement. The evaluation spans multiple benchmarks and verification backends. The counterexample-guided refinement results are promising, particularly the improvement on independent Codeforces hidden tests. The authors also manually audit specifications and explicitly report unresolved cases rather than treating every verifier failure or LLM judgment as conclusive.

Critical weaknesses
  1. Reliability of the Spec Critic and intent validation. My main concern is whether the Spec Critic can reliably identify actual mismatches with natural-language intent. Formal verification can confirm that a counterexample violates the generated specification, but it does not independently validate the LLM's interpretation of the original description. The manual audit identifies false-positive defects caused by incorrect interpretations, and some endorsed specifications remain incorrect. It is still unclear how often the critic misses important errors and how much assurance an endorsement provides.

  2. Limited isolation of the main improvement and evaluation generalization. The counterexample-guided refinement results are encouraging, but it is difficult to separate the benefits of the methodology from using a stronger critic and additional refinement opportunities. The baseline comparisons are not fully equivalent, since the baselines do not receive counterexample-guided repair. Also, independent held-out evaluation is limited to Codeforces, while the manual endorsement audit covers only a subset of the benchmarks. This makes it harder to assess how well the reported improvements generalize.

Questions for authors
  1. How reliable is the Spec Critic at identifying genuine specification errors? In particular, how often does it miss errors or propose counterexamples based on an incorrect interpretation of the description? Can you estimate recall using independently validated defective specifications?

  2. How do you distinguish a formally confirmed specification mismatch from an incorrect interpretation of natural-language intent? Since both the Spec Critic and Advisor are LLM-based, could they share the same misunderstanding?

  3. How much of the improvement comes from counterexample-guided refinement versus the stronger Spec Critic model? Could you compare against simpler iterative refinement using the same model, budget, and counterexample feedback?

  4. The manual audit reports high adequacy for endorsed specifications. How were those cases selected, and how representative are they across task difficulties and verification backends? Could you provide a more systematic evaluation, particularly for Frama-C and Why3?

  5. How sensitive are the results to the number and quality of behavioral examples and the refinement budget? It would be helpful to see whether fewer examples or additional iterations substantially change the final outcomes.

1 comment

We thank the reviewer for the detailed questions and will update the manuscript accordingly.

W1 / Q1. Spec Critic reliability. On Codeforces, the counterexample phase flags 23 of the 28 Loop 1 specifications that fail the hidden suite (82% recall, App. E). Of the 12 endorsed or repaired specifications that still fail, 7 stem from checker conventions absent from the problem text, 3 from repairs missing rare edge cases, 1 from a benchmark–validator disagreement, and only 1 is a genuine detection miss (App. K). Endorsement precision is 48/52 (92%) on the hidden suite and 97/101 (96%) in the manual audit (Q4).

Q2. Confirmed mismatch vs. misreading. Specat has a dedicated check for each common failure mode. Too-weak and over-strict specifications are caught by backend-confirmed counterexamples from the Spec Critic. Convention mismatches (e.g., a null pointer vs. an empty array) are pinned down by seed examples, and evidence unrelated to the specification (an unfaithful test, a timeout) is filtered by the Translation and Semantic Critics. A counterexample the backend cannot decide is labeled UNADJUDICATED, never DEFECT.

Every counterexample makes two claims: what the specification does on a behavior ("it accepts this output") and what the description says about it ("the description forbids this output"). Specat checks the first claim with the backend, never trusting an LLM for it. The second is a reading of natural language that no machine can check, so the Spec Critic and Advisor could in principle share a wrong reading. This is inherent to the problem: since the description is informal, no method can formally prove alignment with intent, and even very recent industrial verification efforts from a frontier AI lab keep human experts reviewing specification [1]. We limit this by design: the Spec Critic uses a different model, is adversarially prompted, and doesn't see the refinement history. Disagreements escalated to human review. The audit shows that shared misreadings are rare (App. I.5) and do not reach a shipped specification, because any repair built on a wrong counterexample must still pass every seed example.

W2 / Q3. Loop vs. stronger critic. App. F holds the writer, Advisor, and budget fixed (the same 88 specifications before and after Loop 2), so the gain from 46 to 54 clean is attributable to the loop. To isolate the critic model, we reran the identical Loop 2 with GPT-5.4 (the writer/Advisor model) as the Spec Critic:

CriticCleanFailedClean among passedHuman review
Loop 1 only462859/88 (67%)–
GPT-5.4462639/47 (83%)26
Sonnet-5502062/74 (84%)0
GPT-5.6-Sol541566/78 (85%)3

With any critic, 83–85% of passed specifications are clean, compared with 67% for Loop 1 alone, so this gain belongs to the method. The critic's quality determines how much passes: GPT-5.4's low precision (27%, Table 7) yields 26 human-review referrals and only 4 repairs, whereas GPT-5.6-Sol turns similar detection into 26 repairs. We will add this comparison to the final version.

Q4. Audit selection and coverage. The 60 endorsed cases were sampled randomly, 20 each from VT-Dafny, LC-Dafny, and VT-Verus. We have now extended the audit to all 21 endorsed Frama-C specifications and a random sample of 20 endorsed Why3 specifications: 20/21 and 19/20 are adequate, for a total of 97/101 (96%). We will add these results to the final version.

Q5. Sensitivity to examples and budget. Seed examples also anchor the interface design and the interpretation of requirements where the prose is open (boundary cases, conventions, input domain), so their effect is hard to reduce to a single score. In a new experiment on 15 VerifyThis/Dafny units exposing only a few examples, all units still passed Loop 1, at lower cost, but some specifications were weaker, missing constraints the visible examples never exercised. The counterexample loop recovered much of this from the description. However, sparse examples make repair harder than detection, since several repairs may be consistent with both the description and the few visible examples. We will add this experiment to the final version.

Budget. The cap ($2.50 per loop) rarely binds. In Loop 1, the median cost is 0.42 and 90% of units finish under 1.40; caps of 1.50 and 2.00 would retain 92% and 96% of the specifications that pass it. In Loop 2, 0.10 covers 70% of units, 0.50 covers 92%, and 1.50 covers 99%. If needed, we can run a larger budget and assess where it rescues FAILURE units. The final version will include the above stats and a detailed analysis of cost by outcome bucket.

References [1] P. Kohli and S. Chaudhuri. Introducing AlphaProof Code: a breakthrough in verifying complex software at depth. Google DeepMind Blog, November 10, 2026. https://deepmind.google/blog/introducing-alphaproof-code/

Reviewer_iCPUOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper presents Specat, an agentic framework for generating, evaluating, and refining formal specifications from natural-language descriptions and behavioral examples. It introduces a specification evaluation methodology that combines LLM-based critics with formal verification evidence. The framework employs behavioral-oracle refinement and counterexample-guided refinement to improve specification quality. Experiments across four verification backends demonstrate the effectiveness of the proposed approach.

Critical strengths
  1. Interesting research perspective.

  2. Reasonable methodology.

Critical weaknesses
  1. Insufficient evaluation of specification strength.

Although the experiments demonstrate improvements in specification quality, they do not establish whether the generated specifications are sufficiently strong or complete. For example, the reduction in hidden-test violation rate from 5.5% to 1.1% is good, but passing finite test cases cannot guarantee that a specification excludes all unintended behaviors. Similarly, the Endorsed label only indicates that no unresolved counterexample was found within the search budget, rather than proving specification correctness.

  1. Limited baseline comparisons.

The paper mainly compares Specat with basic verifier-feedback refinement and SWE-Agent, but lacks comparisons with existing specification synthesis approaches. Several relevant methods, such as SpecGen and AutoSpec, are discussed in the related work but are not included in the evaluation.

  1. Limited specification scale and complexity.

The evaluation primarily focuses on relatively small, function-level specifications from programming benchmarks such as LeetCode, MBPP, and Codeforces. These tasks may not adequately represent real-world specifications involving multiple interacting functions, complex data structures, shared states, or cross-module constraints. Furthermore, the experiments show that performance decreases as task difficulty increases, raising concerns about scalability.

Questions for authors

See Weaknesses

1 comment

We thank the reviewer for the careful review and address each concern below.

W1. Specification strength.

Alignment with user intent (expressed in natural language) cannot be formally proven by any method. This limitation is inherent to the general problem of natural language rather than specific to Specat. Often some user intent remains implicit in the description. Even if the intent is explicitly stated, they remain informal, hence there is no formal object against which to prove the specification. This is why we define ENDORSED as "no standing challenge under the search budget" rather than a proof (Sec. 4.3). Consequently, a human in the loop remains necessary for specification validation. Even in recent large-scale industrial verification, such as Google DeepMind's AlphaProof Code verification of the Signal protocol, formal specifications are drafted with AI assistance and THEN reviewed by human experts [1]. Specat does not aim to remove this human role. Instead, it narrows the gap as far as possible and concentrates human effort where it matters: it endorses well-supported specifications and routes unresolved or disputed cases (UNADJUDICATED, INCONCLUSIVE) to human review with machine-grounded evidence attached.

Since we assume no ground-truth specification exists in our setting, we measure how strongly a specification resists behaviors it never observed, using two independent sources of evidence:

  • Held-out execution oracle (CF-100). The hidden suite contains negative rows (invalid inputs, real hacks, and wrong participant submissions) that a strong specification must reject. On the same 88 entrants, counterexample-guided refinement reduces wrongly accepted outputs from 5.8% to 0.1% and wrongly admitted invalid inputs from 9.0% to 3.5% (Table 9).
  • Manual audit (non-CF suites). Auditors judge each specification adequate only if it is neither too weak (vacuous or missing obligations required by the description) nor too restrictive (rejecting behaviors the description admits). Under this criterion, 97 of 101 sampled ENDORSED specifications (96%) are adequate across five benchmark/backend pairs, including all 21 endorsed Frama-C specifications and 20 sampled Why3 specifications (newly added audit).

W2. Limited baselines.

SpecGen and AutoSpec infer specifications from an existing implementation. Our setting deliberately assumes no implementation, because the specification is meant to precede and check the code; supplying reference code to these methods would change the task and leak the answer. We therefore compare against the applicable code-free alternatives: verifier-feedback refinement and a general-purpose agent (SWE-Agent), both evaluated under the same counterexample validation. On VT-Dafny, Specat finalizes 63 of 98 units, compared with 14 and 25 for these baselines (App. B)

W3. Scale and complexity.

We agree that our units are function-level contracts, and we will state this explicitly in the Limitations. Our benchmarks range from small exercises (MBPP) to verification-competition problems (VerifyThisBench) that include heap-manipulating, concurrent, and persistent data structures, formalized in four backends including Frama-C/ACSL. Function-level contracts are also the unit of modular verification. Extending Specat to cross-module and repository-level specifications is important future work.

Regarding difficulty, harder tasks mainly reduce coverage rather than producing unflagged errors. When Specat cannot support a specification, it reports this with a label and evidence instead of silently returning an unsupported contract. We view this as the intended behavior of an assurance step rather than a scalability failure. Coverage also improves with model capability: stronger Writer/Advisor models raise both coverage and the number of finalized specifications (App. D), so Specat is positioned to benefit as the underlying models improve.

References

[1] P. Kohli and S. Chaudhuri. Introducing AlphaProof Code: a breakthrough in verifying complex software at depth. Google DeepMind Blog, November 10, 2026. https://deepmind.google/blog/introducing-alphaproof-code/

Reviewer_dPtTOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper studies whether synthesized formal specifications capture natural-language descriptions and finite behavioral examples. SPECAT combines diagnostic refinement on supplied examples with critic-proposed counterexamples checked through verification or execution, and returns a specification with an explicit evidence disposition. Evaluation covers 704 benchmark–backend units across four verification tools, with manual audits and held-out Codeforces evaluation. On the same 88 Codeforces diagnostic entrants, the additional refinement phase increases strictly clean specifications from 46 to 54 and reduces violated hidden rows from 5.5% to 1.1%.

Critical strengths
  • The workflow addresses an important gap between verifying a program against its contract and assessing whether that contract captures the request. Its separation of specification errors, test-translation errors, and backend limitations provides a useful structure for interpreting evidence. Explicitly retaining unresolved cases is appropriate, and the manuscript carefully limits endorsement to the available evidence.
  • The evaluation provides substantial support for the integrated workflow. It includes four backends, relevant verifier-feedback and SWE-Agent baselines, model/prompt studies, manual audits, and a paired held-out comparison showing the benefit of counterexample-guided refinement. The reported critic failures and unsuccessful repairs also help characterize the method's practical limits.
Critical weaknesses
  • The incremental contribution is less clearly established than the workflow's practical usefulness. Verus-SpecGym is discussed mainly as the source of the Codeforces benchmark, although its specification-generation setting and agent workflow are closely related; Lahiri (2024) also already studies implementation-free intent formalization. Please add a concise comparison paragraph or table identifying what Specat adds in its diagnostic checks, counterexample refinement, and treatment of unresolved evidence. Discuss VeriAct/Spec-Harness as well. Distinguishing established ingredients from the proposed additions would make the contribution crisper.
  • The component studies provide different kinds of evidence, but Section 5.4 groups them together as ablations. Appendix C characterizes diagnostic predictions, Appendices D–E study model/prompt choices, and Appendix F measures the complete added refinement phase. Please make this distinction explicit in Section 5.4 and connect each principal claim to the corresponding existing experiment. The individual effects of the Semantic and Translation Critics and the separate Advisor role remain unisolated; this should be stated as an attribution limit.
Questions for authors

Please see "Critical Weaknesses" section.

1 comment

We thank the reviewer for the constructive feedback. We will revise the paper accordingly in the final version.

W1. Comparison with previous work.

Lahiri (2024) [1] studies implementation-free intent formalization for Dafny. It scores a specification by soundness and completeness against a test suite and mutants, but does not refine specifications or perform diagnostic checks. VeriAct/Spec-Harness [2] targets a single language and verifier (JML/OpenJML), scoring pre/postcondition correctness and completeness, and assumes a reference implementation exists. Verus-SpecGym [3] primarily proposes a benchmark and an agentic environment with verifier feedback on sample tests, evaluated on hidden tests. In contrast, Specat assumes no reference specification or implementation. We study how to evaluate a specification given only a natural-language description and a few examples, furthermore we propose a counterexample-guided refinement loop. We will add this discussion and the following table to the final version.

WorkNeeds reference specNeeds implementation or hidden testsRefines the specBackends
Lahiri (2024) [1]NoYes (tests)NoDafny
Verus-SpecGym [3]NoYes (hidden tests)YesVerus
VeriAct [2]NoYes (implementation)YesJML
Specat (ours)NoNoYesDafny, Verus, Why3, Frama-C

In summary, Specat builds on the ideas of using LLMs to infer specifications from natural language, iterative refinement driven by verifier and test feedback, and judging a specification by its agreement with input/output pairs. To the best of our knowledge, Specat is the first work to provide a systematic methodology for evaluating a specification that explicitly accounts for three sources of unreliable evidence: 1) finite behavioral examples, 2) verifier/backend failures and timeouts, and 3) LLM translation errors in formal test artifacts. Specat also uses backend-validated counterexamples beyond the limited test examples, not only to score correctness but also to guide the refinement loop. Finally, while prior systems return a binary verdict (pass/fail) or a single score, Specat produces an evidence-backed label.

W2. Presentation of Section 5.4.

Thank you for the advice. We will restructure Section 5.4 to distinguish the baseline comparison (App. B), the phase ablation (App. F), the characterization of critic predictions (App. C), and configuration sensitivity (App. D–E), and we will explicitly acknowledge that the individual effects of the Semantic Critic, Translation Critic, and Advisor role are not isolated.

References

[1] S. K. Lahiri. Evaluating LLM-driven User-Intent Formalization for Verification-Aware Languages. FMCAD 2024.
[2] M. R. H. Misu, I. Ma, C. V. Lopes. VeriAct: Beyond Verifiability – Agentic Synthesis of Correct and Complete Formal Specifications. arXiv:2604.00280, 2026.
[3] A. Agarwal et al. Verus-SpecGym: An Agentic Environment for Evaluating Specification Autoformalization. arXiv:2605.26457, 2026.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.