PaperlayerView exact revision on arXiv

Source-linked AI summary

SpecFirst: Behavioral Specification Elicitation as a First-Class Step in Agent-Based Program Synthesis from Scratch

Yihao Chen, Shi Chang, Feng Lin, Khaled Chawa, Boyuan Chen, Shaowei Wang, Ahmed E. Hassan

arXiv:2607.27167v1cs.SEcs.CL

TL;DR

From-scratch program synthesis remains difficult when agents must infer behavior from documentation and an execute-only binary. SpecFirst separates behavioral specification elicitation from code synthesis, consistently improving test pass rates by 6.9%–21.3% and exploration coverage by 9.4%–18.5% across 200 ProgramBench instances.

  • Problem

    Existing agents often begin implementation before thoroughly modeling undocumented edge cases, error paths, and flag interactions.

  • Method

    SpecFirst uses a dedicated agent to probe the binary and produce a structured specification before a separate synthesis agent implements the program.

  • Results

    SpecFirst consistently outperforms the baseline across all four models, improving test pass rates by 6.9%–21.3% and exploration coverage by 9.4%–18.5%.

  • Takeaways & Limitations

    Treating behavioral requirements elicitation as a first-class phase is a promising paradigm for from-scratch program construction.

  • Takeaways & Limitations

    Faithful reimplementation remains challenging because documentation can be ambiguous or silent about edge cases, output formats, and error behavior.

Abstract

from arXiv · show

LLM-based agents excel at software engineering tasks where an existing codebase provides context, but constructing a program from scratch remains fundamentally harder. Recent benchmarks such as ProgramBench quantify this gap: given only natural-language documentation and an execute-only binary as a behavioral oracle, even frontier models solve fewer than 1% of instances. Existing frameworks conflate documentation reading, behavioral exploration, and code synthesis into a single pass, causing agents to probe insufficiently, lose behavioral intent as context drifts, and propagate early misinterpretations into the final implementation. Inspired by classical requirements engineering, we argue that behavioral specification elicitation should be a first-class phase that precedes implementation. We present SpecFirst, a two-stage framework that forces the specification elicitation before code synthesis. A dedicated spec agent first probes the binary and combines observations with documentation into a structured specification. Next, a code synthesis agent then uses this specification to drive implementation. This decomposition resolves documentation ambiguities before coding begins and provides a stable behavioral reference throughout synthesis. We evaluate SpecFirst on all 200 ProgramBench instances across four models spanning two families and an order of magnitude of capability. SpecFirst consistently outperforms the single-loop baseline, improving test pass rates by 6.9%-21.3% and binary exploration coverage by 9.4%-18.5%, all statistically significant. Behavioral analysis on code synthesis further shows that a prior specification enables earlier and more sustained code construction. Our results demonstrate that an explicit requirements-engineering phase is an effective paradigm for from-scratch program construction.

I. INTRODUCTION

From-scratch program construction remains difficult because agents must reconstruct behavior from documentation and an execute-only binary, while existing single-loop frameworks inadequately elicit and preserve specifications. SpecFirst addresses this with a two-stage specification-then-synthesis pipeline that improves benchmark performance and changes synthesis behavior.

  • Challenge: Fewer than 1% of ProgramBench instances are fully resolved by frontier models given only documentation and an execute-only binary.ProgramBench requires faithful re-implementation from scratch while leaving architecture and language decisions to the agent.
  • Limitations: Single-loop frameworks mix documentation reading, binary probing, planning, and coding, often committing to implementation before behavioral discovery is complete.This causes missed edge cases, error paths, and flag interactions absent from documentation.
  • Limitations: Without an explicit specification, behavioral intent drifts as context grows and early misinterpretations compound across later implementation decisions.Reasoning-token stripping and context summarization can selectively discard tokens encoding the original specification.
  • Approach: SpecFirst separates behavioral specification elicitation from code synthesis: a dedicated spec agent systematically probes the binary and produces SPEC.md before synthesis begins.The code synthesis agent then receives the documentation, binary, and structured behavioral specification.
  • Results: 6.9%–21.3% test pass rate improvement and 9.4%–18.5% binary exploration coverage gains over mini-SWE-agent were statistically significant across all 200 ProgramBench instances and four models.Behavioral analysis found that prior specifications led agents to start coding earlier and sustain implementation longer.

