PaperlayerView exact revision on arXiv

Source-linked AI summary

DRACO: Fine-Grained Credit Assignment with Dynamic Rubrics for Long-Horizon Agent Training

Shubham Gandhi, Saurabh Goyal, Kiran Kate, Yara Rizk

arXiv:2609.04094v1cs.AIcs.LGcs.SE

TL;DR

Long-horizon agent domains often lack ground-truth verifiers, while a single trajectory-level rubric score provides weak credit across many steps. DRACO dynamically generates per-trajectory rubrics and redistributes their judgments to implicated steps in GRPO; it improves AppWorld performance, transfers to τ-bench, and can match or exceed verifier-trained baselines without a verifier.

  • Problem

    Many long-horizon agent domains lack programmatic verifiers, and uniform trajectory-level rewards poorly assign credit across tens of interdependent steps.

  • Method

    DRACO dynamically generates task-specific rubrics from policy rollouts, scores them per trajectory, and uses closed-form rubric-conditioned step-credit redistribution in GRPO without a verifier.

  • Results

    DRACO improves AppWorld’s TGC by 15.9 points, transfers zero-shot to τ-bench, and matches or exceeds a same-budget verifier-trained baseline.

  • Takeaways & Limitations

    Step-level credit assignment on top of per-trajectory rubrics is key, while criteria must be specific enough to support meaningful attribution.

  • Takeaways & Limitations

    Rubric criteria and step attribution lack independent validation against human judgments or an external correctness signal.

Abstract

from arXiv · show

Reinforcement Learning from Verifiable Rewards works well when a task has a programmatic checker, but most long-horizon agent domains have none. We work in the outcome-blind setting, where ground-truth success signals are not available. Multi-criteria rubrics are a popular way to supply such a reward; they are scored once per trajectory, but a single scalar is a poor signal across tens of steps. We propose DRACO: Distributing Rubric-based Advantage for Credit Optimization. It generates rubrics dynamically during training to track the policy's evolving capability, scores those rubrics once per completed trajectory, and redistributes that judgment over the steps responsible for annotated rubrics to produce differentiated per-step advantages in GRPO. The redistribution is closed-form and does not introduce any trained attribution module. On AppWorld, DRACO gains 15.9 points over the base model and 5.3 points over GRPO trained with a sparse ground-truth reward, despite not using any verifiers itself. On out-of-domain Tau-Bench, it gains 5.3 points over the base model even without a frontier judge, beating both ground-truth-reward training and other rubric-based training settings. The code for DRACO is available at https://github.com/IBM/draco.

1 Introduction

DRACO targets long-horizon agent training without ground-truth verifiers, where outcome-blind rewards must also assign credit across many interdependent steps. It combines dynamic rubrics with rubric-conditioned step attribution and reports strong AppWorld performance with transfer to τ-bench.

  • Motivation: Many real-world agent domains lack programmatic success oracles, making ground-truth verification unavailable for training.Customer-support and open-ended research agents are cited as examples where constructing a verifier can be as difficult as the task itself.
  • Motivation: Uniformly applying one trajectory-level scalar across tens of tool-calling steps can waste or misassign credit because successful trajectories contain redundant steps and failed ones contain mostly correct steps.The paper frames this as a second difficulty coupled to outcome-blind training.
  • Approach: DRACO generates dynamic per-trajectory rubrics and distributes rubric-conditioned advantage to steps within GRPO without using ground-truth outcomes during training.The two components target task-adaptive coverage and faithful per-step attribution.
  • Results: 85.3 TGC on AppWorldTN represents a +15.9-point gain over the untrained policy, with zero-shot transfer to τ-bench and performance at or above a same-budget verifier-trained run.The reported AppWorld result is obtained without accessing the environment’s ground-truth unit tests.
  • Contributions: DRACO contributes outcome-blind rubric-based RL, dynamic per-trajectory rubric generation, and closed-form step-credit redistribution without a verifier.The credit rule is reported to satisfy formal properties including total-push conservation, sign preservation, and length independence.

2 Related Work

