DTS: Delta-Based Tile Scoring for Efficient Long-Context Sparse Attention

Emre Uğur, Jiawen Qi, Qinyu ChenarXiv 2026 · arXiv

TL;DR

DTS (Delta-Based Tile Scoring) is a training-free, content-adaptive method that slashes the cost of identifying important attention blocks in long-context LLMs. By selecting "anchor" tokens based on local vector changes rather than fixed sampling, DTS achieves a 3.3× prefill speedup at 512K tokens while maintaining near-perfect accuracy (within 0.10 percentage points of full attention).

What Problem Does This Paper Address?

As Large Language Models (LLMs) move toward processing massive contexts—think entire codebases or long books—the "prefill" stage becomes a major bottleneck. During prefill, the model must compute the attention matrix for the entire input prompt. Because attention complexity grows quadratically with sequence length, this process becomes incredibly slow.

To solve this, researchers use sparse attention, which skips "unimportant" blocks of the attention matrix. However, there’s a catch: scoring these blocks to decide which ones to skip can itself be computationally expensive. Existing methods like XAttention use fixed-stride sampling (e.g., checking every 16th token), but this is inefficient. It wastes work on redundant, similar tokens and might miss important details in regions where the data changes rapidly.

Methods

The authors introduce DTS (Delta-Based Tile Scoring), which moves away from fixed sampling toward a content-adaptive approach.

1. Delta-Based Anchor Selection

Instead of sampling tokens at fixed intervals, DTS identifies "anchors"—representative tokens that capture the essence of a local region. It scans the query ($Q$) and key ($K$) sequences; if a new token is sufficiently different from the current anchor (measured by cosine similarity), it becomes the new anchor.

  • Redundant regions (similar vectors) get fewer anchors.
  • Heterogeneous regions (changing vectors) get more anchors.

2. Parallel Delta Packing

To make this efficient on GPUs, the authors developed "parallel delta packing." They divide sequences into tile-aligned chunks and perform local scans concurrently. This limits sequential dependencies and ensures the scoring process doesn't become a new bottleneck.

3. Tile Scoring and Selection

Once anchors are selected, DTS computes scores only for these anchor pairs. These scores are summed to estimate the importance of an entire $B \times B$ tile. Finally, the most important tiles are selected for full computation using standard dense kernels (like FlashAttention-2).

Fig. 1: Comparison of XAttention [8] and DTS. (a) XAttention samples strided antidiagonals at a fixed density. (b) DTS selects query and key anchors based on local vector changes, reducing redundant scoring in similar regions.
Fig. 1: Unlike XAttention's fixed antidiagonal sampling (a), DTS (b) adapts to the content, using fewer scoring pairs in similar regions to save time.

Datasets

The authors evaluated DTS using two primary long-context benchmarks:

  • RULER: Tests retrieval and reasoning over contexts ranging from 4K to 128K tokens.
  • LongBench: A comprehensive suite of 16 tasks including multi-document QA, summarization, and code completion.
  • WikiText-103: Used for measuring raw prefill latency at lengths up to 512K tokens.

Experiments were conducted on LLaMA-3.1-8B-Instruct and Qwen2.5-7B-Instruct-1M.

Key Insights and Ideas

  • Local Similarity is Real: The authors observed that neighboring query and key vectors are highly similar in natural text compared to shuffled text. This "local redundancy" is the "aha moment" that justifies using anchors to represent entire blocks.
Mean cosine similarity of neighboring vectors
Fig. 2: High cosine similarity between adjacent tokens suggests that we don't need to score every single one to understand a block's importance.
  • Fixed Patterns are Brittle: Fixed-stride sampling (like XAttention) is a "one-size-fits-all" solution that fails to adapt. DTS proves that by spending a tiny bit of effort to find where the data actually changes, you can save a massive amount of downstream computation.
  • Training-Free is Key: DTS requires no fine-tuning or architectural changes, making it a "plug-and-play" optimization for existing long-context models.

Key Results

  • Speed: On four NVIDIA H100 GPUs, DTS achieved a 3.3× prefill speedup over a FlashAttention-2 baseline at 512K tokens.
  • Efficiency: At 128K tokens, DTS reduced the latency of the scoring pipeline by 38% compared to XAttention.
  • Accuracy: DTS is remarkably precise. On LLaMA-3.1-8B, it stayed within 0.10 percentage points of the full-attention baseline on both RULER and LongBench.
  • Pareto Frontier: DTS consistently sits on the "Pareto frontier" of the accuracy-vs-latency trade-off, outperforming other dynamic sparse methods like MInference and FlexPrefill in the high-accuracy regime.

Limitations and Future Work

  • Offline Calibration: DTS currently requires an offline calibration step to set per-head tile-selection thresholds ($\theta_h$). While this only needs to be done once per model, an entirely online, self-adjusting thresholding mechanism would be more robust.
  • Prefill Only: The paper focuses strictly on the prefill bottleneck. While prefill is a major issue for long contexts, the "decoding" stage (generating tokens one by one) remains a separate challenge that DTS does not address.
  • Hardware Specifics: The current implementation is optimized for Triton/GPUs. Porting these dynamic, scan-based operations to other accelerators (like TPUs or NPUs) might require different optimization strategies.

Summary updated

Abstract

Large language models (LLMs) increasingly need to process long documents and codebases, making long-context attention a major prefill bottleneck. Block sparse attention reduces computation by skipping unimportant blocks of the attention matrix, but scoring blocks accurately can itself be expensive. We propose Delta-Based Tile Scoring (DTS), a training-free, content-adaptive tile scoring method for sparse block attention. DTS selects query and key anchors according to local vector changes, using fewer representatives in redundant regions while retaining more detail in heterogeneous regions. To accelerate anchor selection, parallel delta packing partitions the query and key sequences into tile-aligned chunks and performs bounded local scans over these chunks concurrently. The selected tiles are then computed using the original query, key, and value vectors. On LLaMA-3.1-8B-Instruct, DTS keeps average RULER and LongBench scores within 0.10 percentage points of full attention, with RULER evaluated up to 128K tokens. At 128K tokens, DTS reduces measured scoring-pipeline latency by 38% compared with XAttention. On four NVIDIA H100 GPUs, it achieves a 3.3$\times$ prefill speedup over a PyTorch full-attention baseline using FlashAttention-2 at 512K tokens.
BibTeX
@misc{ugur2026dts,
  author = {Emre Uğur and Jiawen Qi and Qinyu Chen},
  title = {{DTS: Delta-Based Tile Scoring for Efficient Long-Context Sparse Attention}},
  year = {2026},
  eprint = {2611.25938},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.25938},
}
Figure