One-sentence Summary

Researchers from Microsoft Corporation and the University of Surrey introduce SCBench, a KV cache-centric benchmark evaluating long-context LLMs across generation, compression, retrieval, and loading using shared-context tasks, revealing that $sub-$sub−O(n) memory methods struggle in multi-turn scenarios while sparse encoding with $O(n)$ memory and $sub-$O(n^2) pre-filling remains robust.

Key Contributions

• Introduces SCBench, a KV cache-centric benchmark for long-context LLM evaluation that spans 12 tasks across two shared-context modes and covers four capability categories: string retrieval, semantic retrieval, global information, and multi-tasking.
• Proposes a KV cache-centric framework that organizes long-context inference methods into four stages: generation, compression, retrieval, and loading, and evaluates 13 methods across eight categories, including gated linear RNNs, hybrid models, sparse attention, and prompt compression, on eight LLMs (Llama-3.1-8B/70B, Qwen2.5-72B/32B, Llama-3-8B-262K, GLM-4-9B, Codestral-Mamba, and Jamba-1.5-Mini).
• Findings show that sub-O(n) memory methods struggle in multi-turn shared-context scenarios, while sparse encoding with O(n) memory and sub-O(n²) pre-filling computation performs robustly; dynamic sparsity yields more expressive KV caches than static patterns, and attention distribution shift issues arise in long-generation scenarios.

Introduction

The authors tackle the growing need for efficient long-context inference in Large Language Models (LLMs), which now support context windows from 128K to 10M tokens. These capabilities enable real-world use cases such as repository-level code understanding, long-document question answering, and many-shot in-context learning, but they also impose high computational and memory costs during inference. Prior efficient solutions exploit sparsity at various stages of the KV cache pipeline, including generation, compression, retrieval, and loading. However, these methods are typically evaluated only on single-request benchmarks, which fail to capture real-world patterns like shared prompt contexts, prefix caching, and multi-round interactions. Query-conditioned compression methods can even break down on follow-up queries, as prior work on Mamba has shown. To close this gap, the authors introduce SCBench, a KV-cache-centric benchmark that covers the full lifecycle of the KV cache across 12 tasks and four long-context capabilities: string retrieval, semantic retrieval, global information processing, and multi-tasking, in two shared-context modes: multi-turn and multi-request. They also propose Tri-shape, a training-free sparse attention method that improves first-turn accuracy. Their evaluations span 13 long-context methods and eight open-source LLMs, revealing that sub-linear-memory approaches lose accuracy in multi-turn decoding while O(n)-memory methods better approximate full attention accuracy across follow-up queries.

Dataset

SCBench is a benchmark dataset designed to evaluate four long-context abilities: string retrieval, semantic retrieval, global information processing, and multi-tasking. It covers two shared context modes, namely multi-turn and multi-request, across domains including code, retrieval, question answering, summarization, in-context learning, and multi-hop tracing. In total, SCBench includes 931 multi-turn sessions with 4,853 queries, averaging 5 turns per session.

Dataset composition by task group

• String Retrieval

  • Retrieve.KV: built from large JSON objects with random key-value pairs. Each session retrieves 5 KV pairs, with target KVs evenly distributed across the input.
  • Retrieve.Prefix-Suffix: uses a large list of variable-length strings. Models must retrieve a string matching a specified prefix and suffix. Distractors that share only the prefix or suffix prevent reliance on simple lookup.
  • Retrieve.MultiHop: adapted from RULER, embedding 5 multi-hop variable assignment chains. Each turn requires retrieving the exact chain for a given value.

• Semantic Retrieval

  • Code.RepoQA: extended from RepoQA to 64K tokens. Inputs come from GitHub repositories in Python, C++, Java, PHP, Rust, Go, and TypeScript. Function descriptions are generated with GPT-4. Each session retrieves one function per turn across 5 turns.
  • En.QA, Zh.QA, En.MultiChoice: extended from InfiniteBench, using human-annotated QA tests based on fictional novels. Question types include aggregation (compiling scattered information) and filtering (identifying specific details). QA pairs sharing the same input context are combined into shared-context sessions.

