Overview
A coding model can try the same problem dozens of times and still produce nothing that works. Give it a fixed budget across many problems and another question arises. Which problem should get the next attempt? EFFICODE uses signals from code the model has already generated to move attempts among problems and to stop some snippets before they finish. The experiments ask how many attempts a system needs to reach a given test pass rate.
Key Findings
A hundred attempts can be spent in different ways
Imagine a coding assistant facing a pile of bug reports. Some yield quickly. Others absorb one near-identical failed attempt after another. A uniform sampler gives every problem the same allowance. EFFICODE instead allocates a shared average budget across problems. It shifts attempts toward unsolved problems that the model appears able to solve, while still sampling among candidates when the signals are uncertain.
Learn where another attempt might pay off
The first signal is a history of syntax errors. The second measures how closely sampled code resembles correct code for previously solved problems, using CodeBLEU. The comparison includes the high-level plans produced by Self-planning prompting as well as the code. Each signal gives a problem a priority value. The system samples the next problem with a probability proportional to the smaller of those two priorities. If and denote those values, Equation 8 is
Taking the minimum keeps one promising signal from overwhelming the other. Both are indirect measurements of solvability, and neither checks what a program actually does. Section 4.2 and Equation 8
Stop a dead-end draft before paying for the rest
The second intervention takes place inside a single generation. The sampler periodically asks a compiler whether the partial program is already irreparably malformed. An incomplete expression at the end can still become valid, so the method exempts errors that a continuation could repair. When it identifies an error that will persist, it stops decoding that sample. This saves generation work without treating a successful parse as evidence of functional correctness.
Distinguish finding a working program from selecting it
Pass@ asks whether at least one of candidates solves a problem under the tests. The efficiency comparison in Figure 4 asks how much sampling budget is needed to reach a target pass rate. On CodeContests-Extreme, the paper reports using 16% less sample budget to reach the uniform-sampling Pass@100 result. The study’s extreme subsets use a preliminary solve ratio below 10% and contain 151 CodeContests, 22 HumanEval, and 89 MBPP problems.
Submitting one program from a pool of 100 is a different task. The table reports how often a problem is solved with one or two selected programs, using GPT-3.5-turbo-0301 with Self-planning. One solved HumanEval-Extreme problem changes the score by about 4.5 percentage points. Table 2
| Benchmark | Selection | One program | Two programs |
|---|---|---|---|
| HumanEval-Extreme | None | 2.0% | 3.9% |
| HumanEval-Extreme | EFFICODE | 4.6% | 9.1% |
| MBPP-Extreme | None | 1.4% | 2.7% |
| MBPP-Extreme | EFFICODE | 4.5% | 4.5% |
| CodeContests-Extreme | None | 0.3% | 0.6% |
| CodeContests-Extreme | EFFICODE | 1.3% | 2.0% |
Questions & Answers
Q: Does the method need the hidden tests to choose where to sample?
A: The allocation and ranking described here use syntax and similarity signals. Hidden tests are used to measure the correctness of generated programs during evaluation. The similarity component uses correct code from previously solved problems. The CodeContests log comes from ten samples per validation problem. HumanEval and MBPP each use the other benchmark for this log.
Q: Is 16% the expected runtime saving for another coding service?
A: It is the reduction in the sample budget for a specific target on CodeContests-Extreme. Runtime depends on how much code each attempt generates and how expensive it is to check a prefix. A service would measure tokens, elapsed time, and successful tasks together.
Q: Could the scheduler neglect a difficult problem it would otherwise solve?
A: Yes. A weak estimated solvability can reduce a problem’s share of attempts. Aggregate pass rate can improve while some problems receive too little exploration. A service should track solved problems by difficulty and measure which cases lose coverage.
Q: How much should we generalize from the extreme difficulty subsets?
A: The subsets are defined using preliminary performance, and HumanEval-Extreme contains only 22 problems. A small change in the number solved can move the percentage substantially. Keeping the same split for different schedulers and tracking their effect on the full difficulty range would give a clearer result for a different service.
Future Ideas
A retry scheduler for code repair queues
A continuous-integration service often has several failing changes waiting for a repair attempt. Give each change a small initial budget, then use syntax recovery and similarity to previously verified repairs to route remaining attempts. Use tests and compiler results as the acceptance gate. Run the scheduler in shadow mode on historical failures before letting it affect a live queue.
Compare it with uniform allocation and with an allocation based only on the failure type. Measure verified repairs per fixed token budget and time to first verified repair. Reserve some attempts for jobs with no useful historical match and report their repair rate separately. Move beyond the shadow trial only if the overall gain survives that coverage check.
Factor the syntax filter and budget scheduler into separate test arms. Of the prefixes the filter would discard, record how many eventually produce verified repairs under a matched uniform budget.
Sources
- EMNLP 2023 Industry Track paper and bibliographic record
- Published PDF, including Figures 2–4 and Table 2
Original abstract
Large language models often struggle to predict runtime behavior in code generation tasks, leading to a reliance on rejection sampling (best-of-n) to generate multiple code snippets then select the best. Our distinction is reducing sampling costs, without compromising generation quality. We introduce EFFICODE, a novel framework that prioritizes sampling on test problems that models can solve. We show how EFFICODE estimates solvability to optimize computational costs during multiple sampling. Based on empirical evidence, EFFICODE consistently demonstrates reduced sampling budgets while maintaining comparable code generation performance, especially when problems are challenging. In addition, utilizing EFFICODE to rank sampled code snippets also shows its effectiveness in answer code selection for reducing temporal costs, by not requiring any execution or test case generation.