Graph-KV: Breaking Sequence via Injecting Structural Biases into Large Language Models
Authors: Haoyu Peter Wang
Peihao Wang
Mufei Li
Shikun Liu
Siqi Miao
Zhangyang Wang
Pan Li
Venue: NeurIPS 2025 poster ()
Keywords: Large Language Model
Graph
Retrieval-augmented Generation
Structural Inductive Biases
Primary area: deep_learning

Abstract: Modern large language models (LLMs) are inherently auto-regressive, requiring input to be serialized into flat sequences regardless of their structural dependencies. This serialization hinders the model’s ability to leverage structural inductive biases, especially in tasks such as retrieval-augmented generation (RAG) and reasoning on data with native graph structures, where inter-segment dependencies are crucial. 
We introduce Graph-KV with the potential to overcome this limitation. Graph-KV leverages the KV-cache of text segments as condensed representations and governs their interaction through structural inductive biases. In this framework, ''target'' segments selectively attend only to the KV-caches of their designated ''source'' segments, rather than all preceding segments in a serialized sequence. This approach induces a graph-structured block mask, sparsifying attention and enabling a message-passing-like step within the LLM. Furthermore, strategically allocated positional encodings for source and target segments reduce positional bias and context window consumption. 
We evaluate Graph-KV across three scenarios: (1) seven RAG benchmarks spanning direct inference, multi-hop reasoning, and long-document understanding; (2) Arxiv-QA, a novel academic paper QA task with full-text scientific papers structured as citation ego-graphs; and (3) paper topic classification within a citation network.
By effectively reducing positional bias and harnessing structural inductive biases, Graph-KV substantially outperforms baselines, including standard costly sequential encoding, across various settings.

Graph-KV: Breaking Sequence via Injecting Structural Biases into Large Language Models
Haoyu Wang",, Peihao Wang", Mufei Li', Shikun Liu', Siqi Miao', Zhangyang Wang", Pan Li!* Georgia Institute of Technology The University of Texas at Austin
Abstract
Modern large language models (LLMs) inherently auto-regressive, requiring imput to be serialized into flat sequences regardless of their structural dependencies. This serialization hinders the model's ability to leverage structural inductive biases, especially in tasks such as retrieval-augmented generation (RAG) and reasoning on data with native graph structures, where inter-segment dependencies are crucial. We introduce Graph-KV with the potential to overcome this limitation. Graph- KV leverages the KV-cache of text segments as condensed representations and governs their interaction through structural inductive biases. In this framework, "target" segments selectively attend only to the KV-caches of their designated "source" segments, rather than all preceding segments in serialized sequence. This approach induces a graph-structure block mask, sparsifying attention and enabling pessaagepassing-iiie step within the LLM. Furthermore, strategically allocated positional encodings for source and target segments reduce positional bias and context window consumption. We evaluate Graph-KV across three scenarios: (1) seven RAG benchmarks spanning direct inference, multi-hop reasoning, and long-document understanding; (2) ARXIV-QA novel academic paper QA task with full-text scientific papers structured as citation ego-graphs; and (3) paper topic classification within citation network. By effectively reducing positional bias and harnessing structural inductive biases, Graph-KV substantially outperforms baselines, including standard costly sequential encoding, across various settings. Code and the ARXIV-QA A data are publicly available at httpt:tt////// //ggthtb......./// com/ Graph-CoM Ceae-CCM/Grappa Grah//
Introduction
Modern large language models (LLMs) [1 50 2], despite their notable successes, are fundamentally auto-regressive. This characteristic, consequence of their training approaches [1], necessi- tates the serialization of information for processing. Consequently, all input, regardless of its intrinsic structure or complex dependencies, such as order-insensitivity, temporal or logical relationships, must be flattened into an ordered sequence. This forced serialization can be suboptimal and may introduce sequential bias, potentially hindering the LLM's ability to fully leverage these internal relationships.
segments, which may lack a linear order or possess complex, non-linear interdependencies, must still be artificially serialized, which can limit effective multi-hop reasoning 17
For example, in retrieval-augmentte generation (RAG) 29
67
30 retrieved
and introduce positional biases [58 [5) (66) Similarly, processing data with native graph structures, such as citation networks 220 14] where citations signify knowledge dependencies, presents challenges. Serializing documents referenced by the same document, for instance, leads to drawbacks including: 1) positional biases that can obscure parallel citation relationships: 2) quadratic computational complexity when
62
44
49]
"Correspondence to: haoyu. wang @ gatech.edu, panli @ @atechh.euu.
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

The
The snswer ie:
Positional Encoding
Full Attention and Quadratic Complexity
Context Window Issue
Positional Bius
Doscll
Dacc 2
DesiS
Step1: Lnject Structural Inductive Binses when Prefilling
Step2: Attend Query
Doc
Doxc
Shared
L+
211 ZL/
Query with Structured
Graph-KV
When processing data with inherent structure (bottom-leftt, modern LLMs encounter three challenges due to scrialized input reading (top row): (1) positional hias, where different serialization orders lead to varied outputs 66 :2) quadratic computational complexity from full attention between all document pairs; and (3) rapid context window consumption,
Figure 1:
position indices quickly exceed limits. The bottom-right subfigure illustrates Graph-KV. Text chunks are independently encoded into KV caches, where Graph-KV arranges the text chunk of each target text after the KV of their source texts to update their respective KV caches. Notably, all source texts share same positional encoding (PE) range, while all target texts share another, with their position index immediately following that of the source nodes. This approach reduces the PE and context window usage. At query time, the query attends both the source chunks and the target chunks to perform decoding.
attending to all document pairs; and 3) context window limitations when dealing with numerous references (Fig. I.
Therefore, a critical question arises: How can we align the structural inductive bias of the data with the mechanisms of auto-regressive LLMs, moving beyond simplistic serialization?
Existing literature has explored mitigating the negative effects of token- serealssiiaiz,,inn,, primarily by aiming to climinate positional bias and enable LLMs to process text segments in permutation- invariant manner. For instance, Wang et al. [56] proposed to reorder documents based on attention scores computed without positional encodings (PEs); however, the requisite sorting and full attention computations in this method introduce significant computational overhead. Other works prioritize efficient inference by prefilling the key-value (KV) cache of documents independently in parallel [61] In these approaches, the encoding of documents within the KV-cache often relies on either shared PEs sorting based semantic similarity scores from external retrievers. Although these parallel encoding strategies enhance efficiency, they inherently cannot model inter-segment dependencies, let alone native inductive biases within the structured data (as summarized Table
43
[2] 35
To address these limitations, we introduce Graph- KV. The core principle of Graph-KV is to treat the KV cache of a given text segment as its con- densed information representation and control its generation using structural inductive biases. Specif- ically, after initially prefilling the independent KV caches of all text segments, a "target" segment's KV cache is generated by attending only the KV caches of its "source" text segments, rather than all segments that merely precede in the ooken-serialization sequence. The determination of "source + target" relationships guided by structural inductive biases tied to either the data or the specific tasks. From another perspective, this approach essentially introduces graph-structune block mask (Fig. [ that sparsifies attention computation during KV cache generation, effectively enabling "message passing through graph" step within the LLM. Moreover, to mitigate inherent positional biases from the LLM, the attention computation imposes shared PEs across the source segments, with the target segment receiving PEs with position indices immediately following sources. This design substantially reduces context window consumption through shared PEs while preserving structural alignment.
LongeCretee Frieddly
Spane Attennce Ellkiany
Piez tree
Strecuss
Saparntx Thradies Pocrptcate
13 FTW
AFE
Block Arpetinn Eoegh (1en))
Table 1: Comparison among existing approaches. "Long-Context Friendly" refers avoiding rapid context window consumption as the number input text chunks increases. "Free from positional bias" mcans model predictions remain stable irrespective of the input chunks' placement order.

---

We evaluated Graph-KV across three diverse settings. First, Graph-KV was assessed on seven
and long-document understanding [ For these tasks, where native graph structures are absent, we introduced a bipartite graph to establish structural bias between text segments. Across all RAG benchmarks, Graph-KV significantly outperformed parallel text encoding baselines. Notably, in multi-hop reasoning tasks, Graph-KV surpassed even sequential reading while maintaining sparse computation. Second, we introduced ARXIV-QA, a novel and challenging task featuring real-world graph biases. In ARXIV-QA, questions are constructed from the full text of a central scientific paper and its linked references, sourced from the arXiv citation network 20). These questions require probing technical details and understanding both content and citation relationships. On ARXIV-QA. existing efficient parallel text encoding baselines performed poorly, and standard sequential encoding demonstrated severe positional biases. In contrast, Graph-KV exhibited significant robustness, achieving performance comparable to the peak results of sequential encoding (which necessitates optimal document positioning) without displaying such sensitivity. Third, Graph-KV was evaluated on paper topic classification tasks within citation networks, which possess inherent structural biases through citation links. In this setup, LLMS must classify central paper by analyzing its title, abstract, and potentially hundreds of references. Graph-KV demonstrated significantly superior performance compared to both sequential encoding and parallel text encoding baselines.
RAG benchmarks, covering direct inference [22 25), multi-hop reasoning 49
I7
4 62],
2 Related Work
Positional Bias in LLMs. Large Language Models (LLMs) exhibit positional bias, wherein their
performance is adversely affected by the sequential order of input data 66 [5] 71
46
[8]
66 33
[5]
This phenomenon is widely believed to stem from the interplay of Positional Embeddings (PEs) 47
58
40 and the inherent causal attention mechanism [42 Although some research indicates
that removing PEs from the transformer architecture can enhance LLM generalization to longer
context windows 54, the causal attention mechanism itself can still implicitly induce positional biases [24. 16.. Concrete examples of positional bias are evident in RAG, where models often favor information placed at the beginning or end of the context [33 39], and in in-context learning, where the order of examples significantly impacts outcomes [68 34 The tasks investigated in this work necessitate a more explicit capture of structural dependencies, and our findings reveal that naively serializing input exacerbates positional bias in such scenarios.
Parallel Encoding and Block Attention. Research has explored techniques avoid quadratic computational complexity in RAG for generating KV caches for retrieved documents individually and in parallel [2] 43 12
64 70, 63). PCW 4 initiated this line of study; however, its performance can degrade substantially in many cases due to distribution shifts in the new form of KV caches. APE 61 proposes a fine-tuning-fee algorithm that mitigates distribution shifts with parallel encoding by re-scaling attention magnitudes. 772 further trains a small-LM as a scorer to refine the retrieved parallel contexts. Block-Attention over these methods, attributed to its more extensive post-training process. However, common limitation of these parallel processing strategies is their failure to model inter-document dependencies. Graph-KV mitigates this limitation while preserving the efficiency of parallel encoding.
61
72
35 demonstrates further performance improvements
Modeling structured data with LLMs. LLMs predominantly process structured data via two main strategies. The first serializes structured information like graphs into natural language formats for model input [5] 10 38]. However, this method faces scalability issues from quadratic attention complexity and the inherent challenge of accurately verbalizing intricate structural dependencies. As a result, even reasoning over moderately sized text-attributed graphs (e.g., tens of documents, 100k+ tokens) can be problematic [19 53 The second strategy uses adapter modules to project graph data into the LLM's token embedding space [60] 26 6 52 48). These adapter- based solutions often exhibit limited generalization. largely due to challenges in achieving robust adapter-mediated alignment 7 32 31 73). Graph-KV offers a distinct, more foundational approach by being the first to directly modify the LLM's attention mechanism for structured data integration.
The Challenge of Noisy Multi-Hop Reasoning. Multi-hop reasoning, which demands capturing ar- bitrary structural dependencies among multiple pieces of information, remains challenging for LLMs with standard sequential encoding. This difficulty substantially amplified in real-world scenarios where information is non-contiguous and sparsely distributed within noisy, long contexts, leading to N-fold reductions in LLM performance E 27 65). However, as our experiments demonstrate, with structural inductive biases, Graph-KV& can significantly improve the reasoning capabilities of LLMs.
3

---

3 Methodology
In this section, we introduce Graph-KV. We assume structural inductive biases can be described by a graph connecting text chunks. Such biases might originate natively from the data or be defined based on the tasks. How these are specified for various tasks will be detailed in the experimental section.
Preliminaries. Let 9 be a natural language query and G (V.E) be directed graph representing input structured data. Each node u E V corresponds to a text chunk with an average token length and each directed edge (21, E E represents some structural dependence from a source chunk un to target chunk u2- The objective is for an LLM I to generate an answer a = f(g. G) by encoding both q and G. This task requires the LLM to comprehend the individual textual content of nodes while also properly leveraging and reasoning over the structural inductive biases encoded in G.
Sequential Encoding is the default approach in modern LLMs 42 13 23 It involves processing an arbitrary linearized sequence of text chunks, denoted without loss of generality as [ui, u2...., Un where each u, E V is composed of sequence of token embeddings, by using the concatenated sequence [u1, u2..... u 9) as input. Modern LLMs commonly employ causal attention, where each token attends to all preceding tokens. This mechanism results in a computational complexity of (n (n), where L denotes the max chunk length. consequence of sequential encoding the sensitivity of the model output to input order, termed positional biases. Moreover, this default setting lacks inherent mechanisms for leveraging structural inductive biases, should they exist in the data.
Parallel Text Encoding is adopted by an alternative line of work 43 61 12 35 that treats text chunks as an unordered set, S {u,, ug...., }. Here, the LLM encodes each chunk u, E S independently and in parallel, often with all chunks sharing the same PEs to signify their lack of explicit order. The computational complexity for this encoding process is (nLL)), linear in n (the number of chunks). This method, however, discards the modeling of direct interactions among chunks, thereby sacrificing relational information critical for multi-hop hop reasoning favor of efficiency. During answer generation, tokens attend to all encoded text chunks in S and the query q.
Gvaph-KV injects structural inductive bias using two main strategies: a structure-aware attention mechanism and appropriately assigned shared Płs.
3.1 Graph-KV
The Structure-aware Attention Mechanism. First,
offline parallel encod- ing of each text chunk u, obtain its initial la- tent representation 10) These representations, Ja,ev, are then used to form initial Key- Value (KV) pairs, denoted as {(h-1) ve. )m,ev which can be loaded into the KV cache. Fol- lowing the graph structure G = (V. F), Graph- KV updates the representation of target chunk Uj by modeling its relationships via the atten- tion mechanism with its source chunks, denoted as N(i) = {u; I (ug, Uy) E E}. This update is achieved by computing sparsified attention:
"Seera' Telk
Turge Test
Query
Raad Searce
Mergo
PE:
Est w- Ma
Graph-KY Generation
Figure 2: PE-sharing mechanism in Graph-KV. As shown on the right side, source does share one PE range, while targets share another. Attending D I to the KVs of its sources (Doc.2 and Doc.3), is func- tionally equivalent
the left side: reading D followed by Doc. and Doc.3 followed by Doc. then merging the resulting representations of 1.
@2KMI VNG) where Q, is the Query vector associated with uy (the target chunk),
softmax
-Van
Vdn
KNO) = [k:10] (A()) and VirG)= = [ Iu,eN()) are matrices formed by stacking the key-values of its source chunks, respectively, and d,, used for normalization denotes the dimension of QK values.
This update procedure can be iterated for multiple rounds. However, for our experiments, we conduct a single round (i.e., t = 1). This serves as proof-of-concey to model interactions extending beyond those addressed by existing parallel encoding methods, which typically process chunks as purely independent, while preserving low computational complexity. Iterating for multiple rounds does not yield significant performance gains on the current evaluation tasks. Nevertheless, we believe that with more complex tasks, or if the model were further fine-tuned to adapt to this new attention architecture, greater improvements could be anticipated. Finally, upon query, input query tokens and subsequently generated answer tokens attend to the representations of both source and target chunks.

