FuseRAG: Fusing Structure and Evidence into Inference for Cost-Efficient Graph-based RAG

I. INTRODUCTION

• Serialization can separate related entities across distant positions, making reasoning paths harder to trace even when the retrieved evidence is unchanged.Query-aligned serialization can instead place adjacent sentences along a continuous reasoning chain.Source: §I · p. 1, Figure 1 · p. 1
• Different serialization orders for equivalent evidence undermine KV-cache reuse, while jointly optimizing structural ordering and cache reuse involves trade-offs and an NP-hard ordering problem.Conventional reuse assumes identical token prefixes.Source: §I · p. 2
• FuseRAG integrates graph evidence and structural interactions through latent representations, retaining only a small amount of explicit evidence as semantic anchors.The paper reports that this design significantly improves inference efficiency.Source: §I · p. 2
• Up to 2.7× and 2.2× TTFT speedups over the fastest graph-based baseline accompany improved QA performance on Llama-3-8B and Qwen3.5-9B, respectively.Experiments cover three multi-hop QA datasets.Source: §I · p. 2

A. Graph-based RAG

• Different serialization orders preserve the same graph evidence but can change inference because connected evidence may be far apart and LLMs exhibit positional biases.Graph-based RAG retrieves relevant entities and relations as evidence for multi-hop reasoning.Source: A. Graph-based RAG · pp. 2–3

B. KV-Cache Reuse in LLM Inference

• KV-cache reuse avoids repeated prefill only when a new input shares an identical token prefix with a cached input, a condition inconsistent graph serializations often prevent.RAG prefill cost rises with context length, and retrieved evidence can form most of that context.Source: B. KV-Cache Reuse in LLM Inference · p. 3

C. Challenges in Serialization-Order Optimization

• Structural cost measures weighted distances between connected nodes in the serialized order, and minimizing it is NP-hard; cache reuse instead favors orders with longer shared token prefixes.Jointly optimizing the objectives is computationally intractable because cache reuse may conflict with structural locality.Source: C. Challenges in Serialization-Order… · p. 3

III. METHODOLOGY

• FuseRAG shifts graph evidence from textual serialization to latent representations to preserve graph structure while enabling efficient KV-cache reuse.Its execution flow has evidence retrieval, dual-path evidence representation, and LLM integration stages.Source: §III · p. 3, A. Overview · p. 3

A. Overview

• The dual-path stage combines reusable token-level latent evidence and graph-encoded structural dependencies with compact query-aware textual facts under a strict token budget.The overview identifies the compact facts as semantic anchors and notes that only a small amount of evidence is serialized.Source: A. Overview · p. 4, Figure 2 · p. 4

B. Evidence Retrieval

• The implemented selector progressively expands a partial subgraph by greedily choosing the highest-scoring neighbor action or stopping, then passes the selected evidence and subgraph onward.Its action score includes query relevance and complementary information; retrieval can also stop when the estimated remaining utility is nonnegative.Source: B. Evidence Retrieval · p. 4

1) Latent Evidence Encoding:

• Each evidence unit is independently encoded into reusable token-level states; query cross-attention and graph message passing add query-aware evidence summaries and structural auxiliary states.The latent memory combines evidence states with graph-aware auxiliary representations, and the encoder implementation uses GAT.Source: 1) Latent Evidence Encoding · pp. 4–5

2) Explicit Fact Anchoring:

• FuseRAG extracts query-aware facts as semantic anchors because latent representations lack direct textual grounding, selecting complete clauses under a strict token budget.Evidence omitted from the explicit anchor text remains available through the latent path.Source: 2) Explicit Fact Anchoring · p. 5

D. LLM Integration

• Latent memory enters decoder inference through key–value states, while explicit facts remain in the prompt as direct semantic grounding.The two evidence paths use memory attention and the standard decoder path, respectively.Source: D. LLM Integration · p. 5

1) Memory Projection:

• A lightweight adapter maps evidence-encoder representations into the decoder’s key–value space at selected layers.The adapter uses separate low-rank projections for memory keys and values.Source: 1) Memory Projection · p. 5
• Each decoder layer has independent adapter parameters, and its projected memory states preserve token positions and are computed once for reuse during decoding.The key and value projections separately learn how evidence is matched and read in each layer’s attention space.Source: 1) Memory Projection · p. 5

2) Joint Attention:

• At selected injection layers, FuseRAG concatenates textual and memory states along the key–value sequence dimension for joint attention.The textual input contains the query and explicit anchors.Source: 2) Joint Attention · p. 5
• Attention masks enforce causal and memory-validity constraints, while a separate term controls preference for memory positions.Source: 2) Joint Attention · p. 5
• Shared softmax normalization lets memory keys affect attention weights; aggregated memory values alter decoder hidden states, logits, and token probabilities.As decoding proceeds, changing decoder queries can attend to different positions while latent memory stays fixed.Source: 2) Joint Attention · p. 5

E. Training and Inference

• Training optimizes latent-path components with autoregressive language-modeling loss, while retrieval and explicit anchoring are deterministic and require no additional training.The objective trains latent representations and their integration into decoder attention for answer generation.Source: E. Training and Inference · p. 6
• At inference, cached evidence states are reused when available, and query-specific memory key–value states are computed once for reuse across decoding steps.Evidence states can be shared across queries when the same evidence recurs; within generation, latent memory remains fixed.Source: E. Training and Inference · p. 6

• Retrieval candidate scoring has an upper bound of O(cmaxK^2ds) for at most K expansion steps and at most cmax candidate actions per step.This bound covers direct candidate scoring with precomputed node and relation embeddings.Source: §IV · p. 6
• Stage 2 combines evidence encoding, query representation, query-aware graph processing, and explicit-anchor extraction; query-aware pooling and graph encoding are recomputed for each question.The passage gives anchor-extraction cost O(Waux + kW + UD + Fτ), including O(Fτ) knapsack time.Source: §IV · p. 6
• Stage 3 projects memory once per question and reuses its key–value states, while memory attention still adds O(J(n + a)LMd) computation.The stated Stage 3 total is C3 = Cproj + Ctext + Cmem.Source: §IV · p. 6
• FuseRAG reduces decoding attention computation when L(p − n) > JLM, a condition the paper says is typically achievable when J ≪ L.The method adds memory attention across prefill and decoding, but latent memory positions avoid tokenwise projections and feed-forward networks at every decoder layer.Source: §IV · p. 6
• Lower total storage is not guaranteed: FuseRAG reduces textual KV-cache storage but adds evidence and memory states, and practical cache lookup and transfer latency are excluded.The storage comparison excludes temporary activations.Source: §IV · p. 7

1) Datasets:

• The evaluation samples 1,000 validation questions from each of MuSiQue, HotpotQA, and 2WikiMultiHopQA and uses Llama-3-8B and Qwen3.5-9B.The datasets cover composed multi-hop reasoning, questions over multiple Wikipedia articles, and questions built from Wikipedia and Wikidata with explicit reasoning paths.Source: 1) Datasets · p. 7

2) Metrics:

• Effectiveness is measured by average accuracy and F1, while efficiency includes token consumption, runtime latency, and time to first token.TTFT measures the delay from query submission until the first answer token; end-to-end latency measures total query completion time.Source: 2) Metrics · p. 7

3) Comparison Methods:

• The comparisons include zero-shot and conventional VanillaRAG baselines, graph-based methods, and FuseRAG configurations with explicit-fact budgets of 32, 64, or 128.The graph-based set includes KGP and G-Retriever.Source: 3) Comparison Methods · pp. 7–8

• Experiments used a unified framework with default configurations and two NVIDIA RTX PRO 6000 GPUs.Source: 4) Implementation · p. 8

B. Main Results

• Ours-128 achieves the highest F1 and accuracy on all three datasets with Llama-3-8B; Qwen3.5-9B shows the same trend.On Llama-3-8B, Ours-128 F1 is 41.08%, 63.05%, and 55.35% on MuSiQue, HotpotQA, and 2WikiMultiHopQA, respectively.Source: B. Main Results · p. 8
• FuseRAG has lower TTFT than RAPTOR and VanillaRAG across the reported backbones and corresponding settings.Llama-3-8B TTFT is 44.26–65.74 ms versus RAPTOR's 107.25–132.55 ms; Qwen3.5-9B TTFT is 141.82–174.52 ms versus RAPTOR's 247.36–306 ms.Source: B. Main Results · pp. 8–9

C. Efficiency

• FuseRAG configurations generally occupy Figure 3's upper-left region, indicating competitive or higher F1 with lower TTFT and token consumption.The figure plots F1 against logarithmic TTFT or token cost; 128-token FuseRAG achieves the highest F1 on all three Llama-3-8B datasets.Source: Figure 3 · p. 9, C. Efficiency · p. 9

