We thank reviewer mq6i for their detailed review and suggestions. Below we try to address their questions.

[Q.1 How is the representation used in Initial KV pairs formulation]

Below we try to explain how to use the representation in initial KV pairs formulation:

The initial Key-Value (KV) pairs are generated from token embeddings using the standard mechanism within a Transformer's self-attention layer.

The process is as follows:

1. 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.
2. 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.

These generated K and V vectors form the initial KV pairs, which are then stored in the KV cache for that text chunk.

[Q.2 Implementation of Sparsified Attention]

Thank you for the question. We are happy to clarify the implementation of the sparsified attention mechanism.

How Attention is Sparsified

In 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.

The 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).

[Q.3 Multiple Round Iteration of Graph-KV]

We 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.

In response, we conducted new experiments to directly assess Graph-KV's multi-hop capabilities. The results confirm that iterative updates improve performance.

[Scenario 1] New Multi-Hop RAG Experiments

To simulate deeper reasoning, we constructed multi-layered dependency graphs based on retriever relevance scores. Information is propagated through iterative Graph-KV updates:

• 2-Hop Structure: We defined a dependency chain as (Top 1 Chunk) → (Top 2-4 Chunks) → (Remaining Chunks).

Iteration 1: The "Top 1" chunk acts as the source to update the KV-caches of the "Top 2-4" chunks.

Iteration 2: The updated "Top 2-4" chunks then serve as the source to update the remaining chunks.

• 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.

The 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.

[Scenario 2] 2-Hop Paper Topic Classification

We 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.

Incorporating information from these 2-hop neighbors via a second Graph-KV iteration further boosts classification accuracy.

[conclusion]

These 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.

[Ablation]

Thank 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.

The 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.

Our 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.

We tested four configurations on the topic classification task. Note that the variance (±) reflects sensitivity to the input order of reference documents, indicating positional bias.

This study confirms our reasoning:

• 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.

• 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.

• 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.

[W. Organization, in different sections]

Thank 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.

To clarify the existing layout:

• 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.

• 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.

• Task 3: Paper Topic Classification: The modeling approach for topic classification is described in Section 4.3 (lines 322-330) .

To 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.

[Typos]

Thanks for pointing out the typos, we will fix them in our final version.

We thank Reviewer C8Lc for their insightful questions, constructive suggestions, and acknowledgment of Graph-KV's novelty and effectiveness. We address their questions below.

[Q.1 Edge Generation]

Thank you for this insightful question. Yes, the graph edges are generated automatically based on the nature of the task. We consider two primary scenarios:

1. For Tasks Without an Explicit Graph (e.g., General RAG)

In 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. 2. For Tasks With a Natural Graph Structure (e.g., ARXIV-QA, Topic Classification)

For 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.

[Q.2 Choose L]

Thank 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.

For 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.

Our 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.

[Q.3 Merge]

We 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.

Figure 2 and its caption provide the intuition behind this analogy. For a target chunk (e.g., Doc.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.

Technically, 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.

We will add this explicit clarification to the final version of the paper to improve readability.

[Q.4 Properties and Limitation]

Thank you for this insightful question regarding the framework's scalability to dense graphs.

You 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.

Our 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. Therefore, 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.

[Typo]

Thanks for pointing out the typo, we will fix them in our final version.

[W.1 and Q.1: Applicability to General LLM]

We clarify our motivation and present new results showing model-agnostic benefits.

1. 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.
2. 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.

Even 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.

[1]APE: Faster and Longer Context-Augmented Generation via Adaptive Parallel Encoding. Yang, et al. ICLR 2025.

[2] Parallel Context Windows for Large Language Models. Ratner, et al.

[3] Block-Attention for Efficient Prefilling. Ma, et al. ICLR 2025.

[W.2, Q.2 Multi-hop topologies]

We 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:

[Scenario 1] Multi-Hop RAG

We built multi-layer graphs from retriever relevance scores for iterative information propagation.

• 2-Hop: We design a chain of (Top 1 chunk) → (Top 2-4 chunks) → (Rest).

Iteration 1: "Top 1" acts as 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 1) → (Top 2-3) → (Top 4-5) → (Rest) with three-step propagation.

