Skip to content

EarlySelectKV: Anticipatory KV Selection via Cross-Layer Query Proxies

Conference: EMNLP 2026
Paper: ACL Anthology
Code: https://github.com/sea-with-sakura/EarlySelectKV
Area: Model Compression
Keywords: KV Cache Compression, Dynamic Sparse Attention, Cross-Layer Query Proxies, Long-Context Inference, Scheduling Optimization

TL;DR

Addressing the critical pre-attention serialization bottleneck in query-conditioned dynamic KV selection where selectors must wait for the target-layer query, EarlySelectKV introduces a training-free transformation that uses proxy queries derived from preceding hidden states to precompute selected KV indices asynchronously, matching native accuracy across LongBench and RULER while improving end-to-end throughput by up to 12.4% and cutting GPU routing memory by 11.1%.

Background & Motivation

Serving long-context large language models (LLMs) in workloads such as long-document understanding and repository-level code completion incurs prohibitive GPU memory footprints and memory bandwidth demands. Because key-value (KV) cache storage scales linearly with sequence length, batch size, and network depth, inference quickly becomes memory-bound. Dynamic sparse KV selection methods—such as Quest, Loki, and RocketKV—mitigate these costs at inference time by retaining a candidate pool and dynamically selecting a compact subset of historical KV blocks at each decoding step based on the active query. This dynamic query-conditioned paradigm offers superior adaptivity and preserves model accuracy even under constrained token budgets.

However, existing query-conditioned selectors suffer from an intrinsic system scheduling inefficiency: they must wait until the target-layer query is computed before they can score candidate pages, rank them, and generate selected indices. As the sparse token budget is reduced, the actual attention computation scales down and becomes cheaper, yet the routing computation and metadata memory access remain exposed on the immediate critical path directly preceding attention. Consequently, deciding which KV entries to fetch becomes a dominant, non-negligible source of decoding latency, completely stalling the hardware execution pipeline.

The authors observe a crucial divergence in fidelity requirements: while the final value aggregation in sparse attention strictly requires the exact target-layer query, candidate routing only needs to preserve relative preference rankings among historical candidates. Because adjacent transformer representations exhibit high cross-layer continuity, waiting for the target-layer query to complete before initiating routing is fundamentally unnecessary. Core idea: decouple dynamic KV selection into asynchronous anticipatory routing and exact sparse attention, deriving a proxy query from earlier hidden states to precompute next-layer KV page indices, so that the target layer can instantly execute sparse attention with its exact query upon arrival without exposed routing stalls.

Method

Overall Architecture

EarlySelectKV is a training-free, selector-preserving framework that wraps existing query-conditioned sparse KV selectors without altering their underlying scoring formulations or candidate views. The framework decomposes decoding at each layer into a synchronous Main Flow and an asynchronous Side Flow.

For decoding step \(t\) and target layer \(\ell+1\), the Main Flow executes exact sparse attention: it reads the precomputed page indices \(\hat{I}_{\ell+1}^t\), fetches the corresponding KV cache pages, and performs attention aggregation using the real target-layer query \(q_{\ell+1}^{t, \text{real}}\). Concurrently, the Side Flow executes during an earlier computation window at layer \(\ell\). It taps an anchor hidden state \(\tilde{H}_{t,\ell}\), projects it into an anticipatory proxy query \(q_{\ell+1}^{t, \text{proxy}}\), and invokes the selector over a compact routing view (such as an FP8 K-summary cache) to predetermine \(\hat{I}_{\ell+1}^t\). This advances index availability and completely removes index generation from the target layer's critical path.

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["Preceding Layer Hidden State<br/>Hin or intermediate Hmid"] --> B["Anticipatory Proxy Generation<br/>Derive proxy query via projection"]
    B --> C["Asynchronous Selection Logic<br/>Score K-summaries and output indices"]
    C --> D["Precomputed Index Availability<br/>Zero-wait delivery to target layer"]
    D --> E["Exact Sparse Attention<br/>Real query + fetched KV blocks"]
    E --> F["Output Target Hidden State"]

