INTRA: Interleaved Non-contiguous Token spaRse Attention

Yuxuan Xia; Wenbo Lu; Shaoyi Zheng; Shengjie Wang

cs.LGOct 25, 2026

INTRA: Interleaved Non-contiguous Token spaRse Attention

Authors: Yuxuan Xia, Wenbo Lu, Shaoyi Zheng, Shengjie Wang

Organizations: New York University

Abstract

Transformers achieve strong performance across modalities but are bottlenecked by the quadratic cost of attention. Sparse attention can reduce this cost, but effective sparsity must preserve useful long-range communication and map well to GPU hardware. We introduce INTRA--Interleaved Non-contiguous Token spaRse Attention--a hardware-aware static sparse attention design based on a relay-communication view under Computational Query Set (CQS) constraints. Rather than directly covering all token-to-token interactions within each sparse layer, INTRA uses complementary sparse groups to provide short mediated communication paths across layers. Scatter forms relay groups that sample broadly across local neighborhoods, while Gather reconnects these groups in subsequent layers. Under a partition model, this structure guides CQS-compatible sparse patterns with global reachability. Our CQS-aware FlashAttention-style kernel computes structured indices at runtime, loads selected non-contiguous tokens, and packs them densely for computation. On an A100, INTRA achieves a $1.53\times$ speedup in $2K$ FLUX.1-dev generation, with better measured image quality than evaluated CLEAR configurations after LoRA self-distillation. On LLaMA-3.1-8B, it improves long-context prefill efficiency with strong teacher-forced retrieval performance under matched LoRA adaptation. Attention-only benchmarks further show up to $8.4\times$ and $10.4\times$ speedups over MoBA and density-constrained NSA, respectively. Code is available at https://github.com/NovTi/INTRA.

Figures & tables

Figure 1: The figure reports the relative speedup achieved by INTRA compared to CLEAR and FlashAttention 2 on 4K and 16K input lengths, evaluated on an A100 GPU. Note that the axis density differs between the left and right sides of the figure to accommodate varying inference times.

Figure 2: Low-level implementation of blockwise sparsity for handling mixed blocks. A mix block is the block that partially preserves attention scores, as shown on the left side of the figure.

Figure 3: The Scatter and Gather 0 attention patterns used for image generation. Query and key tokens are arranged in a 2D feature map. Scatter groups tokens at the same local position across neighborhoods, while Gather 0 uses a

16\times 16

neighborhood spanning multiple Scatter groups.

Methods	Seq Len	Config	GFLOPS	Latency(ms)	Speedup	FID $\downarrow$
FlashAttention 2	4K	-	260.9	1.181	-	-
CLEAR		r=8	63.5	0.893	$1.32\times$	11.70
INTRA		Interleave Scatter/Gather	50.75	0.324	$3.64\times$	11.74
FlashAttention 2	16K	-	3507.9	15.764	-	-
CLEAR		r=8	246.2	4.625	$3.41\times$	32.46
INTRA		Interleave Scatter/Gather	345.5	2.056	$7.67\times$	15.67

Table 1: Single full-attention latency and speedup on A100. INTRA interleaves Scatter/Gather for image generation.

	1024 $\times$ 1024 Image Generation				2048 $\times$ 2048 Image Generation
Method	FID ( $\downarrow$ )	LPIPS ( $\downarrow$ )	CLIPI ( $\uparrow$ )	Gen Time(s)	FID ( $\downarrow$ )	LPIPS ( $\downarrow$ )	CLIPI ( $\uparrow$ )	Gen Time(s)
Original Model	-	-	-	13.42	-	-	-	66.78
CLEAR (r=8)	11.70	49.96	0.8995	12.85	32.46	61.62	0.8046	47.81
CLEAR (r=4-8)	-	-	-	13.73	19.27	54.60	0.8467	52.07
INTRA	11.74	49.46	0.9045	11.97	15.67	51.99	0.8559	43.72

Table 2: End-to-end latency and image quality at 1K/2K. CLEAR (r=4–8) uses 1/4-resolution K/V and radius 8; CLEAR (r=48) is slower than dense FLUX.1-dev .

Table 3: Attention operation speed and separate SCROLLS quality. INTRA achieves 2.23

\times

the speed of XAttention and 14.94

\times

the speed of MInference (geometric means, 8K–32K). Respective unweighted mean-score gaps are 0.87 and 0.42 points.

Table 4: LLaMA-3.1-8B retrieval quality and separate attention timing experiments.

Pattern in selected layers	Overall retained density	Mean NIAH $\uparrow$
Sliding window	0.069	0.028
INTRA block-level sparse attention	0.123	0.923
Dense attention	0.185	1.000

Table 5: LLaMA-3.1-8B attention-pattern ablation at four fixed layers with matched training budgets. The other 28 layers use windows with sinks; density covers all 32 layers.