[Scenario 2] 2-Hop Paper Topic Classification

We 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.

[conclusion]

These results validate that Graph-KV can model deeper dependencies beyond single-hop interactions. We thank you for pushing us in this valuable direction.

[W.3 Q.3 Concerns about Performance]

We appreciate the detailed analysis. Here, we contextualize these nuances by highlighting Graph-KV's fundamental advantages.

1. Significant Gains on Complex Reasoning

Graph-KV consistently excels on complex reasoning benchmarks.

• Advanced Multi-Hop RAG (Table 2): On challenging multi-hop datasets, Graph-KV significantly surpasses all baselines, including a strong sequential model.
• Long-Context Reasoning (ARXIV-QA, Figure 6):Only Graph-KV beats sequential models that are crippled by positional bias.
• Classic Graph Learning (Table 4):It again outperforms all baselines.

When structure is paramount, Graph-KV is a clear winner.

2. Understanding the Nuances when simpler (Table 3)

On 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.

3. Fundamental Advantages

Graph-KV solves fundamental auto-regressive flaws, not just achieve high scores:

• Eliminates Positional Bias: It is robust to document order, ensuring reliable reasoning.
• Far More Efficient: Its reduced complexity enables reasoning over document scales infeasible for sequential models.
• Superior in its Class: It consistently beats peers (e.g., Block-RAG) by modeling inter-document structure.

4. The Untapped Potential of Structure-Aware Training

Sequential 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.

[W. 4 similarity scores cannot fully capture the relationships]

We 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.

[W. 5 Edge weights]

An 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.

[W. 6 explanation of Figure. 6]

Figure 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.

In 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 .

[Top Panel - 0 Distractor]

Without 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..

[Middle & Bottom Panel - Positional Bias Test with 1,2 Distractors]

This is the most important part. For sequential models, relevant docs were placed either at the context's very beginning ("First") or very end ("Last").

• 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."
• 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.

[Q.4 Table. 2]

This 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.

We thank the reviewer again for their insightful comments, which have pushed us to verify the general applicability of Graph-KV and its capability for multi-hop iteration. We will incorporate experimental results for these two aspects into the next version of our paper. We also appreciate the suggestion to discuss the complexity of multi-hop iterative Graph-KV. Below, we provide a preliminary analysis of the computational complexity, which will be expanded upon in the revised manuscript.

As discussed in lines 199–204 of our paper, the complexity of sequential encoding is $O(∣V∣^2L^2)$, where $V$ is the number of text chunks and $L$ is the average number of tokens per chunk. The computational complexity of a single Graph-KV iteration is $O(∣E∣L^2)$, where E represents the number of dependencies. For a two-step, multi-hop iterative propagation, the complexity becomes $O((∣E_1​∣+∣E_2​∣)L^2)$, where $E_1​$ and $E_2$ ​are the numbers of dependencies in the first and second iterations, respectively. In real-world scenarios, the number of dependencies $(∣E∣)$ is often much smaller than the number of nodes $(∣V∣)$, making the computational complexity of these propagations sparse.

We now analyze the complexity of building dependencies within the RAG task:

• Graph-KV Full: A fully connected bipartite graph is constructed, so the number of dependencies, $∣E∣$, is on the order of $∣V∣^2$. The complexity is therefore comparable to that of sequential encoding.
• Graph-KV Top-3: The number of dependencies is significantly reduced, requiring only $(3×∣V∣)L^2$ computations.
• Graph-KV Top-1-Top-3-Top-5: The computational cost is $(5∣V∣+18)L^2$, which is still more efficient than Graph-KV Full.

We will include a more detailed discussion and formal analysis in the next version of our paper to provide a comprehensive view of the complexity of our proposed method.

We thank the reviewer once again for their time and valuable contributions to the discussion. Their active participation has greatly helped us refine our analysis and improve the paper.