💬 NLP

KV-Fold: One-Step KV-Cache Recurrence for Long-Context Inference

KV-Fold is a simple, training-free long-context inference protocol that treats the KV cache as a left-fold accumulator to enable stable, memory-efficient sequence processing across deep chains without requiring model retraining or architectural changes.

Original authors: Alireza Nadali, Patrick Cooper, Ashutosh Trivedi, Alvaro Velasquez

Published 2026-05-13

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Alireza Nadali, Patrick Cooper, Ashutosh Trivedi, Alvaro Velasquez

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you have a brilliant, super-smart librarian (the AI model) who can read a book and answer questions about it. But there's a catch: this librarian has a very small desk. They can only hold a few pages of the book open at once. If you give them a 1,000-page novel, they can't read the whole thing at once without their desk overflowing.

Usually, to solve this, we tell the librarian to either:

Forget the beginning: Only look at the last few pages (like a sliding window).
Summarize the past: Try to compress the whole story into a tiny note (which often loses details).
Build a bigger desk: Which is expensive and often impossible for huge books.

KV-Fold is a new, clever trick that lets the librarian read the entire book without needing a bigger desk, without summarizing, and without forgetting the beginning.

The Core Idea: The "Folding" Trick

Think of the book as a long strip of paper. Instead of trying to read the whole strip at once, you cut it into small, manageable chunks.

The First Chunk: The librarian reads the first chunk. As they read, they take notes on a special "sticky note" (this is the KV Cache). This note contains the essence of what they just read, but in a way that allows them to look back at specific details later.
The Next Chunk: When they move to the second chunk, they don't throw away the first sticky note. Instead, they tape the new notes from the second chunk right next to the first ones. Now they have a longer strip of notes.
The Recurrence: They keep doing this. Read a chunk, add the notes to the growing strip, and move to the next chunk.

The paper calls this a "Left Fold." Imagine folding a long piece of paper over and over. Each fold adds a new layer, but the previous layers are still there underneath, accessible. The librarian carries this growing stack of notes forward, step by step.

The Big Surprise: It Doesn't Get "Messy"

You might think, "If I keep adding notes to a stack, eventually the librarian will get confused. The notes from page 1 might get lost in the noise of page 500."

The paper discovered something amazing: The librarian doesn't get confused.

The "Drift" Plateau: At first, when the librarian switches from the first chunk to the second, their thinking style shifts slightly (like adjusting to a new room). But after just a few steps, this shift stops. It hits a "flat plateau."
Stable State: Even after reading hundreds of chunks (up to 511 steps in their tests), the librarian's performance doesn't get worse and worse. It stays stable. It's as if the librarian found a comfortable rhythm and stuck to it.
Precision Doesn't Matter: Even if you change the "ruler" the librarian uses to measure things (changing from high-precision math to low-precision math), the result stays the same. The stability is built into the logic, not just the math.

The "Needle in a Haystack" Test

To prove this works, the researchers played a game called "Needle in a Haystack."

The Game: They hid a specific sentence (the "needle") deep inside a massive document (the "haystack").
The Test: They asked the librarian to find that sentence after reading the whole document.
The Result:
- Old Methods (Streaming): If the needle was in the first few pages, the librarian found it. If the needle was in the middle or end, the librarian forgot it because the "desk" was too small.
- KV-Fold: The librarian found the needle 100% of the time, even if it was buried at the very beginning of a 128,000-word document. They could recall the exact details from the very first chunk, even after reading hundreds of chunks since then.

Why This Matters (Without the Jargon)

No Re-training: You don't need to teach the librarian a new way of thinking. You just change how you hand them the book. The librarian is already smart enough to do this; we just gave them a better workflow.
Memory Trade-off: The librarian still needs to keep all the notes (the KV cache) on their desk. So, the desk grows as the book gets longer. However, this is much better than trying to hold the entire book in your head at once, which is impossible for current computers.
Exact Recall: Unlike methods that summarize or throw away old pages, KV-Fold keeps every detail accessible. If you ask about something from the very first sentence, the librarian can still find it.

Summary Analogy

Imagine you are telling a long story to a friend.

Old Way: You only remember the last 5 minutes of the story. If I ask about the beginning, you say, "I don't know."
KV-Fold Way: You keep a running list of every character and plot point you've mentioned so far. As you tell the next part of the story, you glance at your list to remember who everyone is. Even though the list gets longer, you don't get confused by it. You can still answer, "What was the name of the dog from the very first sentence?" because that name is still on your list, perfectly preserved.

The paper shows that AI models already have this "list" capability built-in. We just needed to realize we could use it as a repeating loop to read infinite-length books without breaking the computer's memory.

Technical Summary: KV-Fold

Problem Statement

Large pretrained transformers are constrained by the quadratic memory cost of full attention and the fixed context window of a single forward pass. While recent models support context windows up to hundreds of thousands of tokens, real-world workloads (e.g., repository-scale code, longitudinal medical records) often exceed these limits. Existing solutions face a persistent trade-off:

Streaming methods (e.g., StreamingLLM) maintain bounded memory by retaining only recent tokens and "attention sinks," but they lose the ability to retrieve information once it falls outside the sliding window.
KV-cache compression and recurrent memory methods often require model modification, fine-tuning, or introduce lossy approximations that degrade retrieval fidelity.
Full attention is computationally infeasible for extremely long sequences on standard hardware due to the massive size of the attention score matrix (e.g., ~1 TB for a 128K sequence on a 40GB GPU).

The paper asks whether a frozen, pretrained transformer can carry its internal state across successive chunks to perform long-context inference as a recurrence, without architectural changes or training.

Methodology: KV-Fold

The authors propose KV-Fold, a training-free inference protocol that treats the Key-Value (KV) cache as the accumulator in a left fold (foldl) over sequence chunks.

Mechanism: A long sequence of length $T$ $T$ is divided into chunks of length $C$ $C$ . When processing chunk $t$ $t$ , the model performs a forward pass where:
1. The queries ( $Q$ ) are generated from the current chunk's tokens.
2. The keys ( $K$ ) and values ( $V$ ) are formed by concatenating the KV cache accumulated from all previous chunks ($0$ to $t-1$ ) with the current chunk's KV states.
3. Positional embeddings (RoPE) are applied continuously across chunk boundaries to maintain absolute sequence alignment.
4. The enlarged KV cache is passed forward to chunk $t+1$ .
State: The model parameters remain frozen. No special memory tokens or fine-tuning are introduced. The KV cache grows linearly with the sequence length, acting as a structured, uncompressed record of the model's past computation.
Analogy: The process is analogous to a functional programming left fold, where the KV cache serves as the accumulator state updated by a single-step recurrence function $F_\theta$ at each chunk boundary.

Key Contributions

KV-Fold Protocol: A simple, operational shift that converts a standard transformer into a recurrent long-context model by carrying the accumulated KV cache across chunks.
Stability of Recurrence: Empirical evidence showing that the induced recurrence does not suffer from unbounded error accumulation. Instead, the "drift" (difference in Negative Log-Likelihood compared to full attention) rises briefly and then saturates into a flat plateau that persists across deep chains.
Structural vs. Numerical Drift: The plateau is shown to be a structural property of the attention dynamics rather than a numerical artifact. It remains stable under a 10,000× increase in numerical precision (from bf16 to fp32) and is robust across different model families (OLMoE, Qwen, Llama) and chunk sizes.
Exact Long-Range Retrieval: The method preserves exact factual information over long distances. On "needle-in-a-haystack" benchmarks, KV-Fold achieves 100% exact-match retrieval across contexts up to 128K tokens and chain depths up to 511, matching full-attention performance.
Practical Trade-offs: The paper characterizes the method's position on the memory-versus-retrieval spectrum. While it requires linear memory growth (unlike bounded-memory streaming), it enables retrieval at arbitrary depths where streaming methods fail, making it feasible to run full-attention-equivalent retrieval on hardware that cannot support a single monolithic forward pass.

Key Results

Drift Saturation: On Qwen2.5-7B-Instruct, drift saturates by depth 7 and remains flat through depth 63, with a total change of only -0.0003 nats between depths 15 and 60.
Retrieval Performance:
- Single Needle: 100% retrieval accuracy across 152 trials spanning contexts from 16K to 128K tokens and chain depths up to 511 on Llama-3.1-8B.
- Multi-Needle: 99.4% retrieval accuracy (175/176) when retrieving multiple distinct facts simultaneously.
Hardware Feasibility: On a 40GB A100 GPU, a single full-attention forward pass for a 128K sequence is infeasible (requiring ~1 TB for attention scores). KV-Fold processes the same sequence in 171 seconds with a peak memory usage of 35.6 GB, staying within hardware limits.
Comparison to StreamingLLM: At 128K context, StreamingLLM maintains bounded memory (16.6 GB) and faster runtime (22s) but drops to 0% retrieval once the "needle" exits its 1024-token window. KV-Fold maintains 100% retrieval at all tested distances but requires higher memory (35.6 GB) and longer runtime.

Significance and Claims

The paper claims that frozen pretrained transformers already support a stable form of KV-cache recurrence. The primary significance is demonstrating that long-context inference does not strictly require architectural changes, training, or lossy compression to achieve high-fidelity retrieval.

The authors argue that KV-Fold reveals a "slightly shifted but stable attention regime" where the model can recursively process information without degrading its ability to access specific past tokens. This provides a practical route to extending context windows on existing hardware by trading linear memory growth for the ability to perform exact retrieval over sequences that would otherwise be truncated or approximated. The paper concludes that while the method does not reduce total FLOPs or memory below full attention, it reorganizes computation into tractable steps, making long-context inference feasible where it was previously impossible. Future work suggested includes modest fine-tuning to reduce residual drift and combining the method with position-extension techniques to push beyond native context limits.