DRACO: Fine-Grained Credit Assignment with Dynamic Rubrics for Long-Horizon Agent Training
Shubham Gandhi, Saurabh Goyal, Kiran Kate, Yara Rizk
cs.AI, cs.LG, cs.SE
2026-09-04
DRACO writes per-trajectory rubrics and sends GRPO advantage to cited steps, with no success label. AppWorldTN TGC on Qwen3.6-27B goes 69.4 to 85.3, 5.3 above unit-test GRPO.
Math and code can use unit tests as RLVR. Customer support, research agents, and cross-app tool use usually have no programmatic oracle, and building one is often as hard as the task. Rubrics are the usual substitute: one scalar on a finished trajectory. A long-horizon agent takes tens of steps. Successful rollouts contain fluff and luck; failed ones contain mostly correct work. Multiplying one advantage onto every token wastes signal and can reinforce the wrong turns.
CMU and IBM Research tighten the setting further. Training never sees task success or a gold answer. The reward is process criteria only. That is stricter than most rubric papers. Every prior RL result they cite on AppWorld trains against the environment's unit tests. DRACO is, they say, the first run that never touches that signal.
Two pieces.
Dynamic rubrics. A judge proposes criteria from the instruction, then adds criteria from each rollout in a GRPO group. Proposals merge and deduplicate into one shared set. Discriminative dropout keeps a criterion only if some group member failed it, so universal passes do not flatten the reward. A frozen judge (GPT-5.4 in the main runs) labels each trajectory on each criterion as pass, fail, or not applicable, and cites the responsible steps. The trajectory reward is (passes − fails) / (passes + fails) over applicable criteria, not over the raw criterion count.
Step credit. GRPO still standardizes rewards into a trajectory advantage Ai. That scalar is no longer copied onto every token. Cited steps get a quality Q = passes / (passes + fails). Weights are Q when Ai ≥ 0 and 1−Q when Ai < 0, so winners reinforce the steps judged good and losers suppress the steps judged bad. Token counts then spread a fixed per-step budget so the sum of nj aj equals Ai N: total push is conserved and the sign never flips. Glue tokens get zero credit. The rule is closed form. There is no trained attribution head.
Training uses the 90-task AppWorld split, LoRA, GRPO with group size 6 and batch 16, on 8 H100s. Qwen3.6-27B runs 100 steps; Qwen2.5-32B-Instruct runs 75. τ-bench is zero-shot transfer. Unit tests are evaluation-only.
On Qwen3.6-27B, AppWorldTN (168 tasks) TGC/SGC moves from 69.4/41.1 to 85.3/70.6 (+15.9 / +29.5). AppWorldTC TGC moves from 49.7 to 61.5. τ-bench success goes 15.8→20.4. A matched GRPO run that does use unit tests scores 80.0/59.3; DRACO still leads by 5.3 TGC and 11.3 SGC. Consistency moves more than discovery: TGC p3 on TN rises 47.6→72.8 (+25.2), while pass@3 rises only 3.9. Random rewards stall at 74.0/50.0.
Ablations say both pieces are required. Drop dynamic rubrics or step credit and the p1 average sits at 52.0-53.3 against DRACO's 55.7; p3 averages 35.3-37.8 against 40.9. On TN, adding step credit to per-trajectory rubrics is worth +3.2 TGC and +5.7 SGC. On TC the same credit rule costs 3.7 TGC at p3 on a fixed rubric and gains 1.4 once the rubric is episode-specific. Attribution needs criteria that actually point at steps.
On Qwen2.5-32B-Instruct, TN TGC/SGC moves 35.7/17.3 → 62.9/42.3, close to verifier-trained SALT at 66.2/47.9. Episode length on AppWorld shortens (TN 18.7→14.7 turns) and eval cost falls from $10.77 to $8.27. A self-judge with thinking and k=3 unanimous passes reaches 81.1/62.7 on TN, above the verifier baseline. Dropping thinking and using one scoring call cuts 100-step judge spend from $1607 to $316. The self-judge is lenient: 89.4% agreement on 60,689 criterion verdicts, passing 30.4% of GPT-5.4 fails and failing 1.3% of its passes.
Long-horizon tool agents without an oracle have been waiting on a verifier, or compressing a whole trajectory into one scalar. DRACO is a runnable middle path: let a judge write process criteria, then push the score back to steps with a formula. Beating matched verifier GRPO on AppWorld means "no outcome label" is not the same as "nothing to learn," at least on this benchmark. The self-judge variant also takes the frontier model out of the inner loop and can cut judge spend by about 5×.
The holes they list are the right ones. Rubrics are never checked by humans, so a consistent judge can still be systematically wrong, and the policy inherits that bias. End-task gains do not prove credit landed on the right steps. Discriminative dropout makes the criterion set a function of the sampled group; that training variance is unmeasured. Main runs freeze GPT-5.4, so the quality floor is unknown. AppWorld's APIs are relatively clean. Whether dynamic rubrics stay ungameable in messier environments is open.