InstaGen: Group-Shared Importance Sampling for Fast Video Generation

Introduction

Diffusion Transformers (DiTs) have been instrumental in achieving state-of-the-art quality in image and video generation [14, 20, 7]. However, image and video generation with DiTs remains computationally expensive, primarily due to the quadratic cost of attention, which is repeated across layers and diffusion steps. As a result, generating even short videos can be extremely slow. For instance, generating a single 5-second 720p video (81 frames, 50 denoising steps) with Wan2.1-T2V-14B takes about 22.6 minutes on one H100 GPU. Improving generation latency is therefore essential for enabling the efficient generation of high-quality, long-form videos.

Training-free sparse attention is a natural paradigm for reducing the computational workload of attention in existing video generation models and improving generation latency. However, effective attention sparsity must strike a unique balance between three often non-aligned goals: (1) Quality per query: Each query token should, in effect, attend to the tokens that are most important for that specific query. (2) Efficiency: The sparsity pattern should be amenable to block-based execution so that it can naturally integrate with FlashAttention [11] and benefit from hardware acceleration. (3) Alignment with the underlying model: While each query may, in principle, attend to its most important tokens, the approximation error introduced by sparsity can accumulate across layers and diffusion steps, potentially derailing the model and causing substantial downstream quality degradation. Permuted block-sparse attention (PBSA) methods such as SVG2 and SVG-EAR [19, 23] have primarily focused on addressing the first two goals through clustering query and key tokens, permuting the tokens into contiguous blocks, scoring each block from the cluster centroids, and computing only the selected blocks with a block-sparse attention kernel. However, their treatment of the third goal often results in an unfavorable trade-off between sparsity and downstream generation quality.

To maintain alignment, it is critical to ensure that the local approximation error in attention computation under sparsity is well controlled. Existing PBSA methods employ top-$p$ as the underlying sparsification strategy. However, for high-entropy attention distributions, top-$p$ ends up retaining a large number of tokens. Thus, the top-$p$ paradigm inevitably sacrifices either efficiency or approximation quality. In fact, to the best of our knowledge, all existing sparse video generation methods retain 30% dense steps, as any sparsification under the top-$p$ paradigm leads to large approximation errors. This calls for a paradigm shift in sparsity. InstaGen moves away from the deterministic sparsification underlying existing PBSA methods and instead employs stochastic sampling based on importance scores. We find that stochastic sparsity offers a significantly better quality-efficiency tradeoff. In fact, it enables us to completely eliminate dense steps, achieving fully sparse inference for video generation across all layers and all steps.

In InstaGen, we formalize sparse attention as a sampling problem. For each query cluster, the keys are split into an exact set of top-scoring keys, whose attention is computed exactly, and a residual whose contribution is estimated from a sample of its keys reweighted by inverse sampling probability [5]. Top-$k$ selection is the special case with no sample. We consider two ways of drawing this sample, importance and uniform sampling. In importance sampling, the attention estimated from the cluster centroids sets the sampling probabilities, and we draw the sample by proportional-to-size sampling without replacement (PPSWOR; § 3.2.1). Uniform sampling includes every residual key with equal probability, thus making it a special case of importance sampling. In this paper, we parameterize InstaGen by SVG2, i.e., it keeps SVG2’s clustering and block scoring and replaces its top-$p$ selection. This choice is not a requirement, and the same estimator can be applied to other methods that produce block scores, such as SVOO [10].

Sampling addresses the third goal, but if done naively it can conflict with the second, i.e., efficient execution. If each query had its own sample, it would attend to its own random keys. Then no two queries share a block of keys, and FlashAttention cannot run it. Drawing about 75,600 separate samples per head in every attention call (Wan2.1 at 720p, 81 frames) is also costly. We instead draw one sample per query cluster, using the probabilities computed from its centroid. All queries within the cluster share the resulting sampled keys, yielding a group-shared sampling scheme. This amortizes the sampling overhead across queries while producing a block structure: the cluster’s queries and the sampled keys form a dense block, which is compatible with FlashAttention and can be efficiently accelerated on GPUs. Moreover, sharing a sample adds no bias. For every query in the cluster, the estimates of the attention sums stay unbiased, because the weights use the probabilities the keys were actually drawn with.

