SCAD: Structured Credit Assignment and Distillation for Long-Horizon Agents

Shangyang Wu, Shuai Zhao, Ziyue Zhu, Jinyang Wu, Anh Tuan Luu, Haoran LuoarXiv 2026 · arXiv

TL;DR

SCAD (Structured Credit Assignment and Distillation) is a new framework designed to train AI agents for complex, long-horizon tasks. By separating an agent into "Planner" and "Executor" roles and using a novel combination of local teacher distillation and prefix-tree-based credit assignment, SCAD significantly outperforms existing methods on both text-based and multimodal benchmarks.

What Problem Does This Paper Address?

Training agents to solve tasks that require dozens of steps—like researching a complex topic across multiple websites—is notoriously difficult. The authors identify three primary "Target Challenges":

  1. Teacher Signal Fading: In on-policy distillation (where a student model learns from a stronger "teacher"), the student's generated history grows long and messy. Eventually, the teacher's guidance becomes less relevant because the context has diverged too far from what the teacher was trained on.
  2. Ambiguous Credit: If an agent succeeds or fails after 50 steps, it’s hard to know which specific actions contributed to that outcome. Sparse terminal rewards make it difficult to provide granular feedback.
  3. Conflicting Signals: A "good" action taken during a task that ultimately fails shouldn't necessarily be penalized. Standard reinforcement learning (RL) often applies a negative reward to every step in a failed trajectory, which can suppress useful behaviors learned through distillation.
Figure 1: Target challenges and SCAD

Methods

SCAD introduces a "Planner-Worker" architecture and three core innovations to tackle these challenges:

  • Subtask-Local Distillation: Instead of distilling the entire long trajectory, SCAD breaks tasks into bounded subtasks. The "Executor" (Worker) operates in a fresh, local context for each subtask. This keeps the context window small and ensures the teacher's feedback remains sharp and relevant.
  • Cross-Rollout Prefix Tree: To solve the credit assignment problem for the "Planner," SCAD builds a tree of subtask decisions and reports across multiple attempts (rollouts). By comparing "sibling" nodes—different actions taken from the same historical state—the system can mathematically estimate the relative value of a planning decision without needing a separate, complex "critic" model.
  • Structured Signal Allocation: This is the "secret sauce." SCAD assigns rewards differently based on the agent's role:
  • Planning receives the full signed terminal reward (success/failure) plus the "Tree Credit" from the prefix tree.
  • Execution receives only the positive part of the terminal reward and the teacher's distillation signal. This ensures that even if a task fails, the executor isn't punished for correctly following the teacher's guidance during individual subtasks.
Figure 3: SCAD training framework with local distillation and subtask prefix-tree credit. Planning uses full terminal credit; execution uses positive terminal credit and teacher guidance.

Datasets

The authors evaluated SCAD on a massive suite of 19 datasets, totaling over 1,300 test questions:

  • Text-based ID (In-Distribution): BrowseComp-Plus, WebWalkerQA, HotpotQA, 2WikiMultiHopQA, MuSiQue, NQ, and TriviaQA.
  • Text-based OOD (Out-of-Distribution): Bamboogle, PopQA, GAIA, and xbench.
  • Multimodal ID: MMSearch-Plus, VDR-Bench, VisBrowse-Bench, MMSearch, and SimpleVQA.
  • Multimodal OOD: FVQA, InfoSeek, and LiveVQA.

Key Insights and Ideas

  • Role-Specific Supervision: The most important "aha moment" is that planning and execution are fundamentally different skills that require different feedback loops. Planners need to know if their strategy led to a win; Executors just need to know if they performed a specific tool-use step correctly.
  • Context Isolation as a Feature: While most research focuses on expanding context windows, SCAD shows that isolating context for subtasks actually makes teacher supervision more effective by preventing "history bloat."
  • Efficiency through Parallelism: Because subtasks are local and independent, teacher scoring can be done in parallel, significantly speeding up the training process compared to sequential trajectory distillation.

Key Results

SCAD achieved a new state-of-the-art across all evaluated benchmarks:

  • Text Tasks: SCAD reached 46.10% macro-average accuracy, a 4.48 percentage point improvement over the strongest baseline (ATOD).
  • Multimodal Tasks: SCAD reached 33.13% accuracy, outperforming the best baseline (HyperEyes) by 4.19 points. Notably, the SCAD student model actually surpassed its own teacher's performance by 2.23 points.
  • Computational Efficiency: SCAD is significantly faster to train, using 37.96% less time than the ATOD baseline while achieving better results.
Figure 2: SCAD training overview (left) and benchmark accuracy (%) across text and multimodal tasks (right; SCAD in red). Axes use separate zero-based scales; † marks out-of-distribution datasets.

Limitations and Future Work

The authors acknowledge a few areas for growth:

  • Teacher Dependence: The quality of local distillation is still capped by the teacher's competence on specific subtasks.
  • Tree Sparsity: If the agent's rollouts are extremely diverse, the prefix tree might have few "sibling" comparisons, leading to noisier credit estimates.
  • Fixed Budgets: Currently, every subtask has the same token budget. Future work could involve "adaptive allocation," giving more resources to harder subtasks that offer a higher potential learning benefit.

Summary updated

Abstract

Training long-horizon agents to solve complex tasks requires effective supervision over extended interaction sequences. However, sparse terminal rewards obscure intermediate contributions, while on-policy distillation can lose informative teacher guidance as student-generated histories grow. To address this problem, we introduce SCAD, which organizes interactions into planning and bounded subtask execution, distills execution in local contexts, and refines planning credit through cross-rollout subtask prefix trees, with planning receiving full terminal credit and execution receiving positive terminal credit and teacher guidance. Across all evaluated benchmarks, SCAD improves macro-average accuracy over the strongest training baseline by 4.48 percentage points for text tasks and 4.19 points for multimodal tasks. SCAD effectively combines outcome-based credit assignment with teacher-guided distillation to improve planning and execution in long-horizon agents.
BibTeX
@misc{wu2026scad,
  author = {Shangyang Wu and Shuai Zhao and Ziyue Zhu and Jinyang Wu and Anh Tuan Luu and Haoran Luo},
  title = {{SCAD: Structured Credit Assignment and Distillation for Long-Horizon Agents}},
  year = {2026},
  eprint = {2610.03372},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.03372},
}
Figure