Dependency-Aware Containers for Reusable Long-Document KV Caches

Serving systems that answer many questions over the same long documents save time by storing the key-value (KV) cache, the per-token attention states a transformer computes when it reads a prompt, and reusing it across queries. To make reuse modular, documents are cut into fixed-length segments that are encoded separately. The cost is that a segment encoded alone never sees the definition, condition, or antecedent it depends on. KVLink reports accuracy drops of up to 35% from this independent encoding. Its repair is to fix positions after the fact and add a few trained "link tokens" between segments. Those tokens are learned blindly: they do not know which segment actually needs which other segment.

We propose to borrow an idea from hybrid row/column databases. HYRISE groups table attributes that are frequently accessed together into wide containers and leaves the rest in narrow ones, choosing the layout with a cost model. We apply the same logic to document segments. First, we measure how much each segment's meaning depends on other segments, which gives a weighted dependency graph. Then we choose which segments to encode jointly by cutting that graph so that the dependence lost at the cuts is as small as possible, under a fixed memory budget. Segments that heavily reference one another go into a shared container, even when they are far apart in the document. Widely referenced material such as definitions and governing clauses goes into a small shared "scope" container that every dependent container is encoded on top of. The claim is narrow and testable. At equal cache storage and equal time to first token, dependency-chosen containers should recover more of the accuracy gap between independent encoding and full joint encoding than fixed, section-based, or learned-link segmentation. The recovered accuracy should be concentrated on questions whose evidence crosses the edges the baselines cut.

What is new relative to existing work

Three systems already work where cache layout meets fragmentation, and all of them split the cache along token position. KVLink precomputes per-segment caches and bridges them with learned link tokens. Cake splits prefill along the token axis between GPU computation and SSD loading. TableKV prunes table caches by attention score and, tellingly, loses execution accuracy on Spider even while keeping tuple-level precision. That result is a warning that statistical retention can discard the specific links that relational correctness depends on. None of the three decides which content is encoded together based on measured dependence. We take KVLink's positional re-encoding as a component, because it is what makes non-contiguous containers possible. We treat Cake as orthogonal, since it schedules computation and does not change what is stored.

Two lines of work on the fragmentation side motivate the proposal and also limit it. Late Chunking shows that context before pooling helps retrieval embeddings, about a 3.6% relative nDCG@10 gain on BeIR. It still needs a full long-context pass per document and produces vectors, not reusable generation caches. EnSI-RAG avoids naive chunking by indexing entity tuples, reaching 78.24 average accuracy on Loong and Oolong. Its authors note that the LLM extraction it requires is a barrier for frequently changing corpora. Our graph has to be cheaper to build than EnSI-RAG's index, or the comparison is unfair to them.

The dependency-mapping side supplies the method. The "thought anchors" toolkit builds causal graphs over reasoning traces by masking sentences and measuring how much later predictions change. We apply the same intervention to document segments instead of reasoning steps. CGRiC and DAG-Math argue that dependency structure, rather than surface position, is what has to be preserved for downstream claims to be sound. That is the premise we test in cache form. Unlike them, we use the graph to lay out memory, not to verify outputs.

Core Mechanism

We split a document into sentence-aligned segments $s_1,\dots,s_n$. We define the dependence of segment $j$ on segment $i$ as the average, over tokens of $s_j$, of the KL divergence between a small reference model's next-token distributions under two conditions: $s_j$ encoded alone, and $s_j$ encoded after $s_i$. We write this $d(i\to j)$.

Measuring every pair would be quadratic in $n$. We therefore score only candidate pairs proposed by cheap signals: shared entity strings, explicit cross-references ("Section 4.2", "as defined above"), and nearby positions. The result is a sparse weighted directed graph.

A layout consists of three parts. The first is a scope set $S$ of segments, encoded once as a shared prefix. The second is a partition of the remaining segments into containers $C_1,\dots,C_m$, each encoded jointly on top of $S$. The third is a width cap $W$ tokens per container. We choose the layout by solving

$$\min_{S,\{C_k\}} \sum_{(i\to j)\ \text{severed}} d(i\to j) \;+\; \lambda\,|S|\,m \quad \text{s.t.}\ |S|+|C_k|\le W\ \ \forall k.$$

An edge counts as severed when $i$ and $j$ fall in different containers and $i$ is not in $S$. The second term charges for the scope prefix being attended from every container, and $\lambda$ trades that cost against lost dependence. This is a balanced graph-partitioning problem. We will solve it greedily with local refinement and do not claim optimality.

At query time, the model loads the containers a retriever selects plus $S$. It applies global positional re-encoding as in KVLink and optionally inserts KVLink's link tokens between containers, so the two methods combine rather than compete. When a document is edited, only the containers holding changed segments, and their graph neighbors, need recomputation. This is a weak analogue of the append-then-consolidate design in L-Store, and we measure it but do not center the proposal on it.