II. BACKGROUND AND MOTIVATION · A. Problem Formulation

The task is to reconstruct a deterministic command-line program from natural-language documentation and an execute-only binary, producing an implementation whose executable matches the binary’s observable behavior on hidden tests. Existing agents use an iterative probe-then-build loop that combines behavioral exploration, documentation reading, and progressive code refinement.

  • A. Problem Formulation: P is a deterministic command-line program observed through documentation D and an execute-only binary B, with source code and internal structure inaccessible.The agent must infer behavior from these two artifacts.
  • A. Problem Formulation: The agent produces implementation ˆI and necessary build files, reconstructing executable ˆB from the resulting source.The reconstructed executable is evaluated as the behavioral replica of P.
  • A. Problem Formulation: Each hidden test case specifies a command-line argument string ai, standard-input stream si, and ground-truth output B(ai, si).The test suite is represented as T = {ti}N.
  • A. Problem Formulation: PassRate measures the fraction of tests where ˆB exactly reproduces P’s observable behavior, reaching 1.0 if and only if ˆB is behaviorally equivalent to B on T.The objective is to maximize this hidden-test pass rate.
  • A. Problem Formulation: Existing code synthesis agents iteratively invoke B on selected inputs, read D, write source, test it, and progressively refine the implementation.This is the probe-then-build pipeline presented in Figure 1’s blue box.
  • A. Problem Formulation: The documentation example describes gomplate as a template renderer supporting JSON, YAML, HTTP endpoints, environment variables, and other datasources.This illustrates the natural-language documentation available to the agent.
  • A. Problem Formulation: The gomplate documentation includes environment-variable usage, inline template evaluation, and datasource-file access through command examples.The examples include `{{ .Env .USER }}`, `{{ mul 6 7 }}`, and `(ds "config").foo.bar.baz`.

B. Limitations of Existing Code Synthesis Agent · III. APPROACH OF SPECFIRST · A. Eliciting Behavior Specification through Probing of the Executable File

Existing synthesis agents can miss undocumented behavior and let early misunderstandings propagate into implementation failures. SpecFirst addresses these limitations by eliciting and persisting a behavioral specification through iterative black-box probing before code synthesis.

  • B. Limitations of Existing Code Synthesis Agent: Documentation describes primary features and typical usage but remains ambiguous or silent on edge cases, output formats, and error behavior.The gomplate README illustrates this gap by listing common flags while omitting extensive built-in-function behavior.
  • B. Limitations of Existing Code Synthesis Agent: 126 test cases failed when the final submission omitted six namespaces after previously observed information was never re-referenced.The function map registered 17 namespaces and silently omitted all six, causing failures before implementation began.
  • III. APPROACH OF SPECFIRST: SpecFirst introduces a dedicated specification elicitation phase before implementation to address incomplete exploration and persistent error propagation.A spec agent systematically probes the binary, while the elicited specification is persisted as SPEC.md for subsequent synthesis.
  • A. Eliciting Behavior Specification through Probing of the Executable File: At each turn, the spec agent selects a probe from inferred behavior and observes stdout, stderr, and exit results.Free-form bash mirrors human interaction and supports chained commands for constructing inputs, running the binary, and inspecting outputs.
  • A. Eliciting Behavior Specification through Probing of the Executable File: The iterative probing loop uses each binary observation to choose the next probe, progressively deepening exploration beyond the behavioral skeleton supplied by documentation.The method targets behavior classes that documentation characteristically under-specifies.
  • A. Eliciting Behavior Specification through Probing of the Executable File: Boundary probing tests limits such as empty input, maximum-length strings, and special characters to determine exact boundary semantics.These tests target behaviors that documentation leaves implicit.
  • A. Eliciting Behavior Specification through Probing of the Executable File: Error-path elicitation triggers malformed inputs, missing arguments, and conflicting flags to record precise stderr messages and exit codes.This systematically characterizes error conditions omitted from prose documentation.
  • A. Eliciting Behavior Specification through Probing of the Executable File: Combinatorial flag testing and output-format refinement expose flag interactions and resolve ambiguities in ordering, delimiters, and whitespace.Adjacent inputs are compared to distinguish output-format behavior that prose descriptions leave underspecified.

