PageWeaver: KV-Guided Query Unions for Sparse Attention

Zhiyuan Li; Zihan Li; Zefang Yuan; Lei Wang; Hao Wang

cs.DCOct 8, 2026

PageWeaver: KV-Guided Query Unions for Sparse Attention

Authors: Zhiyuan Li, Zihan Li, Zefang Yuan, Lei Wang, Hao Wang

Organizations: SenseTime

Abstract

Dynamic sparse attention limits the KV pages selected by each query, but a small support does not necessarily yield efficient GPU work. Query unions share page loads and populate Tensor Core tiles; their cost depends on which queries are grouped together. We present PageWeaver, an execution design that uses selected-page affinity to assemble query groups while preserving each query's original support and complete output ownership. A bounded GPU search produces query IDs, and an ID-aware two-CTA kernel consumes them without materializing reordered Q tensors or cross-page partial outputs. A direct KV-page union implementation provides a complementary design study of nonlocal reuse and reduction cost. With FP8 KV throughout, the H200 Union8 implementation achieves a 1.70x geometric-mean complete-call speedup over the measured FlashInfer path on six captures. Online regrouping further lowers latency by 3.26-7.66% on five selected 64K-context captures. Whole-model prefill throughput is 7.88-14.36% above the tested native path; the incremental regrouping benefit is smaller, with observed median gains of 0.47-0.73% at 32K/64K and regressions at 8K. A B300 comparison identifies cases where preparation cost and a stronger native kernel remove the advantage. These results separate execution-group reuse from the complete cost of exploiting it online.

Figures & tables

Figure 1: PageWeaver overview. Fixed TopK pages guide bounded query regrouping. Original IDs carry support, causal positions, and output addresses through a two-CTA Union8 kernel. The illustrated page sets are a subset; measured groups use up to eight queries and Top16.

Figure 2: The same support can induce different amounts of work. Adjacent groups mix two page communities; the page-side relation reveals nonadjacent queries sharing support. Regrouping reduces logical page visits from 16 to 8 and masked query–page slots from 16 to 0 in this illustrative example. All 16 selected edges are retained. The diagram uses two-query groups and two selected pages; the measured implementation uses groups of eight and Top16.

Figure 3: Hopper execution and buffer ownership. Each CTA has four warps, four queries, and two local 32 KiB KV slots. Memory and compute lanes share an illustrative left-to-right schedule. Event 1 marks KV readiness; event 2 permits slot 0 to be refilled only after both CTAs release page 0. The same warps execute QK, softmax, and PV, retaining each query’s state and original output ID. Empty subgroups still honor buffer lifetime. Widths are schematic, not measured durations.

Study	Workloads and repetitions
Base execution	Six captures, one request; L3/L32/L59, 0/16K prefixes. Seven rounds $\times$ 20 replays.
Online grouping	Five captures of one constructed 64K input: L39/r0–3, L43/r1; plus one 16K L51 control. Eleven rounds $\times$ 50.
H200 service	Five frozen prompts per 8K/32K/64K bucket; concurrency 1/4; three measured blocks per arm/cell.
B300 auxiliary	Eight TP4/rank0 captures: L3/L20/L32/L59 at two chunks. Seven rotated graph/eager rounds.

Table 1: Evaluation units and their scope. Replays measure timing variability; they do not create additional independent documents.

Figure 4: Base-kernel and group-size gains on H200. Complete-call timings use the same six captures and FP8 KV bytes. Backend families can differ in Q/P arithmetic; Union4 and Union8 use matched arithmetic. Repeated-round ranges show measurement variability. L denotes layer and p the prefix preceding the current 16K-query chunk.

Figure 5: Direct page execution exposes an opportunity and its cost. Controlled interleaved supports and model captures are distinct workload groups. Every timing includes required preparation and output processing. The constructed cases demonstrate a possible advantage of KV-page union; they do not estimate its prevalence in a model. Ranges cover repeated timing rounds.

Figure 6: Explaining the incremental regrouping gain. The complete online call is compared with original-order Union8 and execution using fixed grouped IDs on the same capture. Execution savings and the additional online cost determine the net saving (Equation 7 ). Structural statistics come from separate diagnostics of the same captures; page visits are logical counts, not HBM bytes. Timing repetitions do not expand the document sample size.

Figure 7: Whole-model H200 prefill and repeated regrouping effects. Three arms use identical prompts within each length/concurrency cell. Throughput medians and ranges retain every block; the incremental view pairs online and original Union8 within each round. Large positive ratios arise when an original-Union8 block slows down, and remain visible. Three technical repeats do not establish statistical significance across documents.

Figure 8: B300 auxiliary comparison. Each input is normalized to its faster existing native/original-Union8 backend. Online grouping can improve Union8 while still losing to native. These are complete eager operator timings, not service throughput or a controlled comparison of H200 and B300 hardware.

Backend	NRMS (%)
Union8	2.246–3.967
FlashInfer	2.288–4.077
Native SM90	6.258–9.120

Table 2: Numerical differences on six base-kernel captures. All rows use the same Triton reference and full output. Ranges are across inputs, not confidence intervals.

Explore similar work

QUILT: Rethinking Sparse-Attention Prefill through Shared Query Execution
Oct 8, 2026Zhenduo Zhao, Qihui Zhou, Mingcong Song +7LLM Inference Acceleration Sparse Attention
Huawei Technologies Co., Ltd. China
An Efficient Hybrid Sparse Attention with CPU-GPU Parallelism for Long-Context Inference
May 8, 2026Feiyu Yao, Zhixiong Niu, Xiaqing Li +3GPU Acceleration Self-Attention
Beijing University of Technology Beijing, China · Microsoft Research Beijing, China · Beijing Jiaotong University Beijing, China
PIVOT: Efficient Query-Group Indexing for Token-Level Sparse Attention
Jul 27, 2026Hong Liu, Yuan Cheng, Lin Niu +5LLM Inference Acceleration Efficient Attention
Tencent

Oct 8, 2026, cs.LGJ/K move · Enter open · S save

QUILT: Rethinking Sparse-Attention Prefill through Shared Query Execution

Zhenduo Zhao, Qihui Zhou, Mingcong Song, Zhiyi Chen+6

Huawei Technologies Co., Ltd. China

LLM Inference Acceleration Sparse Attention GPU Kernel Optimization

Open paper AskPDF arXiv

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.

Abstract

Explore similar work

QUILT: Rethinking Sparse-Attention Prefill through Shared Query Execution

An Efficient Hybrid Sparse Attention with CPU-GPU Parallelism for Long-Context Inference

PIVOT: Efficient Query-Group Indexing for Token-Level Sparse Attention