When a language model writes code and the code fails its tests, the system has three sensible moves. It can show the model the error and ask for a fix. It can throw the attempt away and draw a fresh sample. Or it can give up on the problem because further spending is unlikely to pay off. Today's systems make this choice once, in advance, and apply it the same way to every problem. S* always runs two debugging rounds per candidate. RLEF always allows the same fixed number of turns. Parallel-sampling pipelines never debug at all. This proposal builds a small, cheap decision module that makes the choice after every test run. It reads what the test harness actually reported: a missing import, a crash on an edge case, a wrong answer on half the tests, or a timeout. From that report it estimates which move buys the most expected success per token spent. The question is whether treating these execution reports as the main signal for allocating compute can match the accuracy of the best fixed pipelines at a fraction of the cost.
The opportunity matters because the literature currently disagrees about where code-generation compute should go. Formalizing Test-Time Compute for Function-Level Code Generation finds that iterative self-debugging saturates after one round and loses to high-temperature parallel sampling. S*: Test Time Scaling for Code Generation and RLEF report large gains from debugging grounded in execution feedback. Our hypothesis is that both are right, but for different kinds of failures. A per-failure decision rule should therefore beat both fixed strategies. The same measurements should also explain the disagreement by showing which failure types reward refinement and which reward fresh samples.
Core Claim
The marginal value of one more unit of compute in a code-generation loop depends strongly on the content of the most recent execution report, not just on how hard the problem looked at the start. A predictor of marginal gain that uses only black-box features can drive per-turn choices among five actions: stop, refine with a short reasoning budget, refine with a long reasoning budget, resample from scratch, or abandon. Those features are the problem text, the current code, the structured test report, and the history of previous reports. We claim such a predictor will trace an accuracy-versus-compute curve that dominates the curves of fixed-schedule refinement, fixed-budget parallel sampling, and allocators that decide budgets once before any code runs.
Concretely, let $s_t$ be the state after the $t$-th execution: the problem, the current best candidate, and its test report. Let $c(a)$ be the expected token cost of action $a$, and let $\hat g(s_t, a)$ be the predicted probability that $a$ yields a candidate passing all public tests at the next execution. The policy is
$$ a_t = \arg\max_{a} \frac{\hat g(s_t, a)}{c(a)} \quad \text{if } \max_a \frac{\hat g(s_t,a)}{c(a)} \ge \lambda, \text{ otherwise abandon,} $$
where $\lambda$ is a single scalar that sets the price of compute. Sweeping $\lambda$ traces the whole cost–accuracy curve with one trained predictor. The form comes from the threshold rule that Adaptive Generate-Rank-Verify proves optimal when success probabilities are known. Here those probabilities are estimated from execution content rather than from a scalar reward score.
Relation to Prior Work
Three lines of work supply the allocation idea but are blind to execution content. Learning How Hard to Think trains a predictor of marginal reward per extra best-of-$k$ sample and halves sample counts on math and code. The LLM Already Knows probes the hidden state before generation to decide whether to invoke Self-Refine or Best-of-N. Both make a single decision before any code has run, and the second needs access to the model's internal activations. We borrow their marginal-gain formulation but re-estimate after every execution, using only externally visible signals.
ADAP, from Adaptive Generate-Rank-Verify, is the closest work. It grows a pool of independent samples geometrically and decides what to verify from reward-model scores. Its search is purely parallel, ignores error text, and assumes the reward model ranks candidates monotonically. That assumption fails with noisy verifiers. We add the sequential refine action and condition on execution content. OSCA learns a static mix of sampling configurations per dataset, which is complementary: its portfolio could serve as our resample action.
The refinement line supplies the environment and constrains the design. S* and RLEF show that feedback-grounded debugging can be powerful but apply it uniformly. Improving Code Efficiency with Iterative Refinement (ICER) shows two things that shape our design. First, strict acceptance rules overfit to visible tests. Second, asking models to label Big-O complexity injects noise. For both reasons we do not ask the generating model to self-assess, and we keep public-test and hidden-test signals strictly separate. TGPR moves search entirely to training and runs a fixed single pass at inference. We take the opposite stance and test whether flexible inference-time spending is worth its overhead.
Dynamic inference-time scaling enters through the short-versus-long reasoning budget on refine actions. DRQA and ReBalance show that reasoning models over-think and under-think, and that controlling reasoning length saves 30–52% of tokens without hurting accuracy. Neither conditions that control on external feedback. We deliberately do not use per-token internal compression of the kind in Compute Where it Counts. That work shows early compression damages the stored attention cache for later tokens, and the file notes that FLOP savings from such methods often fail to appear as wall-clock speedups. Reasoning-length control is the dynamic-compute knob that survives batching and reaches real latency.
Research Program
The first stage is a measurement study, which is useful even if the learned policy fails. On training problems we run a branching rollout procedure. Starting from several initial samples per problem, we execute against public tests at every reached state and run each action several times. We record pass outcomes, token costs, and the resulting states. From these rollouts we build a "gain map": the empirical success-per-token of each action, broken down by failure type. The failure types are syntax or compile error, runtime exception, wrong answer with a given fraction of tests passing, timeout, and repeated identical failure. This directly tests whether the saturation result of Li et al. and the gains reported by S* come from different mixes of failure types.
The second stage trains the predictor $\hat g$. It uses two parts: a gradient-boosted model on structured features (error class, fraction of public tests passed, turn index, whether the error string repeats, code length, problem length), and a small fine-tuned text encoder over the problem and the truncated error report whose output feeds the boosted model. The predictor never reads the generating model's activations, so it works with API-only models. It is trained on the rollout data from stage one.
The third stage is the policy above. It uses a fixed per-problem token ceiling and, as the final answer, the last candidate passing all public tests. If no candidate passes, it selects among candidates with the input-synthesis selection from S*, so that the selection method is held constant against our strongest baseline.
Two design choices guard against known failure modes. First, the train/test split is temporal: older LiveCodeBench windows plus the CodeContests training split for training, and later windows for testing. This directly probes the distribution-shift weakness that ADAP's authors attribute to supervised difficulty predictors. Second, we track public-pass/hidden-fail rates separately to detect the visible-test overfitting ICER warns about.
Baselines
The naive reference point is greedy single-sample generation with no execution. It anchors the cost axis at one call and shows how much any test-time compute helps.
The strongest existing method is S. It samples candidates in parallel, debugs each for two rounds against public tests, and selects with synthesized discriminating inputs. On LiveCodeBench it lifts DeepSeek-R1-Distill-Qwen-32B from 69.1% to 85.7% pass@1, and GPT-4o-mini with S reaches 61.3% (S*). We rerun S* with its published two-round schedule on the same models, test windows, and public/hidden test split, and with the same selection stage, recording total generated tokens and execution calls. Beating it means one of two things: matching its hidden-test pass@1 within one point at no more than half its token cost, or exceeding it by at least two points at equal cost, measured on the temporally held-out window.
The strongest parallel-only competitor is high-temperature sampling with execution-based reranking, following Formalizing Test-Time Compute. On HumanEval+ this approach raises CodeLlama-7B from 39.0% to 72.0%; no reported result was found on Lacuna for this method on LiveCodeBench. We run it with temperature tuned on the training window, early-stopped once a sample passes all public tests, and swept across sample budgets to give a full curve.
The strongest adaptive allocator is ADAP, which Adaptive Generate-Rank-Verify reports as 5.5x cheaper than the best fixed-budget policy on LiveCodeBench at 100% success on solvable problems. We run it with the same generator and a code reward model, charging execution calls at the same rate as in our system.
We also run the a priori allocator of Learning How Hard to Think. It sets a per-problem budget before generation, then uniformly runs S*-style debugging within that budget. It is trained on the same calibration problems, giving it the same supervision we have.
Three ablations isolate the key ingredient. A category-only rule removes the learned predictor and maps each error type to its best action from the gain map. A no-content predictor sees turn index, pass fraction, and cost but no error text or failure type. A no-abandon variant tests how much savings come from giving up on hopeless problems. An oracle allocator, which picks actions with hindsight from the rollouts, bounds what any policy could achieve.
Why not just…?
Why not just use a hand-written rule: fix syntax and runtime errors, resample on wrong answers, stop on pass? This is the most serious threat, and we take it seriously enough that the category-only rule is a headline baseline rather than a footnote. The rule cannot detect within-category variation: a wrong answer on 9 of 10 tests is very different from 0 of 10, and the third identical crash is very different from the first. It also cannot price abandonment. If the learned predictor fails to beat the rule by a clear margin on the held-out window, we will report the rule, together with the gain map that justifies it, as the contribution. That would be a cheap and useful result in its own right. The gap between the rule and the oracle allocator tells us how much room was ever available.
Why not just spend everything on parallel samples with early stopping, given that self-debugging saturates after one round? Li et al.'s evidence is averaged over failure types and comes mostly from function-level benchmarks where many failures are shallow. The S* and RLEF results show that the averaged picture does not carry over to harder problems. The gain map tests this directly. If resampling dominates refinement in every failure category, our policy will learn to resample, will collapse onto this baseline, and the claim is falsified.
Why not just train the generator with reinforcement learning to decide for itself when to stop, as RLEF and TGPR train refinement behavior? That approach ties the allocation to one set of model weights, needs a costly training run per model, and is impossible for closed-weight models. RLEF still runs a fixed turn limit, and TGPR runs a fixed single pass. An external predictor can be reused across generators. We test this by training it on rollouts from one model and evaluating it on another. If cross-model transfer fails badly, that is evidence the decision belongs inside the model.
Why not just predict difficulty once, up front, and set the budget? Execution feedback reveals information the problem text cannot. A problem that looked easy can produce a deep logic error, and one that looked hard can fail on a typo. The a priori allocator baseline isolates exactly this. Our ablation that freezes the predictor's input at turn zero measures how much accuracy per token comes from re-estimating after each execution.
Proposed Experiments
The main evaluation is on LiveCodeBench code generation (LiveCodeBench), with problems split by release date so the predictor is tested only on problems published after its training data. CodeContests serves as a harder secondary set, and HumanEval+ and MBPP+ provide an easy-skewed regime where most savings should come from stopping early. The generators are Qwen2.5-Coder-7B-Instruct, DeepSeek-R1-Distill-Qwen-7B and 32B (whose reasoning length makes the short/long refine actions meaningful), and GPT-4o-mini through its API to demonstrate black-box use.
The primary metric is hidden-test pass@1 of the final answer, plotted against total generated tokens per problem, with execution calls reported alongside. Secondary metrics are wall-clock latency under batched serving, the rate at which candidates pass public tests but fail hidden ones, and the precision and recall of abandon decisions against problems the oracle never solves.
Four decisive checks would confirm or kill the idea. First, the gain map should show that the best action differs systematically by failure type. If one action dominates everywhere, the premise is false. Second, the learned policy should beat the category-only rule on the temporally held-out window. If it does not, the simple rule is the result. Third, at matched tokens, the policy should beat S*, ADAP, and tuned parallel sampling, and the margin should survive the temporal shift rather than appear only on in-distribution problems. Fourth, the short/long reasoning action should account for a measurable share of savings on the reasoning models. Those savings should hold up in wall-clock time, not just in token counts.
References
- Formalizing Test-Time Compute for Function-Level Code Generation
- S*: Test Time Scaling for Code Generation
- RLEF: Grounding Code LLMs in Execution Feedback with Reinforcement Learning
- Adaptive Generate-Rank-Verify: Inference-Time Search with Costly Verification
- Learning How Hard to Think: Input-Adaptive Allocation of LM Computation
- The LLM Already Knows: Estimating LLM-Perceived Question Difficulty via Hidden Representations
- Scaling LLM Inference Efficiently with Optimized Sample Compute Allocation
- Improving Code Efficiency with Iterative Refinement using LLMs
- From Search to Policy: Thompson Sampling Trees for Robust LLM Code Refinement
- DRQA: Dynamic Reasoning Quota Allocation for Controlling Overthinking in Reasoning Large Language Models
- Efficient Reasoning with Balanced Thinking
- Compute Where it Counts: Self Optimizing Language Models
- LiveCodeBench: Holistic and Contamination Free Evaluation of Large Language Models for Code