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 × 20 replays.
Online grouping
Five captures of one constructed 64K input: L39/r0–3, L43/r1; plus one 16K L51 control. Eleven rounds × 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.
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.
Long-context inference increasingly operates over CPU-resident KV caches, either because decoding-time KV states exceed GPU memory capacity or because disaggregated prefill-decode systems place KV data in host memory. Although block-sparse attention reduces attention cost in this setting, sparsity alone is insufficient for end-to-end efficiency. GPU-only designs remain constrained by PCIe bandwidth and metadata memory overhead, while CPU-GPU hybrid designs still suffer from substantial GPU idle time and bottlenecks in CPU-side top-k selection and sparse attention computation. Fluxion is built on three key insights: output-aware KV budgeting, head-specific and granularity-aware sparse configuration, and cross-device coordinated execution for sparse attention over CPU-resident KV caches. Guided by these insights, Fluxion combines a lightweight head-property predictor, a granularity-budget selector, and a priority-based scheduler to jointly optimize budget allocation, sparse configuration, and CPU-GPU execution overlap. This co-design enables hybrid sparse attention to achieve both accuracy and system efficiency in long-context inference. Across 2 models, 3 benchmarks, and 40 tasks, Fluxion preserves quality well -- the worst average degradation is only -0.26 relative to FULL, while delivering 1.5×-3.7× speedup over the strongest fixed sparse hybrid baseline, whose KV budget is only 0.05.
Feiyu Yao, Zhixiong Niu, Xiaqing Li +3
Beijing University of Technology Beijing, China · Microsoft Research Beijing, China · Beijing Jiaotong University Beijing, China
Token-level sparse attention, as implemented by DeepSeek Sparse Attention (DSA) in production systems, makes the downstream attention efficient but shifts the bottleneck to the indexer that feeds it. To select the top-k tokens for each query, the indexer must still score every preceding token, incurring a cost of O(L^2) per layer for a sequence of length L. We observe that this per-query scan is largely redundant: nearby queries select highly overlapping top-k tokens, and the indexer scores are long-tailed along the key axis. We exploit these properties in PIVOT, Proxy Indexing Via One full-prefix Traversal, a training-free, drop-in replacement for the DSA indexer that shares one prefix scan across a group of nearby queries. PIVOT aggregates a group into a single proxy query, performs one shared full-prefix scan to obtain a candidate set, and then selects a top-k for each query from that set. Two variants trade speed for fidelity: PIVOT-Reuse shares the proxy top-k across the group for maximum speed, whereas PIVOT-Refine re-scores the candidate set with the indexer of each query and then selects an individual top-k, matching the dense indexer at a small additional cost. A single algorithm covers both inference phases, differing only in how groups are formed: fixed-size groups of consecutive queries in prefill, and the queries decoded together in one multi-token prediction (MTP) step in decode. On DeepSeek-V3.2 and GLM-5.1 across LongBench and RULER, PIVOT matches the accuracy of the dense DSA indexer while accelerating it by up to 4x and reducing end-to-end latency by up to 1.6x at long context.