Table 6: Ablation study: pattern choice and number of Scatter groups during interleaving.

Appendix figures & tables18 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 4: Token-level Scatter and Gather 1 patterns with a grouping factor of 4. Tokens are partitioned into 4 groups, shown by color, and both patterns compute attention within each group. These illustrate kernel variants rather than the block-level mask used in the retrieval experiments.

Method	4K	8K	16K	32K
FlashAttention 2	0.82	2.86	10.57	40.96
INTRA	0.16	See Table 3 (a)

Appendix

Table 7: Supplementary single causal-attention operation latency (ms) on A100. The FlashAttention 2 baseline and INTRA 4K result complement Table 3 (a), which reports the 8K–32K sparse-method timings. INTRA uses token-level Scatter/Gather.

Method	4K	8K	16K	32K
FlashAttention 2	137.4	549.8	2199.1	8796.3
MInference	–	329.8	1275.4	4398.1
XAttn S=16	–	153.6	614.2	2615.1
INTRA	17.2	68.7	274.9	1099.5

Appendix

Table 8: GFLOPS entries accompanying the single causal-attention timings in Tables 3 (a) and 7 . Dashes indicate unreported settings.

Pattern	Seq. Len.	Ideal	Actual
Scatter	4K	$8\times$	$4.81\times$
Gather 1	4K	$8\times$	$5.84\times$
Scatter	8K	$8\times$	$5.43\times$
Gather 1	8K	$8\times$	$5.83\times$
Scatter	16K	$8\times$	$5.90\times$
Gather 1	16K	$8\times$	$6.15\times$

Appendix

Table 9: Ideal vs. actual speedups for the token-level Scatter/Gather kernels on A100.

Method	Memory Throughput	Compute Throughput	Time (ms)
FlashAttention	49.95	70.69	15.80
INTRA Scatter	86.31	56.64	3.04
INTRA Gather 0	79.48	51.19	1.07

Appendix

Table 10: Nsight profiling at 16K in the image setting. Throughput numbers are reported by NVIDIA profiling tools at the kernel level.

Pattern	Seq. Len.	INTRA (ms)	Equally Sparse (ms)
Scatter	4K	0.17	0.19
Scatter	8K	0.53	0.52
Scatter	16K	1.79	1.65
Scatter	32K	6.58	5.73
Gather 1	4K	0.29	0.22
Gather 1	16K	1.07	0.79

Appendix

Table 11: INTRA compared with an equally sparse dense-FlashAttention simulation.

Table 12: End-to-end latency with and without attention.

Figure 5: Speed–quality trade-offs for LLaMA 3 on Qasper (left) and FLUX.1-dev (right). Horizontal axes show relative speed with the INTRA default at 1: points nearer the origin are slower, and points farther right are faster.

Table 13: Additional image-generation ablations. Left: comparison with a smaller dense diffusion model. Right: ablation on interleaving frequency.

	GovReport	Qasper	QMSum	QuALITY	SummScreen-FD
Original model (no fine-tune)	24.13	34.91	21.17	0.0	16.77
Original model	31.05	40.09	25.37	26.0	20.51
INTRA	27.77	39.64	24.45	29.0	19.71

Appendix

Table 14: LLaMA 3.1 8B performance on SCROLLS with and without fine-tuning.

Window width	NIAH at 4K $\uparrow$	NIAH at 32K $\uparrow$
575	0.111	0.000
2048	0.556	0.000
4096	1.000	0.111

Appendix

Table 15: Window-width ablation on LLaMA-3.1-8B with sliding-window attention in all 32 layers. Scores are measured NIAH results at 4K and 32K context lengths.

Configuration	Retained density	Mean NIAH $\uparrow$
Sparse attention in 16 layers (per-layer density 0.125)	0.098	0.130
Wider windows	0.234	0.222
Four global sparse layers (per-layer density 0.5)	0.123	0.923
Dense + LoRA	1.000	1.000

Appendix

Table 16: Language attention configurations under the same adaptation budget. Retained density refers to the overall attention configuration, normalized to dense attention at 1.000.

Table 17: Causal prefill attention latency (ms) on A100-SXM4-80GB. (a) Sum of 32 per-layer medians for the fixed INTRA g2s4 schedule and baselines. (b) Single-layer comparison with target density 0.125. NSA (tuned) is the fastest tested setting satisfying

\rho\leq 0.125

; NSA (paper) uses its paper hyperparameters. INTRA speedup over a baseline is

t_{\mathrm{baseline}}/t_{\mathrm{INTRA}}

VBench dimension	Dense	INTRA	Absolute difference
Subject consistency	0.9427	0.9405	0.0022
Background consistency	0.9587	0.9551	0.0036
Aesthetic quality	0.5362	0.5168	0.0194
Imaging quality	0.6036	0.5472	0.0564
Temporal flickering	0.9886	0.9874	0.0012
Motion smoothness	0.9664	0.9689	0.0025

