PaperlayerView exact revision on arXiv

Source-linked AI summary

QUILT: Rethinking Sparse-Attention Prefill through Shared Query Execution

Zhenduo Zhao, Qihui Zhou, Mingcong Song, Zhiyi Chen, Chuangguan Ye, Fengfan Hou, Zequn Gong, Jing Li, Hongjie Si, Guoping Long

arXiv:2610.11134v1cs.LG

TL;DR

Long-context sparse-attention kernels process queries independently, repeating loads and dequantization for KV entries shared across neighboring queries. QUILT jointly executes neighboring queries, using set decomposition and hierarchical, tile-aware sharing. Against the state-of-the-art sparse-attention kernel, it reduces kernel latency, processed KV data, and TTFT latency with negligible accuracy degradation.

  • Problem

    Existing sparse-attention kernels process queries independently, overlooking overlap in neighboring queries’ KV selections and repeating loads and dequantization.

    Source: §1 · p. 2

  • Method

    QUILT jointly executes neighboring queries and uses SCSD, cascaded sharing, and tile-aware execution to exploit cross-query KV reuse.

    Source: §1 · pp. 2–3, §6 · p. 13

  • Results

    Up to 55.1% lower average kernel execution latency, 55.9% less processed KV data, and 36.8% lower average TTFT latency, with negligible accuracy degradation.

    Source: §1 · p. 3

  • Takeaways & Limitations

    QUILT demonstrates that exploiting correlated sparse workloads can translate into kernel-level savings and end-to-end TTFT gains with negligible accuracy degradation.

    Source: §1 · p. 3, §6 · p. 13

Abstract

from arXiv · show

Sparse attention reduces the cost of long-context attention, but existing kernels typically process queries independently, repeatedly loading and dequantizing KV entries shared across queries. We observe substantial overlap in the KV entries selected by neighboring queries, creating opportunities for cross-query reuse. We present QUILT, a workload-aware sparse-attention execution mechanism that jointly processes neighboring queries and reuses shared KV entries to reduce redundant memory traffic and computation. QUILT introduces Shift-and-Compare Set Decomposition (SCSD), which transforms irregular set operations into regular data-parallel primitives suitable for modern accelerators, and pipelines SCSD with attention computation to hide its overhead. Cascaded sharing captures reuse hierarchically at multiple granularities. A tile-aware execution strategy balances sharing granularity with hardware tile utilization and selectively removes low-importance query-specific tails to eliminate underutilized tiles. We evaluate QUILT on LongBench using GLM-5.3 and DeepSeek-3.2 under both tensor and sequence parallelism. Compared with the state-of-the-art sparse-attention kernel, QUILT reduces average kernel latency by up to 55.1% and processed KV data by up to 55.9%, while reducing time-to-first-token (TTFT) latency by up to 36.8% with negligible accuracy degradation.

1 Introduction

Long-context prefill makes attention a growing, user-visible TTFT cost, while independent sparse-query execution repeats shared KV work. QUILT jointly processes neighboring queries with data-parallel decomposition and hierarchical, tile-aware sharing, reducing latency and processed KV data with negligible accuracy degradation.

1 Introduction

  • At long contexts, attention takes an increasing share of prefill latency, which directly determines time-to-first-token.Prefill processes the whole input context before generating the first output token.Source: §1 · p. 2
  • For two-query groups, KV overlap exceeds 85.91% on Qasper and 78.06% on GovReport across layers, and exceeds 90.03% in the first layer.Overlap varies across datasets, layers, and group sizes, although considerable overlap persists as group size increases.Source: §1 · p. 2
  • Existing query-parallel kernels independently gather and dequantize each query’s selected KV entries, repeatedly processing entries shared by neighboring queries.KV loading and dequantization account for a large portion of execution time across profiled sequence lengths and models.Source: §1 · p. 2
  • QUILT jointly executes neighboring queries so shared KV entries are loaded and dequantized once, reducing redundant processing and improving accelerator utilization.Group-based execution follows the sharing structure of the queries’ KV accesses.Source: §1 · pp. 2–3
  • SCSD sorts concatenated KV indices and uses shifts, comparisons, and Boolean primitives for data-parallel set decomposition, overlapped with attention computation.The pipeline largely hides SCSD latency behind useful computation.Source: §1 · p. 3
  • Cascaded sharing recursively identifies KV entries shared across a large query group and then smaller subgroups, avoiding commitment to one sharing granularity.The hierarchy processes each KV entry at the largest group granularity at which it can be shared.Source: §1 · p. 3
  • Tile-aware clipping pushes underfilled shared-segment tails to finer levels and pads sufficiently occupied tails; importance-aware clipping prunes low-ranked residual entries at the final level.The final residual pruning eliminates an underutilized tile and is described as introducing negligible accuracy degradation.Source: §1 · p. 3
  • Up to 55.1% lower average kernel execution latency, 55.9% less processed KV data, and 36.8% lower average TTFT latency, with negligible accuracy degradation.Evaluated on LongBench with GLM-5.3 and DeepSeek-3.2 under tensor and sequence parallelism, against the state-of-the-art sparse-attention kernel.Source: §1 · p. 3

