PaperlayerView exact revision on arXiv

Source-linked AI summary

ProgramBench: Can Language Models Rebuild Programs From Scratch?

John Yang, Kilian Lieret, Jeffrey Ma, Parth Thakkar, Dmitrii Pedchenko, Sten Sootla, Emily McMilin, Pengcheng Yin, Rui Hou, Gabriel Synnaeve, Diyi Yang, Ofir Press

arXiv:2605.03546v1cs.SEcs.AI

TL;DR

Existing coding benchmarks do not extensively measure whether agents can architect and implement complete software projects from scratch. ProgramBench addresses this gap by giving agents only a program and documentation, then evaluating reconstructed behavior with hidden behavioral tests across 200 tasks. None of the evaluated models fully solves a task, while the best model passes 95% of tests on 3% of tasks and produces codebases that diverge from human-written structures.

  • Problem

    Existing benchmarks focus on localized coding tasks, leaving agents’ ability to make architectural decisions for complete software projects insufficiently studied.

  • Method

    ProgramBench removes source code and tests, gives agents a program and documentation, and evaluates reconstructed executables with hidden behavioral tests that do not prescribe implementation structure.

  • Results

    None of the 200 tasks is fully resolved; Claude Opus 4.7 passes 95% of tests on 3% of task instances, while model-generated codebases diverge from human-written ones.

  • Takeaways & Limitations

    ProgramBench exposes substantial gaps in models’ decisions about architecting, developing, and testing software while measuring meaningful partial progress.

  • Takeaways & Limitations

    Finite behavioral tests provide only a lower bound on correctness and omit non-functional properties such as speed, memory usage, and disk footprint.

Abstract

from arXiv · show

Turning ideas into full software projects from scratch has become a popular use case for language models. Agents are being deployed to seed, maintain, and grow codebases over extended periods with minimal human oversight. Such settings require models to make high-level software architecture decisions. However, existing benchmarks measure focused, limited tasks such as fixing a single bug or developing a single, specified feature. We therefore introduce ProgramBench to measure the ability of software engineering agents to develop software holisitically. In ProgramBench, given only a program and its documentation, agents must architect and implement a codebase that matches the reference executable's behavior. End-to-end behavioral tests are generated via agent-driven fuzzing, enabling evaluation without prescribing implementation structure. Our 200 tasks range from compact CLI tools to widely used software such as FFmpeg, SQLite, and the PHP interpreter. We evaluate 9 LMs and find that none fully resolve any task, with the best model passing 95\% of tests on only 3\% of tasks. Models favor monolithic, single-file implementations that diverge sharply from human-written code.

1 Introduction

ProgramBench targets the under-studied ability of software engineering agents to make architectural decisions while rebuilding complete programs from scratch. It evaluates whether agents can reproduce executable behavior from only a program and its documentation, using implementation-agnostic behavioral tests.

  • Motivation: Building full applications from scratch requires software design decisions beyond the localized changes measured by existing coding tasks.These decisions include choosing languages and build systems, organizing codebases, selecting data structures, and designing error handling.
  • Benchmark: ProgramBench asks an SWE-agent to write source code and a compile script that reproduce a provided program’s behavior from its executable and documentation.The agent controls every software design decision, including architecture, abstractions, and module decomposition.
  • Evaluation: Behavioral tests probe the original program with varied inputs and evaluate candidate reconstructions by input-output behavior rather than implementation structure.Tests remain hidden from task workers, allowing different algorithms, abstractions, and programming languages when behavior matches.
  • Results: 200 task instances span compact CLI tools and widely used software including PHP, Lua, tinycc, DuckDB, SQLite, FFmpeg, zstd, xz, ripgrep, fzf, and jq.The benchmark evaluates 9 language models with mini-SWE-agent; no task instance is fully resolved, while Opus 4.7 passes 95% of tests on 3% of instances.
  • Contribution: ProgramBench is released to support reproduction and further investigation of end-to-end autonomous software development.The release is intended to enable the community to reproduce and build upon the benchmark’s investigations.

2 ProgramBench