Appendix

Table 18: All 13 evaluated VBench ( Huang et al., 2024 ) dimensions on Wan2.2-TI2V-5B ( Team Wan et al., 2025 ; Team Wan, 2025 ) , using 944 prompts and five samples per prompt. Higher scores are better; the final column reports absolute dense–INTRA differences.

End-to-end generation and pipeline components (s)
Resolution	$480\times 832$	$704\times 1280$	$704\times 1280$
Frames / video tokens	49 / 5,070	121 / 27,280	241 / 53,680
Total generation	$44.1\rightarrow 41.2$	$340.9\rightarrow 238.4$	—
End-to-end speedup	$1.07\times$	$\mathbf{1.43\times}$	—
DiT total (100 forwards)	$40.9\rightarrow 38.0$	$326.9\rightarrow 224.2$	—
VAE decoding	2.6	13.4	—

Appendix

Table 19: Wan2.2-TI2V-5B video timing on A100-SXM4-80GB. Arrows show dense

\rightarrow

INTRA; speedups are dense time divided by INTRA time. End-to-end and pipeline components are in seconds, while standalone forward and self-attention times are in milliseconds. The 49-frame setting matches VBench; 121 frames corresponds to the native five-second setting at 24 fps. The 241-frame setting measures standalone speed only; dashes denote unmeasured pipeline timings.

Figure 6: FLUX.1-dev outputs: original FlashAttention 2, INTRA, and CLEAR (left to right).

Figure 7: Visual examples comparing original FLUX.1-dev , INTRA, and CLEAR.

Figure 8: Additional visual examples with the same column order as Figure 7 : original FLUX.1-dev , INTRA, and CLEAR within each triplet.

Sparse Attention

Sparse attention reduces the token interactions computed by Transformers to lower the cost of long-context modeling and inference.

See all 245 papers

Block Sparse Flash Attention
Dec 7, 2025Daniel Ohayon, Itay Lamprecht, Itay Hubara +3GPU Acceleration Self-Attention
Technion – Israel Institute of Technology, Haifa, Israel · Intel - Habana Labs · Intel – Habana Labs, Tel Aviv, Israel
FSA: An Alternative Efficient Implementation of Native Sparse Attention Kernel
Aug 25, 2025Ran Yan, Youhe Jiang, Zhuoming Chen +3GPU Kernel Optimization GPU Acceleration
1. The Hong Kong University of Science and Technology · 2. Carnegie Mellon University
SpotAttention: Plug-In Block-Sparse Routing for Pretrained Long-Context Transformers
Jun 22, 2026Huzama Ahmad, Se-Young YunSparse Attention Block-Sparse Attention
KAIST

Dec 7, 2025J/K move · Enter open · S save

Block Sparse Flash Attention

Daniel Ohayon, Itay Lamprecht, Itay Hubara, Israel Cohen+2

Technion – Israel Institute of Technology, Haifa, Israel · Intel - Habana Labs · Intel – Habana Labs, Tel Aviv, Israel

GPU Acceleration Self-Attention Long-Context Language Model Inference High-Performance Computing LLM Inference Acceleration Sparse Attention+3

Open paper AskPDF arXiv

Modern large language models increasingly require long contexts for reasoning and multi-document tasks, but attention's quadratic complexity creates a severe computational bottleneck. We present Block Sparse Flash Attention (BSFA), a drop-in replacement that accelerates long-context inference while preserving model quality. Unlike methods that predict importance before computing scores, BSFA computes exact query-key similarities to select the top-k most important value blocks for each query. By comparing per-block maximum scores against calibrated thresholds, we skip approximately 50% of the computation and memory transfers for pruned blocks. Our training-free approach requires only a one-time threshold calibration on a small dataset to learn the per-layer and per-head attention score distributions. We provide a CUDA kernel implementation that can be used as a drop-in replacement for FlashAttention. On Llama-3.1-8B, BSFA achieves up to 1.13x end-to-end speedup on LongBench with only a 1.1% accuracy drop, and up to 1.24x on Needle-in-a-Haystack retrieval at a 1% accuracy drop. The attention kernel itself accelerates by up to 1.38x. We compare BSFA against five recent sparse attention baselines (SpargeAttention, MInference, FlexPrefill, XAttention, and BLASST), and verify the method on Qwen2.5-7B and on A6000 and H100 GPUs. The implementation is available at https://github.com/Danielohayon/Block-Sparse-Flash-Attention.

Abstract

Sparse Attention

Explore similar work

Block Sparse Flash Attention

FSA: An Alternative Efficient Implementation of Native Sparse Attention Kernel

SpotAttention: Plug-In Block-Sparse Routing for Pretrained Long-Context Transformers