Agentic Graph Token Reasoning

# Agentic Graph Token Reasoning
Source: [https://arxiv.org/html/2608.00542](https://arxiv.org/html/2608.00542)
andYi YangThe Hong Kong University of Science and Technology[imyiyang@ust\.hk](https://arxiv.org/html/2608.00542v1/mailto:[email protected])

###### Abstract\.

Graphs model relational data throughout science and industry, from citation networks and protein interactions to product co\-purchase graphs\. Because the nodes of many such graphs carry rich text, a growing line of work applies large language models \(LLMs\) to graph analysis\. The most graph\-native of these methods use*graph tokens*: a graph encoder compresses a graph view—a subgraph such as a node, itskk\-hop neighbourhood, or a cluster—into a short block of continuous tokens that jointly encodes node attributes and topology and is read directly by the model\. Existing methods, however, use graph tokens in a static single\-shot manner: they encode one predefined graph view before the model has even seen the target and never revise it, leaving the model’s step\-by\-step reasoning ability unused for a task\. We introduce*agentic graph token reasoning*, which recasts graph tokenization as part of the reasoning process itself\. At each step, the model chooses which graph view to encode and at what granularity; a graph encoder is invoked on demand to materialise the corresponding graph tokens; and the resulting block is spliced into the running context\. The model thus reasons step by step in the graph token space, and the tokens it reads are trajectory\-dependent\. We realise this with a three\-stage training pipeline: \(i\) self\-supervised tasks that teach the model to read heterogeneous graph tokens, \(ii\) a token\-robust trajectory stage with a graph\-token consistency regulariser, and \(iii\) preference optimisation that rewards trajectories in which the graph\-token evidence and the node\-text evidence agree, incentivising the model to ground its predictions in the consistency between the two\. Across extensive evaluations spanning seven graph domains, our models outperform a broad set of baselines by a large margin and transfer zero\-shot to unseen domains without any per\-target fine\-tuning\. Further analysis shows that our agentic approach substantially reduces errors on the most challenging samples\. More broadly, this work pushes LLM\-based graph analysis from static graph\-token encoders towards a graph\-native agent paradigm\.

graph neural networks, large language models, agentic reasoning, graph tokens

††copyright:none## 1\.Introduction

Graphs are a universal representation for relational data, and in many domains their nodes carry rich text, a paper and its abstract, a product and its description, a protein and its functional annotation\. A promising line of recent progress uses large language models to analyse such graphs: one asks a question about the graph \(what is this paper’s field? do these two proteins interact?\), and the model returns the answer\. The challenge is that a language model is trained purely on language: aligning graph data with its language space, so that the model can understand a graph at all, is difficult\. The technique that has emerged for this is the*graph token*\. Methods such as LLaGA\(Chen et al\.,[2024c](https://arxiv.org/html/2608.00542#bib.bib4)\), TEA\-GLM\(Wang et al\.,[2024](https://arxiv.org/html/2608.00542#bib.bib37)\), GraphGPT\(Tang et al\.,[2024](https://arxiv.org/html/2608.00542#bib.bib33)\), GraphTranslator\(Zhang et al\.,[2024](https://arxiv.org/html/2608.00542#bib.bib41)\), and GOFA\(Kong et al\.,[2025](https://arxiv.org/html/2608.00542#bib.bib21)\)run a graph encoder over a graph view111A*graph view*is a subgraph of the full graph, or the full graph itself, including but not limited to the target node, itskk\-hop neighbourhood, or a cluster, forming a graph region for the language model to process\.around the target and compress it into a short, fixed\-length block of continuous tokens that the model reads alongside the question\. Their success comes from exactly this compression: the graph is turned into tokens a language model can understand, and the block stays the same length however large the encoded graph view\.

These methods, however, read the graph using a predefined, static graph\-token pattern\. Given a target, the graph view to encode, typically the anchor’skk\-hop neighbourhood or a single global token, is chosen in advance, encoded before the model has even seen the question, and never revised; the model must then produce its answer in a single forward pass \(Figure[1](https://arxiv.org/html/2608.00542#S1.F1)a\)\. Everything therefore rests on the quality of that one chosen graph view: it must be neither too narrow to contain the evidence nor so wide that the signal is diluted, and it is committed before the question is known\. This raises a basic concern: how can one assume that a predefined, static graph token is sufficient for the language model to read and derive the final answer in one shot?

Meanwhile, language models have developed a capability that speaks directly to this problem:*agentic reasoning*\. Rather than answering from whatever happens to be in the prompt, a model can now decide what it still needs, act to obtain it, and repeat, a behaviour typically instilled through large\-scale reinforcement learning\(Shao et al\.,[2024](https://arxiv.org/html/2608.00542#bib.bib27); Jaech et al\.,[2024](https://arxiv.org/html/2608.00542#bib.bib17); Guo et al\.,[2025](https://arxiv.org/html/2608.00542#bib.bib10)\)\. The benefit of such iteration is that the context is enriched round by round, each step adding evidence chosen in light of what the previous steps revealed, until it is sufficient to derive the answer, so how much evidence is gathered adapts to how hard the instance is instead of being fixed beforehand\. Graph analysis is a natural fit for this, since the evidence a target needs \(its own attributes, its neighbours, the community around it, look\-alike nodes elsewhere\) is rarely apparent before one starts looking\. Yet current graph\-token methods lag far behind this paradigm: they commit to one graph view up front and answer in a single pass, so the model never gets to ask for the evidence it turns out to need\. As a result, the capability of language models for graph analysis is far from fully unleashed\. Closing this gap calls for a multi\-step formulation in which reasoning proceeds over several rounds, each represented by graph tokens, and leads to our research question:

*How can a language model perform step\-by\-step agentic reasoning via graph tokens?*

\(a\) Single\-shotgraph token\(prior work\)graph𝒢\\mathcal\{G\}questionQQpredefinedviewGVG^\{V\}𝐙\\mathbf\{Z\}answerAAfixedfGNNf^\{\\mathrm\{GNN\}\}fLLMf^\{\\mathrm\{LLM\}\}\(b\) Agentic graphtoken reasoning\(ours, AGT\)graph𝒢\\mathcal\{G\}questionQQfLLMf^\{\\mathrm\{LLM\}\}actionata\_\{t\}selects viewGVtG^\{V\_\{t\}\}𝐙tAGT\\mathbf\{Z\}^\{\\mathrm\{AGT\}\}\_\{t\}answerAAfGNNf^\{\\mathrm\{GNN\}\}nextstepifanswer

Figure 1\.Single\-shot vs\. AGT, from the same inputs: a graph𝒢\\mathcal\{G\}and a questionQQ\. \(a\) Prior graph\-token methods encode one predefined view into a graph token𝐙\\mathbf\{Z\}and answer in a single pass\. \(b\) Ours lets the model emit an action at each step that calls a graph view to encode; the encoder returns an agentic graph\-token block that is spliced back into the context, and the loop repeats until the terminatingansweraction\. A fraud check, for example, may read the account’s own text, then its transaction partners, the surrounding community, and look\-alike accounts before answering\.We address this question with*Agentic Graph Token*\(AGT\) reasoning \(Figure[1](https://arxiv.org/html/2608.00542#S1.F1)b\), which turns graph tokenization from a pre\-processing step into part of the reasoning process\. Given a graph and a task question, the model reasons one step at a time: it emits a discrete action that names a scope and a granularity, from the anchor node itself up to akk\-hop subgraph, a retrieved set of semantically similar nodes, or a whole cluster, and a graph encoder is invoked on demand to encode that graph view into a fixed\-length block of graph tokens, and the block is spliced into the running context before the next step\. The model thereby grows a reasoning trajectory222A*trajectory*is the sequence of interleaved reasoning steps and actions a model produces while solving a query, ending in its answer\.adaptively, each step chosen in light of the reasoning so far, and adaptively terminates to output the task answer\. Reasoning thus unfolds in the graph token space rather than in language, in the spirit of reasoning in a continuous latent space\(Hao et al\.,[2024](https://arxiv.org/html/2608.00542#bib.bib13)\)\.

Eliciting this behaviour is non\-trivial, chiefly because a model given both prompt text and graph tokens tends to lean on the text and ignore the tokens\. We therefore train the model in three stages, each contributing a component that, to our knowledge, is new to graph\-token learning: \(1\)*learning to read graph tokens*, self\-supervised pre\-training that aligns the encoder with the language model so it can read the varied token blocks that different actions produce; \(2\)*incentivising reasoning trajectories*, trajectory SFT with a graph\-token consistency term so the reasoning is driven by token content rather than brittle cues; and \(3\)*graph\-text consistency preference*, IPO that prefers rollouts which stay consistent with the graph over ones a corrupted anchor text throws off, pushing the policy to ground its answers in the graph\.

![Refer to caption](https://arxiv.org/html/2608.00542v1/framework.png)Figure 2\.Overview of Agentic Graph Token \(AGT\) reasoning\. Stage 1 grounds the block with two self\-supervised reading tasks; Stage 2 fits agentic trajectories with a consistency term over perturbed graph tokens; Stage 3 optimises preference pairs in which a text\-consistent rollout is correct and a text\-corrupted, graph\-inconsistent one is wrong, teaching model to prefer the reasoning path where graph token and node text agree\. LLM and GNN are jointly optimised in all stages\.#### Contributions

Our contributions are threefold\.

- •An agentic graph\-token reasoning framework\.We recast graph tokenization as part of reasoning: the model interleaves its reasoning with on\-demand graph\-token materialisations in a single sequence, moving graph learning from a static, single\-shot paradigm to an agentic one whose intermediate evidence is graph\-native rather than verbalised text\.
- •A three\-stage training recipe\.We contribute one targeted design per stage, teaching the model to read graph tokens, keeping its reading grounded in their content, and rewarding trajectories where the graph and text evidence agree\.
- •Strong empirical results\.Across seven graph domains our model outperforms comparably sized graph\-token and agentic baselines on node classification and link prediction, and transfers zero\-shot to targets the checkpoint was never trained on\.

This work pushes LLM\-based graph analysis from static graph\-token encoders towards a graph\-native agent paradigm\.

## 2\.Related Work

### 2\.1\.Graph learning with large language models

A large body of work adapts large language models to text\-attributed graphs, and the approaches differ mainly in how the graph is presented to the model\.*Verbalisation*methods render local structure as natural\-language text that the model reads in the prompt: they serialise a node’s neighbourhood into a description\(Ye et al\.,[2024](https://arxiv.org/html/2608.00542#bib.bib40); Zhao et al\.,[2023](https://arxiv.org/html/2608.00542#bib.bib43); Guo et al\.,[2023](https://arxiv.org/html/2608.00542#bib.bib11)\), use an LLM to generate explanations or augmented features for a downstream model\(He et al\.,[2023](https://arxiv.org/html/2608.00542#bib.bib14); Fang et al\.,[2024](https://arxiv.org/html/2608.00542#bib.bib8)\), or select the most informative neighbours to describe\(Li et al\.,[2024](https://arxiv.org/html/2608.00542#bib.bib22)\); broad empirical studies compare such text encodings\(Chen et al\.,[2024a](https://arxiv.org/html/2608.00542#bib.bib5)\)\. Such text encodes topology poorly and inflates the context\.*Graph\-token*methods instead learn a graph encoder that compresses a graph view into structure\-aware soft tokens injected into the prompt: LLaGA\(Chen et al\.,[2024c](https://arxiv.org/html/2608.00542#bib.bib4)\), GOFA\(Kong et al\.,[2025](https://arxiv.org/html/2608.00542#bib.bib21)\), TEA\-GLM\(Wang et al\.,[2024](https://arxiv.org/html/2608.00542#bib.bib37)\), GraphGPT\(Tang et al\.,[2024](https://arxiv.org/html/2608.00542#bib.bib33)\), GraphTranslator\(Zhang et al\.,[2024](https://arxiv.org/html/2608.00542#bib.bib41)\), and GraphPrompter\(Liu et al\.,[2024](https://arxiv.org/html/2608.00542#bib.bib24)\)follow this route, typically attaching a GNN encoder to an open LLM backbone such as LLaMA or Mistral\(Touvron et al\.,[2023](https://arxiv.org/html/2608.00542#bib.bib35); Jiang et al\.,[2023](https://arxiv.org/html/2608.00542#bib.bib18)\)\. A training\-free variant instead performs graph in\-context learning without any tuning\(Sun et al\.,[2025](https://arxiv.org/html/2608.00542#bib.bib31)\), and complementary analyses ask when and why structural prompts help at all\(Huang et al\.,[2023](https://arxiv.org/html/2608.00542#bib.bib16)\)\. These representations are graph\-native, but the encoded graph view is a fixed template chosen at architecture time, encoded once before the model reads the target, and never revised, so the model cannot request a different graph view as it reasons\. A third, recent*agentic*line lets the model gather evidence over several steps: AgentGL\(Sun et al\.,[2026](https://arxiv.org/html/2608.00542#bib.bib30)\)trains an RL policy that issues text queries and reads back text snippets, and GraphCoT\(Jin et al\.,[2024](https://arxiv.org/html/2608.00542#bib.bib19)\)and GraphSearch\(Liu et al\.,[2026](https://arxiv.org/html/2608.00542#bib.bib23)\)likewise operate over text renderings of the graph; relatedly, Graph\-of\-Thoughts\(Besta et al\.,[2024](https://arxiv.org/html/2608.00542#bib.bib3)\)organises the model’s own textual thoughts as a graph rather than analysing input graph data\. None of these methods ever re\-encodes graph tokens\. In short, existing work is either agentic but text\-based, or graph\-token\-based but static\. To our knowledge, ours is the first agentic graph\-token reasoning framework, in which each reasoning step is itself an on\-demand graph\-token materialisation, uniting the graph\-native representation of graph\-token methods with the adaptivity of agentic ones\. This also makes it differ fundamentally from any text\-based reasoning method, such as chain\-of\-thought prompting\(Wei et al\.,[2022](https://arxiv.org/html/2608.00542#bib.bib38)\)or AgentGL\(Sun et al\.,[2026](https://arxiv.org/html/2608.00542#bib.bib30)\): each reasoning step carries graph\-topology and node\-attribute information in the token block itself, which a purely textual step can convey only clumsily, if at all\.

### 2\.2\.Reasoning in large language models

A parallel line of work improves how language models reason\. Chain\-of\-thought prompting\(Wei et al\.,[2022](https://arxiv.org/html/2608.00542#bib.bib38)\)shows that generating intermediate steps in language before the final answer substantially improves multi\-step problem solving, and a large family of methods builds on this idea of explicit step\-by\-step reasoning\. Such reasoning, however, is carried out entirely in language\. A growing line argues that language is not always the best medium and moves computation off the token stream: pause tokens add latent compute before the model answers\(Goyal et al\.,[\[n\. d\.\]](https://arxiv.org/html/2608.00542#bib.bib9)\), implicit chain\-of\-thought internalises the reasoning into hidden states\(Deng et al\.,[2024](https://arxiv.org/html/2608.00542#bib.bib7)\), and Coconut\(Hao et al\.,[2024](https://arxiv.org/html/2608.00542#bib.bib13)\)lets a model reason in a continuous latent space, showing that a latent state can carry information that a verbalised step cannot\. Our setting inherits exactly this tension, but in a graph context, where each reasoning step should convey structural evidence about the graph\. Graph tokens are a natural latent medium for such steps, yethow to represent a graph reasoning step efficiently and effectivelyremains an open question, which this work sets out to address\.

## 3\.Preliminaries

We study learning on a*text\-attributed graph*\(TAG\)𝒢=\(𝒱,ℰ,𝒯\)\\mathcal\{G\}=\(\\mathcal\{V\},\\mathcal\{E\},\\mathcal\{T\}\)with node set𝒱\\mathcal\{V\}, edge setℰ\\mathcal\{E\}, and node texts𝒯=\{tv∣v∈𝒱\}\\mathcal\{T\}=\\\{t\_\{v\}\\mid v\\in\\mathcal\{V\}\\\}\. A task instance is a questionQQabout the graph, with a ground\-truth labely∈𝒴y\\in\\mathcal\{Y\}, and the model returns an answerA∈𝒴A\\in\\mathcal\{Y\}\. The question may concern a node, a node pair, or more generally any graph\-defined object whose label depends on the surrounding structure\. Unlike a classifier that maps a fixed precomputed feature to its prediction, our model formsAAfrom evidence drawn from𝒢\\mathcal\{G\}at inference time: the target’s own text, its neighbours’ texts, and the surrounding structure\.

#### Graph tokens via a GNN

The interface to the graph is a graph neural networkfGNNf^\{\\mathrm\{GNN\}\}that maps a graph viewGVG^\{V\}, a subgraph of𝒢\\mathcal\{G\}\(or𝒢\\mathcal\{G\}itself\) such as a node, akk\-hop neighbourhood, or a cluster, to a fixed\-size block of soft tokens

\(1\)𝐙=fGNN​\(GV\)\.\\mathbf\{Z\}=f^\{\\mathrm\{GNN\}\}\(G^\{V\}\)\.The block has the same length for every graph view and lies directly in the LLM’s embedding space, so any graph view, from a single node to a large neighbourhood, is summarised by a constant\-length set of tokens the language model can read\.

#### Reading graph tokens with an LLM

A pretrained large language modelfLLMf^\{\\mathrm\{LLM\}\}is the backbone: it consumes accompanying text together with one or more graph\-token blocks𝐙=fGNN​\(GV\)\\mathbf\{Z\}=f^\{\\mathrm\{GNN\}\}\(G^\{V\}\)and produces the answer\. In the simplest, single\-shot form used by prior graph\-LLMs, a fixed graph viewGVG^\{V\}is encoded once and read alongside the questionQQ,

\(2\)A=fLLM​\(Q,𝐙\),𝐙=fGNN​\(GV\),A\\;=\\;f^\{\\mathrm\{LLM\}\}\\\!\\left\(Q,\\ \\mathbf\{Z\}\\right\),\\qquad\\mathbf\{Z\}=f^\{\\mathrm\{GNN\}\}\(G^\{V\}\),in one forward pass\. Here the graph view is chosen at architecture time, before the model has seenQQ, and never revised\. Our departure is exactly in*when*and*which*blocks are read: rather than a single prepended block, the model requests blocks step by step during generation, so the graph tokens it reads become trajectory\-dependent\. Section[4](https://arxiv.org/html/2608.00542#S4)develops this and contrasts it directly with Eq\. equation[2](https://arxiv.org/html/2608.00542#S3.E2)\.

## 4\.Methodology

Graph analysis needs step\-by\-step reasoning, and each step should be a graph token\.Consider predicting a protein’s function\. For a well\-characterised protein its own annotation settles it; for a less studied one the function emerges only from its direct interaction partners; and for a poorly annotated protein the answer appears only once the larger pathway or complex it belongs to comes into view\. The informative graph view is thus instance\-dependent and is not known in advance, so the model has to gather evidence over several steps rather than from one fixed view\. A single graph\-token block, fixed before the model has seen the target, cannot match this: it over\-encodes easy targets, starves hard ones, and cannot be revised once decoding has begun\. Once reasoning is step by step, the evidence each step needs is inherently*structural*: a neighbourhood, a pathway, a cluster\. A graph token encodes such structure natively and compactly, packing node attributes and topology into a fixed\-size block, whereas verbalising the same graph view would inflate the context and bury the topology in text\. This makes the graph token the right medium for a reasoning step on a graph\. We therefore let the model choose the graph view*as it reasons*, using the interface of Section[3](https://arxiv.org/html/2608.00542#S3), where a graph viewGVG^\{V\}encodes to a fixed\-size block𝐙=fGNN​\(GV\)\\mathbf\{Z\}=f^\{\\mathrm\{GNN\}\}\(G^\{V\}\)infLLMf^\{\\mathrm\{LLM\}\}’s embedding space\.

From single\-shot to step\-by\-step graph token reasoning\.Prior graph\-LLMs use the interface of Eq\. equation[2](https://arxiv.org/html/2608.00542#S3.E2)once: a single graph view is fixed, encoded, and read in one forward pass to produce the answer\. We instead unroll the computation overTTsteps and produce the answer only at the end\. To begin with, the model is given the graph𝒢\\mathcal\{G\}and the questionQQ, and the context holds the question alone, with no graph tokens yet:

At each stept=1,…,Tt=1,\\dots,T, the model reads the context so far and emits a single*action*ata\_\{t\}from the action space𝒜\\mathcal\{A\}\(Table[1](https://arxiv.org/html/2608.00542#S4.T1)\), no natural language, only the action itself, which names a graph viewGVtG^\{V\_\{t\}\}, whereVt=V​\(at\)V\_\{t\}=V\(a\_\{t\}\)is determined by the action; a GNN encoderfGNNf^\{\\mathrm\{GNN\}\}turns that graph view into the step’s*agentic graph\-token*\(AGT\) block, and the block is appended to the context:

\(4\)at\\displaystyle a\_\{t\}∼fLLM\(⋅∣τt−1\),\\displaystyle\\sim f^\{\\mathrm\{LLM\}\}\(\\,\\cdot\\mid\\tau\_\{t\-1\}\),\(5\)𝐙tAGT\\displaystyle\\mathbf\{Z\}^\{\\mathrm\{AGT\}\}\_\{t\}=fGNN​\(GVt\),Vt=V​\(at\),\\displaystyle=f^\{\\mathrm\{GNN\}\}\\\!\\big\(G^\{V\_\{t\}\}\\big\),\\qquad V\_\{t\}=V\(a\_\{t\}\),\(6\)τt\\displaystyle\\tau\_\{t\}=\(τt−1,at,𝐙tAGT\)\.\\displaystyle=\\big\(\\tau\_\{t\-1\},\\,a\_\{t\},\\,\\mathbf\{Z\}^\{\\mathrm\{AGT\}\}\_\{t\}\\big\)\.The block𝐙tAGT\\mathbf\{Z\}^\{\\mathrm\{AGT\}\}\_\{t\}thus depends on the actionata\_\{t\}through the graph viewGVtG^\{V\_\{t\}\}it names\. What stept\+1t\{\+\}1conditions on is therefore the token block𝐙tAGT\\mathbf\{Z\}^\{\\mathrm\{AGT\}\}\_\{t\}itself, not a verbalisation ofGVtG^\{V\_\{t\}\}\. Crucially,𝐙tAGT\\mathbf\{Z\}^\{\\mathrm\{AGT\}\}\_\{t\}is then read at the next step, it is part of the contextτt\\tau\_\{t\}that stept\+1t\{\+\}1conditions on, so the graph tokens gathered so far steer which graph view is requested next\. And because the graph view is chosen anew every step,𝐙tAGT\\mathbf\{Z\}^\{\\mathrm\{AGT\}\}\_\{t\}can differ from round to round: the model may zoom in, widen, or jump to a different part of the graph rather than reusing one fixed block\.

Specifically, ifata\_\{t\}is the terminating action, the model outputs the final answerAAand the loop ends\. The number of stepsTTand the graph views visited are chosen by the model, so they vary withQQ\. The action set in Table[1](https://arxiv.org/html/2608.00542#S4.T1)is by no means a complete action space; we choose these actions for their generality across graphs and tasks, and the interface is open, so follow\-up work can add its own actions without changing the rest of the method\.

We give the model this behaviour with three training stages, each initialised from the previous one: Stage 1 aligns the encoder’s tokens with the language model’s embedding space so a block can be read at all; Stage 2 teaches the model to emit graph\-token actions and answer from what they return; and Stage 3 sharpens the resulting policy through preference optimisation on its own rollouts\. The three training corpora are constructed as detailed inAppendix[D](https://arxiv.org/html/2608.00542#A4)\. We first fix the token interface and encoder, then develop each stage\. Figure[2](https://arxiv.org/html/2608.00542#S1.F2)summarises both the inference\-time rollout and the three training stages\.

Table 1\.The action space𝒜\\mathcal\{A\}used in this work\. This is by no means an exhaustive set, but a representative one: we choose these actions for their generality across graphs and tasks\.### 4\.1\.Stage 1: Learning to read graph tokens

A graph\-token block is a set of continuous vectors that match no word in the language model’s vocabulary, so out of the box the model has no idea what they mean\. Stage 1 grounds them: it teaches the model that a block𝐙AGT\\mathbf\{Z\}^\{\\mathrm\{AGT\}\}carries graph\-derived evidence, node content and local structure, rather than text\. For each training anchorvvwe build two self\-supervised tasks\.*Text reconstruction*feedsvv’s`node\_token`block and asks the model to reproducevv’s title and abstract, forcing the block to encode content;*masked link prediction*feedsvv’s block together with a candidatewwand asks`yes`/`no`whether\(v,w\)\(v,w\)is an edge \(every edge touching a validation or test node removed\), forcing it to encode local structure\. The objective is a cross\-entropy over the model’s response tokens, with the graph\-token positions masked out,

\(7\)ℒ1=−∑t∈𝒮log⁡fLLM​\(yt∣y<t,𝐙AGT\),\\mathcal\{L\}\_\{1\}\\;=\\;\-\\\!\\sum\_\{t\\in\\mathcal\{S\}\}\\log f^\{\\mathrm\{LLM\}\}\\\!\\left\(y\_\{t\}\\mid y\_\{<t\},\\mathbf\{Z\}^\{\\mathrm\{AGT\}\}\\right\),where𝒮\\mathcal\{S\}indexes the response tokens and𝐙AGT\\mathbf\{Z\}^\{\\mathrm\{AGT\}\}is an input rather than a target\. This objective updates the graph encoderfGNNf^\{\\mathrm\{GNN\}\}and the language modelfLLMf^\{\\mathrm\{LLM\}\}jointly, with the mpnet text features and the graph topology held frozen\. Unlike prior graph\-token methods, which tie the encoder to a single task\-specific instruction\-tuning objective, these two task\-agnostic objectives ground the block on its own content and structure, so one reader transfers across the heterogeneous blocks that different actions later produce\.

### 4\.2\.Stage 2: Token\-robust trajectory SFT

Reading a single block, as in Stage 1, is not the same as reasoning over a whole sequence of them: acting requires the model to decide which graph view to request next and to combine the blocks it gets back\. Moreover, if we simply imitate trajectories on clean encodings, the model tends to latch onto easy surface cues in a block and its reading collapses the moment the block changes\. Stage 2 therefore teaches the model to*act*, to emit graph\-token actions and derive the answer from what they return, while keeping that reading robust, over a corpus of synthesized trajectories, each pairing a training anchor with a variable\-length sequence of actions from𝒜\\mathcal\{A\}\(Table[1](https://arxiv.org/html/2608.00542#S4.T1)\) and the correct final answer\. Training has two phases\. A warm\-up is ordinary supervised fine\-tuning that reproduces each trajectory’s action calls and answer under a token\-weighted cross\-entropy over the model’s own positions𝒮\\mathcal\{S\}\(the injected blocks are inputs and are excluded\),

\(8\)ℒCE=1\|𝒮\|​∑t∈𝒮wt​CE​\(ℓt,yt\),\\mathcal\{L\}\_\{\\text\{CE\}\}\\;=\\;\\frac\{1\}\{\|\\mathcal\{S\}\|\}\\sum\_\{t\\in\\mathcal\{S\}\}w\_\{t\}\\,\\mathrm\{CE\}\\\!\\bigl\(\\ell\_\{t\},y\_\{t\}\\bigr\),wherewt=ωw\_\{t\}=\\omegaon answer tokens and11otherwise \(ω=20\\omega\{=\}20\): upweighting the answer tokens keeps the surface format from crowding out the decision\. Because warm\-up sees only clean encodings, the reading it learns is brittle; a consistency phase repairs this\. We form two encodings of each sampled graph view, a clean one and an augmented one that drops its edges with probabilityped=0\.1p\_\{\\text\{ed\}\}\{=\}0\.1and masks graph tokens with probabilityptm=0\.2p\_\{\\text\{tm\}\}\{=\}0\.2, and add a term that aligns their response distributions:

\(9\)ℒ2=ℒCEclean\+λKL​KL​\(sg​\[pclean\]∥paug\),\\mathcal\{L\}\_\{2\}\\;=\\;\\mathcal\{L\}\_\{\\text\{CE\}\}^\{\\text\{clean\}\}\\;\+\\;\\lambda\_\{\\text\{KL\}\}\\,\\mathrm\{KL\}\\\!\\Bigl\(\\mathrm\{sg\}\\bigl\[p^\{\\text\{clean\}\}\\bigr\]\\,\\big\\\|\\,p^\{\\text\{aug\}\}\\Bigr\),wherepcleanp^\{\\text\{clean\}\}andpaugp^\{\\text\{aug\}\}are the softmaxed response distributions of the two encodings,sg​\[⋅\]\\mathrm\{sg\}\[\\cdot\]is the stop\-gradient that makes the clean encoding a fixed teacher, the KL runs over𝒮\\mathcal\{S\}, andλKL=0\.5\\lambda\_\{\\text\{KL\}\}\{=\}0\.5\. Because the augmentations perturb exactly the graph signal, matching the two distributions forces the model to rely on token content that survives perturbation\. Both phases updatefGNNf^\{\\mathrm\{GNN\}\}andfLLMf^\{\\mathrm\{LLM\}\}jointly\.

### 4\.3\.Stage 3: Graph\-text\-consistent IPO

Stages 1 and 2 make the graph tokens readable and robust, but they do not compel the model to*use*them\. The anchor’s own text sits in the prompt and is often enough to guess the label by itself, so the policy can score well while treating the graph tokens as optional, the very shortcut we set out to avoid\. Indeed, GraphLLMs are known to lean heavily on node text, to the point that perturbing a few words of it can flip their predictions\(Zhang et al\.,[2025](https://arxiv.org/html/2608.00542#bib.bib42)\)\. Supervised fine\-tuning cannot remove this shortcut: it only imitates correct trajectories and never shows the model a case where the text and the graph point different ways, so it gives no signal about which to trust\. Stage 3 supplies that signal by learning from the policy’s own behaviour\. Working from the Stage 2 policy’s rollouts, it rewards trajectories in which the graph\-token evidence and the node\-text evidence agree over ones where they disagree, incentivising the policy to ground its decision in graph\-text consistency\. We build preference pairs around the*consistency between a node’s input text and its graph tokens*: the preferred trajectory is one where the two agree, and the dispreferred one is obtained by corrupting the input text so that it disagrees with the graph\. For each training anchorvvwe run two greedy rollouts of the current policy:

- •a*consistent*rolloutτc\\tau^\{\\mathrm\{c\}\}onvv’s real node text and real graph, where the input text attribute and the graph tokens describe the same node and therefore agree, giving answerAcA^\{\\mathrm\{c\}\};
- •an*inconsistent*rolloutτi\\tau^\{\\mathrm\{i\}\}that corrupts only the input text attribute, replacingvv’s node text with that of a randomly chosen other nodev′v^\{\\prime\}while leavingvv’s graph \(its neighbours and their texts\) unchanged, so the text now disagrees with the graph tokens, giving answerAiA^\{\\mathrm\{i\}\}\.

We keep the pair only when all three conditions hold: the consistent answer is correct \(Ac=yA^\{\\mathrm\{c\}\}\{=\}y\), the inconsistent answer is wrong \(Ai≠yA^\{\\mathrm\{i\}\}\{\\neq\}y\), and the two answers differ \(Ac≠AiA^\{\\mathrm\{c\}\}\{\\neq\}A^\{\\mathrm\{i\}\}\)\. Such a case is exactly one where making the input text disagree with the graph flips a correct decision, so the answer had to rest on the graph: the consistent rollout shows the graph\-grounded behaviour we want and the inconsistent one the text\-reliant failure we do not\. We therefore set the preferenceτ\+=τc≻τ−=τi\\tau^\{\+\}\{=\}\\tau^\{\\mathrm\{c\}\}\\succ\\tau^\{\-\}\{=\}\\tau^\{\\mathrm\{i\}\}, which yields on the order of300300pairs per run, and preferringτ\+\\tau^\{\+\}trains the policy to trust the graph over a misleading anchor text\. We optimise the pairs with Identity Preference Optimisation\(Azar et al\.,[2024](https://arxiv.org/html/2608.00542#bib.bib2)\),

\(10\)ℒ3=𝔼\(τ\+,τ−\)​\[\(h​\(τ\+\)−h​\(τ−\)−12​β\)2\],h​\(τ\)=log⁡fLLM​\(τ∣Q\)frefLLM​\(τ∣Q\),\\begin\{gathered\}\\mathcal\{L\}\_\{3\}\\;=\\;\\mathbb\{E\}\_\{\(\\tau^\{\+\},\\tau^\{\-\}\)\}\\\!\\left\[\\Bigl\(h\(\\tau^\{\+\}\)\-h\(\\tau^\{\-\}\)\-\\tfrac\{1\}\{2\\beta\}\\Bigr\)^\{2\}\\right\],\\\\\[2\.0pt\] h\(\\tau\)=\\log\\frac\{f^\{\\mathrm\{LLM\}\}\(\\tau\\mid Q\)\}\{f^\{\\mathrm\{LLM\}\}\_\{\\text\{ref\}\}\(\\tau\\mid Q\)\},\\end\{gathered\}taking the Stage 2 model asfrefLLMf^\{\\mathrm\{LLM\}\}\_\{\\text\{ref\}\}withβ=0\.3\\beta\{=\}0\.3\. As in the earlier stages, this objective updates the graph encoderfGNNf^\{\\mathrm\{GNN\}\}and the language modelfLLMf^\{\\mathrm\{LLM\}\}jointly \(mpnet features and topology frozen\)\. Unlike preference optimisation that ranks by human or quality judgements, our pairs are constructed to isolate graph\-dependence, so the preference directly trains graph\-grounding; we use IPO over DPO\(Rafailov et al\.,[2023](https://arxiv.org/html/2608.00542#bib.bib25)\)because the small pair set is brittle to DPO’s unbounded log\-ratio, whereas IPO’s squared objective stays bounded\.

## 5\.Experiments

### 5\.1\.Setup

#### Datasets

We use ten text\-attributed graphs across four families: citation networks \(ogbn\-arxiv\(Hu et al\.,[2020](https://arxiv.org/html/2608.00542#bib.bib15)\), arXiv\-2023\(He et al\.,[2023](https://arxiv.org/html/2608.00542#bib.bib14)\), and PubMed, Cora, CiteSeer\(Yang et al\.,[2016](https://arxiv.org/html/2608.00542#bib.bib39)\)\), Amazon co\-purchase and co\-review graphs \(ogbn\-products\(Hu et al\.,[2020](https://arxiv.org/html/2608.00542#bib.bib15)\), Amazon\-Computers, Amazon\-Photo\(Shchur et al\.,[2018](https://arxiv.org/html/2608.00542#bib.bib28)\)\), a social graph \(Reddit\(Hamilton et al\.,[2017](https://arxiv.org/html/2608.00542#bib.bib12)\)\), and a protein\-interaction graph \(STRING\-db\(Szklarczyk et al\.,[2019](https://arxiv.org/html/2608.00542#bib.bib32)\)\)\. Seven are used for in\-domain training and evaluation \(ogbn\-arxiv, ogbn\-products, PubMed, Reddit, arXiv\-2023, CiteSeer, STRING\-db\), and a zero\-shot study transfers the ogbn\-arxiv\-trained policy, without any further training, to seven targets it has never seen \(Table[3](https://arxiv.org/html/2608.00542#S5.T3)\)\. Per\-dataset node text, label spaces, sizes, and sources are given inAppendix[B](https://arxiv.org/html/2608.00542#A2)\.

#### Policy and encoder

Qwen2\.5\-3B\-Instruct\(Team,[2024](https://arxiv.org/html/2608.00542#bib.bib34)\), hidden=2,048=2\{,\}048\. Encoder: mpnet sentence embeddings\(Song et al\.,[2020](https://arxiv.org/html/2608.00542#bib.bib29); Reimers and Gurevych,[2019](https://arxiv.org/html/2608.00542#bib.bib26)\)\(768\-d\) \+ 2\-layer GraphSAGE\(Hamilton et al\.,[2017](https://arxiv.org/html/2608.00542#bib.bib12)\)\(hidden512512, output768768\) with a cross\-attention pool that emits a128128\-token block per action, linearly projected to the backbone’s embedding width \(our default\)\. The 3B models train with DDP across4×4\\timesRTX 5880 Ada \(48 GB\); the 7B models train on H800 GPUs\. Stage 3 is single\-GPU with gradient accumulation\. Per\-stage training corpora \(construction, format, and sizes\) are detailed inAppendix[D](https://arxiv.org/html/2608.00542#A4)\.

#### Baselines

We compare against a series of baselines: AgentGL\-3B and AgentGL\-7B\(Sun et al\.,[2026](https://arxiv.org/html/2608.00542#bib.bib30)\)\(the RL\-trained agentic retrieval baseline\), the LLaGA\(Chen et al\.,[2024c](https://arxiv.org/html/2608.00542#bib.bib4)\)static\-graph\-token baseline, the GOFA\(Kong et al\.,[2025](https://arxiv.org/html/2608.00542#bib.bib21)\)graph foundation model, and GNN references \(GraphSAGE\(Hamilton et al\.,[2017](https://arxiv.org/html/2608.00542#bib.bib12)\), GCN\(Kipf and Welling,[2016](https://arxiv.org/html/2608.00542#bib.bib20)\), and GAT\(Veličković et al\.,[2018](https://arxiv.org/html/2608.00542#bib.bib36)\)\)\. All of these are run on the same1,0001\{,\}000\-node test samples and the same splits as our method, so every number in Table[2](https://arxiv.org/html/2608.00542#S5.T2)is measured under one protocol\. AgentGL\-7B is the strongest reported agent\. We additionally re\-implement seven same\-backbone baselines on our exact splits \(both Qwen2\.5\-3B and 7B\): Qwen zero\-shot, Qwen chain\-of\-thought\(Wei et al\.,[2022](https://arxiv.org/html/2608.00542#bib.bib38)\), a graph\-to\-text SFT model, LLM\-GNN\(Chen et al\.,[2024b](https://arxiv.org/html/2608.00542#bib.bib6)\), and the graph\-token methods TEA\-GLM\(Wang et al\.,[2024](https://arxiv.org/html/2608.00542#bib.bib37)\), GraphGPT\(Tang et al\.,[2024](https://arxiv.org/html/2608.00542#bib.bib33)\), and GraphTranslator\(Zhang et al\.,[2024](https://arxiv.org/html/2608.00542#bib.bib41)\); full details for these are inAppendix[C](https://arxiv.org/html/2608.00542#A3)\.

### 5\.2\.Main results

Table 2\.Main results: in\-domainnode classification\(% accuracy\) and maskedlink prediction\(AUC×100\\times 100\)\.Boldindicates the best result under the same backbone\. 3\-run average is reported\.Our 3B model sets a new state of the art among comparably sized graph LLMs \(Table[2](https://arxiv.org/html/2608.00542#S5.T2)\)\. On node classification it leads on six of the seven domains, reaching73\.0%73\.0\\%on ogbn\-arxiv and beating the comparably sized AgentGL\-3B baseline \(63\.9%63\.9\\%\) by9\.19\.1points; we show later \(Figure[3](https://arxiv.org/html/2608.00542#S5.F3)\) that this gain concentrates on the challenging nodes, where the anchor text alone is ambiguous, rather than on the easy ones\. On masked link prediction it wins six of the seven domains, trailing only LLaGA on arXiv\-2023\. In fact LLaGA and GraphTranslator are the only trained graph\-LLM baselines that beat ours on any domain \(LLaGA on arXiv\-2023 LP and CiteSeer NC, GraphTranslator on CiteSeer NC\), while the retrieval\-based AgentGL and frozen\-feature GOFA sit well below\. A plain GNN stays ahead of ours only on the two most structure\-dominated cases, the homophilous CiteSeer \(NC\) and the STRING\-db \(LP\) graphs\.

The advantage is consistent at larger scale\. With a Qwen2\.5\-7B backbone our model tops every node\-classification domain \(e\.g\.75\.6%75\.6\\%on ogbn\-arxiv and80\.1%80\.1\\%on ogbn\-products\) and every link\-prediction domain among the same\-backbone baselines, so it consistently outperforms every same\-backbone baseline across both tasks and the approach scales with backbone size\.

### 5\.3\.Zero\-shot transfer

Table 3\.Zero\-shot accuracy: every method trained only on ogbn\-arxiv and evaluated on target with no fine\-tuning\.We use the arxiv checkpoint without any further training to validate zero\-shot performance\. Transfer quality \(Table[3](https://arxiv.org/html/2608.00542#S5.T3)\) tracks the results: PubMed’s three broad medical categories admit reliable text classification \(82\.0%82\.0\\%\), while the 21\-class STRING\-db is hardest \(37\.4%37\.4\\%\)\. Ours leads on six of the seven transfer targets, trailing only Amazon\-Photo \(won by GraphTranslator,48\.448\.4vs43\.743\.7\), and by large margins over LLaGA, AgentGL, and GOFA\.

### 5\.4\.Ablations

Table 4\.Component ablation \(Qwen2\.5\-3B\)\. N/A marks an action outside a task’s action space\.#### Stage components

Table[4](https://arxiv.org/html/2608.00542#S5.T4)isolates the Stage 2 consistency term \(CRJT\) from full model; averaged over domains, it is the largest of the training components \(1\.91\.9points on node classification and5\.15\.1on link prediction\)\. CRJT pushes the LM to be invariant to two augmentations \(edge\-drop and token\-mask\) that the encoder cannot itself control, forcing the projection head and the LM’s attention into the graph\-token block to extract scope\-invariant signal\. Without it the LM treats graph tokens as a weak prior; with it the model calls`cluster\_token`and`three\_hop\_token`far more often at greedy decoding, which translates directly into accuracy\. Every domain improves with CRJT, with the largest gains on link prediction \(Table[4](https://arxiv.org/html/2608.00542#S5.T4)\)\.

#### Action contributions

The lower block of Table[4](https://arxiv.org/html/2608.00542#S5.T4)removes one action at a time\. For node classification the neighbour tokens \(1/2/3\-hop\) matter most: dropping them causes the largest accuracy fall, confirming that the topological signal, not the anchor alone, drives the label\. The single\-node, retrieval, and cluster tokens each contribute smaller amounts; on the1,0001\{,\}000\-node samples several of these node\-classification differences are within measurement noise, and we treat them as indicative rather than individually significant\. For link prediction the picture shifts, as a link decision rests on comparing the two endpoints: the cosine\-similarity action becomes decisive and the single\-node token is next most important, both collapsing AUC sharply when ablated \(the cosine action costs32\.632\.6AUC on ogbn\-products, the node token13\.413\.4on PubMed\)\. Every action contributes on at least one task, which supports keeping the full action space rather than a fixed subset\.

### 5\.5\.Is graph token better for reasoning?

Our central claim is that the*medium*, encoding each reasoning step as a graph token rather than as text, is what drives the gains, not the agentic loop alone\. To test this directly, we build a text\-medium ablation that shares our exact agentic framework: the same action space \(Table[1](https://arxiv.org/html/2608.00542#S4.T1)\), the same step\-by\-step rollout, and the same Stage 2–3 training recipe, changing only what each action returns\. Stage 1 is skipped for the text medium, since there is no graph\-token block to ground\. The verbaliser renders the same graph view the encoder would have pooled and is subject to the same20482048\-token context limit used throughout; the serialised views fit within that budget, so the text medium is not penalised by truncation\. Instead of an AGT block𝐙tAGT\\mathbf\{Z\}^\{\\mathrm\{AGT\}\}\_\{t\}, the encoder is replaced by a verbaliser that serialises the named graph viewGVtG^\{V\_\{t\}\}into natural\-language text spliced into the context\. Any gap between the two rows in Table[5](https://arxiv.org/html/2608.00542#S5.T5)is attributable to the medium alone\. In domain the two media stay close \(81\.0 versus 77\.8 on average, a 3\.2\-point gap\), where the anchor text alone often settles the label, but they diverge sharply under transfer\. The graph\-token medium retains57\.4%57\.4\\%zero\-shot accuracy against28\.1%28\.1\\%for the verbalised\-text medium, a 29\-point gap on the same targets\. The verbaliser preserves the same neighbourhood the encoder sees, so the difference is not about which graph view is read but about how it is represented: serialising to text discards the compact structural signal the encoder carries across datasets, which is precisely where out\-of\-domain accuracy depends on it\. Because the text medium keeps our trajectory SFT and rollout unchanged and only forgoes the pooler it has no use for, this gap is an estimate of what the medium contributes\.

Table 5\.Isolating the graph\-token medium\. Our agentic framework is run with each action returning either verbalised*text*\(Ours\-Text\) or a*graph token*\(Ours\-Token\), with identical actions;Δ\\Deltais the graph\-token gain over text\.AgentGLOurs\-TextOurs\-TokenΔ\\Delta*In\-domain*arxiv63\.971\.973\.0\+1\.1\+1\.1products64\.471\.376\.8\+5\.5\+5\.5pubmed89\.190\.193\.3\+3\.2\+3\.2average72\.577\.881\.0\+3\.2\+3\.2*Zero\-shot transfer*pubmed39\.832\.682\.0\+49\.4\+49\.4products36\.643\.755\.8\+12\.1\+12\.1citeseer40\.431\.854\.4\+22\.6\+22\.6STRING\-db21\.04\.337\.4\+33\.1\+33\.1average34\.528\.157\.4\+29\.3\+29\.3#### Where the errors reduce\.

The medium’s advantage is spread across nodes, not confined to a few\. Figure[3](https://arxiv.org/html/2608.00542#S5.F3)plots the density of misclassified nodes over node degree forOurs\-Tokenagainst the AgentGL text agent onPubMedandogbn\-products, each curve scaled to its total error mass\. Our error mass on PubMed is about three\-fifths of the text agent’s and on ogbn\-products about two\-thirds, removing roughly38%38\\%and35%35\\%of its errors\. Both methods err most on low\-degree nodes, where the neighbourhood carries the least signal, yet our curve stays below the text agent across the entire degree range, not only on well\-connected hubs\. The graph\-token medium thus lowers error mass broadly, which is consistent with the transfer gap in Table[5](https://arxiv.org/html/2608.00542#S5.T5)\.Appendix[E](https://arxiv.org/html/2608.00542#A5)extends this analysis \(Figure[5](https://arxiv.org/html/2608.00542#A5.F5)\)\.

![Refer to caption](https://arxiv.org/html/2608.00542v1/figures/error_density_pp.png)Figure 3\.Error\-fraction density over node degree:Ours\-Token\(orange\) versus the AgentGL text agent \(blue\)\. A lower curve means fewer and better\-placed errors\. The full analysis is in Figure[5](https://arxiv.org/html/2608.00542#A5.F5)\.

### 5\.6\.Pareto frontier

Figure[4](https://arxiv.org/html/2608.00542#S5.F4)places the methods on the accuracy versus token consumption forogbn\-products, with a dashed line tracing the Pareto frontier for each backbone size; we zoom into the informative larger\-context region\. Our33B and77B models occupy the entire high\-accuracy end of their frontier while holding a bounded budget \(near900900tokens for 4 actions\), because each action contributes a fixed\-size graph\-token block rather than growing with the retrieved text\. To make the trade\-off explicit we also plot checkpoints constrained to emit at most one, two, or three actions: the one\-action variant already lands above every baseline, and accuracy climbs by roughly a point as the budget grows to the full trajectory before saturating, so a caller can trade a few tokens for a small accuracy change without leaving the frontier\. The retrieval\-based AgentGL spends the most context yet trails in accuracy, and the single\-pass graph\-token baselines are cheaper but several points lower\. The full per\-dataset analysis is inAppendix[F](https://arxiv.org/html/2608.00542#A6)\(Figures[6](https://arxiv.org/html/2608.00542#A6.F6)and[7](https://arxiv.org/html/2608.00542#A6.F7)\)\.

![Refer to caption](https://arxiv.org/html/2608.00542v1/figures/pareto_products.png)Figure 4\.Accuracy versus inference tokens onogbn\-products\. Blue33B, orange77B; Star: ours, circle: baseline, and the dashed line is the Pareto frontier for each size\. More results are inAppendix[F](https://arxiv.org/html/2608.00542#A6)\.
### 5\.7\.Understanding the learned policy

We inspect the trained policy on ogbn\-arxiv, where it issues on average 4 actions per trajectory\. Three findings emerge\. First, the policy is adaptive: trajectory length is stable within ogbn\-arxiv but ranges from a single action to the full ladder across datasets, lengthening with how much the node text leaves unresolved, so the model reaches for graph tokens only when the text falls short\. Second, the graph view it chooses to encode carries the discriminative signal the text alone leaves ambiguous\. Third, the injected tokens are legible: passed through a Stage 1 reader, a token decodes to the research area of its graph view, and that topical signal is what fixes the label\. The activity\-recognition paper “gimme signals”, whose abstract reads like signal processing, is a representative case: its tokens decode to computer\-vision content and move the prediction tocs\.CV\. More analysis results are inAppendix[I](https://arxiv.org/html/2608.00542#A9)\.

### 5\.8\.Further analysis

More studies are deferred to the appendix for space\.Appendix[G](https://arxiv.org/html/2608.00542#A7)analyses training cost, placing accuracy against total training time and breaking our three\-stage pipeline down stage by stage\.Appendix[H](https://arxiv.org/html/2608.00542#A8)reports sensitivity checks on hyperparameters\.

## 6\.Conclusion

We introduced*Agentic Graph Token \(AGT\) reasoning*, which turns graph token from a one\-shot preprocessing step into part of reasoning: at each step the model names a graph view, an encoder materialises it into a fixed\-size graph\-token block on demand, and the block is spliced back into the context, so the tokens it reads are chosen as it reasons\. A three\-stage pipeline teaches the model to read graph tokens, keeps that reading grounded through a consistency regulariser, and rewards trajectories whose graph and text evidence agree\. Our model outperforms comparably sized graph\-token and agentic baselines on graph benchmarks and transfers zero\-shot to unrelated domains, with our analyses attributing the gains to the graph\-token medium rather than the agentic loop alone\. Taken together, the results argue for treating the graph tokens as an instrument the model calls during reasoning rather than a fixed pattern, pushing graph analysis to an effective agentic paradigm\.

## References

- \(1\)
- Azar et al\.\(2024\)Mohammad Gheshlaghi Azar, Zhaohan Daniel Guo, Bilal Piot, Remi Munos, Mark Rowland, Michal Valko, and Daniele Calandriello\. 2024\.A general theoretical paradigm to understand learning from human preferences\. In*International Conference on Artificial Intelligence and Statistics*\. PMLR, 4447–4455\.
- Besta et al\.\(2024\)Maciej Besta, Nils Blach, Ales Kubicek, Robert Gerstenberger, Michal Podstawski, Lukas Gianinazzi, Joanna Gajda, Tomasz Lehmann, Hubert Niewiadomski, Piotr Nyczyk, et al\.2024\.Graph of thoughts: Solving elaborate problems with large language models\. In*Proceedings of the AAAI conference on artificial intelligence*, Vol\. 38\. 17682–17690\.
- Chen et al\.\(2024c\)Runjin Chen, Tong Zhao, Ajay Jaiswal, Neil Shah, and Zhangyang Wang\. 2024c\.LLaGA: large language and graph assistant\. In*Proceedings of the 41st International Conference on Machine Learning*\. 7809–7823\.
- Chen et al\.\(2024a\)Zhikai Chen, Haitao Mao, Hang Li, Wei Jin, Hongzhi Wen, Xiaochi Wei, Shuaiqiang Wang, Dawei Yin, Wenqi Fan, Hui Liu, et al\.2024a\.Exploring the potential of large language models \(llms\) in learning on graphs\.*ACM SIGKDD Explorations Newsletter*25, 2 \(2024\), 42–61\.
- Chen et al\.\(2024b\)Zhikai Chen, Haitao Mao, Hongzhi Wen, Haoyu Han, Wei Jin, Haiyang Zhang, Hui Liu, and Jiliang Tang\. 2024b\.Label\-free node classification on graphs with large language models \(llms\)\. In*International Conference on Learning Representations*, Vol\. 2024\. 31632–31655\.
- Deng et al\.\(2024\)Yuntian Deng, Yejin Choi, and Stuart Shieber\. 2024\.From explicit cot to implicit cot: Learning to internalize cot step by step\.*arXiv preprint arXiv:2405\.14838*\(2024\)\.
- Fang et al\.\(2024\)Yi Fang, Dongzhe Fan, Daochen Zha, and Qiaoyu Tan\. 2024\.Gaugllm: Improving graph contrastive learning for text\-attributed graphs with large language models\. In*Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining*\. 747–758\.
- Goyal et al\.\(\[n\. d\.\]\)Sachin Goyal, Ziwei Ji, Ankit Singh Rawat, Aditya Krishna Menon, Sanjiv Kumar, and Vaishnavh Nagarajan\. \[n\. d\.\]\.Think before you speak: Training Language Models With Pause Tokens\. In*The Twelfth International Conference on Learning Representations*\.
- Guo et al\.\(2025\)Daya Guo, Dejian Yang, Haowei Zhang, Junxiao Song, Peiyi Wang, Qihao Zhu, Runxin Xu, Ruoyu Zhang, Shirong Ma, Xiao Bi, et al\.2025\.DeepSeek\-R1 incentivizes reasoning in LLMs through reinforcement learning\.*Nature*645, 8081 \(2025\), 633–638\.
- Guo et al\.\(2023\)Jiayan Guo, Lun Du, Hengyu Liu, Mengyu Zhou, Xinyi He, and Shi Han\. 2023\.Gpt4graph: Can large language models understand graph structured data? an empirical evaluation and benchmarking\.*arXiv preprint arXiv:2305\.15066*\(2023\)\.
- Hamilton et al\.\(2017\)William L\. Hamilton, Rex Ying, and Jure Leskovec\. 2017\.Inductive Representation Learning on Large Graphs\. In*Advances in Neural Information Processing Systems \(NeurIPS\)*\.
- Hao et al\.\(2024\)Shibo Hao, Sainbayar Sukhbaatar, DiJia Su, Xian Li, Zhiting Hu, Jason Weston, and Yuandong Tian\. 2024\.Training large language models to reason in a continuous latent space\.*arXiv preprint arXiv:2412\.06769*\(2024\)\.
- He et al\.\(2023\)Xiaoxin He, Xavier Bresson, Thomas Laurent, Adam Perold, Yann LeCun, and Bryan Hooi\. 2023\.Harnessing explanations: Llm\-to\-lm interpreter for enhanced text\-attributed graph representation learning\.*arXiv preprint arXiv:2305\.19523*\(2023\)\.
- Hu et al\.\(2020\)Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec\. 2020\.Open graph benchmark: Datasets for machine learning on graphs\.*Advances in neural information processing systems*33 \(2020\), 22118–22133\.
- Huang et al\.\(2023\)Jin Huang, Xingjian Zhang, Qiaozhu Mei, and Jiaqi Ma\. 2023\.Can LLMs Effectively Leverage Graph Structural Information through Prompts, and Why?*arXiv preprint arXiv:2309\.16595*\(2023\)\.
- Jaech et al\.\(2024\)Aaron Jaech, Adam Kalai, Adam Lerer, Adam Richardson, Ahmed El\-Kishky, Aiden Low, Alec Helyar, Aleksander Madry, Alex Beutel, Alex Carney, et al\.2024\.Openai o1 system card\.*arXiv preprint arXiv:2412\.16720*\(2024\)\.
- Jiang et al\.\(2023\)Albert Q Jiang, Alexandre Sablayrolles, Arthur Mensch, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Florian Bressand, Gianna Lengyel, Guillaume Lample, Lucile Saulnier, et al\.2023\.Mistral 7B\.*arXiv preprint arXiv:2310\.06825*\(2023\)\.
- Jin et al\.\(2024\)Bowen Jin, Chulin Xie, Jiawei Zhang, Kashob Kumar Roy, Yu Zhang, Zheng Li, Ruirui Li, Xianfeng Tang, Suhang Wang, Yu Meng, et al\.2024\.Graph chain\-of\-thought: Augmenting large language models by reasoning on graphs\. In*Findings of the Association for Computational Linguistics: ACL 2024*\. 163–184\.
- Kipf and Welling \(2016\)Thomas N Kipf and Max Welling\. 2016\.Semi\-supervised classification with graph convolutional networks\.*arXiv preprint arXiv:1609\.02907*\(2016\)\.
- Kong et al\.\(2025\)Lecheng Kong, Jiarui Feng, Hao Liu, Chengsong Huang, Jiaxin Huang, Yixin Chen, and Muhan Zhang\. 2025\.GOFA: A generative one\-for\-all model for joint graph language modeling\. In*13th International Conference on Learning Representations, ICLR 2025*\. International Conference on Learning Representations, ICLR, 58209–58240\.
- Li et al\.\(2024\)Rui Li, Jiwei Li, Jiawei Han, and Guoyin Wang\. 2024\.Similarity\-based neighbor selection for graph llms\.*arXiv preprint arXiv:2402\.03720*\(2024\)\.
- Liu et al\.\(2026\)Jiajin Liu, Yuanfu Sun, Dongzhe Fan, and Qiaoyu Tan\. 2026\.GraphSearch: Agentic Search\-Augmented Reasoning for Zero\-Shot Graph Learning\.*arXiv preprint arXiv:2601\.08621*\(2026\)\.
- Liu et al\.\(2024\)Zheyuan Liu, Xiaoxin He, Yijun Tian, and Nitesh V Chawla\. 2024\.Can we soft prompt llms for graph learning tasks?\. In*Companion proceedings of the ACM web conference 2024*\. 481–484\.
- Rafailov et al\.\(2023\)Rafael Rafailov, Archit Sharma, Eric Mitchell, Stefano Ermon, Christopher D Manning, and Chelsea Finn\. 2023\.Direct preference optimization: your language model is secretly a reward model\. In*Proceedings of the 37th International Conference on Neural Information Processing Systems*\. 53728–53741\.
- Reimers and Gurevych \(2019\)Nils Reimers and Iryna Gurevych\. 2019\.Sentence\-bert: Sentence embeddings using siamese bert\-networks\. In*Proceedings of the 2019 conference on empirical methods in natural language processing and the 9th international joint conference on natural language processing \(EMNLP\-IJCNLP\)*\. 3982–3992\.
- Shao et al\.\(2024\)Zhihong Shao, Peiyi Wang, Qihao Zhu, Runxin Xu, Junxiao Song, Xiao Bi, Haowei Zhang, Mingchuan Zhang, YK Li, Yang Wu, et al\.2024\.Deepseekmath: Pushing the limits of mathematical reasoning in open language models\.*arXiv preprint arXiv:2402\.03300*\(2024\)\.
- Shchur et al\.\(2018\)Oleksandr Shchur, Maximilian Mumme, Aleksandar Bojchevski, and Stephan Günnemann\. 2018\.Pitfalls of graph neural network evaluation\.*arXiv preprint arXiv:1811\.05868*\(2018\)\.
- Song et al\.\(2020\)Kaitao Song, Xu Tan, Tao Qin, Jianfeng Lu, and Tie\-Yan Liu\. 2020\.Mpnet: Masked and permuted pre\-training for language understanding\.*Advances in neural information processing systems*33 \(2020\), 16857–16867\.
- Sun et al\.\(2026\)Yuanfu Sun, Kang Li, Dongzhe Fan, Jiajin Liu, and Qiaoyu Tan\. 2026\.Agentgl: Towards agentic graph learning with llms via reinforcement learning\. In*Proceedings of the 64th Annual Meeting of the Association for Computational Linguistics \(Volume 1: Long Papers\)*\. 25313–25335\.
- Sun et al\.\(2025\)Yuanfu Sun, Zhengnan Ma, Yi Fang, Jing Ma, and Qiaoyu Tan\. 2025\.Graphicl: Unlocking graph learning potential in llms through structured prompt design\. In*Findings of the Association for Computational Linguistics: NAACL 2025*\. 2440–2459\.
- Szklarczyk et al\.\(2019\)Damian Szklarczyk, Annika L Gable, David Lyon, Alexander Junge, Stefan Wyder, Jaime Huerta\-Cepas, Milan Simonovic, Nadezhda T Doncheva, John H Morris, Peer Bork, et al\.2019\.STRING v11: protein–protein association networks with increased coverage, supporting functional discovery in genome\-wide experimental datasets\.*Nucleic acids research*47, D1 \(2019\), D607–D613\.
- Tang et al\.\(2024\)Jiabin Tang, Yuhao Yang, Wei Wei, Lei Shi, Lixin Su, Suqi Cheng, Dawei Yin, and Chao Huang\. 2024\.Graphgpt: Graph instruction tuning for large language models\. In*Proceedings of the 47th International ACM SIGIR Conference on Research and Development in Information Retrieval*\. 491–500\.
- Team \(2024\)Qwen Team\. 2024\.Qwen2\.5 Technical Report\.*arXiv preprint arXiv:2412\.15115*\(2024\)\.
- Touvron et al\.\(2023\)Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie\-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al\.2023\.Llama: Open and efficient foundation language models\.*arXiv preprint arXiv:2302\.13971*\(2023\)\.
- Veličković et al\.\(2018\)Petar Veličković, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio\. 2018\.Graph Attention Networks\. In*International Conference on Learning Representations*\.
- Wang et al\.\(2024\)Duo Wang, Yuan Zuo, Fengzhi Li, and Junjie Wu\. 2024\.Llms as zero\-shot graph learners: Alignment of gnn representations with llm token embeddings\.*Advances in neural information processing systems*37 \(2024\), 5950–5973\.
- Wei et al\.\(2022\)Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al\.2022\.Chain\-of\-thought prompting elicits reasoning in large language models\.*Advances in neural information processing systems*35 \(2022\), 24824–24837\.
- Yang et al\.\(2016\)Zhilin Yang, William Cohen, and Ruslan Salakhudinov\. 2016\.Revisiting semi\-supervised learning with graph embeddings\. In*International conference on machine learning*\. PMLR, 40–48\.
- Ye et al\.\(2024\)Ruosong Ye, Caiqi Zhang, Runhui Wang, Shuyuan Xu, and Yongfeng Zhang\. 2024\.Language is All a Graph Needs\. In*18th Conference of the European Chapter of the Association for Computational Linguistics, EACL 2024\-Findings of EACL 2024*\. Association for Computational Linguistics \(ACL\), 1955–1973\.
- Zhang et al\.\(2024\)Mengmei Zhang, Mingwei Sun, Peng Wang, Shen Fan, Yanhu Mo, Xiaoxiao Xu, Hong Liu, Cheng Yang, and Chuan Shi\. 2024\.Graphtranslator: Aligning graph model to large language model for open\-ended tasks\. In*Proceedings of the ACM Web Conference 2024*\. 1003–1014\.
- Zhang et al\.\(2025\)Qihai Zhang, Xinyue Sheng, Yuanfu Sun, and Qiaoyu Tan\. 2025\.Trustglm: Evaluating the robustness of graphllms against prompt, text, and structure attacks\. In*Proceedings of the 31st ACM SIGKDD Conference on Knowledge Discovery and Data Mining V\. 2*\. 5912–5923\.
- Zhao et al\.\(2023\)Jianan Zhao, Le Zhuo, Yikang Shen, Meng Qu, Kai Liu, Michael Bronstein, Zhaocheng Zhu, and Jian Tang\. 2023\.Graphtext: Graph reasoning in text space\.*arXiv preprint arXiv:2310\.01089*\(2023\)\.

## Appendix ALimitations and Future Work

The node text features come from a frozen mpnet encoder throughout; a stronger pretrained feature extractor would propagate directly through our jointly trained graph encoder\. We did not explore joint NC\+\+LP training extensively in this work; preliminary results suggest that node\-classification and link\-prediction actions need separate namespaces before the model emits them coherently, and we leave a full joint study to future work\. The IPO stage is currently fed only with text\-shuffle preference pairs; combining text and graph perturbations into a single pair set is a natural next step\.

## Appendix BDataset descriptions

We evaluate on the ten text\-attributed graphs listed in Section[5\.1](https://arxiv.org/html/2608.00542#S5.SS1); each node carries raw text, from which the MPNet features are computed\. Following AgentGL\(Sun et al\.,[2026](https://arxiv.org/html/2608.00542#bib.bib30)\), node classification samples3,0003\{,\}000training nodes per dataset from the training split and evaluates on a held\-out sample of1,0001\{,\}000test nodes; link prediction trains on1,5001\{,\}500positive and1,5001\{,\}500negative node pairs per dataset and tests on500500positive and500500negative pairs\. We detail each graph below\.

#### Citation graphs

ogbn\-arxivis a citation network of arXiv CS papers labelled with4040subject areas, with the title and abstract as node text; it is our primary in\-domain benchmark and the source domain for all zero\-shot transfer\.arXiv\-2023is a same\-label\-space \(4040\-class\) citation graph of papers published in 2023, used to probe temporal distribution shift\.PubMed\(33diabetes\-related classes\),Cora\(77machine\-learning topics\), andCiteSeer\(66computer\-science topics\) are the standard small citation benchmarks, again with titles/abstracts as node text\.

#### Co\-purchase / co\-review graphs

ogbn\-productsis an Amazon co\-purchase graph with product descriptions as node text and4242product categories\.Amazon\-Computers\(1010classes\) andAmazon\-Photo\(88classes\) are smaller co\-purchase graphs from the same family, used as zero\-shot targets\.

#### Social graph

Redditis a post\-interaction graph with post text as node attributes and community labels\.

#### Biological graph

STRING\-dbis a human protein\-protein interaction network built from the STRING database\(Szklarczyk et al\.,[2019](https://arxiv.org/html/2608.00542#bib.bib32)\); node text describes each protein and the2121labels are COG protein\-function classes\. It stresses methods on a largely non\-text\-centric domain where the label depends heavily on graph structure\.

## Appendix CBaseline implementation details

Every same\-backbone baseline uses the identical Qwen2\.5\-3B\-Instruct backbone, the identical per\-domain splits \(the same train/test node splits for node classification and the same candidate pairs for link prediction\), and the same MPNet node text\-features as our method; they differ only in mechanism\. All are re\-implemented faithfully to each method’s original design\. We verified that no test node or candidate pair appears in any training corpus for any domain, including the alignment corpora\.

#### Qwen \(zero\-shot\)

The frozen backbone is prompted with the target node’s title\+\+abstract and the candidate\-category list and asked to emit a single category\. No graph structure and no training\.

#### Qwen \(CoT\)

As zero\-shot, but the model is asked to reason step by step before committing to a category \(it names the core topic and method, shortlists the likely classes, and eliminates the rest\)\. Text only, no graph, no training\.

#### Graph2Text\-SFT

A supervised baseline that verbalises the anchor node together with its one\-hop neighbours as text and fine\-tunes the Qwen backbone to predict the label\. It uses the graph structure but as serialised text rather than tokens\.

#### LLM\-GNN

Following the LLM\-as\-annotator recipe, Qwen labels a pool of nodes from text alone; a GraphSAGE classifier is then trained on these pseudo\-labels over the graph and evaluated on the held\-out test set\.

#### Graph\-token baselines \(TEA\-GLM, GraphGPT, GraphTranslator\)

These share our token interface: a node’skk\-hop neighbourhood is pooled by a GraphSAGE encoder over MPNet features and projected to a block of128128graph\-token embeddings that are spliced into the prompt in place of a placeholder span\. They differ in*what is trained*:

- •TEA\-GLMkeeps the LLM frozen and trains only the graph encoder/projector, on a single\-token instruction corpus, one11\-hop graph token per training node plus a direct classification instruction\.
- •GraphGPTuses the same single\-token corpus but*tunes*the LLM jointly with the encoder \(learning rate10−510^\{\-5\}\); it is the tuned counterpart of frozen TEA\-GLM\.
- •GraphTranslatorfreezes the LLM and trains a two\-stage translator: Stage A aligns graph tokens to an LLM\-generated description of the node and its neighbours, following the method’s Producer stage, and Stage B fine\-tunes the translator on the downstream task\.

#### Common training setup

The encoder/projector are trained with graph learning rate5×10−45\\times 10^\{\-4\}, one epoch, gradient accumulation44, maximum sequence length20482048, and an answer\-token loss weight of2020\. Node\-classification corpora are capped at2020k training samples and link\-prediction corpora at66k, drawn only from the training split\. All baselines run on the same hardware as our method\.

#### Link prediction

For a pair\(u,v\)\(u,v\), each endpoint’s11\-hop subgraph is encoded*with the target edge masked from both endpoints*, identical to our method\. The two token blocks are spliced into a yes/no edge\-existence prompt and we scorelogit​\(yes\)−logit​\(no\)\\mathrm\{logit\}\(\\texttt\{yes\}\)\-\\mathrm\{logit\}\(\\texttt\{no\}\), reporting AUC over the balanced1,0001\{,\}000\-pair test set\. TEA\-GLM freezes the LLM, GraphGPT tunes it \(learning rate10−510^\{\-5\}\), and GraphTranslator uses its two\-stage translator; all train on AgentGL’s canonical1,5001\{,\}500positive\+\+1,5001\{,\}500negative training pairs, the same pairs our Stages 2–3 consume\.

## Appendix DPer\-stage training corpus

Our three training stages consume distinct corpora, all built from the same per\-domain training split; no test node appears in any stage\. Node text\-features are MPNet embeddings of title\+\+abstract, and graph tokens are produced on the fly by the GraphSAGE encoder for whichever scope an action requests\. We describe each stage’s corpus construction, format, and size below \(ogbn\-arxiv figures; other domains follow the same recipe\)\.

#### Stage 1: alignment \(learning to read graph tokens\)

Purpose: ground every kind of graph token so the LM can decode node content and local structure from the token block alone\. For each training node we sample one action scope \(11\-,22\-, or33\-hop subgraph pooling, top\-KKMPNet retrieval, or cosine\-similarity\), encode it to a128128\-token block, and set the target to \(i\) reconstruct the anchor’s title\+\+abstract and/or \(ii\) answer a masked link\-prediction query, from the tokens alone\. Covering all scopes ensures every token type is supervised\. Corpus:≈40\\approx\\\!40k examples, one epoch\.

#### Stage 2: token\-robust trajectory SFT

Purpose: teach free\-choice agentic reasoning\. Each example is a multi\-turn trajectory: the prompt carries the node’s title\+\+abstract and the task; the assistant then emits a sequence of action calls \(node\_token,one\_hop\_token,two\_hop\_token,three\_hop\_token,retrieval\_token,cluster\_token; pluscosine\_simfor link prediction\), each returning a graph\-token block, and finally the answer\. The loss is masked to the assistant’s action and answer spans\. Corpus:≈9\\approx\\\!9k trajectories, one epoch, maximum length20482048\. To force the policy to*use*the tokens rather than lean on the prompt text, training uses consistency\-regularized joint training \(CRJT\): graph tokens are perturbed \(token\-mask0\.20\.2, edge\-drop0\.10\.1\) and a KL term \(weight0\.50\.5\) aligns the clean and perturbed predictions\.

#### Stage 3: rollout IPO

Purpose: refine the Stage\-2 policy with preference optimisation on its own rollouts\. For each training node we run two greedy rollouts of the Stage\-2 policy: a consistent one on the real node text and graph, and an inconsistent one whose node text is shuffled so that it disagrees with the graph\. We keep a pair only when the consistent rollout is correct and the shuffled one is wrong, and prefer the consistent trajectory, so the objective rewards agreement between the graph and text evidence\. Preferences are optimised with IPO \(β=0\.3\\beta=0\.3, learning rate3×10−73\\times 10^\{\-7\}, gradient accumulation44\)\. No new graph data is introduced, the stage reweights trajectories the model already produces\.

#### Link prediction

LP shares Stage 1 and re\-runs Stages 2–3 on LP\-specific corpora built from AgentGL’s canonical training pairs \(1,5001\{,\}500positive\+\+1,5001\{,\}500negative per domain\): each example encodes both endpoints’11\-hop subgraphs with the target edge masked from both, and supervises ayes/noedge decision\.

## Appendix EError structure analysis

To understand*where*our agentic graph\-token policy helps, we compare its per\-node error structure against AgentGL, the strongest agentic text\-retrieval baseline, on the shared1,0001\{,\}000\-node test samples of four datasets: ogbn\-arxiv, ogbn\-products, PubMed, and Reddit\. Both methods answer the same nodes, so the comparison is paired\. Figure[5](https://arxiv.org/html/2608.00542#A5.F5)plots the error\-fraction density over node degree, one panel per dataset: a Gaussian kernel density estimate over the degree of the misclassified nodes, with each curve scaled so its area equals that model’s error mass\. A lower curve therefore means fewer errors, and its shape shows on which nodes they fall\.

On every dataset our error mass sits below AgentGL’s, and on the text\-rich graphs the gap is wide\. The errors of both methods concentrate on lower\-degree nodes, where the graph signal is scarcest, but our density stays below AgentGL’s across the whole degree range, not merely at the well\-connected end\. Choosing a graph view to encode thus leaves fewer residual errors than retrieving text, and the improvement is spread across the degree spectrum instead of resting on a few easy hubs\.

![Refer to caption](https://arxiv.org/html/2608.00542v1/figures/error_density_4panel.png)Figure 5\.Error\-fraction density over node degree, one panel per dataset, using the same conventions as Figure[3](https://arxiv.org/html/2608.00542#S5.F3)\. Our density lies below AgentGL’s on all four datasets\.
## Appendix FInference cost

A method is only useful if it reaches an answer at a reasonable cost, so we ask how much context each approach spends per node: the average number of tokens the model processes for one query, counting the prompt, every injected graph\-token or retrieved\-text block, and the generated reasoning\. For our method and the agentic and static\-token baselines we tokenise the recorded trajectories with the Qwen tokeniser; for the single\-pass graph\-token baselines we read the budget off their architecture\. Figures[6](https://arxiv.org/html/2608.00542#A6.F6)and[7](https://arxiv.org/html/2608.00542#A6.F7)place each method on the accuracy versus context plane for every dataset and both backbone sizes\. The vertical position is a method’s measured node\-classification accuracy from the main table; the horizontal position is its per\-query context\.

For AgentGL we measure the context per dataset, since the amount of text it retrieves varies with the corpus: its budget ranges from about790790tokens on Reddit to about1,4301\{,\}430on STRING\-db, where the protein descriptions are long, and on the heaviest individual queries it passes1,6001\{,\}600\. Our own budget stays near900900tokens on every dataset because each action contributes the same fixed\-size block regardless of the graph view it summarises, so the graph evidence never inflates the context the way retrieved text does\. The single\-pass graph\-token baselines are cheaper still, near300300tokens, but their accuracy settles several points lower because one static block cannot be revised as the reasoning proceeds\. On every dataset except the homophilous CiteSeer, where LLaGA leads at the 3B scale, our method occupies the accuracy\-maximal position on the frontier while keeping this bounded budget\.

![Refer to caption](https://arxiv.org/html/2608.00542v1/figures/pareto_pp_a.png)Figure 6\.Accuracy against inference context \(part 1 of 2\): ogbn\-arxiv, ogbn\-products, PubMed, Reddit\. Colour encodes backbone size \(blue = 3B, orange = 7B\) and marker encodes method \(star = ours, circle = baseline\); the horizontal axis is tokens processed per query on a log scale\. AgentGL’s context is measured per dataset; the other methods use a method\-representative value measured on ogbn\-arxiv\. Both our variants sit on the accuracy\-maximal corner of the frontier at a bounded context near900900tokens\.![Refer to caption](https://arxiv.org/html/2608.00542v1/figures/pareto_pp_b.png)Figure 7\.Accuracy against inference context \(part 2 of 2\): arXiv\-2023, CiteSeer, STRING\-db\. Same conventions as Figure[6](https://arxiv.org/html/2608.00542#A6.F6): blue = 3B, orange = 7B; star = ours, circle = baseline\.
## Appendix GTraining\-time analysis

Beyond inference context \(Appendix[F](https://arxiv.org/html/2608.00542#A6)\), we compare methods by their one\-time training cost\. Figure[8](https://arxiv.org/html/2608.00542#A7.F8)plots ogbn\-arxiv node\-classification accuracy against total training time for the 3B configuration\. We gauge each method on a single GPU: for our pipeline and the fine\-tuned baselines we multiply the number of optimiser steps \(corpus size times epochs, over the effective batch\) by a measured throughput of about two optimiser steps per second for the 3B backbone; the reinforcement\-learning baseline AgentGL is dominated by on\-policy rollouts and is scaled up per its rollout\-heavy recipe; the zero\-shot and chain\-of\-thought baselines need no training\. Our full pipeline \(Stage 1 alignment on4040k pairs, Stage 2 trajectory SFT plus consistency regularisation on99k, and Stage 3 rollout IPO\) totals about2\.82\.8GPU\-hours\. This sits in the same band as the single\-stage fine\-tuned baselines and roughly4×4\\timesbelow the RL\-trained AgentGL \(∼12\\sim\\\!12GPU\-hours\), while reaching the highest accuracy\. The training\-free baselines are cheapest but trail in accuracy, chain\-of\-thought being the strongest among them\. Our method thus occupies the accuracy\-maximal corner at a moderate, supervised\-fine\-tuning\-level budget\. These are single\-GPU estimates gauged from each method’s configuration and measured per\-step throughput, intended as order\-of\-magnitude comparisons rather than exact wall\-clock\. Figure[9](https://arxiv.org/html/2608.00542#A7.F9)breaks our budget down by stage: the Stage 1 alignment pass over4040k pairs is the largest single item at about1\.41\.4hours, with the trajectory SFT, consistency, and rollout phases together accounting for the remaining1\.41\.4hours\.

![Refer to caption](https://arxiv.org/html/2608.00542v1/figures/time_analysis.png)Figure 8\.Accuracy against total training time \(3B configuration\) on ogbn\-arxiv\. Our three\-stage pipeline \(star\) reaches the highest accuracy at a moderate, SFT\-level budget \(∼2\.8\\sim\\\!2\.8GPU\-hours\), roughly4×4\\timesbelow the RL\-trained AgentGL\. Training\-free baselines \(zero\-shot, chain\-of\-thought\) are cheapest but lower in accuracy\. Times are single\-GPU estimates gauged from each method’s configuration and a measured per\-step throughput\.![Refer to caption](https://arxiv.org/html/2608.00542v1/figures/time_breakdown.png)Figure 9\.Per\-stage training\-time breakdown of our three\-stage 3B pipeline \(Stage 2 shown as its trajectory\-SFT and consistency phases\)\. The Stage 1 alignment pass over4040k pairs is the largest single cost; the trajectory SFT, consistency regularisation, and rollout IPO phases are comparatively cheap, for a total of about2\.82\.8GPU\-hours\.
## Appendix HSensitivity analysis

We study how two pooler design choices affect end\-to\-end accuracy: the number of tokens each graph\-token action emits and the GNN backbone inside the pooler\. For each setting we run the full pipeline with the33B backbone and report node\-classification accuracy on the same1,0001\{,\}000\-node test split, across four datasets: two citation graphs \(ogbn\-arxiv and PubMed\), a co\-purchase graph \(ogbn\-products\), and a social graph \(Reddit\)\.

Figure[10](https://arxiv.org/html/2608.00542#A8.F10)varies the per\-action token budget\. Accuracy rises steeply from1616to3232tokens and then flattens: beyond6464tokens the four datasets move by only a few tenths of a point, and128128is at or within noise of the best setting everywhere whileogbn\-arxivstill gains slightly at256256\. We use128128as the default, trading a negligible accuracy change for half the inference context of256256\.

Figure[11](https://arxiv.org/html/2608.00542#A8.F11)varies the GNN backbone at the default128128tokens\. The pooler is robust to this choice, with the three convolutions within about a point and a half on every dataset\. GraphSAGE is the strongest or tied\-strongest on three of the four datasets and the cheapest of the three, so we adopt it throughout\.

![Refer to caption](https://arxiv.org/html/2608.00542v1/figures/sens_tokens.png)Figure 10\.Per\-action token budget vs\. full\-pipeline NC accuracy \(33B\) on four datasets \(note the independentyy\-axis per panel\)\. Accuracy saturates by roughly6464–128128tokens; the starred point marks the128128\-token default\.![Refer to caption](https://arxiv.org/html/2608.00542v1/figures/sens_gnn.png)Figure 11\.GNN backbone vs\. full\-pipeline NC accuracy \(33B,128128tokens per action; note the independentyy\-axis per panel\)\. The three convolutions stay within about a point and a half; GraphSAGE \(blue\) is the default\.
## Appendix ITrajectory case studies

The number of actions the policy issues is not fixed\. Across datasets a trajectory runs from a single action to the full ladder, and the length grows with how much the node’s own text leaves unresolved\. We walk through four correct predictions, one at each observed length\.

#### One action\.

ARedditpost reading “recently got into japanese knives and this 120mm wa\-petty is my favorite” \(goldchefknives\) is unambiguous from its text alone\. The policy issues a single`anchor\_text`echo of the post and stops; no graph token is needed\.

#### Two actions\.

APubMedarticle, “altered glycolytic and oxidative capacities of skeletal muscle contribute to insulin resistance” \(goldType 2 diabetes\), is clearly metabolic but its label is one of a few closely related diabetes classes\. The policy reads the anchor text and then a`cluster\_token`for the community it sits in, whose members pin down the specific class\.

#### Three actions\.

Anogbn\-productsitem, “Brother high\-speed label printer with wireless networking” \(goldOffice Products\), could as easily be filed under electronics\. The policy escalates:`anchor\_text`, then a`cluster\_token`for the product community, then a`one\_hop\_token`for the item’s co\-purchase neighbourhood; the co\-purchased office equipment settles it onOffice Productsinstead of a generic electronics label\.

#### Four actions \(Figure[12](https://arxiv.org/html/2608.00542#A9.F12)\)\.

The longest of our case studies is theogbn\-arxivpaper “gimme signals: discriminative signal encoding for multimodal activity recognition” \(goldcs\.CV\), whose title alone reads like signal processing\. Figure[12](https://arxiv.org/html/2608.00542#A9.F12)traces the four steps\. The policy first echoes the abstract with`anchor\_text`, which leaves the label unresolved\. It then issues a`cluster\_token`for the paper’s community; passed through the Stage\-1 reader \(below\), that token decodes to “deep learning for image classification with multiple labels\.” Still not settled, it widens to a`three\_hop\_token`, whose token reads back as “deep learning for image captioning,” and closes with a second`cluster\_token`that again decodes to image\-classification content\. All three graph tokens land in computer\-vision methodology, so the model answerscs\.CVrather than a signal\-processing label\.

Query paper:“gimme signals: discriminative signal encoding for multimodal activity recognition” gold labelcs\.CVthe text alone reads like signal processing1\. anchor\_text
echo the paper’s own title and abstract2\. cluster\_token
pooled community token3\. three\_hop\_token
pooled 3\-hop neighbourhood token4\. cluster\_token
re\-encode the communitypredicted label:cs\.CV\(computer vision, not signal processing\)Stage\-1 reader decodes this token as:
“deep learning for image classification with multiple labels”Stage\-1 reader decodes this token as:
“deep learning for image captioning”Stage\-1 reader decodes this token as:
“deep learning for image classification” \(same community, re\-encoded\)Figure 12\.Agentic trajectory for oneogbn\-arxivnode and what a Stage\-1 reader recovers from each injected graph token\. The policy escalates from the paper’s own text to pooled community and neighbourhood tokens; decoding those tokens back to text shows they carry computer\-vision content \(the discriminative signal forcs\.CV\), recovering the research area of that neighbourhood, not a verbatim copy\.
#### Reading the injected tokens\.

To check what the policy actually recovers from a graph token, we decode it with a Stage 1 reader, a copy of the aligned model asked to describe a node from its pooled token alone \(using the Stage 1 encoder, not the preference\-tuned one\)\. For the arxiv paper above \(Figure[12](https://arxiv.org/html/2608.00542#A9.F12)\), its`three\_hop\_token`and`cluster\_token`decode to computer\-vision text, for instance “deep learning for image classification” and “image captioning,” none of which echoes the paper’s own signal\-processing wording\. What the reader recovers is the research area of the encoded graph view, not a verbatim copy, and this topical signal is what pulls the prediction towardcs\.CV\. The behaviour is consistent across nodes: analbertlanguage\-model paper decodes to text\-generation content and a knowledge\-graph\-embedding paper to machine\-learning methodology, each landing in the right area without reproducing the title\. The pooled token thus carries enough topical structure to place the node, though not enough to reconstruct its text\.

In each case the policy spends more graph tokens exactly when the text is least sufficient, and the graph view it chooses to encode carries the discriminative signal\.