We evaluate InstaGen against SVG [16], SVG2, and SVG-EAR on Wan2.1-T2V-1.3B and Wan2.1-T2V-14B, measuring fidelity to the dense model’s video (PSNR, SSIM [15], LPIPS [22]) and video quality with VBench [6]. Over SVG2, InstaGen improves PSNR by 3.4 dB and 2 dB on the 1.3B and 14B models, respectively, at matched attention density (Figure 2, § 5), and on the 14B model it beats SVG-EAR by 1.1 dB PSNR at nearly the same density while running faster. On Wan2.1-T2V-1.3B, InstaGen needs no dense warmup: it runs sparse attention at every diffusion step and still outperforms SVG and SVG2 run with their warmup (Figure 1). Removing the warmup matters most for long videos, because a dense step grows almost quadratically with video length: generating 561 frames, InstaGen without warmup takes 57.3 minutes, against 82.8 for SVG2 and 162 for dense attention (Figure 6).

Vector (PDF)

Vector (PDF)

Related Work

Structured sparse attention for video diffusion. Sparse VideoGen (SVG) profiles sampled query rows to assign each head a spatial or temporal sparsity layout [16], and Radial Attention uses a static $O(S \log S)$ mask whose density decays with temporal distance [9]. Both fix the layout structurally rather than adapting it to content.

Content-adaptive sparse routing. Other methods estimate block importance from content: XAttention scores blocks by antidiagonal sums [18], AdaSpa searches hierarchical block patterns online [17], and SpargeAttention filters blocks with compressed query/key representatives and an in-kernel softmax-aware test [21]. SVG2 clusters queries and keys, permutes clusters into contiguous storage, and selects cluster pairs by a centroid score [19]. AdaCluster adapts the clustering to layerwise token geometry [13], and SVOO combines an offline per-layer sparsity schedule with online query–key co-clustering [10]. These methods route each query cluster by a single centroid-derived score. InstaGen reuses this component to score token importance.

Recovering skipped attention. SVG-EAR approximates skipped blocks with key/value centroids and recomputes those with high predicted error [23]; SparsePR learns an affine residual correction from the computed attention [12]; and Sol-Attn estimates the skipped contribution from the computed subset [8]. Attention, developed for LLM decoding, instead samples the residual, giving an unbiased estimate with a probabilistic error guarantee [3]. We extend this idea by casting sparse attention as importance sampling, under which top-$k$ selection and residual sampling arise naturally.

Changing the model. Veda distills full-attention tile distributions into a learned selector [4]; SANA-Video trains a block-linear video diffusion transformer [2], and SANA-Video 2.0 a hybrid with periodic softmax anchors and cross-depth attention residuals [1]. We focus on training-free sparse attention.

Background

Scaled Dot-Product Attention

Consider a single self-attention head with queries, keys, and values $Q$, $K$, $V \in\mathbb{R}^{n \times d}$, where $n$ is the sequence length and $d$ is the head dimension. For query $i$, the scaled attention logits are

Softmax attention then produces the output

or, equivalently, as the ratio of two sums

Evaluating dense attention for all $n$ queries costs $O(n^2d)$ per head. Sparse and sampled approximations target the sums in Eq. (3): rather than including every key/value index $j$, they retain a small subset of indices and estimate the contribution of the remainder. The sampling estimators described below apply directly to approximating $n_i$ and $z_i$.

Sampling with Probabilities Proportional to Size

Consider the problem of estimating a sum $Y = \sum_{j=1}^{n} y_j$ from a subset of $m < n$ of its terms. This problem underlies sparse attention, since the numerator and denominator in Eq. (3) are sums of $n$ terms: setting $y_j = e^{\ell_{ij}}v_j$ recovers $n_i$, and setting $y_j = e^{\ell_{ij}}$ recovers $z_i$. We assume that each term is associated with a score $s_j > 0$ that is much cheaper to compute than $y_j$ and serves as an estimate of its magnitude $\lvert y_j\rvert$. The goal is an unbiased estimator of $Y$ with low variance under a budget of $m$ terms.

PPSWOR: Probabilities Proportional to Size Without Replacement

PPSWOR is an importance sampling scheme that draws a sample $S$ of $m$ distinct terms such that terms with larger scores, and hence a larger expected contribution to the sum, are more likely to be included. The scheme is characterized by the inclusion probabilities $\pi_j = \Pr[j \in S]$, which satisfy $\sum_{j=1}^{n}\pi_j = m$ and are set proportional to the scores, $\pi_j \propto s_j$. Capping the target $ms_j/\sum_{j'}s_{j'}$ at 1 and renormalizing gives

