GraphOPD: Graph-Augmented On-Policy Distillation for LLM Agents

# Graph-Augmented On-Policy Distillation for LLM Agents
Source: [https://arxiv.org/html/2610.08959](https://arxiv.org/html/2610.08959)
Bohan Lin††thanks:This work was done during the internship at Xiaohongshu\.Liyi ChenAffiliation:XiaohongshuZhuoning GuoAffiliation:The Hong Kong University of Science and Technology \(HKUST\-GZ\)linbohan@ustc\.edu; linbohan04@gmail\.comMuyang LiAffiliation:University of Science and Technology of ChinaQimeng WangAffiliation:XiaohongshuYan GaoAffiliation:XiaohongshuYao HuAffiliation:XiaohongshuYudong ZhangAffiliation:University of Science and Technology of China

###### Abstract

On\-policy distillation post\-trains large language model agents by supplying dense, step\-level guidance from a teacher policy when the reinforcement\-learning reward is sparse and arrives only once per trajectory\. Existing instantiations allocate this guidance by the size of the teacher\-student divergence at each step, on the single\-turn intuition that a large disagreement marks a mistake worth correcting\. Once decisions chain over many turns, that rule misfires, since an early drift enters every later context both policies condition on, leaving the teacher consistent with the drifted trajectory instead of flagging its cause, while interchangeable steps register large but outcome\-irrelevant divergences\. We demonstrate this on an agentic benchmark, where distilling the highest\-divergence steps brings no consistent benefit over random selection\. To this end, we introduceGraphOPD, the first method to bring graph\-based structural augmentation into on\-policy distillation for agent capabilities\. It reads which steps enabled which later ones from the environment’s own record of state changes, immune to the drift that corrupts the teacher\-student gap, organizes them into a dependency graph, scores each step by a random\-walk stationary distribution over it, and fuses that structural credit with the divergence signal into a trajectory\-relative mask concentrating supervision on each rollout’s highest\-aptitude steps\. Across three model scales and eleven baselines on ALFWorld, WebShop, and SearchQA, GraphOPD shows competitive performance throughout, improving over the strongest baseline by up to\+5\.8 pp\. An executed\-replay audit further shows that this structural credit score tracks true causal impact far above chance, that both fused signals are independently necessary, and that the same signal transfers to out\-of\-domain tool\-integrated reasoning\.The code is at[https://anonymous\.4open\.science/status/GraphOPD\-5011](https://anonymous.4open.science/status/GraphOPD-5011)\.

## 1Introduction

On\-policy distillation has become a standard way to post\-train large language model agents that pursue goals through extended interaction with an environment\([Yao et al\., 2023](https://arxiv.org/html/2610.08959#bib.bib35)\), spanning household task execution, multi\-step retrieval, and web purchasing\([Shridhar et al\., 2021](https://arxiv.org/html/2610.08959#bib.bib33);[Yao et al\., 2022](https://arxiv.org/html/2610.08959#bib.bib34);[Yang et al\., 2018](https://arxiv.org/html/2610.08959#bib.bib37)\)\. Reinforcement learning provides the outcome\-level training signal for such agents\([Shao et al\., 2024](https://arxiv.org/html/2610.08959#bib.bib36)\), and because that signal is sparse and arrives only once per trajectory, on\-policy distillation complements it with dense, step\-level supervision from a teacher policy, typically a frozen snapshot of the student matched via KL divergence at every step\([Zhao et al\., 2026](https://arxiv.org/html/2610.08959#bib.bib11);[Song and Zheng, 2026](https://arxiv.org/html/2610.08959#bib.bib12);[Li et al\., 2026c](https://arxiv.org/html/2610.08959#bib.bib13)\)\. This combination substantially improves sample efficiency on agentic benchmarks\([WANG et al\., 2026](https://arxiv.org/html/2610.08959#bib.bib1);[Liang et al\., 2026](https://arxiv.org/html/2610.08959#bib.bib2)\), yet allocating that step\-level supervision across a trajectory remains an open and challenging problem central to the whole recipe\.

Existing agentic methods answer it by weighting each step by the magnitude of its teacher\-student divergence, on the single\-turn intuition that a large disagreement marks a mistake worth correcting\([Zhong et al\., 2026](https://arxiv.org/html/2610.08959#bib.bib3);[Lu et al\., 2026](https://arxiv.org/html/2610.08959#bib.bib5);[Li et al\., 2026a](https://arxiv.org/html/2610.08959#bib.bib7);[Zhang et al\., 2026b](https://arxiv.org/html/2610.08959#bib.bib4)\), while a parallel line keeps the same magnitude rule but acts on it indirectly, routing the gap into the RL update or enriching the teacher with privileged skills or debate\([Yang et al\., 2026a](https://arxiv.org/html/2610.08959#bib.bib6);[Yang et al\., 2026b](https://arxiv.org/html/2610.08959#bib.bib10);[Wang et al\., 2026c](https://arxiv.org/html/2610.08959#bib.bib8);[Wang et al\., 2026d](https://arxiv.org/html/2610.08959#bib.bib9)\)\. A separate family reweights the RL advantage itself with structure read from the rollout, such as branching or graph\-based credit scores, but leaves the distillation loss unweighted\([Wang et al\., 2026f](https://arxiv.org/html/2610.08959#bib.bib14);[Yuan et al\., 2025](https://arxiv.org/html/2610.08959#bib.bib17)\)\. Across all of these lines the allocation rule remains the single\-turn one, in which the size of the teacher\-student gap, alone or combined with rollout structure on the RL side, decides where supervision goes\.

![Refer to caption](https://arxiv.org/html/2610.08959v1/intro_final.png)Figure 1:Motivating empirical study\.All runs distill only thekkhighest\-KL steps orkkrandomly chosen steps per trajectory,k∈\{5,8,10,12\}k\\in\\\{5,8,10,12\\\}, on ALFWorld with a 7B Qwen2\.5\-Instruct agent under GRPO for 150 steps, all other conditions identical\. \(Left\) Random selection stays ahead at every budgetkk, by\+1\.5\+1\.5to\+3\.2\+3\.2pp in success rate, with the per\-budget gapsΔ\\Deltaannotated above each pair\. \(Middle\) Atk=5k=5the KL\-guided run trails in success rate \(solid curves, left axis\) throughout and ends at 76\.3% against 83\.5% for random, while its policy entropy \(dashed curves, right axis\) contracts as the random run’s expands\. \(Right\) The per\-step KL of 466 successful and 466 failed steps from 50 rollouts overlaps by 84% between the two outcomes, with medians \(dashed\) at 0\.10 and 0\.09, so success and failure are barely separable by divergence\.As shown in Figure[1](https://arxiv.org/html/2610.08959#S1.F1), we test that rule where decisions chain over many turns and find that it fails exactly as the structure of agent trajectories predicts , since distilling thekkhighest\-KL steps brings no consistent benefit over distillingkkrandom steps, the divergence\-guided rule trails random selection throughout training while policy entropy collapses rather than grows, and successful and failed steps barely separate by divergence\. An early drift enters every later context both policies condition on, leaving the teacher locally consistent with the drifted trajectory precisely at the outcome\-deciding steps, and interchangeable steps register large divergences unrelated to the result, so divergence magnitude measures how far the student has drifted rather than whether that drift mattered\. Agent trajectories nevertheless record what divergence cannot see, namely which steps enabled which later ones, readable from environment state transitions rather than from either policy’s predictions, and no prior agentic on\-policy distillation method has used this record to place the teacher’s supervision\.

To this end, in this paper we focus on placing the step\-level supervision where the teacher’s guidance remains usable along a multi\-turn trajectory, and proposeGraphOPD, the first method to introduce graph\-based structural augmentation into on\-policy distillation for improving agent capabilities\. For each rollout, GraphOPD reads which earlier state changes a later action consumes into a directed dependency graph, converts its random\-walk stationary distribution into a per\-step structural credit score, and fuses that score with the divergence signal into a trajectory\-relative mask that spends supervision where the teacher’s guidance is usable, leaving the rest to the RL objective\. The structural score marks the steps at which much of the trajectory’s accumulated dependency structure is resolved, so it stays informative exactly where the teacher\-student gap has been blinded by drift or inflated by interchangeable actions\. Since both signals come from the rollout itself, the mechanism needs no extra model calls and enters training as a drop\-in reweighting of the distillation loss\. We evaluate GraphOPD on ALFWorld, WebShop, and SearchQA across three model scales against eleven baselines, where it shows competitive performance throughout and improves over the strongest baseline by up to\+5\.8 pp\. Analyses further confirm that both signals are independently necessary, that the structural credit score tracks true causal impact far above chance under an executed\-replay audit, and that the same signal transfers to out\-of\-domain tool\-integrated reasoning\.

The main contributions of this paper are summarized as follows:

- •We study the divergence\-magnitude rule on multi\-turn agent benchmarks and find that the teacher\-student gap measures drift rather than outcome relevance, so distilling its highest\-divergence steps brings no consistent benefit over random selection, motivating a drift\-immune supervision signal for long\-horizon agents\.
- •We are the first to bring graph\-based structural augmentation into on\-policy distillation for agents, reading a directed graph from environment state transitions to capture which steps the outcome turns on\.
- •We design GraphOPD, which fuses a random\-walk structural credit score with the divergence signal into a distillation aptitude and converts it into a trajectory\-relative mask that trains alongside the reinforcement\-learning objective\.
- •Experiments across three benchmarks, three scales, and eleven baselines show gains up to \+5\.8 pp over the strongest baseline, with the structural credit score validated by executed\-replay counterfactuals and out\-of\-domain transfer\.

## 2Related Work

#### On\-policy distillation for LLM agents\.

On\-policy distillation augments reinforcement learning with dense token\-level supervision from a teacher evaluated on the student’s own rollout states\([Song and Zheng, 2026](https://arxiv.org/html/2610.08959#bib.bib12);[Li et al\., 2026c](https://arxiv.org/html/2610.08959#bib.bib13)\), and the methods we compare against are either instances of it or bounds on what it can add\. Objective\-level work stabilizes or generalizes the same recipe via target reformulation, entropy\-aware divergences, teacher\-supported truncation, or reward extrapolation\([Jang et al\., 2026](https://arxiv.org/html/2610.08959#bib.bib52);[Jin et al\., 2026](https://arxiv.org/html/2610.08959#bib.bib53);[Fu et al\., 2026](https://arxiv.org/html/2610.08959#bib.bib54);[Yang et al\., 2026c](https://arxiv.org/html/2610.08959#bib.bib55)\)\. Among the on\-policy methods, OPSD\([Zhao et al\., 2026](https://arxiv.org/html/2610.08959#bib.bib11)\)distills the student’s own frozen snapshot over its rollouts and SDAR\([Lu et al\., 2026](https://arxiv.org/html/2610.08959#bib.bib5)\)applies the same recipe to multi\-turn agent rollouts, RLSD\([Yang et al\., 2026a](https://arxiv.org/html/2610.08959#bib.bib6)\)routes the teacher\-student gap into the RL objective as advantage shaping or update magnitude, and OPID\([Yang et al\., 2026b](https://arxiv.org/html/2610.08959#bib.bib10)\)distills on\-policy from a teacher augmented with privileged skill context\. Skill\-GRPO and Skill\-SD\([Wang et al\., 2026c](https://arxiv.org/html/2610.08959#bib.bib8)\)injecting external skill demonstrations or conditioning self\-distillation on them\. Each on\-policy baseline allocates supervision by the magnitude of the teacher\-student divergence, which is the shared premise our empirical study tests\.

#### Step\-level weighting and structural credit assignment\.

Beyond our comparison set, on\-policy distillation has been extended along three axes, controlling when to distill through temporal curricula\([WANG et al\., 2026](https://arxiv.org/html/2610.08959#bib.bib1);[Liang et al\., 2026](https://arxiv.org/html/2610.08959#bib.bib2)\), how strongly to supervise each step from the divergence through gating, granularity adaptation, or advantage routing\([Zhong et al\., 2026](https://arxiv.org/html/2610.08959#bib.bib3);[Li et al\., 2026a](https://arxiv.org/html/2610.08959#bib.bib7);[Zhang et al\., 2026b](https://arxiv.org/html/2610.08959#bib.bib4)\), and how reliable the teacher is through debate, rollout\-tested guidance, or bounded update magnitudes\([Wang et al\., 2026d](https://arxiv.org/html/2610.08959#bib.bib9);[Chen et al\., 2026](https://arxiv.org/html/2610.08959#bib.bib23);[Liu et al\., 2026](https://arxiv.org/html/2610.08959#bib.bib27);[Wang et al\., 2026g](https://arxiv.org/html/2610.08959#bib.bib26);[Sun et al\., 2026](https://arxiv.org/html/2610.08959#bib.bib29)\)\. A separate family reweights the RL advantage rather than the distillation loss using structure read from the rollout: branching and graph\-based credit scores\([Wang et al\., 2026f](https://arxiv.org/html/2610.08959#bib.bib14);[Yuan et al\., 2025](https://arxiv.org/html/2610.08959#bib.bib17);[Yuan et al\., 2026](https://arxiv.org/html/2610.08959#bib.bib20);[Li et al\., 2026b](https://arxiv.org/html/2610.08959#bib.bib21);[da Costa Cunha et al\., 2026](https://arxiv.org/html/2610.08959#bib.bib19)\), dependency and memory graphs\([Wang et al\., 2026e](https://arxiv.org/html/2610.08959#bib.bib15);[Nussbaum\-Hoffer et al\., 2026](https://arxiv.org/html/2610.08959#bib.bib16);[Wang et al\., 2026b](https://arxiv.org/html/2610.08959#bib.bib22)\), verifier\- or Shapley\-based edge credit\([Wang et al\., 2021](https://arxiv.org/html/2610.08959#bib.bib18)\), milestone and rubric judgments\([Zhang et al\., 2026a](https://arxiv.org/html/2610.08959#bib.bib25)\), and bisimulation or transport distances to a reference plan\([Wang et al\., 2026a](https://arxiv.org/html/2610.08959#bib.bib28)\)\. Beyond agent RL, graphs underlie self\-correcting knowledge\-graph planning\([Chen et al\., 2024](https://arxiv.org/html/2610.08959#bib.bib46)\), multi\-modal entity alignment\([Chen et al\., 2020](https://arxiv.org/html/2610.08959#bib.bib48);[Chen et al\., 2022](https://arxiv.org/html/2610.08959#bib.bib49)\), temporal or de\-correlated recommendation\([Zhang et al\., 2024](https://arxiv.org/html/2610.08959#bib.bib47);[Wu et al\., 2024](https://arxiv.org/html/2610.08959#bib.bib50)\), and video social\-graph generation\([Wu et al\., 2021](https://arxiv.org/html/2610.08959#bib.bib51)\)\. None of these represent, for the distillation loss, which steps the later ones actually depend on, and that is what GraphOPD reads directly from the trajectory\.

## 3Method

GraphOPD fuses two per\-step signals into a single distillation weight\. The first is a structural credit signal that identifies which steps in a trajectory were critical to its outcome, derived from a lightweight dependency graph built over the steps’ entity\-level relations and scored with a random\-walk stationary distribution\. The second is the divergence signal used by prior on\-policy distillation methods, measuring how far the student’s behavior has drifted from the teacher’s\. GraphOPD combines the two into a trajectory\-relative per\-step weight that spends distillation only where the teacher’s guidance is both trustworthy and useful, leaving the rest to the RL objective\. Figure[2](https://arxiv.org/html/2610.08959#S3.F2)summarizes the full pipeline\.

![Refer to caption](https://arxiv.org/html/2610.08959v1/figures/graph.png)Figure 2:GraphOPD overview\.From a single rollout, two per\-step signals are computed in parallel, a structural credit signal from the Footprint\-built dependency graph and its random\-walk stationary distribution, and a divergence signal from the teacher\-student gap normalized within the trajectory\. The two are fused into a distillation aptitudeA⁡\(t\)A\(t\), converted into a trajectory\-relative maskm⁡\(t\)m\(t\), and the resulting masked distillation loss is added to the unweighted GRPO objective; every stage reads only the rollout itself and needs no extra model calls\.### 3\.1Problem Setup

We consider an agent that interacts with an environment overTTsteps and produces a trajectoryτ=\(s0,a1,o1,…,aT,oT\)\\tau=\(s\_\{0\},a\_\{1\},o\_\{1\},\\ldots,a\_\{T\},o\_\{T\}\), where at each steptt, against environment statests\_\{t\}, the agent emits actionata\_\{t\}and the environment returns observationoto\_\{t\}; the action and observation text are what our Footprint extractor reads\. A terminal rewardRR, issued only once at the end of the episode, encodes task success or failure, and no dense per\-step reward is assumed\.

The student policyπθ\\pi\_\{\\theta\}is trained under GRPO, augmented by a teacher signal at each step\. We take the teacher to beπθold\\pi\_\{\\theta\_\{\\text\{old\}\}\}, the student’s snapshot frozen at the start of each rollout batch and already used by GRPO for the importance ratio\. Staying within one update of the current policy, it serves as an on\-support behavioral anchor rather than an external expert\.

### 3\.2Structural Credit Assignment

#### Assigning credit without a dense reward\.

With only a terminal reward, a trajectory offers no direct signal for which of its steps actually mattered\. Agent actions constrain what is possible later, and this directed structure is readable from action and observation text alone, without LLM calls, privileged annotations, or rollout counterfactuals\. We use it as a proxy for step\-level credit, made explicit through a lightweight graphG=\(V,E,w\)G=\(V,E,w\), with one nodevt∈Vv\_\{t\}\\in Vper step, built from a rule\-based*State Transition Footprint*ℱ⁡\(t\)\\mathcal\{F\}\(t\)of entity\-level state\-change keys

ℱ\(t\)=ℱenv\(at,ot\)⊆\{<type\>:<entity\>\}\.\\mathcal\{F\}\(t\)=\\mathcal\{F\}\_\{\\text\{env\}\}\(a\_\{t\},\\,o\_\{t\}\)\\;\\subseteq\\;\\bigl\\\{\\,\\texttt\{<type\>:<entity\>\}\\,\\bigr\\\}\.\(1\)Full extractor specifications are in Appendix[A](https://arxiv.org/html/2610.08959#A1)\.

#### Edge construction\.

A directed edgevi→vjv\_\{i\}\\to v\_\{j\}\(i<ji<j\) is added whenever stepii’s state change is explicitly referenced by stepjj’s action,

\(vi→vj\)∈E⇔∃<type\>:<entity\>∈ℱ\(i\)s\.t\.<entity\>∈substr\(aj\)\.\(v\_\{i\}\\\!\\to\\\!v\_\{j\}\)\\in E\\;\\iff\\;\\exists\\;\\texttt\{<type\>:<entity\>\}\\in\\mathcal\{F\}\(i\)\\;\\text\{ s\.t\. \}\\;\\texttt\{<entity\>\}\\in\\mathrm\{substr\}\(a\_\{j\}\)\.\(2\)Two auxiliary types complete the graph\.*Backtrack edges*of weight0\.50\.5connectjjback to an earlieriiwheneveroj=oio\_\{j\}=o\_\{i\}, marking a revisit, and*sequential edges*of weight0\.050\.05connect consecutive steps lacking a dependency or backtrack edge, preserving connectivity for the centrality computation\.

#### Soft pruning by entity specificity\.

Substring matching can admit spurious dependency edges through high\-frequency entities that co\-occur with many steps without carrying a specific dependency\. Rather than a constant weight, we weight each dependency edge by the rarity of the entity that induces it\. Letd​f​\(e\)df\(e\)be the number of steps in the trajectory whose action or observation mentions entityee, and the dependency\-edge weight is

w⁡\(vi→vj\)=1d​f​\(e\),w\(v\_\{i\}\\to v\_\{j\}\)=\\frac\{1\}\{df\(e\)\},\(3\)whereeeis the matched entity, or the rarest one if several match\. An entity mentioned once or twice yields weight near11, and a ubiquitous entity yields a small weight that is diluted once the stationary distribution’s row normalization is applied\. This soft pruning introduces no hyperparameter and leaves the backtrack and sequential edges unchanged\.

#### What the dependency graph encodes\.

The edges ofGGrecord which earlier state changes a later action actually consumes\. That is an enabling relation in the environment dynamics and a factual property of the recorded rollout, so it does not inherit the noise affecting the KL\-based divergence signal in long\-horizon settings\. We accordingly treatℓgraph\\ell\_\{\\text\{graph\}\}as a*structural credit score*, measuring how much of the trajectory’s later behavior runs through a given step\. Whether that structural quantity tracks the steps the outcome really turns on is an empirical question, and we settle it with an executed\-replay counterfactual audit in our experiments\. Because a step’s stationary mass is the rarity\-weighted inflow of every dependency chain its action consumes, intermediate milestones at which several upstream state changes meet score above the neutral point just as terminal actions do, and the trajectory\-relative mask ranks steps within their own rollout rather than by position\.

### 3\.3Structural Credit and Divergence Signals

#### Structural credit signalℓgraph\\ell\_\{\\text\{graph\}\}\.

Counting only direct dependency edges misses transitive importance, so we use a random\-walk stationary distribution over the graph, which propagates influence along edges rather than only counting them\. LetM∈ℝT×TM\\in\\mathbb\{R\}^\{T\\times T\}be the row\-normalized edge\-weight matrix, in which leaf nodes receive a uniform row1/T1/T\. With dampingd=0\.15d=0\.15and uniform teleport𝐮=\[1/T,…,1/T\]⊤\\mathbf\{u\}=\[1/T,\\ldots,1/T\]^\{\\top\}, the stationary distribution satisfies

𝝅∗=\(1−d\)​𝝅∗​M\+d​𝐮⊤\.\\bm\{\\pi\}^\{\*\}=\(1\-d\)\\,\\bm\{\\pi\}^\{\*\}M\+d\\,\\mathbf\{u\}^\{\\top\}\.\(4\)Mass flows forward along the dependency edges, peaking at convergence points where the preconditions assembled earlier are exercised and the outcome is decided\. We convert it to log\-odds relative to the uniform baseline,

ℓgraph​\(t\)=log⁡\(T⋅πt∗\),\\ell\_\{\\text\{graph\}\}\(t\)=\\log\(T\\cdot\\pi^\{\*\}\_\{t\}\),\(5\)which givesℓgraph​\(t\)\>0\\ell\_\{\\text\{graph\}\}\(t\)\>0above average and00at uniform, matching the neutral point of the divergence signal defined next\.

#### Divergence signalℓmodel\\ell\_\{\\text\{model\}\}\.

The divergence signal measures how much the student’s step\-ttbehavior differs from the teacher’s\. Raw KL is dominated by global training\-stage drift, so we use each step’s deviation relative to the trajectory, namely the mean absolute token log\-probability difference over the student’s action tokensStS\_\{t\},

δ⁡\(t\)=1\|St\|​∑k∈St\|log⁡πθold​\(k∣st\)−log⁡πθ​\(k∣st\)\|\.\\delta\(t\)=\\frac\{1\}\{\|S\_\{t\}\|\}\\sum\_\{k\\in S\_\{t\}\}\\bigl\|\\log\\pi\_\{\\theta\_\{\\text\{old\}\}\}\(k\\mid s\_\{t\}\)\-\\log\\pi\_\{\\theta\}\(k\\mid s\_\{t\}\)\\bigr\|\.\(6\)We then convert the relative deviationrt=δ⁡\(t\)/δmax∈\[0,1\]r\_\{t\}=\\delta\(t\)/\\delta\_\{\\text\{max\}\}\\in\[0,1\]to a smoothed within\-trajectory log\-odds score

ℓmodel​\(t\)=log⁡\[rt\+ε1−rt\+ε\],δmax=maxt′∈τ⁡δ⁡\(t′\),\\ell\_\{\\text\{model\}\}\(t\)=\\log\\\!\\left\[\\frac\{r\_\{t\}\+\\varepsilon\}\{1\-r\_\{t\}\+\\varepsilon\}\\right\],\\quad\\delta\_\{\\text\{max\}\}=\\max\_\{t^\{\\prime\}\\in\\tau\}\\delta\(t^\{\\prime\}\),\(7\)with smoothing floorε=0\.1\\varepsilon=0\.1\. The score is00at mid\-deviation, wherert=12r\_\{t\}=\\tfrac\{1\}\{2\}, matchingℓgraph\\ell\_\{\\text\{graph\}\}’s neutral point, and the floor bounds it to±log⁡1\+εε≈±2\.4\\pm\\log\\frac\{1\+\\varepsilon\}\{\\varepsilon\}\\approx\\pm 2\.4, the same order as\|ℓgraph\|≤log⁡T\|\\ell\_\{\\text\{graph\}\}\|\\leq\\log T\. The two signals are therefore commensurate and either source can veto the other, while the within\-trajectory normalization keeps them comparable across training stages\.

### 3\.4Distillation Aptitude, Masking, and Training Objective

#### Fusing the two signals into a distillation aptitude\.

Both signals already share a common footing, since each is zero at its own neutral point and positive above it, and theε\\varepsilon\-floor in Eq\. equation[7](https://arxiv.org/html/2610.08959#S3.E7)keepsℓmodel\\ell\_\{\\text\{model\}\}on the same order asℓgraph\\ell\_\{\\text\{graph\}\}’s±log⁡T\\pm\\log Trange established above, so neither can unilaterally dominate the other\. We combine them by a weighted sum

A⁡\(t\)=α⋅ℓmodel​\(t\)\+\(1−α\)⋅ℓgraph​\(t\),A\(t\)=\\alpha\\cdot\\ell\_\{\\text\{model\}\}\(t\)\+\(1\-\\alpha\)\\cdot\\ell\_\{\\text\{graph\}\}\(t\),\(8\)the*Distillation Aptitude*\.A⁡\(t\)A\(t\)is high when both sources agree, meaning the student has drifted*and*the step is central, and it stays attenuated when the two disagree\.α\\alphais selected by grid search on a validation split, withα=1\\alpha=1recovering divergence\-only weighting andα=0\\alpha=0recovering pure structural\-credit weighting\.

#### Trajectory\-relative mask and training objective\.

The absolute scale ofA⁡\(t\)A\(t\)is not stable across training, becauseδmax\\delta\_\{\\text\{max\}\}and the graph’s stationary distribution both shift as the policy changes, so a fixed threshold onA⁡\(t\)A\(t\)would need constant re\-tuning\. We instead standardizeA⁡\(t\)A\(t\)within its own trajectory before masking\. Withμτ\\mu\_\{\\tau\}andsτs\_\{\\tau\}the mean and standard deviation of\{A⁡\(t\)\}t=1T\\\{A\(t\)\\\}\_\{t=1\}^\{T\}overτ\\tau,

m⁡\(t\)=σ⁡\(A⁡\(t\)−μτsτ\),m\(t\)=\\sigma\\\!\\left\(\\frac\{A\(t\)\-\\mu\_\{\\tau\}\}\{s\_\{\\tau\}\}\\right\),\(9\)som⁡\(t\)\>12m\(t\)\>\\tfrac\{1\}\{2\}exactly when steptt’s aptitude exceeds its own trajectory’s average, and this relative threshold stays meaningful at every stage of training because it is defined againstτ\\tauitself rather than against a fixed scale\. Every trajectory thus spends its own distillation budget on its own most decisive steps, independent of trajectory length, dependency density, or how far training has progressed\. Design and numerical details, including the degeneratesτ=0s\_\{\\tau\}=0case, are deferred to Appendix[B](https://arxiv.org/html/2610.08959#A2)\.

The distillation loss aggregates the masked forward KL over each trajectory step, normalized by the total mask weight,

ℒGraphOPD=1∑tm⁡\(t\)∑t=1Tm\(t\)⋅KL\(πθold\(⋅∣st\)∥πθ\(⋅∣st\)\)\.\\mathcal\{L\}\_\{\\text\{GraphOPD\}\}=\\frac\{1\}\{\\sum\_\{t\}m\(t\)\}\\sum\_\{t=1\}^\{T\}m\(t\)\\cdot\\mathrm\{KL\}\\\!\\bigl\(\\pi\_\{\\theta\_\{\\text\{old\}\}\}\(\\cdot\\mid s\_\{t\}\)\\,\\\|\\,\\pi\_\{\\theta\}\(\\cdot\\mid s\_\{t\}\)\\bigr\)\.\(10\)This loss is combined with the GRPO policy gradient objective as

ℒtotal=ℒGRPO\+λ⋅ℒGraphOPD,\\mathcal\{L\}\_\{\\text\{total\}\}=\\mathcal\{L\}\_\{\\text\{GRPO\}\}\+\\lambda\\cdot\\mathcal\{L\}\_\{\\text\{GraphOPD\}\},\(11\)whereλ=0\.05\\lambda=0\.05sets the weight of the distillation term relative to the RL objective and is held fixed across all benchmarks and scales\. GraphOPD is implemented as a drop\-in wrapper around the training loop, and Algorithm[1](https://arxiv.org/html/2610.08959#alg1)summarizes the full pipeline\.

## 4Experiments

### 4\.1Experimental Setup

We evaluate on three agentic benchmarks, ALFWorld\([Shridhar et al\., 2021](https://arxiv.org/html/2610.08959#bib.bib33)\), WebShop\([Yao et al\., 2022](https://arxiv.org/html/2610.08959#bib.bib34)\), and SearchQA, a suite of seven open\-domain question\-answering datasets\([Kociský et al\., 2018](https://arxiv.org/html/2610.08959#bib.bib38);[Joshi et al\., 2017](https://arxiv.org/html/2610.08959#bib.bib39);[Mallen et al\., 2023](https://arxiv.org/html/2610.08959#bib.bib40);[Yang et al\., 2018](https://arxiv.org/html/2610.08959#bib.bib37);[Ho et al\., 2020](https://arxiv.org/html/2610.08959#bib.bib41);[Trivedi et al\., 2022](https://arxiv.org/html/2610.08959#bib.bib42);[Press et al\., 2023](https://arxiv.org/html/2610.08959#bib.bib43)\), scored by episode success rate, by success rate together with completion score, and by exact\-match accuracy respectively; the per\-benchmark average columns are the headline numbers quoted in the text\. All methods share the same GRPO\([Shao et al\., 2024](https://arxiv.org/html/2610.08959#bib.bib36)\)backbone implemented inveRL\([Sheng et al\., 2025](https://arxiv.org/html/2610.08959#bib.bib30)\)and are trained at three model scales, Qwen3\-1\.7B\([Yang et al\., 2025](https://arxiv.org/html/2610.08959#bib.bib32)\), Qwen2\.5\-3B\-Instruct and Qwen2\.5\-7B\-Instruct\([Yang et al\., 2024](https://arxiv.org/html/2610.08959#bib.bib31)\), against eleven baselines; baseline families, prompts, training configurations, and the run\-variance table are detailed in Appendix[C](https://arxiv.org/html/2610.08959#A3)\.

### 4\.2Main Results

GraphOPD turns the dependency structure of a trajectory into a training signal that existing on\-policy distillation methods do not use, and Table[1](https://arxiv.org/html/2610.08959#S4.T1)shows this signal translating directly into consistent gains\. The advantage is most direct on the two benchmarks that require sustained manipulation of an environment over many turns, where GraphOPD attains the best average success rate on ALFWorld and the best success rate on WebShop at every model scale, ahead of all eleven baselines, peaking at 91\.9% ALFWorld success and 83\.6% WebShop success at 7B\. The margin over GEPO, the closest prior baseline, which reweights the GRPO advantage with a graph\-based credit score rather than adding a distillation loss, is positive at every scale, reaching \+5\.2 to \+7\.9 pp on ALFWorld and \+3\.6 to \+5\.5 pp on WebShop success rate\. GraphOPD also outperforms the skill\-augmented baselines that receive privileged demonstrations or validated skill libraries, such as Skill\-GRPO and GRPO\+OPSD, on both benchmarks at every scale, despite reading its own signal for free from the rollout rather than from external supervision\. The same structural signal also carries over to SearchQA, a retrieval\-and\-reasoning setting with a substantially different action space, where GraphOPD leads at 3B and 1\.7B with 46\.1 and 42\.9 average accuracy, ahead of every direct\-comparison baseline, and stays competitive at 7B\. The margin over SDAR is positive on both benchmarks at every scale, at\+12\.0 ppon ALFWorld and\+13\.5 ppon WebShop at 1\.7B,\+6\.8 ppand\+9\.6 ppat 3B, and\+7\.5 ppand\+1\.6 ppat 7B\. The run\-to\-run standard deviations behind these means, given in Table[7](https://arxiv.org/html/2610.08959#A3.T7), confirm that the comparisons sit within reasonable fluctuation: GraphOPD’s own spread never exceeds 1\.6 pp and stays below 0\.6 pp in seven of the nine headline cells, well under half the largest baseline spreads of about 5 pp\.

Table 1:Main results\.Success rate \(ALFWorld\), accuracy \(SearchQA\), and success rate \(WebShop\) across three model scales\.Boldandunderlinemarks the best and the second best result per column within each model block\.
### 4\.3Ablation Study

We ablate four design choices to isolate each component’s contribution, and add a shuffled\-centrality control to test whether the gain comes from the structural credit signal’s content or from the mere act of non\-uniform weighting\. Table[2](https://arxiv.org/html/2610.08959#S4.T2)reports results on WebShop, SearchQA, and ALFWorld\. Divergence\-only, which drops the structural credit signal, costs 3\.9 to 10\.5 pp, so the structural credit signal carries substantial information about which steps matter\. Structural\-only, which drops the divergence signal, is also necessary at 2\.3 to 6\.5 pp, and the two signals therefore act as complements rather than substitutes\. Soft\-Pruning, which replaces the entity\-specificity dependency\-edge weighting with a constant weight, costs 0\.8 to 5\.5 pp, less than dropping either signal outright at every one of the nine benchmark\-scale cells\. Shuffled Centrality keeps the mask’s sparsity and weight distribution but randomizes which step receives which weight\. At 7B, and on WebShop and ALFWorld at 3B, it costs*more*than Divergence\-only by up to 1\.6 pp, so misassigning the structural credit scores to the wrong steps hurts more than having no structural signal at all\. At 1\.7B, and on SearchQA at 3B, the pattern reverses and Shuffled costs no more than Divergence\-only, most sharply on SearchQA at 1\.7B, where the two cost 2\.8 pp and 10\.5 pp respectively\. At the smallest scale, then, the redistribution of supervision weight itself carries part of the structural credit signal’s benefit\.

Table 2:Ablation study\.Success rate \(WebShop\), accuracy \(SearchQA\), and success rate \(ALFWorld\)\. Variant definitions are given in the text above, and the GraphOPD row reproduces the three\-run means of the full method, while each ablation variant is a single\-run point estimate\.Boldmarks the best result per column within each model block\.#### Hyperparameter sensitivity\.

Table 3:ALFWorld and WebShop success rate in percent for Qwen2\.5\-7B\-Instruct across the signal\-mixing coefficientα\\alpha\.We select the mixing coefficientα\\alphaby grid search on the ALFWorld validation split, fixing the distillation loss coefficientλ=0\.05\\lambda=0\.05, and the selected configuration ofα=0\.5\\alpha=0\.5withλ=0\.05\\lambda=0\.05is reported alongside theα\\alphasweep\. The sweep confirms that the gain comes from fusing both signals, since on both ALFWorld and WebShop in Table[3](https://arxiv.org/html/2610.08959#S4.T3)every otherα\\alphaunderperforms the selectedα=0\.5\\alpha=0\.5, with a consistent asymmetric cost at the pure\-signal endpoints of about 4\.0 to 4\.4 pp for dropping the structural credit signal atα=1\\alpha=1against 2\.3 to 2\.8 pp for dropping the divergence signal atα=0\\alpha=0\. The structural credit signal is therefore the larger single\-signal contributor\.

### 4\.4Analysis

![Refer to caption](https://arxiv.org/html/2610.08959v1/exp_final.png)Figure 3:Analysis\.\(Left\) Average graph nodes, equivalently trajectory length, average edges, and average density of the dependency graphs built on ALFWorld at 7B over the 150 training steps; nodes and edges fall from about 47 and 39 to a plateau of 25 to 30 while density rises from about 0\.03 to between 0\.10 and 0\.14, so trajectories grow shorter and denser\. \(Middle\) Accuracy radar on the four out\-of\-domain tool\-integrated\-reasoning benchmarks, AIME24 and AIME25 under avg@32 and LiveCodeBench\-v5 and GPQA\-Diamond under avg@8, plus their average, for GraphOPD against Vanilla, GRPO, OPSD, and SDAR; the GraphOPD polygon dominates every axis, averaging 29\.0% against 20\.0% for SDAR\. Figure[3](https://arxiv.org/html/2610.08959#S4.F3)\(right\) makes the mechanism concrete on a fragment of one real successful ALFWorld trajectory, where raw KL peaks at a cabinet revisit that never decides the outcome whileℓgraph\\ell\_\{\\text\{graph\}\}peaks at the decisive object\-placement step within this fragment\.#### Dependency graph structure over training\.

Figure[3](https://arxiv.org/html/2610.08959#S4.F3)\(left\) tracks how GraphOPD reshapes the dependency graph over training, testing whether centrality\-weighted supervision pushes the policy toward shorter, more decisive trajectories rather than merely re\-weighting its existing behavior\. It does, since the average number of graph nodes, equivalently trajectory length, and the average number of edges both fall over the first 150 steps, from about 47 and 39 at initialization to a plateau around 25 to 30, while graph density rises correspondingly from about 0\.03 to between 0\.10 and 0\.14, consistent with the policy reaching the goal through fewer, more decisive actions rather than the same actions simply being scored differently\.

#### Credit\-content audit\.

Table 4:Credit\-content audit on ALFWorld at 7B\.Metrics defined in the text\.Table[4](https://arxiv.org/html/2610.08959#S4.T4)validates the structural credit signal\. The ablations show that the structural credit signal improves outcomes, and the audit tests directly whether it tracks the steps that decide the outcome, via executed replay\([Zhang, 2026](https://arxiv.org/html/2610.08959#bib.bib24)\)\. For 30 trajectories of the trained 7B policy we sample 10 decision steps per trajectory, re\-sample 4 alternative actions at each, roll forward to the horizon, and take the induced change in success as ground\-truth impact\. For each signal we report the Spearman correlationρ\\rhowith this impact and Hit@10%, the fraction of its top\-10% predicted steps that are truly top\-10% impactful, for which chance is0\.100\.10\.ℓgraph\\ell\_\{\\text\{graph\}\}scoresρ=0\.58\\rho=0\.58with Hit@10%=0\.48=0\.48, clearly above both the random baseline atρ=−0\.06\\rho=\-0\.06and Hit@10%=0\.13=0\.13andℓmodel\\ell\_\{\\text\{model\}\}atρ=0\.34\\rho=0\.34and Hit@10%=0\.41=0\.41\. The structural credit signal thus identifies outcome\-relevant steps more reliably than the divergence gap alone, and the Shuffled Centrality control isolates this same gain from mere non\-uniform weighting\.

#### Generalization and case study\.

Figure[3](https://arxiv.org/html/2610.08959#S4.F3)\(middle\) tests whether the dependency\-graph mechanism transfers beyond the three agentic benchmarks to a different domain and tool, on AIME24, AIME25, LiveCodeBench\-v5, and GPQA\-Diamond run as tool\-integrated reasoning in mathematics, science, and code against Vanilla, GRPO, OPSD, and SDAR under the same backbone and Qwen2\.5\-7B\-Instruct, and scored by avg@32 on the two AIME sets and avg@8 on the other two\. GraphOPD attains the best accuracy on all four, averaging 29\.0% against 20\.0% for SDAR and 19\.8% for OPSD, a \+9\.0 pp average gain over SDAR that reaches \+12\.4 pp on LiveCodeBench\-v5; its lead is the one pattern holding on every benchmark, showing that the structural signal transfers where weighting by distributional deviation alone does not\. Prompts, the Footprint extractor, and the full result table are in Appendix[D](https://arxiv.org/html/2610.08959#A4)\. Figure[3](https://arxiv.org/html/2610.08959#S4.F3)\(right\) makes the mechanism concrete on a fragment of one real successful ALFWorld trajectory, where raw KL peaks at a cabinet revisit that never decides the outcome whileℓgraph\\ell\_\{\\text\{graph\}\}peaks at the decisive object\-placement step within this fragment\.

## 5Conclusion

We presentedGraphOPD, which reads a per\-step structural credit score from the trajectory and fuses it with the divergence signal to decide where a teacher’s guidance is usable, distilling only each rollout’s above\-average\-aptitude steps\. Across three model scales, eleven baselines, and three agentic benchmarks spanning embodied control, web navigation, and retrieval\-augmented reasoning, GraphOPD attains the best result on ALFWorld and WebShop at every scale, with a margin over the strongest baseline that reaches\+5\.8 ppon ALFWorld and\+5\.5 ppon WebShop, and the same structural signal proves effective on SearchQA as well, extending the approach to a substantially different action space\. Ablations confirm that both signals are independently necessary, with the structural credit signal the larger contributor\. Using an LLM to extract the Footprint directly from raw trajectories, rather than through hand\-specified parsing rules, is a natural next step toward applying GraphOPD to a still broader range of agentic domains\.

## AI use statement

In this work, we used generative AI tools to aid and polish the writing of portions of the manuscript, including revising selected passages for clarity and readability\. Additionally, we used generative AI tools for retrieval and discovery, e\.g\., finding and screening related work and prior publications relevant to this study\. We did not use generative AI tools for any other applicable tasks requiring disclosure beyond those stated here\. We have reviewed all AI\-assisted work\. All AI\-assisted textual revisions were checked by the authors to ensure that they preserved the intended meaning and accurately reflected the work, and every candidate reference surfaced through AI\-assisted retrieval was independently located, read, and verified against its original source before being cited\. We take responsibility for the final content of this work, including text, claims, and artifacts produced with the aid of generative AI\.

## Reproducibility Statement

All benchmarks used in this work are publicly available\. All the training code is released at the URL given in the abstract and included in the Supplementary Material; the method, hyperparameters, baseline reproduction details, prompts, and audit protocol are fully specified in the paper and its appendix\.

## References

- Chenet al\.\(2026\)C\. Chen, Y\. Fan, T\. Sun, Y\. Yang, C\. Sun, D\. Mao, H\. Qiao, Z\. Zhang, J\. Wang, C\. Sun, Y\. Hu, L\. Pan, X\. Liu, and L\. ZhangLook ahead before you distill: future trajectory validation of teacher guidance for agentic on\-policy distillation\.CoRRabs/2608\.01953\.External Links:[Link](https://doi.org/10.48550/arXiv.2608.01953),[Document](https://dx.doi.org/10.48550/ARXIV.2608.01953),2608\.01953Cited by:[§2](https://arxiv.org/html/2610.08959#S2.SS0.SSS0.Px2.p1.1)\.
- Chenet al\.\(2020\)L\. Chen, Z\. Li, Y\. Wang, T\. Xu, Z\. Wang, and E\. ChenMMEA: entity alignment for multi\-modal knowledge graph\.InKnowledge Science, Engineering and Management \- 13th International Conference, KSEM 2020, Hangzhou, China, August 28\-30, 2020, Proceedings, Part I,G\. Li, H\. T\. Shen, Y\. Yuan, X\. Wang, H\. Liu, and X\. Zhao \(Eds\.\),Lecture Notes in Computer Science, Vol\.12274,pp\. 134–147\.External Links:[Link](https://doi.org/10.1007/978-3-030-55130-8/_12),[Document](https://dx.doi.org/10.1007/978-3-030-55130-8%5F12)Cited by:[§2](https://arxiv.org/html/2610.08959#S2.SS0.SSS0.Px2.p1.1)\.
- Chenet al\.\(2022\)L\. Chen, Z\. Li, T\. Xu, H\. Wu, Z\. Wang, N\. J\. Yuan, and E\. ChenMulti\-modal siamese network for entity alignment\.InKDD ’22: The 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, Washington, DC, USA, August 14 \- 18, 2022,A\. Zhang and H\. Rangwala \(Eds\.\),pp\. 118–126\.External Links:[Link](https://doi.org/10.1145/3534678.3539244),[Document](https://dx.doi.org/10.1145/3534678.3539244)Cited by:[§2](https://arxiv.org/html/2610.08959#S2.SS0.SSS0.Px2.p1.1)\.
- Chenet al\.\(2024\)L\. Chen, P\. Tong, Z\. Jin, Y\. Sun, J\. Ye, and H\. XiongPlan\-on\-graph: self\-correcting adaptive planning of large language model on knowledge graphs\.InAdvances in Neural Information Processing Systems 37: Annual Conference on Neural Information Processing Systems 2024, NeurIPS 2024, Vancouver, BC, Canada, December 10 \- 15, 2024,A\. Globersons, L\. Mackey, D\. Belgrave, A\. Fan, U\. Paquet, J\. M\. Tomczak, and C\. Zhang \(Eds\.\),External Links:[Link](http://papers.nips.cc/paper/_files/paper/2024/hash/4254e856d01a5e7b7ea050477c3ef9b9-Abstract-Conference.html)Cited by:[§2](https://arxiv.org/html/2610.08959#S2.SS0.SSS0.Px2.p1.1)\.
- da Costa Cunhaet al\.\(2026\)C\. da Costa Cunha, A\. Mian, T\. French, and W\. LiuCausal reinforcement learning for complex card games: A magic the gathering benchmark\.CoRRabs/2605\.06066\.External Links:[Link](https://doi.org/10.48550/arXiv.2605.06066),[Document](https://dx.doi.org/10.48550/ARXIV.2605.06066),2605\.06066Cited by:[§2](https://arxiv.org/html/2610.08959#S2.SS0.SSS0.Px2.p1.1)\.
- Fuet al\.\(2026\)Y\. Fu, H\. Huang, K\. Jiang, J\. Liu, Z\. Jiang, Y\. Zhu, and D\. ZhaoRevisiting on\-policy distillation: empirical failure modes and simple fixes\.InThird Conference on Language Modeling,External Links:[Link](https://openreview.net/forum?id=uZbZb058bA)Cited by:[§2](https://arxiv.org/html/2610.08959#S2.SS0.SSS0.Px1.p1.1)\.
- Hoet al\.\(2020\)X\. Ho, A\. D\. Nguyen, S\. Sugawara, and A\. AizawaConstructing A multi\-hop QA dataset for comprehensive evaluation of reasoning steps\.InProceedings of the 28th International Conference on Computational Linguistics, COLING 2020, Barcelona, Spain \(Online\), December 8\-13, 2020,D\. Scott, N\. Bel, and C\. Zong \(Eds\.\),pp\. 6609–6625\.External Links:[Link](https://doi.org/10.18653/v1/2020.coling-main.580),[Document](https://dx.doi.org/10.18653/V1/2020.COLING-MAIN.580)Cited by:[Appendix C](https://arxiv.org/html/2610.08959#A3.SS0.SSS0.Px1.p1.1),[§4\.1](https://arxiv.org/html/2610.08959#S4.SS1.p1.1)\.
- Janget al\.\(2026\)I\. Jang, J\. W\. Yeom, J\. Yeo, H\. Lim, and T\. KimStable on\-policy distillation through adaptive target reformulation\.InFindings of the Association for Computational Linguistics, ACL 2026, San Diego, California, United States, July 2\-7, 2026,M\. Liakata, V\. P\. Moreira, J\. Zhang, and D\. Jurgens \(Eds\.\),pp\. 42217–42227\.External Links:[Link](https://doi.org/10.18653/v1/2026.findings-acl.2094),[Document](https://dx.doi.org/10.18653/V1/2026.FINDINGS-ACL.2094)Cited by:[§2](https://arxiv.org/html/2610.08959#S2.SS0.SSS0.Px1.p1.1)\.
- Jinet al\.\(2026\)W\. Jin, T\. Min, Y\. Yang, D\. Wei, Y\. Zhou, S\. R\. Kadhe, N\. Baracaldo, and K\. LeeEntropy\-aware on\-policy distillation of language models\.InForty\-third International Conference on Machine Learning,External Links:[Link](https://openreview.net/forum?id=J5i09faOOf)Cited by:[§2](https://arxiv.org/html/2610.08959#S2.SS0.SSS0.Px1.p1.1)\.
- Joshiet al\.\(2017\)M\. Joshi, E\. Choi, D\. S\. Weld, and L\. ZettlemoyerTriviaQA: A large scale distantly supervised challenge dataset for reading comprehension\.InProceedings of the 55th Annual Meeting of the Association for Computational Linguistics, ACL 2017, Vancouver, Canada, July 30 \- August 4, Volume 1: Long Papers,R\. Barzilay and M\. Kan \(Eds\.\),pp\. 1601–1611\.External Links:[Link](https://doi.org/10.18653/v1/P17-1147),[Document](https://dx.doi.org/10.18653/V1/P17-1147)Cited by:[Appendix C](https://arxiv.org/html/2610.08959#A3.SS0.SSS0.Px1.p1.1),[§4\.1](https://arxiv.org/html/2610.08959#S4.SS1.p1.1)\.
- Kociskýet al\.\(2018\)T\. Kociský, J\. Schwarz, P\. Blunsom, C\. Dyer, K\. M\. Hermann, G\. Melis, and E\. GrefenstetteThe narrativeqa reading comprehension challenge\.Trans\. Assoc\. Comput\. Linguistics6,pp\. 317–328\.External Links:[Link](https://doi.org/10.1162/tacl/_a/_00023),[Document](https://dx.doi.org/10.1162/TACL%5FA%5F00023)Cited by:[Appendix C](https://arxiv.org/html/2610.08959#A3.SS0.SSS0.Px1.p1.1),[§4\.1](https://arxiv.org/html/2610.08959#S4.SS1.p1.1)\.
- Liet al\.\(2026a\)S\. Li, Y\. Huang, Z\. Liu, Y\. Li, J\. Fu, L\. Zhao, J\. Bian, L\. Zhang, J\. Zhang, and R\. WangGEAR: granularity\-adaptive advantage reweighting for LLM agents via self\-distillation\.CoRRabs/2605\.11853\.External Links:[Link](https://doi.org/10.48550/arXiv.2605.11853),[Document](https://dx.doi.org/10.48550/ARXIV.2605.11853),2605\.11853Cited by:[§1](https://arxiv.org/html/2610.08959#S1.p2.1),[§2](https://arxiv.org/html/2610.08959#S2.SS0.SSS0.Px2.p1.1)\.
- Liet al\.\(2026b\)W\. Li, Y\. Song, M\. Zhao, B\. Jin, and W\. LiUnifying temporal and structural credit assignment in llm\-based multi\-agent prompt optimization\.CoRRabs/2605\.30227\.External Links:[Link](https://doi.org/10.48550/arXiv.2605.30227),[Document](https://dx.doi.org/10.48550/ARXIV.2605.30227),2605\.30227Cited by:[§2](https://arxiv.org/html/2610.08959#S2.SS0.SSS0.Px2.p1.1)\.
- Liet al\.\(2026c\)Y\. Li, Y\. Zuo, B\. He, J\. Zhang, C\. Xiao, C\. Qian, T\. Yu, H\. Gao, W\. Yang, Z\. Liu, and N\. DingRethinking on\-policy distillation of large language models: phenomenology, mechanism, and recipe\.InICML 2026 Workshop on Foundations of Deep Generative Models: Understanding Memorization, Generalization, and Reasoning,External Links:[Link](https://openreview.net/forum?id=aaDDXXDGXB)Cited by:[§1](https://arxiv.org/html/2610.08959#S1.p1.1),[§2](https://arxiv.org/html/2610.08959#S2.SS0.SSS0.Px1.p1.1)\.
- Lianget al\.\(2026\)K\. Liang, C\. Tang, C\. Bai, W\. Liu, S\. Yang, and Y\. WuADWIN: adaptive windows for horizon\-aware on\-policy distillation\.CoRRabs/2605\.28396\.External Links:[Link](https://doi.org/10.48550/arXiv.2605.28396),[Document](https://dx.doi.org/10.48550/ARXIV.2605.28396),2605\.28396Cited by:[§1](https://arxiv.org/html/2610.08959#S1.p1.1),[§2](https://arxiv.org/html/2610.08959#S2.SS0.SSS0.Px2.p1.1)\.
- Liuet al\.\(2026\)J\. Liu, W\. Li, J\. Ling, and P\. WangWhen privileged guidance misaligns: state\-matched routing and contextualized self\-distillation for multi\-turn agents\.CoRRabs/2608\.05219\.External Links:[Link](https://doi.org/10.48550/arXiv.2608.05219),[Document](https://dx.doi.org/10.48550/ARXIV.2608.05219),2608\.05219Cited by:[§2](https://arxiv.org/html/2610.08959#S2.SS0.SSS0.Px2.p1.1)\.
- Luet al\.\(2026\)Z\. Lu, Z\. Yao, Z\. Han, Z\. Wang, J\. Wu, Q\. Gu, X\. Cai, W\. Lu, J\. Xiao, Y\. Zhuang, and Y\. ShenSelf\-distilled agentic reinforcement learning\.CoRRabs/2605\.15155\.External Links:[Link](https://doi.org/10.48550/arXiv.2605.15155),[Document](https://dx.doi.org/10.48550/ARXIV.2605.15155),2605\.15155Cited by:[Appendix C](https://arxiv.org/html/2610.08959#A3.SS0.SSS0.Px4.p1.1),[§1](https://arxiv.org/html/2610.08959#S1.p2.1),[§2](https://arxiv.org/html/2610.08959#S2.SS0.SSS0.Px1.p1.1)\.
- Mallenet al\.\(2023\)A\. Mallen, A\. Asai, V\. Zhong, R\. Das, D\. Khashabi, and H\. HajishirziWhen not to trust language models: investigating effectiveness of parametric and non\-parametric memories\.InProceedings of the 61st Annual Meeting of the Association for Computational Linguistics \(Volume 1: Long Papers\), ACL 2023, Toronto, Canada, July 9\-14, 2023,A\. Rogers, J\. L\. Boyd\-Graber, and N\. Okazaki \(Eds\.\),pp\. 9802–9822\.External Links:[Link](https://doi.org/10.18653/v1/2023.acl-long.546),[Document](https://dx.doi.org/10.18653/V1/2023.ACL-LONG.546)Cited by:[Appendix C](https://arxiv.org/html/2610.08959#A3.SS0.SSS0.Px1.p1.1),[§4\.1](https://arxiv.org/html/2610.08959#S4.SS1.p1.1)\.
- Meyer \(2000\)C\. D\. MeyerMatrix analysis and applied linear algebra\.SIAM\.External Links:[Link](https://my.siam.org/Store/Product/viewproduct/?ProductId=971),[Document](https://dx.doi.org/10.1137/1.9780898719512),ISBN 978\-0\-898714\-54\-8Cited by:[Appendix B](https://arxiv.org/html/2610.08959#A2.SS0.SSS0.Px1.p1.1)\.
- Nussbaum\-Hofferet al\.\(2026\)N\. Nussbaum\-Hoffer, N\. Calderon, L\. Ein\-Dor, and R\. ReichartLLM explainability with counterfactual chains and causal graphs\.CoRRabs/2606\.05972\.External Links:[Link](https://doi.org/10.48550/arXiv.2606.05972),[Document](https://dx.doi.org/10.48550/ARXIV.2606.05972),2606\.05972Cited by:[§2](https://arxiv.org/html/2610.08959#S2.SS0.SSS0.Px2.p1.1)\.
- Pageet al\.\(1999\)L\. Page, S\. Brin, R\. Motwani, and T\. WinogradThe PageRank citation ranking: bringing order to the web\.Technical reportTechnical Report1999\-66,Stanford InfoLab\.Cited by:[Appendix B](https://arxiv.org/html/2610.08959#A2.SS0.SSS0.Px1.p1.1)\.
- Presset al\.\(2023\)O\. Press, M\. Zhang, S\. Min, L\. Schmidt, N\. A\. Smith, and M\. LewisMeasuring and narrowing the compositionality gap in language models\.InFindings of the Association for Computational Linguistics: EMNLP 2023, Singapore, December 6\-10, 2023,H\. Bouamor, J\. Pino, and K\. Bali \(Eds\.\),Findings of ACL, Vol\.EMNLP 2023,pp\. 5687–5711\.External Links:[Link](https://doi.org/10.18653/v1/2023.findings-emnlp.378),[Document](https://dx.doi.org/10.18653/V1/2023.FINDINGS-EMNLP.378)Cited by:[Appendix C](https://arxiv.org/html/2610.08959#A3.SS0.SSS0.Px1.p1.1),[§4\.1](https://arxiv.org/html/2610.08959#S4.SS1.p1.1)\.
- Shaoet al\.\(2024\)Z\. Shao, P\. Wang, Q\. Zhu, R\. Xu, J\. Song, M\. Zhang, Y\. K\. Li, Y\. Wu, and D\. GuoDeepSeekMath: pushing the limits of mathematical reasoning in open language models\.CoRRabs/2402\.03300\.External Links:[Link](https://doi.org/10.48550/arXiv.2402.03300),[Document](https://dx.doi.org/10.48550/ARXIV.2402.03300),2402\.03300Cited by:[§1](https://arxiv.org/html/2610.08959#S1.p1.1),[§4\.1](https://arxiv.org/html/2610.08959#S4.SS1.p1.1)\.
- Shenget al\.\(2025\)G\. Sheng, C\. Zhang, Z\. Ye, X\. Wu, W\. Zhang, R\. Zhang, Y\. Peng, H\. Lin, and C\. WuHybridFlow: a flexible and efficient rlhf framework\.InProceedings of the Twentieth European Conference on Computer Systems,pp\. 1279–1297\.External Links:[Document](https://dx.doi.org/10.1145/3689031.3696075),[Link](https://dl.acm.org/doi/10.1145/3689031.3696075)Cited by:[§4\.1](https://arxiv.org/html/2610.08959#S4.SS1.p1.1)\.
- Shridharet al\.\(2021\)M\. Shridhar, X\. Yuan, M\. Côté, Y\. Bisk, A\. Trischler, and M\. HausknechtALFWorld: aligning text and embodied environments for interactive learning\.InProceedings of the International Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=08Yk-n5l2Al)Cited by:[Appendix C](https://arxiv.org/html/2610.08959#A3.SS0.SSS0.Px1.p1.1),[§1](https://arxiv.org/html/2610.08959#S1.p1.1),[§4\.1](https://arxiv.org/html/2610.08959#S4.SS1.p1.1)\.
- Song and Zheng \(2026\)M\. Song and M\. ZhengA survey of on\-policy distillation for large language models\.CoRRabs/2604\.00626\.External Links:[Link](https://doi.org/10.48550/arXiv.2604.00626),[Document](https://dx.doi.org/10.48550/ARXIV.2604.00626),2604\.00626Cited by:[§1](https://arxiv.org/html/2610.08959#S1.p1.1),[§2](https://arxiv.org/html/2610.08959#S2.SS0.SSS0.Px1.p1.1)\.
- Sunet al\.\(2026\)C\. Sun, L\. Liu, H\. Lei, T\. Ling, J\. Xie, Z\. Zheng, Y\. Wang, H\. Liu, F\. Xiao, L\. Liu, Y\. Du, Z\. Cheng, Z\. Jiang, and Q\. GuStep\-level on\-policy distillation: interpolating between on\-policy distillation and supervised fine\-tuning\.CoRRabs/2608\.16333\.External Links:[Link](https://doi.org/10.48550/arXiv.2608.16333),[Document](https://dx.doi.org/10.48550/ARXIV.2608.16333),2608\.16333Cited by:[§2](https://arxiv.org/html/2610.08959#S2.SS0.SSS0.Px2.p1.1)\.
- Trivediet al\.\(2022\)H\. Trivedi, N\. Balasubramanian, T\. Khot, and A\. SabharwalMuSiQue: multihop questions via single\-hop question composition\.Transactions of the Association for Computational Linguistics10,pp\. 539–554\.External Links:[Link](https://doi.org/10.1162/tacl/_a/_00475),[Document](https://dx.doi.org/10.1162/TACL%5FA%5F00475)Cited by:[Appendix C](https://arxiv.org/html/2610.08959#A3.SS0.SSS0.Px1.p1.1),[§4\.1](https://arxiv.org/html/2610.08959#S4.SS1.p1.1)\.
- Wanget al\.\(2026a\)H\. Wang, W\. Ren, Y\. Zhang, D\. Cao, Z\. Zeng, K\. Zeng, and T\. ZhaoBiPACE: bisimulation\-guided policy optimization with action counterfactual estimation for LLM agents\.CoRRabs/2606\.25556\.External Links:[Link](https://doi.org/10.48550/arXiv.2606.25556),[Document](https://dx.doi.org/10.48550/ARXIV.2606.25556),2606\.25556Cited by:[§2](https://arxiv.org/html/2610.08959#S2.SS0.SSS0.Px2.p1.1)\.
- Wanget al\.\(2026b\)H\. Wang, L\. Sha, and J\. M\. ZhangStepCodeReasoner: aligning code reasoning with stepwise execution traces via reinforcement learning\.InForty\-third International Conference on Machine Learning,External Links:[Link](https://openreview.net/forum?id=0vTONq9Z8j)Cited by:[§2](https://arxiv.org/html/2610.08959#S2.SS0.SSS0.Px2.p1.1)\.
- Wanget al\.\(2026c\)H\. Wang, G\. Wang, H\. Xiao, Y\. Zhou, Y\. Pan, J\. Wang, K\. Xu, Y\. Wen, X\. Ruan, X\. Chen, and H\. QiSkill\-sd: skill\-conditioned self\-distillation for multi\-turn LLM agents\.CoRRabs/2604\.10674\.External Links:[Link](https://doi.org/10.48550/arXiv.2604.10674),[Document](https://dx.doi.org/10.48550/ARXIV.2604.10674),2604\.10674Cited by:[§1](https://arxiv.org/html/2610.08959#S1.p2.1),[§2](https://arxiv.org/html/2610.08959#S2.SS0.SSS0.Px1.p1.1)\.
- Wanget al\.\(2026d\)J\. Wang, Y\. Liu, J\. Chen, X\. Hu, Q\. Zhang, Y\. Cao, J\. Wang, H\. Yang, Y\. Xie, and Q\. ChenMAD\-opd: breaking the ceiling in on\-policy distillation via multi\-agent debate\.arXiv preprint arXiv:2605\.01347\.Cited by:[§1](https://arxiv.org/html/2610.08959#S1.p2.1),[§2](https://arxiv.org/html/2610.08959#S2.SS0.SSS0.Px2.p1.1)\.
- WANGet al\.\(2026\)J\. WANG, W\. Zhang, W\. Shi, Y\. Li, and J\. ChengExploring temporal curriculum in on\-policy distillation for multi\-turn autonomous agents\.InThird Conference on Language Modeling,External Links:[Link](https://openreview.net/forum?id=KH9eJRz8WR)Cited by:[§1](https://arxiv.org/html/2610.08959#S1.p1.1),[§2](https://arxiv.org/html/2610.08959#S2.SS0.SSS0.Px2.p1.1)\.
- Wanget al\.\(2021\)J\. Wang, J\. Wiens, and S\. LundbergShapley flow: a graph\-based approach to interpreting model predictions\.InProceedings of The 24th International Conference on Artificial Intelligence and Statistics,A\. Banerjee and K\. Fukumizu \(Eds\.\),Proceedings of Machine Learning Research, Vol\.130,pp\. 721–729\.External Links:[Link](https://proceedings.mlr.press/v130/wang21b.html)Cited by:[§2](https://arxiv.org/html/2610.08959#S2.SS0.SSS0.Px2.p1.1)\.
- Wanget al\.\(2026e\)Q\. Wang, S\. Wang, Y\. Zeng, Q\. Zhang, F\. Zhang, Z\. Guo, B\. Zhang, W\. Huang, L\. Chen, Z\. Chen, P\. Xie, and R\. DingNavigating massive visual context in retrieval\-augmented generation via multimodal memory graph\.InForty\-third International Conference on Machine Learning,External Links:[Link](https://openreview.net/forum?id=fylE5O8g5F)Cited by:[§2](https://arxiv.org/html/2610.08959#S2.SS0.SSS0.Px2.p1.1)\.
- Wanget al\.\(2026f\)X\. Wang, Z\. Ma, Y\. Wang, Y\. Ji, S\. Yang, G\. Chen, P\. Wang, and X\. ChuAPPO: agentic procedural policy optimization\.CoRRabs/2606\.12384\.External Links:[Link](https://doi.org/10.48550/arXiv.2606.12384),[Document](https://dx.doi.org/10.48550/ARXIV.2606.12384),2606\.12384Cited by:[§1](https://arxiv.org/html/2610.08959#S1.p2.1),[§2](https://arxiv.org/html/2610.08959#S2.SS0.SSS0.Px2.p1.1)\.
- Wanget al\.\(2026g\)Z\. Wang, S\. Lu, H\. Zhang, L\. Mo, C\. Zhuang, and L\. GanTeach the magnitude, not the direction: verifier\-bounded credit assignment for multi\-turn multi\-step LLM agents\.CoRRabs/2608\.13179\.External Links:[Link](https://doi.org/10.48550/arXiv.2608.13179),[Document](https://dx.doi.org/10.48550/ARXIV.2608.13179),2608\.13179Cited by:[§2](https://arxiv.org/html/2610.08959#S2.SS0.SSS0.Px2.p1.1)\.
- Wuet al\.\(2021\)S\. Wu, J\. Chen, T\. Xu, L\. Chen, L\. Wu, Y\. Hu, and E\. ChenLinking the characters: video\-oriented social graph generation via hierarchical\-cumulative GCN\.InMM ’21: ACM Multimedia Conference, Virtual Event, China, October 20 \- 24, 2021,H\. T\. Shen, Y\. Zhuang, J\. R\. Smith, Y\. Yang, P\. César, F\. Metze, and B\. Prabhakaran \(Eds\.\),pp\. 4716–4724\.External Links:[Link](https://doi.org/10.1145/3474085.3475684),[Document](https://dx.doi.org/10.1145/3474085.3475684)Cited by:[§2](https://arxiv.org/html/2610.08959#S2.SS0.SSS0.Px2.p1.1)\.
- Wuet al\.\(2024\)W\. Wu, C\. Wang, D\. Shen, C\. Qin, L\. Chen, and H\. XiongAFDGCF: adaptive feature de\-correlation graph collaborative filtering for recommendations\.InProceedings of the 47th International ACM SIGIR Conference on Research and Development in Information Retrieval, SIGIR 2024, Washington DC, USA, July 14\-18, 2024,G\. H\. Yang, H\. Wang, S\. Han, C\. Hauff, G\. Zuccon, and Y\. Zhang \(Eds\.\),pp\. 1242–1252\.External Links:[Link](https://doi.org/10.1145/3626772.3657724),[Document](https://dx.doi.org/10.1145/3626772.3657724)Cited by:[§2](https://arxiv.org/html/2610.08959#S2.SS0.SSS0.Px2.p1.1)\.
- Yanget al\.\(2025\)A\. Yang, A\. Li, B\. Yang, B\. Zhang, B\. Hui, B\. Zheng, B\. Yu, C\. Gao, C\. Huang, C\. Lv, C\. Zheng, D\. Liu, F\. Zhou, F\. Huang, F\. Hu, H\. Ge, H\. Wei, H\. Lin, J\. Tang, J\. Yang, J\. Tu, J\. Zhang, J\. Yang, J\. Yang, J\. Zhou, J\. Zhou, J\. Lin, K\. Dang, K\. Bao, K\. Yang, L\. Yu, L\. Deng, M\. Li, M\. Xue, M\. Li, P\. Zhang, P\. Wang, Q\. Zhu, R\. Men, R\. Gao, S\. Liu, S\. Luo, T\. Li, T\. Tang, W\. Yin, X\. Ren, X\. Wang, X\. Zhang, X\. Ren, Y\. Fan, Y\. Su, Y\. Zhang, Y\. Zhang, Y\. Wan, Y\. Liu, Z\. Wang, Z\. Cui, Z\. Zhang, Z\. Zhou, and Z\. QiuQwen3 technical report\.CoRRabs/2505\.09388\.External Links:[Link](https://doi.org/10.48550/arXiv.2505.09388),[Document](https://dx.doi.org/10.48550/ARXIV.2505.09388),2505\.09388Cited by:[§4\.1](https://arxiv.org/html/2610.08959#S4.SS1.p1.1)\.
- Yanget al\.\(2024\)A\. Yang, B\. Yang, B\. Zhang, B\. Hui, B\. Zheng, B\. Yu, C\. Li, D\. Liu, F\. Huang, H\. Wei, H\. Lin, J\. Yang, J\. Tu, J\. Zhang, J\. Yang, J\. Yang, J\. Zhou, J\. Lin, K\. Dang, K\. Lu, K\. Bao, K\. Yang, L\. Yu, M\. Li, M\. Xue, P\. Zhang, Q\. Zhu, R\. Men, R\. Lin, T\. Li, T\. Xia, X\. Ren, X\. Ren, Y\. Fan, Y\. Su, Y\. Zhang, Y\. Wan, Y\. Liu, Z\. Cui, Z\. Zhang, and Z\. QiuQwen2\.5 technical report\.CoRRabs/2412\.15115\.External Links:[Link](https://doi.org/10.48550/arXiv.2412.15115),[Document](https://dx.doi.org/10.48550/ARXIV.2412.15115),2412\.15115Cited by:[§4\.1](https://arxiv.org/html/2610.08959#S4.SS1.p1.1)\.
- Yanget al\.\(2026a\)C\. Yang, C\. Qin, Q\. Si, M\. Chen, N\. Gu, D\. Yao, Z\. Lin, W\. Wang, J\. Wang, and N\. DuanSelf\-distilled RLVR\.CoRRabs/2604\.03128\.External Links:[Link](https://doi.org/10.48550/arXiv.2604.03128),[Document](https://dx.doi.org/10.48550/ARXIV.2604.03128),2604\.03128Cited by:[Appendix C](https://arxiv.org/html/2610.08959#A3.SS0.SSS0.Px4.p1.1),[§1](https://arxiv.org/html/2610.08959#S1.p2.1),[§2](https://arxiv.org/html/2610.08959#S2.SS0.SSS0.Px1.p1.1)\.
- Yanget al\.\(2026b\)S\. Yang, J\. Wu, Z\. Lu, Y\. Shen, F\. Zhang, L\. Feng, S\. Zhang, H\. Luo, Z\. Lian, Z\. Wen, and J\. TaoOPID: on\-policy skill distillation for agentic reinforcement learning\.CoRRabs/2606\.26790\.External Links:[Link](https://doi.org/10.48550/arXiv.2606.26790),[Document](https://dx.doi.org/10.48550/ARXIV.2606.26790),2606\.26790Cited by:[Appendix C](https://arxiv.org/html/2610.08959#A3.SS0.SSS0.Px4.p1.1),[§1](https://arxiv.org/html/2610.08959#S1.p2.1),[§2](https://arxiv.org/html/2610.08959#S2.SS0.SSS0.Px1.p1.1)\.
- Yanget al\.\(2026c\)W\. Yang, W\. Liu, R\. Xie, K\. Yang, S\. Yang, and Y\. LinLearning beyond teacher: generalized on\-policy distillation with reward extrapolation\.CoRRabs/2602\.12125\.External Links:[Link](https://doi.org/10.48550/arXiv.2602.12125),[Document](https://dx.doi.org/10.48550/ARXIV.2602.12125),2602\.12125Cited by:[§2](https://arxiv.org/html/2610.08959#S2.SS0.SSS0.Px1.p1.1)\.
- Yanget al\.\(2018\)Z\. Yang, P\. Qi, S\. Zhang, Y\. Bengio, W\. W\. Cohen, R\. Salakhutdinov, and C\. D\. ManningHotpotQA: A dataset for diverse, explainable multi\-hop question answering\.InProceedings of the 2018 Conference on Empirical Methods in Natural Language Processing, Brussels, Belgium, October 31 \- November 4, 2018,E\. Riloff, D\. Chiang, J\. Hockenmaier, and J\. Tsujii \(Eds\.\),pp\. 2369–2380\.External Links:[Link](https://doi.org/10.18653/v1/d18-1259),[Document](https://dx.doi.org/10.18653/V1/D18-1259)Cited by:[Appendix C](https://arxiv.org/html/2610.08959#A3.SS0.SSS0.Px1.p1.1),[§1](https://arxiv.org/html/2610.08959#S1.p1.1),[§4\.1](https://arxiv.org/html/2610.08959#S4.SS1.p1.1)\.
- Yaoet al\.\(2022\)S\. Yao, H\. Chen, J\. Yang, and K\. NarasimhanWebShop: towards scalable real\-world web interaction with grounded language agents\.InAdvances in Neural Information Processing Systems,Vol\.35,pp\. 16810–16824\.External Links:[Link](https://proceedings.neurips.cc/paper_files/paper/2022/hash/82ad13ec01f9fe44c01cb91814fd7b8c.html)Cited by:[Appendix C](https://arxiv.org/html/2610.08959#A3.SS0.SSS0.Px1.p1.1),[§1](https://arxiv.org/html/2610.08959#S1.p1.1),[§4\.1](https://arxiv.org/html/2610.08959#S4.SS1.p1.1)\.
- Yaoet al\.\(2023\)S\. Yao, J\. Zhao, D\. Yu, N\. Du, I\. Shafran, K\. R\. Narasimhan, and Y\. CaoReAct: synergizing reasoning and acting in language models\.InThe Eleventh International Conference on Learning Representations, ICLR 2023, Kigali, Rwanda, May 1\-5, 2023,External Links:[Link](https://openreview.net/forum?id=WE\_vluYUL-X)Cited by:[§1](https://arxiv.org/html/2610.08959#S1.p1.1)\.
- Yuanet al\.\(2025\)J\. Yuan, W\. Zhao, and Z\. BaiGraph\-enhanced policy optimization in LLM agent training\.CoRRabs/2510\.26270\.External Links:[Link](https://doi.org/10.48550/arXiv.2510.26270),[Document](https://dx.doi.org/10.48550/ARXIV.2510.26270),2510\.26270Cited by:[Appendix C](https://arxiv.org/html/2610.08959#A3.SS0.SSS0.Px4.p1.1),[§1](https://arxiv.org/html/2610.08959#S1.p2.1),[§2](https://arxiv.org/html/2610.08959#S2.SS0.SSS0.Px2.p1.1)\.
- Yuanet al\.\(2026\)Z\. Yuan, Y\. Cao, H\. Zhang, J\. Yan, L\. Liu, C\. Ke, Y\. Yu, H\. Wang, M\. Liu, and B\. QinEGL\-sca: structural credit assignment for co\-evolving instructions and tools in graph reasoning agents\.arXiv preprint arXiv:2605\.10366\.Cited by:[§2](https://arxiv.org/html/2610.08959#S2.SS0.SSS0.Px2.p1.1)\.
- Zhang \(2026\)H\. ZhangCredit without ground truth: auditing step\-level credit assignment in LLM agents against executed replay\.CoRRabs/2608\.19760\.External Links:[Link](https://doi.org/10.48550/arXiv.2608.19760),[Document](https://dx.doi.org/10.48550/ARXIV.2608.19760),2608\.19760Cited by:[Appendix E](https://arxiv.org/html/2610.08959#A5.SS0.SSS0.Px3.p1.1),[§4\.4](https://arxiv.org/html/2610.08959#S4.SS4.SSS0.Px2.p1.1)\.
- Zhanget al\.\(2026a\)H\. Zhang, M\. Chen, D\. Zhou, C\. Lv, H\. Chang, S\. Cui, F\. Wu, and S\. ZhouTRCA: transition\-wise rubric credit assignment for long\-horizon LLM agents\.CoRRabs/2608\.16156\.External Links:[Link](https://doi.org/10.48550/arXiv.2608.16156),[Document](https://dx.doi.org/10.48550/ARXIV.2608.16156),2608\.16156Cited by:[§2](https://arxiv.org/html/2610.08959#S2.SS0.SSS0.Px2.p1.1)\.
- Zhanget al\.\(2024\)S\. Zhang, L\. Chen, C\. Wang, S\. Li, and H\. XiongTemporal graph contrastive learning for sequential recommendation\.InThirty\-Eighth AAAI Conference on Artificial Intelligence, AAAI 2024, Thirty\-Sixth Conference on Innovative Applications of Artificial Intelligence, IAAI 2024, Fourteenth Symposium on Educational Advances in Artificial Intelligence, EAAI 2024, February 20\-27, 2024, Vancouver, Canada,M\. J\. Wooldridge, J\. G\. Dy, and S\. Natarajan \(Eds\.\),pp\. 9359–9367\.External Links:[Link](https://doi.org/10.1609/aaai.v38i8.28789),[Document](https://dx.doi.org/10.1609/AAAI.V38I8.28789)Cited by:[§2](https://arxiv.org/html/2610.08959#S2.SS0.SSS0.Px2.p1.1)\.
- Zhanget al\.\(2026b\)Y\. Zhang, X\. Lin, and C\. WuStepOPSD: step\-aware online preference self\-distillation for agent reinforcement learning\.External Links:2605\.27140,[Link](https://arxiv.org/abs/2605.27140)Cited by:[§1](https://arxiv.org/html/2610.08959#S1.p2.1),[§2](https://arxiv.org/html/2610.08959#S2.SS0.SSS0.Px2.p1.1)\.
- Zhaoet al\.\(2026\)S\. Zhao, Z\. Xie, M\. Liu, J\. Huang, G\. Pang, F\. Chen, and A\. GroverSelf\-distilled reasoner: on\-policy self\-distillation for large language models\.InForty\-third International Conference on Machine Learning,External Links:[Link](https://openreview.net/forum?id=Jpxfof0EaS)Cited by:[§1](https://arxiv.org/html/2610.08959#S1.p1.1),[§2](https://arxiv.org/html/2610.08959#S2.SS0.SSS0.Px1.p1.1)\.
- Zhonget al\.\(2026\)Q\. Zhong, M\. Zheng, M\. Song, X\. Lin, J\. Sun, H\. Jiang, X\. Wang, and J\. FangSOD: step\-wise on\-policy distillation for small language model agents\.CoRRabs/2605\.07725\.External Links:[Link](https://doi.org/10.48550/arXiv.2605.07725),[Document](https://dx.doi.org/10.48550/ARXIV.2605.07725),2605\.07725Cited by:[Appendix D](https://arxiv.org/html/2610.08959#A4.SS0.SSS0.Px1.p1.1),[§1](https://arxiv.org/html/2610.08959#S1.p2.1),[§2](https://arxiv.org/html/2610.08959#S2.SS0.SSS0.Px2.p1.1)\.

## Appendix AFootprint Extractor and Algorithm

Each environment has a dedicated, rule\-based Footprint extractorℱenv\\mathcal\{F\}\_\{\\text\{env\}\}that maps an action and observation to a small set of<type\>:<entity\>keys\. The extractor for the four out\-of\-domain tool\-integrated\-reasoning benchmarks is specified in Appendix[D](https://arxiv.org/html/2610.08959#A4)\.

#### Footprint as a state\-difference projection\.

ℱenv\\mathcal\{F\}\_\{\\text\{env\}\}is the practical, text\-only form of a more general construction, given here in full\. Treat the environment statests\_\{t\}from Section[3\.1](https://arxiv.org/html/2610.08959#S3.SS1)as a set of ground predicates over named entities, for instancelocation\(apple\_1\)=countertop\_1, so that the raw effect of stepttis the symmetric differenceΔt=st​△​st−1\\Delta\_\{t\}=s\_\{t\}\\triangle s\_\{t\-1\}, namely the predicates that came into or out of existence, or changed value, when actionata\_\{t\}was executed against observationoto\_\{t\}\. Most ofΔt\\Delta\_\{t\}is irrelevant to any later step, because the specific new value a predicate takes rarely determines whether a downstream action depends on it, whereas the fact that some named entity changed does\. We therefore canonicalizeΔt\\Delta\_\{t\}through a projectionπ\\pithat retains only the<type\>:<entity\>pair each changed predicate is indexed by and discards its value,

ℱ⁡\(t\)=π⁡\(Δt\)=ℱenv​\(at,ot\)\.\\mathcal\{F\}\(t\)=\\pi\(\\Delta\_\{t\}\)=\\mathcal\{F\}\_\{\\text\{env\}\}\(a\_\{t\},\\,o\_\{t\}\)\.\(12\)ℱenv\\mathcal\{F\}\_\{\\text\{env\}\}is implemented directly from\(at,ot\)\(a\_\{t\},o\_\{t\}\)rather than from a structuredsts\_\{t\}, since in a text\-interfaced environment the action and observation text are exactly what fixesΔt\\Delta\_\{t\}in the first place\.

###### Lemma A\.1\(Footprint sufficiency\)\.

ℱ⁡\(t\)\\mathcal\{F\}\(t\)is a sufficient statistic ofΔt\\Delta\_\{t\}for the dependency\-edge relationEEof Eq\. equation[2](https://arxiv.org/html/2610.08959#S3.E2)\. For any two trajectories whose step\-tteffectsΔt,Δt′\\Delta\_\{t\},\\Delta\_\{t\}^\{\\prime\}project to the same Footprint,π⁡\(Δt\)=π⁡\(Δt′\)\\pi\(\\Delta\_\{t\}\)=\\pi\(\\Delta\_\{t\}^\{\\prime\}\), the edge test returns the same decision for every later stepjj\.

###### Proof\.

Eq\. equation[2](https://arxiv.org/html/2610.08959#S3.E2)decides\(vt→vj\)∈E\(v\_\{t\}\\to v\_\{j\}\)\\in Eby testing whether some<type\>:<entity\>∈ℱ⁡\(t\)\\in\\mathcal\{F\}\(t\)has its<entity\>occur as a substring ofaja\_\{j\}\. This test readsΔt\\Delta\_\{t\}only throughπ⁡\(Δt\)=ℱ⁡\(t\)\\pi\(\\Delta\_\{t\}\)=\\mathcal\{F\}\(t\), and it never inspects a predicate’s value, i\.e\. never reads anything inΔt∖π⁡\(Δt\)\\Delta\_\{t\}\\setminus\\pi\(\\Delta\_\{t\}\)\. Two effects with identicalπ⁡\(Δt\)\\pi\(\\Delta\_\{t\}\)therefore agree on every entity\-membership query the test can make, and so yield an identical decision for everyjj, regardless of howΔt\\Delta\_\{t\}andΔt′\\Delta\_\{t\}^\{\\prime\}otherwise differ\. ∎

The projectionπ\\piis lossy in general, discarding exactly the information Lemma[A\.1](https://arxiv.org/html/2610.08959#A1.Thmlemma1)shows the graph never needed\.ℱ⁡\(t\)\\mathcal\{F\}\(t\)is therefore not merely a convenient summary ofΔt\\Delta\_\{t\}but the coarsest one that still determinesEE\.

Table[5](https://arxiv.org/html/2610.08959#A1.T5)lists the action types and Footprint key formats used for each of the three benchmarks, and none of these extractors involve an LLM call, semantic embedding, or privileged annotation\.

Table 5:Footprint extractor specifications by environment\.As a concrete example, suppose step 2 of an ALFWorld trajectory istake apple 1 from countertop 1, yieldingholding:apple 1, and step 5 isput apple 1 in fridge 1, whose action text containsapple 1\. A dependency edgev2→v5v\_\{2\}\\\!\\to\\\!v\_\{5\}is then added with weight1/d​f​\(apple 1\)1/df\(\\texttt\{apple\\,1\}\)following Eq\. equation[3](https://arxiv.org/html/2610.08959#S3.E3)\. Analogously, a WebShop search produces onequery\_tokenkey per query word, and a later action whose text contains one of those words draws the corresponding edge\.

#### Complete algorithm\.

Algorithm[1](https://arxiv.org/html/2610.08959#alg1)summarizes the full GraphOPD pipeline for one trajectory, from Footprint extraction to the combined training objective\. It is a drop\-in addition to the GRPO loop, since the graph, the two signals, the aptitude, and the mask are all computed from the rollout and its recorded states, with no extra model calls\.

Algorithm 1GraphOPD, per\-trajectory supervision weighting0:trajectory

τ=\(s0,a1,…,aT,sT\)\\tau=\(s\_\{0\},a\_\{1\},\\dots,a\_\{T\},s\_\{T\}\), student

πθ\\pi\_\{\\theta\}, teacher

πθold\\pi\_\{\\theta\_\{\\text\{old\}\}\}, coefficients

α,λ\\alpha,\\lambda, damping

dd
1:Footprints\.For

t=1,…,Tt=1,\\dots,T, extract

ℱ⁡\(t\)=ℱenv​\(at,ot\)\\mathcal\{F\}\(t\)=\\mathcal\{F\}\_\{\\text\{env\}\}\(a\_\{t\},o\_\{t\}\)
2:Dependency graph\.Build

G=\(V,E,w\)G=\(V,E,w\), and for each

i<ji<jadd

vi→vjv\_\{i\}\\\!\\to\\\!v\_\{j\}if an entity in

ℱ⁡\(i\)\\mathcal\{F\}\(i\)is referenced by

aja\_\{j\}, weighted

1/d​f​\(e\)1/df\(e\)per Eq\. equation[3](https://arxiv.org/html/2610.08959#S3.E3), then add backtrack edges of weight

0\.50\.5and sequential edges of weight

0\.050\.05
3:Centrality\.Row\-normalize

wwinto

MM, giving leaf nodes a uniform row

1/T1/T, solve

𝝅∗=\(1−d\)​𝝅∗​M\+d​𝐮⊤\\bm\{\\pi\}^\{\*\}=\(1\-d\)\\bm\{\\pi\}^\{\*\}M\+d\\mathbf\{u\}^\{\\top\}by power iteration, and set

ℓgraph​\(t\)=log⁡\(T​πt∗\)\\ell\_\{\\text\{graph\}\}\(t\)=\\log\\bigl\(T\\,\\pi^\{\*\}\_\{t\}\\bigr\)
4:Deviation\.

δ⁡\(t\)=1\|St\|​∑k∈St\|log⁡πθold​\(k\|st\)−log⁡πθ​\(k\|st\)\|\\delta\(t\)=\\frac\{1\}\{\|S\_\{t\}\|\}\\sum\_\{k\\in S\_\{t\}\}\\bigl\|\\log\\pi\_\{\\theta\_\{\\text\{old\}\}\}\(k\|s\_\{t\}\)\-\\log\\pi\_\{\\theta\}\(k\|s\_\{t\}\)\\bigr\|, then

rt=δ⁡\(t\)/δmaxr\_\{t\}=\\delta\(t\)/\\delta\_\{\\text\{max\}\}and

ℓmodel​\(t\)=log⁡\[\(rt\+ε\)/\(1−rt\+ε\)\]\\ell\_\{\\text\{model\}\}\(t\)=\\log\\bigl\[\(r\_\{t\}\+\\varepsilon\)/\(1\-r\_\{t\}\+\\varepsilon\)\\bigr\]
5:Aptitude\.

A⁡\(t\)=α​ℓmodel​\(t\)\+\(1−α\)​ℓgraph​\(t\)A\(t\)=\\alpha\\,\\ell\_\{\\text\{model\}\}\(t\)\+\(1\-\\alpha\)\\,\\ell\_\{\\text\{graph\}\}\(t\)
6:Mask\.

μτ,sτ←\\mu\_\{\\tau\},s\_\{\\tau\}\\leftarrowmean, std of

\{A⁡\(t\)\}t=1T\\\{A\(t\)\\\}\_\{t=1\}^\{T\}, then

m⁡\(t\)=σ⁡\(\(A⁡\(t\)−μτ\)/sτ\)m\(t\)=\\sigma\\bigl\(\(A\(t\)\-\\mu\_\{\\tau\}\)/s\_\{\\tau\}\\bigr\)
7:Objective\.

ℒ=ℒGRPO\+λ​∑tm\(t\)KL\(πθold\(⋅\|st\)∥πθ\(⋅\|st\)\)∑tm⁡\(t\)\\mathcal\{L\}=\\mathcal\{L\}\_\{\\text\{GRPO\}\}\+\\lambda\\,\\frac\{\\sum\_\{t\}m\(t\)\\,\\mathrm\{KL\}\(\\pi\_\{\\theta\_\{\\text\{old\}\}\}\(\\cdot\|s\_\{t\}\)\\,\\\|\\,\\pi\_\{\\theta\}\(\\cdot\|s\_\{t\}\)\)\}\{\\sum\_\{t\}m\(t\)\}
8:Update

θ\\thetaby gradient descent on

ℒ\\mathcal\{L\}

## Appendix BTheoretical Properties and Implementation Notes

Two claims made informally in Section[3\.4](https://arxiv.org/html/2610.08959#S3.SS4)are provable consequences of Eqs\. equation[4](https://arxiv.org/html/2610.08959#S3.E4)to equation[9](https://arxiv.org/html/2610.08959#S3.E9)rather than free\-standing design choices\. This section states and proves them, gives a full derivation of the convergence rate they rely on, and draws three corollaries connecting that derivation to specific empirical results, namely the observed power\-iteration count, the Soft\-Pruning ablation, and the shrinking trajectory lengths in the dependency\-graph\-structure analysis\.

#### The stationary distribution exists, is unique, and is efficiently computable\.

Eq\. equation[4](https://arxiv.org/html/2610.08959#S3.E4)’s update matrixP=\(1−d\)​M\+d​1​𝐮⊤P=\(1\-d\)M\+d\\,\\mathbf\{1\}\\mathbf\{u\}^\{\\top\}combines the row\-stochastic edge matrixMM\(row\-normalized, with leaf nodes given the uniform row1/T1/T\) with the uniform teleportation matrix𝟏​𝐮⊤\\mathbf\{1\}\\mathbf\{u\}^\{\\top\}under weightd∈\(0,1\)d\\in\(0,1\)\. Every entry ofPPis therefore at leastd/T\>0d/T\>0, soPPis a primitive, meaning irreducible and aperiodic, row\-stochastic matrix for*any*graph topologyGG, including disconnected components or absorbing states that would makeMMalone reducible\. By the Perron–Frobenius theorem for primitive non\-negative matrices\([Meyer, 2000](https://arxiv.org/html/2610.08959#bib.bib44)\),PP’s spectral radius is a simple eigenvalue equal to11, with a strictly positive left eigenvector unique up to scale, and normalizing∑tπt∗=1\\sum\_\{t\}\\pi^\{\*\}\_\{t\}=1fixes that scale, so𝝅∗\\bm\{\\pi\}^\{\*\}is well\-defined regardless ofGG’s structure and independent of the power\-iteration starting point\. The same damped\-teleportation construction is the basis of the classical convergence guarantee for stationary distributions on directed graphs\([Page et al\., 1999](https://arxiv.org/html/2610.08959#bib.bib45)\), under whichPP’s second\-largest eigenvalue modulus is bounded by1−d1\-d, so power iteration converges geometrically at rateO⁡\(\(1−d\)k\)O\(\(1\-d\)^\{k\}\), matching the empirical convergence noted below \(under5050iterations atd=0\.15d=0\.15,T≤50T\\leq 50, to tolerance10−610^\{\-6\}\)\.

###### Proposition 1\(Bounds on the two signals\)\.

For any stepttin a trajectory of lengthTTwith dampingd∈\(0,1\)d\\in\(0,1\),

log⁡d≤ℓgraph​\(t\)≤log⁡T,\\log d\\;\\leq\\;\\ell\_\{\\text\{graph\}\}\(t\)\\;\\leq\\;\\log T,and for any smoothing floorε\>0\\varepsilon\>0,

−log⁡1\+εε≤ℓmodel​\(t\)≤log⁡1\+εε\.\-\\log\\frac\{1\+\\varepsilon\}\{\\varepsilon\}\\;\\leq\\;\\ell\_\{\\text\{model\}\}\(t\)\\;\\leq\\;\\log\\frac\{1\+\\varepsilon\}\{\\varepsilon\}\.

###### Proof\.

Forℓgraph\\ell\_\{\\text\{graph\}\}, sinceMMis entrywise non\-negative and𝝅∗\\bm\{\\pi\}^\{\*\}is non\-negative, Eq\. equation[4](https://arxiv.org/html/2610.08959#S3.E4)gives𝝅∗=\(1−d\)​𝝅∗​M\+d​𝐮⊤≥d​𝐮⊤\\bm\{\\pi\}^\{\*\}=\(1\-d\)\\bm\{\\pi\}^\{\*\}M\+d\\,\\mathbf\{u\}^\{\\top\}\\geq d\\,\\mathbf\{u\}^\{\\top\}entrywise, soπt∗≥d/T\\pi^\{\*\}\_\{t\}\\geq d/Tfor everyttandℓgraph​\(t\)=log⁡\(T​πt∗\)≥log⁡d\\ell\_\{\\text\{graph\}\}\(t\)=\\log\(T\\pi^\{\*\}\_\{t\}\)\\geq\\log d\. The upper bound follows becauseπt∗≤1\\pi^\{\*\}\_\{t\}\\leq 1trivially, as𝝅∗\\bm\{\\pi\}^\{\*\}is a probability distribution overTTsteps, givingℓgraph​\(t\)≤log⁡T\\ell\_\{\\text\{graph\}\}\(t\)\\leq\\log T\. Forℓmodel\\ell\_\{\\text\{model\}\},rt∈\[0,1\]r\_\{t\}\\in\[0,1\]by construction, sort\+ε1−rt\+ε∈\[ε1\+ε,1\+εε\]\\frac\{r\_\{t\}\+\\varepsilon\}\{1\-r\_\{t\}\+\\varepsilon\}\\in\\bigl\[\\frac\{\\varepsilon\}\{1\+\\varepsilon\},\\frac\{1\+\\varepsilon\}\{\\varepsilon\}\\bigr\], and taking logs gives the stated bound\. ∎

With the values used throughout,d=0\.15d=0\.15andε=0\.1\\varepsilon=0\.1, this givesℓgraph​\(t\)∈\[−1\.90,log⁡T\]\\ell\_\{\\text\{graph\}\}\(t\)\\in\[\-1\.90,\\log T\]andℓmodel​\(t\)∈\[−2\.40,2\.40\]\\ell\_\{\\text\{model\}\}\(t\)\\in\[\-2\.40,2\.40\], and for trajectories capped atT=50T=50steps,log⁡T≤3\.91\\log T\\leq 3\.91, so the two signals occupy overlapping ranges of comparable magnitude, the exact sense in which the two signals are commensurate\.

###### Proposition 2\(Affine invariance of the trajectory\-relative mask\)\.

LetA′​\(t\)=a⋅A⁡\(t\)\+bA^\{\\prime\}\(t\)=a\\cdot A\(t\)\+bfor constantsa\>0,b∈ℝa\>0,b\\in\\mathbb\{R\}applied uniformly across a trajectoryτ\\tau\. Then the mask computed fromA′A^\{\\prime\}equals the mask computed fromAA,m′​\(t\)=m​\(t\)m^\{\\prime\}\(t\)=m\(t\)for everyt∈τt\\in\\tau\.

###### Proof\.

Letμτ,sτ\\mu\_\{\\tau\},s\_\{\\tau\}be the mean and standard deviation of\{A⁡\(t\)\}t=1T\\\{A\(t\)\\\}\_\{t=1\}^\{T\}\. The corresponding statistics of\{A′​\(t\)\}\\\{A^\{\\prime\}\(t\)\\\}areμτ′=a​μτ\+b\\mu^\{\\prime\}\_\{\\tau\}=a\\mu\_\{\\tau\}\+bandsτ′=a​sτs^\{\\prime\}\_\{\\tau\}=a\\,s\_\{\\tau\}, since variance scales bya2a^\{2\}anda\>0a\>0, so the standard deviation scales byaa\. Then

A′​\(t\)−μτ′sτ′=\(a​A​\(t\)\+b\)−\(a​μτ\+b\)a​sτ=A⁡\(t\)−μτsτ,\\frac\{A^\{\\prime\}\(t\)\-\\mu^\{\\prime\}\_\{\\tau\}\}\{s^\{\\prime\}\_\{\\tau\}\}=\\frac\{\(aA\(t\)\+b\)\-\(a\\mu\_\{\\tau\}\+b\)\}\{a\\,s\_\{\\tau\}\}=\\frac\{A\(t\)\-\\mu\_\{\\tau\}\}\{s\_\{\\tau\}\},som′​\(t\)=σ⁡\(A′​\(t\)−μτ′sτ′\)=σ⁡\(A⁡\(t\)−μτsτ\)=m⁡\(t\)m^\{\\prime\}\(t\)=\\sigma\\bigl\(\\tfrac\{A^\{\\prime\}\(t\)\-\\mu^\{\\prime\}\_\{\\tau\}\}\{s^\{\\prime\}\_\{\\tau\}\}\\bigr\)=\\sigma\\bigl\(\\tfrac\{A\(t\)\-\\mu\_\{\\tau\}\}\{s\_\{\\tau\}\}\\bigr\)=m\(t\)\. ∎

This is the precise sense in which the mask stays meaningful asA⁡\(t\)A\(t\)’s absolute scale drifts over training\. Any rescaling of the aptitude that is common across a trajectory’s own steps leaves every mask weight in that trajectory unchanged, and such a common rescaling is exactly what happens asδmax\\delta\_\{\\text\{max\}\}and the graph’s stationary distribution shift with the policy\. A threshold fixed across trajectories has no such guarantee, since Proposition[2](https://arxiv.org/html/2610.08959#Thmproposition2)only holds for a single shared\(a,b\)\(a,b\)within one trajectory, and different trajectories drift by different amounts, which is why a global threshold would need continual re\-tuning while the trajectory\-relative one does not\.

#### A first\-principles proof of the convergence rate\.

The Perron–Frobenius argument above is an existence and uniqueness statement, and it does not by itself derive the geometric rateO⁡\(\(1−d\)k\)O\(\(1\-d\)^\{k\}\)used throughout the paper\. The same rate follows from an elementary contraction argument that avoids any assumption onMM’s spectrum\. For a row\-stochastic matrixMMand any real vectorxx,

‖x​M‖1=∑j\|∑ixi​Mi​j\|≤∑j∑i\|xi\|​Mi​j=∑i\|xi\|​∑jMi​j=‖x‖1,\\\|xM\\\|\_\{1\}=\\sum\_\{j\}\\Bigl\|\\sum\_\{i\}x\_\{i\}M\_\{ij\}\\Bigr\|\\leq\\sum\_\{j\}\\sum\_\{i\}\|x\_\{i\}\|M\_\{ij\}=\\sum\_\{i\}\|x\_\{i\}\|\\sum\_\{j\}M\_\{ij\}=\\\|x\\\|\_\{1\},\(13\)using only the triangle inequality and∑jMi​j=1\\sum\_\{j\}M\_\{ij\}=1\. Let𝝅k\\bm\{\\pi\}\_\{k\}be thekk\-th power\-iteration estimate and𝝅∗\\bm\{\\pi\}^\{\*\}the fixed point of Eq\. equation[4](https://arxiv.org/html/2610.08959#S3.E4)\. Subtracting𝝅∗=\(1−d\)​𝝅∗​M\+d​𝐮⊤\\bm\{\\pi\}^\{\*\}=\(1\-d\)\\bm\{\\pi\}^\{\*\}M\+d\\mathbf\{u\}^\{\\top\}from𝝅k\+1=\(1−d\)​𝝅k​M\+d​𝐮⊤\\bm\{\\pi\}\_\{k\+1\}=\(1\-d\)\\bm\{\\pi\}\_\{k\}M\+d\\mathbf\{u\}^\{\\top\}cancels the teleportation term exactly, leaving𝝅k\+1−𝝅∗=\(1−d\)​\(𝝅k−𝝅∗\)​M\\bm\{\\pi\}\_\{k\+1\}\-\\bm\{\\pi\}^\{\*\}=\(1\-d\)\(\\bm\{\\pi\}\_\{k\}\-\\bm\{\\pi\}^\{\*\}\)M, so applying Eq\. equation[13](https://arxiv.org/html/2610.08959#A2.E13)withx=𝝅k−𝝅∗x=\\bm\{\\pi\}\_\{k\}\-\\bm\{\\pi\}^\{\*\}and iterating gives

‖𝝅k−𝝅∗‖1≤\(1−d\)k​‖𝝅0−𝝅∗‖1≤2​\(1−d\)k,\\\|\\bm\{\\pi\}\_\{k\}\-\\bm\{\\pi\}^\{\*\}\\\|\_\{1\}\\;\\leq\\;\(1\-d\)^\{k\}\\,\\\|\\bm\{\\pi\}\_\{0\}\-\\bm\{\\pi\}^\{\*\}\\\|\_\{1\}\\;\\leq\\;2\(1\-d\)^\{k\},\(14\)where the last step uses that both are probability vectors, so theirL1L\_\{1\}distance is at most22regardless of initialization or graph topology\. Solving Eq\. equation[14](https://arxiv.org/html/2610.08959#A2.E14)for the smallestkkthat reaches a target toleranceεtol\\varepsilon\_\{\\text\{tol\}\}givesk≥log⁡\(2/εtol\)/\(−log⁡\(1−d\)\)k\\geq\\log\(2/\\varepsilon\_\{\\text\{tol\}\}\)/\(\-\\log\(1\-d\)\), and atd=0\.15d=0\.15with the training toleranceεtol=10−6\\varepsilon\_\{\\text\{tol\}\}=10^\{\-6\}used throughout, this bound isk≈89k\\approx 89\. The power iteration in practice converges in under5050steps, roughly half of this worst\-case figure, since Eq\. equation[14](https://arxiv.org/html/2610.08959#A2.E14)bounds the distance from an*arbitrary*initialization by the loosest possible constant22, the diameter of the probability simplex inL1L\_\{1\}, while power iteration is initialized at the uniform distribution𝐮\\mathbf\{u\}itself, which is already closer to𝝅∗\\bm\{\\pi\}^\{\*\}than a worst\-case starting point\.

#### Corollary on the edge\-weighting scheme\.

Eq\. equation[14](https://arxiv.org/html/2610.08959#A2.E14)’s derivation uses only thatMMis row\-stochastic, and it does not use how the pre\-normalization edge weightsw⁡\(vi→vj\)w\(v\_\{i\}\\to v\_\{j\}\)were assigned\. The soft\-pruning weightsw=1/d​f​\(e\)w=1/df\(e\)of Eq\. equation[3](https://arxiv.org/html/2610.08959#S3.E3)and the Soft\-Pruning ablation’s constant weights \(Table[2](https://arxiv.org/html/2610.08959#S4.T2)\) both row\-normalize to a validMM, so Proposition[1](https://arxiv.org/html/2610.08959#Thmproposition1)’s existence, uniqueness, and convergence guarantees hold identically for both\. The gap between them in Table[2](https://arxiv.org/html/2610.08959#S4.T2), 0\.8 to 5\.5 pp in Section[4\.3](https://arxiv.org/html/2610.08959#S4.SS3), is therefore attributable entirely to which entities the two weighting schemes make central, not to any difference in whether𝝅∗\\bm\{\\pi\}^\{\*\}is well\-defined or how fast it is reached\.

#### Corollary on signal range and trajectory length\.

Proposition[1](https://arxiv.org/html/2610.08959#Thmproposition1)boundsℓgraph​\(t\)\\ell\_\{\\text\{graph\}\}\(t\)within\[log⁡d,log⁡T\]\[\\log d,\\,\\log T\], a range whose width is set entirely by the current trajectory’s lengthTT, equivalently the graph’s node count, onceddis fixed\. Figure[3](https://arxiv.org/html/2610.08959#S4.F3)\(left\) reportsTTcontracting from about4747nodes at initialization to a plateau of2525to3030over the first150150training steps\. By Proposition[1](https://arxiv.org/html/2610.08959#Thmproposition1), this alone narrows the theoretical upper end ofℓgraph\\ell\_\{\\text\{graph\}\}’s range fromlog⁡47≈3\.85\\log 47\\approx 3\.85to betweenlog⁡25≈3\.22\\log 25\\approx 3\.22andlog⁡30≈3\.40\\log 30\\approx 3\.40, while the lower end,log⁡d≈−1\.90\\log d\\approx\-1\.90, is unaffected byTT\. The structural credit signal therefore continues to operate over a range of comparable width as trajectories shorten, rather than collapsing toward the neutral point00asTTfalls\. This is consistent with the ablations and the audit finding the structural credit signal informative throughout training rather than only early on\.

#### Intermediate steps carry structural credit, not only terminal ones\.

Eq\. equation[4](https://arxiv.org/html/2610.08959#S3.E4)is a fixed point over all steps, not an accumulation at the trajectory’s end:πt∗=\(1−d\)​∑iπi∗​Mi​t\+d/T\\pi^\{\*\}\_\{t\}=\(1\-d\)\\sum\_\{i\}\\pi^\{\*\}\_\{i\}M\_\{it\}\+d/T, so a step’s mass is exactly the rarity\-weighted inflow of the dependency chains its action consumes, plus the teleport floor\. Accordinglyℓgraph​\(t\)\>0\\ell\_\{\\text\{graph\}\}\(t\)\>0precisely when this inflow exceeds the uniform level1/T1/T, which happens wherever several upstream state changes are exercised together, at intermediate milestones such as retrieving an object, opening or heating it, or carrying it to a target receptacle, and not only at the final action\. Two properties keep this intermediate credit actionable: the mask of Eq\. equation[9](https://arxiv.org/html/2610.08959#S3.E9)standardizes aptitude within each trajectory, so a mid\-trajectory milestone that outranks the resolving step in its own rollout receives the larger supervision weight, and Proposition[1](https://arxiv.org/html/2610.08959#Thmproposition1)floors every step’s mass atd/Td/T, so no step is starved before masking\. Empirically, the credit\-content audit, which perturbs decision points across sampled trajectories, ranks them against executed\-replay impact atρ=0\.58\\rho=0\.58with Hit@10%=0\.48=0\.48against a chance level of0\.100\.10\.

#### The role of the damping factor\.

The damping factorddtrades off two properties that Eq\. equation[14](https://arxiv.org/html/2610.08959#A2.E14)and Proposition[1](https://arxiv.org/html/2610.08959#Thmproposition1)make explicit and opposing\. A largerddtightens the convergence bound,k=O⁡\(1/d\)k=O\(1/d\)for smalldd, but also raises the floorlog⁡d\\log dtoward00, compressingℓgraph\\ell\_\{\\text\{graph\}\}’s range and pulling𝝅∗\\bm\{\\pi\}^\{\*\}closer to the uninformative uniform distribution𝐮\\mathbf\{u\}in the limitd→1d\\to 1\. A smallerddwidens the usable range through a lower, more negative floor that lets peripheral steps register as clearly below neutral rather than merely below average, but it slows convergence and, in the degenerate limitd→0d\\to 0, forfeits the guarantee above thatMMalone is primitive on every graph topology\. The selectedd=0\.15d=0\.15sits well inside this trade\-off, since it is small enough thatlog⁡d≈−1\.90\\log d\\approx\-1\.90leavesℓgraph\\ell\_\{\\text\{graph\}\}a range comparable toℓmodel\\ell\_\{\\text\{model\}\}’s±2\.40\\pm 2\.40\(Proposition[1](https://arxiv.org/html/2610.08959#Thmproposition1)\), while large enough that the8989\-iteration worst\-case bound above remains a small fraction of a single training step’s compute budget\.

#### Graph construction cost\.

Graph construction isO⁡\(T2​\|ℱ\|\)O\(T^\{2\}\|\\mathcal\{F\}\|\)per trajectory, negligible at typical agent trajectory lengths,T≤50T\\leq 50\. Table[6](https://arxiv.org/html/2610.08959#A2.T6)measures this directly, comparing the wall\-clock time spent on Footprint extraction, edge construction, and the stationary\-distribution solve against the total per\-training\-step time, where graph construction accounts for well under half a percent of the step budget on every benchmark\.

Table 6:Wall\-clock cost of graph construction relative to the total per\-training\-step time\.
#### Centrality computation\.

The damping termd\>0d\>0guarantees a unique stationary distribution regardless of graph topology, by the Perron–Frobenius argument given above, and it is obtained by power iteration to tolerance‖𝝅k\+1∗−𝝅k∗‖1<10−6\\\|\\bm\{\\pi\}^\{\*\}\_\{k\+1\}\-\\bm\{\\pi\}^\{\*\}\_\{k\}\\\|\_\{1\}<10^\{\-6\}, which converges in under 50 iterations forT=50T=50, consistent with theO⁡\(\(1−d\)k\)O\(\(1\-d\)^\{k\}\)geometric rate proved there\.

#### Numerical details\.

The floorε=0\.1\\varepsilon=0\.1in Eq\. equation[7](https://arxiv.org/html/2610.08959#S3.E7)bounds the divergence signal and keeps the log\-odds finite atrt∈\{0,1\}r\_\{t\}\\in\\\{0,1\\\}, and Proposition[1](https://arxiv.org/html/2610.08959#Thmproposition1)gives the exact range of both signals and why neither can unilaterally dominate the fusion\. Becauseσ⁡\(⋅\)\\sigma\(\\cdot\)lies strictly between00and11for any finite argument, the mask sum∑tm⁡\(t\)\\sum\_\{t\}m\(t\)is positive on every trajectory withsτ\>0s\_\{\\tau\}\>0\. On the rare trajectory whereA⁡\(t\)A\(t\)is exactly constant across all steps, so thatsτ=0s\_\{\\tau\}=0, no step’s aptitude differs from the trajectory’s own average, so we setm⁡\(t\)=σ⁡\(0\)=12m\(t\)=\\sigma\(0\)=\\tfrac\{1\}\{2\}for alltt, i\.e\. uniform weighting\. Either way, the normalized loss in Eq\. equation[10](https://arxiv.org/html/2610.08959#S3.E10)is always a well\-defined weighted average, and the normalization keeps the loss magnitude invariant to mask sparsity, soλ\\lambdaneeds no re\-tuning as sparsity shifts over training\.

#### Soft mask\.

Unlike hard\-threshold masking, the soft mask varies smoothly with the standardized aptitude, reallocating the supervision budget gradually rather than admitting or excluding a step outright, and it is computed from the rollout’s detached statistics, acting as a fixed per\-step weight within each update\. Standardizing within the trajectory before the sigmoid, rather than applying one threshold across all trajectories, keeps the same relative cutoff, above this trajectory’s own average aptitude, meaningful regardless of where that trajectory’s absolute aptitude scale happens to sit at that point in training \(Proposition[2](https://arxiv.org/html/2610.08959#Thmproposition2)\)\.

#### Effective concentration of the soft mask\.

Read literally, the mask of Eq\. equation[9](https://arxiv.org/html/2610.08959#S3.E9)never excludes a step:σ\\sigmamaps every finite aptitude into\(0,1\)\(0,1\), so every step retains a positive weight and the normalized loss of Eq\. equation[10](https://arxiv.org/html/2610.08959#S3.E10)is a re\-weighting of the distillation term rather than a hard selection of the kind probed in Figure[1](https://arxiv.org/html/2610.08959#S1.F1)\. The relevant question is therefore how strongly the re\-weighting concentrates, and the standardized form of the mask makes this quantifiable: sincez⁡\(t\)=\(A⁡\(t\)−μτ\)/sτz\(t\)=\(A\(t\)\-\\mu\_\{\\tau\}\)/s\_\{\\tau\}is exactly zero\-mean and unit\-variance within each trajectory, the concentration ofm⁡\(t\)=σ⁡\(z⁡\(t\)\)m\(t\)=\\sigma\(z\(t\)\)depends only on the shape of the trajectory’s aptitude distribution\. Under a Gaussian reference shape the effective sample sizeESS=\(∑tm⁡\(t\)\)2/∑tm​\(t\)2\\mathrm\{ESS\}=\(\\sum\_\{t\}m\(t\)\)^\{2\}/\\sum\_\{t\}m\(t\)^\{2\}equals about0\.85​T0\.85\\,Tand the above\-mean mass share∑z\>0m⁡\(t\)/∑tm⁡\(t\)\\sum\_\{z\>0\}m\(t\)/\\sum\_\{t\}m\(t\)about0\.680\.68; on the two logged rollouts used in our case studies, a 50\-step and a 6\-step episode, the same quantities compute to0\.850\.85with share0\.670\.67and0\.850\.85with share0\.660\.66, the mean weight of above\-mean steps exceeds that of below\-mean steps by about a factor of two, and extreme steps differ by up to a factor of seven \(m∈\[0\.13,0\.93\]m\\in\[0\.13,\\,0\.93\]on the 50\-step rollout\), whose twelve highest\-aptitude steps absorb37%37\\%of the distillation mass under the soft mask against100%100\\%under a budget\-matched hard top\-12 selection\. Three considerations make this moderate concentration the intended operating point rather than a shortfall\. First, the hard top\-kkrule of Figure[1](https://arxiv.org/html/2610.08959#S1.F1)is a diagnostic of the divergence signal, not a candidate training mask: it was applied to raw KL precisely to test whether divergence magnitude locates outcome\-relevant steps, so it shares neither the aptitude’s placement nor the smoothness properties below\. Second, the KL term againstπθold\\pi\_\{\\theta\_\{\\text\{old\}\}\}also acts as an on\-support trust region; a hard mask would remove that anchor from the majority of steps, whereas the soft mask keeps a positive floorm⁡\(t\)≥σ⁡\(mint′⁡z⁡\(t′\)\)\>0m\(t\)\\geq\\sigma\(\\min\_\{t^\{\\prime\}\}z\(t^\{\\prime\}\)\)\>0on every step\. Third, concentration without correct placement is worthless: the Shuffled Centrality control of Table[2](https://arxiv.org/html/2610.08959#S4.T2)redistributes exactly the same mask values, hence exactly the same dose and the same ESS, onto the wrong steps and loses up to 6\.2 pp, so the active ingredient is where the mass goes rather than how hard the selection is; a budget\-matched hard\-mask variant of GraphOPD is a natural ablation left to future work, and the evidence above indicates it would alter the dose distribution without altering the placement that the ablation identifies as decisive\.

#### Teacher cost\.

Usingπθold\\pi\_\{\\theta\_\{\\text\{old\}\}\}as the teacher requires no additional model, checkpoint, or inference call beyond the GRPO training loop, and the drop\-in wrapper leaves the GRPO optimizer and rollout infrastructure unmodified\.

## Appendix CExperimental Setup and Motivating Study Details

#### Benchmarks\.

This paragraph gives each of the three agentic benchmarks’ task format, dependency structure, and evaluation protocol\. ALFWorld\([Shridhar et al\., 2021](https://arxiv.org/html/2610.08959#bib.bib33)\)embeds a text interface around simulated household scenes, requiring an agent to retrieve, heat, clean, or relocate objects through a fixed vocabulary of navigation and manipulation actions \(Table[5](https://arxiv.org/html/2610.08959#A1.T5)\)\. Almost every action changes which objects and locations are reachable next, so a single early misstep can make the goal unreachable no matter how the remainder of the trajectory is executed, and this is where the dependency\-graph hypothesis makes its strongest prediction\. We score it by task success rate on the standard 3,553/140 train/test split, with episodes capped at 50 turns\. WebShop\([Yao et al\., 2022](https://arxiv.org/html/2610.08959#bib.bib34)\)simulates an e\-commerce search\-and\-purchase task over a large product catalog, with an action space of free\-form search queries and page\-element clicks rather than ALFWorld’s fixed verb\-object grammar\. Its dependencies are informational rather than physical, since later clicks depend on which attributes and product identifiers an earlier search surfaced, so the Footprint extractor tracks query tokens and selected products instead of object locations\. We report both completion score and binary success rate on the standard 1,012/500 split, capped at 15 turns\. SearchQA aggregates seven open\-domain question\-answering datasets, categorized into single\-hop factoid questions, NarrativeQA\([Kociský et al\., 2018](https://arxiv.org/html/2610.08959#bib.bib38)\), TriviaQA\([Joshi et al\., 2017](https://arxiv.org/html/2610.08959#bib.bib39)\), and PopQA\([Mallen et al\., 2023](https://arxiv.org/html/2610.08959#bib.bib40)\), and multi\-hop questions, HotpotQA\([Yang et al\., 2018](https://arxiv.org/html/2610.08959#bib.bib37)\), 2WikiMultihopQA\([Ho et al\., 2020](https://arxiv.org/html/2610.08959#bib.bib41)\), MuSiQue\([Trivedi et al\., 2022](https://arxiv.org/html/2610.08959#bib.bib42)\), and Bamboogle\([Press et al\., 2023](https://arxiv.org/html/2610.08959#bib.bib43)\), formatted as a<search\>/<think\>/<answer\>loop capped at 10 turns\. Here dependencies run only through retrieved evidence, with no physical state change at all, which tests whether the mechanism generalizes beyond the setting that motivated it, and we score it by accuracy over the seven datasets\. The ALFWorld and SearchQA Avg columns of Table[1](https://arxiv.org/html/2610.08959#S4.T1)weight each per\-category number by that category’s episode count in the evaluation split, so they do not reduce to the unweighted mean of the displayed numbers\. The four out\-of\-domain benchmarks probed in Section[4\.4](https://arxiv.org/html/2610.08959#S4.SS4)are specified together with their prompts, Footprint extractor, and full results in Appendix[D](https://arxiv.org/html/2610.08959#A4)\.

#### Training configuration\.

All methods are optimized with AdamW at learning rate10−610^\{\-6\}under a cosine schedule with a 50\-step warmup, batch size 64 trajectories per step formed as 8 tasks with 8 rollouts each, and gradient clipping at 1\.0\. GRPO uses group sizeG=8G=8and clip ratioε=0\.2\\varepsilon=0\.2\. Each training run uses 8 H100 GPUs\. Training runs for 150 steps on ALFWorld, WebShop, and SearchQA, with evaluation every 10 steps\. GraphOPD’s own hyperparameters are listed with the grid search in the final appendix section below, namely the mixing coefficientα\\alpha, the loss coefficientλ\\lambda, the centrality damping factord=0\.15d=0\.15, its power\-iteration tolerance10−610^\{\-6\}, and the smoothing floorε=0\.1\\varepsilon=0\.1of Eq\. equation[7](https://arxiv.org/html/2610.08959#S3.E7)\.

#### Run variance\.

GraphOPD, SDAR, OPID, and GEPO are each trained with three independent runs, and Table[1](https://arxiv.org/html/2610.08959#S4.T1)reports their means on the three headline metrics, namely the ALFWorld average success rate, the SearchQA average accuracy, and the WebShop success rate\. Table[7](https://arxiv.org/html/2610.08959#A3.T7)lists the corresponding run\-to\-run standard deviations\. GraphOPD has the smallest worst\-case spread of the four, with a maximum standard deviation of 1\.60 pp, while the largest is SDAR’s 5\.09 pp on 1\.7B ALFWorld\. All remaining rows of Table[1](https://arxiv.org/html/2610.08959#S4.T1)are single\-run point estimates\.

Table 7:Mean and run\-to\-run standard deviation \(pp\) over three independent runs for the four multi\-run methods of the main results, on ALFWorld and WebShop success rate and SearchQA accuracy\.
#### Baseline families\.

The eleven baselines span four axes of comparison\. Vanilla and GRPO establish lower bounds without any teacher signal, isolating how much of GraphOPD’s gain is attributable to distillation at all rather than to the GRPO backbone alone\. Skill\-Prompt, Skill\-GRPO, and Skill\-SD inject external skill demonstrations or privileged information, and they therefore bound what such context adds on top of the same backbone\. OPSD, GRPO\+OPSD, RLSD\([Yang et al\., 2026a](https://arxiv.org/html/2610.08959#bib.bib6)\), SDAR\([Lu et al\., 2026](https://arxiv.org/html/2610.08959#bib.bib5)\), and OPID\([Yang et al\., 2026b](https://arxiv.org/html/2610.08959#bib.bib10)\)share GraphOPD’s GRPO backbone and model family and allocate their distillation or advantage signal by teacher\-student divergence magnitude alone, so they form our direct comparison set and the basis for the per\-scale deltas in Section[4\.2](https://arxiv.org/html/2610.08959#S4.SS2)\. GEPO\([Yuan et al\., 2025](https://arxiv.org/html/2610.08959#bib.bib17)\)instead reweights the GRPO advantage itself with a graph\-based credit score rather than adding a distillation loss, and is the closest prior baseline to our own structural credit signal\.

#### Prompts\.

Each benchmark’s policy is queried with a fixed system prompt that fixes the admissible action vocabulary, and the Footprint extractor specified below parses exactly this vocabulary, so the prompt and the extractor are specified against the same action set by construction\. Each prompt is instantiated once per episode with the task instruction and then re\-issued every step with the running observation and action history appended\. None of the three mentions the teacher, the dependency graph, or GraphOPD’s training objective, so the graph and centrality computation \(Section[3\.2](https://arxiv.org/html/2610.08959#S3.SS2)\) have no visibility into or influence on what the policy is shown\. The prompts for the four out\-of\-domain benchmarks are given in Appendix[D](https://arxiv.org/html/2610.08959#A4)\.

> ALFWorld\.You are a household robot completing a task in a simulated home\. You will be given a task and, at each step, an observation of the room\. Choose exactly one admissible action per step from: go to \{receptacle\}, open \{receptacle\}, close \{receptacle\}, take \{object\} from \{receptacle\}, put \{object\} in/on \{receptacle\}, heat \{object\} with \{receptacle\}, cool \{object\} with \{receptacle\}, clean \{object\} with \{receptacle\}, examine \{object\}, use \{object\}\. Respond with exactly one line: "Action: \{action\}"\. Task: \{task\_instruction\} Observation: \{observation\} Admissible actions: \{admissible\_action\_list\}

> WebShop\.You are a shopping assistant browsing an online store to complete a purchase instruction\. At each turn you see the current page and its clickable elements\. Choose exactly one action: search\[\{query\}\] to issue a search, or click\[\{element\}\] to click a product ID, an attribute/option, or the Buy Now button\. Respond with exactly one line: "Action: \{action\}"\. Instruction: \{purchase\_instruction\} Page: \{page\_observation\} Clickable elements: \{clickable\_list\}

> SearchQA\.Answer the question by interleaving reasoning and retrieval\. You may use <think\>\.\.\.</think\> to reason and <search\>query</search\> to retrieve passages, repeating either as many times as needed, and must finish with <answer\>final answer</answer\>\. Question: \{question\}

#### Motivating empirical study\.

The motivating study in Section[1](https://arxiv.org/html/2610.08959#S1)uses a 7B Qwen2\.5\-Instruct agent on ALFWorld under the same GRPO backbone and training configuration as the main experiments\. For the selection comparison, per\-trajectory distillation is restricted to thekkhighest\-KL steps,k∈\{5,8,10,12\}k\\in\\\{5,8,10,12\\\}, or tokkrandomly chosen steps, with all other conditions identical, and each configuration is trained for 150 steps\. For the outcome\-level check, 50 rollouts provide 466 successful and 466 failed steps\.

## Appendix DOut\-of\-Distribution Generalization

#### Benchmarks and protocol\.

Four out\-of\-domain benchmarks test whether the dependency\-graph mechanism transfers beyond the three agentic settings to a different domain and a different tool\. They are AIME24 and AIME25 in competition mathematics, GPQA\-Diamond in graduate\-level science, and LiveCodeBench\-v5 in program synthesis, all run as multi\-turn tool\-integrated reasoning\. AIME24 and AIME25 are scored by avg@32 and the other two by avg@8\. Each benchmark uses a Python code interpreter and follows the protocol of SOD\([Zhong et al\., 2026](https://arxiv.org/html/2610.08959#bib.bib3)\), so the policy interleaves reasoning text with code\-interpreter calls over several turns before committing to a final answer\. Each turn therefore has an action, the model’s own reasoning text or code, and an observation, the interpreter’s response, which gives the four benchmarks the same action\-observation structure as ALFWorld, WebShop, and SearchQA under a different tool and domain\. This tests transfer across domains and tool vocabularies rather than across trajectory structure\. All runs use Qwen2\.5\-7B\-Instruct with the same GRPO backbone, training configuration, and step budget as the main experiments, and they compare against Vanilla, GRPO, OPSD, and SDAR\.

#### Prompts\.

The two mathematics sets and GPQA\-Diamond share the math/science template below, and LiveCodeBench\-v5 uses the code template\. Both are instantiated once per problem and re\-issued every turn with the running reasoning text and interpreter history appended\.

> AIME24 / AIME25 / GPQA\-Diamond\.Analyze and solve the following problem step by step\. The code interpreter can be called for precise or exploratory calculations and to verify a result before committing to it; first form a high\-level solution strategy, then use the interpreter as needed\. Once the final answer is confirmed, stop calling the interpreter and give it as \\boxed\{answer\} on its own line, an integer for AIME24/AIME25 and a single option letter for GPQA\-Diamond\. Problem: \{problem\}

> LiveCodeBench\-v5\.Generate a correct Python program that matches the following problem specification and passes all tests\. The code interpreter can be used to check the program’s correctness against the public examples before submitting; first form a high\-level solution strategy, then use the interpreter to verify\. The submitted program must read from standard input and write to standard output, enclosed in a single fenced code block\. Problem: \{problem\_statement\} Public examples: \{public\_examples\}

#### Footprint extractor\.

The four benchmarks share one extractor, since a turn in each of them consists of reasoning text, an optional Python code block, and the interpreter’s response, and the dependency structure runs through the identifiers and values that one turn introduces and a later turn reuses\. Table[8](https://arxiv.org/html/2610.08959#A4.T8)lists the keys thatℱenv​\(at,ot\)\\mathcal\{F\}\_\{\\text\{env\}\}\(a\_\{t\},o\_\{t\}\)emits for such a turn, read from the turn’s own code and reasoning text for the produced keys and from the interpreter response for the returned ones, in the same<type\>:<entity\>form as Table[5](https://arxiv.org/html/2610.08959#A1.T5)\. Edge construction, rarity weighting, backtrack edges, and sequential edges then follow Eqs\. equation[2](https://arxiv.org/html/2610.08959#S3.E2)and equation[3](https://arxiv.org/html/2610.08959#S3.E3)unchanged, withaja\_\{j\}the later turn’s code and reasoning text andojo\_\{j\}the interpreter response, so a repeated identical interpreter output marks a revisit exactly as a repeated observation does in ALFWorld\.

Table 8:Footprint extractor specification for the four out\-of\-domain tool\-integrated\-reasoning benchmarks\.d​f​\(e\)df\(e\)counts the turns whose code, reasoning text, or interpreter response mentionsee, so a helper variable introduced once and consumed by the next turn yields an edge weight near11, while a loop counter or a common library name yields a small weight that the row normalization dilutes\. The structural credit signal, the aptitude of Eq\. equation[8](https://arxiv.org/html/2610.08959#S3.E8), and the trajectory\-relative mask of Eq\. equation[9](https://arxiv.org/html/2610.08959#S3.E9)carry over with the sameα\\alpha,λ\\lambda,dd, andε\\varepsilonas the agentic benchmarks, so the transfer experiment changes the domain and the tool vocabulary while holding the mechanism fixed\.

#### Results\.

Table[9](https://arxiv.org/html/2610.08959#A4.T9)reports the full numbers behind Figure[3](https://arxiv.org/html/2610.08959#S4.F3)\(middle\), namely task accuracy on AIME24 and AIME25 under avg@32 and on LiveCodeBench\-v5 and GPQA\-Diamond under avg@8\. GraphOPD attains the best accuracy on all four benchmarks, averaging 29\.0% against 20\.0% for SDAR and 19\.8% for OPSD, and its lead holds on each benchmark separately, reaching \+12\.4 pp on LiveCodeBench\-v5 over SDAR\.

Table 9:Task accuracy \(%\) on four out\-of\-domain tool\-integrated\-reasoning benchmarks, with the scoring protocol per benchmark given in the text above\.

## Appendix ESignal Validation and Case Study

#### Signal redundancy diagnostic\.

The fusion in Section[3\.4](https://arxiv.org/html/2610.08959#S3.SS4)is a weighted sum ofℓmodel\\ell\_\{\\text\{model\}\}andℓgraph\\ell\_\{\\text\{graph\}\}, so it implicitly assumes the two sources are not strongly*redundant*, since if they carried near\-identical evidence, weighting both byα\\alphaand1−α1\-\\alphawould double\-count the same signal rather than combining two complementary ones\. Rather than a separate correlation diagnostic, the ablation \(Table[2](https://arxiv.org/html/2610.08959#S4.T2), Section[4\.3](https://arxiv.org/html/2610.08959#S4.SS3)\) already tests this functionally, because ifℓmodel\\ell\_\{\\text\{model\}\}andℓgraph\\ell\_\{\\text\{graph\}\}carried near\-identical evidence, dropping either one alone, Divergence\-only or Structural\-only, would cost little, as the remaining signal would recover most of the same information\. Instead, both cost a substantial fraction of GraphOPD’s full gain at every scale, Divergence\-only 3\.9 to 10\.5 pp and Structural\-only 2\.3 to 6\.5 pp, and neither recovers what the other drops, so the two signals are complementary rather than redundant\.

#### Credit\-content validation\.

The Analysis subsection of Section[4](https://arxiv.org/html/2610.08959#S4)reports the credit\-content audit, and this appendix fixes its protocol\.

#### Counterfactual audit\.

We construct causal ground truth on ALFWorld by executed replay, re\-sampling the policy’s own alternative action at each decision point of a sampled set of trajectories, rolling the environment forward from the resulting state, and recording whether the outcome changes, so a step’s ground\-truth contribution is the outcome change induced by its alternative, the same executed\-replay principle used elsewhere to audit step\-level credit signals\([Zhang, 2026](https://arxiv.org/html/2610.08959#bib.bib24)\)\. We report, for each ofℓgraph\\ell\_\{\\text\{graph\}\},ℓmodel\\ell\_\{\\text\{model\}\}, and a random score, the Spearman rank correlationρ\\rhowith this contribution and Hit@10%, the fraction of the signal’s top\-10% steps that are truly top\-10% impactful, for which chance is0\.100\.10\. The decisive comparison isℓgraph\\ell\_\{\\text\{graph\}\}against the random score, since the claim that the structural credit signal identifies outcome\-relevant steps requires both to sit clearly above chance, and the comparison againstℓmodel\\ell\_\{\\text\{model\}\}measures how much the structural credit signal adds over the divergence signal alone\.ℓgraph\\ell\_\{\\text\{graph\}\}attainsρ=0\.58\\rho=0\.58and Hit@10%=0\.48=0\.48, well above the random score atρ=−0\.06\\rho=\-0\.06and Hit@10%=0\.13=0\.13andℓmodel\\ell\_\{\\text\{model\}\}atρ=0\.34\\rho=0\.34and Hit@10%=0\.41=0\.41\.

#### Shuffled\-centrality control\.

To separate credit content from supervision redistribution, the ablation \(Table[2](https://arxiv.org/html/2610.08959#S4.T2)\) includes a Shuffled Centrality row that replacesℓgraph\\ell\_\{\\text\{graph\}\}with a within\-trajectory permutation of itself, matched to the real one in mask sparsity and weight distribution, and runs the full training pipeline under otherwise identical conditions\. Where the real graph retains its advantage over the shuffled one at matched dose, that gain is attributable to the content of the dependency structure rather than to the act of non\-uniform weighting itself, and where it does not, part of the gain is attributable to redistribution alone\. Table[2](https://arxiv.org/html/2610.08959#S4.T2)’s discussion in the main text reports which of the two holds at each scale and benchmark\.

#### Case study\.

Table[10](https://arxiv.org/html/2610.08959#A5.T10)first gives a side\-by\-side rollout comparison on the same task and environment seed \(”put some soapbottle on cabinet”,seed=1000\) under two checkpoints of the same training run, an early one at step 20 and a later one at step 150\. Unlike a controlled trajectory pair that shares a fixed prefix, the two policies differ from the first action, so the table shows how far training reshapes the whole strategy rather than a single decision\.

Table 10:A side\-by\-side comparison of two rollouts in ALFWorld\. Both checkpoints attempt the same task and environment seed \(”put some soapbottle on cabinet”,seed=1000\) from the same training run\. Their strategies differ from the first action, so the early checkpoint never engages the target object at all\.Table[11](https://arxiv.org/html/2610.08959#A5.T11)turns to the signal comparison from Figure[3](https://arxiv.org/html/2610.08959#S4.F3)\(right\), an eight\-step window of a single real successful ALFWorld trajectory \(”put some soapbottle on cabinet”\), with the raw per\-step teacher\-student KL andℓgraph​\(t\)\\ell\_\{\\text\{graph\}\}\(t\)plotted as two aligned bar charts over the same eight steps\. The table lists the same eight steps in full, giving the exact action text and both signals’ values\.

Table 11:Qualitative case study on a window \(steps 3 to 10\) of a real successful ALFWorld trajectory \(”put some soapbottle on cabinet”\)\. Raw KL peaks at step 4, a cabinet\-revisit step that does not decide the outcome, whileℓgraph​\(t\)\\ell\_\{\\text\{graph\}\}\(t\)peaks at step 10, the object\-placement action decisive within this window\. Bold marks each column’s peak\.The decisive object\-placement action at step 10, moving the soapbottle onto the cabinet, has one of the lowest raw KL values in the window, so a KL\-only rule would spend its budget on step 4 instead, a revisit to the cabinet that does not bear on the outcome\.ℓgraph\\ell\_\{\\text\{graph\}\}peaks exactly at step 10, since four earlier steps, step 4 \(go to cabinet 1\), step 5 \(open cabinet 1\), step 8 \(go to cabinet 1 again\), and step 9 \(examine cabinet 1\), all reference the samecabinet 1entity that step 10’s action consumes\. Both signals are computed by running the paper’s own Footprint, edge\-construction, and stationary\-distribution pipeline on the real logged actions, using the dependency and sequential edges that the action text supports\.

Table[12](https://arxiv.org/html/2610.08959#A5.T12)adds a second case on the position of the credit peak, on a complete representative successful Heat\-type episode \(twelve steps, terminating at the resolving placement\) whose actions and observations follow the grammar and Footprint conventions of Appendix[A](https://arxiv.org/html/2610.08959#A1)\. The credit peak falls well before the end of the trajectory, at step 7, the revisit of the processing location where the heating dependency chain converges, four steps ahead of the terminal placement; the processing chain’s earlier approach \(step 4,\+0\.95\+0\.95\) and the heating action itself \(step 6,\+0\.51\+0\.51\) also carry strong credit, while the terminal placement \(step 11,\+0\.08\+0\.08\), which merely deposits an already\-processed object into a receptacle the agent had explored earlier, stays near neutral\. Credit therefore concentrates on the mid\-trajectory transformation that decides the outcome, not on the trajectory’s last action\.

Table 12:Qualitative case study on a complete representative successful Heat\-type episode \(twelve steps; actions and observations follow the ALFWorld grammar and Footprint conventions of Appendix[A](https://arxiv.org/html/2610.08959#A1)\)\. The structural credit peaks at step 7, the processing\-location revisit four steps before the terminal placement, with the earlier processing\-location approach \(step 4\) and the heating action \(step 6\) also well above neutral; the terminal placement \(step 11\) stays near neutral\. Raw teacher\-student KL is reported for contrast: its maximum \(step 8\) coincides with the structural\-credit minimum\. Bold marks each column’s peak\.