Research map / Graph learning / Knowledge and temporal graphs
Graph-KV: Breaking Sequence via Injecting Structural Biases into Large Language Models
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Graph-KV injects graph-structured block attention masks over per-segment KV caches plus shared/offset positional encodings so target segments attend only to their source segments' KV caches, improving RAG, citation-graph QA (Arxiv-QA), and paper topic classification over sequential and parallel encoding baselines.
Problem
Auto-regressive LLMs require structured inputs (RAG segments, citation networks) to be serialized into flat sequences, which induces positional bias, ignores inter-segment dependencies, and consumes context window and quadratic compute.
Approach
Treat each text segment's KV cache as a condensed representation and update target segments by attending only to designated source segments' KV caches (a graph-structured block mask), with source chunks sharing positions [0,L) and target chunks following at [L,2L) to reduce positional bias and context usage.
Key results
- On MorehopQA, Graph-KV Top-3 reaches 38.11 average vs 37.38 for sequential 8B-Block and 11.35 for PCW; Graph-KV Full reaches 44.90 average.
- On HotpotQA, Graph-KV Top-3 averages 75.19 vs 77.43 for sequential 8B-Block, while outperforming Block-RAG (71.31) by about 4 points.
- On paper topic classification, Graph-KV reaches 71.03 on Cora and 84.61 on Pubmed, above sequential (67.09, 79.79) and Block-RAG (69.55, 83.24).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| inject graph-structured source-to-target attention instead of independent parallel chunk encoding | Llama-3.1-8B-Block on MultiHop-RAG · MultiHop-RAG Avg | accuracy: 43.32 -> 45.79 | Helped |
| use top-3 instead of top-1 retrieved chunks as source chunks (ablation) | Graph-KV on MultiHop-RAG · MultiHop-RAG Avg | accuracy: 44.81 -> 45.79 | Helped |
| use all retrieved chunks as source and target chunks (ablation) | Graph-KV on MultiHop-RAG · MultiHop-RAG Avg | accuracy: 45.79 -> 46.41 | Helped |
| use top-3 instead of top-1 retrieved chunks as source chunks (ablation) | Graph-KV on MorehopQA · MorehopQA Avg | accuracy: 37.96 -> 38.11 | Helped |
| use all retrieved chunks as source and target chunks (ablation) | Graph-KV on MorehopQA · MorehopQA Avg | accuracy: 38.11 -> 44.90 | Helped |
| use top-3 instead of top-1 retrieved chunks as source chunks (ablation) | Graph-KV on LongBench-V2 Single Document QA · LongBench-V2 Single Document QA Avg | accuracy: 29.9 -> 32.5 | Helped |
| use all retrieved chunks as source and target chunks (ablation) | Graph-KV on LongBench-V2 Single Document QA · LongBench-V2 Single Document QA Avg | accuracy: 32.5 -> 37.5 | Helped |
| use top-3 instead of top-1 retrieved chunks as source chunks (ablation) | Graph-KV on 2Wiki · 2Wiki Avg | accuracy: 73.60 -> 75.15 | Helped |
| use all retrieved chunks as source and target chunks (ablation) | Graph-KV on 2Wiki · 2Wiki Avg | accuracy: 75.15 -> 74.38 | Hurt |
| use top-3 instead of top-1 retrieved chunks as source chunks (ablation) | Graph-KV on HotpotQA · HotpotQA Avg | accuracy: 73.39 -> 75.19 | Helped |
| use all retrieved chunks as source and target chunks (ablation) | Graph-KV on HotpotQA · HotpotQA Avg | accuracy: 75.19 -> 76.17 | Helped |
| incorporate citation-reference dependencies with Graph-KV | Llama-3.1-8B-Block · Cora | accuracy: 69.55±0.30 -> 71.03 | Helped |
Surprising findings
- Graph-KV Top-3 on HotpotQA comparison/bridge and 2Wiki falls slightly short of sequential encoding on several RAG tasks, indicating sequential order can capture two-hop dependencies.
- Tuning-free APE leaves a large gap versus the fine-tuned block-attention model, suggesting fine-tuning is needed for independent encoding.
Limitations
- Evaluates only one-hop structural dependencies; multi-round propagation gives no significant gain on current tasks.
- Backbone requires post-training with block attention; Graph-KV was not directly fine-tuned, and experiments are limited to the Llama-3.1-8B family.
- Sequential encoding still matches or beats Graph-KV on some single-hop and two-hop RAG tasks.
Experimental setup
Datasets: tulu-3 2Wiki TriviaQA NarrativeQA HotpotQA Multihop-RAG MorehopQA LongBench-V2 arXiv dataset Cora Pubmed
Benchmarks: NarrativeQA TriviaQA HotpotQA 2Wiki Multihop-RAG MorehopQA LongBench-V2 Arxiv-QA Cora Pubmed
Metrics: accuracy time-to-first-token peak GPU memory
Baselines: Sequential encoding PCW APE Block-RAG Query-Only
Builds on: Block-Attention APE Parallel Context Windows Promptcache
Closest papers by meaning
- A Systematic Exploration of Knowledge Graph Alignment with Large Language Models in Retrieval Augmented Generation (AAAI 2025 · similarity 0.91)
- Simple is Effective: The Roles of Graphs and Large Language Models in Knowledge-Graph-Based Retrieval-Augmented Generation (ICLR 2025 · similarity 0.90)
- Talk like a Graph: Encoding Graphs for Large Language Models (ICLR 2024 · similarity 0.88)
- Think-on-Graph 2.0: Deep and Faithful Large Language Model Reasoning with Knowledge-guided Retrieval Augmented Generation (ICLR 2025 · similarity 0.88)
- Attention Mechanisms Perspective: Exploring LLM Processing of Graph-Structured Data (ICML 2025 · similarity 0.88)
- Harnessing Large Language Models for Knowledge Graph Question Answering via Adaptive Multi-Aspect Retrieval-Augmentation (AAAI 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.