The left-hand side is nondecreasing in $\lambda$, so $\lambda$ is well defined. The terms with $\pi_j = 1$ form the heavy set $\mathcal{H} = \{j : \lambda s_j \ge1\}$, which is the top-$k$ set by score, with $k = \lvert\mathcal{H}\rvert$ determined by the scores rather than fixed in advance. The sample therefore consists of all of $\mathcal{H}$ and $m-\lvert\mathcal{H}\rvert$ residual terms, each included with probability exactly $\pi_j < 1$.

The Horvitz–Thompson estimator [5] weights each sampled term by the inverse of its inclusion probability. For the sample above, it separates into a deterministic part and a sampled part:

This estimator is unbiased for any choice of scores, and top-$k$ selection is recovered by dropping the second term. We use this formulation in InstaGen.

Algorithm 1 InstaGen attention for one head. $\ell_{ij} = q_i^\mathsf{T} k_j / \sqrt{d}$ are the logits of § 3.1, $\bar{q}_g$ and $\bar{k}_c$ are the centroids of query group $g$ and key cluster $c$, $c(j)$ is the cluster of key $j$, and $|c|$ is its size. Budgets are fractions of the sequence length: $\rho_E+\rho_S$ means $m_E = \rho_E n$ and $m_S = \rho_S n$ (written $E+S$, in percent, in Section 5). Warmup calls, when used, compute dense attention instead.

Input: $Q, K, V \in\mathbb{R}^{n \times d}$; budgets $m_E, m_S$; sampler UNIFORM or IMPORTANCE

Output: $\hat{O} \in\mathbb{R}^{n \times d}$

1. Cluster queries into $C_q$ groups and keys into $C_k$ clusters ▷ $k$-means, warm-started

2. $s_{gc} \leftarrow\exp(\bar{q}_g^\mathsf{T}\bar{k}_c/\sqrt{d})$ for every pair $(g,c)$ ▷ centroid scores

3. for each query group $g$ do

4. $\mathcal{E}_g \leftarrow$ whole clusters by decreasing $|c|\,s_{gc}$ until $|\mathcal{E}_g| \approx m_E$ ▷ exact keys

5. $\mathcal{R}_g \leftarrow\{1,\ldots,n\} \setminus\mathcal{E}_g$ ▷ residual keys

6. if sampler is UNIFORM then

7. $\pi_j \leftarrow m_S/|\mathcal{R}_g|$ for all $j \in\mathcal{R}_g$

8. $\mathcal{S}_g \leftarrow m_S$ keys of $\mathcal{R}_g$, uniformly without replacement

9. else

10. $\pi_j \leftarrow\min(1,\lambda_g s_{g,c(j)})$, with $\lambda_g$ such that $\sum_{j\in\mathcal{R}_g}\pi_j = m_S$ ▷ § 3.2.1

11. $\mathcal{S}_g \leftarrow$ systematic PPS sample of $\mathcal{R}_g$ with probabilities $\pi_j$

12. end if

13. $w_j \leftarrow1$ for $j \in\mathcal{E}_g$, $w_j \leftarrow1/\pi_j$ for $j \in\mathcal{S}_g$ ▷ Horvitz–Thompson

14. $\hat{o}_i \leftarrow\sum_{j\in\mathcal{E}_g\cup\mathcal{S}_g}\operatorname{softmax}_j(\ell_{ij}+\log w_j)v_j$ for all $i \in g$ ▷ $= \hat{n}_i/\hat{z}_i$

15. end for

16. return $\hat{O}$

InstaGen

InstaGen builds on the observation in vAttention [3] that sampling can outperform top-$p$ selection in high-entropy regimes. InstaGen formulates sparse attention as a sampling problem, which leads naturally to an importance sampling formulation with uniform sampling as a special case.

InstaGen performs PPSWOR sampling using scores that serve as proxies for the exponentiated raw attention scores. We obtain these scores from clusters for two reasons: the centroid of a cluster is a cheap proxy that represents the scores of its tokens, and clustering lets us permute the tokens into contiguous blocks, so that attention follows the block structure of FlashAttention [11] and realizes the theoretical speedup of sparsity. Such scores can come from any method that produces them, such as SVG2 [19] and SVOO [10], among others. For clarity, we adopt the clustering of SVG2, in which the queries and keys are clustered separately with $k$-means into $C_q$ query groups and $C_k$ key clusters with centroids $\bar{q}_g$ and $\bar{k}_c$. The score of query group $g$ and key cluster $c$ is

