acceptodds
Under review as a conference paper at ICLR 2027

Agentic Separation Logic Specification Synthesis

Abstract

Specification synthesis, the task of automatically inferring formal specifications from program implementations and natural language, is important for refactoring, transpilation, and optimization, yet remains an open challenge for large software repositories. Existing LLM-based approaches fail to simultaneously scale to such repositories, produce specifications expressive enough to capture systems-code features such as dynamic memory and heap-allocated data structures, and systematically validate those specifications to rule out incorrect candidates. We present Spec-Agent, a model-agnostic inference-time method for synthesizing expressive, well-validated specifications across programming languages and large codebases. Spec-Agent targets a ladder of specification languages: propositional logic, first-order logic, propositional separation logic, and first-order separation logic. For each function, Spec-Agent uses static analysis and runtime heap tracing to select the appropriate target specification language, generalizes existing functional tests into fuzz harnesses, and iteratively refines LLM-generated candidates via counterexample-guided feedback. We evaluate the same method on large open-source C++ repositories and a popular open-source Rust codebase. Across the evaluated settings, Spec-Agent synthesizes test-valid specifications for up to of target functions, with no false positives observed under fuzzing and expert validation in either language, outperforming Claude Code Opus 4.6 at \textbf{10\times} lower token cost.

Primary area:
neurosymbolic & hybrid AI systems (physics-informed, logic & formal reasoning, etc.)
Keywords:
Coding Agents, Specification Synthesis, Program Logic and Formal Reasoning

Reviews

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

This paper describes a new research of using separation logic, fuzz and LLM in spec generation.The main idea is to use symbolic approach first to generate spec candidates and then use fuzz method to generate test cases which rejects invalid specs. The authors also report experiments on large real programs.

Critical strengths
  1. This work targets large real programs.
  2. This provide informative ablation test results.
Critical weaknesses
  1. This work does not generate correct separation logic spec and fuzz test seems unable to figure that out. In the appendix of this paper, one simple example and generated spec are provided. But the spec is clearly wrong. Not all used memory permission is described. The paper tries to clarify that fuzzing test is not full verification in another appendix. However, this does not mean that wrong spec should be allowed.

  2. Separation logic assertions used in the materiel lack a clear definition.

Questions for authors
  1. What is the meaning of “it.begin()" in your separation logic assertion? Especially it can be a dynamic function. Or does your assertion language only allow read only functions?
  2. If in some C++ class "it.end()" is implemented using internally stored "begin" and "size", is it allowed to use "it.end()" in your assertion language? If yes, what is its meaning?
Reviewer_fwSNOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

This paper presents Spec-Agent, an inference-time framework for synthesizing preconditions and postconditions for functions in large software repositories. It selects among four specification languages based on control-flow and heap-related features, generates candidate contracts using an LLM, and refines them through feedback from compilation, unit tests, and fuzzing. The evaluation covers two C++ repositories and one Rust repository. The authors report higher test-valid rates and lower monetary costs than Claude Code, together with an ablation studying the contribution of separation logic.

Critical strengths
  1. The paper studies a practically relevant problem using functions from real C++ and Rust repositories. Supporting heap-related specifications is useful for systems code, where simple input-output conditions may miss important memory constraints.

  2. Combining specification refinement with fuzz harnesses derived from existing tests is a useful design choice. Table 5 shows that fuzzing finds counterexamples missed by unit tests, providing evidence that this additional validation step can improve candidate filtering.

Critical weaknesses
  1. The correctness and validation of the specifications are not sufficiently established. In Section 2, the encoding of conditional behavior, (p⇒q1)∨(¬p⇒q2)(p \Rightarrow q_1) \lor (\neg p \Rightarrow q_2), is a tautology rather than the intended constraint. Appendix F also contains examples whose executable meaning is unclear. Example 1 uses toAscii(value).size() and stream + i, while Example 64 contains a comment in place of an operand after ||. The paper does not clearly identify whether these are rejected candidates or accepted specifications. These issues make it difficult to assess the reliability of the claimed compilation and fuzz-validation procedure.

  2. The expressivity evaluation does not adequately establish specification quality, and some results conflict with its definition. Examples 61 and 63 introduce an existentially quantified dummy variable that is unused in the predicate, increasing the reported logic level without adding information. Moreover, since Prop is the bottom of the lattice, every test-valid contract for a Prop target should satisfy the stated target-expressivity criterion. However, Figures 5(a) and 9(a) report fewer target-expressive contracts than test-valid contracts. This discrepancy directly affects the interpretation of a central evaluation metric.

Questions for authors
  1. Are Appendix F Examples 1 and 64 accepted specifications? Please provide their translated runtime assertions and compilation results, and explain whether the incorrect conditional encoding in Section 2 appears in the implementation or prompting examples.

  2. How are the target-expressive counts in Figures 5(a) and 9(a) computed, given that Prop is the bottom of the lattice? Please also reconcile the Rust counts stated at the end of Appendix B on page 15 with Figure 9.

  3. Were accepted contracts evaluated using an independent fuzzing run or input set after refinement? How did the evaluation handle vacuous specifications and unnecessarily restrictive preconditions, and what were the criteria used in the expert review?