B. Constraints and Shortcut Prevention · C. Specification Deliverable and Format · D. Termination

SpecFirst prevents shortcut-based performance inflation by restricting agents to black-box interaction and rejecting prohibited behavior. It delivers specifications through a lightweight six-section scaffold and terminates elicitation using prioritized completion, step, and wall-clock safeguards plus an artifact-presence gate.

  • B. Constraints and Shortcut Prevention: Source recovery and binary introspection are prohibited because they bypass genuine behavioral understanding and would confound evaluation.Source recovery includes locating original code online; introspection includes disassemblers, tracers, or decompilers.
  • B. Constraints and Shortcut Prevention: All binary interactions use the normal user interface, while command-history violations trigger disqualification and a score of zero.The judge checks for repository clones, registry installs, source-tarball downloads, and disassembler calls.
  • C. Specification Deliverable and Format: The specification uses six headings—Overview, Flags, Input & stdin, Output format, Error patterns, and Edge cases—to balance actionability with behavioral detail.This light scaffold replaces raw transcripts, which are difficult to act on, without imposing an over-prescribed template.
  • D. Termination: Specification completeness has no semantic oracle, so premature termination risks incompleteness while nontermination yields no specification.Termination conditions are therefore applied in priority order.
  • D. Termination: Self-declared completion is primary: the spec agent finalizes when it judges the specification complete, and that judgment is measured as a research variable.Completeness is determined by the agent itself rather than an external completeness evaluator.
  • D. Termination: 1,000 agent–environment turns provide a high-coverage safety net, although most runs self-terminate well before reaching the cap.The step limit is generous and generally nonbinding in practice.
  • D. Termination: 6 hours is the final wall-clock safeguard, after which the spec agent is terminated.This condition follows the self-declared completion and step-limit safeguards.
  • D. Termination: A deliverable gate rejects submissions without the specification file and permits at most 8 rejections before recording failure.After each rejection, the agent is asked to write the missing specification file.

E. Principles of Agent Design · IV. EXPERIMENTAL DESIGN · A. Research Question

SpecFirst’s agents use a ReAct architecture with explicit reasoning after each tool call, while the experiments evaluate effectiveness, difficulty robustness, exploration coverage, and effects on code-synthesis behavior.

  • E. Principles of Agent Design: SpecFirst agents follow the ReAct design and emit reasoning after every tool call to process observations, alternatives, and next actions explicitly.This design is intended to prevent blind tool-call chaining and make reasoning interpretable.
  • IV. EXPERIMENTAL DESIGN: The experimental-design section covers research questions, the studied dataset, retrievers, prompt templates, and implementation details.
  • A. Research Question: RQ1 asks: “What is the effectiveness of SPECFIRST?”
  • A. Research Question: RQ2 asks how effective SPECFIRST is across task difficulty levels.
  • A. Research Question: RQ3 asks whether the Spec Agent improves behavioral exploration coverage.
  • A. Research Question: RQ4 asks how SPECFIRST affects the code synthesis agent’s behavior.The study evaluates RQ1 on from-scratch synthesis against a selected baseline, RQ2 across difficulty levels, RQ3 against the baseline for specification exploration, and RQ4 on code-synthesis behavior.

B. Benchmark … E. Baselines

