cs.LGNov 19, 2026

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

Authors: Emre Uğur, Jiawen Qi, Qinyu Chen

Organizations: Leiden Institute of Advanced Computer Science (LIACS), Leiden University, The Netherlands

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.

Figures & tables

Explore similar work

CardsList
  1. Block Sparse Flash Attention

    Dec 7, 2025Daniel Ohayon, Itay Lamprecht, Itay Hubara +3GPU AccelerationSelf-Attention

  2. Coarse Semantic Blocks for Efficient Training-Free Sparse Attention

    Nov 3, 2026Sosuke Kobayashi, Shoichiro Yamaguchi, Seiya TokuiSparse AttentionLLM Inference Acceleration

  3. DashAttention: Differentiable and Adaptive Sparse Hierarchical Attention

    May 18, 2026Yuxiang Huang, Nuno M. T. Gonçalves, Federico Alvetreti +5Self-AttentionHierarchical Attention