Tests Turn Prompting into Search

The evaluation is the objective

Suppose a coding task begins with an initial prompt and a set of developer tests. A base language model produces code, and the code receives a score from the fraction of tests it passes. We want a revised prompt that raises that score while trying as few prompts as possible.

The search is hard for two reasons. Prompts are discrete sequences drawn from a huge combinatorial space, and every candidate is expensive: it requires model inference followed by program execution. Randomly rewriting the prompt wastes the information contained in previous trials. Bayesian optimization is useful because it maintains a probabilistic model of that history and chooses the next candidate by balancing promising regions against uncertain ones.

Searching without losing language

Standard Bayesian optimization works most naturally in a continuous, low-dimensional space. Natural-language prompts are neither. BODE-GEN bridges that mismatch with an auxiliary Llama 2 model: optimization happens over continuous input embeddings, while the auxiliary model decodes each candidate back into an interpretable text prompt for the base code model.

The raw search point contains four 4,096-dimensional embeddings. Random projections reduce each one to 64 dimensions, producing a 256-dimensional search space. A Gaussian Process surrogate with dimensionality-scaled priors models prompt quality, and Expected Improvement chooses among 10,000 candidate points at each iteration.

The loop

1. Choose a candidate embedding with Expected Improvement.
2. Combine it with the original prompt and a fixed rewriting instruction.
3. Use the auxiliary model to decode an interpretable candidate prompt.
4. Ask the base model for code and execute that code against the tests.
5. Return correctness to the surrogate model and repeat.

history = []
for candidate in optimizer:
    prompt = auxiliary_llm.decode(candidate, initial_prompt)
    code = base_llm.generate(prompt)
    score = run_tests(code)
    history.append((candidate, score))
    optimizer.update(history)

The important detail is that the optimizer never evaluates whether a prompt sounds more sophisticated. It only sees whether the resulting program works.

What I built

My contribution centered on the test-driven evaluation infrastructure. I built the pipeline that generated programs, executed them against the expanded HumanEval+ tests, aggregated correctness, and supported repeatable comparisons across the three base models and prompting baselines.

That work made a mundane point feel concrete: an optimization method is only as credible as the evaluator underneath it. A malformed generation, inconsistent harness, or nondeterministic comparison can look like an optimization gain. The experiment pipeline is not plumbing around the research result; it is part of the result.

Experimental setup

We evaluated all 164 Python tasks in HumanEval+. Compared with the original HumanEval, the benchmark expands the test suites by roughly 80 times, making it harder for superficially correct programs to survive evaluation.

The base models were ChatGPT-3.5 Turbo, CodeLlama-7B, and DeepSeek-Coder-33B. Each prompt produced three code samples for pass@1-style evaluation. The optimizer began with 20 randomly selected embedding points, then ran for 50 Bayesian optimization iterations across five seeds. The baselines were the initial HumanEval+ prompt, zero-shot Chain-of-Thought, and OPRO, an iterative LLM-driven prompt optimizer.

Results

The table reports the share of HumanEval+ tasks solved to full test-suite correctness. BODE-GEN improved over the initial prompt and OPRO for all three base models in our setup.

The search often found meaningful gains within the first 20 to 30 iterations and approached its best observed performance by iteration 50. The advantage over the baselines also grew on tasks where the initial prompt performed poorly. That matters because easy tasks leave little room for any optimizer to demonstrate value.

What optimized prompts changed

We manually examined 15 tasks with substantial correctness improvements. The optimized prompts did not converge on one magic phrase. They repeatedly made the task easier to parse:

• Examples became visible. Inputs and outputs were separated from dense docstrings.
• Instructions became explicit. Short requirements were expanded into plain-language descriptions.
• Structure improved. Assumptions, constraints, and examples were placed in distinct sections.
• Edge cases were named. The prompt made hidden conditions harder for the model to overlook.
• Tasks were decomposed. Multi-step behavior was described in the order the program needed to implement it.

These observations are useful, but they are not a causal proof that any one pattern produces the gain. The optimizer changes several aspects at once. The tests tell us which complete prompt worked, not which sentence deserves credit.

What the results do not say

HumanEval+ is a controlled benchmark, not a production codebase. Its function prompts and unit tests give us a clean objective, but real software tasks carry repository context, integration constraints, and requirements that are much harder to encode in one score.

The method also depends on having useful tests. If the test suite misses an important behavior, optimization can confidently select a prompt that exploits that omission. Better search does not repair a weak objective.

Finally, sample-efficient does not mean free. Each candidate still requires multiple generations and program executions, and model behavior remains stochastic. The experiments show that this search worked for the selected models and benchmark; they do not guarantee the same margin for newer models or arbitrary software tasks.

The broader lesson

Optimization does not rescue a bad evaluator. It amplifies it.

The most interesting part of BODE-GEN is not that Bayesian optimization can rewrite a prompt. It is that executable feedback changes what prompting can be. Without tests, revisions are judged by taste or a proxy model. With tests, each trial becomes evidence, and the history of failures can guide the next search decision.

I now think of evaluation as part of the learning system rather than a final report card. The same principle appears in agents and robotics: the behavior we can improve is constrained by the feedback we can measure. Better optimization helps only after that feedback represents what we actually care about.