Call Neighbours Yourself: Graph Walks with Destination-Conditioned On-Policy Self-Distillation

1 Introduction

• On WikiCS targets whose full neighbourhood fits the context, neighbour selection during generation outperforms embedding-based RAG at 6.3× fewer tokens.The comparison uses a frozen Qwen2.5-32B backbone and identical neighbour previews.Source: Figure 1 · p. 1, §1 · p. 2
• Fixed neighbour sets limit adaptation and recovery when decisive evidence lies outside the selected context, a problem on dense TAGs.On WikiCS, the full one-hop neighbourhood exceeds a 32K-token window for 40.3% of 2,340 test targets.Source: §1 · pp. 1–2
• CNY lets an LLM inspect lightweight previews and issue graph-walk actions during generation to acquire selected neighbours step by step.This replaces a pre-selected neighbour set with adaptive evidence acquisition.Source: §1 · p. 2
• Destination-conditioned OPSD uses the revealed destination to re-score the same LLM’s walk action and derive per-action credit without step labels, an external judge, or extra rollouts.The probability shift supplies credit where outcome-only RL lacks a direct signal for individual walks.Source: §1 · p. 2
• CNY outperforms fixed-context baselines across citation, hyperlink, co-purchase, and knowledge-graph benchmarks.The introduction reports this as the result of extensive experiments.Source: §1 · p. 2

2 Related Work

• Prior TAG methods use graph-aware prompting, adapters, or reinforcement learning over neighbourhoods selected by non-learned heuristics (Li et al., 2024a; He et al., 2024a; Tang et al., 2024a; Chen et al., 2024b; Kong et al., 2025; Wu et al., 2025b; Liu et al., 2026).CNY instead makes neighbour selection itself a learnable graph walk.Source: §2 · p. 2
• Agentic retrieval systems interleave reasoning with free-form queries to semantic retrievers over unstructured corpora (Asai et al., 2024; Li et al., 2025; Jin et al., 2025; Song et al., 2025; Chen et al., 2025), whereas CNY constrains actions to graph topology and observes destination-node text.CNY uses the destination node’s own text rather than a retrieval approximation.Source: §2 · p. 2
• Sparse-reward work includes process reward models requiring step-level supervision (Lightman et al., 2024; Wang et al., 2024) and on-policy self-distillation with outcome-privileged teachers (Shenfeld et al., 2026; Hübotter et al., 2026; Zhao et al., 2026; Wang et al., 2026b).CNY’s destination-conditioned OPSD provides action-level supervision from revealed neighbour destinations without labelled intermediate trajectories.Source: §2 · p. 2

• A TAG is defined by its adjacency matrix, node text descriptions, and label set with class descriptions.Source: §3 · p. 2
• Given a target node v0, the task is to predict its label from evidence distributed across its graph neighbourhood.Source: §3 · p. 2
• With a limited reading budget, selecting informative neighbours matters: uninformative text or burying decisive evidence degrades prediction, and WikiCS exceeds 32K tokens for 40.3% of evaluation nodes.Source: §3 · p. 3

4.1 Interactive Graph Environment

• The LLM sees ego-node text and neighbour previews, then reveals a selected neighbour’s full text and expands the frontier only to its previously unseen adjacent nodes.This makes evidence acquisition follow graph connectivity rather than allowing access to arbitrary nodes.Source: §4.1 · p. 3

4.2 Reward

• The reward favors correct predictions, valid action formatting, successful evidence acquisition, and answer completion, while assigning intermediate nonzero rewards to support learning before correct reasoning emerges.Its values encode a lexicographic ordering of desirable behaviors, not calibrated utility estimates.Source: §4.2 · p. 4

4.3 Reinforcement Learning Optimisation

• CNY trains its policy with GRPO (Shao et al., 2024); because uniform trajectory advantages poorly match walk decisions, OPSD re-prices the tokens that determine neighbour exploration.The method uses the Dr. GRPO implementation (Liu et al., 2025c).Source: §4.3 · p. 4

4.4 Destination-Conditioned On-Policy Self-Distillation (OPSD)