Research Program

The work has three stages. First, we validate the dependence measure. Cutting high-$d$ edges must hurt answer accuracy more than cutting low-$d$ edges of the same total size; if that correlation is absent, the mechanism has no basis. Second, we build the layout solver and the serving path on Llama-3.1-8B-Instruct. That is the model family KVLink fine-tunes, so its link tokens can be reused rather than reimplemented. Third, we run matched-budget comparisons on multi-hop and multi-document question answering, along with an ingestion-cost accounting against EnSI-RAG-style extraction.

Baselines

The naive reference point is independent fixed-length segment caches with no repair. This is the setting KVLink reports as losing up to 35%, and it sets the floor.

The ceiling is full joint prefill of all retrieved content. It defines the gap we try to close, and we report results as the fraction of that gap recovered.

The strongest existing method is KVLink itself: positional re-encoding plus trained link tokens over fixed segments. KVLink reports beating its best baseline by 6.6% on NaturalQuestions and BlockAttention and PromptCache by 4% on average across general question answering, along with a 96% reduction in time to first token at 5,000 tokens. We found no reported absolute KVLink accuracy on HotpotQA in the file, so we will reproduce KVLink on our splits with its released recipe and link-token count. Fairness requires several things to be held equal: the same base model, the same retriever and top-k, and the same total stored cache bytes, with our scope prefix counted against the budget. Any extra fine-tuning for our variant gets the same training token budget as KVLink's link tokens. Beating KVLink means recovering a larger fraction of the full-prefill gap at matched storage and matched median time to first token, with statistical significance across three seeds.

Two structural baselines test whether dependence measurement is needed at all. One uses section-boundary segmentation with header text prepended, which is the obvious structure-aware heuristic. The other uses fixed segments enlarged to the same $W$.

Three ablations isolate the key ingredient. The random-grouping ablation keeps our container sizes but assigns segments randomly. The contiguous-only ablation forbids containers that join distant sections. The no-scope ablation removes the shared scope prefix ($S=\emptyset$).

For retrieval-side context we also report against EnSI-RAG on Loong, using its published 78.24 average.

Why not just…?

Why not just use bigger fixed chunks? Larger segments sever fewer edges simply because there are fewer boundaries. Under a fixed memory budget, though, each retrieved segment then carries more irrelevant text, and edges between distant sections, such as a definition in Section 1 used in Section 9, are still cut. This is a real threat. The matched-$W$ fixed-chunk baseline and the contiguous-only ablation settle it. If enlarged fixed chunks match us at equal bytes, the dependency graph is not earning its cost, and we would report that.

Why not just train more link tokens in KVLink? Learned links can only pass information between segments that are both loaded. If the retriever fetches a segment without its antecedent, no link token can recover the missing content. Co-locating a segment with its antecedent fixes exactly this failure. We test it by splitting evaluation questions according to whether gold evidence spans a cut made by the baseline layout. We also run KVLink with doubled link tokens and give our method the same training budget.

Why not just retrieve a few chunks and prefill them jointly at query time? When top-k is small, joint prefill is affordable, and Cake makes it faster still. This baseline beats ours on accuracy by construction. Our case rests on the reuse regime, where many queries hit the same documents and per-query prefill dominates latency. We will report the crossover point in queries per document at which precomputed containers become cheaper overall. If that point is unrealistically high, the proposal applies only narrowly.

Why not just use EnSI-RAG's entity index? It fixes retrieval granularity but still hands the generator text to prefill. Its offline LLM extraction is also costly on corpora that change often. We compare ingestion GPU-seconds per document, and accuracy on Loong, at matched generation budgets.

Proposed Experiments

We evaluate on HotpotQA and NaturalQuestions, which KVLink uses, and on Loong's chain-of-reasoning and spotlight-locating tasks, where dependencies cross documents and sections. Metrics are exact match and F1, fraction of the full-prefill gap recovered, stored cache bytes, median and p95 time to first token, ingestion compute, and recomputation cost after simulated edits that rewrite 5% of segments. As a secondary check that containers also make better retrieval units, we pool the container caches into embeddings and score them on ConTEB against EBCAR's reported nDCG@10 of 64.92 from Embedding-Based Context-Aware Reranker. We treat this as exploratory.

Three outcomes are decisive. First, within each layout, the measured severed dependence must predict per-question accuracy loss. Second, at matched bytes and latency, dependency containers must beat both enlarged fixed chunks and KVLink, with the gain concentrated on questions whose evidence crosses a baseline cut. Third, random grouping at identical container sizes must lose most of that gain. If the first check fails, the measure is wrong. If the second fails while the first holds, simple segmentation already captures the useful structure, and the result is a negative one worth publishing.