Training-free · KV-cache eviction · long-context LLMs

LORE-KV: Monte Carlo Estimation
for KV-Cache Eviction

Lookahead Output-perturbation with Reliability-weighted Ensembles for Key-Value caches

Ahsan Bilal¹Muhammad Ahmed Mohsin² Muhammad Umer²Wajih Hassan Raza³ Atta Ul Asad⁴Young D. Kwon⁵ Michal Valko⁶Dean F. Hougen¹

¹University of Oklahoma²Stanford University ³University of Houston⁴Lahore University of Management Sciences ⁵University of Cambridge⁶Isara Labs

Most eviction methods ask which memory looked important while reading the prompt.
LORE-KV asks which memory will matter while answering.

arXiv 2610.07643 PDF Code BibTeX

LORE-KV pipeline: prefill, Monte Carlo lookahead, reliability weights, projected deletion score, eviction and decoding

TL;DR. Before evicting, LORE-KV samples a few short continuations from the frozen model, treats their query states as Monte Carlo samples of the queries it will issue while answering, and keeps the tokens whose deletion would most change the attention output under those queries. The continuations are discarded; nothing is trained.

+2.75

LongBench points on Qwen2.5-14B at B = 128 (45.49 → 48.24)

+5.85

RULER-16K points on Mistral-7B at B = 128 (45.20 → 51.05)

+11.65

RULER-128K points over AnDPro on Llama-3.1-8B at B = 128

1.5–1.6×

less KV cache than AnDPro at equal LongBench accuracy (Mistral-7B)

The query-reference mismatch

Eviction happens once, after prefill and before any answer token exists, so the queries that will read the cache are unknown. What should a token's importance be measured against?

Prompt-side eviction

Score with the last prompt queries $Q_W$

SnapKV, Ada-KV, CriticalKV and AnDPro rank tokens by how the last $w$ prompt tokens attend to them. When answer-time queries differ, tokens the answer needs are evicted, and the loss grows with the mismatch.

LORE-KV

Score with sampled answer-time queries

Short continuations sampled from the model itself give a Monte Carlo estimate of the queries it will issue. Tokens are ranked by the projected change of the attention output their deletion would cause under those queries.

Method

Algorithm 1 of the paper. Steps 2-4 are a one-time test-time computation of $M\times T$ sampled tokens and $w+MT$ scoring queries; decoding then runs on the compressed cache at the same cost as any method at budget $B$.

Prefill

Run the prompt $X=(x_1,\dots,x_n)$ once, keeping the full cache $K,V$ and the window queries $Q_W$ of the last $w=32$ tokens. The attention sink and the window form the protected set.

Monte Carlo lookahead Eq. 1

Sample $M$ continuations of $T$ tokens from the frozen model and record their query states:

$$Y^{(m)}\sim f_\theta(\cdot\mid X),\qquad Q^{(m)}_{\mathrm{look}}=\{q^{(m)}_1,\dots,q^{(m)}_T\},\qquad m=1,\dots,M.$$

Reliability weights Eqs. 2-4, 10

The centered score separates how atypical a sampled token was from how uncertain its context was, and has zero conditional mean. Trajectories are weighted softly:

$$c_u=\log q(y_u\mid h_u)+H\big(q(\cdot\mid h_u)\big),\qquad R_m=\beta\,\bar c_m-\gamma\,\bar H_m-\lambda_D\,\hat D_m,\qquad \omega=\operatorname{softmax}(R),$$

where $\hat D_m$ is the standardized cosine disagreement of trajectory $m$'s queries with the others. LORE-KV /E uses $(\beta,\gamma,\lambda_D)=(1,1.3,0)$, LORE-KV /D uses $(1,1,0.3)$.

Projected deletion score Eqs. 5-7

Removing token $i$ and renormalizing changes the attention output in closed form. Its impact is measured in the residual stream through the head's output projection, then aggregated over the window and the weighted trajectories:

$$\Delta o_{q,i}=\frac{a_{q,i}}{1-a_{q,i}+\epsilon}\,(v_i-o_q),\qquad e_{q,i}=\big\|W_O\,\Delta o_{q,i}\big\|,\qquad S_i=\psi(E_{i,W})+\lambda_L\sum_{m=1}^{M}\omega_m\,\psi(E_{i,m}).$$

Evict and decode Eq. 8

Each KV head keeps the protected set and its top-$B$ tokens by $S_i$. The continuations are discarded, and the answer is decoded greedily from the compressed cache.

Walk-through

Hyperparameters

