QUILT: Rethinking Sparse-Attention Prefill through Shared Query Execution

arXiv:2610.11134 · cs.LG · Submitted 2026-10-08 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Today's paper: "QUILT: Rethinking Sparse-Attention Prefill through Shared Query Execution".

Jane: The gist The proposed QUILT mechanism rethinks sparse-attention prefill by introducing a workload-aware execution strategy that exploits cross-query reuse to reduce redundant KV data processing and improve hardware utilization.

Tom: First, who's behind it and why it matters.

Paper summary: Tom: So to wrap up this look at "QUILT: Rethinking Sparse-Attention Prefill through Shared Query Execution," the authors are essentially arguing that treating sparse queries as independent entities misses a huge opportunity in how they interact during prefill.

Jane: They're proposing a mechanism where neighboring queries collaborate, explicitly exploiting the cross-query reuse of KV entries to cut down on redundant data handling and boost hardware usage.

Lu: The core technical contribution is introducing Shift-and-Compare Set Decomposition to handle that set intersection work in a data parallel way, along with cascaded sharing for hierarchical reuse detection and tile-aware execution for better hardware alignment.

Meng: From an engineering standpoint, it’s about making sure the software knows how to map those shared resources efficiently onto the hardware tiles, which is a real challenge in accelerator design.

Tom: And their results show that this isn't just theoretical; they achieved latency reductions of up to fifty-five point one percent and data reduction of up to fifty-five point nine percent in kernel-level tests, leading to a time-to-first-token improvement of about thirty-six point eight percent.

Jane: The implication is that for anyone building systems that deal with long context LLMs, they shouldn't just build kernels that run each query in isolation; they need to design execution strategies that account for how those queries share context.

Lu: This work points toward a direction where understanding the workload structure across all active queries is more critical than the individual query selection process itself.

Meng: It changes how we think about optimizing inference—it’s not just about making one operation faster; it's about optimizing the entire prefill sequence based on expected data overlap.

Tom: That’s the gist of "QUILT: Rethinking Sparse-Attention Prefill through Shared Query Execution," and it really shows that leveraging workload correlation can give you real speedups when dealing with long context inference.

Conclusion: Tom: So we're wrapping up our look at QUILT now, looking at how they rethink sparse attention prefill through shared query execution.

Jane: Basically, this paper shows that instead of treating every sparse query as totally separate, you can actually let them talk to each other and reuse data.

Lu: They use this group-based query execution strategy to explicitly exploit the cross-query reuse of the Key Value data. It cuts down on redundant processing a lot.

Meng: From an engineering standpoint, that means we're not loading the same pieces of information from memory multiple times across different cores when they should be sharing it.

Lalam: This approach really improves how the model handles long contexts efficiently during prefill, making the whole process smoother for inference.

Tom: It sounds like they found a way to make that inherent correlation in sparse attention actually work for performance gains instead of just being a problem.

Jane: That's right. They show that by structuring the execution this way, you can get big speedups without sacrificing accuracy much at all.

Lu: The methodology involves three main parts: Shift-and-Compare Set Decomposition to figure out what's shared, cascaded sharing to find reuse at different levels, and tile-aware execution for better hardware mapping.

Meng: I like the idea of the tile awareness thing. That’s where things get tricky in real hardware; you have to make sure that a segment of work lines up well with the physical processing units.

Tom: And they showed some pretty solid numbers on it, reducing kernel latency by fifty-five point one percent and cutting processed KV data by nearly fifty-six percent.

Jane: So for someone just listening, it means that if you're running a big language model with long text inputs, the way the queries are organized matters a ton for how fast things start generating output.

Lu: It really suggests that optimizing these workloads isn't just about making one part faster; it’s about understanding the overall structure of all those concurrent requests.

Meng: And that structure can be exploited to get much better utilization out of the hardware we have on the chip.

Tom: QUILT comes from a team working on advanced transformer operators, and their work here really shows how deep architectural thinking can translate into real-world inference speedups.

Jane: It’s a big step because it moves away from treating every sparse query as an isolated task and starts looking at the whole group together.

Lu: The paper opens up possibilities for how we handle massive context windows where you have thousands of overlapping queries all running at once.

Meng: So what this means practically is that for deploying these large models, we need to start thinking about this kind of workload-aware scheduling right from the design phase.