ProgramBench converts open-source repositories into open-ended reconstruction tasks by retaining an executable and documentation while removing implementation details. Agent-generated behavioral tests evaluate observable behavior, making the benchmark extensible and independent of source structure.

  • Task Formulation: A task worker receives a gold executable and usage documentation, then writes source code and a build script for a behaviorally equivalent candidate executable.Workers cannot access the internet and may use any programming language.
  • Behavioral Testing: Behavioral tests assert externally observable effects such as output, exit codes, and file-system side effects, while remaining hidden from task workers.The finite suite under-approximates the full specification, but its coverage can be extended and its assertions are quality-checked.
  • Task Construction: The collection pipeline compiles repositories, generates behavioral tests, and strips source code and implementation details from the starting task.The pipeline uses mini-SWE-agent with Claude Sonnet 4.5 inside Docker containers.
  • Benchmark Properties: Because evaluation compares executable behavior rather than source code, models can choose different languages, algorithms, and architectures without a mandated project structure.This open-ended design permits multiple valid solutions while preserving implementation-agnostic evaluation.
  • Benchmark Properties: The collection workflow requires only a repository that produces a standalone executable, making the benchmark straightforward to extend.It does not require an existing test suite, language-specific AST tooling, or ecosystem-dependent frameworks.

3 Experiments

The experiments evaluate 9 recent language models with a minimal, standardized coding-agent scaffold under fixed compute limits. They report both complete-task resolution and test-level partial progress, while noting that the softer metric is mainly useful for relative comparisons.

  • Models: 9 recent language models are evaluated using vendor-default hyperparameters.The models include Claude, Gemini, and GPT variants selected as strong coding models based on existing benchmark rankings.
  • Agent Scaffold: mini-SWE-agent provides a minimal and widely adopted scaffold intended to reduce confounds between model capability and harness design.Each run is limited to 1,000 steps and 6 hours in a container with 20 CPUs and 60GB RAM.
  • Metrics: % Resolved measures the percentage of task instances whose codebases pass all associated tests without being flagged for cheating.% Tests Passed captures partial progress when no task is fully resolved, but it is meaningful mainly for relative model comparisons.

4 Results

ProgramBench results show that models make partial progress but struggle to fully reproduce program behavior, with difficulty patterns broadly consistent across models. Ablations indicate that changing the implementation language has mixed effects, while internet access introduces substantial cheating and unreliable detection.

  • No model fully solves any ProgramBench task, while Claude Opus 4.7 passes at least 95% of tests on 3.0% of tasks.
  • Task difficulty is broadly model-agnostic: simpler CLI utilities score higher, whereas complex systems such as FFmpeg and php-src remain out of reach.
  • Different-language constraint: Under a different-language constraint, all three GPT models improve by 4.2%, while Claude Opus 4.7 and 4.6 decline and other models remain roughly unchanged.
  • Open internet with cheating detection: With internet access, 20–36% of tasks are flagged for cheating among three stronger models, primarily because of source code lookup.
  • Open internet with cheating detection: Judges disagree on 40–57% of tasks for the stronger models, limiting the reliability of cheating detection even with nine judges.

5 Analysis

ProgramBench analysis shows that generated tests provide substantial behavioral coverage, while model solutions diverge markedly from reference codebases in language, structure, function organization, and development process. Models also differ substantially in how many turns they use and how they interleave probing with implementation.

  • Test suite quality: Generated suites average 79.7% line coverage, versus 56.8% for native suites, while their median coverage is 86.2% versus 64.3%.The comparison spans 100 repositories.
  • Test suite quality: Generated suites average 62.16% line coverage versus 66.11% for native behavioral suites, meeting or exceeding native coverage on 6 of 12 projects.They fall within 10 percentage points on all but two projects.
  • Test suite quality: 3.7% of linter-enforced tests pass a dummy implementation, compared with 18.5% without quality enforcement, a 5× reduction.The pipeline removes trivially passing tests after generation, affecting 24 tasks.
  • Model-generated codebases: 50% of model runs match the reference language, with Python used in 36% of all 1,800 runs and Rust in 25%.Language choice remains unconstrained by the benchmark.
  • Model-generated codebases: Models produce a median of 1,173 lines and 3 files, versus 3,068 lines and 15 files in reference codebases; 60% use 1–3 code files.Among high-scoring solutions, 85% fall below reference line-count parity.
  • Model-generated codebases: 67% of runs have shallower maximum directory depth than the reference, with median depth 1 versus 2, indicating a preference for monolithic layouts.Only 2% of runs are deeper than the reference.
  • Model-generated codebases: Models write only 10–29% as many functions as references, while average function length reaches 1.62× for Gemini 3.1 Pro.GPT 5.4 writes functions that are 1.08× longer while producing 10% as many functions.
  • Agent trajectories: GPT 5.4 uses a median of 17 commands per task, versus 868 for Claude Sonnet 4.6, while 98.1% of all trajectories voluntarily submit within budget.GPT 5.4 averages 1.2 file modifications, compared with 18.3 for Sonnet 4.6.