• Global Information Processing

  • Many-shot ICL: sourced from Big-Bench Hard, with three sub-tasks: date understanding, salient error translation detection, and tracking seven shuffled objects. All sub-tasks are multiple-choice with four options, and contexts are shared across turns.
  • Math.Find: extended from InfiniteBench, expanding from maximum value to minimum and median values over a large array.
  • En.Sum: built from concatenated arXiv papers ranging from 8K to 20K tokens. Ground truth summaries, averaging 654 tokens, are generated by GPT-4 as concise one-sentence summaries. Target documents are evenly distributed across the context.

• Multi-Tasking

  • Mix.Sum+NIAH: combines document summarization with a Needle in a Haystack task. A random needle is inserted evenly into the En.Sum input, and the model alternates between summarization and retrieval.
  • Mix.RepoQA+KV: combines RepoQA with KV retrieval. 100 KV pairs are inserted evenly into a source code input, with 4 target KVs and the rest as distractors. The model alternates between code retrieval and KV retrieval.

Shared context modes

• Multi-turn mode: follow-up turns use ground-truth answers as context instead of model-generated content, reflecting long-context chat and multi-step reasoning scenarios. This matters for methods with KV cache reuse, since focus shifts across turns can cause information loss.
• Multi-request mode: context is shared across sessions or users, such as collaborators on a shared code repository. Models can encode shared context and reuse KV cache across requests. This tests methods that depend on the query for sparse encoding or decoding, such as MInference and SnapKV, assessing their generalization without query access.

Processing and usage details

• Target strings, KV pairs, and documents are positioned evenly across the input to test full-context utilization.
• Ground-truth answers are used in multi-turn settings to avoid error accumulation from model-generated content.
• The benchmark combines tasks with shared contexts to simulate realistic multi-request scenarios where models must handle mixed workloads.

Method

The authors propose a unified analytical framework that categorizes efficient long-context methods through a KV-cache-centric perspective. This framework systematically divides the inference lifecycle into four distinct stages: KV Cache Generation, Compression, Retrieval, and Loading.

The framework operates as follows:

1. KV Cache Generation: This initial stage focuses on efficiently processing the input prompt to produce the KV cache. Techniques in this category include sparse attention mechanisms (e.g., A-shape, Tri-shape), State Space Models (SSM) or hybrid approaches (e.g., Mamba), and prompt compression methods (e.g., LLMLingua 2).
2. KV Cache Compression: After generation, the KV cache is compressed to reduce memory costs before being stored. This stage employs methods such as KV cache dropping (e.g., StreamingLLM, SnapKV) and KV cache quantization (e.g., KIVI).
3. KV Cache Retrieval: To reduce the time-to-first-token (TTFT), relevant KV cache blocks are retrieved from a storage pool based on the request's prefix. This involves semantic retrieval methods (e.g., CacheBlend) or extract matching.
4. KV Cache Loading: The final stage dynamically loads the KV cache from external storage (such as VRAM, DRAM, or SSD) into the GPU on-chip SRAM to compute sparse attention during the decoding phase.

Within the generation stage, the authors introduce Tri-shape, a training-free sparse attention method designed to improve accuracy across multiple requests.

Unlike the standard A-shape pattern, which retains only the sink token and a local window, Tri-shape preserves the last window query region. This modification forms a triangular sparse attention pattern for pre-filling. This design enhances performance for both the initial turn and subsequent multi-request interactions while maintaining the model's instruction-following capabilities.

Experiment

The evaluation builds SCBench, a benchmark of 12 tasks spanning four long-context abilities across multi-turn and multi-request shared context modes, and tests eight long-context method categories on six open-source LLMs. Results show that most compression methods fail at exact retrieval tasks, with sparse attention and dynamic sparse methods like MInference performing best, while KV cache compression and prompt compression degrade in shared scenarios. Analysis reveals that sub-O(n) memory is nearly infeasible for multi-turn decoding because attention patterns shift across queries, sparse encoding is more robust than sparse decoding, and highly compressible tasks overestimate model capabilities compared to incompressible retrieval tasks. Query-dependent methods suffer accuracy losses without query access, though MInference generalizes better due to its adaptive sparse patterns.