Prior work varies in whether it uses dynamic rubrics, trajectory-level scoring, and step attribution, but most fine-grained methods depend on reliable outcome signals. DRACO combines trajectory-scored evolving rubrics with closed-form, verifier-free step redistribution and no learned attribution module.

  • Rubric-based rewards: Rubric-based methods either evolve a rubric and score it once per rollout or score fresh criteria at every position.Per-position scoring is expensive and task-specific, while trajectory-level scoring provides a different granularity.
  • Rubric-based rewards: DRACO retains evolving, trajectory-scored rubrics while redistributing their judgments over steps in closed form, avoiding per-position judge calls and learned attribution.This distinguishes it from methods using a trained discriminator to propagate rubric scores to tokens.
  • Step-level credit assignment: Most fine-grained credit-assignment methods for LLM agents require a reliable outcome signal, whether through progress estimators, rollout recurrence, or gold-answer likelihood.Other approaches perform post-hoc LLM attribution or specialize to particular action spaces.
  • Step-level credit assignment: DRACO’s attribution uses no ground-truth outcome, assumes no particular action structure, and requires no learned component.These are the paper’s three stated departures from prior attribution methods.

3 Method

DRACO combines dynamic, group-shared rubric scoring with a closed-form rule that reallocates GRPO’s trajectory advantage to implicated steps. The design remains outcome-blind, preserves total influence and sign, and falls back to baseline GRPO when no step is cited.

  • Setup: The method assumes long-horizon trajectories, no verifier at training time, and rewards derived solely from process criteria.Each task produces a trajectory of interleaved reasoning and tool calls, typically spanning tens of steps.
  • GRPO background: GRPO standardizes scalar trajectory rewards within each sampled group, then ordinarily applies the same advantage to every emitted token.DRACO changes both the reward source and the uniform use of that advantage.
  • Dynamic Per-Trajectory Rubrics: For each task, DRACO generates criteria from the instruction and sampled rollouts, merges and deduplicates them, drops criteria no group member failed, and scores applicable criteria per trajectory.A frozen judge returns pass, fail, or not applicable together with justifications and responsible steps; the reward is outcome-blind.
  • Step Credit: Step quality is computed from the pass fraction of criteria citing each step, with uncited steps inheriting the mean quality over cited steps.The resulting qualities determine the step weights used for credit redistribution.
  • Step Credit: DRACO replaces uniform trajectory advantage with one step advantage per agent turn, using sign-preserving weights to place more influence on judged-good or judged-bad steps.The sign of the trajectory advantage determines reinforcement versus suppression, while step weights determine where that push lands.
  • Step Credit: Credit redistribution preserves the trajectory’s total push, makes influence independent of step length, and reverts to baseline GRPO when no rubric citation identifies a step.Each step’s total contribution depends on its quality weight rather than verbosity.

4 Experimentation

DRACO is evaluated as an outcome-blind training method on AppWorld and τ-bench, with experiments isolating dynamic rubrics, step credit, judge choice, consistency, efficiency, and rollout behavior.

  • Overall Results: DRACO raises Qwen3.6-27B AppWorldTN TGC/SGC from 69.4/41.1 to 85.3/70.6, gains +15.9/+29.5 points, and improves AppWorldTC TGC from 49.7 to 61.5.With Qwen2.5-32B-Instruct, AppWorldTN TGC/SGC increases from 35.7/17.3 to 62.9/42.3.
  • Overall Results: DRACO transfers zero-shot to τ-bench, raising SR from 15.8 to 20.4 without verifiers, gold answers, or reference trajectories.All training uses AppWorld; τ-bench is evaluated out of domain.
  • Consistency and Discovery: DRACO improves both discovery and consistency, with AppWorldTN TGC p3 increasing by 25.2 points while pass@3 rises by 3.9.Retention p3/p1 is highest for DRACO on both TGC and SGC.
  • Outcome Reward: Against vanilla GRPO trained on AppWorld unit tests, DRACO gains +5.3 TGC and +11.3 SGC on AppWorldTN and +1.6/+2.4 on AppWorldTC.At p3, the margins widen to +9.5/+13.7 on AppWorldTN and +3.5/+6.0 on AppWorldTC.
  • Rubric Type and Step Credit: Step credit helps when rubrics are per-trajectory and dynamic: on AppWorldTN it adds +3.2 TGC and +5.7 SGC over per-trajectory rubrics alone, while fixed-rubric step credit can hurt.On AppWorldTC, fixed-rubric step credit costs 3.7 TGC at p3, whereas per-trajectory step credit adds +1.4 TGC.
  • Self-Judge: Self-judging cuts judge cost from $1607 to $316 for 100 training steps, a 5.1× saving, while reaching 81.1/62.7 AppWorldTN TGC/SGC and 21.1 τ-bench SR.The self-judge uses three scoring calls per criterion and accepts a pass only when all three calls pass.