which is the proxy for the exponentiated attention score of every query in $g$ with every key in $c$.

These scores are used to perform PPSWOR as described in § 3.2.1. All queries in a group share the same scores, and so do all keys in a cluster, so the whole procedure is carried out once per query group. For each query group, the total budget is split in advance into an exact budget $m_E$ and a sampling budget $m_S$. The exact budget is handled first: the key clusters with the largest total score are selected deterministically until $m_E$ is reached, and we set $\pi_j = 1$ for their keys.

PPSWOR with budget $m_S$ is then applied to the remaining keys, the residual. Each residual key $j$ receives an inclusion probability $\pi_j$ proportional to its score and capped at 1, as in equation 4, such that the sample contains $m_S$ keys. Keys whose probability reaches 1 are promoted, that is, they are always retained like the exact keys; since scores are constant within a cluster, whole clusters are promoted. The remaining keys ($\pi_j < 1$) are sampled using PPS, and the sample is shared across all queries of the group. In our kernel, it is drawn with systematic PPS sampling, which attains the prescribed inclusion probabilities exactly. The resulting attention map is illustrated in Figure 3.

Vector (PDF)

This sharing across queries is what keeps the kernel GPU-friendly: all queries in a group attend to the same keys, so queries and attended keys form dense blocks. Let $\mathcal{S}$ be the PPS sample over the residual. For a query $i$, the estimators of the numerator $n_i$ and denominator $z_i$ in equation (3) can be written as

where $\mathbb{I}(\cdot)$ is the indicator function, and the output is $\hat{o}_i = \hat{n}_i / \hat{z}_i$. Note that both the numerator and denominator estimators are unbiased:

Hardware Efficiency. InstaGen is designed to be compatible with FlashAttention ([11]). All queries in the same cluster attend to the same set of keys, whether exact or sampled. Thus, attention is computed in blocks rather than per query (each selected 128-key tile is either entirely exact or entirely sampled), with the importance weights applied as a logit bias. The sample is drawn on the GPU, where we implement the attention kernel by modifying FlashAttention-3 for NVIDIA Hopper GPUs. Clustering, scoring, and sampling run as separate GPU steps before the attention kernel. Figure 3(d) illustrates this implementation.

Residual Approximation. Like SVG-EAR ([23]), InstaGen estimates the attention of skipped keys instead of dropping it. SVG-EAR does so deterministically, by replacing each skipped cluster with its centroid key and mean value. InstaGen instead samples actual skipped keys with inverse-probability weights, giving unbiased estimates of the attention sums whose variance decreases as the sample grows.

Discussion on Alternative Sampling Schemes. Several sampling schemes can be used to estimate the residual. While we use PPSWOR in our kernel, other choices are possible, and we discuss them below.

PPSWR. Sampling with replacement can be used to estimate the residual in Algorithm 1. Its downside is that keys may be sampled repeatedly. While this matters little statistically at small budgets, it becomes undesirable at large ones; for instance, it does not recover dense attention even when the budget equals that of dense attention. On the other hand, it is easier to analyze: the independence of the samples allows us to apply strong tail bounds, which can be used to devise a verifiable approximation of attention for sparse video generation ([3]).

PPSWOR. Sampling without replacement has several desirable properties for our algorithm. For instance, at large budgets, PPSWOR is guaranteed to cover a larger number of distinct keys. In the limit, it covers all keys for each query and recovers exact dense attention. However, its downside is that the variance of the estimator is difficult to analyze and, consequently, so are analytical guarantees on the approximation error.

Poisson sampling. Poisson sampling is another technique for residual sampling, in which each key is included independently by a separate Bernoulli trial. Its advantage is that the sample is obtained without replacement; however, the sample size equals the budget only in expectation. Nevertheless, the independence again allows us to apply strong tail bounds to the estimators, and thus to obtain a verifiable sparse attention approximation.

These alternative schemes can be seen as extensions of this work, and we leave their exploration to future work.

Experiments