Tom: It definitely gives us a new angle on prefill optimization and how we manage those long context situations efficiently.

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

Huawei Technologies Co., Ltd.

cs.LG

Submitted: 2026-10-08

Updated: 2026-10-08

Code: https://github.com/hicann/ops-transformer

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 90/100

The gist: The gist The proposed QUILT mechanism rethinks sparse-attention prefill by introducing a workload-aware execution strategy that exploits cross-query reuse to reduce redundant KV data processing and

Key concepts

Sparse Attention Problem: Sparse attention is used to handle very long contexts in LLMs by only attending to a subset of tokens. The problem is that current methods treat each query independently, leading neighboring queries to repeatedly load and process the same shared Key-Value (KV) data, wasting memory and computation.
Shift-and-Compare Set Decomposition (SCSD): This is a technique that converts irregular set operations into regular ones for better hardware performance. It sorts KV indices and uses shifts to efficiently find intersections and differences between the sets of tokens selected by neighboring queries, exposing parallelism.
Cascaded Sharing: This mechanism captures shared KV data hierarchically across different levels of query groups. It starts by finding entries shared among all queries in a large group and then recursively finds sharing within smaller subgroups, ensuring reuse is captured at multiple granularities.

Summary

The gist The proposed QUILT mechanism rethinks sparse-attention prefill by introducing a workload-aware execution strategy that exploits cross-query reuse to reduce redundant KV data processing and improve hardware utilization.

Motivation and Problem

Sparse attention has emerged as a promising approach to mitigate the growing cost of long-context attention, but existing query-parallel execution overlooks the strong correlation among sparse workloads across queries, leading to redundant memory traffic and computation because neighboring queries frequently select substantially overlapping KV entries The root cause is that existing sparse-attention kernels are workload-agnostic, executing each query according to its own Top-K selection without considering the correlation or sharing structure of sparse workloads across queries This results in KV entries shared by neighboring queries being repeatedly loaded from HBM into on-chip memory and independently dequantized on different compute cores, causing substantial overhead as shown in Figure 2.

QUILT Mechanism

To solve this issue, QUILT introduces a new workloadaware sparse-attention execution mechanism with groupbased query execution that explicitly exploits cross-query reuse QUILT jointly processes neighboring queries and reuses KV entries shared across their sparse workloads, reducing redundant KV data processing and improving hardware utilization.

QUILT introduces three key components to realize this execution efficiently:

** Shift-and-Compare Set Decomposition (SCSD)**

To address the overhead of identifying shared and query-specific KV entries, QUILT proposes Shift-and-Compare Set Decomposition (SCSD), a dataparallel algorithm that transforms irregular set operations into regular dataparallel primitives. SCSD concatenates and sorts the KV indices, then uses right- and left-shifted sequences to compute intersections and differences, exposing abundant datalevel parallelism. QUILT further pipelines SCSD with attention computation to hide its remaining overhead.

** Cascaded Sharing**

To accommodate heterogeneous sharing patterns, QUILT is equipped with cascaded sharing to capture cross-query reuse hierarchically at multiple granularities. This mechanism starts from a relatively large query group, extracts KV entries shared by all queries in the group, and recursively identifies additional sharing within smaller subgroups.

** Tile-Aware Execution**

To address tile underutilization caused by misaligned segments, QUILT adopts a tileaware execution strategy that jointly considers sharing granularity and hardware tile utilization. It employs importanceaware clipping to prune the lowest-ranked residual entries to eliminate the final underutilized tile while introducing negligible accuracy degradation.

Performance Evaluation

QUILT was evaluated 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 the amount of processed KV data by up to 55.9%. These kernel-level improvements translate into substantial end-toend benefits, reducing the average time-tofirst-token (TTFT) latency by up to 36.8% with negligible accuracy degradation.

Key Findings

The results demonstrate that exploiting cross-query workload structure can effectively translate the inherent correlation in sparse attention into tangible systemlevel performance gains. Specifically, increasing the sharing length from 0 to 2048 reduces the kernel latency by 42.74% and 33.25% for GLM-5.3 under TP and SP, respectively. Furthermore, cascaded sharing captures both four-way and two-way reuse, reducing the total number of processed KV entries to 8 in the example shown. The importanceaware clipping preserves the attention output more accurately than random clipping, achieving a headlevel mean cosine similarity of 1.0000.

Conclusion

