Organizations: Computer Science and Engineering, Indian Institute of Technology Bombay, India · Electrical Engineering and Computer Sciences, University of California, Berkeley, USA
Diffusion Transformers (DiTs) are the dominant architecture for video generation, but their quadratic attention complexity results in substantial computational cost and latency. Permuted block-sparse attention (PBSA) offers a promising approach to reducing this cost by selectively computing blocks of a semantically permuted attention matrix. However, existing approaches typically select only the top few key blocks for each query block, following a top-p paradigm. We find that top-p selection can be highly sample inefficient in high-entropy attention regimes, which are common in video generation. In these regimes, we show that sampling can provide substantially better approximations under the same computational budget. More generally, we cast block selection as importance sampling, where the top-scoring keys form an exact set that is computed in full and the remaining keys are represented by a sample drawn in proportion to their estimated attention and reweighted by inverse sampling probability. Building on this formulation, we present InstaGen, which can be parameterized by any PBSA method: it replaces the method's block selection with an exact set plus a weighted sample. Each query cluster draws one sample shared by all its queries, so the sampled keys form blocks amenable to efficient GPU execution. In this paper, we take the SVG family of PBSA methods and show that, on Wan2.1-T2V-1.3B and Wan2.1-T2V-14B, InstaGen parameterized by SVG2 improves PSNR over SVG2 by 3.4 dB and 2 dB, respectively, at matched attention density, and by 1.6 dB and 2.2 dB at matched wall-clock time. On Wan2.1-T2V-14B, InstaGen also beats SVG-EAR by 1.1 dB PSNR at nearly the same density while running faster (1.65x against 1.48x over dense).
Figures & tables
Figure 1: Frames from a single Wan2.1-T2V-1.3B generation (720p, 81 frames, 50 steps). InstaGen achieves higher pixel fidelity, reaching a PSNR of 25.50 dB at a lower attention density of 32% when compared to SVG and SVG2.
Figure 2: InstaGen gives higher quality than SVG2 at both matched density and matched latency on Wan2.1-T2V-1.3B. Left: PSNR against generation time per video. Right: PSNR against attention density, the share of attention computed over the whole generation. SVG2 uses the configuration from its paper ( Cq=100 , Ck=500 , full attention for the first 30% of steps, key floor 0.1) at top- p 0.5, 0.75, 0.9 and 0.95. InstaGen runs exact + sampled budgets from 4+4% to 32+32% at two clustering configurations for uniform and one for importance, with the same warmup and without it.
Figure 3: Overview of InstaGen. (a) Queries and keys are clustered into groups. (b) Centroid scores give each key group a probability π of being used by each query group. (c) The top key group is always kept; the remaining keys are sampled in proportion to π and weighted by 1/π . (d) Queries in a group share the same keys, so attention runs over dense blocks in one kernel.
Dense-reference quality
VBench
Efficiency
Method
E + S
Warm-up
PSNR ↑
SSIM ↑
LPIPS ↓
ImgQual ↑
AesQual ↑
SubCons ↑
BackCons ↑
Density ↓
Speedup ↑
Wan2.1-T2V-1.3B
Dense
–
–
–
–
0.6689
0.6416
0.9569
0.9612
100%
1.00 ×
SVG
–
✓
23.62
0.794
0.214
0.6837
0.6378
0.9489
0.9518
49.85%
1.47 ×
SVG2 ( p=0.95 )
–
✓
26.11
0.834
0.122
0.6185
0.6091
0.9420
0.9495
48.92%
1.65 ×
SVG-EAR
–
✓
28.29
0.910
0.064
0.6625
0.6357
0.9497
0.9543
34.87%
1.63 ×
Table 1: Main results on Wan2.1-T2V-1.3B and 14B. PSNR, SSIM and LPIPS compare each video with the dense video from the same seed, and all quality metrics are averaged over the 22 VBench prompts. E + S : exact and sampled share of keys per sparse call with dense warmup, as prescribed by each baseline’s paper; InstaGen uses SVG2’s (first 30% of steps and 3% of layers). Density is overall, counting warmup calls as full attention. Speedup is end-to-end wall-clock on one H100 against a dense run. Bold: best sparse method in each column.
Figure 4: InstaGen approximates attention more accurately than prior sparse methods. Left: relative L2 error of one self-attention call from Wan2.1-T2V-1.3B against exact attention. Importance sampling gives the lowest error at every density, several times below SVG2. Right: per-block, per-head error over one full generation averaged across all steps. InstaGen (uniform, 16+16, no warm-up) keeps the error low everywhere at 32% density, while SVG2 ( p=0.9 , warm-up counted as zero error) leaves large errors in individual heads and layers despite computing 46%.
Figure 5: Warmup ablations on Wan2.1-T2V-14B (720p, 81 frames, 50 steps). InstaGen with uniform sampling runs its first 0, 5, 10 or 15 of 50 steps at full attention (warmup), ranging from 4+4% to 32+32% budget. SVG2 runs at its paper configurations at top- p 0.1, 0.25, 0.5, 0.75, 0.9 and 0.99. A 5–10 step warmup matches or beats the 15 steps SVG2 uses. The hollow diamond is SVG2 without its one-layer warmup; the InstaGen runs have none. The prompt used is svg2_ex1 , Appendix A.1 .
Figure 6: InstaGen with importance sampling matches SVG2’s quality at much lower density. (a) PSNR against overall attention density (warm-up steps count as dense), averaged over 22 VBench prompts on Wan2.1-T2V-1.3B (720p, 81 frames, 50 steps). SVG2 in its paper configuration ( p=0.9 ) reaches 25.03 dB at 44.1%; InstaGen (importance sampling) reaches the same PSNR at 34.0% with the same 30% warm-up, and at 20.0% with no warm-up. (b) Denoising time against the number of frames on one H100 SXM, on one prompt ( svg2_ex1 , Appendix A.1 ; VAE decoding excluded), with InstaGen (importance sampling) at 4+4% with the 30% warm-up and at 14+14% with no warm-up, budgets at which it beats SVG2 ( p=0.9 ) on PSNR, SSIM and LPIPS on this prompt at 81 frames. At 561 frames dense takes 162 min, SVG2 82.8 min (1.97 × ), and InstaGen 61.9 min (2.62 × ) with warm-up and 57.3 min (2.83 × ) without.
Appendix figures & tables1 asset
Supplementary material from the paper’s appendix.
Appendix
ID
VBench dimension
Prompt
d22-01
appearance style
a shark is swimming in the ocean by Hokusai, in the style of Ukiyo
d22-02
appearance style
A couple in formal evening wear going home get caught in a heavy downpour with umbrellas, in cyberpunk style
Diffusion Transformers (DiTs) dominate video generation but suffer from high inference cost due to the quadratic complexity of self-attention. Sparse attention mitigates this by skipping unnecessary computation in the attention matrix, but existing methods apply a fixed sparsity ratio throughout denoising and struggle to accurately determine which computations to skip. To address these limitations, we analyze attention dynamics through attention entropy and mean attention distance, and find that attention becomes increasingly concentrated across denoising steps. We further observe that blocks selected early continue to capture a large fraction of the total attention weight at later steps. These findings suggest two acceleration opportunities: the sparsity ratio should grow as denoising progresses, and earlier search results can be reused to reduce the search space. Based on these findings, we propose Growing Sparsity and Reduced Search (GSRS), a training-free framework that retains more computation early and progressively reduces it later, while restricting subsequent searches to an early candidate set to reduce search overhead. GSRS adopts Top-p selection for adaptive sparsity control, supported by a precise evaluation scheme that computes exact attention weights within the FlashAttention computation at negligible overhead. Experiments on HunyuanVideo and Wan 2.1 validate that GSRS achieves 1.55×--2.21× speedup while maintaining generation quality comparable to full attention.
Diffusion transformers have achieved remarkable success in high-quality video generation, yet their reliance on spatiotemporal 3D full attention incurs prohibitive computational cost due to the quadratic complexity of attention. Block sparse attention is a common approach to mitigate this by focusing computation on important regions. However, attention maps in DiTs exhibit inherently dynamic and fine-grained sparsity, which causes existing block sparse attention methods to degrade significantly in quality, especially at high sparsity ratios. In this paper, we revisit block sparse attention and derive a theoretical lower bound on attention recall to characterize the key factors governing its effectiveness. Guided by these insights, we propose DFSAttn, a training-free sparse attention framework that enables dynamic, fine-grained sparsification efficiently. DFSAttn incorporates three core designs: Hilbert curve-based token reordering to achieve fine-grained sparsity while preserving efficient GPU execution, hierarchical block scoring for accurate block importance estimation, and sparse mask caching with adaptive ratios to balance accuracy and efficiency. Experimental results demonstrate that DFSAttn consistently outperforms prior methods under high sparsity, achieving up to 2.1× end-to-end speedup while maintaining high generation quality. Our code is open-sourced and available at https://github.com/jessica-hujie/DFSAttn.
Diffusion transformers are essential for high-fidelity video generation, but long token sequences make attention a dominant inference bottleneck. Training-free dynamic sparse attention alleviates this bottleneck by computing only selected key-value blocks, yet existing methods struggle to sparsify attention both efficiently and accurately for two reasons: (1) Rigid, unpredictable, and costly routing: selecting a fixed fraction of top-ranked blocks by proxy score imposes fixed budgets, whereas retaining blocks to reach a target cumulative proxy probability mass yields dynamic but potentially imbalanced budgets; both incur non-negligible overhead from computing and materializing proxy scores. (2) Lossy keep-or-drop sparsification: unselected blocks are discarded entirely, degrading accuracy under aggressive sparsity. These limitations motivate cheaper dynamic-budget routing while limiting accuracy degradation. In this paper, we introduce training-free Sol-Attn (Sparsifying online attention), which unifies dynamic routing, sparse computation, and approximation correction in a single online-softmax pass, achieving a better accuracy-efficiency trade-off in sparse attention. The core of Sol-Attn is on-the-fly block thresholding with proxy-score reuse, which selects critical blocks by comparing block proxy scores against a threshold during online softmax. This design enables dynamic yet controllable block budgets without materializing the proxy map, while directly reusing the proxy scores of unselected blocks to approximate their contribution. Experiments across image and video generation tasks show that Sol-Attn advances the quality-efficiency frontier of training-free sparse attention, delivering 2.1 times and 2.3 times end-to-end speedups for video generation and editing, respectively, while preserving visual quality.