The table compares long-context methods across KV cache stages, noting differences in cache size and computational complexity. Evaluation results show that sparse attention methods generally outperform sparse decoding methods, particularly in shared context scenarios, while KV cache compression approaches tend to underperform. Sparse attention methods like MInference and A-shape/Tri-shape provide efficient pre-filling with reduced complexity, while KV cache dropping and quantization only offer decoding-stage efficiency. Gated linear RNNs such as Codestral Mamba achieve constant KV cache size and linear pre-filling complexity, contrasting with quadratic complexity of full attention. Prompt compression reduces cache size proportionally to compression factor but still incurs quadratic pre-filling complexity, limiting its efficiency gains.

SCBench comprises 12 tasks spanning four long-context abilities: string retrieval, semantic retrieval, global information processing, and multi-tasking, across multi-turn and multi-request context modes. Tasks vary widely in input length, with semantic retrieval tasks such as Chinese QA reaching much longer inputs than code or English QA tasks. The benchmark includes nearly a thousand multi-turn sessions and thousands of queries, averaging about five turns per session. String retrieval tasks like key-value and prefix-suffix matching have input lengths around 110K-125K, with relatively short outputs. Semantic retrieval tasks show a wide input length spread, from 65K for code QA to 1.5M for Chinese QA, while English QA and multi-choice stay near 188K-198K. All tasks are organized into multi-turn sessions, with session counts ranging from 35 to 100 and turn counts roughly five times the session count.

SCBench includes 12 tasks that assess four long-context abilities across shared context modes, with configurations varying by source, task-specific parameters, and evaluation metrics. The tasks span diverse domains and are designed to test retrieval, reasoning, and summarization in multi-turn or multi-request settings. Each task uses custom inputs and expected outputs, with some tasks leveraging existing benchmarks and others proposing new configurations. Retrieval tasks such as Retr.KV and Retr.Prefix-Suffix use randomized key-value pairs or string dictionaries with accuracy as the metric, emphasizing incompressible context utilization. Multi-hop retrieval, adapted from RULER, chains variable assignments across turns, testing the model's ability to track indirect references. Code repository question answering uses GPT-4 generated function descriptions and Pass@1, while English and Chinese QA tasks rely on human-annotated ground truth with accuracy. A math-focused task asks for the maximum number in a large array, repeated across turns, highlighting iterative numeric reasoning in shared contexts.

Across shared context modes, most long-context compression methods underperform relative to the full-attention baseline, with particularly poor results in exact retrieval tasks. MInference, a dynamic sparse attention method, consistently achieves the highest average scores among the compressed approaches, while static sparse decoding and KV cache compression show substantial degradation, especially as requests accumulate. MInference outperforms all other compressed methods in both multi-turn and multi-request modes, though it still trails the uncompressed baseline. Static sparse decoding methods like StreamingLLM yield near-zero scores on exact string retrieval tasks, indicating severe limitations for query-independent shared contexts. Tri-shape sparse attention generalizes relatively well across tasks, ranking second to MInference, while KV cache compression and prompt compression methods generally show weaker average performance. Exact retrieval performance collapses for most compressed methods, including A-shape and LLMLingua-2, suggesting that sub-O(n) approaches struggle with incompressible key-value patterns.

Query-aware long-context methods generally degrade when the query is unavailable during encoding, but the extent varies by method. Dynamic sparse attention (MInference) shows stronger generalization without query access compared to KV cache compression (SnapKV) and static sparse attention (Tri-Shape). Removing query access causes substantial performance drops for SnapKV and Tri-Shape across most tasks. MInference maintains relatively higher accuracy without the query, likely due to its adaptive sparse patterns. Static sparse attention and KV cache compression are more sensitive to query absence than dynamic sparse attention.

The evaluation uses SCBench, which comprises 12 tasks spanning four long-context abilities in multi-turn and multi-request shared context modes. Across all settings, most compression methods underperform the full-attention baseline, and exact retrieval tasks prove especially challenging, with static sparse decoding and KV cache compression showing severe degradation while dynamic sparse attention, led by MInference, generalizes best. When query access is removed during encoding, query-aware methods decline in accuracy, but dynamic sparse attention remains more robust than KV cache compression or static sparse attention, highlighting that adaptive sparse patterns better preserve performance without the query.