Key Designs

1. Anticipatory Proxy Query Generation: Bridging Hidden States Across Layers

In conventional selectors, next-layer indices are generated sequentially on the critical path: \(I_{\ell+1}^t = \mathcal{R}_{\ell+1}(q_{\ell+1}^{t,\text{real}}, \mathcal{M}_{\ell+1}^t; B)\), where \(\mathcal{R}\) is the routing rule, \(\mathcal{M}\) represents the candidate/summary view, and \(B\) is the token budget. EarlySelectKV replaces the blocking real query with an anticipatory proxy query constructed from an anchor state \(\tilde{H}_{t,\ell}\): $\(q_{\ell+1}^{t,\text{proxy}} = W_{q,\text{proxy}}^{\ell+1} \text{LN}_{\ell+1}(\tilde{H}_{t,\ell})\)$ The projection matrix \(W_{q,\text{proxy}}^{\ell+1}\) can directly reuse the native query projection \(W_q^{\ell+1}\) or employ a rank-\(r\) truncated SVD approximation \(U_r^{\ell+1} \Sigma_r^{\ell+1} (V_r^{\ell+1})^\top\). In resource-sensitive offloaded deployment settings, low-rank projection (such as \(r=128\)) dramatically curbs host-side proxy construction costs with virtually zero degradation in selection quality.

2. Anchor Selection Strategies: Balancing Preparation Window Against Selection Fidelity

The choice of anchor state \(\tilde{H}_{t,\ell}\) establishes an explicit trade-off between the available index preparation window and routing representation fidelity. The framework formalizes three anchor modes: - ES-In (Input Anchor): Uses the layer input block \(H_{\ell}^{\text{in}}\) directly. Because this state is available before layer \(\ell\) begins execution, ES-In grants an extensive preparation window spanning the entire computation of layer \(\ell\), maximizing opportunities to hide routing latency and offloaded memory transfers. - ES-Mid (Post-Attention Intermediate Anchor): Uses the post-attention residual state \(H_{\ell}^{\text{mid}} = H_{\ell}^{\text{in}} + \text{Attn}_{\ell}(\text{LN}_{\ell}(H_{\ell}^{\text{in}}), K_\ell, V_\ell)\). By incorporating intra-layer contextual interactions, \(H_{\ell}^{\text{mid}}\) provides superior query fidelity that closely mirrors the target space, serving as a robust default for approximation-sensitive layers at the expense of a narrower window (spanning the FFN block). - ES-Mix (Layer-Wise Calibrated Mixed Profiling): Measures the retention gap \(g_{\ell+1} = \mathcal{M}_{\ell+1}(Q_{\text{mid}}) - \mathcal{M}_{\ell+1}(Q_{\text{in}})\) over calibration prompts. If the attention mass advantage of ES-Mid over ES-In satisfies \(g_{\ell+1} \le \tau\) (with threshold \(\tau=0.01\)), the layer is classified as insensitive and assigned ES-In to maximize the latency-hiding window; otherwise, it retains ES-Mid for fidelity preservation.

3. Asynchronous Selection and Decoupled Hardware Scheduling

Because page index generation occurs before target attention execution, the entire routing pipeline can be decoupled from the GPU execution path. In CPU-GPU heterogeneous deployments, EarlySelectKV offloads proxy query generation, FP8 K-summary caches, and top-\(k\) page scoring entirely to the host CPU (accelerated with AVX-512 BF16 dot products). During GPU layer \(\ell\) computation, the CPU computes indices and transfers a minimal set of index integers via PCIe. The local tail page is always preserved outside the selection pool to guarantee recent locality, allowing the GPU to maintain zero idle bubbles waiting on metadata.

A Worked Example

