Stopping rules that balance expected quality gains against per-call costs can make self-refinement far more cost-efficient: threshold policies derived from an optimal-stopping formulation outperform heuristic stopping on a 50-task coding benchmark across three frontier models, reducing API expenditure while preserving code quality.

Main Finding

Self-refinement (iterative generate → verify → revise) for foundation models can be framed and solved as a finite-horizon optimal stopping problem. Under empirically identified dynamics for code-generation tasks, the optimal policy has a simple threshold structure (stop when the current score exceeds a stage-dependent threshold). These policies can be computed efficiently (via dynamic programming/stochastic approximation) and, on a coding benchmark, yield substantially better cost–quality trade-offs than previously used heuristic stopping rules.

Key Points

• Problem formulation

  • Each refinement iteration incurs cost c > 0 and produces a new quality score x ∈ [0,1].
  • Objective: maximize expected payoff E[g(x_τ) − c τ] where τ is the stopping time and g is a payoff (in experiments g(x) = β x).
  • Dynamics modeled as x_{k+1} = f(x_k, w_k); the process is Markovian and runs for at most N iterations.

• Theoretical results

  • Bellman recursion: V_k(x) = max{ g(x), −c + E[V_{k+1}(f(x,w))] }.
  • Under empirically observed structure (f nondecreasing in x; diminishing returns: f(x,w) − x nonincreasing in x), the optimal value V_k is nondecreasing and V_k − g is nonincreasing.
  • Consequently, there exists an optimal threshold policy: at stage k stop iff x ≥ α_k, for thresholds α_0,...,α_{N−1}.
  • Thresholds can be computed efficiently via dynamic programming and stochastic approximation.

• Empirical observations guiding theory

  • Using a code-optimization task, all three tested models show most improvement in the first 3–4 refinement iterations and then diminishing returns.
  • Token usage and monetary cost grow approximately linearly with iterations, creating a clear trade-off.

Data & Methods

• Use case and metric

  • Task: code optimization (EFFIBENCH). Candidate score \tilde x ∈ [0,1] combines correctness, execution time and memory (tests failing ⇒ 0; otherwise normalized execution-time/memory metric).
  • State x_k = best candidate score so far (x_k = max{x_{k−1}, \tilde x_k}).

• Models and experimental setup

  • Models: HAIKU 4.5, GEMINI FLASH-LITE 3.1, GPT CODEX MINI 5.1.
  • Runs: self-refinement loop for N = 10 iterations, across 50 tasks per model.
  • Continuation cost c set to empirical average per-iteration monetary cost (table in paper; e.g., HAIKU 4.5: $0.01/iter; costs computed from per-token charges as of 2026-03-17).

• System identification

  • Transition model: x_{k+1} = min{1, max{x_k, q(x_k) + w_k}}; w_k Gaussian noise.
  • q(·) estimated by Gaussian Process regression (mean m(x)=x, Matérn 5/2 covariance), yielding posterior mean \tilde q(x) and noise variance σ^2.
  • Two empirical structural observations from GP posterior: (1) monotonicity (q nondecreasing → f nondecreasing), (2) diminishing returns (\tilde q(x) − x nonincreasing).

• Optimization/Computation

  • Standard dynamic programming / Bellman recursion for finite horizon.
  • Use of stochastic approximation to compute thresholds efficiently in practice.
  • Implementation of method published by authors (reference [13] in paper).

• Empirical results

  • The stopping policies derived from the optimal stopping formulation outperform heuristic stopping rules in cost-efficiency on the code benchmark: similar or better final-quality per dollar spent, due to early stopping when marginal improvement falls below cost.
  • Most model improvement occurs early; thus optimal stopping tends to accept after a small number of iterations unless low initial quality justifies more attempts.

Implications for AI Economics

• Quantifying per-invocation value: The formulation makes explicit the marginal-value calculus for each API/model invocation (expected quality gain vs cost), enabling rational decisions about how many refinement calls to make.
• Pricing and billing design: Providers and consumers can use such stopping rules to estimate willingness-to-pay per call, set tiered pricing, or design metered products that align payments with expected marginal benefit.
• Resource allocation and throughput: In production systems, stopping policies reduce wasted compute/time by terminating refinement when expected gain < cost, improving overall system throughput and reducing operational spend.
• Contracting and SLAs: The framework supplies a transparent criterion (threshold α_k tied to β, c, and dynamics) for specifying SLAs or pay-per-improvement contracts (e.g., pay until quality threshold or marginal benefit floor).
• Product design and UX: Systems that offer iterative refinement (code assistants, scientific assistants) can expose controls or defaults that reflect optimal stopping thresholds tailored to customer value-weights β.
• Calibration of verifier investment: The model depends on the verifier/score; investing in better verification (more accurate scores) could improve thresholding decisions and overall cost-effectiveness — a trade-off analyzable in the same framework.

Caveats and extensions - Assumptions: linear payoff g(x)=βx, constant per-iteration cost c, finite horizon, and Markovian score dynamics. Real applications may require non-linear utilities, variable cost (e.g., varying token counts), multi-criteria payoffs, or partial observability. - Estimation errors: GP-based dynamics are approximations; misestimation of q or noise can shift thresholds. Robust or online/adaptive stopping policies could mitigate this. - Multi-agent or strategic settings: If multiple agents share model resources or if providers alter pricing dynamically, game-theoretic extensions will be needed. - Broader tasks and verifiers: Results come from a code benchmark; other modalities (dialogue, design, planning) with different verifier structures may exhibit different dynamics and thresholds.

Overall, the paper provides a principled decision-theoretic approach to when to stop self-refinement loops, with theoretical guarantees under empirically justified structural assumptions and practical gains in monetary efficiency on coding tasks.