---

The Allocation of Positional Encodings. Our allocation of PEs aims to reduce positional bias and improve context efficiency. We begin by considering the scenario without explicit directed edges, where graph-structured data effectively becomes a collection of independent text chunks. This configuration is analogous to those many existing studies on parallel encoding [6] 35) To mitigate positional bias for these independent chunks, all such text chunks are assigned positions within the shared range [0, L). where we assume a maximum chunk length of L. Furthermore, when structural dependencies are present in the data (e.g.. via directed edges), target chunks are subsequently assigned positions from L to 2L, i.e., within another shared range [L, 2L) immediately following the first. Query tokens and any generated tokens are then allocated positions in range beyond 2L, subsequent to those of the target chunks.
While this study does not investigate the iterative application of target chunks as source chunks in subsequent processing rounds, the proposed methodology permits such natural extension. For instance, target chunks in subsequent round could be allocated positions within the range (TT,, with query token positions adjusted correspondingly; this iterative pattern can be continued as needed. A key benefit of this procedure is its conservation of the context window: since numerous chunks share identical positional ranges, the overall required positional span is only about TL. Here, T denotes the number of iterations (a generally small constant), and L is often less than 10k.
To illustrate how latent representations of target chunks are formed by Graph-KV, please refer to Fig. 2 Suppose there are directed edges doc.2 - doc. and doc.3 - doc. Graph-KV can be understood as guiding the LLM process two effective "documents": one formed by doc.2 followed by 1, and another by doc.3 followed by 1.c. The representations of the 1oc. portions obtained from both these effective documents, are then aggregated. Consequently, the representation of target chunk 1 contains the information reflecting its connections to source chunks doc.2 and doc.3.
Computational Complexity. The representations for all text chunks in the first round are computed with complexity O(VV)L), aligning with previous parallel encoding methods. Sup- pose T is set of target chunks, updating target chunk representations has complexity of as E is the total number of such dependencies. During query time, the attention complexity for each query or generated token over all source and target chunks is ((V)), similar to vanilla sequential and parallel encoding schemes at generation.
O(E,, ET (3)) = O(E)L?)
Remark: Attention Sink. APE [6] considers sharing the PE range but avoids using the first several positions to avoid the attention sink problem (59]. We find that Graph-KV remains unaffected even though its chunks share the PE range from the first token. This is because we adopt the model that has been fine-tuned with independent attention blocks 33 to fit this change.
4 Experiments
Task Selection We design four tasks to evaluate Graph-KV, including three real-world applications and one stress test: Task 1: Aunmeeval-Angmmnneed Generation (RAG), Task 2: ARXIV-QA, a new task of multi-hop paper understanding, Task 3: Paper topic classification, which is a classical graph learning task; Task 4: Stress test on scalability and efficiency over synthetic data.
Backbone for Graph-KV. Graph-KV necessitates the independent encoding of different text seg- ments. This process introduces a distributional shift standard LLM backbones (3). Two primary solutions address this challenge. The first involves applying tuning-free heuristic, such as APE (61, which alleviates the shift by adjusting the temperature and scaling of attention weights. The second approach is to post-train the model with attention masks composed of independent attention blocks for different text chunks, such as RAG [35]. Empirically, we found that the fine-tuned model exhibits more stable performance, particularly when employing Graph-KV, as demonstrated in subse- quent experiments. Consequently, we default to using the 11ama-3. 3. 1-11--88blllce ft (BB-llock) model the backbone for Graph-KV. This model is based on the pre-trained 1lama-3 3. 1-8B and is further post-trained with independent attention blocks (35) on the tulu-3 dataset 28 and 20k RAG training instances from 2Wiki [17] and TriviaQA (22]
Due to limited computational resources, our work focuses on the 1lama-3. 3. family, and we have not extended this specific tuning to other L.MMs. However, our findings are, in principle, generalizable. Furthermore, we did not attempt to directly fine-tune the model with Graph-KV, although we believe such a step could further enhance its performance on many of the tasks discussed later.
5

---

Inference
Bring--Comarisn
dizkera docuraar it of Sive Nend
Paragrahh A:FAQ livqunitly
Asked Quolisen is fozare- kngl
Peregroph B: The Rig Mancy dioced by Jahn Palkly Cantain
dystpiin cauris wnficen ond diccted by Cartee stam and rieaerr...
Query: Are direttr fike FAQi Froqpeatly The Big Nangy ane eunty?
Peragripk B: The first Notod Princ Papiio
wus averted to phonuess thstre Hiteage
Phessragh Br John Fuddy
Candaiis wos prolite
Phregraph C: Carles Alanns 2. Axponki fin dratter
Quwess siu got first mobel prite plapica
Paragraph Comparison
Chunks Long
Compositional
July is,
Paragraph
Panggaah Ac Verua (Verseo) a the diffatze of lidtin. ooe zitt frander Glasel Docstell
Asserio
Paragroph BI
Aireoker...
Paregraph
10, 1978)
Detectiie Nowel: The Sour Rusel
Parasiigh II
Paregrigh B: Crnssl Verseer.. Venmor waa ther and biled resade
Beriored Phrggragh Chankas
Was vatuasing
Querry Fless try to doller the the varyy foned on the Tocaiiiiicee Cascatlyy bepom Whokklee Exdea Harkerde in todasiin?
Qsepp founder Navar
Figure 4: The reasoning settings in RAG tasks. Direct inference task requires identifying evidence chunks (from NarrativeQA (55) ). Others that require multi-hop reasoning include multi-hop reasoning (comparison, bridge and compositional (from 2Wiki [17], HotporQA (62] ) and bong-docmment understanding (from LongBench-v2 ( In these tasks, there exists implicit temporal logical dependencies among the retrieved chunks.
Baselines for comparison. 1) Sequential Encoding: We consider two models which conducts serial- ized next-token prediction during post- tra-ttraning based on 1lama-3 3. 1-88. One is 11ama-3. 1-81-stt tff (8B-SFT) which is fully supervised tuned on the tulu-3 dataset. For fair comparison, we also take 1lama-3. 3. 1-g (BBRAG), which is further tuned with the extra RAG data that used for 1lama-3. 10mma-3.--B---- 1--8---lock- ft (8B-Block), which were also used for comparison in [35] The two models encode inputs standard serialized manner, serving as direct baselines for Graph-KV, particularly in assessing its ability to leverage structural inductive biases, eliminate positional bias, and reduce context window consumption. 2) Parallel Context Window (PCW) (43), 3) Adap- tive Parallel Encoding (APE) 661) and 4) Block-RAG [35] are methods with block attentions. Block-RAG serves as another direct baseline for Graph-KV KV as they adopt the same backbone LLM.
4.1 Task 1: Retrieval Augmented Generation (RAG)
Examples of the task scenarios in RAG are shown in Fig. including direct inference, multi-hop reasoning, and long document understanding. We evaluate these scenarios us- ing a total of datasets, including NarrativeQA (5). Trivi- aQA (22), HotpotQA (62), 2Wiki [17], Multihop-RAA RAG [4]. MorehopQA 4d and LongBench [4] For all the datasets, 10 text chunks are provided, and accuracy is selected as the
with Staelbrity Sparce
Grogle Madi
primary metric. We follow [35] 33 1 to judge whether any
Figure 3: Graph-KV modeling for RAG.
correct answers appear in the predicted output. See more implementation details in Appendix. 1
Graph-KV for Structure Modeling in RAG. In RAG tasks, especially those involving multi-hop reasoning, text segments exhibit strong logical or temporal structural inductive biases. However, these dependencies are implicit and could not be cheaply modeled. We do not assume the dependencies are explicit, instead we construct them using a bipartite graph of text chunks. As illustrated in Fig. 3 Graph-KV KV tries to capture the structural dependencies among retrieved chunks without introducing too much complexity. Specifically, the retrieved chunks with the top-m (m==1,3 in our experiments) similarity scores are considered source chunks, the KV-cache them is concatenated, and attended by each of the remaining text chunks to independently generate the corresponding KV values. We also consider all retrieved chunks as both source and target chunks (named as "Graph-KV-Full) which can be viewed modeling all potential wair-wisc dependencies.
Result Analysis. Experiment results on RAG datasets are displayed in Tables with key insights as follows: Across all the tasks, results show a clear trend: Graph- -V-lll generally outperforms its sparsified variants. Specifically, Graph-KV. KV-Top-3 generally achieves better performance than m=1. Among them, the Graph-KV-Top outperforms the Block-RAG 331 baseline except on Single Document QA while -roph-KV-Top-3 consistently outperforms Block-RAG across all cases, which reveals that our injected sparse dependency effectively complements the lack of dependencies among text chunks in parallel encoding methods. Notably, in tasks that emphasize multi-hop reasoning, or medium and long reasoning from long documents (Table. 2). Graph- Craph-KV-Ton KV-T---3 significantly

---

MonillepRAA RAG
MewhoyOA
Single Theamen QA in Inghlngginbb/e
Infer
Cumpue
Vemppraa
Nall
Avg
Hep--1
Dop-2
Hop-3
Hup-4
1kp-5
A+g
EBay
Fard
Short
Malian
Lang
Avg
Buckoree
-44
91
24
18-SFT
Segaential
42.56
31.49
31.37
04.34
35.15
5765
34.27
24.57
15.36
26.37
36.37
35.8
26.8
35.1
31.2
20.8
31.4
38-SFT
PCW
09:39
34.29
34.35
47.10
43.01
11.3 1:256
10.11
10:38
01101
17.5%
13:35
K.1
20.0
15.8
21.0
0.0
15.6
13.74
61.55
10.9%
21.4
261
20,0
90-KAG
Seapanniall
23,02
3466
3600
43.33
34.23
56.72
12.59
22.00
$3.85
25.37
35.36
32.8
12.4
56.1
35.1
16.7
12.5
1B-KAL
FCW
50377
3082
54.19
48.15
99.35
0.22
1.20
0.00
0100
1.00
1852
16.7
27.1
202
219
9.5
25.3
18.3 88-
APE
51.71
3405
35.05
35.97
40.10
22.97
27.88
163.2
46.15
$2.96
24.55
2500
19.4
10.5
318
16.7
21.3
Block
25.50
23.07
30.76
36.5
20,8
38-Slbck
Black-RAG
72.75
54.15
19.01
40.71
43.33
56.33 71
38.72
28.67
15.16
37.47
13.91
17.5
17.9
122
38.1
16.3
114
S8-Biack
GapboXV Tip-1
73,25
54.10
36.08
53.85
48.61
54.72
18.72
34.67
23.07
11.86
17.00
64.9
37.0
X2.9
28.6
25.0
79.9
Block
Gugh KV Top-3
73.02
34,43
35,69
63164
45:79
56.53
25.72
34.07
23.07
20:67
35.33
30.51
29.5
22.4
35.7"
33.1
32.5
Black
Gugh
3463
35,45
46.410
64.867
38/76
31.51
50.4
35.1
35331
Table 2: Performance on Multhhop-AAGi [49].
MorehopQA [44] and single documentQA in LongBench-V V2 [4].
The best sequential encoding method is underlined, the best non-sequential approach is bolded. f refers that the
best non-sequential approach outperforms the best sequential encoding.
NarrativeQA
2Wiki
TriviaQA
Hotpol QA
Infer
Compare
Infer
Bridge
Compose
Avg
Infer
Compare
Bridge
Avg
Buckbone
Atlention
3610
3040
1549
2751
5236
12576
11313
1487
5918
7405
8B-SFT
Sequential
60.60
86.84
24.66
74.62
67.20
74.37
73.42
8B-SFT
PCW
39.22
70.13
14.07
67.17
32.58
46.94
60.13
54.87
33.28
37.62
8B-SFT
APF.
49.05
74.44
18.26
61.17
37.41
49.20
66.28
60.52
46.24
49.11
8B RAG
Sequential
62.18
82.29
60.94
90.54
68.22
75.75
76.38
73.43
78.59
77.55
SB-RAG
PCW
46.59
66.21
72.88
19.49
42.37
33.51
8B-RAG
APE
49.14
74.40
21,88
84.55
29.96
51.65
67.31
63.34
42.41
46.61
8B-Block
Soqueatial
63.21
84.24
63.08
90.07
70.26
77.29
76.64
71.88
78.82
27.43
8B- Block
Block-RAG
59.39
83.25
50.41
89.85
60.90
71.35
74.44
70.20
71.59
71.31
Sn. Block
Graph. KV Top-1 I
82.76
52.42
90.00
73.60
75.17
70.41
74.14
73.39
8B Block
Graph KV 3
62.29
83.25
56.74
90.47
67.83
75.15
75.
71.01
76.24
75.19
SB-Block
Graph KV Full
62.88
82.69
54.16
90.43
67.11
70.41
77.62
76.17
Table 3: Performance on NarrativeQA (25). 2Wiki [17]. TriviaQA (22) and HotpoiQA 662]. The best sequential
encoding method is underlined, the best non-sequential approach is bolded. refers that the best non-sequential approach outperforms the best sequential encoding.
outperforms Sequential Encoding by about 2% 10%. In the rest tasks (in Table. 3 although the gaps are generally narrower HotpotQA, 6.93% in compose on 2Wiki). Graph-KT Mithh-KV-Toe --Top-3 only achieves performance comparable to, but not exceeding, the sequential baseline. This is because, in many tasks in Table. such as inference and comparison (e.g. Narrative (25). TriviaQA (22))) models can often directly infer from one text chunk. In the tasks that require two-hop reasoning, such as bridge or compose, sequential encoding may model structural dependencies that are originally held in the serialized order.
still outperforms Block-RAG by 4.65% in bridge on
Regarding tuning-free approaches, although APE 61 consistently outperforms PCW [43 due to its temperature and scale adjustments, substantial performance gap remains between the tuning-frre approach APE and the fine-tuned model Block-RAG. This reveals the need for fine-tuning to enable LLMs that were pretrained on full causal attention to effectively encode text chunks independently and decode properly from these text chunks.
To evaluate the applicability of Graph-KV general LLMs, we take Llama- 3.B..B...BBBBB 1-BB-SFFT as the backbone and provide detailed results in Appendix. A.T While we observe a performance decline compared with the 8B-Block backbone due distribution shift in the absence of post-training with block-wise attention, Graph-KV still outperforms the other parallel encoding baselines. Furthermore, as demonstrated in Appendix. A.1.2 employing multi-hop graph construction with Graph-KV yields additional performance improvements.
4.2 Task 2: ARXIV- Multi-Hopp Reasoning over Citation Network with Full Texts
Experimental Setup. We randomly selected 100 academic papers from the Arxiv dataset [20), each with its corre- sponding reference papers. Following a data processing and cleaning phase, which focused on the relationships between the primary paper and its references (detailed in Appendix A.2.2), we curated final dataset comprising 60 primary papers. Including their references, this dataset encompassed total of 472 papers with full-text availability. We then formulated one technical question for each of the 60 papers. Answering these questions necessitates: 1) inter-
Sequence Lergth
Hfmber Tokeess
Graph KV
200
15.0
Number of Distractors
Figure 7: Average input sequence length (equivalent to position index range in se- quential encoding) on ARXIV-QA with 0, 1, 2 distractors, compared to the position index range used in Graph-KV.
7