• OPSD re-evaluates selected node-ID tokens with destination information, adding hindsight credit only to successful walk actions while reasoning tokens remain supervised by trajectory reward.The destination recap compresses revealed content into a topic-level description; the teacher uses the realized destination rather than a gold answer or external supervision.Source: §4.4 · pp. 4–5

4.5 Training

• The final training loop samples N rollouts per target from the current policy, scores them with trajectory rewards, and refines trajectory advantages on walk-destination tokens with OPSD.Training uses the multi-task mixture described in §5.1.Source: §4.5 · p. 5

5.1 Setup

• CNY trains one checkpoint on eight text-attributed graphs and evaluates it without per-task fine-tuning on five held-out graphs spanning node-, edge-, and graph-level tasks.The graph-level task is absent during training; neighbour previews are deterministic prefixes of raw node text, and CNY and prior reasoners use identical raw node text.Source: §5.1 · p. 5

5.2 Main Results

• CNY achieves the highest zero-shot accuracy across every held-out setting, leading Graph-R1 on every task family.On unseen graph-level Expla-Graph, CNY scores 92.60 versus 89.71 for Graph-R1 and 85.92 for TRN-R1-Zero despite receiving only seed concepts while the baselines receive the full graph.Source: §5.2 · pp. 5–6, Table 1 · p. 6

5.3 Effectiveness of Walking

• At matched text budgets, walking improves accuracy across datasets; on WikiCS it also beats higher-token self-consistency and best-of-4 reranking.Rewiring WikiCS edges while preserving node degrees drops walk accuracy from 76.6 to 73.0, near the preview-plus-direct baseline’s 73.4, supporting the importance of real graph structure.Source: §5.3 · pp. 6–7, Table 2 · p. 7

5.4 Generalisation to Multi-Hop KGQA

• Without question-answering training, frozen CNY-14B reaches 58.4 WebQSP Hits@1, versus 38.5 from identical previews, 44.0 from the question alone, and 49.0 from the full 1-hop context.It walks 2.31 times per question, more than its roughly 1.2 realized depth on classification benchmarks, indicating exploration scales to multi-hop demands.Source: §5.4 · p. 7, Table 3 · p. 7

5.5 Effectiveness of OPSD

• OPSD improves cross-domain accuracy over GRPO at matched training reward, and its benefit rises with β on both WikiCS and Cora.For Qwen3-4B-Instruct-2507, WikiCS rises from 69.5 to 75.1 and Cora from 58.5 to 65.5 as β increases from 0 to 0.03. The recap supplies bidirectional, increasingly discriminative walk-action credit; rescaling reward tiers preserves results, but removing intermediate tiers collapses rollout behaviour.Source: §5.5 · pp. 7–8, Figure 3 · p. 7, Table 4 · p. 8

5.6 Impact of Different LLM Backbones

• CNY training improves held-out accuracy on both datasets for all five backbones, with the largest gains for the weakest base models.The improvement shrinks as backbone strength increases, indicating the benefit is not limited to one backbone or dataset.Source: Figure 4 · p. 8, §5.6 · p. 8

5.7 Computation Cost

• On a matched Qwen2.5-7B setup, OPSD raises compute from 12.0 to 14.8 PFLOP (+24%) and log-probability time from 14.1 to 17.6 s/step.Its extra teacher forward uses a bounded recap, making that overhead independent of graph-context size; inference cost scales with explored local context, not global graph size.Source: §5.7 · p. 9, Table 7 · p. 9

5.8 Case Study

• On WikiCS, walking corrects 290 direct errors while introducing 91 new errors; over 92% of analyzed flips arise from plausible but insufficiently discriminative evidence.Across 282 flips, adjacent-class interference accounts for 53.5%, misleading emphasis 39.4%, and reasoning drift 6.7%; no case exhausts the walk budget.Source: §5.8 · p. 9

6 Conclusion

• CNY consistently improves reasoning across multiple TAG benchmarks and transfers to unseen domains.The findings suggest effective graph reasoning depends on adaptively acquiring evidence as well as interpreting it.Source: §6 · p. 9
• CNY treats neighbour acquisition as graph-walk actions and supervises them with destination-conditioned on-policy self-distillation.The method derives action-level credit from revealed destinations without annotated trajectories, external judges, or additional rollouts.Source: §6 · p. 9