Consider serving Llama-3.1-8B on a 40K-token sequence with page size \(p=4\) and \(k=32\) selected pages (128 historical tokens) in a CPU-offloaded environment: 1. Layer \(\ell\) Execution: While the GPU computes self-attention at layer \(\ell\), intermediate hidden state \(H_\ell^{\text{mid}}\) is generated. The CPU immediately pulls this tensor and multiplies it by the rank-128 BF16 projection weights, constructing \(q_{\ell+1}^{t, \text{proxy}}\) in under \(0.1\text{ ms}\). 2. Asynchronous CPU Scoring: The CPU evaluates dot-product scores against 10,000 candidate page summaries in FP8 host memory using AVX-512, selects the top 32 pages, and appends the reserved local page index. 3. Target Layer Zero-Wait Execution: When the GPU concludes layer \(\ell\) FFN and arrives at layer \(\ell+1\), the 32 page indices are already resident on the GPU. The GPU directly gathers the 128 active KV vectors, computes the exact query \(q_{\ell+1}^{t, \text{real}}\), and triggers the sparse attention kernel without experiencing any routing stall.

Key Experimental Results

Main Results

Evaluations across LongBench (16 multi-task benchmarks spanning QA, summarization, few-shot learning, and code) and RULER demonstrate that ES-RocketKV achieves near-identical accuracy to native RocketKV across various models and budgets, with an average score difference of merely \(+0.018\) points.

Model KV Access Budget FullCache TopK (Oracle) RocketKV (Native) ES-RocketKV (Ours) Delta (\(\Delta\))
Llama-3-8B-Instruct 128 43.23 43.72 41.68 41.78 +0.10
Llama-3-8B-Instruct 512 43.23 43.50 43.07 43.03 -0.04
Llama-3-8B-Instruct 1024 43.23 43.31 43.18 43.21 +0.03
Llama-3.1-8B-Instruct 128 49.72 49.66 47.57 47.47 -0.10
Llama-3.1-8B-Instruct 512 49.72 49.66 49.17 49.08 -0.09
Llama-3.1-8B-Instruct 1024 49.72 49.70 49.41 49.50 +0.09
Mistral-7B-Instruct-v0.2 128 43.20 42.02 39.24 39.32 +0.08
Mistral-7B-Instruct-v0.2 512 43.20 43.01 41.96 42.33 +0.37
Mistral-7B-Instruct-v0.2 1024 43.20 43.04 42.71 42.59 -0.12
Qwen2.5-7B-Instruct 128 49.07 47.34 44.26 44.06 -0.20
Qwen2.5-7B-Instruct 512 49.07 47.66 46.73 46.72 -0.01
Qwen2.5-7B-Instruct 1024 49.07 47.46 46.95 46.95 0.00

On synthetic Needle-in-a-Haystack (NIAH/Passkey) retrieval, ES-RocketKV achieves 100% exact-match retrieval on Mistral-7B and Llama-3.1 at budget 128, matching native RocketKV within an average difference of \(+0.25\) percentage points.

Ablation Study

Ablation investigations into anchor configurations (ES-In vs. ES-Mid vs. ES-Mix) and SVD projection ranks highlight the stability of proxy representations.

Config Mechanism / Parameter Setting LongBench Avg (Mistral-7B, Budget 512) Delta vs. RocketKV Note
RocketKV (Native) Exact target \(W_q\) query routing 41.96 - Base synchronous baseline
ES-Mid (Exact \(W_q\)) Post-attention anchor \(H_{\ell}^{\text{mid}}\) + full \(W_q\) 42.33 +0.37 Conservative default, FFN window
ES-In (Exact \(W_q\)) Input block anchor \(H_{\ell}^{\text{in}}\) + full \(W_q\) 42.39 +0.43 Full-layer preparation window
ES-Mix (Adaptive) Layer-wise calibrated anchor assignment 42.18 +0.22 Bridges latency hiding and fidelity
ES-RocketKV (SVD r=64) Rank-64 proxy projection 41.32 -0.64 Visible drop on retrieval tasks
ES-RocketKV (SVD r=128) Rank-128 proxy projection 41.82 -0.14 Halved CPU overhead, near-identical
ES-RocketKV (SVD r=256) Rank-256 proxy projection 42.09 +0.13 Reaches performance saturation