---

Reada Baay Goscata
Opanal Locile Repistiical Senoe
Syices
Assnzr: Ciasc
Altunigg Liuur Crids enk Faeuee
Local Codo
Quenry hypeen Tyrku iiveayy and war frpotubily poe Cipeats Syrnee Jore tecembbl reept prrfenene setereeeeeee offerm peppr Provcctte
pape
Figure 5: An example from the ARXIV-QÁ task. One needs first locate the central paper's introduction of the row-weight generator matrix, and then compare the described methods with the content across all provided
references (e.g., Theorems and 3 in the ground-truth reference paper) to arrive at the correct answer.
8B BB-FFT-SE
#7:27
#/:2
4B SF ++PE
86 RAG+SE0
8/:3 2:25
86 RAC-APE
f7:4
3B bock&llock
8B BlockkGraphhe
8/:27
8B SET+SEO FES00Firrss First
8/:9
First Craee
irst
RACH le
Irst ( FLGIFL RAC+Latt
Bock GraphKy
FLrSt
BBCK Lock MC
Figure 6: QA accuracy when querying with 1, distractors (up to down) on the 60 questions from ARXIV- QA. The number of correct answers provided after v. 'SEQ' refers sequential encoding. Green entry and Red refers to wrong. When querying with distractors, 'Last' and 'First' refers to the
means correct position where the paper along with references that are contain the answer are positioned (at beginning or end of the sequence).
preting the main context of the paper, 2) comprehending the citation relationships, and 3) understanding the context of its references. An illustrative example is provided in Fig. 55 (note: the figure size has been significantly reduced due space constraints; readers encouraged zoom in for detailed content). On average, addressing each question involves processing approximately 88k tokens of context, which approaches the 1 128k effective context window limit of the foundational models used.
To further elevate the difficulty of the question-anse answering task, we introduced distractors for each question. This was achieved by randomly grouping multiple papers along with their respective references. This expanded setup enables the evaluation the model's positional bias (e.g.. by varying the placement of the relevant paper and its references within the paper sequence) and rigorously tests the boundaries of extremely long contexts. For instance, grouping three papers and their references (i.e., relevant paper plus two distractor papers, along with all their associated references) results in an average input length of 264.6k tokens. Fig. 7 provides a comparison.
Graph-KV for Structure-Aware Modeling in ARXIV-QA. Understanding technical details in paper often involves reviewing its references, particularly when methods in the references are adapted to solving the problem in the current work. Graph-KV forms target-source pairs connecting the central paper with all its references. When distractors are included and text length surpasses 128k tokens, the shared PE strategy is vital for the LLM properly digest the full context.
Result Analysis. Fig. 6 displays the QA accuracy. When queried solely with the paper and its references containing the answer (without distractors), sequential encoding demonstrates strong performance in this straightforward scenario. However, parallel text encoding baselines (PCW, APE, and Block-RAG) fail to capture cross-document connections, resulting in significantly fewer correct answers. the setup including distractors, sequential encoding exhibits severe positional bias. When the relevant paper is placed at the end of the sequence, performance remains comparable
8

---

to Gvaph-KV, primarily due to the recency bias of pre-trained auto regressegeee LLMs, which tend to focus more on aater-positione text chunks [58]. Conversely. when relevant texts are positioned at the beginning of the sequence, the distractors and extended contexts lead to substantial performance degradation. For instance, all sequential encoding baselines fail to answer correctly when queried with two distractors. This demonstrates the limitations of sequential encoding in long-context, multi- source structured reasoning. Due to its PE sharing strategy and structural inductive bias injection, Graph-KV does not suffer from the positional bias and consistently achieves the best performance.
4.3 Paper Topic Classification
We further evaluated Graph-KV on the paper topic classification task using the Cora [36] and Pubmed [45 citation graphs. This task, which orig-
Backbone 8B-SFT
Attention Sequential
Cora
Pubmed
66.6620.62
80.64+0.39
8B-SFT
PCW
68.63
76.95
8B-SFT
APE
66.92
77.01
inated from graph learning as 'node classification", requires LLMS to classify central paper into one of several categories based on its abstract, title, and neighbors. See Appendix, [A.2.3] for details. Each
8B-RAG
Sequential
70.35 17
82,06+0.16
8B-RAG
PCW
66.05
76.52
8B-RAG
APE
68.46
76.49
88 3H-Block
Query-Only
57.38
83,60
8B-Block Block
Sequential
67. 07.09+0.1 17
79. 19.79+0.16
central paper may have hundreds of references (e.g. up to 130 in Pubmed), thus making the task chal- lenging. To verify the effectiveness of including reference information, we added a 'Query-Only' baseline that only feeds the model the central paper. For all methods, the central paper was consistently placed at the end of the sequence. Since Sequential encoding and Block RAG showed varying performance depending on the order of references placed before the central paper, we report their average performance across seeds 42 to 44. In contrast, Graph-KVV is robust to the order of references. The results, presented in Table show that by incorporating the dependency on references from the central paper, Graph-KV outperforms both sequential encoding and parallel text encoding baselines. is important to note that existing works applying LLMs to this traditional graph learning task typically either perform classification in the text embedding latent space
8B-Block
Block-RAG
69 90.55++0.00
83, 13.24+1.16
8B-Block
Graph-
71.03
84.61
Table 4: Performance on paper topic classification.
Sequential encoding and Block-RAG produce varied answer due to different placement order of references. 'Query-Only means only providing the central paper.
32 8 or train an adapter
to map sampled reference papers into the LLM's token space 6
48 52]. Graph-KV is the first
approach to address this task by adjusting the fundamental mechanism of LLMs.
4.4 Task 4: Stress Test on Scalability & Efficiency
We conduct stress test synthetic data with Nvidia RTX6000 GPU (48GB) with AMD EPYC 7763 64-core processor, to compare Graph-KV with sequential encoding baseline on scalability and ef- ficiency. For details, refer to Appendix. A.2.4 1) We construct synthetic star graphs (similar to the ego graphs used previous tasks) with fixed word number on each node of 500 and 1000. We then gradually increase the number of neighbors to as- sess GPÚ peak memory usage and report the remaining available memory. Results are presented on the left side of Fig. Graph-KV capable of encoding more than times the number of neighbors compared with sequential encoding. 2) To evaluate efficiency, we report the time-to-firss first-tookknn (TTFT) latency on star graphs with fixed 10 neighbors, varying the number of words per node from 100 to 800. The results are shown on the right side of Fig. [ The benefit stems from pre-filling text chunks with injected structural biases, a capability not achievable with sequential encoding.
500
Hun telioon
suni Vide
Figure 8: Left: Memory left w.r.t. num of nodes encode. Right: TTFT w.r.t. num words per node.
5 Conclusion and Future Work
This paper introduces Graph-KV, novel approach designed to overcome the limitations of auto- regressive LLMs processing structured data. It achieves this by directly injecting structural inductive biases into the attention mechanism and employing strategic positional encoding, which in turn reduces positional bias and context window demands. Evaluations across diverse tasks, including RAG, new academic QA benchmark (ARXIV-QA), and paper topic classification, demonstrate

---

Graph-KV's substantial outperformance of sequential and parallel encoding baselines, particularly in multi-hop reasoning and long-con cong-context scenarios. Although this work currently evaluates Graph-KV on one-hop structural dependencies, the core idea of leveraging structural dependencies to improve I.M understanding of more intricate data topologies holds significant promise for broader research.
Acknowledgements
H. Wang. M. Li, S. Liu, S. Miao and P. Li are partially supported by NSF awards IIS-2239565, CCF-2402816, IIS-2428777, PHY-2117997, DOE award DE-FOA-0002785, JPMC faculty awards; Openai Research Credits; and Meta research award.
We extend our sincere gratitude to Xinyu Yang and Beidi Chen for their valuable discussion.
References
[1] Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, lige Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al. Gpt-4 technical report. arXiv preprint vrXiv:2303.08774, 2023.
[2] Jinze Bai, Shuai Bai, Yunfei Chu, Zeyu Cui, Kai Dang, Xiaodong Deng, Yang Fan, Wenbin Ge, Yu Han, Fei Huang, et al. Qwen technical report. arXiv preprint arXiv:2309. 16609, 2023.
[3] Yushi Bai, Xin Lv, Jiajie Zhang. Hongchang Lyu, Jiankai Tang, Zhidian Huang, Zhengxiao Du, Xiao Liu, Aohan Zeng, Lei Hou, Yuxiao Dong, Jie Tang, and Juanzi Li. LongBench; A bilingual, multitask benchmark for long context understanding. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume I: Long Pupers),
pages 31 19-33137, 2024.
[4] Yushi Bai, Shangqing Tu, Jiajie Zhang, Hao Peng. Xiaozhi Wang, Xin Lv, Shulin Cao, Jiazheng Xu, Lei Hou, Yuxiao Dong, et al. Longbench v2: Towards deeper understanding and reasoning on realistic long-context multitasks. arXiv preprint arXiv:24/2. 15204, 2024.
[5] Nuo Chen, Yuhan Li, Jianheng Tang, and Jia Li. Graphwiz: An instruction-followin language model for graph problems. arXiv preprint 2XXx:22422.16029 2024.
[6] Runjin Chen, Tong Zhao, Ajay Jaiswal. Neil Shah, and Zhangyang Wang. Llaga: Large language and graph assistant. arXiv preprint arXiv:2402.081770 2024.
[7] Zhikai Chen, Haitao Mao, Jingzhe Liu, Yu Song, Bingheng Li, Wei Jin, Bahare Fatemi, Anton Tsitsulin, Bryan Perozzi, Hui Liu, et al. Text-space graph foundation models: Comprehensive benchmarks and new insights. arXiv preprint urXiv:2406.10722 2024.
[8] Eli Chien, Wei-Cheng Chang, Cho-Jui Hsieh, Hsiang-Fu Yu, Jiong Zhang, Olgica Milenkovic, and Inderjit S Dhillon. Node feature extraction by self-supervised multi-scale neighborhood prediction. arXiv preprint arXiv:2111.00064 2021.
[9] Tri Dao. Flashattention-2: Faster attention with better parallelism and work partitioning. arXiv preprint arXiv:2307.0869/ 2023.
[10] Bahare Fatemi, Jonathan Halcrow, and Bryan Perozzi. Talk like a graph: Encoding graphs for large language models. arXiv preprint arXiv:2310.04560 2023.
[11] Yunfan Gao, Yun Xiong, Xinyu Gao, Kangxiang Jia, Jinliu Pan, Yuxi Bi, Yixin Dai, Jiawei Sun, Haofen Wang, and Haofen Wang. Retrieval-auumennte generation for large language models: 2:1, 2023.
A survey. arXiv preprint 2rXiv:23/2.1099
[12) In Gim, Guojun Chen, Seung-seob Lee, Nikhil Sarda, Anurag Khandelwal, and Lin Zhong. Prompt cache: Modular attention reuse for low-latency inference. Proceedings of Machine Learning and Systems, 6:325-338, 2024.
[13] Aaron Grattafiori, Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Alex Vaughan, et al. The llama 3 herd of models. arXiv preprint arXiv:2407.21783, 2024.
10

---

