Partition the Support, Reconstruct the Residual: Training-Free Sparse Attention for Video Generation and World Models

Abstract

Block-sparse attention accelerates video transformers by grouping queries and keys and computing attention only between selected groups. However, it faces two challenges: (1) queries sharing a block route may attend to different keys; and (2) retaining most attention mass does not necessarily preserve the attention output. We find that partition choice affects both the overlap among grouped queries'preferred supports and how well an affine function of the sparse output can represent the difference between dense and sparse outputs. We introduce SparsePR, a training-free method combining Response-Coupled Partitioning with Probe-Fitted Residual Reconstruction. We first group paired key/value tokens by how their keys respond to sampled queries. We then group queries by their responses to the resulting key-group centroids for shared sparse routing. We compute exact attention on a small set of query rows and fit an affine correction to the differences between their dense and sparse outputs using weighted ridge regression. The fitted map predicts a residual for each unprobed query, which we add to its sparse output. We measure attention-output error as the relative L2 error with respect to each query's dense output. Across four video generation and world models, SparsePR reduces this error, averaged over unprobed queries, by 61.6--90.5% compared with semantic block-sparse attention without residual correction, at 22% executed-pair density including exact probes. SparsePR achieves 1.48x--2.61x end-to-end speedups over dense attention, with dense-reference PSNR of 24.42--31.84 dB at 21.9--26.0% realized executed-pair density. Project page: https://pardistaghavi.github.io/SparsePR-website/