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).
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.
- 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