[14] Steven A Greenberg. How citation distortions create unfounded authority: analysis of a citation network. Bmj, 339, 2009.
[15] Xiaobo Guo and Soroush Vosoughi. Serial position effects of large language models. arXiv preprint arXiv:2406. 15981, 2024.
[16] Adi Haviv, Ori Ram, Ofir Press, Peter Izsak, and Omer Levy. Transformer language models without positional encodings still learn positional information. In Findings of the Association for Computational Linguistics: EMNLP 2022, pages 1382- 1390, 2022.
[17] Xanh Ho, Anh-Khoa Duong Nguyen, Saku Sugawara, and Akiko Aizawa. Constructing a multi-hop qa dataset for comprehensive evaluation of reasoning steps. arXiv preprint arXiv:2011.01061 2020.
(18) Yupeng Hou, Junjie Zhang, Zihan Lin, Hongyu Lu, Ruobing Xie, Julian McAuley, and Wayne Xin Zhao. Large language models are zero-shot rankers for recommender systems, In European Conference on Information Retrieval, pages 364-381. Springer, 2024.
[19] Cheng-Ping Hsieh, Simeng Sun, Samuel Kriman, Shantanu Acharya, Dima Rekesh, Fei Jia, Yang Zhang, and Boris Ginsburg. Ruler: What's 's the real context size of your long-com conecconextt language models? arXiv preprint arXiv:2404.06654, 2024.
[20] Weihua Hu, Matthias Fey, Marinka Zitnik, Yuxiao Dong, Hongyu Ren, Bowen Liu, Michele Catasta, and Jure Leskovec. Open graph benchmark: Datasets for machine learning on graphs Advances in neural information processing systems, 33:221 18-22333, 2020.
[21] Gautier Izacard and Edouard Grave. Leveraging passage retrieval with generative models for open domain question answering. arXiv preprint arXiv:2007.01282, 2020.
[22] Mandar Joshi, Eunsol Choi, Daniel Weld, and Luke Zettlemoyer. Triviaqa: A large scale distantly supervised challenge dataset for reading comprehension. arXiv preprint arXiv:1705.0355/ 2017.
[23] Jared Kaplan, Sam McCandlish, Tom Henighan, Tom B Brown, Benjamin Chess, Rewon Child, Scott Gray, Alec Radford, Jeffrey Wu, and Dario Amodei. Scaling laws for neural language models. arXiv preprint XxXx:20001.0861,, 2020.
[24] Amirhossein Kazemnejad, Inkit Padhi, Karthikeyan Natesan Ramamurthy, Payel Das, and Siva Reddy. The impact of positional encoding on length generalization in transformers. Advances Neural Information Processing Systems, 36:24892-244444 24928, 2023.
[25] Tomáš Kočiský, Jonathan Schwarz, Phil Blunsom, Chris Dyer, Karl Moritz Hermann, Gábor Melis, and Edward Grefenstette. The narrativeqa reading comprehension challenge. Transac- tions of the Association for Computational Linguisties, 6:317-328, 2018
[26] Lecheng Kong, Jiarui Feng. Hao Liu, Chengsong Huang, Jiaxin Huang. Yixin Chen, and Muhan Zhang. Gofa: A generative one-for-all model for joint graph language modeling. arXiv preprint 2xXiv:2407.09709 2024.
[27] Yuri Kuratov, Aydar Bulatov, Petr Anokhin, Ivan Rodkin, Dmitry Sorokin, Artyom Sorokin, and Mikhail Burtsev. Babilong: Testing the limits of lims with long context reasoning iaaiiiin--------ttttaaaa -aasthaastack. In Advances in Neural Information Processing Systems, pages 106519-106554, 2024.
[28] Nathan Lambert, Jacob Morrison, Valentina Pyatkin, Shengyi Huang, Hamish Ivison, Faeze Brahman, Lester James V Miranda, Alisa Liu, Nouha Dziri, Shane Lyu, et al. T) ulu 3: Pushing frontiers in open language model post-training, arXiv preprint arXiv:2411.15124 2024.
[29] Patrick Lewis, Ethan Perez, Aleksandra Piktus, Fabio Petroni, Vladimir Karpukhin, Naman Goyal, Heinrich Küttler, Mike Lewis, Wen-tau Yih, Tim Rocktäschel, generation for knowledge-intent intensiveee nip tasks. Advances in neural information processing systems, 33:9459 9474, 2020.
Retrieval-augmennt
[30] Huayang Li, Yixuan Su, Deng Cai, Yan Wang, and Lemao Liu, survey on retrieval-augmennted text generation. arXiv preprint 20110022022011100, 2022.

---

[31] Yuhan Li, Peisong Wang, Zhixun Li, Jeffrey Xu Yu, and Jia Li. Zerog: Investigating cross- dataset zero-shot transferability in graphs. In Proceedings of the 30th ACM SIGKDD Conference on Knowledge Discovery and Data Mining, pages 1725-1735, 2024.
[32] Yuhan Li, Peisong Wang, Xiao Zhu, Aochuan Chen, Haiyun Jiang, Deng Cai, Victor W Chan, and Jia Li. Glbench: A comprehensive benchmark for graph with large language models. Advances in Neural Information Processing Systems, 022422244423664 2024.
[33] Nelson F Liu, Kevin Lin, John Hewitt, Ashwin Paranjape, Michele Bevilacqua, Fabio Petroni, and Percy Liang. Lost in the middle: How language models use long contexts. arXiv preprint arXiv:2307.03 172, 2023.
[34] Yao Lu, Max Bartolo, Alastair Moore, Sebastian Riedel, and Pontus Stenetorp. Fantastically ordered prompts and where to find them: Overcoming few-shot prompt order sensitivity. arXiv preprint arXiv:2104.08786, 2021.
[35] Dongyang Ma, Yan Wang, and Tian Lan. Block-attention for efficient prefilling. In The Thirteenth International Conference on Learning Representations, 2024.
[36] Andrew Kachites McCallum, Kamal Nigam, Jason Rennie, and Kristie Seymore. Automating the construction of internet portals with machine learning. Information Retrieval, 3:127-163, 2000.
[37] A Paszke. Pytorch: An imperative style, high- segh-perforaacce deep learning library. arXiv preprint arXiv:911.001703, 2019.
[38] Bryan Perozzi, Bahare Fatemi, Dustin Zelle, Anton Tsitsulin, Mehran Kazemi, Rami Al-Rfou, and Jonathan Halcrow. Let your graph do the talking: Encoding structured data for llms. arXiv preprint arXiv:2402.05862, 2024.
[39] Alexander Peysakhovich and Adam Lerer. Attention sorting combats recency bias in long context language models. arXiv preprint arXiv:2310.01427, 2023.
[40] Ofir Press, Noah A Smith, and Mike Lewis. Train short, test long: Attention with linear biases enables input length extrapolation. arXiv preprint arXiv:2108. 12409, 2021.
[41] Alec Radford, Karthik Narasimhan, Tim Salimans, Ilya Sutskever, et al. Improving language understanding by generative pre-training, 2018.
[42] Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, al. Language models are unsupervised multitask learners. OpenAl blog, 1(8):9, 2019.
[43] Nir Ratner, Yoav Levine, Yonatan Belinkov, Ori Ram, Inbal Magar, Omri Abend, Ehud Karpas, Amnon Shashua, Kevin Leyton-Browe Brown, and Yoav Shoham. Parallel context windows for large language models. arXiv preprint arXiv:22 10947, 2022.
[44] Julian Schnitzler, Xanh Ho, Jiahao Huang, Florian Boudin, Saku Sugawara, and Akiko Aizawa. Morchopqa: More than multi-hop reasoning. arXiv preprint arXiv.2406.13397 2024.
[45] Prithviraj Sen, Galileo Namata, Mustafa Bilgic, Lise Getoor, Brian Galligher, and Tina Eliassi- Rad. Collective classification in network data. Al magazine, 29(3):93-95 2008.
[46] Lin Shi, Chiyu Ma, Wenhua Liang, Weicheng Ma, and Soroush Vosoughi. Judging the judges: systematic investigation of position bias in pairwise comparative assessments by llms. arXiv preprint arXiv:2406.07791, 2024.
[47] Jianlin Su, Murtadha Ahmed, Yu Lu, Shengfeng Pan, Wen Bo, and Yunfeng Liu. Roformer: Enhanced transformer with rotary position embedding. Nenrocomputing. 127063, 2024.
[48] Jiabin Tang, Yuhao Yang, Wei Wei, Lei Shi, Lixin Su, Suqi Cheng, Dawei Yin, and Chao Huang. Graphgpt: Graph instruction tuning for large language models. In Proceedings of the 47th International ACM SIGIR Conference on Research and Development in Information Retrieval, pages 491-500, 2024.
12

---

[49] Yixuan Tang and Yi Yang. Multihop-rag: Benchmarking retrieval- augmented generation for multi-hop queries. arXiv preprint arXiv:2401.1539, 2024.
[50] Gemini Team, Rohan Anil, Sebastian Borgeaud, Jean- Baptiste Alayrac, Jiahui Yu, Radu Soricut, Johan Schalkwyk, Andrew M Dai, Anja Hauth, Katie Millican, et al. Gemini: a family of highly capable multimodal models. arXiv preprint arXiv:2312.1 1805, 2023.
[51] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez, Fukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017.
[52] Duo Wang, Yuan Zuo, Fengzhi Li, and Junjie Wu. Llms as zero-shot graph learners: Alignment of gnn representations with Ilm token embeddings. Advances in Neural Information Processing Systems, 37:5950-5973, 2024.
[53] Haoyu Wang, Shikun Liu, Rongzhe Wei, and Pan Li. Model generalization on text attribute graphs: Principles with large language models. arXiv preprint arXiv:2502.11836, 2025.
[54] Jie Wang. Tao Ji, Yuanbin Wu, Hang Yan, Tao Gui, Qi Zhang, Xuanjing Huang, and Xiaoling Wang. Length generalization of causal transformers without position encoding. arXiv preprint arXiv:2404. 12224, 2024.
[55] Yiwei Wang, Yujun Cai, Muhao Chen, Yuxuan Liang, and Bryan Hooi. Primacy effect of chatgpt. arXiv preprint arXiv:2310. 13206, 2023.
[56] Ziqi Wang, Hanlin Zhang, Xiner Li, Kuan-Hao Huang, Chi Han, Shuiwang Ji, Sham M Kakade, Hao Peng, and Heng Ji. Eliminating position bias of language models: A mechanistic approach. arXiv preprint arXiv:2407.00 100,0000000,,,, 2024.
[57] Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, et al. Huggingface's 's transform- ers: State-of-the-art natural language processing. arXiv preprint 190.07191, 2019.
[58] Xinyi Wu, Yifei Wang, Stefanie Jegelka, and Ali Jadbabaie. On the emergence of position bias in transformers. arXiv preprint 2XXv:2502.00951, 2025.
[59] Guangxuan Xiao, Yuandong Tian, Beidi Chen, Song Han, and Mike Lewis. Efficient streaming language models with attention sinks. arXiv preprint arXiv:2309. 17453, 2023.
[60] Haotong Yang. Xiyuan Wang, Qian Tao, Shuxian Hu, Zhouchen Lin, and Muhan Zhang. GI- fusion: Rethinking the combination of graph neural network and large language model. arXiv preprint arXiv:2412.06684 2024.
[61] Xinyu Yang, Tianqi Chen, and Beidi Chen. Ape: Faster and longer context-augmented genera- tion via adaptive parallel encoding, arXiv preprint arXiv:2502.0543) 2025.
[62] Zhilin Yang, Peng Qi, Saizheng Zhang, Yoshua Bengio, William W Cohen, Ruslan Salakhut- dinov, and Christopher Manning. Hotpotqa: dataset for diverse, explainable multi-hop question answering. arXiv preprint 17Xiv:1809009000 2018.
[63] Jiyy Yao, Hanchen Li, Yuhan Liu, Siddhant Ray, Yihua Cheng. Qizheng Zhang, Kuntai Du, Shan Lu, and Junchen Jiang. Cacheblend: Fast large language model serving for rag with cached knowledge fusion. In Proceedings of the Twentieth European Conference on Computer Systems, pages 90- 2025.
[64] Howard Yen. Long-context language modeling with parallel context encoding. Master's thesis, Princeton University, 2024.
[65] Tao Yuan, Xuefei Ning, Dong Zhou, Zhijie Yang. Shiyao Li, Minghui Zhuang, Zheyue Tan, Zhuyu Yao, Dahua Lin, Boxun Li, Guohao Dai, Shengen Yan, and Yu Wang. Lv-eval: A bal- anced long-context benchmark with length levels up to 256k. arXiv preprint 150. 2024.
13

---

[66] Zhenyu Zhang, Runjin Chen, Shiwei Liu, Zhewei Yao. Olatunji Ruwase, Beidi Chen, Xiaoxia Wu, and Zhangyang Wang. Found the middle: How language models use long contexts better via plug-and-play positional encoding. arXiv preprint arXiv:2403.04797, 2024.
[67] Penghao Zhao, Hailin Zhang, Qinhan Yu, Zhengren Wang, Yunteng Geng, Fangcheng Fu, Ling Yang, Wentao Zhang. Jie Jiang. and Bin Cui. Retrieval- -augmeetdd generation for ai ni-generated content: A survey. arXiv preprint arXiv:2402.19422
2024.
[68] Zihao Zhao, Eric Wallace, Shi Feng, Dan Klein, and Sameer Singh. Calibrate before use: Improving few-shot performance of language models, In International conference on machine learning, pages 12697-12706. PMLR, 2021.
[69] Lianmin Zheng, Wei-Lin Chiang, Ying Sheng, Siyuan Zhuang, Zhanghao Wu, Yonghao Zhuang, Zi Lin, Zhuohan Li, Dacheng Li, Eric Xing, et al. Judging llm-as-a-judge with mt-bench and chatbot arena. Advances in Neural Information Processing Systems, 36:46595 46623, 2023.
[70] Lianmin Zheng, Liangsheng Yin, Zhiqiang Xie, Chuyue Sun, Jeff Huang. Cody Hao Yu, Shiyi Cao, Christos Kozyrakis, Ion Stoica, Joseph E Gonzalez, et al. Sglang: Efficient execution of structured language model programs, 2024. URL https://arxiv. org/abs/2312.07104.
[71] Lianghui Zhu, Xinggang Wang. and Xinlong Wang. Judgelm: Fine-tuned large language models scalable judges. arXiv preprint arXiv:2310.1763// 2023.
[72] Yun Zhu, Jia-Chen Gu, Caitlin Sikora, Ho Ko, Yinxiao Liu, Chu-Cheng Lin, Lei Shu, Liangchen Luo, Lei Meng, Bang Liu, et al. Accelerating inference of sarieval-auumenter generation via sparse context selection. arXiv preprint arXiv:2405. 16100...117..... 2024.
[73] Yun Zhu, Haizhou Shi, Xiaotang Wang, Yongchao Liu, Yaoke Wang, Boci Peng, Chuntao Hong, and Siliang Tang. Graphclip: Enhancing transferability in graph foundation models for text-attributed graphs. In Proceedings of the ACM on Web Conference 2025, pages 2183-2197, 2025.
14

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The paper's contribution and scope covered in abstract and introduction.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
See Section. methodology and Section. Conclusion and Future Work for
details.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [NA]
15

---

Justification:
The paper does not include theoretical results.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Answer: [Yes]
Justification: Please refer supplementary materials for codes and implementation details.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution is primarily a new algorithm, the paper should make clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reprodueibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
16

