Coverage, Not Credit: Failure-Credit Routing of Zeroth-Order Perturbation Budgets Does Not Improve On-Pool Sample Efficiency for LLM Agents

Yuxu Ge

cs.AIAug 28, 2026

Coverage, Not Credit: Failure-Credit Routing of Zeroth-Order Perturbation Budgets Does Not Improve On-Pool Sample Efficiency for LLM Agents

Authors: Yuxu Ge

Organizations: University of York

Abstract

Trajectory-level credit assignment can localize which module of a tool-using LLM agent causes failures using only verifiable signals. We ask whether such failure credit should route a fixed zeroth-order/evolution-strategies (ZO/ES) perturbation budget. Across a synthetic environment and frozen Qwen2.5-1.5B/3B and SmolLM2-1.7B agents, three task families, six allocation schemes, a credit-noise sweep, paired seeds, and exact sign-flip tests, we find no statistically detectable improvement over uniform allocation in any on-pool comparison (no gain of at least 2 percentage points). The joint soft-plus-sigma scheme is equivalent to uniform within a +/- 0.02 AUC margin on 1.5B and 3B; concentrating the full budget on the credit argmax is marginally equivalent on 1.5B, where that module is the verified bottleneck, and significantly worse on 3B. Inverse-propensity debiasing does not rescue routing, and misrouting costs up to -0.074 AUC in-house and -0.118 end-to-end on the BFCL-derived family. Across six fixed-step schedules, loss is linear in bottleneck starvation rate (R^2 = 0.94, descriptive), and a preregistered credit-free coverage floor removes detected harm. Matched-budget burst and step-compensating catch-up schedules are consistent with harm arising from insufficient cumulative parameter movement rather than update frequency. Our primary estimand is optimization efficiency on a fixed task pool. On unseen BFCL functions, the study's one exception is that soft routing exceeds uniform on held-out endpoints (+0.047, p = 0.031, n = 6). A plausible but untested reading is that routing-favored caller improvements transfer while uniform's on-pool gains reflect a synthesizer behavior specific to our harness. We report this exception explicitly and document three failure modes that can silently invalidate ZO/ES experiments on frozen LLMs.

Figures & tables

Panel of Figure 1 — Figure 1: (a) Arms optimize a frozen Qwen2.5-1.5B agent from success 0.734 to 0.90–0.92 (last-five-generation means; uniform reaches ${\approx}0.92$ , final generation 0.945); only the misrouted arm lags. (b) Loss vs uniform is linear in the bottleneck starvation rate ( $R^{2}=0.94$ ); error bars are 95% CIs of paired differences.

arm	conc.	AUC	$\Delta$ vs uniform	$p$ (perm.)	TOST $\pm 0.02$
uniform	0.25	$0.8418\pm 0.0250$	—	—	—
soft+ $\sigma$	0.64	$0.8280\pm 0.0145$	$-0.0139$	0.156	✗
hard ( $\arg\max$ credit)	1.00	$0.8389\pm 0.0215$	$-0.0030$	0.766	✓
random module	1.00	$0.7675\pm 0.0075$	$\mathbf{-0.0743}$	0.008	—

Table 1: Main experiment (Qwen2.5-1.5B,

n=8

, paired;

\pm

is SD across seeds in this table). “Conc.” is the mean per-generation fraction of budget on the most-funded module. TOST column: ✓ equivalence certified within

\pm 0.02

; ✗ not certified at

n=8

(soft is certified on the 12-seed replication below); — not applicable. Hard’s equivalence is marginal under paired-

t