Overall, QUILT consistently reduces sparse-attention kernel latency and translates these improvements into substantial endtoend prefill speedups across diverse longcontext workloads and parallel configurations. The work demonstrates the importance of exploiting cross-query workload structure, rather than treating sparse queries independently, for efficient longcontext LLM inference.

References

[3] CANN. 2025. OPS-Transformer: Advanced Transformer Operator Library for Ascend

[9] DeepSeek-AI. 2025. DeepSeek-V3.2: Pushing the Frontier of Open Large Language Models

[8] Pradeep Dasigi, Kyle Lo, Iz Beltagy, Arman Cohan, Noah A Smith, and Matt Gardner. 2021. A dataset of information-seeking questions and answers anchored in research papers

[9] DeepSeek-AI. 2026. DeepSeek-V4: Towards Highly Efficient Million-Token Context Intelligence

[5] Yaoqi Chen, Jinkai Zhang, Baotong Lu, Qianxi Zhang, Chengruidong Zhang, Jing Liu, Jingjia Luo, Di Liu, Huiqiang Jiang, Qi Chen, Bailu Ding, Xiao Yan, Jiawei Jiang

[6] Tri Dao. 2024. FlashAttention-2: Faster Attention with Better Parallelism and Work Partitioning

[7] Tri Dao, Daniel Y. Fu, Stefano Ermon, Atri Rudra, and Christopher Ré. 2022. FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness

[34] Zihao Ye, Lequn Chen, Ruihang Lai, Wuwei Lin, Yineng Zhang, Stephanie Wang, Tianqi Chen, Baris Kasikci, Vinod Grover, Arvind Krishnamurthy

[27] Mingcong Song, Xinru Tang, Fengfan Hou, Jing Li

[38] Wanjun Zhong, Lianghong Guo, Qiqi Gao, He Ye, and Yanlin Wang. 2024. MemoryBank: Enhancing Large Language Models with LongTerm Memory

[9] DeepSeek-AI. 2026. DeepSeek-V4.1-Flash: Pushing the Limits of KV Cache Compression

[39] Qihui Zhou, Peiqi Yin, Pengfei Zuo, and James Cheng. 2025. SparseServe: Unlocking Parallelism for Dynamic Sparse Attention in LongContext LLM Serving

[36] Jingyang Yuan, Huazuo Gao, Damai Dai, Junyu Luo, Liang Zhao, Zhengyan Zhang, Zhenda Xie, Yuxing Wei

[28] Jiaming Tang, Yilong Zhao, Kan Zhu, Guangxuan Xiao

[37] Zhenyu Zhang, Ying Sheng, Tianyi Zhou, Tianlong Chen, Lianmin Zheng, Ruisi Cai

[5] Yaoqi Chen, Jinkai Zhang, Baotong Lu, Qianxi Zhang

[32] Guangxuan Xiao, Yuandong Tian, Beidi Chen, Song Han

[35] Jiawei Yi, Ping Gong, Youhui Bai, Zewen Jin

[26] Jay Shah, Ganesh Bikshandi, Ying Zhang, Vijay Thakkar, Pradeep Ramani

[3] CANN. 2025.

Improvements for AI systems

textbfWeight-Aware Grouped Query Execution (QUILT): Enables cross-query reuse by grouping neighboring queries and reusing shared KV entries, directly addressing the strong correlation among sparse workloads across queries. This allows the system to jointly process neighboring queries and reuse KV entries shared across their sparse workloads, which reduces redundant KV data processing and improves hardware utilization.
textbfShift-and-Compare Set Decomposition (SCSD): Efficient set intersection via regular primitives. SCSD transforms irregular set operations into regular data-parallel primitives that can be efficiently executed on modern accelerators, ensuring that the overhead of identifying shared entries is largely hidden behind useful computation.
textbfCascaded Sharing for Heterogeneous Reuse: Captures reuse at multiple granularities. By using cascaded sharing to capture reuse at multiple granularities, the system can exploit coarse-grained and fine-grained reuse without committing to a single fixed sharing granularity, maximizing data reuse across varying query group sizes.
textbfTile-Aware Execution with Importance-Aware Clipping: Optimizes hardware utilization while preserving accuracy. The system employs tile-aware execution and importanceaware clipping to address poorly utilized tail tiles, ensuring the final residual entries are processed efficiently while maintaining fidelity by pruning only the lowest-ranked residual entries.