Every Query Routes Itself: Accelerating Video Diffusion Transformers with Per-Query Routed Sparse Attention

Zhen Huang, Shuwei Li, Ruizhe Yao, Xinrui Chen, Danyi Liu, Haoyuan Liang, Zhiyu Ye, Qiuyan Sun, Bingwei Chen, Yiyuan Li, Xu Zhou, Haohuan FuarXiv 2026 · arXiv

TL;DR

Per-Query Routed Sparse Attention (PQRS) is a training-free method that accelerates video diffusion transformers by allowing every query to independently select its own set of key clusters. By ditching the traditional "query clustering" step and using a novel GPU kernel that leverages temporal stability in the softmax normalization, PQRS achieves up to a 2.10× end-to-end speedup while maintaining significantly higher visual fidelity than existing sparse attention baselines.

What Problem Does This Paper Address?

Video Diffusion Transformers (DiTs) are the current state-of-the-art for high-quality video generation, but they are computationally expensive. Generating a 720p, five-second clip involves processing over 75,000 tokens. Because self-attention cost grows quadratically with the number of tokens, it accounts for the vast majority of inference time—often taking nearly half an hour on a high-end H100 GPU.

To speed this up, researchers use sparse attention, which only computes the most important token interactions. Many current methods use clustering: they group similar queries and keys together, then have an entire cluster of queries share a single selection of key clusters. The authors of this paper identify a major "accuracy tax" in this approach: individual queries within a cluster often want to attend to different keys. Forcing them to share a selection leads to "recall" errors that degrade video quality.

Visual comparison showing PQRS preserves quality while significantly reducing latency compared to dense attention.

Methods

The authors propose PQRS, which breaks the "shared selection" paradigm through several key innovations:

  1. Per-Query Routing: Instead of clustering queries, PQRS only clusters keys. Each query independently scores the key centroids and selects its own "top-p" set of clusters to attend to. This ensures that every query gets exactly the keys it needs.
  2. Centroid Compensation: To avoid losing information from unselected keys, PQRS approximates their contribution using the cluster centroids (means). This "lightweight" approximation fills in the gaps left by sparsity.
  3. Cluster-Major Execution: Standard GPU kernels are optimized for blocks of queries attending to the same keys. To make irregular per-query selections efficient, the authors designed a kernel that traverses key clusters and buckets queries with identical selections into dense tasks.
  4. Cross-Step Softmax Offsets: Softmax requires a normalization factor (Log-Sum-Exp or LSE) that usually requires two passes over the data. PQRS observes that LSE is stable across denoising steps. It "borrows" the LSE from the previous step to use as a fixed offset, allowing the kernel to finish in a single, efficient pass.
Comparison of shared selection (a) vs. per-query routing (b). Per-query routing achieves higher recall by tailoring the selection to each individual query.

Datasets

The researchers evaluated PQRS on four major video generation models:

  • Wan2.1-T2V-14B (Text-to-Video)
  • Wan2.1-I2V-14B (Image-to-Video)
  • Wan2.2-T2V-A14B
  • HunyuanVideo-T2V-13B

Evaluation was performed using VBench (a comprehensive benchmark for video generation) and standard image quality metrics like PSNR, SSIM, and LPIPS compared against the "ground truth" of dense attention.

Key Insights and Ideas

  • The "Sharing" Penalty: The authors proved that the error in clustering-based attention comes primarily from queries sharing a selection, not from the clustering itself. As query clusters are refined (made smaller), accuracy consistently improves, peaking at one query per cluster.
  • Routing is Cheaper than Clustering: Surprisingly, scoring every query against key centroids is often computationally cheaper than running the k-means iterations required to cluster queries.
  • Temporal LSE Stability: One of the most clever "aha" moments is the realization that the softmax normalization factor changes very little between consecutive denoising steps (see Figure 5 in the paper). This allows for a "predictive" kernel design that avoids the overhead of online softmax rescaling.
The PQRS execution pipeline: key clustering, per-query routing, bucketing by selection code, and cluster-major attention with atomic adds.

Key Results

  • Speed: PQRS is the fastest training-free sparse attention method tested, reaching 1.75× speedup on Wan2.1 and 2.10× on HunyuanVideo.
  • Fidelity: It achieved a 28.9 dB PSNR on Wan2.1-T2V, significantly higher than baselines like SVG-EAR (~27.2 dB) or SVG2 (~25.7 dB).
  • Zero Degradation: On the VBench benchmark, which evaluates videos without a reference, PQRS showed no detectable degradation in subject consistency, motion smoothness, or aesthetic quality compared to full dense attention.

Limitations and Future Work

  • Hardware Specificity: The custom kernels are currently optimized for NVIDIA H100 GPUs using CuTe and CUTLASS. Porting these benefits to other architectures (like consumer GPUs or TPUs) would require additional engineering.
  • Fixed Hyperparameters: While the paper uses a single configuration for all models, further gains might be possible with per-model or per-layer calibration of the routing threshold ($p$).
  • Extreme Sparsity: The method was tested at densities around 20%. Exploring how well per-query routing holds up at even higher sparsity levels (e.g., <5%) remains an open question.

Summary updated

Abstract

Self-attention over long token sequences dominates the inference cost of video diffusion transformers. Clustering-based sparse attention clusters both queries and keys and lets all queries in a cluster share one selection of key clusters. We show that this sharing limits accuracy: with key clusters and density fixed, attention grows more accurate as the query clusters are refined, and is most accurate when each query selects on its own, which needs no query clustering at all. We therefore propose Per-Query Routed Sparse Attention (PQRS), a training-free method that clusters only keys, lets each query select its own key clusters, and compensates for the unselected ones with their centroids. Per-query selections leave no query tile with a shared key list, so PQRS traverses key clusters instead of queries, buckets queries with identical selections into dense tasks, and merges their partial results in one pass under a fixed softmax offset carried from the previous denoising step. On four text-to-video and image-to-video models from the Wan and HunyuanVideo families, PQRS is the fastest of all the sparse attention methods we evaluate and the closest to the dense output, reaching $28.9$ dB PSNR on Wan2.1-T2V and $35.4$ dB on HunyuanVideo at $1.66$--$2.10\times$ end-to-end speedup.
BibTeX
@misc{huang2026every,
  author = {Zhen Huang and Shuwei Li and Ruizhe Yao and Xinrui Chen and Danyi Liu and Haoyuan Liang and Zhiyu Ye and Qiuyan Sun and Bingwei Chen and Yiyuan Li and Xu Zhou and Haohuan Fu},
  title = {{Every Query Routes Itself: Accelerating Video Diffusion Transformers with Per-Query Routed Sparse Attention}},
  year = {2026},
  eprint = {2611.24479},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.24479},
}
Figure