The evaluation uses all 200 PROGRAMBENCH command-line program instances, measures mean average test pass rate and probing coverage, compares four models, and isolates SpecFirst’s specification-elicitation phase against direct synthesis. The benchmark metric captures partial behavioral reproduction, while the baseline keeps the synthesis scaffold and settings fixed except for adding a spec agent.

  • B. Benchmark: 200 PROGRAMBENCH instances cover real-world open-source command-line tools, including FFmpeg, SQLite, and the PHP interpreter.The repositories are primarily written in Rust, Go, and C/C++, with one Java and one Haskell repository.
  • C. Evaluation Metric: Average test pass rate is the primary metric, computed as the mean instance-level ratio of hidden test cases passed to total test cases.For instance p, the pass rate is r_p = k_p/n_p, averaged over all benchmark instances.
  • C. Evaluation Metric: 1 of 200 instances is fully resolved by the strongest Direct-Synthesis baseline, yet average pass rate still captures partial behavioral coverage.This partial-credit metric detects incremental improvements that a binary resolved/unresolved rate would mask.
  • C. Evaluation Metric: Probing coverage records the fraction of executable lines exercised during specification through language-specific instrumentation of every binary probe.The setup uses go build -cover for Go, gcc --coverage for C/C++, and cargo llvm-cov for Rust.
  • D. Models: The study evaluates four models spanning two families and an order of magnitude of capability to separate model-scale effects from model-family effects.All models use reasoning enabled; Qwen models use thinking by default, and other decoding parameters remain at provider defaults.
  • E. Baselines: Direct-Synthesis gives the code agent documentation and binary access, then proceeds directly to implementation without specification elicitation.It establishes the standard pipeline’s performance and the net gain attributable to the full elicitation phase.
  • E. Baselines: The Direct-Synthesis and SpecFirst conditions use the same official mini-swe-agent scaffold, differing only by SpecFirst’s added spec agent.All other settings are kept the same, isolating the effect of specification elicitation.

F. Implementation details … 2) Results:

Across the full 200-instance evaluation, SPECFIRST significantly outperforms Direct-Synthesis in average and near-perfect test performance. Its isolated, phase-separated implementation and elicited specifications support consistent behavioral improvements across models.

  • F. Implementation details: Experiments run in isolated, no-network Docker containers using ProgramBench task images, with the same model performing specification elicitation and code synthesis.Local modifications were released as patches against the exact commits.
  • F. Implementation details: LiteLLM routed all model API calls, while each pipeline phase received a fresh context to prevent information leakage between specification and execution runtimes.Experiments used model APIs accessed through a stable API provider.
  • 1) Approach:: SPECFIRST was compared with Direct-Synthesis across all four models and the full 200-instance suite under otherwise identical conditions.Per-instance pass rates were analyzed with a paired two-sided Wilcoxon signed-rank test at α = 0.05, alongside win/loss/tie counts.
  • 2) Results:: 6.9%-21.3% relative gains in average test pass rate were achieved by SPECFIRST across all four models, with all improvements statistically significant at p < 0.01.The reported range spans GPT-5.4-mini at 6.9% and Qwen3.5-397B-A17B at 21.3%.
  • 2) Results:: 5.5% to 16.5%: SPECFIRST tripled the proportion of near-perfect solutions at t ≥90% under GPT-5.5-high.Near-perfect solutions are programs passing almost all tests, and the upper-tail improvement was observed across the score distribution.
  • 2) Results:: 1.5% to 6.5%: SPECFIRST more than quadrupled the proportion of programs exceeding t ≥95% under GPT-5.5-high.A consistently similar trend appeared across the other evaluated models.
  • 2) Results:: The elicited gomplate SPEC.md records function sets, aliases, flags, and edge cases so the execution agent can implement behaviors without guessing.The paper links this thorough specification to reduced behavioral residual and the consistent pass-rate lift across all four models.

B. RQ2 - Effectiveness across different difficulty levels · 1) Approach:

SpecFirst’s robustness is assessed across three benchmark-defined task-difficulty tiers: Easy, Medium, and Hard.

  • 1) Approach:: The analysis evaluates SpecFirst across different task-difficulty levels to assess robustness.Difficulty tiers are provided by the benchmark.
  • 1) Approach:: Three difficulty tiers are examined: Easy, Medium, and Hard.
  • 1) Approach:: Easy tasks comprise 28 benchmark instances.The passage reports Easy as n = 28.
  • 1) Approach:: Medium tasks comprise 143 benchmark instances.The passage reports Medium as n = 143.
  • 1) Approach:: Hard tasks comprise 29 benchmark instances.The passage reports Hard as n = 29.
  • 1) Approach:: The tier assignments used in the analysis come from the benchmark’s difficulty tags.

2) Result: … 1) Approach:

SpecFirst separates behavioral specification elicitation from code synthesis, producing broader probing coverage and higher test pass rates than Direct-Synthesis across models and difficulty levels. The dedicated spec agent drives the coverage gains, while the elicited specification shapes subsequent code construction.

  • 2) Result:: SpecFirst consistently outperforms Direct-Synthesis across all difficulty levels and evaluated models.The reported improvement is not restricted to a particular task tier or model architecture.
  • 2) Result:: 29.9% improvement raises GPT-5.5-high’s average test pass rate on Hard instances from 30.8% to 40.0%.The passage identifies this as the frontier model’s most pronounced surge and notes that the largest absolute gains often occur where the baseline struggles most.
  • 1) Approach:: The spec agent probes the binary and elicits a behavioral specification before implementation, unlike Direct-Synthesis, which has no dedicated elicitation phase.This comparison evaluates whether specification elicitation improves exploratory coverage.
  • C. RQ3 - Effectiveness of Spec Agent: 58.3%–60.3% total coverage represents a 9.4%–18.5% improvement over Direct-Synthesis on every model, with all improvements statistically significant (p < 0.05).The passage attributes the gain to the spec agent rather than the code synthesis agent.
  • 2) Results:: 54.9%–58.3% coverage from the spec agent exceeds the code synthesis agent’s 31.2%–51.3% on all models, while their union adds only marginally.This indicates that coverage gains are driven by dedicated elicitation rather than incidental synthesis exploration.
  • 1) Approach:: The analysis records codebase size in lines of code at every agent–environment turn for SpecFirst and Direct-Synthesis.Turn indices are normalized to [0, 1] by dividing each index by the run’s total number of turns.

2) Results: · VI. RELATED WORK · A. LLM-based Code Generation and Program Synthesis

SpecFirst separates behavioral specification elicitation from implementation, causing agents to begin coding earlier and sustain construction longer than Direct-Synthesis. This addresses limitations of current LLM program-synthesis approaches, whose performance degrades as tasks move from constrained functions to repository- or whole-program settings.

  • 2) Results:: SpecFirst shifts code synthesis from probe-then-build toward earlier, more sustained implementation.The code synthesis agent receives a persistent behavioral specification before implementation.
  • 2) Results:: Direct-Synthesis typically spends 11 to 20 turns probing, whereas SPECFIRST spends 2 to 9 turns establishing context before implementation.SPECFIRST externalizes exploration into a persistent SPEC.md during a dedicated specification phase.
  • 2) Results:: Direct-Synthesis agents stop because they believe they understand enough behavior, rather than because they exhaust their turn budget.The results identify behavioral understanding, not compute allocation, as the bottleneck.
  • 2) Results:: 7–29% larger final codebases are produced by SPECFIRST across models, consistent with more complete implementations under reduced behavioral uncertainty.The passage connects larger codebases to higher probing coverage and broader implementation coverage.
  • A. LLM-based Code Generation and Program Synthesis: Current LLM code synthesis has progressed from template filling and neural program induction to autoregressive models trained on hundreds of billions of source-code tokens.These models perform strongly on function-level benchmarks such as HumanEval and MBPP, where specifications are highly constrained and unambiguous.
  • A. LLM-based Code Generation and Program Synthesis: Performance degrades markedly when the same synthesis paradigm expands from isolated functions to repository-level or whole-program tasks.SWE-bench requires resolving real GitHub issues while understanding substantially harder repository context.
  • A. LLM-based Code Generation and Program Synthesis: Agentic frameworks extend LLM reach through shell, file-editor, and web-search tool loops but still treat a human-written task description as fixed.This limitation motivates separating behavioral exploration from implementation.