5 Conclusion

DRACO addresses outcome-blind reinforcement learning for long-horizon tool-using agents by combining task-specific rubrics with step-level credit assignment. It improves AppWorld performance, transfers zero-shot to τ-bench, and matches or exceeds a verifier-trained baseline.

  • DRACO targets long-horizon tool-using agents when ground-truth success signals are unavailable and rewards must come from process criteria.
  • Task-specific rubrics are generated from policy-model rollouts and merged at the group level.
  • The step-credit rule redistributes trajectory advantage using per-criterion judge attributions while preserving total magnitude and sign.
  • +15.9 points in AppWorld TGC on AppWorldTN, with zero-shot transfer to τ-bench and performance at or above a same-budget verifier-trained run.
  • Ablations identify step-level credit assignment on top of per-trajectory rubrics as key, while criterion specificity remains the main evaluation challenge.

6 Limitations

The paper’s rubric-based rewards and step-level attribution lack independent validation against human or ground-truth signals. Training-time variability from discriminative dropout is also not characterized.

  • Rubric criteria cannot be independently checked for faithful task description on unverifiable tasks without human raters.
  • A frozen judge may be internally consistent yet systematically wrong, and the experiments do not separate these possibilities.
  • End-task performance does not establish that redistributed credit lands on the correct steps.
  • Discriminative dropout makes criteria depend on the sampled group, but training-time variance from this effect is not measured.

7 Ethics Statement

The evaluation uses fully simulated benchmarks with no real user data, live services, or human subjects. The explicit rubric objective is auditable, but judge bias can be inherited by the policy without verifier-based correction.

  • AppWorld and τ-bench use synthetic fixtures for every app, account, and record under their released licenses.
  • No real user data or live service is touched, and no human subjects are involved.
  • Natural-language reward criteria make the optimization target explicit and auditable, which the authors regard as a safety property.
  • Judge bias may be inherited by the policy without a verifier to catch it, while more competent tool use remains dual-use.

A Additional Results

Additional results report checkpoint variability, difficulty-stratified task success, consistency-versus-discovery comparisons, and a self-judge variant using repeated scoring with unanimity.

  • Tables 4 and 5 restate core tables with standard deviations across the three reported checkpoints.
  • Table 6 splits task success by AppWorld difficulty label, supporting the by-difficulty analysis in Section 4.3.
  • Figure 5 compares passk with pass@k for every setting, separating consistency from discovery.
  • The self-judge uses thinking in every judge phase and repeats scoring k=3 times per trajectory.
  • The unanimity rule counts a criterion as passed only when all three scoring calls pass it, targeting lenient false passes.

A.2 Comparison with frontier models

DRACO brings a 27B model close to substantially larger frontier models on AppWorldTN while reducing evaluation cost, using outcome-blind rewards alone.

  • 85.3/70.6 TGC/SGC lifts the Qwen3.6-27B policy from 69.4/41.1 after 100 training steps.The same training lowers evaluation cost from $10.77 to $8.27.
  • DRACO comes within 4.6 TGC of claude-sonnet-4-6 and 8.2 of claude-opus-4-7 at 44% and 25% of their cost.
  • DRACO exceeds DeepSeek-V4-Flash and gpt-oss-120b by 14.5 and 41.3 TGC, respectively.
  • +29.5 points on SGC produces the largest gain, bringing DRACO within 11.5 points of Kimi-K2.7-Code.

B Additional Analysis

The appendix analyzes evaluation behavior, consistency metrics, and experimental reporting conventions for DRACO and related settings.

  • Table 4 reports task success and consistency with checkpoint and evaluation-run variability, reproducing Table 2 means.Trained rows average three checkpoints; base rows use three independent evaluation runs.
  • Figure 5 contrasts passk, requiring all k runs to succeed, with pass@k, requiring at least one success; they coincide at k=1.Axes do not start at zero, and all panels use Qwen3.6-27B.
  • Figure 9 analyzes how the self-model and GPT-5.4 score rubrics, generate criteria, and merge criteria using replayed judge calls.

B.1.1 Annotation: applying a given rubric