In runtime deployment benchmarks on TensorRT-LLM with an NVIDIA RTX 6000D GPU and Intel Xeon Platinum CPU: - Throughput Scaling: With 40K prompt input, end-to-end output throughput improvements scale from \(1.3\%\) at 128 output tokens to \(12.4\%\) at 8192 output tokens (steady-state decode throughput gains reach \(7.67\% \sim 13.14\%\)). - GPU Memory Relief: Offloading K-summary routing state to host memory reclaims 5.3 GiB of GPU VRAM, accounting for \(11.1\%\) of the total KV and K-summary pool.

Key Findings

  • Decoding Latency Amortization: Precomputing indices yields escalating throughput benefits on long generation horizons (e.g., up to \(12.4\%\) at 8K output tokens), where repeated pre-attention stalls are systematically eliminated.
  • Layer-Wise Fidelity Convergence: In early-to-mid layers, ES-Mid exhibits higher signed top-\(r\) channel recall and retained attention mass than ES-In; in deeper layers (post-layer 20), the two anchors converge, confirming that deep layers readily tolerate the longer ES-In preparation window.
  • Broad Framework Generality: Wrapping Quest and Loki with EarlySelectKV yields an average delta of only \(-0.07\) points across eight configurations; integrating it into the trainable InfLLM-V2 sparse model yields \(+0.26\) points, verifying plug-and-play architectural compatibility.

Highlights & Insights

  • Decoupling Timing from Value Aggregation: The fundamental realization that routing is merely a ranking problem over candidates, whereas attention is an exact weighted sum, allows breaking the synchronous data dependency without sacrificing accuracy.
  • System-Algorithm Co-Design: Advancing index availability unlocks practical CPU-offloaded dynamic routing, converting host CPU memory and AVX units into an effective latency-hiding pipeline.

Limitations & Future Work

  • Preparation Window Boundaries: Latency-hiding benefits diminish on extremely short output sequences or ultra-heavy routing networks where selector execution exceeds the available intra-layer forward time.
  • Offline Profile Sensitivity: ES-Mix depends on offline layer profiling; substantial domain shifts in target distributions may necessitate re-profiling anchor transition layers.
  • Distributed Scaling: The current runtime study focuses on single-GPU serving; extending anticipatory routing to pipeline and tensor parallel serving topologies remains an open avenue.
  • vs RocketKV / Quest / Loki: Existing selectors compute routing sequentially at the target layer; EarlySelectKV acts as an orthogonal timing wrapper that pulls index generation forward into preceding windows.
  • vs IndexCache: IndexCache directly reuses stale top-\(k\) indices across layers, causing noticeable semantic drift; EarlySelectKV independently constructs layer-specific proxy queries, preserving pristine selection fidelity.
  • vs InfiniGen / ScoutAttention: While speculative prefetching predicts downstream queries for full attention computation, EarlySelectKV restricts approximation strictly to the selection phase, leaving attention execution mathematically exact.

Rating

  • Novelty: ⭐⭐⭐⭐☆ Pioneers the perspective of optimizing "when to select" rather than "what to select", advancing query-conditioned routing.
  • Experimental Thoroughness: ⭐⭐⭐⭐⭐ Rigorous validation across 4 backbones (7B–32B), 3 established long-context benchmarks, real TensorRT-LLM deployment, and micro-diagnostics.
  • Writing Quality: ⭐⭐⭐⭐⭐ Extremely lucid narrative structure, well-defined mathematical abstractions, and informative pipeline diagrams.
  • Value: ⭐⭐⭐⭐⭐ Training-free, highly generalizable, and directly deliverable as concrete throughput and memory gains in production serving.