Models. We evaluate InstaGen on two open-source text-to-video diffusion transformers, Wan2.1-T2V-1.3B and Wan2.1-T2V-14B (Wan Team, [14]), generating 81-frame videos at 720p (720 × 1280). After 3D-VAE tokenization, each video has 21 latent frames of 3,600 tokens, so every self-attention call spans 75,600 tokens. We sparsify only self-attention; cross-attention to the text embeddings remains dense.

Metrics. We measure how closely each sparse method reproduces the dense model’s video with Peak Signal-to-Noise Ratio (PSNR), Structural Similarity Index Measure (SSIM) (Wang et al., [15]) and Learned Perceptual Image Patch Similarity (LPIPS) (Zhang et al., [22]). Each method is compared with the dense video from the same pipeline on the same hardware. We assess perceptual quality with four VBench (Huang et al., [6]) dimensions: Imaging Quality (ImgQual), Aesthetic Quality (AesQual), Subject Consistency (SubCons) and Background Consistency (BackCons). Efficiency is measured by density, the fraction of query-key pairs computed relative to full attention. Table 1 reports overall density, counting dense warm-up calls as full attention. End-to-end efficiency is measured by wall-clock speedup over dense generation.

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×
InstaGen (uniform)	8+8	✓	27.12	0.856	0.093	0.6331	0.5798	0.9411	0.9467	41.20%	1.76×
InstaGen (uniform)	16+16		26.54	0.876	0.088	0.6718	0.6490	0.9521	0.9596	32.00%	1.68×
InstaGen (uniform)	16+16	✓	28.98	0.906	0.057	0.6434	0.5976	0.9528	0.9572	52.40%	1.49×
InstaGen (importance)	8+8	✓	27.69	0.869	0.071	0.6826	0.6272	0.9665	0.9591	41.20%	1.72×
InstaGen (importance)	16+16		27.72	0.891	0.061	0.6909	0.6312	0.9702	0.9673	32.00%	1.63×
InstaGen (importance)	16+16	✓	29.39	0.906	0.053	0.6864	0.6306	0.9701	0.9652	52.40%	1.46×
Wan2.1-T2V-14B
Dense	–	–	–	–	–	0.6876	0.6676	0.9677	0.9715	100%	1.00×
SVG	–	✓	21.01	0.742	0.202	0.6892	0.6742	0.9653	0.9728	51.11%	1.41×
SVG2 ($p=0.9$)	–	✓	22.38	0.749	0.167	0.6927	0.6239	0.9661	0.9704	53.34%	1.53×
SVG-EAR	–	✓	23.55	0.827	0.126	0.6848	0.6700	0.9666	0.9677	42.19%	1.48×
InstaGen (uniform)	8+8	✓	22.91	0.771	0.136	0.6963	0.6345	0.9763	0.9693	42.67%	1.67×
InstaGen (uniform)	16+16		19.10	0.664	0.237	0.6792	0.6334	0.9736	0.9748	32.00%	1.63×
InstaGen (uniform)	16+16	✓	23.55	0.796	0.122	0.6990	0.6361	0.9763	0.9711	53.59%	1.45×
InstaGen (importance)	8+8	✓	24.61	0.871	0.083	0.6877	0.6701	0.9701	0.9701	42.67%	1.65×
InstaGen (importance)	16+16		21.84	0.811	0.138	0.6858	0.6623	0.9730	0.9753	32.00%	1.58×
InstaGen (importance)	16+16	✓	25.50	0.887	0.072	0.6857	0.6652	0.9699	0.9716	53.59%	1.42×

Prompts. We use 22 prompts from the VBench prompt suite (Huang et al., [6]), the two prompts with the most motion from each of its eleven per-dimension lists, as judged by an LLM. Each prompt

is generated once with a fixed seed, shared by all methods. Figure 5 and Figure 6(b) use a single prompt, the first example prompt of SVG2’s released Wan2.1 script [19]. Appendix § 7.§ 1 lists all prompts.

Baselines. We compare InstaGen against dense attention and three training-free sparse attention methods: the static method SVG [16], which assigns each head a spatial or temporal pattern, and the dynamic methods SVG2 [19], which keeps the $k$-means clusters that reach a top-$p$ attention-mass threshold, and SVG-EAR [23], which approximates skipped blocks with centroids and routes by predicted error. Each baseline uses its official configuration and dense warm-up schedule. We evaluate InstaGen with both uniform and importance samplers to compare against these baselines.