---

Answer: [Yes]
Justification:
Data is publicly available. Code provided in supplementary materials.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://niis.. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https Cooeeeoodeesssseeeeee //nips.com / casssiinnccccyyc for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification:
See implementation details in Appendix.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented in the core the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: In scenarios that may involve randomness, at least three random seeds used.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
17

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
See in implementation details in Appendix.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question:
Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics http://aaarr...cccplalll/aaccaaa
Answer: [Yes]
Justification: Checked.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification:
To the best of our knowledge, there is societal impact if the work performed.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
18

---

The conference expects that many papers will be foundational research and not tied particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms monitor how system learns from feedback over time, improving the efficiency and accessibility of MI..
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Lieenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: All data, methods' license are explicit.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (c.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com com/datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
19

---

If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
The assets well-documentedd.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/mmoel as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question:
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
No crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
20

---

Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that if the LLM used only for writing, editing, or formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [Yes]
Justification: The work develops methodology for LLMs.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs any important, original, non-standard components.
Please refer to our LLM policy fattps://neuriie http://///////oofeeeeee///////// for what should or should not be described.
21

---

A Appendix
A.1 Additional Experiment Results
A.1.1
Applicability to General LLM
We apply Graph-KV to standard baselines. Graph-KV consistently outperforms all parallel baselines, shown in Table.
comparing it against the parallel encoding
MorehopQA
2Wiki
Attention
Hop-1
Hop-2
Hop-3
Hop-4
Hop-5
Avg
Compare
Infer
Bridge
Compose
Avg
PCW
11.26
10.81
10.38
0.00
17.58
11.35
70.13
13.07
67.17
32.58
46.94
APE
13.28
15.86
9.47
61.53
10,98
14.13
74.44
18.26
61.17
37.41
49.20
Block-RAG
13.96
13.94
9.74
15.38
13.32
72.17
15.17
68.01
35.54
48.99
Graph-KV Top-3
15.54
16.10
12.98
18.68
15.47
76.41
17.43
64.15
47.19
54.30
Table 5: Results with -.a---3.1-8B---
Multihop-Ran
HotpotQA
NarrativeQA
TriviaQA
Attention
Infer
Compare
Temporal
Null
Avg.
Compare
Bridge
Avg
Infer
Infer
PCW
69.39
34.29
34.35
42.10
42.01
54.87
33.28
37.62
39.22
60.13
APE
48.34
33.46
33.49
86.25
40.34
60.52
46.24
49.11
49.05
66.28
Block-RAG
49.28
33.54
33.76
41.86
38.41
$7.83
37.39
41.49
46.53
65.55
Graph-KY KV Top-3
67.00
35.14
34.76
42.35
51.44
51.08
69.47
Table 6: Results with Llama-3.1-8B-SFT.
A.1.2 Multi-Hop Graph-KV
We built multi-layer graphs from retriever relevance scores for iterative information propagation. The design of multi-hop propagation is as follows:
2- Hopo We design chain of (Top chunk) + (Top 2-4 chunks) - (Rest).
Iteration "Top 1" acts the source to update the KV of "Top 2-4".
Iteration 2: The updated "Top 2-4" then update the rest.
3-Hop: A deeper chain (Top (Top 2-3) - (Top 4-5) - (Rest) with three-step propagation.
Multihop- RAG
HotpotQA
Narrative(A
TriviaQA
Attention
#hop
Infer
Compare
Temporal
Null
Avg.
Compare
Bridge
Avg
Infer
Infer
Graph-KV Top-1
73.25
34,19
38.18
53.85
44.81
70.41
74.14
73.39
62.04
75.17
Graph KV T
71.01
Graph-KV Fall
69.04
34.63
38.48
88.79
46.41
70.41
77.62
76.17
62.88
75.85
Graph KV Top Top-3
73.20
34.54
38.78
70.82
46.15
71.95
77.25
76.19
62.60
75.90
Gruph KV Topl Top3 Top3-Top5 Top5
73.30
34.76
38.78
75.44
46.74
72.02
77.57
76.45
62.74
76.04
MorchopQA
2Wiki
Attention
#hop
Hop-1
Hop-3
Hop-4
Hop-5
Avg
Compare
Bridge
Compose
Avg
Graph-KV Top1
54.12
25.72
24.67
23.07
31.86
37.96
82.76
52.42
90.00
65.94
73.60
Graph-KV Top3
56.63
25.72
24.67
23.07
29.67
38.11
83.25
56.74
90.47
67.83
75.15
Graph_ KV Full
64.86
30.52
25.97
30.76
47.25
44.90
82.69
54.16
90.43
67.11
74.38
Graph-K KV Top1-Top3
67.11
32.69
25.32
30.76
37.36
45.70
83.45
57.04
90.77
68.97
75.76
Graph-KV KV Top Topp-Top3-Tar Tops
67.56
32.93
25.97
38.46
43.95
46.69
83,75
57.04
90.77
69.34
75.99
Table 7: Multi-Hop performance.
A.2 Implementation Details
Hardware and Platform
For all experiments involved in this study, the code implemented using PyTorch [37
HuggingFace Transformers library [57), and FlashArtention-2 9 As to hardware, for the task ARXIV-O QA, A the parallel text encoding baselines (Block-RAG. PCW, APE) and Graph-KV run on NVIDIA A100 Tensor Core GPUs, while the sequential encoding bascline runs NVIDIA A.00
22

---

Tensor Core GPUs, as it requires higher memory. For the other tasks, all the methods run on with NVIDIA RTX 6000 Ada GPUs.
Model Weights For all the experiments, we adopt the open-source weight of 11ama 1-8B-sfttt TAC and and 1lama-3. 1-1---BBBcck----11 Fofeeeerrsseeeessseesee by 35
1lama-3. 1-----88BAA
We do not further fine-tune the 1lama-3.. 1-8B with Graph-KV due to limited computational re- sources, although we believe that doing could further improve performance the experiments.
A.2.1 Implementation Details for RAG
Data Process and Evaluation For 2Wiki 17.. NarrativeQA 25 TriviaQA [22] MorehopQA 44
and HotpotQA 622 the data processing (the process to retrieve chunk and the evaluation pipeline) strictly follows Block-RAG [35 For Mulihop-RAse [49]. the data processing and evaluation follows the original implementatior Across all benchmarks, the top 10 text chunks retrieved based on similarity scores are included in the input prompt in ascending order with respect to the scores [35]. Following 335 18 we use accuracy as the metric, and evaluate whether the correct answer appears in the output. For all methods, the output is constrained to maximum of 256 tokens.
Prompt: For RAG tasks, the entire prompt input is divided into parts, namely Prefix, Text Chunks, and Question, with each formatted as follows:
Prefix: To ensure fair comparison, all the methods adopt the same prefix as follows:
You intelligent AI assistant. Please answer questions based the user 's instructions. Below some reference documents that may help you in answering the user\'s question.
Text Chunks:
The format for each text chunk (10 chunks total for each question) is as follows:
-Title: (Title #1). An (Text #1)
-Title: (Title #2}. An (Text #2}
-Title:
(Title #10). An (Text #10}
Question: All the methods adopt the same question format as follows:
For 2Wiki [77, HotpotQA 662. NarrativeQA 225 and TriviaQA 22], the question prompt follows
those used in 35
Please write high-quality
for the given question using only the provided
search documents (some of which might be irrelevant). Question: (Question)
For MultiHop-QA we adopt the prompt from the original implementation, which is as follows:
Please write a high-quality answer for the given question using only the provided search documents, The answer to the question is word or entity. If the provided information is insufficient to answer the question, respond Insufficient Information'. Please finally give your answer started with: 'The answer is: Question: (Question)
For MoreHop- QA [44, the prompt also from the original implementation, which is:
Please write a high-quality answer for the given question using only the provided search documents. (If the answer is a date, format is as follows: YYYY-MM-DD ( ISO standard).) After thinking step by step, give your final ansver following Answer: An Question: (Question]
https://uuggingfacccoo htt.:h/gginnnaacc.o///s/iit/s/ss
23

---

Implementation
Sequential Encoding: Sequential method directly feeds the model with the sequence of Prefix Text Chunks + Question.
Parallel Encoding: independently encode the Prefix, each one of the Text Chunks, and Question, and then concatenate the KV cache together. The positional encoding setup follows the implementation used in the corresponding papers.
Graph-KV: independently encode Prefix and Question, while inject the structural inductive biases as introduced in Section. 4.1
A.2.2 Implementation Details for ARXIV-QA
Dataset Curation We initially sample 100 central papers along with their references from the OGBN- ARXIV [20] citation network. Using the Arxiv AP we download the PDF files for each paper and convert them to full text using the fitz library During data cleaning, we ensure that the correct papers are downloaded and that each contains at least three valid references. For each reference, if appears in standalone sentence in the central paper- paper-inditee indecinnii that the central paper uses least one sentence to compare or discuss the reference-we manually design a corresponding question. Through this process, 60 central papers with associated questions selected to form the ARXIV-QA task, which is publicly available Ff
Distractors When adding distractors, we also employ randoms seeds 42 - 44 to randomly sample distractors paper citation ego-graphs, but we do not observe different outputs across the methods with different seeds.
Prompt: For ARXIV-QA, the input prompt can be divided into parts, namely Prefix, Paper texts, Question:
Prefix:
To ensure fair comparison, all the methods adopt the same prefix follows:
You intelligent AI assistant. You will first read the related works of paper, then you will read the paper. Then answer the question.
Paper texts:
[Full Text of Reference a}, {Full Text of Reference b,,..., [Full Text of Reference k} \n'n Now please read the paper: {Full Text of Central Paper #1}
(if with distractors:)
(Distractor #1) (Full Text of Reference 1}, (Full Text of Reference m....., (Full Text of Reference s} \n Now please read the paper: (Full Text of Central Paper #2}
(Distractor #2) (Full Text of Reference t), (Full Text of Reference u)...., (Full Text of Reference y} An Now please read the paper: {Full Text of Central Paper #3}
Question:
To ensure fair comparison, all the attention methods adopt the same question follows:
Question: (Question)
Implementation
directly input the sequence of Prefix Paper Texts + Question. When distractors are included, the Paper Texts are repeated accordingly, while ensuring that each citation ego-graph remains intact, illustrated above.
Sequential Encoding:
html
See the zip file
24

---

Parallel Encoding: independently encode the Prefix, the full text of each reference and each paper, Question, and then concatenate the KV cache together. The positional encoding setup follows the implementation used in the corresponding paper.
Graph-KV: independently encode Prefix and Question, while inject the structural inductive biases following the method introduced in Section. 4.2
Demo Example Below display two examples of question of ARXIV-QA, and the corresponding answers generated by different attention methods. Full questions and ground truth answers could be found in
Demo Example #1
Question: In paper 'xLED; Covert Data Exfiltration from Air-Gapped Networks via Router LEDs', the authors describe method from another paper that introduces type of malware aimed bridging the air- gap between computers and a nearby mobile phone by exploiting FM radio signals emanating from the video card. You'l also read this paper. please provide the full name of the paper.
Ground Truth: AirHopper: Bridging the Air-Gap between Isolated Networks and Mobile Phones using Radio Frequencies
Without Distractor
The paper that introduces a type of malware aimed bridging the air-gap between computers and nearby mobile phone by exploiting FM radio signals emanating from the video card is titled AirHopper: Bridging the Air-Gap between Isolated Networks and Mobile Phones using Radio Frequencies.
8B-SFT+SEQ:
The paper that introduces a type of malware aimed bridging the air-gap between computers and nearby mobile phone by exploiting FM radio signals emanating from the video card is titled AirHopper: Bridging the Air-Gap between Isolated Networks and Mobile Phones using Radio Frequencies
8B-RAG+SEQ:
SB-Block-FT+SEO The paper that introduces type of malware aimed bridging the air-gap between computers and a nearby mobile phone by exploiting FM radio signals emanating from the video card is titled Airlopper: Bridging the Air-Gap between Isolated Networks and Mobile Phones using Radio Frequencies
The paper that introduces a type malware aimed at bridging the air- gap between computers and a nearby mobile phone by exploiting FM radio signals emanating from the video card titled COTTONMOUTH. An Asymmetric Subtle Software Attack by Mordechai Guri, Gabi Kedma, Assaf Kachlon, and Yuval Elovici.
B.-Block-FT-Bloc--RAe
8B-Block-FTs FaecckFF+Grrah-KTT The paper that introduces type of malware aimed bridging the air-gap between computers and a nearby mobile phone by exploiting FM radio signals emanating from the video card is titled: AirHopper: Bridging the Air-Gap between Isolated Networks and Mobile Phones using Radio Frequencies. Authors: Mordechai Guri, Gabi Kedma, Assaf Kachlon, Yuval Elovici.
zip file of supplementary material
25

---

With #1 Distractor
8B-SFT+SRQ-Finstt
The full name of the paper is xLED; Covert Data Exfiltration from Air-Gapped Networks via Router LEDss.
8B-SFT+SEQ-Last AirHopper: Bridging the Air-Gap between Isolated Networks and Mobile Phones using Radio Frequencies
SB-RAG+SEQ-Fins According to the provided information, the paper that introduces the malware that exploits FM radio signals emanating from the video card to bridge the gir-gap between computers and nearby mobile phone is xLEDD: Covert Data Exfiltration from Air-Gapped Networks via Router LEDs
8B-RAG+SEEQ-Last According to the provided information, the paper you're 're referring to is AirHopper: Bridging the Air- Gap between Isolated Networks and Mobile Phones using Radio Frequencies by Mordechai Guri, Yosef Solewicz, Andrey Daidakulov, and Yuval Elovici.
BB-BBock-FT+-SE--Fiist The paper you are referring to is titled Software-Defined Radio and the RF Fingerprints of Computersby Mordechai Guri, Yuval Elovici, and Boris Zadov.
DB-Block-FT+SEO-Laas The paper you referring is ÄirHopper: Bridging the Air- Gap between Isolated Networks and Mobile Phones using Radio Frequencieshy Mordechai Guri, K. Gabi, K. Assaf, and Yuval Elovici.
Baolocc-FT-BBooc-RAA
<end of text>
The authors of the 5. The 5. The 5. and the 5. The 5. The 5. and the The 5. The 5. The 5. The The
Be-BBlok-FF--BBocc-RA------
The paper that introduces type of malware aimed bridging the air-gap between computers and a nearby mobile phone by exploiting FM radio signals emanating from the video card is titled Airllopper: Bridging the Air-Gap between Isolated Networks and Mobile Phones using Radio Frequencies by Mordechai Guri, Gabi Kedma, Assaf Kachlon, and Yuval Elovici.
DB-Block-FT+Graph-KK
With #2 Distractors
8B-SFT+SEQ-Fire The full name of the paper is Learning to Bridge the Air-Gap between Isolated Networks and Mobile Devices using RF Modulation from the Video Card
SB-SFT+SEQ-Last xLED: Covert Data Exfiltration from Air-Gapped Networks via Router LEDs
8B-RAG+SEQ-Firrst: <end of text>
3B-RAG+SEQ-LLatt: <end text>
8--Block-FT-SEE--Fiitttccc of text>
8B-BBlck-FT--SOO--Laattcc.l. cend of text>
80-Bhock-FT--Blod--AA---iii Null
9B--Blck--F1--Booc--AA-----s- Null
BB-Block-FT++Graa---KY The paper that introduces a type of malware aimed bridging the air- between computers and a nearby mobile phone by exploiting FM radio signals emanating from the video card is: AirHopper: Bridging the air-gap between isolated networks and mobile phones using radio frequencies by Mordechai Guri, Gabi Kedma, Assaf Kachlon, and Yuval Elovici.
26

---

Demo Example #2
In paper 'Fast Multi-frame Stereo Scene Flow with Motion Segmentation' they directly adopt an edge detector, which originates from another paper that you' read. Provide the full name of that paper.
Question:
Ground Truth: Fast Edge Detection Using Structured Forests
Without Distractor
The edge detector adopted in the paper 'Fast Multi-frame Stereo Scene Flow with Motion Segmentation' originates from the paper titled Fast Edge Detection Using Structured Forests by Piotr Dollár and C. Lawrence Zitnick.
8B-SFT+SEQ:
The paper Fast Multi-frane Stereo Scene Flow with Motion Segmentation by Tatsunori Taniai, Sudipta N. Sinha, and Yoichi Sato directly adopts an edge detector from the paper Fast Edge Detection Using Structured Forests by Piotr Dollár and C. Lawrence Zitnick.
8B-RAG+SEQ:
:B-B:ock-FT+SEQ: According to the paper Fast Multi-frame Stereo Scene Flow with Motion Segmentation by Tatsunori Taniai, Sudipta N. Sinha, and Yoichi Sato, they directly adopt an edge detector from the paper Fast Edge Detection Using Structured Forests by Piotr Dollár and C. Lawrence Zitnick.
3B-BBock-FT-BBlcc-RAAG The edge detector adopted in the paper Fast Multi-frame Stereo Scene Flow with Motion Segmentation is the Census Transform, which is robust and efficient edge detection method. The Census Transform a parammamettic image matching technique that was first introduced by Zabih and Woodfill in their paper Non- parametric Local Transforms for Computing Visual Correspondence (Zabih and Woodfill, 1994).
8B-Block-FTs SBlock-FT+Grann Graph-KV: The paper Fast Multi-frame Stereo Scene Flow with Motion Segmentation directly adopts an edge detector that originates from the paper Fast Edge Detection Using Structured Forests by Piotr Dollár and C. Lawrence Zitnick.
27

---

With #1 Distractor
8B-SFT+SEQ-Finstt
The edge detector adopted the paper 'Fast Multi-frame Stereo Scene Flow with Motion Segmentation' is Dollár and Zitnick's Fast Edge Detection Using Structured Forests (DOI: 2011009PAMM..215.24555
SB-SFT+SEQ-Lase The edge detector adopted in the paper 'Fast Multi-frame Stereo Scene Flow with Motion Segmentation' is the Fast Edge Detection Using Structured Forests by Piotr Dollár and C. Lawrence Zitnick.
DB-RAG+SEQ-Firstt According the supplementary material of the paper Fast Multi- frame Stereo Scene Flow with Motion Segmentation by Tatsunori Taniai, Sudipta N. Sinha, and Yoichi Sato, they directly adopt edge detector from the paper Fast Edge Detection Using Structured Forests by Piotr Dollár and C. Lawrence Zitnick.
SB-RAG+SEQ-Laas According to the paper Fast Multi-frame Sterco Scene Flow with Motion Segmentation by Tatsunori Taniai, Sudipta N. Sinha, and Yoichi Sato, the edge detector they adopted is from the paper Fast Edge Detection Using Structured Forests by Piotr Dollár and C. Lawrence Zitnick.
According to the supplementary material of the paper Fast Multi- frame Stereo Scene Flow with Motion Segmentation by Tatsunori Taniai, Sudipta N. Sinha, and Yoichi Sato, the edge detector used in their work originates from the paper Fast Edge Detection Using Structured Forests by Piotr Dollár and C. Lawrence Zitnick.
88-Block-FT+SEQ-A
The paper Fast Multi-frame Stereo Scene Flow with Motion Segmentation directly adopts an edge detector from the paper Fast Edge Detection Using Structured Forests by Piotr Dollár and C. Lawrence Zitnick.
De-BBlck-FT+SEQ-LL-ae
The paper that is directly adopted edge detector in 'Fast Multi-frame Stereo Scene Flow with Motion Segmentation' is Fast Edge Detection Using Structured Forests by Piotr Dollár and C. Lawrence Zitnick.
The paper Fast Multi-frame Stereo Scene Flow with Motion Segmentation by Tatsunori Taniai, Sudipta N. Sinha, and Yoichi Sato does not directly adopt edge detector from another paper. Instead, they fast edge detector proposed by Dollár and Zitnick (2017) their work A Continuous Optimization Approach for Efficient and Accurate Scene Flow
SB-Block-FT+Blonn
The paper Fast Multi-frame Stereo Scene Flow with Motion Segmentation directly adopts an edge detector from the paper Fast Edge Detection Using Structured Forests by Piotr Dolkár and C. Lawrence Zitnick.
Di-Block-FT+Graph---
28

---

With #2 Distractors
SB-sFT+SEQ--irtt:
The paper that the edge detector originates from Edge-preservingg Multi-scale Video Deblurring by Hu et al.
8B-SFT+SEQ-Lass The edge detector used in the paper Fast Multi-frame Stereo Scene Flow with Motion Segmentation' the Fast Edge Detection Using Structured Forests.
8B- 18-RAG+SEQ-Finng The paper that is referred to in the paper Fast Multi-framee Stereo Scene Flow with Motion Segmentation is Edge- pregeepreeriingg Joint Image Segmentation and Estimation with Contextual and Spatial Priors by J. Shen, X. Yang, and M. Chen.
8B- 8B-RAG+SEQ-Lann Last: According to the provided information, the paper Fast Multi-frame Stereo Scene Flow with Motion Segmentation adopts an edge detector from another paper. The edge detector mentioned in the paper is the Fast Edge Detection Using Structured Forests by Piotr Dollár and C. Lawrence Zitnick.
The paper that the authors of Fast Multi-frame Stereo Scene Flow with Motion Segmentation directly adopted an edge detector from is Edge-preserving Multi-modal Deblurring.
OB-Block-FT+SEO-A The edge detector mentioned in the paper Fast Multi-frame Stereo Scene Flow with Motion Segmentation is the one proposed in the following paper: Fast Edge Detection Using Structured Forests by Piotr Dollár and C. Lawrence Zitnick.
-0-Blok-FT--Blo-RRA--i-ss Null
88-Bhock-FT--Book-RAA------- Null
DB-BBock-FT--Grap--KV The edge detector used in the paper Fast Multi-frame Stereo Scene Flow with Motion Segmentation is the Simplex detector, which is described in the paper: Piotr Dollár and C. Lawrence Zitnick. Fast Edge Detection Using Structured Forests. IEEE Transactions Pattern Analysis and Machine Intelligence (TPAMI), 2015.
A.2.3 Implementation Details for Paper Topic Classification
Dataset Curation The dataset is originally from Cora B6 and Pubmed 45 we adopt the test set split adopted in [7]. For each paper, the input text consists of the title and abstract.
For Paper Topic Classification, the input prompt can divided into 3 parts, namely Prefix, Paper Title & Abstracts, Question:
Prompt:
Prefix: To ensure fair comparison, all the methods adopt the same prefix follows:
You are an intelligent AI assistant. You will first read a list of titles or abstracts of papers cited by a central paper. Then, you will read the title or abstract of the central paper itself. Finally, you will answer question related the central paper:
Puper Tile & Abstructs:
(Title Abstract of Reference 1}, (Title & Abstract of Reference 2),..., (Title & Abstract of Reference k} Anln They are all cited by the following central paper: {Title & Abstract of Central Paper}
Question: To ensure fair comparison, all the attention methods adopt the same question as follows:
Classify the central paper into one of the following categories: {Classes). Provide your answer following 'Answer:'
Implementation
For sequential encoding and Block-RAG 35), we report the average performance with seeds 42 44 to randomly shuffle the placement order of sequence.
29

---

directly input the sequence of Prefix + Paper Title & Abstracct Question. When distractors are included, the Paper Texts are repeated accordingly, while ensuring that each citation ego-graph remains intact.
Sequential Encoding:
Parallel Encoding The parallel encoding baselines independently encode the Prefix, each paper title & abstract, Question, and then concatenate the KV cache together. The positional encoding setup follows the implementation used in the corresponding paper.
Graph-KV; independently encode Prefix and Question, while inject the structural inductive biases with Paper Title & Abstract following the modeling as introduced in Section.
A.2.4 Implementation Details for Stress Test
As introduced in the main text, we employ an Nvidia RTX6000 GPU (48GB) with AMD EPYC 7763 64-core processor for stress test. Specifically, for attention implementation, all the methods use FlashAttention2 [9]. The raw text extracted from the first test sample of the Cora (36] dataset. To meet the specified input length requirements-5500 and 1000 words for the memory test, and 100, 200, 400, and 800 words for the generation latency evaluation-we either repeat or truncate the original text accordingly.
Memory test: To test the memory usage of each method, we gradually increase the num- ber of neighbors of synthetic star graph, and use torch.cuda.reset_re.. saaeee__ee__mmorrr__ memory_statso) and forch.cuda.max_memorg _allocaeedl functions to monitor the peak GPU memory usage.
TameeTTT-iss-Toooe (TTFT): Similar to other parallel encoding baselines, Graph-K's KV also benefits from KV-cache pre-filling With pre-filled KV-cache, Graph-KV achieves significantly lower TTFT (Time-To-Firss To-First- (o-First-Token) compared to sequential encoding. To measure TTFT, we use the time.time() function to record the elapsed time.
30


Reviews:
[{"review_id": "kJo6uljrTx", "reviewer": "Reviewer_khbB", "summary": "This paper addresses a limitation of autoregressive Large Language Models (LLMs): their inability to natively process structured data, forcing all inputs to be serialized into flat sequences. \nThe authors propose Graph-KV, which directly injects structural inductive bias into the LLM's attention mechanism during inference. \nSpecifically, target text chunks selectively attend only to the KV cache of their designated source chunks. This is complemented by strategically assigning shared positional encodings (PE), where all source chunks share one PE range (0-L), all target chunks share another PE range (L-2L), and finally the query is appended. \n Experiments across four different tasks on multiple datasets demonstrate the model's effectiveness.", "questions": "Q1. In the baselines for comparison, Graph-KV is applied to the llama-3.1-8B-block model. Would similar effects be achieved when applied to other LLM models (such as 8B-SFT or 8B-RAG)? The llama-3.1-8B-block itself has already been trained with block attention.\n\nQ2. Can you provide preliminary experimental results or deeper analysis on multi-round iteration performance (e.g., t=2 or t=3)? Multi-hop message passing is common in graph neural network message passing patterns. For example, you could also compare computational overhead between Graph-KV Top-1/3 and Graph-KV Full.\n\nQ3. Compared to the significant effects in Table 2, Graph-KV+8B-Block in Table 3 datasets performs worse than 8B-Block Sequential (though better than block RAG). While the authors acknowledge that Graph-KV doesn't outperform sequential encoding in certain reasoning tasks (e.g., NarrativeQA, TriviaQA), their explanation—that sequential structure already captures implicit dependencies—seems insufficiently validated. Given that the paper's core contribution is that structure-aware attention mechanisms can improve LLM performance, deeper analysis of the potential losses from Graph-KV sparse attention is necessary.\n\nQ4. Regarding Table 2, it is unclear why all experimental groups and control groups show accuracy that first decreases then increases as hop-k increases.", "limitations": "Yes.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "**Strengths:**\n\n1. Graph-KV requires no additional parameters or complex prompting, instead modifying the LLM attention mechanism itself. \n\n2. Thorough baseline comparisons and good computational efficiency.\n\n3. By assigning new PE to preserve structural information of source and target chunks, positional bias is mitigated.\n\n**Weaknesses:**\n\n1. The method is based on block attention post-training on specific backbone models (such as llama-3.1-8B-block-ft), raising questions about applicability to other general LLMs.\n\n2. Experiments mainly focus on single-hop dependencies (source → target). The authors mention that update steps can be iterated with t>1 to simulate deeper interactions, but note this doesn't bring significant improvement on current tasks. This may indicate limitations of the current method for more complex multi-hop graph topologies. Multi-hop graph topologies may have higher value. In the experimental section, on MorehopQA multi-hop answering, Graph-KV Top-1/3 performs significantly worse than Graph-KV Full, not demonstrating the superiority shown on other datasets.\n\n3. In Table 3 datasets, experimental results show that 8B-Block Sequential performs better, suggesting that reasoning dependencies between two paragraphs may already be implicit in the sequential structure. Injecting structural bias through Graph-KV may not provide additional benefits or may even be counterproductive.\n\n4. The paper lacks alternative evaluation methods for assessing chunk relevance. Are there scenarios where similarity scores cannot fully capture the relationships?\n\n5. Although the authors mention that single-layer performance is already good and cite computational constraints, the lack of multi-layer/complex structure testing for comparison is not very convincing. Additionally, it seems this model does not reflect the role of edge weights (since top-k segments are directly concatenated together, there is no difference shown among these k segments).\n\n6. Figure 6 explanation is unclear and difficult to understand.", "was_revised": true, "final_justification": "I appreciate your responses and additional results. The new experiments address key concerns and strengthen the paper. While some limitations remain (e.g., unified edge weights), the overall contribution is solid, particularly for complex reasoning tasks.", "rebuttal": "# [W.1 and Q.1: Applicability to General LLM]\nWe clarify our motivation and **present new results** showing model-agnostic benefits.\n1. Motivation. We deliberately used a specialized backbone for a robust evaluation. While Graph-KV is model-agnostic, applying KV-cache manipulation to standard LLM can cause **distributional shift**[1-3]. Solutions include: 1) Tuning-free heuristics(APE[1]), 2) Post-training on attention blocks (Block-RAG[3]). We chose post-training as it is more stable and state-of-the-art (SOTA), which best isolated Graph-KV's benefits.\n2. Experiments on a Standard LLM. We **apply Graph-KV to standard Llama-3.1-8B-SFT**, comparing it against the parallel encoding baselines on the same backbone. **Graph-KV consistently outperforms all parallel baselines**.\n\n|  | MorehopQA |  |  |  |  |  | 2Wiki |  |  |  |  |\n|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|\n| Attention | Hop-1 | Hop-2 | Hop-3 | Hop-4 | Hop-5 | Avg | Compare | Infer | Bridge | Compose | Avg |\n| PCW | 11.26 | 10.81 | 10.38 | 0.00 | 17.58 | 11.35 | 70.13 | 13.07 | 67.17 | 32.58 | 46.94 |\n| APE | 13.28 | 15.86 | 9.47 | **61.53** | 10.98 | 14.13 | 74.44 | 18.26 | 61.17 | 37.41 | 49.20 |\n| Block-RAG | 13.96 | 13.94 | 9.74 | 0.00 | 15.38 | 13.32 | 72.17 | 15.17 | 68.01 | 35.54 | 48.99 |\n| Graph-KV Top-3 | **15.54** | **16.10** | **12.98** | 0.00 | **18.68** | **15.47** | 76.41 | 17.43 | 64.15 | 47.19 | 54.30 |\n\n|  | Multihop-RAG |  |  |  |  | HotpotQA |  |  | NarrativeQA | TriviaQA |\n|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|\n| Attention | Infer | Compare | Temporal | Null | Avg | Compare | Bridge | Avg | Infer | Infer |\n| PCW | **69.39** | 34.29 | 34.35 | 42.10 | 42.01 | 54.87 | 33.28 | 37.62 | 39.22 | 60.13 |\n| APE | 48.34 | 33.46 | 33.49 | 86.25 | 40.34 | 60.52 | 46.24 | 49.11 | 49.05 | 66.28 |\n| Block-RAG | 49.28 | 33.54 | 33.76 | 41.86 | 38.41 | 57.83 | 37.39 | 41.49 | 46.53 | 65.55 |\n| Graph-KV Top-3 | 67.00 | **35.14** | **34.76** | **42.74** | **42.35** | **63.55** | **51.44** | **53.90** | **51.08** | **69.47** |\n\nEven without a specialized backbone, Graph-KV shows clear advantages. We plan to fine-tune another model with block attention for the final version; this was infeasible during rebuttal.\n\n[1]APE: Faster and Longer Context-Augmented Generation via Adaptive Parallel Encoding.\nYang, et al. ICLR 2025.\n\n[2] Parallel Context Windows for Large Language Models. Ratner, et al. \n\n[3] Block-Attention for Efficient Prefilling. Ma, et al. ICLR 2025.\n# [W.2, Q.2 Multi-hop topologies]\nWe agree evaluating multi-hop dependencies is critical. We ran new experiments on Graph-KV's multi-hop ability, and results confirm iterative updates improve performance:\n\n## [Scenario 1] Multi-Hop RAG\nWe built multi-layer graphs from retriever relevance scores for iterative information propagation.\n- 2-Hop: We design a chain of **(Top 1 chunk) → (Top 2-4 chunks) → (Rest)**.\n\nIteration 1: \"Top 1\" acts as the source to update the KV of \"Top 2-4\".\n\nIteration 2: The updated \"Top 2-4\" then update the rest.\n- 3-Hop: A deeper chain **(Top 1) → (Top 2-3) → (Top 4-5) → (Rest)** with three-step propagation.\n\n|  |  | Multihop-RAG |  |  |  |  | HotpotQA |  |  | NarrativeQA | TriviaQA |\n|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|\n| Attention | #hop | Infer | Compare | Temporal | Null | Avg | Compare | Bridge | Avg | Infer | Infer |\n| Graph-KV Top-1 | 1 | 73.25 | 34.19 | 38.18 | 53.85 | 44.81 | 70.41 | 74.14 | 73.39 | 62.04 | 75.17 |\n| Graph-KV Top-3 | 1 | 73.12 | 34.43 | 38.69 | 63.64 | 45.79 | 71.01 | 76.24 | 75.19 | 62.29 | 75.66 |\n| Graph-KV Full | 1 | 69.04 | 34.63 | 38.48 | **88.79** | 46.41 | 70.41 | 77.62 | 76.17 | **62.88** | 75.85 |\n| Graph-KV Top-1-Top-3 | 2 | 73.20 | 34.54 | **38.78** | 70.82 | 46.15 | 71.95 | 77.25 | 76.19 | 62.60 | 75.90 |\n| Graph-KV Top1-Top3-Top5 | 3 | **73.30** | **34.76** | **38.78** | 75.44 | **46.74** | **72.02** | **77.57** | **76.45** | 62.74 | **76.04** |\n\n|  |  | MorehopQA |  |  |  |  |  | 2Wiki |  |  |  |  |\n|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|\n| Attention | #hop | Hop-1 | Hop-2 | Hop-3 | Hop-4 | Hop-5 | Avg | Compare | Infer | Bridge | Compose | Avg |\n| Graph-KV Top1 | 1 | 54.72 | 25.72 | 24.67 | 23.07 | 31.86 | 37.96 | 82.76 | 52.42 | 90.00 | 65.94 | 73.60 |\n| Graph-KV Top3 | 1 | 56.63 | 25.72 | 24.67 | 23.07 | 29.67 | 38.11 | 83.25 | 56.74 | 90.47 | 67.83 | 75.15 |\n| Graph_KV Full | 1 | 64.86 | 30.52 | 25.97 | 30.76 | **47.25** | 44.90 | 82.69 | 54.16 | 90.43 | 67.11 | 74.38 |\n| Graph-KV Top1-Top3 | 2 | 67.11 | 32.69 | 25.32 | 30.76 | 37.36 | 45.70 | 83.45 | **57.04** | **90.77** | 68.97 | 75.76 |\n| Graph-KV Top1-Top3-Top5 | 3 | **67.56** | **32.93** | **25.97** | **38.46** | 43.95 | **46.69** | **83.75** | **57.04** | **90.77** | **69.34** | **75.99** |\n\n## [Scenario 2] 2-Hop Paper Topic Classification\n\nWe extended to 2-hops via a (2-hop refs) → (1-hop refs) → (paper) message-passing chain. To manage graph size, we sampled k=3,10 references per 1-hop neighbor.\n\n| Topic Classification | # samples | Cora | Pubmed |\n|:---:|:---:|:---:|:---:|\n| Graph-KV | -- | 71.03 | 84.61 |\n| Graph-KV (2Hop) | 3 | 71.21 | 85.04 |\n| Graph-KV (2Hop) | 10 | **71.77** | **85.32** |\n\n## [conclusion]\nThese results validate that Graph-KV can model deeper dependencies beyond single-hop interactions. We thank you for pushing us in this valuable direction.\n# [W.3 Q.3 Concerns about Performance]\nWe appreciate the detailed analysis. Here, we contextualize these nuances by highlighting Graph-KV's fundamental advantages.\n1. Significant Gains on Complex Reasoning\n\n**Graph-KV consistently excels on complex reasoning benchmarks.**\n- Advanced Multi-Hop RAG (Table 2): On challenging multi-hop datasets, Graph-KV significantly surpasses all baselines, including a strong sequential model.\n- Long-Context Reasoning (ARXIV-QA, Figure 6):Only Graph-KV beats sequential models that are crippled by positional bias.\n- Classic Graph Learning (Table 4):It again outperforms all baselines.\n\nWhen structure is paramount, Graph-KV is a clear winner.\n\n2. Understanding the Nuances when simpler (Table 3)\n\nOn less complex tasks, the sequential model is comparable or slightly better. The benefit of Graph-KV is most pronounced on tasks where explicit, injected structure is more valuable than the implicit, linear order of documents. For simple tasks where the answer is in a single doc, vanilla attention can suffice. Graph-KV is designed for challenging cases.\n\n3. Fundamental Advantages\n\nGraph-KV solves fundamental auto-regressive flaws, not just achieve high scores:\n- **Eliminates Positional Bias**: It is robust to document order, ensuring reliable reasoning.\n- **Far More Efficient**: Its reduced complexity enables reasoning over document scales infeasible for sequential models.\n- **Superior in its Class**: It consistently beats peers (e.g., Block-RAG) by modeling inter-document structure.\n\n4. The Untapped Potential of Structure-Aware Training\n\nSequential models have massive pre-training. Graph-KV achieves strong results without large-scale, structure-aware pre-training, yet it already rivals or surpasses the sequential baseline on complex tasks. We believe structure-aware fine-tuning would further improve its performance.\n# [W. 4 similarity scores cannot fully capture the relationships]\nWe agree simple similarity scores are imperfect proxy to model structural dependencies. Our heuristic is a pragmatic choice for RAG tasks, where, as noted in the paper, true dependencies are implicit. We build the graph with the highest-scoring doc as the \"source,\" based on the intuition that the most relevant chunks are often critical hubs for information flow in multi-hop reasoning. Though a heuristic, experiments prove this is highly effective, validating that an approximate structure is far better than none.\n# [W. 5 Edge weights]\nAn excellent suggestion. We currently treat all dependencies (edges) as uniform, as our graphs, like many in practice, do not have explicit edge weights. However, we agree incorporating them is a compelling future direction. A straightforward extension is to modulate attention scores between nodes, allowing the model to prioritize important connections.\n# [W. 6 explanation of Figure. 6]\nFigure 6 shows model performance on ARXIV-QA with very long contexts and \"distractor\" docs. It illustrates standard models' positional bias issue and Graph-KV's robustness.\n\nIn the figure, each grid shows a model's performance (Green=correct, Red=fail). The three panels (top to bottom) correspond to adding 0, 1, and 2 distractor docs, respectively. Adding distractors makes the context much longer and tests models to find information in a \"noisy\" environment .\n## [Top Panel - 0 Distractor]\nWithout distractors, Sequential models perform well, and Parallel methods perform poorly as they can't model cross-document connections. Graph-KV also performs well, nearly matching the top sequential performance by correctly using the citation graph structure..\n## [Middle & Bottom Panel - Positional Bias Test with 1,2 Distractors]\nThis is the most important part. For sequential models, relevant docs were placed either at the context's very beginning (\"First\") or very end (\"Last\").\n- **Sequential Models Fail**: Performance collapses when documents are placed \"First\" but succeeds when \"Last\" (due to recency bias). With two distractors, they get \"lost in the middle.\"\n- **Graph-KV Remains Robust**: In contrast, its performance is high and stable regardless of document order or distractors because it uses explicit graph structure, not linear position.\n# [Q.4 Table. 2]\nThis is likely an artifact for two reasons. **Data Scarcity:** The test set for 4- and 5-hop questions is too small for the accuracy scores to be statistically significant. **Inconsistent Complexity:** Question difficulty may not scale linearly with the hop count, as some higher-hop questions can be incidentally simpler."}, {"review_id": "3Q5b4V2gj6", "reviewer": "Reviewer_C8Lc", "summary": "The paper introduces Graph-KV, a framework that injects structural biases into LLMs by modeling documents as graphs. Instead of sequential attention, target segments attend only to selected source segments based on graph-defined dependencies. Shared positional encodings reduce bias and context usage. Evaluated on RAG, academic QA, and citation classification tasks, Graph-KV outperforms sequential and parallel baselines, particularly in multi-hop reasoning and long-context settings.", "questions": "Further questions to discuss. Do the graphs' properties influence the model predictions? For example, if the graphs are dense, does the current framework still work well? If this is a dense graph, there should be many documents to merge.", "limitations": "The paper does not discuss its limitations. However, a key concern is the scope of graph structures the framework can support and whether the fixed window length may pose constraints on its scalability.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "The paper proposes a novel framework for modeling documents as graph structures and demonstrates its efficiency. The idea of encoding structural information through positional embeddings is particularly impressive and presents a promising direction for incorporating topological bias into LLMs. However, the paper’s main weakness lies in its unclear writing. Below are specific concerns.\n\nIt is unclear how the graph structure is built within the Graph-KV framework. Are the edges in the graph generated automatically? If automatically, what criteria or model is used to define source–target dependencies?\n\nThe framework uses position encoding windows of length L. How is this value chosen? Is it task-specific, empirically tuned, or theoretically motivated?\n\nThe relationship between the left and right sides of Figure 2 is confusing. What exactly does the “merge” operation refer to? There is no introduction in the corresponding paragraph.\n\ntypo in Table 2. wrong bold in MultiHop-8B-RAG,  Temporal.", "was_revised": true, "final_justification": "The authors have addressed all of my concerns. I believe this approach of injecting chunks into LLMs is novel and represents exactly the right direction for integrating graphs into LLMs. I will maintain my positive score.", "rebuttal": "We thank **Reviewer C8Lc** for their insightful questions, constructive suggestions, and acknowledgment of Graph-KV's novelty and effectiveness. We address their questions below.\n\n\n# [Q.1 Edge Generation]\nThank you for this insightful question. Yes, the graph edges are generated automatically based on the nature of the task. We consider two primary scenarios:\n1. For Tasks Without an Explicit Graph (e.g., General RAG)\n\nIn these cases, a graph structure is generated based on a relevance-based heuristic. The chunks with the top-k similarity scores to the query are designated as \"source\" nodes, and the rest are \"targets.\" This models the intuition that understanding the most relevant documents is crucial for contextualizing the others. This is in contrast to the naive sequential models, which assume every pair of documents is connected and thus adopt dense attention. \n2. For Tasks With a Natural Graph Structure (e.g., ARXIV-QA, Topic Classification)\n\nFor these tasks, we use the pre-existing graph structure directly. The edges are automatically defined by the citation links between papers. This approach directly models the natural human reasoning process of consulting references for foundational knowledge.\n\n# [Q.2 Choose L]\nThank you for the excellent question about how the PE window size, L, is determined. This value is not a fixed hyperparameter that requires tuning. Instead, it is determined dynamically and automatically for each input query.\n\nFor any given input, L is set to the maximum token length found across all text chunks being processed for that query. This data-driven approach guarantees the shared PE windows are large enough to accommodate every chunk without truncation.\n\nOur framework then assigns these PE windows to different groups. As detailed in the paper, \"source\" chunks are assigned the shared PE range [0, L), and \"target\" chunks are assigned the subsequent shared range [L, 2L). Defining L as the maximum length of any single chunk ensures that all positional indices fall neatly within their designated windows.\n\n# [Q.3 Merge]\n\nWe apologize that the term \"merge\" was not clearly defined and thank the reviewer for pointing this out. The term is intended as an analogy to describe how a target chunk synthesizes information from multiple source chunks within the attention mechanism.\n\nFigure 2 and its caption provide the intuition behind this analogy. For a target chunk (e.g.,\nDoc.1) with multiple source chunks (e.g., Doc.2 and Doc.3), the process is functionally equivalent to conceptually processing the sequence [Doc.2, Doc.1], then [Doc.3, Doc.1], and finally \"merging\" the resulting representations of Doc.1 from both processes.\n\nTechnically, this \"merge\" is not a separate, explicit step. It is performed implicitly within a single, sparsified attention operation. The attention mechanism's output is a weighted sum of the value vectors from all sources, which naturally creates a single, updated representation for the target chunk that has effectively \"merged\" the contextual information from all its dependencies in one computational step.\n\nWe will add this explicit clarification to the final version of the paper to improve readability.\n\n\n# [Q.4 Properties and Limitation]\n\nThank you for this insightful question regarding the framework's scalability to dense graphs.\n\nYou are correct that a dense graph implies a large number of documents, and our framework is well-suited for this challenge. The key is the **shared PE strategy**, which is designed to handle a large number of documents without suffering the context window limitations of sequential models.\n\nOur **ARXIV-QA experiment** serves as a proof-of-concept for this. In this task, the model successfully processed extremely long inputs (up to 264.6k tokens) by using shared PEs. We note in the paper that this approach was \"vital for the LLM to properly digest the full context\", demonstrating its effectiveness in scenarios where traditional methods would fail.\nTherefore, the shared PE mechanism provides a robust and scalable solution for dense graphs, directly addressing one of the most significant challenges in long-context reasoning.\n\n# [Typo]\nThanks for pointing out the typo, we will fix them in our final version."}, {"review_id": "S21PO03VLd", "reviewer": "Reviewer_mq6i", "summary": "To inject structural inductive bias into auto-regressive models, this paper proposes Graph-KV, which leverages the KV-cache of text segments as condensed representations and governs their interaction through structural inductive biases. The experiments on seven RAG benchmarks, ARXIV-QA, and paper topic classification show that Graph-KV outperforms the baselines.", "questions": "See questions in “Strengths And Weaknesses”, here are some additional suggestions:\n    • Figure 1, line 3, lack a space between “[66]” and “(2)”.\n    • Line 153, lack a space between “Graph-KV” and “performs”.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths\n    • The paper proposes Graph-KV to inject structural inductive bias into auto-regressive models.\n    • Graph-KV exhibits better performances than other methods across three different scenarios.\n\nWeaknesses\n    • Some technical details are not clear. See the below questions.\nLine 156-157, how is the representation $h$ used to form initial KV pairs?\nLine 164-165, how is sparsified attention applied? It is not obvious in the self-attention equation.\nIn addition to the (K, V) pairs of the source chunk, is it also possible to consider (K, V) of the target chunk while using the equation at line 165?\nWhat do the numbers of the “Backbone” rows in Table 2, 3 stand for?\n    • Some experiments are missing.\nLine 168-175, the benefits of multiple rounds are discussed, but there is no experiment supporting this.\nWhile the Graph-KV is composed of 1) Structure-aware Attention Mechanism and 2) Allocation of Positional Encodings, there is no ablation study to discuss the effectiveness of the individual modules of Graph-KV.\n    • The paper is not well organized. The implementation of Graph-KV across different scenarios and their results should be in different sections.", "was_revised": true, "final_justification": "I raised my score from 3 to 4 because the authors addressed the weaknesses. I did not further increase my score because the experimental results are not consistently strong.", "rebuttal": "We thank reviewer mq6i for their detailed review and suggestions. Below we try to address their questions.\n\n# [Q.1 How is the representation used in Initial KV pairs formulation]\nBelow we try to explain how to use the representation in initial KV pairs formulation: \n\n\nThe initial Key-Value (KV) pairs are generated from token embeddings using the standard mechanism within a Transformer's self-attention layer.\n\nThe process is as follows:\n\n1. **Tokenization and Embedding:** First, each text chunk is tokenized, and these tokens are mapped to their corresponding input embeddings. This sequence of embeddings is the latent representation h mentioned in our paper.\n2. **Linear Projection:** Next, these embeddings (h) are processed by a self-attention layer. Inside this layer, two distinct linear projection matrices—a Key projector and a Value projector—transform the input embeddings into Key (K) and Value (V) vectors.\n\nThese generated K and V vectors form the initial KV pairs, which are then stored in the KV cache for that text chunk.\n\n\n# [Q.2 Implementation of Sparsified Attention]\nThank you for the question. We are happy to clarify the implementation of the sparsified attention mechanism.\n\n**How Attention is Sparsified**\n\nIn a standard self-attention mechanism, a query attends to all key-value pairs in its context. Our approach is \"sparsified\" because a target chunk is restricted to attending only to a predefined subset of chunks: its designated sources.\n\nThe equation on line 165 reflects this. For a given target chunk j, its query vectors (Qj​) are computed. However, the key (K) and value (V) matrices used in the attention calculation are constructed **exclusively** from the KV pairs of its source chunks, denoted as N(j). The KV pairs from all other non-source chunks are effectively masked out of the computation. This is analogous to message passing in graphs, where information propagates only along existing edges (from sources to the target).\n\n# [Q.3 Multiple Round Iteration of Graph-KV]\nWe thank you for this constructive suggestion. Our initial 1-hop experiments have shown significant improvements across the three tasks. That said, we agree that evaluating performance on deeper, multi-hop dependencies is a critical test.\n\nIn response, we conducted new experiments to directly assess Graph-KV's multi-hop capabilities. The results confirm that iterative updates improve performance.\n\n## [Scenario 1] New Multi-Hop RAG Experiments\nTo simulate deeper reasoning, we constructed multi-layered dependency graphs based on retriever relevance scores. Information is propagated through iterative Graph-KV updates:\n\n- 2-Hop Structure: We defined a dependency chain as **(Top 1 Chunk) → (Top 2-4 Chunks) → (Remaining Chunks)**.\n\nIteration 1: The \"Top 1\" chunk acts as the source to update the KV-caches of the \"Top 2-4\" chunks.\n\nIteration 2: The updated \"Top 2-4\" chunks then serve as the source to update the remaining chunks.\n\n- 3-Hop Structure: We modeled an even deeper chain as **(Top 1) → (Top 2-3) → (Top 4-5) → (Remaining Chunks)**, realizing a three-step propagation process.\n\n|  |  | Multihop-RAG |  |  |  |  | HotpotQA |  |  | NarrativeQA | TriviaQA |\n|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|\n| Attention | #hop | Infer | Compare | Temporal | Null | Avg | Compare | Bridge | Avg | Infer | Infer |\n| Graph-KV Top-1 | 1 | 73.25 | 34.19 | 38.18 | 53.85 | 44.81 | 70.41 | 74.14 | 73.39 | 62.04 | 75.17 |\n| Graph-KV Top-3 | 1 | 73.12 | 34.43 | 38.69 | 63.64 | 45.79 | 71.01 | 76.24 | 75.19 | 62.29 | 75.66 |\n| Graph-KV Full | 1 | 69.04 | 34.63 | 38.48 | **88.79** | 46.41 | 70.41 | 77.62 | 76.17 | **62.88** | 75.85 |\n| Graph-KV Top-1-Top-3 | 2 | 73.20 | 34.54 | **38.78** | 70.82 | 46.15 | 71.95 | 77.25 | 76.19 | 62.60 | 75.90 |\n| Graph-KV Top1-Top3-Top5 | 3 | **73.30** | **34.76** | **38.78** | 75.44 | **46.74** | **72.02** | **77.57** | **76.45** | 62.74 | **76.04** |\n\n\n\n\n|  |  | MorehopQA |  |  |  |  |  | 2Wiki |  |  |  |  |\n|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|\n| Attention | #hop | Hop-1 | Hop-2 | Hop-3 | Hop-4 | Hop-5 | Avg | Compare | Infer | Bridge | Compose | Avg |\n| Graph-KV Top1 | 1 | 54.72 | 25.72 | 24.67 | 23.07 | 31.86 | 37.96 | 82.76 | 52.42 | 90.00 | 65.94 | 73.60 |\n| Graph-KV Top3 | 1 | 56.63 | 25.72 | 24.67 | 23.07 | 29.67 | 38.11 | 83.25 | 56.74 | 90.47 | 67.83 | 75.15 |\n| Graph_KV Full | 1 | 64.86 | 30.52 | 25.97 | 30.76 | **47.25** | 44.90 | 82.69 | 54.16 | 90.43 | 67.11 | 74.38 |\n| Graph-KV Top1-Top3 | 2 | 67.11 | 32.69 | 25.32 | 30.76 | 37.36 | 45.70 | 83.45 | **57.04** | **90.77** | 68.97 | 75.76 |\n| Graph-KV Top1-Top3-Top5 | 3 | **67.56** | **32.93** | **25.97** | **38.46** | 43.95 | **46.69** | **83.75** | **57.04** | **90.77** | **69.34** | **75.99** |\n\n\n\nThe results show a consistent trend: modeling deeper **2-hop and 3-hop** dependencies yields further performance gains over the strong 1-hop variants across most RAG benchmarks. This confirms that Graph-KV effectively models complex, multi-hop information flow and is not limited to single-step interactions.\n\n\n## [Scenario 2] 2-Hop Paper Topic Classification\n\nWe extend the paper topic classification experiment to a 2-hop citation graph: **(2-hop references) → (1-hop references) → (central paper)**. This creates a natural 2-iteration \"message passing\" scenario. To manage the graph size, we sampled k (k=3,10) references for each 1-hop neighbor.\n\nIncorporating information from these 2-hop neighbors via a second Graph-KV iteration further boosts classification accuracy.\n\n| Topic Classification | # samples | Cora | Pubmed |\n|:---:|:---:|:---:|:---:|\n| Graph-KV | -- | 71.03 | 84.61 |\n| Graph-KV (2Hop) | 3 | 71.21 | 85.04 |\n| Graph-KV (2Hop) | 10 | **71.77** | **85.32** |\n\n\n\n## [conclusion]\nThese new experiments validate that the Graph-KV framework is not limited to single-hop interactions but is a flexible method capable of modeling deeper, multi-hop dependencies when present in the data structure. Thank you for pushing us to explore this valuable direction.\n\n# [Ablation]\nThank you for this excellent suggestion. We have performed the requested ablation study. Before presenting the results, it is important to clarify the deep synergy between Graph-KV's two core components, as they are designed to work together in principle.\n\nThe **Structure-aware Attention** mechanism operates on a set of source documents that ideally should be treated without regard to their order (i.e., maintaining permutation equivariance). Using this mechanism without our **Shared Positional Encoding (PE)** would require imposing an arbitrary sequence on the source chunks. This would break the desired permutation equivariance and introduce severe positional bias, as the model's output would change based on the random ordering of the sources.\n\nOur Shared PE allocation is specifically designed to solve this problem by assigning the same positional information to all source chunks, making the model robust to their ordering. The following ablation study empirically validates this synergy.\n\nWe tested four configurations on the topic classification task. Note that the variance (±) reflects sensitivity to the input order of reference documents, indicating positional bias.\n\n|  |  |  | Cora | Pubmed |\n|:---:|:---:|:---:|:---:|:---:|\n| Structural Attention | Shared PE |  |  |  |\n| No | No | Block-RAG | 69.55±0.30 | 83.24±1.16 |\n| No | Yes | -- | 69.74 | 83.59 |\n| Yes | No | -- | 70.14±0.69 | 83.75±1.02 |\n| Yes | Yes | Graph-KV | 71.03 | 84.61 |\n\nThis study confirms our reasoning:\n\n- **Structural Attention alone:** As predicted, this configuration suffers from high positional bias (e.g., ±0.69 variance on Cora). Lacking permutation equivariance, its performance is unstable, though still better than the baseline.\n\n- **Shared PE alone:** This removes the positional bias but provides only a marginal performance gain, as it lacks the structure-aware mechanism to guide reasoning.\n\n- **Full Graph-KV:** By combining both components, our full Graph-KV method achieves the best of both worlds. It leverages structural dependencies for a significant performance boost and uses Shared PE to maintain permutation equivariance, resulting in the highest accuracy and stable performance.\n\n# [W. Organization, in different sections]\nThank you for your feedback on the paper's organization. We apologize if the structure was not clear. We want to clarify that we have structured the experiments (Section 4) by task, with the implementation details for Graph-KV presented within each respective task's section.\n\nTo clarify the existing layout:\n\n- **Task 1: Retrieval-Augmented Generation (RAG)**: The implementation of Graph-KV for RAG tasks is detailed in **Section 4.1** (lines 249-258), illustrated by Figure 3.\n\n- **Task 2: ARXIV-QA:** The setup and implementation for the ARXIV-QA task are presented in **Section 4.2** (lines 302-307), with an example in Figure 5.\n\n- **Task 3: Paper Topic Classification:** The modeling approach for topic classification is described in **Section 4.3** (lines 322-330) .\n\nTo address your concern directly, we will improve the organization in the final version by adding more distinct sub-headings within each task's section (e.g., \"Graph-KV Implementation\" and \"Result Analysis\") to make the structure more explicit and easier to follow.\n\n# [Typos]\nThanks for pointing out the typos, we will fix them in our final version."}]

Author rebuttal:

Meta-review: This paper proposes a way to incorporate various forms of structured data into LLM by modifying the attention masks and positional encodings. Evaluations are broad, and reviewers broadly agree on significance and execution of the paper are up-to-standard. I agree with them, and think the paper will be broadly interesting to the broader NeurIPS community. Therefore, I recommend acceptance.
Decision: Accept (poster)