Technical Summary: CodeRescue: Budget-Calibrated Recovery Routing for Coding Agents

1. Problem Formulation

The paper addresses the deployment challenge of coding agents operating in executable environments where failed attempts generate actionable feedback (e.g., compiler errors, failed tests, stderr traces) rather than just incorrect outputs. Existing cost-aware systems typically treat model failures as a binary decision: escalate immediately to a stronger, more expensive model.

The authors argue this approach is suboptimal for coding because execution feedback can make further attempts by a cheap model worthwhile. This creates a budgeted deployment question: when an agent fails, should it spend more cheap compute to repair the solution (reflect) or replan, or should it escalate to a stronger model?

The problem is formulated as post-failure recovery routing. Given a failed initial attempt by a cheap model, the system must choose among three heterogeneous actions:

1. Reflect: Revise the existing solution using execution feedback.
2. Replan: Generate a fresh solution from a different plan using the cheap model.
3. Escalate: Defer the problem (with feedback) to a stronger, more expensive model.

The goal is to maximize the solve rate subject to a user-specified mean recovery budget ($B$), without retraining the policy for every new budget constraint.

2. Methodology

2.1 Supervised Recovery Router

The core component is a supervised router trained on offline execution rollouts.

• Input: A recovery context $x = (q, v_0, e_0)$, consisting of the problem statement, the execution verdict, and the stderr trace.
• Labeling: For each failed instance, the "oracle" label is defined as the cheapest successful action ($a^\dagger$) among the set of actions that solve the instance ($S(x)$). Instances where no action succeeds are excluded.
• Training: A language model (e.g., Qwen3.5-4B) is fine-tuned via cross-entropy to predict the cheapest successful action. The router scores actions based on log-probabilities and normalizes them via softmax.

2.2 Cost-Regularized Policy

To enable deployment under varying budgets without retraining, the authors introduce a cost penalty $\lambda \ge 0$. The policy $\pi_\lambda(x)$ selects the action maximizing:
$$s_\theta(a | x) - \lambda c(a, x)$$
where $s_\theta$ is the router's score and $c(a, x)$ is the estimated deployment cost.

• As $\lambda$ increases, the policy shifts toward cheaper actions (reflect/replan).
• This creates a discrete set of operating points (a cost-quality frontier) derived from a single trained router.

2.3 Conformal Budget Calibration (CRC)

To select the appropriate $\lambda$ for a specific user budget $B$ with statistical guarantees, the authors apply Conformal Risk Control (CRC).

• Mechanism: Using a held-out calibration set of failed instances, the system computes the empirical mean cost for various $\lambda$ values.
• Selection Rule: It selects the least restrictive penalty $\hat{\lambda}$ such that the finite-sample budget constraint is satisfied:
  $$\frac{n \hat{C}_n(\lambda) + c_{\max}}{n + 1} \le B$$
  where $c_{\max}$ is a known cost cap and the additive term provides a leave-one-out conformal correction.
• Guarantee: Under the assumption of exchangeability, this procedure guarantees that the expected mean recovery cost of the deployed policy on future test data does not exceed $B$. Crucially, this guarantee applies to cost, not solve rate, allowing for non-monotone success patterns across actions.

3. Key Contributions

1. Post-Failure Recovery Routing: The paper formulates coding-agent recovery as a routing problem over heterogeneous actions (reflect, replan, escalate) rather than a simple cascade to a stronger model.
2. Budget-Controllable Deployment: It introduces a CRC-calibrated cost penalty that allows a single trained router to operate at multiple budgeted points with marginal expected-cost control, eliminating the need to retrain for different budget constraints.
3. Empirical Recovery Trade-offs: The study provides empirical evidence that cheap recovery and model escalation exhibit complementary success patterns (i.e., some failures are only solvable by cheap actions, others only by escalation, and some by both), forming a discrete cost-quality frontier.

4. Experimental Results

The system was evaluated on five coding benchmarks (APPS, TACO, BigCodeBench, LiveCodeBench, CodeContests) using GPT-5.4-NANO as the cheap model and GPT-5.4 as the strong model.

• Router Efficacy: A learned router significantly outperforms fixed-action baselines. The unconstrained learned router achieved an 81.7% solve rate at a mean cost of 5.51 m$, compared to 68.6% for "always-escalate" at 7.22 m$.
• Complementarity: Analysis of the "oracle" cheapest actions revealed that 28% of failures were solvable only by cheap actions, 45% only by escalation, and 27% by both. This heterogeneity justifies the need for a router over a fixed cascade.
• Budget Calibration: The CRC-calibrated frontier demonstrated that at a budget of 2.56 m$, the system achieved a 71.7% solve rate. This exceeded the "always-escalate" baseline (68.6%) while using only 35% of the mean cost of the always-escalate strategy.
• Baselines: The learned router outperformed prompt-only routers (zero-shot LLMs acting as routers) and binary cascade baselines, confirming that the routing signal requires learning from rollouts rather than just prompt engineering.

5. Significance and Claims

The paper claims that treating coding failures as a diagnosable repair problem rather than a simple capability gap allows for more efficient resource allocation. By decoupling the training of the router from the deployment budget via CRC, the system offers a practical mechanism for budget-controlled inference.

The authors emphasize that their approach does not claim to control solve rate conformally; rather, it provides a cost guarantee while the solve rate improvements are empirical. The work suggests that for coding agents, the "cheapest useful next step" is often not the strongest model, but a specific recovery action tailored to the failure mode, and that this decision can be made dynamically under strict budget constraints.

Limitations noted by the authors:

• Recovery is modeled as a single post-failure decision, whereas real agents may iterate over multiple rounds.
• The "cheapest successful" label is a proxy and not a calibrated probability estimate.
• CRC controls expected cost, not solve rate, meaning quality improvements remain empirical observations.