Symbol	Meaning	Default
$w$	prompt observation window	32
$M,\,T$	lookahead trajectories, tokens per trajectory	4, 8
$\lambda_L$	weight of the lookahead term in $S_i$	1.0
$(\beta,\gamma,\lambda_D)$	reliability coefficients (/E; /D uses (1, 1, 0.3))	(1, 1.3, 0)
$\epsilon$, chunk	renormalization guard, adjacent-token grouping	$10^{-6}$, 4
$\alpha,\kappa,\tau,\lambda_k,\lambda_v$	plug-ins: robust aggregation, adaptive budgets, diversity selection	off

Results

All methods share budgets, observation window, chunk size and selector, on four dense and two hybrid-attention backbones. Gains are largest under tight budgets and shrink as the budget grows.

LongBench average, B = 128	Full cache	CriticalKV	AnDPro	LORE-KV /E	LORE-KV /D
Mistral-7B-Instruct-v0.2	42.51	38.42	38.96	40.28	40.21
Llama-3.1-8B-Instruct	49.29	44.62	46.06	46.11	46.27
Qwen2.5-14B-Instruct	49.37	43.47	45.49	48.16	48.24
Ministral-3-8B-Instruct-2512	49.67	44.79	46.74	47.30	47.24
Qwen3.5-9B (hybrid)	52.97	46.30	46.89	48.49	48.57
Gemma-4-12B-it (hybrid)	27.27	19.74	20.21	20.85	20.93

RULER accuracy versus KV budget — **RULER, 4K-16K.** 13-task average versus budget for Mistral-7B (top) and Llama-3.1-8B (bottom).

KV-cache efficiency at equal accuracy — **Equal-accuracy efficiency.** LORE-KV matches AnDPro's LongBench accuracy with 1.50-1.63× less cache.

Long context: RULER at 64K and 128K

Llama-3.1-8B, B = 128	64K	128K
CriticalKV	34.82	30.28
AnDPro	49.62	39.40
LORE-KV /E	57.75	51.05
LORE-KV /D	57.29	51.04

RULER average versus context length up to 128K — The margin over AnDPro grows with context length, from +4.21 at 4K to +11.65 at 128K.

Why it works

Mechanism analyses use the deployed scoring code and, retrospectively, the queries the model really issued while answering with the full cache.

Query states and coverage versus M — **Monte Carlo future-query estimation.** Sampled lookahead queries move toward the true answer-time queries; coverage of those queries rises from 0.785 (prompt window) to 0.811 and saturates near M = 4.

Gain versus mismatch — **Gain grows with mismatch.** Per-example gains in oracle recall and output fidelity increase with the prompt-to-future query mismatch.

Attention-output fidelity — **Output fidelity.** The retained cache reproduces full-cache attention outputs more closely (0.873 → 0.905 on LongBench).

More analyses

**Criterion comparison** against the future-query oracle.

**Retention-order shift**: about 20% of retained tokens change at B = 128.

Retention by token class — **Token classes**: answer-bearing evidence is enriched.

Layer and head structure — **Layers and heads**: the signal is spread across the network.

**Budget equivalence** under behavioral fidelity.

Needle in a haystack — **Needle-in-a-haystack**, Llama-3.1-8B, B = 1024.

**Accuracy-memory trade-off** against OBCache, CAOTE and Expected Attention.

Cost

At a fixed budget every method has the same decoding memory and per-token cost. LORE-KV adds a one-time lookahead and scoring step, 1.46-2.77× AnDPro's per-sample time; it stays ahead of AnDPro scoring the same continuations at every matched lookahead-token budget.

Latency breakdown and quality versus latency — **Latency.** Stage-wise time per sample and quality versus total latency (Mistral-7B).

Matched lookahead-token budget — **Matched compute.** LongBench average versus lookahead tokens M×T at B = 128.

Run it

Every experiment is one config on one benchmark. See the repository README for installation and the map from each table and figure to its config.

git clone https://github.com/AhsanBilal7/train_free_kv.git lorekv && cd lorekv
uv venv --python 3.11 .venv && source .venv/bin/activate
uv sync && make install

# LORE-KV /E on LongBench with Mistral-7B, budgets 128-1024
python scripts/sweep.py --benchmark LongBench --config config/lorekv-ent-unif-topk.conf

Limitations

Every request pays a one-time lookahead and scoring overhead.
Eviction is irreversible, and cross-head and cross-layer interactions are not modeled.
Gains shrink at large budgets and coexist with task-level regressions.
On hybrid backbones the per-trajectory cache copy can exceed device memory at very long context.

Citation

@article{bilal2026lorekv,
  title   = {Monte Carlo Estimation for {KV} Cache Eviction},
  author  = {Bilal, Ahsan and Mohsin, Muhammad Ahmed and Umer, Muhammad and Raza, Wajih Hassan
             and Asad, Atta Ul and Kwon, Young D. and Valko, Michal and Hougen, Dean F.},
  journal = {arXiv preprint arXiv:2610.07643},
  year    = {2026}
}