Reviewer_Qr6HOpenReview ↗
Rating
1(−1)
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper is about specification synthesis, where an LLM infers formal preconditions and postconditions for functions in large C++ and Rust repositories. For each function, the authors pick a target logic (propositional, first-order, propositional separation, or first-order separation logic) based on whether it contains loops and touches the heap. An LLM then writes a candidate contract in that logic. A coding agent turns the project’s unit tests into fuzz harnesses, and the candidate is compiled into a runtime assertion and fuzzed with libFuzzer. Any counterexample, or a contract that is not expressive enough for the target logic, is fed back to the LLM for another attempt, up to a fixed budget. They evaluate four open-weight models on BDE, BlazingMQ, and Tokio, and compare them against Claude Code (Sonnet 4.6 and Opus 4.6) on the fraction of test-valid contracts, contract size, and cost.

Critical strengths
  • The paper is a breath of fresh air to read compared to other papers I have recently reviewed. It is written in a human-friendly way and organized meaningfully. It explains complex PL concepts like separation logic compactly, so someone with only an ML background can follow, and Figure 4 explains the whole pipeline on its own.
  • The idea is sound and practical. Fuzzing is used as a pseudo-oracle for spec inference, and any counterexample is fed back to the LLM for the next attempt. Existing unit tests are generalized into fuzz harnesses, so the validation is stronger than the usual fixed-test checks.
  • The ladder of four logics (propositional, first-order, propositional separation, and first-order separation) is a good design. Each function gets a target logic based on whether it has loops and touches the heap.
  • The evaluation is at a realistic scale. It covers functions from large C++ repositories (BDE and BlazingMQ) and Tokio in Rust, with four open-weight models, and the same method is applied to both languages without changes.
  • The paper is upfront about what it does and doesn’t establish. It states that test validity is empirical non-falsification and not formal proof, and the Limitations section also notes that a target-expressive contract can still miss relevant behavior. The reported cost is also low, at a few dollars per repository for the open models.
Critical weaknesses
  • I do not think the comparison with Claude Code is fair. Spec-Agent gets up to 20 retries, and each retry uses counterexamples from the fuzzer and feedback about the target logic. It only accepts a contract when the fuzzer finds nothing wrong, so a near-zero "Test Invalid" rate is almost guaranteed. For Claude Code, the paper only says it got the same context, prompts, examples, tests, and fuzz harnesses. I could not find whether Claude Code was allowed to run the fuzzer, see the counterexamples, or know the target logic. When you compare against a SOTA model, it is standard to give it the same tools (for example through MCP). Also, Table 1 has no Spec-Agent row with a Claude model, even though the method is called model-agnostic. So I cannot tell whether the gain comes from the model or from the loop, and the claim that a small open model beats Claude is not convincing to me.
  • I feel the test-valid metric is designed to look good. It only means the contract compiles and nobody found a counterexample. I am not sure whether trivial contracts count as valid. They are 16.94% on BMQ and 20.00% on Tokio for Qwen3-Coder-Next, and the Claude rows on Tokio have no value. I also could not tell whether the final score uses a different fuzzing run from the one used during refinement. Table 5 says 8.0% violated on BMQ, while Table 1 says 0.00% to 0.38% test-invalid, and the paper does not explain the difference. The experts only checked 100 sampled specs per repository, which is not much support for "no false positives observed".
  • No contract is ever proved, and there is no small sanity check. The paper says existing verifiers do not cover these languages and repositories. I still wonder why they could not use a verifier like Why3 on a small subset of functions to show how much test validity can be trusted.
  • The Limitations section misses the safe-execution problem. The system compiles and runs LLM-written assertions and harnesses on real repository code. Sandboxing appears only in the Ethics Statement, and I think it belongs in the limitations.
  • The writing is good, but I found a few mistakes. The lookup postcondition in Section 2 is wrong. For an empty list it allows ret = true, and it should have been simply ret = (∃x ∈ lst. P(x)). Figure 1 should be in the experiments section. Algorithm 1 is hard to read and not needed, because Figure 4 already explains the pipeline clearly.
Questions for authors
  1. Could Claude Code run the fuzzer and the assertion builder as tools (for example through MCP) and see the counterexamples, or did it only get the harnesses as part of its context? Was it told the target logic chosen by the selector, and how many attempts did it make per function? If it did not get the same feedback loop as Spec-Agent, why not, given that this loop is the core of the method?
  2. Could you report Spec-Agent with Sonnet 4.6 and Opus 4.6 as the generator? The method is described as model-agnostic, but Table 1 has no Spec-Agent row with a Claude model, so I cannot tell whether the gain comes from the model or from the loop.
  3. Why not discharge the contracts with a deductive verifier such as Why3, at least on a small subset of functions? Appendix C says existing verifiers do not cover these languages and repositories, but even a small verified subset would show how much "test-valid" can be trusted.

Overall, I found the paper very well written (and the idea a bit interesting), but I see weaknesses in the evaluation that I think can be fixed.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.