The appendix evaluates judge annotation, rubric generation, evaluation cost, and related experimental breakdowns for outcome-blind DRACO training.

  • B.1.1 Annotation: applying a given rubric: Self-model annotation errors are asymmetric: false passes occur on 30.4% of GPT-5.4 failures, versus 1.3% false fails on GPT-5.4 passes.The lenient error is about 24 times more likely than the strict error.
  • B.1.1 Annotation: applying a given rubric: False-pass rates rise from 22.1% to 34.9% across training quarters, while false-fail rates remain below 5%.Agreement changes only from 90.8% to 89.0%, alongside fewer criteria per rollout and fewer GPT-5.4 failures.
  • B.1.1 Annotation: applying a given rubric: Table 4 reports task success and consistency with checkpoint and evaluation-run variability, while Table 6 breaks task success down by AppWorld difficulty.
  • B.1.1 Annotation: applying a given rubric: The self-judge variant is evaluated under Table 7’s protocol, including thinking-enabled scoring with three calls per trajectory and a single-call no-thinking variant.
  • B.1.1 Annotation: applying a given rubric: Table 8 compares frontier models and DRACO on AppWorldTN using TGC, SGC, and one-pass evaluation cost.
  • B.1.2 Generation: writing the criteria: Rubric-generation replay measures overlap through recall and precision across 1,024 rollouts over 11 steps.The comparison uses Claude Sonnet to match criteria one to one.
  • B.1.2 Generation: writing the criteria: Self-model rubric generation averages 0.21 recall and 0.39 precision, below GPT-5.4’s self-consistency references of 0.43 and 0.48.It writes 3.8 criteria per rollout versus GPT-5.4’s 5.1.

B.1.3 Union: merging candidates into the scored set

DRACO’s union stage retains most relevant criteria but also preserves excessive additional criteria, weakening the resulting within-group reward signal.

  • The merged rubric set is evaluated over 175 groups, with self-consistency ceilings of 0.55 recall and 0.57 precision.
  • 0.80 recall shows the self-model keeps four in five criteria retained by GPT-5.4, while 0.44 precision reflects surplus criteria.The self-model keeps 15.3 criteria per group versus 6.3 for GPT-5.4.
  • 31.3% of self-model criteria are failed by at least one rollout, versus 46.5% for GPT-5.4, so the surplus adds length without reward discrimination.
  • The replay does not measure compounding degradation in a fully self-judged run because generation and merging still consume GPT-5.4’s archived candidate pool.
  • The reported ceilings are scale references rather than exact bounds because they rely on only 24 and 14 scored pairs.

B.2 What the dynamic rubrics contain

DRACO’s dynamic rubrics are predominantly task-specific sub-goals that expose concrete failure modes, while rediscovered task-general criteria subsume the static rubric set. Their greater discriminative power keeps step credit active more often than static rubrics.

  • B.2 What the dynamic rubrics contain: DRACO’s rollouts recover 91.3% on a fixed static set they never trained on, indicating that the dynamic criteria subsume the static ones.The analysis covers 96 rollouts, 99 completed steps, 6,245 distinct criteria, and 60,119 judgments.
  • B.2 What the dynamic rubrics contain: 84.4% of distinct criteria target a single task, carrying 57.2% of all judgments; only 18 criteria span ten or more tasks.The dynamic rubric inventory is dominated by task-specific criteria rather than broadly reusable checks.
  • B.2 What the dynamic rubrics contain: Task-specific criteria identify concrete sub-goals and likely instruction misreadings, such as deduplicating artists or approving only eligible Venmo requests.These criteria distinguish errors that a generic rubric shared across all tasks cannot express precisely.
  • B.2 What the dynamic rubrics contain: The 18 task-general criteria fall into four families already represented in the static set: secrets, pagination, completion stopping, and error recovery.This provides the generator-side view of static-set subsumption.
  • B.2 What the dynamic rubrics contain: 26.7% of applicable dynamic-rubric verdicts are failures, versus 5.5% for static rubrics, making the per-trajectory criteria more discriminative.A criterion that every group member passes contributes nothing to the advantage.
  • B.3 Why step credit needs dynamic rubrics: Step credit adds +3.2 TGC on per-trajectory rubrics but only +0.8 on static rubrics because it acts only when rubric verdicts are mixed.Unanimous verdicts assign every step the same weight, reproducing baseline GRPO; no surviving criterion also makes credit inert.
  • B.3 Why step credit needs dynamic rubrics: Credit is inert on 76.4% of static rollouts versus 48.1% of DRACO rollouts averaged over training.Static-rollout inertia rises to 91.9% in steps 76–100, whereas DRACO remains near 56.5%.
  • C Rubric Construction: The static rubric was authored once from 720 base-policy trajectories and frozen, whereas dynamic settings generate criteria per task at every training step.Both regimes instruct generation to keep criteria mutually exclusive and collectively exhaustive; static criteria are additionally pruned for applicability and discrimination.