Limitations

• CNY cannot add domain facts absent from its backbone, and its walking gains shrink as backbone strength increases.Held-out accuracy tracks backbone scale; tasks requiring missing knowledge are unlikely to be solved without a stronger or further-pretrained backbone.Source: Limitations · p. 10
• Evaluation uses the GOFA-aligned zero-shot benchmark, but does not cover large-scale, heterogeneous or temporal graphs.Cross-task generalisation evidence is limited to Expla-Graph and WebQSP, leaving broader graph families and task types for future work.Source: Limitations · p. 10
• The backbone study covers only Llama and Qwen models up to 14B, leaving other model families uncharacterised.Source: Limitations · p. 10

A.1 Reasoning on Text-Attributed Graphs

• Graph-R1 and TRN-R1-Zero select neighbourhoods before reasoning, using summarisation or random sampling rather than learning neighbour acquisition as a decision process (Wu et al., 2025b; Liu et al., 2026).Source: §A.1 · p. 13

A.2 Agentic Search

• Agentic retrieval uses external semantic search over document corpora, but degree-preserving rewiring collapses CNY’s walk accuracy to the preview+direct baseline.The rewire preserves node text and degree while destroying topology, so flat retrieval over the same texts does not recover the gain. Related systems include Self-RAG (Asai et al., 2024), Search-o1 (Li et al., 2025), Search-r1 (Jin et al., 2025), R1-Searcher (Song et al., 2025) and ReSearch (Chen et al., 2025).Source: §A.2 · p. 13

A.3 Credit Assignment and On-Policy Self-Distillation

• CNY conditions its distillation teacher on the neighbour retrieved by the model’s own walk, avoiding the labelled intermediate trajectories unavailable for graph exploration.Unlike prior on-policy self-distillation that uses privileged answers, solutions or hints, the teacher evaluates the destination after the walk action reveals it.Source: §A.3 · p. 13

B OPSD Credit Derivation

• The recap is concatenated into the student’s autoregressive prefix immediately before the action span, defining the teacher’s destination-conditioned context.The teacher distribution is undefined for tokens with no associated walk action.Source: B OPSD Credit Derivation · pp. 13–14
• OPSD trains the student at each walk-action token to match its destination-conditioned teacher by minimizing per-token reverse KL.The teacher conditions on a recap associated with the walk action.Source: B OPSD Credit Derivation · pp. 13–14
• With the teacher detached, the reverse-KL gradient becomes REINFORCE-style, weighted per token by the teacher-to-student log-ratio (Shenfeld et al., 2026; Hübotter et al., 2026; Zhao et al., 2026).Source: B OPSD Credit Derivation · p. 14
• Evaluating that log-ratio at the realized token yields δ_t, making distillation toward the teacher equivalent to using δ_t as a per-token advantage.The derivation identifies this realized-token credit with the walk-action credit of Eq. (7).Source: B OPSD Credit Derivation · p. 14
• As a single realized-token term, δ_t is a biased estimator of the reverse-KL gradient, but is used directly as dense credit (Shenfeld et al., 2026).Source: B OPSD Credit Derivation · p. 14

C Algorithms

• Algorithm 1 specifies one CNY rollout, while Algorithm 2 specifies one training step that prices the GRPO advantage with OPSD credit from Eq. (8).Source: C Algorithms · p. 14

D Datasets and Prompt Templates

• Rollouts walk only to frontier nodes, reveal node information, update the frontier, and stop on an answer; training applies GRPO with recap-based adjustments to walk-action advantages.The training step samples rollouts in parallel and adds the recap-conditioned teacher signal to node-ID tokens, leaving other token advantages unchanged.Source: D Datasets and Prompt Templates · p. 14

D.1 Baselines and Evaluation Details

• The evaluation suite reuses Graph-R1’s datasets (Wu et al., 2025b) with molecular regression and link prediction omitted, and re-evaluates its checkpoint on raw node text rather than DeepSeek-v3 summaries.Expla-Graph is the sole graph-level evaluation; general-purpose and graph foundation model baselines are included, with family results taken from the Graph-R1 benchmark.Source: §D.1 · p. 14