TOST (weaker one-sided

p=0.0497

Panel of Figure 2 — Figure 2: (a) Corrupting the routing signal with probability $q$ degrades hard routing monotonically; the endpoints $q=0$ and $q=1$ are the hard and random arms of Table 1 . (b) A credit-free coverage floor removes 80% of hard $\sim$ 0.5’s penalty (a ratio with a noisy denominator; § 5.8 ), landing inside the shaded band, which marks the preregistered prediction $|\Delta|<0.015$ (narrower than the $\pm 0.02$ TOST margin).

arm	predicted	observed
hard $\sim$ 0.5, no floor	$\approx-0.034$	$-0.0273\pm 0.0332$ (5/6 neg.)
hard $\sim$ 0.5, floor $=1$	$\|\Delta\|<0.015$	$\mathbf{-0.0056\pm 0.0124}$ , TOST $p{=}0.002/0.018$

Table 2: Floor test vs preregistered predictions (

\pm

is SD across seeds).

Figure 3: BFCL-derived task family (

n=6

, paired; diamonds: mean with 95% CI; dots: per-seed differences; soft/random/hard at 4 pairs/generation, hard

+

floor at 6; its DiD baseline, the un-floored 6-pair hard arm at

-0.107

, is not drawn). Every routing scheme underperforms uniform—hard most severely (

-0.118

p=0.031

, net learning

+0.013

vs uniform’s

+0.132

)—and a credit-free coverage floor removes the detected harm (

+0.026

vs uniform, n.s.). End-to-end success on the training pool; the arm gaps are carried by the synthesizer relay (§ 5.11 ).

arm	success	caller accuracy	relay
untrained ( $\theta=0$ )	$0.583$	$0.698$	$0.836$
uniform	$0.696\pm 0.031$	$0.696\pm 0.031$	$1.000\pm 0.000$
soft+ $\sigma$	$\mathbf{0.743}\pm 0.016$	$\mathbf{0.745}\pm 0.014$	$0.998\pm 0.006$
random	$0.717\pm 0.022$	$0.727\pm 0.019$	$0.986\pm 0.022$
hard	$0.660\pm 0.043$	$0.733\pm 0.025$	$0.901\pm 0.059$

Table 3: Held-out BFCL evaluation (96 unseen functions; generation-30 coefficients;

n=6

\pm

SD across seeds). Relay is

P(\text{success}\mid\text{call ok})

, the synthesizer’s rate of relaying the constant answer. Bold marks the best value per column (point estimates; only soft’s differences from uniform are individually significant). The untrained row has no seed variance because

\theta=0

is deterministic under greedy decoding.

Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

#	Preregistered prediction	Commit	Date	Outcome
1	Sparse: $\Delta\in[-0.035,-0.015]$ vs uniform †	3b87179	08-19	miss ( $-0.043$ )
2	Floor F1: un-floored hard $\sim$ 0.5 $\approx-0.034$	3b87179	08-19	hit
3	Floor F2: floored $\|\Delta\|<0.015$ (removes $\geq$ 60%)	3b87179	08-19	hit
4	Shaping G1: random ( $w{=}1$ ) $\leq-0.04$ & sig.	11762e7	08-20	hit
4b	Shaping G1: hard ( $w{=}1$ ) $\|\Delta\|<0.02$	11762e7	08-20	hit ( $+0.001$ ; TOST n.c.)
5	Shaping G2: shaping necessary ( $w{=}0$ AUC $<0.78$ )	11762e7	08-20	miss (0.841)

Appendix

Table 4: Preregistration ledger (28 scored: 19 hit, 9 miss; row 25 inert, reported as a control; row 26 unscored). ‡ O2’s “no upside” criterion held; the significant loss was unpredicted and is reported as such (§ 6 , multiple comparisons). § The capacity-matched burst clip never binds, so the arm is bit-identical to plain burst—an inert manipulation, not a scored hit/miss. ¶ The catch-up arm was specified before it ran as a diagnostic whose two outcomes had opposite readings, without a directional prediction; O and Q were preregistered at

n=8

and run at

n=6

. † The sparse prediction was an informal analogy recorded in the analysis commit rather than a separately time-stamped preregistration; it is counted as a miss.

scheme	starv. (nominal)	starv. (measured)	$\Delta\mathrm{AUC}$	95% CI	$p$
hard	0.000	0.028	$-0.003$	$[-0.024,+0.018]$	0.766
hard $\sim$ 0.25	0.188	0.200	$-0.019$	$[-0.041,+0.002]$	0.070
hard $\sim$ 0.5	0.375	0.353	$-0.033$	$[-0.061,-0.005]$	0.023
sparse	0.500	0.500	$-0.043$	$[-0.064,-0.021]$	0.016
hard $\sim$ 0.75	0.562	0.519	$-0.040$	$[-0.063,-0.017]$	0.008
random	0.750	0.767	$-0.074$	$[-0.100,-0.049]$	0.008

Appendix

Table 5: Starvation regression points (

n=8

each, paired sign-flip

p

). Nominal and measured starvation rates agree within

0.05

(deviations

0.028

0.012

0.022

0.000

0.043

0.017

); refitting on measured rates gives slope

-0.091

R^{2}=0.973

regime	uniform AUC	oracle	soft	hard	random
stationary, tight	0.900	$-0.009$	$-0.004$	$-0.037^{*}$	$-0.141^{*}$
non-stationary, wide	0.821	$-0.001$	$-0.006^{*}$	$-0.003$	$+0.003$
non-stationary, tight	0.768	$-0.006$	$-0.007$	$-0.032^{*}$	$-0.220^{*}$
non-stationary, wide ( $d{=}32$ )	0.767	$+0.001$	$+0.001$	$-0.010$	$+0.001$

Appendix

Table 6: Synthetic pre-study,

\Delta\mathrm{AUC}

vs uniform. ∗ paired sign-flip

p<0.05

. Oracle vs uniform passes

\pm 0.02

TOST in three of four regimes (

p_{\mathrm{upper}}/p_{\mathrm{lower}}

{<}0.001/0.021

{<}0.001/{<}0.001

0.006/0.057

{<}0.001/{<}0.001

, in row order; the non-stationary/tight regime is not certified). Per-seed values are in the released results dataset.

sweep	backbone / tasks	arms	$n$	gens	pairs	floor	$w$	reported
synthetic pre-study	mock, 4 regimes	uniform, oracle, soft, hard, random	10	120	4 / 8	0	—	§ 5.1 , App. C
main	1.5B / in-house	uniform, soft+ $\sigma$ , hard, random	8	45	4	0	0.5	§ 5.2
seed extension	1.5B / in-house	uniform, soft+ $\sigma$	12	45	4	0	0.5	§ 5.2
credit noise	1.5B / in-house	hard $\sim$ 0.25, 0.5, 0.75	8	45	4	0	0.5	§ 5.7
sparse	1.5B / in-house	uniform, sparse	8	45	4	0	0.5	§ 5.7
floor	1.5B / in-house	uniform, hard $\sim$ 0.5, hard $\sim$ 0.5+floor	6	45	6	0 / 1	0.5	§ 5.8

Appendix

Table 7: Experiment overview. “BFCL-48” is the 48-task training pool; “BFCL-96 unseen” the held-out set with disjoint questions and function names. Per-module clip is

0.5

except where noted. Synthetic regimes use 4 pairs (tight) or 8 (wide) and module dimensions 16, 8, 16, 32 in the row order of Table 6 .

LLM Agent Training

Large language model agent training teaches models to plan, use tools, and learn from multi-step interaction with environments.

See all 581 papers

Aug 20, 2026

Credit Without Ground Truth: Claim-Matched Evaluation of Step-Level Credit with Finite Executed Replay

Step-level credit evaluation can conflate numerical association with ordering and branch recovery with position-selection value. We test these distinctions in ALFWorld with two independently seeded replay banks: 27,520 continuations over 172 fixed turns. At 16 continuations per arm per bank, cross-bank replay-contrast associations are Pearson 0.736 and pooled Spearman 0.330. On 30 historical failures, A-count-selected branches at confidence-/implicit-selected positions gain 8.54 percentage points over same-position factual reruns, but their 3.33-point advantage over frozen-random positions under the same alternative-selection rule remains unresolved. Numerical association alone does not establish reliable pooled ordering; branch recovery alone does not establish better score-informed position selection. Historical judge alignment is modestly positive with an unresolved archived-control increment. Same-cohort C/D information-source comparisons and a short, sparse-exposure training pilot provide scope checks; incremental hindsight training utility remains unestablished. Findings are conditional on the tested policies, intervention support and finite budgets.

Haiyue Zhang

University of Southern California, Los Angeles, CA, USA

LLM Agent Evaluation Step-Level Credit Assignment in RL Counterfactual Credit Assignment LLM-as-a-Judge

Ask PDF

Mar 6, 2026

The Trace Is the State: Exact Credit Assignment for LLM Agent Teams

Credit assignment for a team of LLM agents, what each message was worth, has mostly been treated as prediction: a learned critic, a trajectory-level score, or an agent ablation stands in for the counterfactual that defines credit, which is rarely run. Teams that communicate through a shared context are different: when everything a downstream agent reads is written into the trace, the trace is the state, and that counterfactual can be executed. A credit signal can then be judged as any estimator is: by bias, variance, and agreement with an independent reference. C3, credit assignment by counterfactual continuation, substitutes one message at a decision point and continues the run to the terminal reward, so its credit is unbiased, exact up to Monte Carlo error. Given the sampled alternatives, that error's variance follows a derived law with no term for the number of agents, and the observed noise follows the law on 6 workflows of 2 to 10 decision points. On the 2-agent chain, from 4 continuations, C3 ranks alternatives at 0.69 rank correlation against a 16-continuation reference, near the 0.73 at which 2 such references agree; a critic trained on the same rollouts reaches 0.29. Used as the advantage in training a 2-agent team, C3 beats MAGRPO, the stronger baseline in our comparison, and spends 37% fewer training tokens than MAPPO, since only the messages downstream of a decision point are regenerated. When the trace is the state, credit need not be predicted; it can be exact.

Yanjun Chen, Yirong Sun, Hanlin Wang +5

Eastern Institute of Technology · The Hong Kong Polytechnic University · Harbin Institute of Technology

Credit Assignment Counterfactual Credit Assignment LLM Agent Training Multi-Agent LLM Systems Multi-Agent Reinforcement Learning

Ask PDF

May 19, 2026

ZEBRA: Zero-shot Budgeted Resource Allocation for LLM Orchestration

As autonomous agents increasingly execute end-to-end tasks under fixed monetary budgets, the pressing open question shifts from whether the budget is respected, to how to spend it effectively. Existing budget-aware methods typically control reasoning step-by-step within a single agent, or learn resource allocation policies via RL. None address how to split a budget across the composing phases of a multi-agent pipeline at inference time. We propose ZEBRA, a zero-shot framework that reduces multi-phase budget allocation to a continuous nonlinear knapsack problem: an LLM controller estimates per-phase utility curves, and a water-filling search on the Lagrange multiplier returns the per-phase split. Additive and multiplicative aggregations are unified under the same solver. On a

150

-task APPS coding benchmark, both ZEBRA variants outperform LLM-direct (budget allocation directly by an LLM) on every aggregate metric. At a budget of

α= 0.5

of the unconstrained spend, ZEBRA recovers

94.4\%

of unconstrained quality, versus

88.1\%

for LLM-direct. The advantage is statistically significant and transfers beyond coding: on a

3

-phase HotpotQA pipeline, ZEBRA beats LLM-direct by

14.3

pp, with allocations empirically robust to curve-estimation noise. On HotpotQA, ZEBRA arrives at a different budget split (near-balanced) compared to the APPS one (skewed towards a refinement phase), showing adaptation to the pipeline structure. More broadly, we show that lightweight algorithmic guidance at inference time can improve the economic behavior of autonomous multi-agent systems.

May Hamri, Inbal Talgam-Cohen

1Tel Aviv University

LLM Agent Orchestration Cost-Aware Inference LLM Agent Workflow Optimization Multi-Agent Systems Multi-Agent Resource Allocation

Ask PDF

Abstract

LLM Agent Training

Explore similar work

Credit Without Ground Truth: Claim-Matched Evaluation of Step-Level Credit with Finite Executed Replay

The Trace Is the State: Exact Credit Assignment for LLM Agent Teams

ZEBRA: Zero-shot Budgeted Resource Allocation for LLM Orchestration