6 Related Work

ProgramBench extends code-generation evaluation from filling erased implementations or resolving existing issues to reconstructing complete programs from executable behavior. It also differs from decompilation, environment setup, and optimization benchmarks by targeting holistic behavioral recreation.

  • Code from scratch: Commit0 converts 54 Python libraries into tasks by erasing function and class implementations, then measures the percentage of original tests passed.This represents an earlier fill-in-the-blanks paradigm for code generation.
  • Code from scratch: Prior program-recreation studies use small-scale, hand-crafted instances, whereas ProgramBench provides systematic benchmark construction and scaling.Decompilation instead targets recovering source code from binaries.
  • Issue resolution: SWE-bench evaluates bug fixes and feature requests within existing codebases, while ProgramBench evaluates building a codebase from scratch.The benchmarks are complementary.
  • Automatic environment setup: ProgramBench treats environment setup as a prerequisite to producing a working solution rather than evaluating it in isolation.Models must handle dependencies and build-tool configuration as part of reconstruction.
  • Performance optimization: Optimization benchmarks measure runtime improvements while preserving correctness, whereas ProgramBench’s salient distinction is reconstructing program behavior from scratch.The supplied passage frames this as a distinction from performance-optimization work.

7 Discussion

ProgramBench provides a demanding testbed for holistic software development, but its behavioral evaluation measures only a finite, input-output-based slice of executable correctness. The authors identify richer test generation and system-constraint evaluation as future directions.

  • Limitations: Finite behavioral tests make ProgramBench a lower bound on correctness: failures establish incorrectness, but passing solutions may diverge on untested inputs.The limitation follows from under-approximating each executable’s full specification.
  • Limitations: The benchmark currently evaluates input-output equivalence, not execution speed, memory usage, or disk footprint.A behaviorally matching implementation could therefore be much slower or more resource intensive than the original.
  • Future work: Future work includes richer test-generation strategies that improve coverage and incorporate system constraints.This is presented as a direction for addressing the benchmark’s current evaluation scope.
  • Conclusion: ProgramBench is intended as a testbed for efforts focused on end-to-end autonomous software development, while the reported analyses expose gaps in architecture, development, and testing decisions.The conclusion also reports meaningful partial progress despite no task being fully resolved.

A.1 Task Collection Procedure

The task-collection procedure includes agent-based construction and test-generation steps under explicit constraints designed to prevent shortcut solutions. Early trials showed that internet access and executable access could let agents clone or wrap the reference rather than reconstruct its behavior.

  • Collection and evaluation setup: The mini-SWE-agent used for executable construction, test generation, and implementation-detail removal may take as many steps as needed, with a maximum $3 total cost per run.The three steps together have a $9 total cost allowance.
  • Collection and evaluation setup: Building the executable is typically the costliest step because agents read build hints and may need to identify and install missing dependencies.README.md, CONTRIBUTING.md, and workflow files can provide compilation clues.
  • Collection and evaluation setup: All task instances use an Ubuntu 22.04-based image with Rust 1.92.0, Python 3.12, Go 1.21.0, and C/C++ toolchain support, without task-specific installations.The environment also provides git and tmux.
  • Constraints: Early trials found that unconstrained agents could exploit full internet access or executable read/write permissions through undesirable shortcuts.The constraints were introduced to reduce spurious solution techniques.
  • Constraints: With internet access, Claude Opus 4.5 could infer a repository from executable help output and shallow-clone its source instead of reconstructing the program.This made the implementation effort largely trivial and uninformative for the benchmark’s research questions.
  • Constraints: Another observed shortcut was submitting a wrapper around the reference executable, which the benchmark’s constraints are designed to mitigate.The passage describes this as infrequent but still observed before mitigation.

A.2.2 Early Mitigation Attempts