B. Main Results

• On HotpotQA with Llama-3-8B, 32-token FuseRAG reaches 51.19% F1, comparable to KET-RAG's 51.75%, while reducing TTFT from 1212.31 ms to 44.26 ms.A 64-token budget strikes a balance between QA performance and inference efficiency in these experiments.Source: B. Main Results · p. 9

C. Efficiency

• FuseRAG consistently reduces textual token consumption and end-to-end inference time versus representative graph-based RAG baselines on both backbones.Extensive evidence serialization and iterative LLM processing incur higher overhead; FuseRAG retains compact explicit facts while incorporating richer evidence and graph structure through latent representations.Source: C. Efficiency · pp. 9–10
• Shorter contexts reduce decoder computation, while latent memory is accessed only at selected Transformer layers.Reusable evidence representations eliminate redundant encoding across queries without requiring identical serialized prefixes; reduced token consumption accompanies lower end-to-end inference time.Source: C. Efficiency · p. 10

E. Ablation Study

• Removing explicit anchors lowers F1 from 30.40% to 23.14% and accuracy from 28.72% to 23.88%, with only a 1.06× speedup.Removing latent memory lowers F1 to 22.63 and accuracy to 18.50%, despite a 2.21× speedup; compact facts alone do not match the full model.Source: E. Ablation Study · pp. 10–11
• Removing query conditioning lowers F1 by 6.94% and accuracy by 8.39%, while removing graph fusion lowers F1 to 26.48 and accuracy to 22.20%.Query conditioning directs question-relevant evidence pooling; graph fusion propagates information among connected passages and provides additional benefits at a relatively small observed latency cost.Source: E. Ablation Study · p. 11
• Replacing token-level memory with passage-level memory gains a 1.33× speedup but reduces F1 to 23.91% and accuracy to 20.45%.Token-level memory exposes multiple evidence positions for selective access to finer-grained information.Source: E. Ablation Study · p. 11
• Evidence reuse leaves F1 and accuracy unchanged while reducing TTFT from 81.49 to 61.48, a 24.6% reduction relative to online re-encoding.The ablations identify complementary quality contributions from textual anchors, fine-grained latent evidence, and query-conditioned structural fusion.Source: E. Ablation Study · pp. 10–11
• Increasing the explicit token budget from 0 to 256 generally improves accuracy and F1, with gains generally diminishing between 128 and 256 tokens.Qwen3.5-9B is particularly sensitive to τ = 0 on MuSiQue, while Llama-3-8B retains higher performance; smaller budgets need latency measurements to assess the efficiency trade-off.Source: E. Ablation Study · p. 11, Figure 5 · p. 11
• Accuracy and F1 improve from zero to two graph message-passing rounds across both models and all three datasets, then decrease slightly at three rounds.Two rounds provide the best answer quality among evaluated settings; the results do not establish oversmoothing as the cause of the decline.Source: E. Ablation Study · pp. 11–12, Figure 6 · p. 11

A. Graph-based RAG

• Graph-based RAG work covers hierarchical and relational indexing, graph retrieval, and online traversal, including RAPTOR, GraphRAG [44], LightRAG, and ToG.FuseRAG instead separates reusable evidence content from query-dependent graph interactions and integrates both into decoder attention alongside textual anchors.Source: A. Graph-based RAG · p. 12

B. Latent Evidence Integration

• Prior latent-context methods compress contexts into summary vectors or memory slots, while FuseRAG integrates evidence semantics and graph structure in latent space for multihop reasoning.The passage contrasts this with approaches that may lose fine-grained semantics or overlook graph relationships.Source: B. Latent Evidence Integration · p. 12

C. Efficient RAG Inference

• Existing caching methods reuse or adapt decoder KV states derived from serialized text, whereas FuseRAG caches query-independent evidence representations and adds graph interactions in latent space.This reduces redundant computation and prefill overhead without requiring identical token prefixes.Source: C. Efficient RAG Inference · p. 12

VII. CONCLUSION

• FuseRAG combines compact textual anchors with latent evidence and graph interactions, and experiments across three multi-hop QA datasets and two LLM backbones show favorable answer-quality and inference-efficiency trade-offs.The framework reuses evidence states and memory K/V across decoding steps without verbalizing the complete retrieved graph.Source: §VII · p. 12