2 Background and Motivation

The background describes prefill and sparse attention, then contrasts regular dense execution with query-specific sparse workloads. It frames cross-query reuse, set-decomposition overhead, heterogeneous sharing granularity, and tile utilization as opportunities and challenges.

2.1 Generative LLM Inference Basics

  • Prefill processes input tokens in parallel to produce the first output token, so its latency determines TTFT; dense attention incurs O(N^2d) computation for sequence length N.This paper focuses on accelerating attention computation during prefill.Source: §2.1 · p. 4

2.2 Sparse Attention

  • Sparse attention selects a Top-K subset of KV entries per query; QUILT operates on these selected workloads regardless of how their indices are generated or refined.The background describes both training-free approaches and model-native sparse attention, while QUILT requires no change to those sparsification strategies.Source: §2.2 · pp. 4–5

2.3 Architecture of Modern Accelerators

  • Accelerators use matrix and vector units backed by hierarchical memory, and tile-based pipelines can overlap data movement with matrix and vector computation.Effective tile shape depends on instruction granularity, data type and alignment, on-chip memory, and available parallelism.Source: §2.3 · p. 5

2.4 Opportunities and Challenges

  • Query-independent sparse execution repeats KV loads and dequantization and fragments matrix operations; sharing must also address decomposition overhead, variable group-level reuse, and underfilled tiles.Naive set processing may offset reuse savings, while small and large groups capture different sharing opportunities and segment sizes may misalign with native tile sizes.Source: §2.4 · p. 5

3 The Design of QUILT

QUILT groups neighboring queries to reuse shared KV entries, then combines set decomposition, pipelining, multigranularity sharing, and tile-aware execution to reduce redundant processing. Its design addresses the overhead of finding shared entries while balancing reuse against accelerator tile utilization.

3 The Design of QUILT

  • QUILT jointly executes neighboring queries, reusing shared KV entries and improving accelerator utilization.This replaces independent query processing with group-based execution of correlated sparse workloads.Source: §3 · p. 5

3.1 Shift-and-Compare Set Decomposition

  • SCSD converts irregular set operations into parallel sorting, shifting, comparisons, Boolean operations, and masked selections.For two lists, it concatenates and sorts indices while tracking their source, then uses shifts and comparisons to identify shared and query-specific entries.Source: §3.1 · p. 6

3.2 Pipelined Execution

  • Pipelining SCSD with attention overlaps set decomposition and attention computation, making the additional bookkeeping overhead largely invisible on the critical path.SCSD constructs a segment before its attention stage consumes it; finer-grained stages can be scheduled across consecutive attention pipeline slots.Source: §3.2 · p. 7

3.3 Cascaded Sharing

  • 8 processed KV entries with cascaded sharing, versus 10 with either fixed group size two or four in the running example.Cascaded sharing extracts reuse at both four-query and subgroup granularities, matching the number of distinct entries in the example.Source: Table 1 · p. 7, §3.3 · pp. 7–8
  • Cascaded sharing captures reuse at multiple granularities, processing each KV entry at the largest query-group size over which it can be shared.This avoids relying on one fixed group size, which can miss either cross-group or subset-only reuse.Source: §3.3 · pp. 7–8

3.4 Tile-Aware Clipping

  • Tile-aware execution pushes tails below a 50% tile-utilization threshold down to the next cascade level, while padding larger tails to a full tile.At the final query-specific level, importance-aware clipping removes the least-important residual entries to eliminate an underutilized tile; this is the only approximate step.Source: §3.4 · p. 8

4.1 Experimental Setup

The evaluation uses Ascend 910C NPUs, two long-context models, and LongBench workloads. QUILT is compared with the OPS-Transformer sparse-attention kernel in a shared serving setup.

4.1 Experimental Setup

  • Experiments use 16 Ascend 910C NPUs, each with 64 GB of HBM, and CANN 9.1.0.The NPUs are connected through a scale-up fabric with up to 784 GB/s bidirectional D2D bandwidth.Source: §4.1 · p. 8
  • Evaluation covers DeepSeek-3.2 and GLM-5.3 on LongBench tasks in question answering, document summarization, and code generation.Both models use model-native sparse attention; each selects Top-2048 KV entries per query, while GLM-5.3 also allows neighboring layers to share indexer selections.Source: §4.1 · p. 8
  • QUILT is compared with the OPS-Transformer sparse-attention kernel in the same XYServe inference setup, where the kernel is the only major difference.The comparison includes accuracy across 21 LongBench datasets.Source: §4.1 · pp. 8–9, Table 2 · p. 9

4.2 Main Results

QUILT preserves LongBench accuracy while reducing sparse-attention kernel latency, processed KV entries, and end-to-end TTFT across both evaluated models. Its latency gains increase with cross-query sharing, although limited sharing can leave set-processing overhead more visible.

4.2.1 Accuracy Retainment.

  • Mean absolute accuracy differences from the baseline are 0.75 points for DeepSeek-3.2 and 0.42 points for GLM-5.3 across 21 LongBench datasets.The corresponding mean absolute percentage differences are 2.01% and 0.90%, respectively.Source: §4.2.1 · p. 9

