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
cs.SE, cs.CL
2026-07-30
SpecFirst inserts a dedicated spec agent that black-box probes an executable into a structured spec before synthesis, lifting test pass rates 6.9–21.3% across four models on all 200 ProgramBench tasks.
LLM agents do well on software engineering when there is an existing codebase to anchor on, whether bug fixing, feature work, or completion. Rebuilding a program from scratch is a different animal: hand the agent natural-language docs and an execute-only binary (you can run it, you cannot read it) and ask for a behaviorally faithful reimplementation. ProgramBench quantifies how hard this is. Even GPT-5.5-high fully resolves fewer than 1% of instances.
Existing agent frameworks (SWE-agent, OpenHands) mash documentation reading, binary probing, and code synthesis into one loop, with the agent switching freely inside a single turn budget. The authors pin three systematic failures on this entanglement: shallow probing (it starts coding before it has explored edge cases and error paths), spec loss over long horizons (as context grows, compression strips out the behavioral details it once read in), and error propagation (a function signature misread at turn 4 gets re-emitted wrong through 140 turns of refactoring).
SpecFirst lifts the requirements-engineering phase out of traditional software engineering: before any code, a dedicated spec agent figures out the program's behavior and writes a structured SPEC.md, which the coding agent then consumes.
The spec agent gets the docs and the binary and probes it black-box with free-form bash (no structured probe API, because that mirrors how a human pokes at an unfamiliar tool and lets it chain commands). It hunts along four patterns: boundary probing (empty input, max-length strings, special chars), error-path elicitation (malformed input, missing args, conflicting flags, recording exact stderr and exit codes), combinatorial flag testing, and output-format refinement. Interactive or TUI programs get a pre-installed tmux virtual terminal for keystroke injection.
To stop the agent cheating, two moves are banned outright: recovering source from GitHub or package registries (that would be copying the answer) and binary introspection with disassemblers or tracers. An automated judge scans the command history; any clone, registry install, source tarball download, or disassembler call scores zero. SPEC.md uses six fixed headings (Overview, Flags, Input & stdin, Output format, Error patterns, Edge cases) that prescribe what to record, not how to discover it, keeping elicitation and synthesis isolated.
Termination, in priority order: the spec agent declares itself done (most runs stop well before the 1,000-turn cap), the 1,000-turn hard limit, and a 6-hour wall clock. Between stages the context is compressed, with the spec agent's verbose reasoning dropped and only SPEC.md passed downstream.
All 200 ProgramBench instances, four models (Qwen3.5-397B, Qwen3.6-35B, GPT-5.5-high, GPT-5.4-mini), baseline is the same mini-swe-agent minus the spec phase:
| Model | Baseline | SpecFirst | Gain |
| Qwen3.5-397B | 33.66% | 40.84% | +21.3% |
| Qwen3.6-35B | 27.51% | 31.40% | +14.1% |
| GPT-5.5-high | 59.02% | 65.14% | +10.4% |
| GPT-5.4-mini | 39.09% | 41.78% | +6.9% |
All p<0.01. GPT-5.5-high wins on 150 of 200 instances. The harder the task, the bigger the lift: on Hard instances GPT-5.5-high goes from 30.8% to 40.0% (+29.9%).
It also fattens the upper tail. With GPT-5.5-high, the share of instances passing at least 90% of tests triples from 5.5% to 16.5%, and at least 95% more than quadruples from 1.5% to 6.5%.
Probing coverage (measured with tools like go build -cover and cargo llvm-cov, counting how many of the binary's executable lines the agent actually ran) reaches 58.3%–60.3% with SpecFirst, up 9.4%–18.5% over baseline. The coverage comes almost entirely from the spec agent: the spec agent alone (54.9%–58.3%) beats the coding agent (31.2%–51.3%).
One behavioral finding cuts against the obvious. Baseline agents do not stop because they run out of budget. Zero hit the 1,000-turn cap; the median uses 22–177 turns (2%–18% of budget). They stop because they think they understand enough. With SPEC.md in hand, the coding agent starts writing earlier, writes longer, and ends with 7%–29% more code.
The cost: per-instance spend rises 48%–130%. GPT-5.5-high goes from $2.54 to $5.85 (+130%, mostly the spec agent itself).
This is a paradigm reminder, not a new model. Wherever your agent task has the shape "the target behavior lives inside something runnable and the docs are incomplete," the recipe ports: separate "figure out what is wanted" into its own phase, and persist the output as a file rather than holding it in context. The binary is just an example, the authors note; a REST API, a containerized service, a compiled SDK, a remote CLI, or even a queryable human are all equivalent to the spec agent.
For agent engineers it makes three easy-to-miss points concrete: behavioral intent gets eaten by context compression on long horizons; small early errors compound; and agents stop early from insufficient understanding, not insufficient compute, so throwing more turns at them will not help.
The authors' own validity threats are honest: only deterministic CLI programs, so GUI or complex IPC programs may not transfer; only one scaffold (SWE-agent).
The headline caveat is the failure analysis. The largest failure class, at 52%, is F4 "execution fault": SPEC.md was correct and complete, and the implementation diverged anyway. The spec phase has already hit its ceiling; the remaining gap needs stronger execution-stage reasoning (self-checking against SPEC.md, test-driven repair loops), not a more complete spec. That tempers the "spec solves everything" reading: the gains come largely from instances the baseline could already partially pass, and the rest is the coding agent's own competence.
The doubled cost is a real constraint too. $5.85 per instance on GPT-5.5-high, and the full 200-instance by four-model by two-config sweep is not cheap.