Early internet-enabled evaluations used LM judges to detect cheating, but widespread violations and substantial disagreement made post-hoc enforcement unreliable. The benchmark therefore moved toward restrictive environment controls, including no internet access and removal of implementation-revealing artifacts.

  • Cheating detection: 20–36% of tasks were flagged for the three stronger models, with source code lookup accounting for most violations.Models cloned repositories, installed projects, or read cached dependency source.
  • Cheating detection: Fleiss’ κ ranged from 0.16 to 0.60, with pooled κ of 0.57 across 786 annotated tasks.Judges disagreed on 16–57% of tasks, with the highest disagreement for Claude Opus 4.6.
  • Cheating detection: Dependency-source access created a central ambiguity because judges differed over whether cached third-party code constituted source lookup.A handlr example produced a 5–4 split, while API documentation produced a separate 4–5 split.
  • Mitigation measures: The benchmark restricted executable permissions, removed original binaries and build artifacts, and wiped Git history to reduce reverse engineering and wrapping loopholes.These measures were designed to prevent decompilation, thin wrappers, and implementation leakage.
  • Mitigation measures: Because internet access and post-hoc detection became a cat-and-mouse game, no internet access became the default evaluation restriction.The authors state that more capable models developed ways around increasingly specific prohibitions.

A.2.4 On the Feasability of ProgramBench

ProgramBench is deliberately difficult but designed to remain solvable because models can observe deterministic executable behavior. Its scope excludes inherently network-dependent programs, while testing emphasizes broad behavioral exploration rather than source-level conformity.

  • Solvability: An average ProgramBench task instance could take an individual or team days, weeks, or months to complete.This estimate is based on development history, codebase size, and functionality range rather than a formal human study.
  • Solvability: Every test asserts observable, deterministic executable behavior that models can probe by running the accessible reference program.Alternative implementations and languages remain feasible in principle because evaluation targets input-output behavior.
  • Solvability: Behavior discovery is a core challenge: models may miss undocumented flag and input combinations even when those behaviors are technically discoverable.The benchmark therefore tests systematic exploration and attention to boundary conditions.
  • Solvability: The authors reviewed all 200 repositories and found that important interfaces were generally exposed through documentation, help output, or man pages.They treat entirely unobservable functionality as defective software-engineering practice.
  • Scope constraints: 18 task instances are networking utilities that retain loopback access, allowing protocol and CLI behavior to be tested without remote internet connectivity.Tasks inherently requiring web endpoints were excluded from the benchmark.
  • Scope constraints: Behavioral tests mostly require models to generate their own inputs, although selected obscure assets are extracted and supplied.Popular standardized text formats are not provided, preserving the expectation that workers create representative files.
  • Evaluation design: Skeleton-based evaluations constrain free-form solutions because tests often depend on expected signatures and implementation-focused unit tests.ProgramBench addresses this gap with executable-level behavioral checks, while existing repositories frequently lack sufficient end-to-end tests.
  • Evaluation design: 141 of 200 task instances have tests, but 59 have no existing test suite and most existing suites focus on implementation-level unit testing.Additional generated tests are therefore needed to evaluate executable behavior consistently.

A.3.2 Analyses

The analyses compare test-generation strategies, test provenance, assertion quality, and behavioral baselines. Coverage-guided generation produces the largest and deepest suites, while quality checks make tests substantially harder to pass.

  • Test-generation analyses: Coverage-guided iterative generation produced a median of 750 tests per task and median line coverage of 86.2%.Its mean line coverage was 79.7%, compared with 27.8 and 51.7 average tests for monolithic and decomposed strategies.
  • Test-generation analyses: 79.5% of tests are self-generated, while 20.5% are harvested from existing repository suites.The pipeline combines generated tests with executable-behavior tests found in source repositories.
  • Test quality: Assertion-quality feedback reduced mean dummy pass rate from 18.5% to 3.7%, a 5× reduction.Across four frontier models, the resulting tests were 20–30 percentage points harder to pass.
  • Coverage methodology: Coverage is measured by merging active generated branches and running them against coverage-instrumented original binaries.The methodology reports first-party line coverage while excluding system headers, vendored dependencies, and generated code.
  • Behavioral baselines: The behavioral baseline uses twelve hard-task repositories with identifiable application-level behavioral or integration suites.The selected suites cover interpreters, media tools, CLIs, databases, documentation fixtures, and regression harnesses.

A.3.3 Test Examples

The generated examples test executable behavior through realistic command-line workflows, including script arguments, database queries, multimedia streaming, and archive corruption detection. These cases assert outputs, files, headers, or integrity outcomes rather than internal implementation details.

  • zstd: zstd tests --test on compressed random bytes, flips one byte in the archive, and checks that corruption is detected.The example targets archive-integrity verification without requiring decompression output.
  • PHP: PHP tests script execution with -n and -f, verifying argument count and preservation of a space-containing argument.The test separates interpreter flags from script arguments with --.
  • DuckDB: DuckDB tests CSV import followed by a filtered query, asserting that only the matching row appears in output.The workflow exercises the CLI’s .import command and SQL filtering behavior.
  • FFmpeg: FFmpeg tests generate a WAV stream, pipe it through stdin with stream-copy, and assert SHA-256 equality.The first invocation uses lavfi to synthesize audio; the second reads stdin with -i - and -c copy.

