Black-Box Program Reconstruction Evaluation: How High Reasoning Budgets Improve Long-Horizon Decisions

1. Problem Definition: The Hard Part Is the Behavioral Space, Not Writing Code

In conventional software development, developers usually have source code, dependency manifests, build scripts, and debugging information. In black-box program reconstruction evaluations, however, an agent receives only a compiled executable and a specification document. The evaluation system does not provide source code, prohibits decompilation of the executable, and cuts off network access. The model must rely entirely on its own designed probing methods to explore and recover the program’s input-output patterns, state changes, boundary conditions, and exception behavior, and ultimately reconstruct a program that compiles, runs, and passes behavioral tests.

At first glance, this task looks like “writing code,” but the real difficulty lies in probing and modeling the behavioral space. A program may contain many implicit states, nondeterministic outputs, resource limits, error-code branches, and boundary conditions. If the model implements only a surface-level version based on the documentation, it may pass a small number of tests on normal paths while failing on exception paths, combined inputs, and edge cases. Therefore, black-box program reconstruction tests the ability to infer internal contracts from observable behavior, not merely syntax proficiency.

From an engineering perspective, this process involves at least four types of decisions: first, which implementation language and runtime form to choose; second, how to design probe inputs that cover the functional surface; third, how to record and summarize behavioral contracts; and fourth, how to generate build scripts and reproduce results stably in an isolated environment. Each decision affects subsequent test pass rates, and these decisions often cannot be made correctly in one pass. They require multiple rounds of hypothesis, validation, and rollback.

2. Evaluation Design: Turning the Invisible into Repeatable Experiments

The core design of black-box program reconstruction evaluation is to turn invisible program behavior into repeatable experiments. The evaluation environment typically needs network isolation, resource quotas, read-only mounts, runtime log collection, and result snapshot preservation. This prevents the model from bypassing reconstruction through external information and ensures that the same submission produces consistent results across different runs. In engineering practice, general-purpose capabilities such as the Baidu AI Cloud container platform, object storage, and log services can be used to build a reproducible evaluation environment and result archiving workflow.

The acceptance mechanism typically uses agent-driven fuzzing technology to generate large numbers of targeted behavioral test cases. The original evaluation covers 200 real tasks of varying complexity and generates more than 248,000 behavioral test cases for all tasks. A submitted program is considered solved only if it passes the entire test set for the corresponding task perfectly; even a tiny deviation in a single edge-case test causes the whole task to fail. This “all-pass” criterion is very strict, and it distinguishes “basically usable” from “behaviorally equivalent.”

An illustrative evaluation flow can be abstracted as:

def evaluate(candidate, cases):
    for case in cases:
        actual = run_isolated(candidate, case.input)
        if not match(actual, case.expected):
            return FAIL
    return PASS

Here, run_isolated needs to limit network, time, memory, and file system access; match needs to handle observable results such as standard output, exit codes, file side effects, and error messages. For nondeterministic outputs, normalization rules also need to be defined to avoid misclassifying reasonable variation as failure.

3. Task Spectrum: From Small Tools to Complex Systems Across the Engineering Chain

The task spectrum in this type of evaluation usually spans a wide range. It ranges from small terminal text processing tools and search tools to large compilers, multimedia processing frameworks, and relational databases. Different task scales bring different difficulties: small tools place more emphasis on boundary conditions and parameter combinations, while large systems place more emphasis on architectural decomposition, state management, build pipelines, and performance trade-offs.

Facing different software forms, the model needs to evaluate and decide which programming language to use, build the underlying system architecture itself, hand-write source code across all logic dimensions, and produce usable build and compilation scripts. Key software engineering design decisions all depend on the model’s own judgment and trade-offs. For example, should it prioritize a complete functional surface or first ensure stability on core paths? Should it use a simple single-process structure or split modules to reduce complexity? Should it reduce external dependencies to improve portability or introduce common components to shorten the implementation cycle? These trade-offs have no standard answers and can only be corrected through continuous feedback from behavioral tests.

4. The Value of High Reasoning Budgets: Thinking Space for Long-Horizon Decisions

In public evaluation records, performance under a medium reasoning budget is often limited and close to lightweight approaches. When the reasoning budget increases, the model can devote more computation to behavioral hypotheses, probing plans, failure attribution, and reconstruction iterations. Black-box reconstruction is a typical long-horizon task: one probe result may overturn a previous hypothesis, and one boundary-case failure may require rewriting a state machine. The value of a high reasoning budget is that it lets the model maintain a more complete hypothesis table, generate more targeted probe inputs, and locate specific behavioral differences after failures.

Public records show that the high-reasoning-budget mode was the first to achieve a full pass on all behavioral tests for a single instance of a small terminal animation program, and it increased the number of near-solved tasks to 26. Here, “near-solved” usually means a behavioral test pass rate above 95%. The full cumulative score histogram also shows that the high-reasoning-budget approach performs better across different thresholds such as average score, median, 90% pass rate, and 50% pass rate. It is important to note that a single-instance full score shows that the upper limit has been opened, while 26 near-solved tasks show an overall improvement in the distribution. Taken together, these two observations are more informative than looking only at one highest score.

A high reasoning budget is not an unlimited improvement. Reasoning cost, latency, and stability all need to be considered in engineering. A more reasonable approach is layered use: first use a lower budget for rapid probing and skeleton generation, then increase the budget on key failure points for deep attribution; at the same time, add early stopping, caching, and regression case reuse to avoid repeated thinking.

5. Engineering Lessons: Best Practices for Building Black-Box Reconstruction Capability

First, probe before coding. Do not rush to write a complete implementation. Instead, construct a minimal input set, observe outputs, exit codes, and file side effects, and form a behavioral contract table. Second, establish differential testing. Repeatedly compare the candidate implementation with observed behavior using the same set of inputs, prioritizing exception paths and boundary conditions. Third, maintain minimal reproducibility. Each failure case should be able to run independently and record the environment, input, and expected output. Fourth, build scripts should be portable. Reduce unnecessary dependencies and clearly define compilation parameters and the runtime entry point. Fifth, value logs and auditing. Runtime logs, resource usage, and failure stacks in the evaluation environment are key evidence for later attribution. Sixth, prevent evaluation overfitting. Test cases should cover normal, exception, combined, and resource-limit scenarios, rather than patching only against known cases.

6. Risks and Boundaries

Black-box reconstruction evaluation must respect compliance boundaries: decompiling executables is prohibited, and obtaining external information through the network is prohibited. The evaluation environment must be securely isolated so that candidate programs cannot affect the host machine. For nondeterministic outputs, clear normalization rules must be defined; for resource-intensive tasks, time and memory limits must be set. Although high reasoning budgets can improve performance on complex tasks, they also increase cost, so budget layering should be combined with business scenarios. Finally, evaluation conclusions should be understood as capability observations under a specific benchmark, not as absolute guarantees for all real-world engineering tasks.