PISA: Piecewise Sparse Attention Is Wiser for Efficient Diffusion Transformers Haopeng Li, Shitong Shao, Wenliang Zhong, Zikai Zhou, Lichen Bai, Hui Xiong, Zeke Xie Abstract Diffusion Transformers are fundamental for video and image generation, but their efficiency is bottlenecked by the quadratic complexity of attention. While block sparse attention accelerates computation by attending only critical key-value blocks, it suffers from degradation at high sparsity by discarding context. In this work, we discover that attention scores of non-critical blocks exhibit distributional stability, allowing them to be approximated accurately and efficiently rather than discarded, which is essentially important for sparse attention design. Motivated by this key insight, we propose PISA , a training-free Pi ecewise S parse A ttention that covers the full attention span with sub-quadratic complexity. Unlike the conventional “keep-or-drop” paradigm that directly drop the non-critical block information, PISA introduces a novel “exact-or-approximate” strategy: it maintains exact computation for critical blocks while efficiently approximating the remainder through block-wise Taylor expansion . This design allows PISA to serve as a faithful proxy to full attention, effectively bridging the gap between speed and quality. Experimental results demonstrate that PISA achieves 1.91 × \times and 2.57 × \times speedups on Wan2.1-14B and Hunyuan-Video, respectively, while consistently maintaining the highest quality among sparse attention methods. Notably, even for image generation on FLUX, PISA achieves a 1.2 × \times acceleration without compromising visual quality. Code is available. A calico cat, with a carrot and a pack of tissues placed in front of it, is staring at the camera with a confused look and resting one of its front paws on the carrot, in a realistic painting style. (a) Wan2.1-14B | Dense Attention | Latency: 1468 s (b) Wan2.1-14B | PISA (Ours) | Latency: 687 s (2.14 \times Speedup) | PSNR: 24.69 Dense Attention Ours (r=85%) SpargeAttn (r=80%) Dense Attention Ours (r=85%) SpargeAttn (r=80%) Dense Attention Ours (r=85%) SpargeAttn (r=80%) Latency: 8.32 s Latency: 6.87 s Latency: 7.47 s LPIPS: 0.129 LPIPS: 0.373 PSNR: 22.60 PSNR: 13.32 (c) Text-to-Image generation results on FLUX.1-dev, where r denotes the sparsity ratio. Figure 1 : PISA accelerates diverse generation tasks . Top (a, b) : Wan2.1-14B video generation. PISA achieves 2.14 \times speedup over Dense Attention with no appreciable quality loss. Bottom (c) : FLUX.1-dev text-to-image generation. PISA at higher sparsity ratio r=85% preserves better quality and structure than SpargeAttn ( 47 ) . 1 Introduction Diffusion Transformers (DiTs) ( 26 ) have demonstrated impressive performance and scalability in generating high-fidelity images and videos, leading to their widespread adoption across diverse visual generation tasks ( 2 ; 15 ; 34 ) . However, as the demand for higher resolutions and longer video durations grows, the sequence length of input tokens increases dramatically. Consequently, the quadratic complexity of the self-attention mechanism ( 33 ) becomes a significant bottleneck, resulting in prohibitively low inference efficiency for large-scale DiTs. To address the computational bottleneck, especially in high-resolution image and video generation, recent research has leveraged the inherent sparsity in DiTs to enable sparse attention. Early works ( 50 ; 37 ; 42 ) capitalized on the spatiotemporal redundancy of video diffusion transformers to introduce static, training-free sparse attention patterns. To improve adaptability, other methods ( 47 ; 41 ; 38 ) propose computing sparse patterns dynamically at runtime. Moving beyond training-free approaches, methods such as VSA ( 49 ) and Radial Attention ( 20 ) have explored trainable sparse attention; works like SANA ( 39 ; 4 ) and Linfusion ( 23 ) have adopted linear attention for efficient generation, while methods such as SLA ( 46 ) have made preliminary attempts to combine sparse and linear attention. However, existing methods still face inherent limitations: (1) Hard truncation: Sparse attention directly discards key-value pairs, leading to performance drops at high sparsity and inefficiency on shorter sequences (e.g., 4K tokens). (2) Incompatibility with pre-trained weights: Linear and hybrid attention fundamentally alter the attention distribution of pre-trained models, precluding the direct reuse of weights and necessitating expensive retraining. These limitations underscore the need for a unified mechanism that enhances efficiency without sacrificing quality or requiring retraining . To this end, we propose PISA , a novel training-free sparse attention that accelerates DiTs while maintaining high accuracy through piecewise computation. Unlike standard sparse attention, which computes only critical blocks and discards the rest, PISA treats attention as a piecewise process: (1) Exact computation for sparse key-value blocks to preserve critical information; (2) Approximation for the remaining blocks using block-wise Taylor expansion to cover the massive amount of non-critical information. Specifically, we propose a hybrid-order approximation strategy that uses block-wise zero-order expansion and global first-order approximation to efficiently improve accuracy. This enables PISA to significantly enhance approximation fidelity relative to full attention, incurring only negligible computational overhead compared to standard sparse attention, as illustrated in Fig. 2 . These dual computational pathways are fused into the online softmax process via a custom kernel, allowing PISA to achieve a state-of-the-art trade-off efficiency speed and accuracy without any training. Extensive experiments demonstrate the superiority of PISA. It accelerates Wan2.1-14B ( 34 ) and Hunyuan-Video ( 18 ) by 1.91 \times and 2.57 \times , respectively, while preserving state-of-the-art quality. Even for image generation tasks with lower inherent sparsity, PISA outperforms existing methods in both efficiency and quality. Our contributions are summarized as follows: 1. We propose a novel piecewise sparse attention that enables full attention span with sub-quadratic complexity. Through a unified exact-or-approximate execution, it resolves the critical dilemma between accuracy and efficiency. 2. We develop a hybrid-order approximation scheme that boosts accuracy with negligible cost. Additionally, we derive a covariance-aware routing strategy from error analysis, which effectively minimizes approximation divergence. 3. Experiments demonstrate that PISA achieves SOTA quality and efficiency across diverse tasks, setting a new sparse attention paradigm for efficient visual generation. Active Blocks: 20% FLOPs: 20.0% L1 Error: 10.34% Full Attention PISA (Ours) Sparse Attention Active Blocks: 100% FLOPs: 100% L1 Error: 0% Active Blocks: 100% FLOPs: 20.4% L1 Error: 1.36% Figure 2 : Visualization of attention patterns on Wan2.1-1.3B. PISA achieves 100% effective block coverage similar to full attention. This near-lossless approximation with only negligible computational overhead relative to standard sparse attention. 2 Related Work Block Sparse Attention. To address the quadratic complexity of standard attention, sparse attention ( 47 ; 49 ; 37 ; 42 ; 20 ; 35 ) limits computation to a subset of critical key-value blocks via static priors or dynamic routing. However, current methods simply discard the unselected blocks, which inevitably exacerbates output error and degrades performance at a high sparsity ratio. In contrast, PISA guarantees a strictly lower error bound than standard sparse attention by approximating the unselected blocks instead of dropping them, enabling superior performance. Bidirectional Linear Attention. Linear attention ( 17 ) achieves linear complexity by replacing the exponential kernel with feature mappings. In the vision domain, existing bidirectional methods primarily focus on modifying these feature mappings ( 23 ; 25 ; 12 ) , yet their core formulation remains consistent with the canonical framework. Notably, Taylor-based approaches ( 3 ) typically expand around zero for the entire sequence. Although kernel tricks ( 11 ) can yield high-order approximations, they incur severe dimension explosion and fail to preserve the pre-trained attention distribution. Consequently, these methods require computationally expensive retraining. Native Hybrid Attention. Recognizing the limitations of pure sparse or linear approaches, recent works have explored hybrid architectures. Methods like SLA ( 46 ) and NHA ( 8 ) attempt to combine sparse (or sliding window) attention with linear attention. However, these methods rely on an additive strategy that directly sums the outputs of different branches. This formulation disrupts the intrinsic normalization of attention weights. Consequently, they suffer from distribution shifts that prevent the inheritance of pre-trained weights, necessitating expensive fine-tuning. In contrast, PISA applies block-wise Taylor expansion to both the normalization numerator and denominator. By natively mixing exact and approximate terms under a unified softmax framework instead of simply adding outputs, our method preserves the intrinsic distribution and enables superior training-free performance. 3 Methodology 3.1 Preliminaries Given an input sequence \bm{X}\in\mathbb{R}^{L\times d} , where L is the length and d is the feature dimension, the query, key, and value \bm{Q},\bm{K},\bm{V}\in\mathbb{R}^{L\times d} are derived from \bm{X} via learnable linear projections. The output \bm{O}\in\mathbb{R}^{L\times d} of attention is: \bm{O}=\text{Softmax}\left(\frac{\bm{Q}\bm{K}^{\top}}{\sqrt{d}}\right)\bm{V}. (1) FlashAttention ( 5 ) introduces online softmax algorithm that avoids materializing attention scores in high bandwidth memory (HBM), significantly reducing memory access overhead. However, it still has quadratic complexity. To mitigate this, sparse attention restrict computation to a subset of critical key-value blocks, which is formulated as: \bm{O}=\text{Softmax}\left(\frac{\bm{Q}\bm{K}^{\top}}{\sqrt{d}}+\bm{M}\right)\bm{V}. (2) Here, \bm{M}\in\{0,-\infty\}^{L\times L} denotes a mask, where entries of -\infty indicate the corresponding key-value pairs are ignored. Figure 3 : Visualization of pre-softmax attention scores ( \bm{Q}\bm{K}^{\top} ) in Wan2.1-1.3B . The block-wise scores exhibit a symmetric bell-shaped distribution. uncritical blocks ( Left ) cluster in negative regions where the 1st-order Taylor expansion is highly accurate, whereas important blocks ( Right ) diverge. This property remains robust under “Safe-Exp” shift for numerical stability ( Bottom ). However, directly discarding blocks inevitably causes the output to deviate sharply from the original attention distribution. This limitation motivated us to design a fast and accurate sparse attention mechanism capable of accelerating inference in a training-free manner . Key Insights. To identify a superior alternative to the “keep-or-drop” strategy, we analyzed the statistical properties of pre-trained models, yielding two key insights: (1) Pre-softmax scores of uncritical blocks exhibit a symmetric distribution centered around zero or negative values , rendering them highly amenable to approximation via mean-centered Taylor expansion, as illustrated in Fig. 3 . (2) Normalization Consistency. Existing hybrid methods rely on an additive strategy ( \bm{O}_{sparse}+\bm{O}_{linear} ) that violates the intrinsic weighted sum rule. To ensure training-free compatibility, the approximation must be integrated internally into the softmax numerator and denominator. 3.2 Piecewise Sparse Attention Based on these insights, we propose Piecewise Sparse Attention (PISA), which unifies exact sparse computation with block-wise approximation directly within the online softmax. The following subsection outline our framework. Formulation. We partition the query, key, value and output matrices ( \bm{Q},\bm{K},\bm{V},\bm{O} ) into blocks of size B . To streamline notation, we express the query and output vectors using a global index. Let \bm{q}_{t}:=\bm{Q}_{iB+m}\in\mathbb{R}^{1\times d} (where t=iB+m ) denote the query vector at global index t , which is the m -th row vector belongs to the i -th \bm{Q} block. For the key and value sides, we preserve the block-internal structure: let \bm{k}_{j,n} and \bm{v}_{j,n} denote the n -th row vectors of the j -th key and value blocks, respectively (where 1\leq n\leq B ). For an arbitrary query \bm{q}_{t} , we partition the key-value block indices into a sparse selected set \mathcal{S}_{i} (computed exactly) and a long-tail unselected set \mathcal{U}_{i} . Instead of discarding the unselected blocks as in standard sparse attention, we approximate the contribution from each block j\in\mathcal{U}_{i} via First-Order Taylor expansion centered at the block centroid \alpha_{t,j}:=\exp(\bm{q}_{t}\bar{\bm{k}}_{j}^{\top}) , where \bar{\bm{k}}_{j}:=\frac{1}{B}\sum_{n=1}^{B}\bm{k}_{j,n} . The output vector \bm{o}_{t}\in\mathbb{R}^{1\times d} is derived by normalizing the weighted value aggregation (omit scale factor for briefly): \displaystyle\bm{o}_{t}:= \displaystyle\frac{\mathcal{N}_{t}}{\mathcal{D}_{t}},\quad\text{where} \displaystyle\mathcal{D}_{t}:= \displaystyle\underbrace{\sum_{j\in\mathcal{S}_{i}}\sum_{n=1}^{B}\exp({\bm{q}_{t}\bm{k}_{j,n}^{\top}})}_{\text{Exact Sparse Term}}+\underbrace{\sum_{j\in\mathcal{U}_{i}}B\cdot\exp({\bm{q}_{t}\bar{\bm{k}}_{j}^{\top}})}_{\text{Block-wise Approx}}, (3) \displaystyle\mathcal{N}_{t}:= \displaystyle\underbrace{\sum_{j\in\mathcal{S}_{i}}\sum_{n=1}^{B}\exp({\bm{q}_{t}\bm{k}_{j,n}^{\top})}\bm{v}_{j,n}}_{\text{Exact Sparse Term}} (4) \displaystyle+ \displaystyle\underbrace{\sum_{j\in\mathcal{U}_{i}}\exp({\bm{q}_{t}\bar{\bm{k}}_{j}^{\top})}\left(\sum_{n=1}^{B}\bm{v}_{j,n}\right)}_{\text{Block-wise Zeroth-order Approx}} (5) \displaystyle+ \displaystyle\underbrace{\sum_{j\in\mathcal{U}_{i}}\exp(\bm{q}_{t}\bar{\bm{k}}_{j}^{\top})\left(\bm{q}_{t}\sum_{n=1}^{B}(\bm{k}_{j,n}-\bar{\bm{k}}_{j})^{\top}\bm{v}_{j,n}\right)}_{\text{Block-wise First-order Approx}}. (6) Note that the first-order term in the denominator \mathcal{D}_{t} cancels out because \sum_{n=1}^{B}(\bm{k}_{j,n}-\bar{\bm{k}}_{j})^{\top}=0 . Since queries within the same block share identical block masking patterns, they can naturally generalize to the full block via matrix operations. Practical Challenge. The term ( 4 ) corresponds to standard block sparse attention, which can be computed efficiently. Similarly, term ( 5 ) can be efficiently computed via matrix multiplication (GEMM) by grouping pre-computed \bar{\bm{k}}_{j} and \sum_{n=1}^{B}\bm{v}_{j,n} into sub-blocks. However, for term ( 6 ), although it theoretically exhibits linear complexity, its practical implementation is severely bottlenecked by memory access. Computing this first-order term necessitates handling distinct matrices \sum_{n=1}^{B}(\bm{k}_{j,n}-\bar{\bm{k}}_{j})^{\top}\bm{v}_{j,n}\in\mathbb{R}^{d\times d} for each block j\in\mathcal{U}_{i} , weighted by block-specific scalar. Whether these matrices are pre-computed and loaded from HBM or computed on-the-fly in SRAM, the process results in a memory-bound operation with low arithmetic intensity , rendering the theoretical speedup unattainable in practice. Figure 4 : The algorithm pipeline of PISA. Prepare Phase: We pre-compute block-wise mean of the queries and keys ( \overline{Q},\overline{K} ), block-wise sum of value ( \hat{V} ) and the global H in a single pass. A block-wise Top-K selection identifies critical blocks. Fused Attention Kernel: The kernel dynamically switches execution paths: selected blocks (e.g., indices 2, 3) undergo exact computation ( Phase 1 ), while unselected blocks (e.g., indices 1, 4) are approximated using block-wise zeroth-order expansion ( Phase 2 ). In Phase 3 , the H is applied to inject global first-order approximation. This design allows loading the global correction term once, avoiding memory-bound streaming. 3.3 Hybrid Approximation To resolve this conflict between theoretical complexity and hardware efficiency, we propose two solutions. Global First-Order Correction. We propose a hybrid-order approximation in which the first-order term is formulated globally across all unselected blocks, rather than block-wise. This allows all blocks to share a unified scale factor \beta_{t} , thereby eliminating the need for weighted summation. Let \bar{\bm{k}}_{t} denote the global centroid of keys across all blocks in \mathcal{U}_{i} . The term ( 6 ) can be rewritten as: \beta_{t}\bm{q}_{t}\sum_{j\in\mathcal{U}_{i}}\sum_{n=1}^{B}(\bm{k}_{j,n}-\bar{\bm{k}}_{t})^{\top}\bm{v}_{j,n}. (7) Determining the expansion coefficient \beta_{t} presents a critical challenge. While a standard first-order Taylor expansion at the global centroid \bar{\bm{k}}_{t} would suggest \beta_{t}=\exp(\bm{q}_{t}\bar{\bm{k}}_{t}^{\top}) , Jensen’s Inequality indicates that this approach severely underestimates the slope of the global first-order term, rendering the correction ineffective. To address this, we define \beta_{t} using the mean of \exp(\bm{q}_{t}\bar{\bm{k}}_{j}^{\top}) effectively employing an average slope to estimate the magnitude of the first-order correction for all unselected blocks. Let \bm{H}_{j}:=\sum_{n=1}^{B}(\bm{k}_{j,n}-\bar{\bm{k}}_{j})^{\top}\bm{v}_{j,n}\in\mathbb{R}^{d\times d} . The term ( 6 ) can be rewritten as: \frac{1}{|\mathcal{U}_{i}|}\left(\sum_{j\in\mathcal{U}_{i}}\exp(\bm{q}_{t}\bar{\bm{k}}_{j}^{\top})\right)\left(\bm{q}_{t}\sum_{j\in\mathcal{U}_{i}}\bm{H}_{j}\right). (8) Furthermore, by associating the normalization factor 1/|\mathcal{U}_{i}| with the summation of \bm{H}_{j} , we essentially compute the mean of \bm{H}_{j} over the unselected blocks. Observing that the set of unselected blocks \mathcal{U}_{i} typically constitutes the vast majority of the total blocks, we approximate the query-dependent mean over \mathcal{U}_{i} using a query-independent global statistic \bar{\bm{H}}=\frac{1}{N}\sum_{j=1}^{N}\bm{H}_{j} , where N is number of blocks. This global statistic can be precomputed via a single pass. Consequently, we arrive at a computationally efficient formulation: \displaystyle\mathcal{N}_{t}:= \displaystyle\underbrace{\sum_{j\in\mathcal{S}_{i}}\sum_{n=1}^{B}\exp({\bm{q}_{t}\bm{k}_{j,n}^{\top})}\bm{v}_{j,n}}_{\text{Exact Sparse Term}} (9) \displaystyle+ \displaystyle\underbrace{\sum_{j\in\mathcal{U}_{i}}\alpha_{t,j}\left(\sum_{n=1}^{B}\bm{v}_{j,n}\right)}_{\text{Block-wise 0th-order}}+\underbrace{\bm{q}_{t}\bar{\bm{H}}\sum_{j\in\mathcal{U}_{i}}\alpha_{t,j}}_{\text{Global 1st-order}}. (10) Error Analysis. As proved in Theorem 3.1 , the error induced by this replacement is bounded by the product of the tail probability mass and the variance of block matrices. Since \alpha_{t,j} is small in the unselected set, the approximation error remains controlled. Theorem 3.1 (Error Analysis of Global First-Order Approximation) . Following our previous notation. Assume there exists a constant C_{q}>0 , such that the query norm is bounded, i.e., \|\bm{q}_{t}\|_{2}\leq C_{q} . Let \bm{o}_{t}=\frac{\mathcal{N}_{t}}{\mathcal{D}_{t}} be the attention output computed using the exact block-wise first-order approximation and let \tilde{\bm{o}}_{t} be the output computed after replacing \sum_{j\in\mathcal{U}_{i}}\alpha_{t,j}\bm{H}_{j} by (\sum_{j\in\mathcal{U}_{i}}\alpha_{t,j})\bar{\bm{H}} . Define \tau_{t}:=\sum_{j\in\mathcal{U}_{i}}\sum_{n=1}^{B}\exp(\bm{q}_{t}\bm{k}_{j,n}^{\top}) . Let M:=\max_{j\in\mathcal{U}_{i}}\|\bm{H}_{j}-\bar{\bm{H}}\|_{2}. If we denote the tail fraction \rho_{t}:=\tau_{t}/\mathcal{D}_{t}\in(0,1) , then \|\tilde{\bm{o}}_{t}-\bm{o}_{t}\|_{2}\leq C_{q}\;M\;\frac{\rho_{t}}{B}. Proofs and further discussions are provided in Appendix C . Covariance-Aware Block Selection. Practically, to guarantee small approximation error it suffices to ensure either the tail fraction \rho_{t} is small, or the per-block heterogeneity M is small. Based on the Theorem 3.1 , we propose a Covariance-Aware Top-k Strategy that incorporates the norm of the block covariance matrix as a prior for importance routing. Let M_{j}:=\|\bm{H}_{j}-\bar{\bm{H}}\|_{2} , the selection score for block j with respect to query \bm{q}_{t} is defined as: \text{Score}_{t,j}=\text{Softmax}\left(\frac{\bm{q}_{t}\bar{\bm{k}}_{j}^{\top}}{\sqrt{d}}+\log\left(M_{j}+\epsilon\right)\right), (11) where \epsilon>0 is a small constant for numerical stability. The derivation of Eq. ( 11 ) is further elaborated on in the Appendix D . This strategy ensures that blocks with either high semantic relevance are preserved in the exact set \mathcal{S}_{i} , while the smoother blocks are delegated to the Taylor expansion. 3.4 Hardware-aware Kernel Implementation We design a fused kernel which efficiently interleaves exact computation with approximate scanning in online softmax. Algorithm 1 PISA Forward Pass 0: \bm{Q},\bm{K},\bm{V}\in\mathbb{R}^{L\times d} , block size B and C , sparsity r 1: Compute block means \bar{\bm{Q}},\bar{\bm{K}} , block sum \hat{\bm{V}} and global \bm{H} . 2: Compute block indices \mathcal{S}_{i} via Eq. ( 11 ) for each query block i . 3: Partition \bar{\bm{K}},\hat{\bm{V}} into groups \{\bar{\bm{K}}_{[g]},\bar{\bm{V}}_{[g]}\} of size C . 4: for i\leftarrow 1 to N=\lceil L/B\rceil do 5: Init \bm{O}_{i}\leftarrow\mathbf{0} , \bm{\ell}_{i}\leftarrow\mathbf{0} , \bm{\ell}^{\text{tail}}_{i}\leftarrow\mathbf{0} , \bm{m}_{i}\leftarrow-\infty . 6: Load \bm{Q}_{i} into SRAM. 7: for j\in\mathcal{S}_{i} do Phase 1 8: Load \bm{K}_{j} , \bm{V}_{j} into SRAM. 9: On-chip: \bm{S}_{ij}=\bm{Q}_{i}\bm{K}_{j}^{\top} Omit the safe softmax 10: On-chip: \bm{P}_{ij}=\exp(\bm{S}_{ij}) procedure for brevity 11: On-chip: \bm{\ell}_{i}\leftarrow\bm{\ell}_{i}+\operatorname{rowsum}(\bm{P}_{ij}) 12: On-chip: \bm{O}_{i}\leftarrow\bm{O}_{i}+\bm{P}_{ij}\bm{V}_{j} 13: end for 14: for g\leftarrow 1 to \lceil N/C\rceil do Phase 2 15: Load \bar{\bm{K}}_{[g]} , \bar{\bm{V}}_{[g]} into SRAM. 16: On-chip: \bm{S}_{ig}=\bm{Q}_{i}\bar{\bm{K}}_{[g]}^{\top} 17: On-chip: \bm{S}_{ig}[\{j\mid j\in\mathcal{S}_{i}\}]\leftarrow-\infty . Column masking 18: On-chip: \bm{P}_{ig}=\exp(\bm{S}_{ig}) Omit the safe softmax 19: On-chip: \bm{\ell}_{i}\leftarrow\bm{\ell}_{i}+\operatorname{rowsum}(\bm{P}_{ig}) 20: On-chip: \bm{\ell}^{\text{tail}}_{i}\leftarrow\bm{\ell}^{\text{tail}}_{i}+\operatorname{rowsum}(\bm{P}_{ig}) . 21: \bm{O}_{i}\leftarrow\bm{O}_{i}+\bm{P}_{ig}\bar{\bm{V}}_{[g]} 22: end for 23: On-chip: \bm{R}_{i}=\text{diag}(\bm{\ell}^{\text{tail}}_{i})(\bm{Q}_{i}\bm{H})\cdot L^{-1} Phase 3 24: On-chip: \bm{O}_{i}\leftarrow\operatorname{diag}(\bm{\ell}_{i}^{-1})(\bm{O}_{i}+\bm{R}_{i}) 25: end for 25: \bm{O}=\{\bm{O}_{i}\}_{i=1}^{M}\in\mathbb{R}^{L\times d} . We illustrate the pipeline in Fig. 4 and present the pseudocode in Algorithm 1 . In Prepare Phase , we pre-computes block centroids and the global statistic \bar{\bm{H}} while selecting critical blocks \mathcal{S}_{i} . In Phase 1 , we load the selected blocks j\in\mathcal{S}_{i} into SRAM to perform exact attention. Then in Phase 2 , we scan aggregated block vectors in groups using coalesced memory access. A dynamic mask excludes selected blocks, enabling high-throughput for the tail mass. Finally, we inject the global approximation in Phase 3 . This operation incurs negligible cost yet effectively recovers first-order gradient information. (a) Latency Analysis (b) Speedup Analysis Figure 5 : Kernel efficiency profile. ( a ) Latency comparison across sequence lengths at 12.5% density (87.5% sparsity) under two mainstream configurations with notation B-H-D ( batch_size , num_heads , head_dim ). ( b ) Relative speedup against FlashAttn-2/3 across varying densities and sequence lengths under the B2-H16-D128 configuration. The dashed line indicates the baseline performance. 4 Experiments 4.1 Experimental Setup Models. We evaluate PISA on both video and image generation tasks. For video generation, we employ Wan2.1 (1.3B/14B) ( 34 ) to produce videos at 480p and 720p resolutions, respectively. For image generation, we utilize SD 3.5 ( 9 ) and FLUX.1 ( 19 ) to generate images at a resolution of 1024 \times 1024. Benchmarks. We employ VBench ( 16 ) to evaluate both video quality and temporal consistency. For image generation, we utilize FID ( 14 ) alongside a suite of human preference metrics, including ImageReward (IR) ( 40 ) , HPSv2 ( 36 ) , and MPS ( 52 ) . Furthermore, we compute SSIM, PSNR and LPIPS ( 51 ) to quantify the similarity between our method and full attention. Regarding efficiency, we note that theoretical FLOPs often fail to reflect real-world speeds. Therefore, to ensure a fair comparison of efficiency, we focus exclusively on end-to-end latency and the speedup ratio relative to full attention. Implementation Details. We define sparsity as the proportion of blocks computed using approximation, analogous to the ratio of skipped blocks in standard sparse attention. Our kernel implementation uses a block size of 64 \times 64. We only employ the Covariance-Aware Block Selection to boost performance for image generation. Following prior works ( 20 ; 42 ) , we adopt a warmup strategy where early layers and inference steps retain dense. Detailed configurations are provided in the Appendix E . 4.2 Kernel Efficiency Evaluation To evaluate the efficiency of our method, we benchmark against state-of-the-art implementations. Specifically, we adopt FlashAttn-2/3 (FA) ( 6 ; 28 ) as the standard for exact full attention, and SpargeAttn ( 47 ) as the baseline for block sparse attention. All efficiency results were profiled on NVIDIA H800 GPUs. Efficiency vs. Sequence Length. As illustrated in Fig. 5(a) , PISA at a density of 12.5% (sparsity 87.5%) consistently outperforms FA3 and SpargeAttn. Notably, even at shorter sequence (e.g., 4K), our method maintains a speed advantage over FA3, whereas SpargeAttn exhibits performance degradation in this regime, becoming slower than FA3. Efficiency vs. Density. Fig. 5(b) illustrates the speedup of PISA relative to FA2 and FA3 across varying densities and sequence lengths. Notably, even when the density exceeds 70% (less than 30% sparsity), our method consistently outperforms FA2 across all sequence lengths. Regarding FA3, our method surpasses it on longer sequences ( > 8K) when the density is below 50%, whereas for shorter sequences (4K), it outperforms FA3 provided the density is below 70%. Runtime Breakdown. We profile the runtime of distinct phases within our kernel. As illustrated in Fig. 6 , the approximation phase incurs minimal overhead, confirming that our method improves accuracy without sacrificing efficiency. Figure 6 : Latency breakdown of PISA. We profile the cumulative runtime of the four kernel phases: (1) block reduction, (2) block selection, (3) exact attention, (4) approximate attention (comprises block-wise zeroth-order and global first-order approximation). Dense Attention Dense Attention PISA (Ours) PISA (Ours) SVG2 SpargeAttn Figure 7 : Video generation samples of different attention mechanisms. Left : Hunyuan-Video 13B. Right : Wan2.1-14B. Table 1: Comparison of different sparse attention on video generation with warmup strategy. \dagger : The sparsity is derived from the actual statistical data of all samples, using the official-provided configuration for reproducing the 87.13% sparsity reported in SVG2 paper. Model Method Sparsity Vbench (\%)\uparrow Similarity Efficiency S.C. I.Q. A.Q. SSIM \uparrow PSNR \uparrow LPIPS \downarrow Latency \downarrow Speedup \uparrow Wan2.1-1.3B Text-to-Video 480P Dense 0.00% 94.96 66.09 60.79 – – – 98 s 1.00 \times Sparge 87.5% 93.76 64.89 58.66 0.761 20.75 0.138 51 s 1.92 \times SVG2 † 84.4% 93.79 64.51 59.09 0.809 22.85 0.104 62 s 1.58 \times Ours 87.5% 94.58 65.94 60.03 0.800 22.62 0.111 48 s 2.04 \times Wan2.1-14B Text-to-Video 720P Dense 0.00% 95.98 67.71 63.08 – – – 1564 s 1.00 \times Sparge 87.5% 95.69 67.11 62.72 0.766 21.47 0.144 844 s 1.85 \times SVG2 † 80.6% 95.39 66.97 61.92 0.796 22.92 0.121 882 s 1.77 \times Ours 87.5% 95.80 67.88 63.38 0.787 22.69 0.124 818 s 1.91 \times Hunyuan-13B Text-to-Video 720P Dense 0.00% 95.60 67.65 61.55 – – – 1651 s 1.00 \times Sparge 87.5% 95.38 67.37 61.35 0.837 24.85 0.107 658 s 2.51 \times SVG2 † 81.4% 94.88 63.10 58.58 0.848 26.40 0.109 649 s 2.54 \times Ours 87.5% 95.47 68.16 61.85 0.840 26.17 0.106 641 s 2.57 \times 4.3 Visual Generation Evaluation Video Generation. We evaluate our PISA against recent sparse attention works (e.g., SpargeAttn ( 47 ) , SVG2 ( 42 ) ) on the Wan2.1 ( 34 ) and Hunyuan-Video ( 18 ) . Table 2 : Comparison of different sparse attention on video generation without warmup strategy. \dagger : Same clarification as in Table 1 . Method Sparsity VBench(%) \uparrow Similarity Speedup \uparrow I.Q. A.Q. PSNR \uparrow LPIPS \downarrow Wan2.1-1.3B (Text-to-Video 480P) Sparge 87.5% 60.10 55.26 10.92 0.397 2.72 \times SVG2 † 75.8% 63.22 57.25 13.42 0.292 2.33 \times Ours 87.5% 66.08 60.32 14.16 0.267 3.06 \times Wan2.1-14B (Text-to-Video 720P) Sparge 87.5% 60.03 51.45 9.48 0.520 2.59 \times SVG2 † 74.7% 58.85 55.72 10.67 0.489 2.37 \times Ours 87.5% 69.95 64.47 12.04 0.398 2.75 \times Hunyuan-13B (Text-to-Video 720P) Sparge 87.5% 65.10 60.34 14.91 0.283 3.65 \times SVG2 † 81.0% 63.96 60.34 16.20 0.275 3.60 \times Ours 87.6% 67.61 61.65 18.73 0.264 3.82 \times Table 3: Comparison of different sparse attention on text-to-image generation with warmup strategy. Model Method Sparsity FID \downarrow IR \uparrow MPS \uparrow HPSv2 \uparrow SSIM \uparrow PSNR \uparrow LPIPS \downarrow Latency \downarrow SD 3.5-M Dense-Attn 0% 15.48 0.912 – 30.13 – – – 3.03 s SpargeAttn 70% 19.52 0.465 32.32% 26.30 0.627 14.60 0.269 2.69 s Ours 70% 14.78 0.883 49.71% 30.40 0.790 19.55 0.158 2.15 s SD 3.5-L Turbo Dense-Attn 0% 17.70 0.877 – 30.75 – – – 0.81 s SpargeAttn 80% 22.27 0.235 26.03% 27.15 0.558 13.88 0.281 0.71 s Ours 85% 17.56 0.782 43.35% 29.84 0.677 16.64 0.201 0.65 s FLUX.1 schnell Dense-Attn 0% 15.21 0.911 – 30.22 – – – 0.82 s SpargeAttn 80% 15.74 0.728 38.69% 28.81 0.563 13.62 0.311 0.75 s Ours 85% 15.25 0.887 45.73% 29.90 0.625 15.17 0.247 0.71 s FLUX.1 dev Dense-Attn 0% 16.35 0.965 – 31.31 – – – 8.32 s SpargeAttn 80% 19.20 0.906 48.13% 31.31 0.539 12.88 0.296 7.47 s Ours 85% 15.91 1.001 51.98% 31.69 0.682 17.07 0.241 6.87 s As demonstrated in Table 1 , our method achieves state-of-the-art performance on the VBench benchmark, significantly outperforming existing approaches while delivering substantial speedup advantages. Remarkably, it even surpasses full attention on certain generation quality metrics. In contrast, although SVG2 achieves high similarity scores, it suffers from severe degradation in overall video quality and consistency, exhibiting noticeable blurring and flickering between frames. Similarly, SpargeAttn struggles with the loss of fine-grained details, whereas PISA exhibits visual quality consistent with full attention, as shown in Fig. 7 . Furthermore, unlike competing methods that deteriorate precipitously without a warmup strategy, PISA maintains high-fidelity generation, as detailed in Table 2 . This underscores the critical advantage of our efficient piecewise computation covering the full attention span. Image Generation. We compare our method against SparseAttn on Stable Diffusion 3.5 (SD3.5) ( 9 ) and FLUX.1 ( 19 ) , with results shown in Table 3 . At similar or higher sparsity levels, our method significantly outperforms SparseAttn in FID and other human preference benchmarks, while achieving greater speedups. In terms of similarity, our method consistently surpasses SparseAttn across different models, demonstrating that our piecewise attention mechanism preserves critical structural and semantic information. Notably, on FLUX.1-dev, our method even outperforms full attention on certain metrics. Visual results are presented in Fig. 1 and Appendix F . Figure 8 : Relative error with respect to dense attention. Left : varying density (32K tokens). Right : varying length (20% density). Table 4 : Ablation of hybrid approximation. The suffixes “-0th” , “-1st” , and “-hyd” denote block-wise 0th/1st-order, and hybrid approximations, respectively. \dagger : With covariance-aware selection. Model Method SSIM \uparrow PSNR \uparrow LPIPS \downarrow Speedup \uparrow PISA- 0th 0.643 16.10 0.274 1.21 \times PISA- 1st 0.679 17.04 0.246 0.96 \times PISA- hyd 0.677 17.01 0.248 1.24 \times FLUX.1-dev PISA- hyd † 0.682 17.09 0.241 1.22 \times PISA- 0th 0.772 21.68 0.136 1.93 \times Wan2.1-14B PISA- hyd 0.787 22.69 0.124 1.91 \times Dense PISA PISA (Zeroth Only) A portrait of a human growing colorful flowers from her hair. Hyperrealistic oil painting. Intricate details. An old car is sitting by the street in front of the sign 2026, in the style of futuristic, scifi elements, dark themes. Figure 9 : Qualitative ablation of the approximation strategy . 4.4 Ablation Study Quantitative Validation. We examine the normalized L_{1} error ratio of attention on Wan2.1-13B. As shown in Fig. 8 , the zeroth-order variant of PISA ( Sparse + Block-0th Approx ) consistently achieves lower errors than standard sparse attention, while the hybrid-order variant ( Sparse + Hybrid Approx ) yields further improvements. This validates the numerical precision of our method, confirming its ability to minimize output error. Beyond output error of attention, we evaluate generation similarity against the exact block-wise first-order baseline. As shown in Table 4 , our hybrid approximation significantly improves similarity over the zeroth-order method and approaches the exact baseline with superior efficiency. These results quantitatively demonstrate an optimal trade-off between generation fidelity and computational cost. Qualitative Validation. We visualized the effects on the FLUX.1-dev ( 85% sparsity) in Fig. 9 . While the zeroth-order approximation maintains semantics and structural integrity, it struggles with local details. In contrast, the hybrid approximation significantly recovers these fine-grained details. This provides intuitive visual evidence that our hybrid strategy effectively preserves human-perceptible details. 5 Conclusion In this work, we transcend the conventional “keep-or-drop” paradigm of sparse attention. We propose a novel Piecewise Sparse Attention that, through a unified “exact-or-approximate” execution, enables full attention span with sub-quadratic complexity, achieving an optimal trade-off between efficiency and accuracy. Impact Statement This paper presents work whose goal is to advance the field of Attention Mechanism. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here. Appendix A Expanded Related Work Sparse Attention for DiTs. Sparse attention reduces computational complexity by selectively computing only critical key-value pairs. In the field of video generation, static sparse attention ( 37 ; 50 ) relies on attention masks derived from intrinsic spatio-temporal sparsity priors, whereas dynamic sparse attention ( 42 ; 38 ; 47 ; 32 ; 22 ; 30 ; 55 ) determines which key-values to prune during runtime. To maximize hardware utilization, sparse attention typically operates at a block-level granularity where a block of queries attends to a shared set of key-value blocks. Although some methods in Large Language Models (LLMs) have achieved finer granularity by allowing token-wise queries to attend to block-wise key-values ( 24 ; 45 ) , they utilize the inherent properties of causal attention. For instance, NSA ( 45 ) leverages Grouped Query Attention (GQA) ( 1 ) to construct GEMM via the attention head dimension. Consequently, these techniques are difficult to implement in bidirectional attention. Bidirectional Linear Attention. Linear attention reduces computational complexity to a linear scale by decomposing \exp(\bm{q}\bm{k}^{\top}) into \phi(\bm{q})\phi(\bm{k})^{\top} and leveraging the associative property of matrix multiplication to compute the \bm{k}^{\top}\bm{v} product first. Initially, to mimic the normalization scheme of softmax attention, the kernel function \phi(\cdot) was typically restricted to element-wise non-negative activation functions (e.g., ReLU or \text{ELU}(\cdot)+1 ) to ensure normalization validity. However, Recent works ( 27 ; 31 ) demonstrated that the normalization denominator is unnecessary and can be replaced by post-normalization of the output. Consequently, the non-negativity constraint on the kernel function is no longer required, allowing for functions like SiLU, a practice now widely adopted in recent LLMs with causal linear attention ( 43 ; 54 ; 44 ) . Despite these advancements, existing variants of bidirectional linear attention continue to adhere to non-negative kernel functions to preserve the form of softmax normalization ( 12 ; 23 ; 39 ; 25 ; 13 ; 10 ) . Linear Attention with Taylor Expansion. In the field of LLMs, several studies ( 3 ; 11 ; 48 ) utilize Taylor expansion to linearize softmax attention. Recent approaches, such as Based ( 3 ) and power attention ( 48 ) , have adopted a second-order Taylor expansion using the feature map \phi_{p}(q)\phi_{p}(k)=(q^{\top}k)^{p} (note that this is an exact equivalence) to efficiently compute second-order terms. However, \phi_{p} significantly increases the head dimension of q and k . For instance, with a base head dimension of 64, Based requires an expansion from 64\to 4096 . Although power attention propose a symmetric powers map to mitigate this dimensional growth (e.g., reducing the expansion to 64\to 2080 ), the computational cost remains high due to its \mathcal{O}(Nd^{2}) complexity. This overhead is considered tolerable in causal attention because inference is performed via token-wise decoding. Furthermore, since these methods expand the function around 0 for the entire sequence, they necessitate training from scratch. Hybrid Attention. Recent works ( 21 ; 53 ) have explored hybridizing softmax and linear attention either across or within layers. Common strategies involve computing the full sequence with both attention types independently and performing a weighted sum of their outputs, or allocating specific attention heads to each mechanism followed by concatenation and linear projection. Recently, efforts have shifted toward hybridization at a finer granularity. For instance, in LLMs, NHA ( 8 ) combines linear attention with sliding window attention, where tokens lying outside the window are processed via the linear branch. Similarly, in the vision domain, SLA ( 46 ) integrates sparse and linear attention by dynamically selecting a subset of key-value pairs for linear computation. However, these methods typically aggregate the two branches via direct summation. This approach inevitably destroys the inherent normalized property of softmax attention, thereby precluding the training-free integration of pre-trained weights. Appendix B Compare with Other Methods In contrast to recent studies, our approach distinguishes itself from existing paradigms in three key aspects. First, unlike pure sparse attention ( 41 ; 37 ; 42 ; 47 ; 29 ) which adheres to a “keep-or-drop” paradigm that discards the majority of key-value pairs, our method adopts an “exact-or-approximate” paradigm, blending sparse exact computation with efficient approximation. Second, in contrast to hybrid attention mechanisms ( 8 ; 46 ) that typically perform a naive summation of softmax and linear attention outputs, we propose a fine-grained and mathematically rigorous mixing strategy. By employing block-wise Taylor expansion to approximate both the numerator and denominator, we unify the hybridization of softmax and linear attention within the canonical normalization framework of attention. Third, compared to other Taylor-based methods ( 3 ; 11 ; 7 ) that perform global expansion over the entire sequence, resulting in prohibitive approximation errors that prevent the reuse of pre-trained weights, our method performs expansion around the local mean of each block. This significantly reduces approximation error, enabling the direct, training-free inheritance of pre-trained weights using only a first-order expansion. To the best of our knowledge, we are the first to natively integrate block-wise Taylor expansion and sparse attention into a unified framework. Appendix C Error Analysis of the Hybrid-Order Approximation Notation. Let the input length be L , block size B , number of blocks N=L/B . For a fixed query row \bm{q}_{t}\in\mathbb{R}^{1\times d} (with t=iB+m ), denote the block-wise key/value rows by \{\bm{k}_{j,n}\}_{j=1,\dots,N}^{n=1,\dots,B} and \{\bm{v}_{j,n}\} . Define the block centroid \bar{\bm{k}}_{j}:=\frac{1}{B}\sum_{n=1}^{B}\bm{k}_{j,n}, and the block-wise first-order matrix \bm{H}_{j}:=\sum_{n=1}^{B}(\bm{k}_{j,n}-\bar{\bm{k}}_{j})^{\top}\bm{v}_{j,n}\in\mathbb{R}^{d\times d}. The global first-order statistic is \bar{\bm{H}}:=\frac{1}{N}\sum_{j=1}^{N}\bm{H}_{j}. For brevity define the block-centroid exponentials (including the scaling \sqrt{d} ) \alpha_{t,j}:=\exp\!\Big(\frac{\bm{q}_{t}\bar{\bm{k}}_{j}^{\top}}{\sqrt{d}}\Big). Let \mathcal{S}_{i} be the set of selected (exact) blocks for query-block i , and \mathcal{U}_{i} its complement (the unselected / tail blocks). Define the full attention denominator \mathcal{D}_{t}:=\sum_{j=1}^{N}\sum_{n=1}^{B}\exp\!\Big(\frac{\bm{q}_{t}\bm{k}_{j,n}^{\top}}{\sqrt{d}}\Big), and the tail (unselected) mass \tau_{t}:=\sum_{j\in\mathcal{U}_{i}}\sum_{n=1}^{B}\exp\!\Big(\frac{\bm{q}_{t}\bm{k}_{j,n}^{\top}}{\sqrt{d}}\Big). Finally denote the operator (spectral) norm by \|\cdot\|_{2} and the Euclidean norm for vectors also by \|\cdot\|_{2} . The core approximation step of our Hybrid-Order Approximation replaces the exact first-order contribution \sum_{j\in\mathcal{U}_{i}}\alpha_{t,j}\,\bm{H}_{j}\quad\text{by}\quad\Big(\sum_{j\in\mathcal{U}_{i}}\alpha_{t,j}\Big)\bar{\bm{H}}. Define the residual matrix \bm{R}_{t}:=\sum_{j\in\mathcal{U}_{i}}\alpha_{t,j}(\bm{H}_{j}-\bar{\bm{H}}). Lemma C.1 (Residual operator norm bound) . Let M:=\max_{j\in\mathcal{U}_{i}}\|\bm{H}_{j}-\bar{\bm{H}}\|_{2}. Then \|\bm{R}_{t}\|_{2}\leq M\cdot\sum_{j\in\mathcal{U}_{i}}\alpha_{t,j}. Proof. By triangle inequality and submultiplicativity of the operator norm, \|\bm{R}_{t}\|_{2}=\Big\|\sum_{j\in\mathcal{U}_{i}}\alpha_{t,j}(\bm{H}_{j}-\bar{\bm{H}})\Big\|_{2}\leq\sum_{j\in\mathcal{U}_{i}}\alpha_{t,j}\|\bm{H}_{j}-\bar{\bm{H}}\|_{2}\leq M\sum_{j\in\mathcal{U}_{i}}\alpha_{t,j}, which proves the lemma. ∎ We restate Theorem 3.1 for completeness as follows: Theorem C.2 (Error Analysis of Global First-Order Approximation) . Assume there exists a constant C_{q}>0 , such that the query norm is bounded, i.e., \|\bm{q}_{t}\|_{2}\leq C_{q} . Let \bm{o}_{t} be the (vector) attention output computed using the exact first-order term \bm{o}_{t}=\frac{\mathcal{N}_{t}}{\mathcal{D}_{t}}, and let \tilde{\bm{o}}_{t} be the output computed after replacing \sum_{j\in\mathcal{U}_{i}}\alpha_{t,j}\bm{H}_{j} by (\sum_{j\in\mathcal{U}_{i}}\alpha_{t,j})\bar{\bm{H}} (while keeping the same denominator \mathcal{D}_{t} ). Then \|\tilde{\bm{o}}_{t}-\bm{o}_{t}\|_{2}\leq\frac{\|\bm{q}_{t}\|_{2}\;\|\bm{R}_{t}\|_{2}}{\mathcal{D}_{t}}\leq\frac{C_{q}\;M}{\mathcal{D}_{t}}\sum_{j\in\mathcal{U}_{i}}\alpha_{t,j}. (12) Moreover, by Jensen’s inequality for the convex exponential function (applied block-wise), \sum_{j\in\mathcal{U}_{i}}\alpha_{t,j}\leq\frac{\tau_{t}}{B}, (13) and consequently \|\tilde{\bm{o}}_{t}-\bm{o}_{t}\|_{2}\leq C_{q}\;M\;\frac{\tau_{t}}{B\,\mathcal{D}_{t}}. Equivalently, if we denote the tail fraction \rho_{t}:=\tau_{t}/\mathcal{D}_{t}\in[0,1] , then \|\tilde{\bm{o}}_{t}-\bm{o}_{t}\|_{2}\leq C_{q}\;M\;\frac{\rho_{t}}{B}. Proof. Write the exact numerator as \mathcal{N}_{t}=\mathcal{N}_{t}^{(\mathcal{S})}+\mathcal{N}_{t}^{(0)}+\mathcal{N}_{t}^{(1)} , where \mathcal{N}_{t}^{(\mathcal{S})} is the selected (exact) contribution, \mathcal{N}_{t}^{(0)} denotes the block-wise zeroth-order term (the grouped value sums multiplied by centroid exponentials), and \mathcal{N}_{t}^{(1)}=\bm{q}_{t}\sum_{j\in\mathcal{U}_{i}}\alpha_{t,j}\bm{H}_{j} is the exact first-order contribution from the unselected blocks. The approximated numerator replaces \mathcal{N}_{t}^{(1)} by \tilde{\mathcal{N}}_{t}^{(1)}=\bm{q}_{t}\Big(\sum_{j\in\mathcal{U}_{i}}\alpha_{t,j}\Big)\bar{\bm{H}}. Therefore the numerator error induced by this replacement is \Delta\mathcal{N}_{t}:=\tilde{\mathcal{N}}_{t}^{(1)}-\mathcal{N}_{t}^{(1)}=\bm{q}_{t}\underbrace{\Big(\sum_{j\in\mathcal{U}_{i}}\alpha_{t,j}\bar{\bm{H}}-\sum_{j\in\mathcal{U}_{i}}\alpha_{t,j}\bm{H}_{j}\Big)}_{-\bm{R}_{t}}=-\bm{q}_{t}\bm{R}_{t}. Since both outputs share the same denominator \mathcal{D}_{t} by assumption, we have \tilde{\bm{o}}_{t}-\bm{o}_{t}=\frac{\Delta\mathcal{N}_{t}}{\mathcal{D}_{t}}=-\frac{\bm{q}_{t}\bm{R}_{t}}{\mathcal{D}_{t}}. Taking Euclidean norm and using submultiplicativity of operator norm, \|\tilde{\bm{o}}_{t}-\bm{o}_{t}\|_{2}\leq\frac{\|\bm{q}_{t}\|_{2}\;\|\bm{R}_{t}\|_{2}}{\mathcal{D}_{t}}. Applying Lemma C.1 yields the first inequality in ( 12 ). To obtain ( 13 ), note that for any block j , \alpha_{t,j}=\exp\!\Big(\frac{\bm{q}_{t}\bar{\bm{k}}_{j}^{\top}}{\sqrt{d}}\Big)=\exp\!\Big(\frac{1}{B}\sum_{n=1}^{B}\frac{\bm{q}_{t}\bm{k}_{j,n}^{\top}}{\sqrt{d}}\Big)\leq\frac{1}{B}\sum_{n=1}^{B}\exp\!\Big(\frac{\bm{q}_{t}\bm{k}_{j,n}^{\top}}{\sqrt{d}}\Big), where the inequality follows from Jensen’s inequality since \exp(\cdot) is convex. Summing over j\in\mathcal{U}_{i} gives ( 13 ). Combining yields the stated bounds and completes the proof. ∎ Remarks. 1. The assumption that the query norm is bounded is mild and justifiable, as modern models predominantly employ QK-Norm (Query-Key Normalization) in their attention layers. 2. The bound in Theorem C.2 cleanly separates (i) a structural heterogeneity term M=\max_{j}\|\bm{H}_{j}-\bar{\bm{H}}\|_{2} , which measures how similar each block’s first-order contribution is to the global statistic, and (ii) a tail mass factor \rho_{t}=\tau_{t}/\mathcal{D}_{t} , which measures how much attention weight remains in the unselected (approximated) blocks. The block size B appears in the denominator because a single block-centroid exponential \alpha_{t,j} is at most the average of the B per-row exponentials (Jensen), hence \sum_{j}\alpha_{t,j}\leq\tau_{t}/B . 3. Theorem C.2 bounds only the error caused by replacing the exact per-block matrices by their global mean. Additional error terms originate from the the truncation of the Taylor series. According to the Lagrange remainder form of Taylor’s theorem, this error is bounded by the second-order moment of the block deviations. Since PISA operates on unselected blocks where the attention distribution is sparse and flat (it is precisely this insight that motivates our work), this quadratic residual is negligible compared to the first-order term. Therefore, Theorem C.2 effectively captures the dominant error bound of our method. Appendix D Covariance-Aware Block Selection Recalling the theoretical error bound in Theorem C.2 that \text{error}\propto\exp(\bm{q}\bm{k}^{\top})\cdot\|\bm{H}\|_{2} , our goal is to identify blocks with both large attention scores and high approximation errors. We simplify this objective by rectifying the attention score using M_{j}:=\|\bm{H}_{j}-\bar{\bm{H}}\| . To eliminate the influence of the absolute magnitude of M_{j} , we define the block-wise routing factor as \exp(\bm{q}_{t}\bar{\bm{k}}_{j}^{\top})\cdot{M_{j}}/{\bar{M}} , where \bar{M} is the mean of M_{j\in\mathcal{U}} . To integrate this into the softmax operation, we take its logarithm: \text{Score}_{t,j}=\text{Softmax}\left(\frac{\bm{q}_{t}\bar{\bm{k}}_{j}^{\top}}{\sqrt{d}}+\log(M_{j})-\log(\bar{M})\right). (14) Since \bar{M} is a constant term, it cancels out during the Softmax normalization, thereby yielding Eq. ( 11 ). Appendix E Implementation Details for Reproducibility We detail the specific configuration of the warmup strategy in Table 6 and Table 6 . Beyond this, to ensure a strictly fair comparison, all other parameters regarding sparse attention adhere to the official implementations. When integrating different attention methods into video and image generation models, we utilize the official recommended configurations for all remaining hyperparameters (e.g., sampling steps, classifier-free guidance (CFG) scale), without further enumeration. Table 5 : Configuration of Video Generation Ref. Config Wan2.1 Wan2.1 Hunyuan 1.3B 14B 13B Table 1 Dense Layer 1 1 1 Dense Step 15 10 10 Table 2 Dense Layer 0 0 0 Dense Step 0 0 0 Table 6 : Configuration of Image Generation Ref. Config SD 3.5 SD 3.5 FLUX.1 FLUX.1 medium turbo schnell dev Table 3 Dense Layer 4 4 4 4 Dense Step 0 0 0 0 Table 4 Dense Layer - - - 4 Dense Step - - - 0 Appendix F More Generation Samples We provide additional image and video generation samples in Fig. 10 and Fig. 11 . Dense Attention     PISA (Ours)    SpargeAttn Dense Attention     PISA (Ours)    SpargeAttn Photorealistic high detail grizzly caught in forest fire with huge flames at night, ground perspective, shot on Nikon z6ii with 20mm at f1.4 aperture. Open bible on fire. Hyper realistic photo about two cute young kids that are lost in a forest. A boy and a girl. There must be a river. 4k resolution. In 3D and with depth perception. The decayed Berlin. Reichstag with destroyed dome. Everything is overgrown with plants and giant fungi. Year 2222. Rain. Dim atmosphere. Photo style, city buildings by the sea, business style, city overlooking, overall blue tone, gorgeous light and lighting, complex and gorgeous texture, calm feeling. Vertical screen. Drone photo of New York, New York center of long shot, soft color, night time, 16k. Troupial in the ray traced morning light. 4K, hyper realistic style, fantastical, otherworldly, brave. Cinematic photo of a 7 year old red hair girl on top of a crocodile on a jungle lake. Narnia style. Wes Anderson color palette. Sunrise natural light. Close up of a man and woman passionately kissing in the rain. Male friends hanging out in Seattle in 1994, smoking cigarettes, wearing grunge outfits, 90s, Style of Petra Collins, 35mm film, Canon EF 50mm, ProMist filter, low contrast, full body pose, wide angle, natural lighting, pastel coloring. A comic book depicting an awesome black dragon attacking a castle ,epic dynamic battle, in the style of dark red and light orange, Mike Deodato, Egyptian iconography, close up, dark blue and red, whiplash lines, afrofuturism. Medieval young woman raising hand volunteering as tribute, zoomed in, dark setting, by Syd Mead, Donato Giancola, Paul Lehr, Frazetta, frank miller, cinematic lighting, raking light. Figure 10 : Text-to-Image generation samples on FLUX.1-dev. The SpargeAttn under the 80% sparsity while PISA under the 85% sparsity. FULL PISA An astronaut is riding a horse in the space in a photorealistic style. FULL PISA A happy fuzzy panda playing guitar nearby a campfire, snow mountain in the background. FULL PISA A space shuttle launching into orbit, with flames and smoke billowing out from the engines. FULL PISA A cute raccoon playing guitar in a boat on the ocean. FULL PISA A teddy bear is playing drum kit in NYC Times Square. Figure 11 : Text-to-Video generation samples on Wan2.1-14B. The PISA under the 87.5% sparsity with 10 steps and 1 layer warmup.