B. Requirements Elicitation in Software Engineering … B. Does the specification’s format matter?

The paper situates SpecFirst at the intersection of interactive requirements elicitation and active black-box analysis, while showing that specification format and execution-stage reasoning shape outcomes. Structured Sections specifications perform best among tested formats, but remaining failures primarily reflect implementation-stage reasoning rather than elicitation alone.

  • B. Requirements Elicitation in Software Engineering: Written requirements often omit behavioral details, contain ambiguities, or conflict, motivating interaction-based elicitation as a standard remedy.NLP and LLM methods have automated ambiguity detection, traceability recovery, and inconsistency detection.
  • C. Black-box Program Analysis and Specification Extraction: Protocol reverse engineering shares SpecFirst’s black-box observation model but targets machine-readable protocol grammars for security analysis rather than natural-language specifications for code generation.Specification mining and dynamic invariant detection infer formal properties from traces, while differing in observation and probing requirements.
  • A. Failure case analysis: Failure analysis jointly examines failing-test messages, Spec.md precision, and relevant source snippets to identify where expected behaviors are omitted or misimplemented.The analysis samples 50 failures across four models.
  • A. Failure case analysis: 52% of failures are dominant F4 cases, indicating that closing the remaining gap requires stronger execution-stage reasoning rather than spec elicitation alone.Suggested remedies include instruction following, self-consistency checks against Spec.md, and test-driven repair loops; F1–F3 account for 40% combined.
  • B. Does the specification’s format matter?: Specification-format conditions differ only in the deliverable-instruction paragraph, with identical prompt text, probing rules, and limits across conditions.Sections asks agents to write structured Markdown under named headings, whereas Freeform lets agents choose their own structure; a more formal condition uses requirements vocabulary and GIVEN/WHEN/THEN scenarios.
  • B. Does the specification’s format matter?: Every tested specification format improves on the baseline, while Sections improves the most and outperforms the other formats.The comparison uses average test pass rate for SpecFirst with GPT-5.4-mini on 50 randomly sampled instances.

C. Cost of SPECFIRST · D. Threats to Validity · VIII. CONCLUSION

SpecFirst improves behavioral specification by adding a dedicated elicitation phase, but this two-agent design increases cost and raises compute-budget validity concerns. The conclusion attributes its benefits to more systematic exploration, specification retention, and reduced error propagation.

  • C. Cost of SPECFIRST: 48%–130% higher total per-instance cost makes SPECFIRST more expensive than Direct-Synthesis across models.The added spec-agent phase costs $0.25–$3.16 per instance.
  • C. Cost of SPECFIRST: +6%–+32% synthesis-cost increases occur for most models as more complete specifications produce larger implementations.The passage characterizes this as a modest increase in code synthesis cost.
  • C. Cost of SPECFIRST: 17% lower synthesis cost for GPT-5.4-mini suggests that clearer upfront specifications can reduce exploratory overhead during coding.GPT-5.4-mini is identified as the exception to the usual synthesis-cost increase.
  • C. Cost of SPECFIRST: +130% overhead for GPT-5.5-high is driven primarily by the spec agent rather than synthesis.This is reported as the largest overhead among the models discussed.
  • D. Threats to Validity: 100% of runs ended early by choice, mitigating the threat that SPECFIRST’s gains came solely from giving the model a larger compute budget.The comparison concerns SPECFIRST’s two agents versus the one-agent baseline without a spec agent.
  • VIII. CONCLUSION: SPECFIRST decouples behavioral specification elicitation from code synthesis through a two-stage framework for from-scratch program re-implementation.A separate spec agent probes the binary and produces a structured specification before implementation.
  • VIII. CONCLUSION: SPECFIRST addresses insufficient exploration, specification loss across multi-turns, and uncorrected error propagation in single-loop baselines.The conclusion presents these as three fundamental limitations of the baseline approach.
Loading 2607.27167v1…