⚡🔗 Caching Hyperedges: KV-Cache Reuse for Hypergraph RAG

Hypergraph-based retrieval captures n-ary relational facts that binary-graph methods fragment, but answering a query is slow: the model must read the text of all retrieved units before generating a response. We present Cachy, which removes this reading cost by precomputing a key-value (KV) cache for each retrieval unit and reusing it whenever a query retrieves that unit. Because retrieval is hyperedge-grounded, each cached unit is a short, self-contained passage, so caches fuse at query time without fine-tuning and with no detectable loss in generation quality. Demand caching combined with INT8/INT4 quantization and 50% K-norm token pruning cuts storage from 1.9 TB to 109 GB, while mean query time drops from 21.61 s to 8.52 s — matching the latency of lightweight RAG at higher retrieval fidelity.

---

📊 Data Source

• UltraDomain: A multi-domain benchmark with long-form contexts and annotated QA pairs, covering five domains:

Domain	Questions
Medicine	180
Law	438
Computer Science	100
Agriculture	100
Mix	130
Total	948

202 documents, ~600 MB of text. Corpora are relation-dense and heterogeneous, making them a natural testbed for hypergraph retrieval.

The datasets used for evaluation can be found in the data/ folder of this repository.

---

🛠️ Technologies Used

• Large Language Model: Mistral-7B-Instruct-v0.2 — used for entity and n-ary relation extraction, KV cache precomputation, and answer generation.
• Embedding Model: all-MiniLM-L6-v2 (384 dimensions) — used for semantic indexing and reranking.
• Vector Store: NanoVectorDB — two separate instances for the entity index and hyperedge index.
• KV Cache Quantization: Absolute-maximum INT8/INT4 quantization for storage compression.
• Token Pruning: K-norm pruning (H2O / SnapKV) — retains the top-ρ tokens by key norm, ρ = 0.5.
• LLM-as-judge: gpt-4o-mini — used to evaluate generation quality (G-E metric) across 7 dimensions.

---

📑 Methodology

Cachy operates in two phases:

1. Offline — Hypergraph and Cache Construction: The corpus is segmented into fixed-length chunks. An LLM extracts entities and n-ary relations from each chunk, building a knowledge hypergraph H = (V, E). Entities and hyperedges are indexed in two vector stores. For each source chunk, a single forward pass through the model precomputes and serializes its KV cache to disk. Caches are keyed by chunk and shared across all incident hyperedges.

2. Online — Query Pipeline: A query is embedded and used to query both vector indices in parallel. Candidate chunks are reranked by cosine similarity, their precomputed KV caches are loaded into GPU memory, concatenated layer by layer with RoPE positional re-encoding, and the model generates the answer attending only to the fused prefix — never re-reading the retrieved text.

The full implementation is available in the cachy/ module of this repository.

Overview

Cachy pipeline. (A) Offline: an LLM extracts entities and n-ary relations from the corpus to build a knowledge hypergraph, and a KV cache is precomputed and stored for each source chunk. (B) Online: a query retrieves candidate chunks via dual vector-index lookup, reranks them by cosine similarity, fuses their precomputed KV caches into a prefix, and the model generates the answer from the query tokens alone.

---

✨ Key Features

• No fine-tuning required. KV caches fuse at query time via RoPE positional re-encoding; the model is used as-is.
• No detectable quality loss. Paired Wilcoxon signed-rank tests (FDR-corrected, n = 948) show no statistically significant difference from the uncached hypergraph pipeline on F1 (p = 0.17) or G-E (p = 0.06).
• 2.5× end-to-end speedup. Mean query time drops from 21.61 s to 8.52 s, reaching lightweight-RAG latency while preserving hypergraph retrieval fidelity.
• Storage-tractable. Demand caching + INT4 quantization + 50% K-norm pruning reduces storage from 1.9 TB (eager FP16) to 109 GB on the benchmark workload.
• Hyperedge-grounded retrieval. Unlike chunk-level caching, Cachy organizes cached evidence by n-ary facts rather than passage boundaries, preserving retrieval fidelity (ΔR-S = +2.78 vs. ChunkCache, p = 10⁻¹³).

---

🏆 Results

Latency

Method	Total (s)	Retrieval (s)	Rerank (s)	Generation (s)
NaiveGeneration	3.51	—	—	3.51
StandardRAG	6.96	1.57	—	5.39
LightRAG	8.97	2.80	0.33	5.84
HyperGraphRAG (no cache)	21.61	2.37	0.35	18.89
Cachy (Demand INT4 + prune 50%)	8.52	0.27	0.32	7.93

Cache Configurations

Configuration	Chunks	Quantization	Pruning	Disk size
Chunk cache (eager)	12,055	FP16	—	1.9 TB
Demand INT8	5,509	INT8	—	436 GB
Demand INT8 + prune 50%	5,509	INT8	50%	218 GB
Demand INT4	5,509	INT4	—	218 GB
Demand INT4 + prune 50%	5,509	INT4	50%	109 GB

All latency figures are warm-cache, closed-workload measurements. The cache-miss hybrid path is not separately profiled.