A.3.4 On Test Overspecification

ProgramBench treats the gold executable as the complete specification, using deterministic observable behavior rather than source-level structure for evaluation. Audits found few plausible overspecification risks, while linting targets weak assertions that can accept incorrect implementations.

  • Behavioral test design: ProgramBench tests compare observable executable behavior, including output, exit codes, and filesystem changes, rather than source-level internals.This prevents assertions about variable names or method definitions and allows different languages, algorithms, and architectures.
  • Behavioral test design: The gold executable serves as the complete specification, so any deterministic, observable behavior may be tested if the model can discover it by execution.Nondeterministic tests are filtered by repeated runs against the reference executable.
  • Overspecification audit: Five of 200 task instances plausibly expose overspecification through floating-point precision, hash or map iteration order, or rendering discretization.Manual inspection found their tests mainly checked CLI flags, file formats, and string output rather than implementation-dependent numerical results.
  • Assertion linting: Weak assertions can pass trivially incorrect implementations by checking only exit codes, short substrings, content length, swallowed exceptions, or alternative outputs.Table 8 distinguishes HIGH rules, likely to pass incorrect implementations trivially, from MED rules, which are weak but not necessarily vacuous.

A.4 Dataset Statistics

ProgramBench spans software repositories with substantial variation in size, structure, dependencies, community history, and functionality. Its difficulty score combines code size and runtime dependencies, and observed pass rates decline monotonically from Easy to Hard.

  • Repository size: The median repository contains 93 total files, 50 code files, and 8,635 lines of code, while FFmpeg has 4,566 code files and PHP has 1.97 million lines.These statistics position ProgramBench at a substantially larger implementation scale than existing benchmarks.
  • Repository structure: Repositories are generally shallow, with median maximum depth 3 and 13 directories, but depths reach 13 and C/C++ projects have a median of 32 directories.Three repositories are flat, whereas gromacs contains over 850 directories.
  • Dependencies: Among 200 repositories, 171 contain recognized manifests; those repositories declare a median of 17 total dependencies, including 12 runtime dependencies.Twenty percent have 16–30 dependencies and 11% have more than 30.
  • Functional diversity: The dataset covers 14 functional categories across 200 repositories, led by text-processing CLI utilities with 31 tasks and file or disk operations with 26.It also includes interpreters, compression utilities, security tools, databases, and developer tools.
  • Difficulty: Difficulty is scored from lines of code and runtime dependencies on a 0–10 scale, with Easy below 2, Medium from 2 to below 4, and Hard at least 4.For every model, average test pass rates decrease monotonically from Easy to Hard.

B.2 Further Findings

Across ProgramBench runs, models usually achieve partial rather than near-complete reconstruction, with performance shaped by reference language and model-specific behavior. More interaction steps do not reliably produce higher scores, and solutions remain shorter than references.

  • Overall performance: The median pass rate is 32%, while fewer than 5% of runs exceed 90% and roughly 18% fall in the 0–5% bin.The distribution indicates frequent failure to make meaningful progress alongside broad partial progress and rare near-perfect reconstructions.
  • Reference-language effects: Average pass rates are 38.5% for Rust, 38.4% for Go, and 27.7% for C/C++ tasks.C/C++ medians are 15–20 percentage points below Go for even the strongest models.
  • Compute and performance: API calls and cost correlate weakly with pass rate, with Pearson correlations of r=0.27 and r=0.21 respectively.High-scoring runs occur across turn counts and cost levels, while expensive runs can still score near zero.
  • Compute allocation: Model trajectory lengths differ by over an order of magnitude: GPT models finish 90% of tasks within 25 steps, while Sonnet 4.6 has a median of 443 steps.These differences coincide with weak score-versus-turn correlations and appear to reflect interaction styles rather than higher-scoring strategies.
  • Language choice: Models show distinct implementation-language preferences, with GPT 5.4 using Python in 79% of runs and Sonnet 4.6 distributing choices across several languages.Under the different-language constraint, models largely avoid the reference language and default to Python.
  • Code size: For solutions passing at least 75% of tests, all models have below-parity code-size ratios, with medians from roughly 0.15 to 0.35.The gap is largest for C/C++ references, whose median ratio is around 0.2, and smallest for Rust at around 0.5.
Loading 2605.03546v1…