4.2.2 Average Kernel Latency Reduction.

  • Up to 55.1% lower average sparse-attention kernel latency with QUILT across the evaluated workloads and parallel configurations.For GLM-5.3, average reductions were 53.8% under TP and 43.4% under SP; for DeepSeek-3.2, 28.7% and 17.1%, respectively.Source: Figure 9 · p. 9, §4.2.2 · p. 9
  • QUILT reduces processed KV entries by 54.7% on average for GLM-5.3 and 30.4% for DeepSeek-3.2 across four workloads.TP and SP partition queries differently but do not change the total KV entries processed.Source: Table 3 · p. 9, §4.2.2 · p. 9

4.2.3 Performance Sensitivity to Sharing Length.

  • Increasing sharing length from 0 to 2048 reduces kernel latency by 42.74% and 33.25% for GLM-5.3 under TP and SP, respectively.Latency also falls as sharing increases for DeepSeek-3.2; limited sharing incurs a small overhead, more visible under SP.Source: Figure 10 · p. 10, §4.2.3 · p. 10

4.2.4 Average TTFT Reduction.

  • Up to 36.8% lower average TTFT with QUILT across the evaluated models, workloads, and parallel configurations.For GLM-5.3, average TTFT reductions were 35.6% under TP and 10.4% under SP; for DeepSeek-3.2, 23.0% and 3.4%, respectively.Source: Figure 11 · p. 10, §4.2.4 · p. 10

4.3 Ablation Studies

The ablations assess SCSD, pipelined execution, cascaded sharing, and tile-aware clipping. Together, they show how efficient set processing, reuse at multiple granularities, and selective clipping contribute to latency reduction while preserving output similarity.

4.3.1 Effectiveness of SCSD and Pipelined Execution.

  • 35.5% average kernel-latency improvement over the baseline from the full design across both models and parallel configurations.For GLM-5.3, SCSD cuts naive-variant latency by 96.1% under TP and 97.3% under SP; pipelining further reduces it by 45.9% and 36.9%.Source: §4.3.1 · p. 11

4.3.3 Effectiveness of Tile-Aware Clipping.

  • 23.71% and 22.68% lower GLM-5.3 kernel latency under TP and SP with tile-aware clipping; DeepSeek-3.2 reductions are 24.44% and 14.13%.The comparison is against an exact variant retaining all query-specific residual KV entries.Source: Figure 14 · p. 11, §4.3.3 · p. 12
  • Importance-aware clipping improves attention-output cosine similarity over random clipping, including head-level minimum similarity of 0.406 versus 0.312.At the hidden level, mean similarity is 1.0000 versus 0.9998, and minimum similarity is 0.719 versus 0.664.Source: Figure 15 · p. 11, §4.3.3 · p. 12

4.3.2 Effectiveness of Cascaded Sharing.

  • Cascaded sharing reduces processed KV entries by up to 30.8% versus fixed query-group sizes and lowers kernel latency across both models.The reported KV-entry reductions versus group sizes 2, 4, and 8 are 30.8%, 20.6%, and 22.9% for GLM-5.3, and 11.2%, 15.4%, and 20.7% for DeepSeek-3.2.Source: §4.3.2 · p. 11

5 Related Work

Prior work addresses sparse attention through pattern selection, KV-cache management, and hardware-efficient kernels. QUILT instead targets shared sparse KV selections across concurrent prefill queries, complementing approaches that choose or execute sparse workloads.

Sparse attention for prefill

  • Sparse-prefill methods select attention patterns or budgets, while QUILT exploits overlap across neighboring queries’ resulting sparse KV sets [9, 12, 13, 17, 20, 33].The paper describes QUILT as orthogonal to these sparsification techniques and applicable on top of their designs.Source: §5 · p. 12

Sparse attention for decoding

  • Decoding methods exploit cache compression, dynamic KV selection, or locality across decoding steps; QUILT instead reuses overlapping workloads inside the prefill attention kernel [5] [14] [22] [24] [28] [31] [32] [35] [39].The paper distinguishes decoding memory-management reuse from prefill reuse across concurrently processed queries.Source: §5 · pp. 12–13

Hardware-efficient attention kernels

  • Hardware-efficient kernels improve data reuse, utilization, and overlap, while QUILT targets cross-query reuse of Top-K KV selections in sparse attention [6] [7] [26] [34].The paper presents this as a complementary source of data reuse.Source: §5 · p. 13

6 Conclusion

QUILT exploits cross-query KV reuse during long-context LLM prefill by jointly processing correlated queries. Its components address set processing, overlap, and hardware utilization; evaluations report lower kernel latency and end-to-end prefill latency across workloads and configurations.

6 Conclusion

  • QUILT jointly processes correlated queries to exploit cross-query KV sharing overlooked by workload-agnostic, query-parallel execution.It combines Shift-and-Compare Set Decomposition, pipelining, cascaded sharing, tile-aware execution, and importance-aware clipping.Source: §6 · p. 13
Loading 2610.11134v1…