Implementation. We implement InstaGen with a fused attention kernel derived from FlashAttention-3 and benchmark on an NVIDIA H100 80GB SXM GPU. All methods use 50 UniPC steps with flow

shift 5.0 and guidance scale 5.0. We set $C_q = 300$ and $C_k = 1000$, running 50 $k$-means iterations at a layer’s first call and two warm-started iterations thereafter [19]. Each query group attends exactly to the top-scoring key blocks within $E\%$ of the keys and estimates the remainder from $S\%$ of the keys, sampled in proportion to their estimated attention mass (§ 3.2.1); we denote this $E+S$. Both terms are computed in one pass, with importance weights applied as a logit bias. Because InstaGen estimates the omitted attention rather than discarding it, it does not require the dense warm-up used by prior methods. We report it both with and without warm-up, with the first 30% of steps and 3% of layers dense, as in SVG2.

Quality and efficiency evaluation

Attention approximation. We first experiment on one self-attention call captured from a Wan2.1-T2V-1.3B generation. Figure 4(left) shows the mean relative error across all heads in one layer for different methods. Importance sampling has the lowest error at every density: at about 24% of attention computed, its relative $L_2$ error is 0.013, against 0.066 for SVG2 and 0.022 for SVG-EAR, and at about 48% it is 0.004, against 0.033 and 0.014. SVG is a static method, so the error comes via incorrect assumption of attention maps in different attention heads, while the error in other methods is the residual approximation of unselected keys. SVG2 fully drops them, so the error is larger; SVG-EAR and InstaGen both apply different approximation techniques, which lead to relatively lower errors. Figure 4(right) shows the error map across all the layers and heads for the whole generation. Averaged over all steps, InstaGen (uniform, 16+16, no warmup) keeps every head and layer at low error at 32% density, while SVG2 ($p=0.9$) leaves large errors in individual heads and layers despite computing 46% even with warmup steps.

Video quality. Table 1 reports quality and efficiency across the two models. Both InstaGen variants share the exact set and budget and differ only in how the sample is drawn: uniform draws the shared sample uniformly without replacement, while importance draws in proportion to the scores from the cluster centroids following PPSWOR. On both models, InstaGen (importance, 8+8 with warm-up) improves PSNR over SVG2 by 1.6 dB at 1.3B and 2.2 dB at 14B while using lower density and running faster. On the 14B model it is the best sparse method on all three fidelity metrics, ahead of SVG-EAR at nearly the same density. Without any warm-up, InstaGen still outperforms SVG and SVG2 on the 1.3B model, even though both run with warm-up. Importance sampling improves on uniform sampling at every configuration: drawing residual keys in proportion to their attention weight lowers the estimator’s variance at the same budget.

We compare algorithms at similar density to get a fair comparison of attention approximation of every method. We fix the overall density at that of SVG2’s paper configuration ($p=0.9$) and give InstaGen (importance) the same budget and warmup, split equally between exact and sampled keys. On Wan2.1-T2V-1.3B (44.1%), InstaGen raises PSNR from 25.03 to 28.42 dB and SSIM from 0.780 to 0.884, and lowers LPIPS from 0.180 to 0.060; on Wan2.1-T2V-14B (54.0%), from 23.40 to 25.41 dB, 0.805 to 0.886, and 0.152 to 0.073. Figure 2(right) shows the curve for quality, where InstaGen envelops SVG2 with both uniform and importance sampling.

Latency. Figure 2 (left) plots quality against generation time on Wan2.1-T2V-1.3B. With importance sampling and no warmup, InstaGen (16+16) reaches 27.72 dB in 173.1 s, 1.6 dB above SVG2’s best setting ($p=0.95$, 26.11 dB in 177.0 s); with warmup, InstaGen (8+8) reaches 27.69 dB in 164.6 s, 1.6 dB higher than SVG2’s best in 12.4 s less time. Figure 6(a) shows the density required to match the quality of SVG2, and at that matched quality Figure 6(b) shows the advantage of InstaGen on longer frames, where it gets higher speedups than SVG2.

