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

Most training-free sparse attention work for video transformers treats sparsity as a row-wise property: find the queries with concentrated attention, skip the rest, done. SparsePR argues that framing is wrong in three distinct ways, and then builds a method around all three corrections.

The first problem is shared-route support. When eight queries share a single routing decision, the union of their individual key supports can be far larger than any one row's support. On Wan2.2, the median per-query support needed to retain a target attention mass expands substantially once those queries are pooled into a shared route. Cosmos-Predict2.5 shows the same expansion from a different cause: its rows are intrinsically broad. Either way, per-query concentration statistics don't tell you what a block-sparse operator actually needs to evaluate.

The second problem is that retained attention mass doesn't predict post-softmax error. Two query rows with nearly identical retained mass can produce very different output errors after renormalization, because the error depends on both the omitted mass and the difference between what the omitted and retained supports would have produced. Cosmos3-Nano is the clearest example of this sensitivity in the paper's experiments.

The third problem is that partition geometry changes how much of the remaining residual can be approximated by an affine function of the sparse output. This is the insight that makes SparsePR's reconstruction component tractable: if you choose partitions well, the residual you need to recover sits largely within a subspace that a small linear map from the sparse output can reach.

SparsePR addresses all three with two components. Response-Coupled Partitioning groups keys by their response profiles under a sample of queries, then uses the resulting group centroids to define query coordinates for shared routing—a single asymmetric pass, no alternating refinement. Probe-Fitted Residual Reconstruction evaluates a small set of exact query rows per head, fits a call-specific affine map from sparse output to residual, and applies it to unprobed rows restricted to the output subspace observed in the probe residuals.

The ablations are unusually honest about where the gains come from. Probe fitting accounts for most of the error reduction; response-coupled partitioning contributes a smaller but consistent improvement, particularly at the p99 tail and under limited probe budgets. On Wan2.2, the reconstruction overhead is only a few percent of total generation latency, so the fidelity gain is nearly free once the sparse operator is already running.

Across HunyuanVideo-13B, Wan2.2-I2V-A14B, Cosmos-Predict2.5-14B, and Cosmos3-Nano-16B, SparsePR achieves 1.48× to 2.61× end-to-end speedups at 22% to 26% realized executed-pair density while closely matching dense benchmark quality. The paper is careful to count probe rows in the density figure and to include all online overheads in the timing—a methodological discipline that makes the numbers trustworthy rather than optimistic.