CHESS: Context-aware Hierarchical Efficient Semantic Selection for Long-Context LLM Inference

Chao Fei, Guozhong Li, Chenxi Liu, Panos Kalnis

TL;DR

CHESS (Context-aware Hierarchical Efficient Semantic Selection) is a KV-cache management system that slashes memory usage by up to 99% while maintaining—and sometimes exceeding—the accuracy of full-context LLMs. By using a hierarchical, "coarse-to-fine" selection strategy and a zero-copy system design, it achieves up to a 4.56× throughput boost for long-context inference.

What Problem Does This Paper Address?

As Large Language Models (LLMs) handle increasingly massive contexts (100k+ tokens), they hit two major walls:

  1. The Memory Wall: The Key-Value (KV) cache, which stores past token information to speed up decoding, grows linearly with sequence length. This eventually exceeds GPU memory or bottlenecks the system with massive data transfers between HBM and SRAM.
  2. The Compute Wall: Attention complexity scales with context length, making each new token more "expensive" to generate than the last.

Existing solutions like H2O or SnapKV use "context-agnostic" pruning—they keep tokens based on global importance (like "heavy hitters") but ignore what the model is currently talking about. Furthermore, many of these methods suffer from high system overhead because they require irregular memory accesses or expensive data movement to "repack" the pruned cache.

Methods

CHESS introduces an algorithm-system co-design to make KV-cache pruning both semantically smart and hardware-efficient.

1. Hierarchical Semantic Representation

Instead of looking at individual tokens, CHESS organizes the KV cache into a three-tier hierarchy: Pages (blocks of tokens), Chunks (groups of pages), and Grids (groups of chunks). It creates a "semantic vector" for each page by mean-pooling and flattening Key states across all layers and heads.

2. Coarse-to-Fine Selection

During decoding, CHESS uses a "query anchor"—a summary of the most recent tokens—to perform a top-down search:

  • Grid Level: Rapidly prune large, irrelevant regions.
  • Chunk Level: Refine the search within active grids.
  • Page Level: Select the specific blocks most relevant to the current generation. This selection is performed via a single, highly optimized GEMM (General Matrix Multiply) operation, avoiding the overhead of calculating individual attention scores for every token.

3. Zero-Copy System Design

To avoid the "memory movement tax," CHESS is implemented atop PagedAttention. It doesn't physically move data; it simply manipulates logical page indices. This allows the system to reconstruct a "coherent" context for the attention engine (like FlashInfer) without expensive copying.

4. Quality-Aware Backtracking

If the model becomes "confused" (measured by high Entropy or Varentropy in its predictions), CHESS can trigger a dynamic reconstruction of the context to retrieve previously pruned information, acting as a safety net against hallucination loops.

Datasets

The authors evaluated CHESS using:

  • LongBenchV2: A comprehensive benchmark for long-context understanding across various tasks (QA, summarization, etc.).
  • Synthetic Workloads: Used to measure system efficiency (throughput and latency) across context lengths ranging from 4k to 32k tokens.

Key Insights and Ideas

  • High-Dimensional Orthogonality: The authors rely on the fact that in high-dimensional LLM latent spaces, unrelated semantic signals tend to be orthogonal. This allows them to mean-pool tokens into page-level vectors without "washing out" the critical information.
  • Context-Awareness > Frequency: Unlike prior methods that keep "globally important" tokens, CHESS proves that keeping semantically relevant segments is more effective for maintaining reasoning quality in long dialogues.
  • The "Distraction" Phase: A fascinating finding (Figure 9) shows that performance isn't strictly linear with cache size. At very low budgets (1%), the model is focused. As the budget increases slightly, "noise" (irrelevant tokens) can actually decrease quality until the budget is large enough to provide full local context again.

Key Results

  • Extreme Sparsity: CHESS (Aggressive) uses only 1% of the KV cache but achieves an overall score of 33.2 on LongBenchV2, actually outperforming the Full-KV baseline (30.2).
  • Massive Throughput: It delivers up to 4.56× higher throughput than Full-KV at 32k context lengths.
  • Latency Stability: While standard LLM decoding latency grows linearly as the context expands, CHESS maintains a nearly flat latency profile, decoupling per-token generation time from the total sequence length.
  • Hardware Agnostic: The benefits were consistent across different GPU architectures (NVIDIA H20 and A800).

Limitations and Future Work

  • Threshold Calibration: The backtracking mechanism currently requires offline calibration on a "golden dataset" to set entropy thresholds.
  • Integration: While it works with PagedAttention and FlashInfer, the authors suggest future work is needed to integrate CHESS with speculative decoding and RAG-augmented pipelines.
  • Fixed Page Size: The experiments standardized on a page size of 32; exploring how different granularities affect the "semantic signal" could be a future area of study.

Summary updated

Abstract

Long-context LLMs demand accurate inference at low latency, yet decoding becomes primarily constrained by KV cache as context grows. Prior pruning methods are largely context-agnostic: their token selection ignores step-wise relevance and local semantics, which undermines quality. Moreover, their irregular accesses and selection overheads yield only limited wall-clock speedups. To address this, we propose \textbf{CHESS}, an \textit{algorithm-system co-design} KV-cache management system. Algorithmically, CHESS introduces a context-aware, hierarchical selection policy that dynamically reconstructs a coherent context for the current decoding. System-wise, coarse granularity selection eliminates expensive data movement, fully realizing practical acceleration from theoretical sparsity. Extensive evaluations demonstrate that CHESS surpasses Full-KV quality using only \textbf{1\%} of the KV cache, delivers low-latency stable inference with up to \textbf{4.56$\times$} higher throughput, and consistently outperforms other strong baselines. Code is available at \href{https://anonymous.4open.science/r/CHESS-9958/}{https://anonymous.4open.science/r/CHESS/}.
BibTeX
@misc{fei2026chess,
  author = {Chao Fei and Guozhong Li and Chenxi Liu and Panos Kalnis},
  title = {{CHESS: Context-aware Hierarchical Efficient Semantic Selection for Long-Context LLM Inference}},
  year = {2026},
  eprint = {2602.20732},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2602.20732},
}
Figure