D.2 Graph Statistics

• Training datasets occupy the top block of the statistics table, while evaluation datasets never enter training; Products lists 47 label names, but only 44 occur as ground-truth classes.For undirected citation and co-purchase graphs, stored edge counts count each undirected edge twice.Source: §D.2 · p. 15

D.3 Node-Classification Prompt

• Node-classification prompts use a multi-step template with two example turns and rely on the strict format reward to enforce well-formed spans.Placeholder fields are substituted per node instance.Source: §D.3 · p. 15

D.4 Edge-Classification Prompt

• Edge prompts anchor both head and tail, start from their combined 1-hop neighborhoods, shortlist K=10 relations (the gold relation plus nine distractors), and allow max_hops=5.Distractors are sampled deterministically from the FB15K237 relation vocabulary.Source: §D.4 · p. 15

D.5 Expla-Graph Stance-Walk Construction

• Expla-Graph maps the belief–argument pair and two stances onto the node-classification walk template, with each instance’s concept graph isolated in a disjoint global graph.The initial frontier is a connected seed and its one-hop concepts, shown as name-only previews; other concepts are revealed only when walked, through the existing information channel.Source: §D.5 · p. 15
• The stance instruction asks whether the argument agrees with the belief, preventing errors from judging the argument’s topic sentiment; the gold explanation string is withheld to avoid revealing the stance.Only the belief, argument, concept-name previews, and relations revealed during a walk are surfaced; the rule leaves plain stance labels and scoring unchanged.Source: §D.5 · pp. 15–16

D.6 Destination Recap Prompt

• OPSD re-scores each walk action using an LLM-generated recap of its destination, constrained to one topic-only sentence that forbids node IDs, navigation recommendations, and guesses at the target class.The recap supplies destination context without leaking a gold label or navigation hint.Source: §D.6 · p. 16

E Implementation

• Table 9 reports CNY-14B reference-run hyperparameters, and Table 10 reports compute allocation per backbone, using the released training configuration.Source: E Implementation · p. 16, Table 9 · p. 16
• With 4×H100 80GB and TP=4, the 14B run takes a median ∼300 s per step and ∼280 s on typical non-evaluation steps, halting after 1,000 steps.Evaluation runs every tenth step, and the schedule fits within each H100’s 80 GB under TP=4.Source: E Implementation · p. 16

F Additional Analyses

• Unless a training run is stated, the measurements use frozen CNY-14B.Source: F Additional Analyses · p. 16

F.1 Preview Construction

• Previews use the format [{id}]: {prefix} ..., with per-dataset lengths fixed in the released configuration.Source: §F.1 · p. 16
• Expla-Graph is the sole exception: its preview is the concept name.The passage points to App. D.5 for this exception.Source: §F.1 · p. 16
• WikiCS accuracy is 77.1 at 5 tokens and 77.9 at 10 tokens when the inference preview budget varies.At 5 tokens, previews are title-only because the page title opens each node’s text.Source: §F.1 · p. 16
• WikiCS accuracy is 76.8 at the published 30-token budget and 77.5 at 60 tokens.Source: §F.1 · p. 16

F.2 Matched Preview Exposure

• Matched previews modestly improve direct answering (Cora 65.0→66.3, WikiCS 71.0→73.4, Products 83.0→83.5), but walking further improves it (Cora 66.3→74.1, WikiCS 73.4→76.6, Products 83.5→87.6).The results place the gain in reading the selected neighbour, not preview exposure.Source: §F.2 · p. 17

F.3 Failure Modes of Walking

• Flips are pooled across three walk-evaluation seeds and manually assigned to three failure modes.A flip occurs when the target text alone is classified correctly but walking causes a misclassification.Source: §F.3 · p. 17
• The first mode concentrates on adjacent class pairs, most often Computer Architecture to Operating Systems.Source: §F.3 · p. 17
• The second mode covers multi-facet targets whose destination text foregrounds the wrong facet.Source: §F.3 · p. 17