Warmup. Sparse video methods keep their initial steps dense because early errors steer the whole trajectory. SVG2 runs its first 30% of steps at full attention; SVG and SVG-EAR use similar schedules. Without any warmup, Figure 2 shows that InstaGen with importance sampling lies above SVG2’s entire frontier, and on Wan2.1-T2V-14B (Figure 5) it needs a short warmup, but 10 steps put it above SVG2 at every density. Removing the warmup matters more as videos get longer, because a dense step grows almost quadratically with length (4.6 s at 81 frames, 187.6 s at 561). In Figure 6(b), InstaGen without warmup (14+14) is slower than with warmup (4+4) at 81 frames (164.2 vs. 153.2 s), level at 241 (778.0 vs. 779.5 s) and faster beyond, taking 57.3 against 61.9 min at 561 frames.

Conclusion

This paper proposes InstaGen, which replaces the top-$p$ block selection of permuted block-sparse attention with a sampling-based estimate of the full attention. At its core, InstaGen computes an exact set of top-scoring keys in full and estimates the contribution of the remaining keys from a weighted sample, which keeps the estimates of the attention sums unbiased. Parameterized by SVG2, it reuses SVG2’s clustering and block scores and replaces its top-$p$ selection. Group-shared sampling makes it fast: each query cluster draws one sample shared by all its queries, so the sampled keys form dense blocks that run with the exact blocks in a single FlashAttention pass.

Across sparse video generation experiments, InstaGen consistently achieves a better quality-efficiency tradeoff than existing methods. On Wan2.1-T2V-1.3B and 14B, InstaGen improves PSNR over SVG2 by 3.4 dB and 2 dB at matched density and by 1.6 dB and 2.2 dB at matched wall-clock time, and on 14B it beats SVG-EAR by 1.1 dB at nearly the same density. On the 1.3B model it needs no dense warmup to outperform SVG2, which matters most for long videos: it denoises a 561-frame video in 57.3 minutes, against 82.8 for SVG2. Because InstaGen treats sparse attention as sampling, other block scorers, such as SVOO’s, can be plugged in. These results demonstrate that importance sampling provides an effective mechanism for allocating a limited attention budget between high-importance tokens and the residual attention mass, and offers a general framework that can be combined with different mechanisms for constructing proxy attention scores.

Supplementary Material

Prompts

Table 2 lists the 22 VBench prompts, two from each of its eleven per-dimension prompt lists, used verbatim for Table 1, Figure 2 and Figure 6(a). The importance-sampling generation times in Figure 2 are measured on the first five (d22-01 to d22-05).

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
d22-03	color	a red car
d22-04	color	a blue bird
d22-05	human action	A person is riding or walking with horse
d22-06	human action	A person is catching or throwing frisbee
d22-07	multiple objects	a cat and a dog
d22-08	multiple objects	an airplane and a train
d22-09	object class	a train
d22-10	object class	a motorcycle
d22-11	overall consistency	Few big purple plums rotating on the turntable. water drops appear on the skin during rotation. isolated on the white background. close-up. macro.
d22-12	overall consistency	Balloon full of water exploding in extreme slow motion.
d22-13	scene	waterfall
d22-14	scene	highway
d22-15	spatial relationship	a skateboard on the top of a surfboard, front view
d22-16	spatial relationship	a traffic light on the left of a fire hydrant, front view
d22-17	subject consistency	a horse running to join a herd of its kind
d22-18	subject consistency	a bear catching a salmon in its powerful jaws
d22-19	temporal flickering	In a still frame, a tranquil pond was fringed by weeping cherry trees, their blossoms drifting lazily onto the glassy surface
d22-20	temporal flickering	A tranquil tableau of a tranquil lakeside cabin nestled among tall pines, its reflection mirrored perfectly in the calm water
d22-21	temporal style	An astronaut flying in space, racking focus
d22-22	temporal style	A panda drinking coffee in a cafe in Paris, zoom out

Figure 6(b), the 81-frame check that sets the InstaGen budgets in it, and Figure 5 use a single prompt, svg2_ex1, the first example prompt of SVG2’s released Wan2.1 script [19]:

warm colors dominate the room, with a focus on the tabby cat sitting contently in the center. the scene captures the fluffy orange tabby cat wearing a tiny virtual reality headset. the setting is a cozy living room, adorned with soft, warm lighting and a modern aesthetic. a plush sofa is visible in the background, along with a few lush potted plants, adding a touch of greenery. the cat’s tail flicks curiously, as if engaging with an unseen virtual environment. its paws swipe at the air, indicating a playful and inquisitive nature, as it delves into the digital realm. the atmosphere is both whimsical and futuristic, highlighting the blend of analog and digital experiences.