D Training Hyperparameters

The training setup uses GRPO with within-group standardized rewards and no value network, while DRACO redistributes trajectory advantage across rubric-cited steps. The redistribution preserves total scalar push, handles step length explicitly, and leaves gradient-vector allocation changed by design.

  • D Training Hyperparameters: GRPO standardizes each trajectory’s reward within a sampled group, using the group mean and standard deviation to form its advantage.The setup samples G trajectories for each task and applies the resulting trajectory-level scalar in the policy-gradient update.
  • D Training Hyperparameters: DRACO replaces uniform trajectory advantage Ai with per-step advantage aj, while every token inside step j receives the same aj.Steps correspond approximately to agent turns or emitted code blocks; gap tokens receive zero advantage and are excluded from redistribution.
  • D Training Hyperparameters: Ai sets the rollout’s total reinforcement or suppression, while credit redistribution determines where that push lands within the trajectory.Positive Ai reinforces a winner relative to its group, negative Ai suppresses a loser, and magnitude controls strength.
  • D Training Hyperparameters: Step quality Qj is the pass fraction of rubric checks citing step j, with uncited steps inheriting the mean quality over cited steps.The credit run has a median of one and mean of 1.95 citing rubrics per step; only 0.6% of steps have ten or more.
  • D Training Hyperparameters: Winner and loser weighting is sign-correct: winners emphasize good steps, whereas losers emphasize bad steps for suppression.A unanimously failed step contributes zero on a winner, and a unanimously passed step is not suppressed on a loser.
  • D Training Hyperparameters: The 1/nj factor keeps each step’s total influence length-independent, so verbose steps receive proportionally smaller per-token pushes.Dropping 1/nj would allow long steps to accumulate larger total influence and reward verbosity.
  • D Training Hyperparameters: The redistribution preserves the baseline scalar sum over credited tokens, AiN, but not the total gradient vector.Moving advantage between steps with different token gradients is the intended effect, while gap tokens remain outside the accounting.
  • D Training Hyperparameters: With Ai=1 and two steps, equal quality splits total influence evenly despite lengths of 2 and 4 tokens; higher quality shifts more influence to the better step.The equal-quality example gives a1=1.50 and a2=0.75, while the higher-quality example gives both step advantages as 1.00.

E.6 Running example (real logged rollout)

The running example shows how DRACO converts rubric verdicts into quality-based step weights while preserving total trajectory influence. Mixed verdicts discriminate among steps, whereas unanimous or degenerate cases fall back toward uniform GRPO behavior.

  • Winner branch: Three of five checks failed, yet the rollout is a winner because its reward exceeded the group mean, not because it passed the task.Its absolute reward is Ri = (2−3)/5 = −0.2, while the winner branch is determined by Ai ≥ 0.
  • Step quality: Step quality is the fraction of cited checks that pass, ranging from 1.000 for steps 1–2 to 0.333 for steps 4 and 6.Steps 1–2 have only one passing citation, while steps 4 and 6 each have one pass and two failures.
  • Step weighting: Strong steps receive 72.47 total influence versus 24.16 for flagged steps, a 3× gap matching their weights.Token counts affect per-token advantages, but step totals depend on weights rather than step length.
  • Degenerate cases: Credit distinguishes steps only when cited rubric verdicts are mixed; unanimous verdicts equalize weights and leave only length-based spreading.No citations, all passes, or all failures produce constant weights, so every step receives an equal total share.
  • Fallbacks: If all winner weights collapse to zero, or no step is cited, the implementation falls back to uniform Ai, equivalent to baseline GRPO.The same collapsed-normalizer guard handles a loser whose verdicts all pass.
  • Invariants: The redistribution conserves the baseline GRPO total over credited tokens and never reverses the sign of the trajectory advantage.Non-credited gap tokens receive zero advantage, and non-negative weights ensure reinforcement remains reinforcement and suppression remains suppression.
Loading 2609.04094v1…