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

Credit Without Ground Truth: Claim-Matched Evaluation of Step-Level Credit with Finite Executed Replay
Aug 20, 2026Haiyue ZhangLLM Agent Evaluation Step-Level Credit Assignment in RL
University of Southern California, Los Angeles, CA, USA
The Trace Is the State: Exact Credit Assignment for LLM Agent Teams
Mar 6, 2026Yanjun Chen, Yirong Sun, Hanlin Wang +5Credit Assignment Counterfactual Credit Assignment
Eastern Institute of Technology · The Hong Kong Polytechnic University · Harbin Institute of Technology
ZEBRA: Zero-shot Budgeted Resource Allocation for LLM Orchestration
May 19, 2026May Hamri, Inbal Talgam-CohenLLM Agent Orchestration Cost-Aware Inference
1Tel Aviv University

Aug 20, 2026J/K move · Enter open · S save

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

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

Open paper AskPDF arXiv

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.

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