MMInference: Accelerating Pre-filling for Long-Context Visual Language Models via Modality-Aware Permutation Sparse Attention
Authors: Yucheng Li
Huiqiang Jiang
Chengruidong Zhang
Qianhui Wu
Xufang Luo
Surin Ahn
Amir H. Abdi
Dongsheng Li
Jianfeng Gao
Yuqing Yang
Lili Qiu
Venue: ICML 2025 poster (2025)
Keywords: Visual Language Model
LLMs Inference
Long-Context LLMs
Dynamic Sparse Attention
Efficient Inference
Primary area: deep_learning->large_language_models

Abstract: The integration of long-context capabilities with visual understanding unlocks unprecedented potential for Vision Language Models (VLMs). However, the quadratic attention complexity during the pre-filling phase remains a significant obstacle to real-world deployment. To overcome this limitation, we introduce MMInference (Multimodality Million tokens Inference), a dynamic sparse attention method that accelerates the prefilling stage for long-context multi-modal inputs. First, our analysis reveals that the temporal and spatial locality of video input leads to a unique sparse pattern, the Grid pattern. Simultaneously, VLMs exhibit markedly different sparse distributions across different modalities. We introduce a permutation-based method to leverage the unique Grid pattern and handle modality boundary issues. By offline search the optimal sparse patterns for each head, MMInference constructs the sparse distribution dynamically based on the input. We also provide optimized GPU kernels for efficient sparse computations. Notably, MMInference integrates seamlessly into existing VLM pipelines without any model modifications or fine-tuning. Experiments on multi-modal benchmarks-including Video QA, Captioning, VisionNIAH, and Mixed-Modality NIAH-with state-of-the-art long-context VLMs (LongVila, LlavaVideo, VideoChat-Flash, Qwen2.5-VL) show that MMInference accelerates the pre-filling stage by up to 8.3x at 1M tokens while maintaining accuracy. Our code is available at https://ama.ms/MMInference.

MMInference: Accelerating Pre-filling for Long-Context Visual Language Models via Modality-Aware Permutation Sparse Attention
Yucheng Li 1 Amir H. Abdi² Dongsheng Li Jianfeng Gao Yuqing Yang² Lili Qiu
Huiqiang Jiang
Chengruidong Zhang² Qianhui Wu? Xufang Luo? Surin Ahn
Abstract
The integration of long-context capabilities with visual understanding unlocks unprecedented po- tential for Vision Language Models (VLMs). However, the quadratic attention complexity dur- ing the pre-fille pre-filling phase remains a significant ob- stacle to world deployment. To overcome this limitation, we introduce MMInference (Multi- modality Million tokens Inference), a dynamic sparse attention method that accelerates the pre- filling stage for long-context multi-modal inputs. First, our analysis reveals that the temporal and spatial locality of video input leads to a unique sparse pattern, the Grid pattern. Simultancously, VLMs exhibit markedly different sparse distribu- tions across different modalities. We introduce a permutation-based method to leverage the unique Grid pattern and handle modality boundary is- sues. By offline search the optimal sparse pat- terns for each head, MMInference constructs the sparse distribution dynamically based on the in- put. We also provide optimized GPU kernels for efficient sparse computations. Notably, MMIn- ference integrates seamlessly into existing VLM pipelines without any model modifications fine-tuning. Experiments multi-modal bench- marks-including Video QA, Captioning, Vision- NIAH, and
Dynamic Sparse Attention
Sparse Pattern
Shape
A-
vs
Grid
Block Sparse
Estimation
Last
Pooling/
Antidia
(e.g. Ong), ((n2))
Compress
gonal
Dynamic Sparse Index
Permutation (Sparse Load)
Column /Row
(back)
Grid
Block
slash
Tile-wise (Dense Compute)
Block-sparse Tensor Core
(eg. WOMMA)
in kernel
Figure 1: Dynamic sparse attention pipelines leverage sparse loading with dense computation (Zheng et al., 2023) enable hardware-efficient acceleration. MMInference adopts a bottom-up system-algorithmm co-design that accounting for both the mathe- matical equivalence constraints of sparse loading and the locality properties of real-world attention patterns.
1. Introduction
Scaling the context size of Vision Language Models (VLMs) allows them handle extended temporal information from long video and text inputs, which is crucial for various appli- cations including robotics (Black al., 2024; Prasad et al., 2024; Cheang et al., 2024), autonomous driving (Hu et al., 2023; Wang et al., 2024c; Gao et al., 2024), and health- care (Liu et al., 2024b). In addition, Zhang et al. (2024b) and Chen et al. (2025) show that scaling the context size of VLMs can improve the resolution in the temporal dimension and lead better performance video understanding tasks.
with state- of-the-art long-context VLMs (Long Vila, Llava- Video, VidcoChat-Flaan Flash, Qwen2.5- 5-LL) show that MMInference accelerates the pre-filling stage by up 8.3x 1M tokens while maintaining ac- curacy. Our code is available at https: //aka. ms /MMMMineeeee.e.
However, due the quadratic complexity of attention, pro- cessing long multi-modal inputs (i.e., the pre-fill stage) can take minutes prior to auto-regressive decoding. As shown in Fig. 2a, this leads to significant Time-to- -iinettt-Frrt---- First----TTo latency, which hinders the wide adoption of long-contex VLMs in real-world applications. Previous work (Child et al., 2019; Liu et al., 2022; 2024a; Yuan et al., 2025; Lu et al., 2025) re-
WWrk during internship Microsoft. Univeessity of Surrey Miicooooft Corporation. Correspondence to: Huiqiang Jiang <hjiang@ microsoft.com>.
Proceedings of the nnnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

MMInference: Accelerating Pre-filling for Long-Context VLMs via Modality-Aware Permutation Sparse Attention
25
VIT
VLM
1-
Attention Recall 71.3%
1.0
Allention
25%
Latency(min)
FRN
Total
Topk Ratio
20%
0.8
15%
12-
10-
916-
10%
0.4
20-
24-
0.2
1-
28
0.0
512
1k
2k Num. Frames
4k
1
5
10
20 Layer Index
15
25 28
1
4
8
12
16 Head
20
24
28
(a) VLMs' attention incurs heavy cost.
(b) VLMs' attention is sparse.
(c) Sparsity of VLMs' attention dynamic.
Figure 2: (a) Latency breakdown of the pre-filling stage, with 256 tokens per frame. (b) How much element in attention needs to be computed to achieve 95% recall in 128k context. (c) Low attention recall when reusing the top-k k indices from different request. Visualizations are based Long VILA-7B- 1M (Chen et al., 2025) with single A100.
veals that attention matrices are typically sparse, prompting the development of sparse attention methods such as Sparse Transformer (Child et al., 2019), Swin Transformer (Liu al., 2021), and LLM (Xiao et al., 2024). More recently, MInference (Jiang et al., 2024) proposes to dy- namic sparse attention that estimates the sparse index online, and leverages optimized GPU kernels for end-to-end accel- eration. However, these methods fail to exploit the unique sparse patterns in long-contexs VLMs, and struggle with mixed or interleaved modalities, limiting their applicability without compromising performance.
2025) and Qwen2.5- VL (Bai et al., 2025), across diverse video understanding tasks such as video captioning (Maaz et al., 2024), video question answering (Yu et al., 2019; Xiao et al., 2021; Mangalam et al., 2023; Fu et al., 2024), and video information retrieval (Zhang et al., 2024a). Addition- ally, propose the Modality Needle in Hackathon task to assess multi-modal input performance. Our method effectively addresses modality boundaries, significantly ac- celerates the prefilling stage, and maintains high accuracy. With a IM-length context, achieves speedups of up to 8.3x and 1.7x over FlashAttention-2 and MInference, re- spectively.
Unlike long-text contexts, video and image inputs in VLMs exhibit spatiotemporal locality, forming grid-like attention patterns with evenly spaced vertical and horizontal lines (Fig. 3a). In mixed-modality inputs, clear modality bound- aries emerge: attention across modalities diverges signifi- cantly from modra-modality attention (Fig. 3b). These factors pose unique challenges for exploiting sparsity to accelerate the fre-fill stage.
2. Attention Heads in VLMs
The sparsity of the attention operation in pre-trained text- only LLMs, particularly in long-context scenarios, has been extensively studied (Wu al., 2025; Ribar et al., 2024; Jiang et al., 2024; Li et al., 2024), showing that only 3% of attention weights are activated while achieving recall rate of 96.8%. Similarly, VLMs also demonstrate notable dynamic sparsity in long-context scenarios. This section examines the shared and distinct properties of text-only and multi-modal LLMs in long-com mon-ccotext scenarios, focusing on attention sparsity, sparse patterns, and modality boundaries.
In this paper, we present MMInference, permutation based dynamic sparse attention method that significantly reduces attention FLOPs, accelerating the pre-fill stage of long- context VLMs. First, MMInference identifies the grid heads and leverages a row- and column- permutation to gather the sparse grid for efficient hardware computation. Next, we detect Query- bounddayy and 2D-boundary patterns to address inter-modality boundary issues, and apply modality-wise permutation to isolate intra-modality regions. This results in a consecutive sparse index within each modality, permitting efficient hardware implementation of sparse computing. Fi- nally, a Modality-Aware Sparse Attention Search Algorithm devised fine-tune both inter- and intra-modality patterns offline, to optimize performance with minimal overhead.
2.1. Multi-modality Attention is Dynamically Sparse
As illustrated in Fig. 2a, for a 128k x 128k attention matrix in VLMs, retaining only the top 5.78% of attention weights on average suffices to recall 95% of total attention, indi- cating that each token attends only limited subset of tokens, even in long sequences. However, VLMs exhibit lower sparsity than text-only L.MMs, where only 1.79% of weights achieve a 95% recall rate. Notably, the bottom lay- ers in VLMs (e.g., the first four layers in LongVila) show reduced sparsity. Yet, due to variability across attention heads, 52.3% of heads in VLMs require less than 2% of
We conduct extensive experiments using four state-of-the- art long-context VLMs, Llava-Video (Zhang et al., 2024b), I LongVi Vila (Chen et al., 2025), VideoChat-FFan (Li et al.,
2

---

MMInference: Accelerating Pre-filling for Long-Context VLMs via Modality-Aware Permutation Sparse Attention
frame
langunge
Vision
K-wise boundary
Fixed strdd size
Language
Vision
Patch size 1d 14
Q Misc boundary
Language
Modslity boundary
(a) Grid pattern.
(b) Q-Boundary pattern.
(c) 2D-Bounday pattern.
V2V
V2T
Vlines after shuffle
Consecutive Modality
Consecutive pattero
Hlinee after shuffle
T2V
T2T
(d) Permuted Grid pattern.
(e) Permuted Q-Boundary pattern.
(l) Permuted 2D- ID-Boundary pattern.
Figure 3: Visualization of pre- vs. post-permutation sparsity attention patterss in VLMs.
attention to be recalled. This highlights substantial compu- tational redundancy in VLMs, especially in long-context scenarios.
predictable patterns.
We observe that certain VLM attention heads exhibit a grid pattern. While the grid's stride and starting position vary with context, the horizontal and vertical lines are evenly spaced and often symmetrical-a distinct behavior com- pared to text-only LLMs (Jiang et al.. 2024; Lai et al., 2025), Fig. 3a visualizes grid head, demonstrating how local tokens in temporal and spatial dimensions are evenly dis- tributed within the attention map, with attention focused primarily on these local tokens.
Similarly to LLMs, while the sparse nature of attention matrices remains consistent across inputs, the specific distri- butions of sparse attention are highly dynamic. As shown in Fig. 2c, reusing top-k indices for 95% attention recall (derived from Fig. 2b) across different contexts leads to a significant drop performance.
2.2. The Grid Head in VLMs
2.3. Modality Boundaries in Multi-Modal Input
In long-context language modeling, efficient attention mech- anisms like sliding window attention (Jiang et al., 2023) and StreamingLLM (Xiao al., 2024) exploit the locality property of text sequences. However, multi-modal inputs introduce unique geometric structures that redefine local- ity. As shown in Child et al. (2019), image patches exhibit locality along both vertical and horizontal directions, form- ing local window and slash-like patterns. Similarly, video inputs maintain locality across temporal and spatial dimen- sions, with frame-based sampling yielding more regular and
The input format of VLMs differs significantly from text- only LLMs. A dedicated vision encoder generates visual representations, which processed alongside text beddings by the LLM. Despite pretraining large-scale datasets, the interactions and processing patterns between modalities vary considerably, leading to distinct modality boundaries attention (Tu et al., 2025), as illustrated in Fig. and 3c.
3

---

MMInference: Accelerating Pre-filling for Long-Context VLMs via Modality-Aware Permutation Sparse Attention
Inter-modality Attention Pattern
No-Boundary head
K-Boundary head
Q-Boundary head
Bo-Bddadrry head
Intra-modalit Attention Pattern
www.mm
Approximate by lest
Permutation
UAAAAAA
A-shape head
vertical-slash head
grdd head
Figure The framework MMInference, encompassing both inter- and intra-modality sparse attention patterns.
Specifically, we observe two key characteristics: 1) Intra- modality consistency: Attention within each modality fol- lows a consistent pattern. For instance, the vision region in Fig. 3b exhibits clear slash pattern, where critical elements are effectively clustered. 2) Modality-spparatte continuity: Patterns within a modality can be interrupted by boundaries from other modalities. As shown in Fig. 3b, vision slashes are segmented by the boundary introduced by the language region.
2.4. Sparse Distributions Continuity Across Boundaries
Although sparsity patterns in VLMs are often discontinuous across modalities due to modality boundaries, we find that sparsity distributions can remain continuous boundaries and extrapolate to other regions of the same modality. For example, in Fig. 3b, the slash lines maintain the same relative position across different areas of the vision modality. In more complex case, Fig. 3c shows interleaved vision and text modalities forming mixed structure. How- ever, by spatially aggregating regions of the same modality, we observe that sparsity patterns can extend beyond local regions and often exhibit global extrapolation potential. The upper-left region in Fig. 3c exemplifies this, where the grid patter, initially separated by textual boundaries, becomes consecutive after spatial clustering in both row and column dimensions. To validate this observation, we conducted a quantitative attention recall experiment on mixel-modalityy imputs, as detailed in $4.6.
these
We categorize the modality boundary patterns of VLMS into four distinct types: No-Boundary, K-Boundary, Q- Boundary, and 2D-Boundary, as illustrated in Figs. and 4. I) No Boundary and K-Boundary exhibit either no clear modality boundary or boundary only along the key dimension, as shown Fig. 9. Since continuity is main- tained along the query dimension, these heads can be ef- ficiently handled using intra-modality sparse patterns. 2) Q-Boundary refers attention modality boundaries across the query dimension. For example, in Fig. 3b, sparse pat- terns like Text-to-Video and Video-to-Videe appear inter- connected, forming a trapezoidal structure, while a clear boundary separates Visual-to- iisual-to-Text and Text-to- text-to-Visual atten- tion. 3) 2D-Boundary occurs when modality boundaries present in both query and key dimensions. As shown in Fig. 3c, the 2D modality boundary segments attention weights into distinct blocks. Additionally, our analysis of Audio LMs (Chu et al., 2024) and end-to-end multimodal LMs (Xu et al., 2025a; Li et al., 2025) reveals that the mross-modality boundary phenomenon persists across these architectures. These boundaries pose unique challenges and hinder direct application of existing sparse attention methods multi-modal inputs.
3. MMInference
Following the analysis in $2, we propose MMInference to accelerate the pre-filling stage of long-context VLMs as shown in Fig. 4. The framework consists of three modules, covering both inter- and intra-modality sparse patterns: the novel Grid sparse attention, together with the A-shape and Vertical-SCe -atical-Slash patterns (Jiang et al., 2024) forms the intra-modality attention; 2) Q-Boundary and 2D- ID-Boundary mix-mon mix-mtoallty patterns; 3) Modality-aware sparse attention search algorithm. We first perform offline pattern search to identify different patterns for each attention head. Then we

---

MMInference: Accelerating Pre-filling for Long-Context VLMs via Modality-Aware Permutation Sparse Attention
use online dynamic sparse approximation build the sparse index, and finally perform dynamic sparse computation using optimized GPU kernels.
and K-Boundary heads, we can directly apply the three intra-modality attention globally. However, for Q-Boundary and 2D-Boundary, MMInference uses a permutation-based approach to efficiently handle these modality boundaries.
3.1. Grid Head in Multi-Modality
To better leverage the inductive bias in visual modalities (e.g., images, videos) and the vertical and horizontal struc- tures in attention patterns, we propose permutation bernutation-based dynamic sparse attention for grid head, as shown in Algo. 1.
Q-Boundary Head As shown in Fig.3b, Fig.3e, and $2.4, the Q-Boundary pattern shows a clear separation across modality, but the sparse distribution remains continuous within each modality. Building on this insight, we propose row-wise permutation (Algorithm 2) that groups tokens of the same modality by permuting Q, and then applies offine-optimized sparse attention (A-shape, Vertical-Slash, and Grid Head) for intra-modality processing. Note that we leverage the final segment of each modality's queries to dynamically approximate the sparse indices and extrapolate to the entire modality. This method enables flexibility in handling fragmented multi-modality inputs. Additionally, instead of explicitly permuting tensors, our implementation performs dynamic loading and writing inside the kernel for optimized efficiency.
Algorithm 1 Grid Head
Input: Q,K, V. RSSxs, stride space sy E 0g
# Approximate stride and phase (last q= 64)
Ä softmax (Qi-mag)] / + Messual
# Online search grid stride and phase br,
for to 10,1 do
if max(view( AA, :)) > by then
S9 f Sy.s, Ps f argmax(view) A, sg.s))
by c max(view A, s).:))
end
Algorithm Q-Boundary Head
end for
Input: Q, K, V E Sxds, modality type index km. modality type set m E Φm
# Permute K. tensors
Q, Q.K.V V + permute (Q), permute (K), permute (V)
# Dynamic block sparse attention w/ FlashAttention (only the last and righimost block)
# Permute Q tensors based on modality
Q + permute (Q, km)
A 4- softmax (sparse QK' (sg:Pa)/ P/)///)
# Looping over the modalities in query dimension
y + 0 for i + 1 to I@ml do
# Sparse mixed scores and values
y f sparse(AV (AV, Pg) return y
Intra-modality sporse attention for each modality w/ FlashAttention
Ams + softmax (sparse Qm.. (mms) l
Specifically, we first perform an online search to determine the stride and phase of grid pattern. Since only a view oper- ation is applied the approximate attention matrix A, the actual latency overhead remains minimal. Next, we use the identified grid stride and phase to permute the Q, K, and V tensors to compute sparse attention efficiently (see Fig. 3d). In our implementation, instead of explicitly permuting Q. K. and V. we optimize computational efficiency by dynam- ically loading and writing these tensors within the kernel, minimizing the overhead associated with tensor transposi- tions. In addition to Grid sparse attention, we also employ A-shape and Vertical-Slane attention for intra- intra-modality op- eration, see Appendix C.3 for more details.
ymi <- sparse( V)
# Update the modality output to the final output
y < yms Ug
end for return y
2D-Boundary Head Beyond Query-Boundary. there attention heads that exhibit modality boundaries in both query and key dimensions, as shown in Fig. 3c. Given a query token, attention to key tokens from different modali- ties varies significantly, and queries from different modali- ties focus on keys highly diverse patterns. To address 2D modality boundaries, we design a 2D permutation approach that groups Q, K, and V according to their modalities. This allows us to leverage intra-mon midaa-ty continuity to handle each part of 2D boundary pattern separately and efficiently. We further illustrate this approach in Fig. 3f and it detailed in Algorithm 3. Specifically, we perform permutation on both row- and column- for Q. K, and V. and then iteratively traverse each modality pair to compute dynamic
3.2. Hybrid Modality Sparse Attention
As analyzed in $2 and illustrated in Fig. 3. modality bound- aries exist in multi-modal LLMs. We classify these bound- aries into four patterns: No-Boundary, K- K-Boundary, Q- Boundary, and 2D-Boundary. As the sparse index is contin- uous along the query dimension for both the No- ho-Boundary
5

---

MMInference: Accelerating Pre-filling for Long-Context VLMs via Modality-Aware Permutation Sparse Attention
Table I: Performance (%) different models and different methods on video understanding tasks evaluated frames 256.
VideoDC
ActNet-QA
EgoSchema
Next-QA
PerceptionIesi
VideoMME
Model
FLOPs
Avg.
test
test
test
me
val
w/o sub.
w/ sub.
Llava Video-7B
Frames: 110; Total tokens:
20,240
Full Attention
100%
3.66
59.6
57.0
81.2
66.1
64.7
71.0
57.6
SF-fixed
4.8%
3.26
57.3
53.3
79.8
62.9
59.9
67.1
54.8
SF-strided
41.4%
3,45
58.5
64.4
61.4
68.5
56.1
A-shape
48.2%
3,56
56.0
51.6
79.8
65.7
54.4
65.6
53.8
Tri-shape
49.0%
3,58
59.3
54.5
80.3
66.1
63.6
70.1
56.7
VisionZip
35.2%
1.35
42.1
40.5
69.5
41.4
44.9
62.1
43.1
MInference
78.8%
3.64
59.6
57.0
80.6
66.1
64.6
71.0
S7.5
Ours
47.3%
3.58
59.8
57.1
80.1
66.2
64.5
71.8
57.6
Long VILA-7B
Frames: 256;
Total tokens: 65,800
Full Attention
100%
2.76
59.5
61.9
80.7
58.1
60.1
65.1
55,5
SF-fixed
2.2%
1.99
51.3
59.6
76.5
55.5
57.1
63.0
52.1
SF-strided
26.6%
2.58
56.0
61.4
76.7
55.5
53.6
59.2
52.2
A-shape
29.1%
2.75
56.6
60.9
75.0
55.3
49.1
59.6
51.3
Tri-shape
29.3%
2.63
58.1
62.0
77.8
56.2
59.3
63.3
54.2
VisionZip
OOM
MInference
47.0%
2.77
59.7
62.2
79.1
57.8
60.0
65.2
55.2
Ours
31.8%
2.84
60.2
62.2
79.4
57.8
60.0
65.5
55.4
Qwen2.5-VL 10--mn.5-VV-7---nsiiii
# Frames: 256; Total # tokens: 33,950
Full Attention 100%
3.71
58.3
64.3
85.4
68.7
64.7
71.3
59.5
Ours
41.3%
3.75
58.0
63.9
84.9
68.9
65.1
70.9
59.4
3.3. Modality-Aware Sparse Attention Search Algorithm
Algorithm 3 Boundary Head
Input: Q.K. K, VE RSSx,,, modality type index i. modality type
Due to modality boundaries in VLMs, we propose modality-aware sparse attention pattern search algorithm (see Algorithm 4). The process unfolds in three steps: I) intra-modality search within each modality following (Jiang et al., 2024), 2) cross-modality search across all modality pairs, and 3) inter-modality search informed by the results of the first two steps.
E dmn
Permute K. V tensors based modality
Q permute (Q, im). + permute (K, im)
V pernute (V, (.im)
Looping over the modalities in puirs + 0
for to [dml do
for [0ml do
4. Experiments
# Dynamic sparse attention for each modality pair w/ FlashAttention
In this section, we address two key questions: (i) How effective MMInference is? We evaluate our method on three general long- tasks: long- understanding. Video Needle in Haystack, and Video-Text Needle in Haystack. These benchmarks cover long-video captioning, open-ended QA, multiple-choice QA, mixed-modality tasks, and retrieval tasks, providing a comprehensive assessment of MMInference's effectiveness across diverse long-vidas scenarios. (ii) How efficient MMInference is? We analyze end-to-end latency and its breakdown thoroughly evaluate the efficiency of MMInference.
Mm + buildmask( (imi kmn))
Ans,mj <- softmax(
sparse Qm:: mjj kmss kmn)) ) dd mons,m)
Fmi.mn <- sparse(AAas (Ami,ms m))
Update the modality output to the final output
y < Umimmj Ug!
end for end for return y
sparse attention. The 2D-Boundary requires constructing an attention mask and searching for sparse patterns in cross- modality regions. For example, in Fig. 3f, we build modal- ity boundary indices for Vision-to-Teex (bottom-left) and Text-to- Text-to-Vision (upper-right) attention. This mask index con- struction implemented Triton (Tillet et al., 2019).
4.1. Dataset and Baselines
Implementation Details Our experiments are con- ducted on two state-of-the-arr long-video VLMs: Llava-
6

---

MMInference: Accelerating Pre-filling for Long-Context VLMs via Modality-Aware Permutation Sparse Attention
LongVILA-1M w/ MMInference VNIAH Recall 97.7%
LongViLA-1M in VNIAH Recall 98.3%
-10
1.0
0-
0-
Dapth Percent
20
0.8
Depth Percent(/5
-0-
-0.8
0.6
0.6
0,4
0.4
80
-02
0.2
100
100
0.0
-0.0
300
500
300
600
900
Num. of Frames
(a) MMInference in V-NIAH
(h) FullAttention V-NIAH
LongVILA-11 w/ MMinference in MMNIAH Recall 91.3%
LongViLA-1M in MMNIAH Recall 90.9%
1.0
0-
Depth Percent(%)
Depth Percent(96)
40
0.6
e
40-
0.6
60
00
60
-0.4
00
0.2
-.2
100
300
3,3k
3,8k
4.2%
ask
0.0
900
3,8
4.k
0.0
Num. of Frames
Num. of Frames
(c) MMInference in MM-NIAH
(d) FullAttention in MM-NIAI
Figure 5: V-NIAH (Zhang et al., 2024a) and MM-NIAH results using VonnVVil--Qe filla-Qee22-7B- (Chen al., 2025).
Video (Zhang et al., 2024b) and Long (Chen al., 2025). We follow the MInference experimental setup, con- figuring the corresponding search space while adopting op- timal configurations from prior work for other methods. We adjust the local window sizes of A-shape and tri-shape pat- terns align FLOPs with our method. For MInference, we adopt its optimal configuration, which results with FLOPs approximately twice high
frames (c.g.. g. 66k) in Llava- Video (Zhang et al., 2024b) and LongVILA (Chen et al., 2025).
(ii) Video Needle in a Haystack (V-NIAH) (Zhang et al., 2024a): A long-video retrieval task testing VLMs' perfor- mance with tokens of up to 6k frames (e.g.. 1.IM tokens), where inserted images are placed various positions.
method's in VLMs. Our implementation leverages Triton (Tillet et al., 2019), FlashAttention (Dao, 2024), and dynamic sparse compiler PIT (Zheng et al., 2023). For the Vertical-Slash and Grid Head patterns, we set last, = 64. Latency experiments are performed on a single NVIDIA 100 using bíloat16, with greedy decoding to ensure stable results. Additional implementation details provided in Appendix C.
(iii) Mixed-Modalie Needle in Haystack (MM-NIAH): To evaluate VLMs in mixed-modall scenarios, we construct mix-modality version of NIAH. Specifically, 25% of the input consists of text segments inserted at the document level across different frames long-video inputs, forming mix-modality haystack. All other settings align with NIAH, including the multi-choice VQA task with randomly inserted images. This benchmark tests input lengths of up to 4.5k frames (e.g.. 1.1M tokens).
Dataset Our evaluation uses the official metrics and scripts provided by these tasks. Additionally, we introduce a Mixed-Modality Needle in a Haystack (MM-NIAH) task to assess VLMs' retrieval capabilities on mixed -odalityy inputs. Dataset details are provided in Appendix D.
Baselines We include five training-free sparse attention approaches, one visual token compression method, and also incorporate FlashAttention-2 (Dao, 2024) as a baseline. 1) OparseTransforen (Fixed) (Child al., 2019): Retains attention within each segment and allows all tokens at- tend the segment's initial tokens. 2) Sparse Transforree (Strided) (Child et al., 2019): Employs local windows with dilated attention. 3) A-Shape (Xiao et al., 2024): Preserves only the sink token with local attention. 4) Tri-Shape (LI et al., 2025; Acharya et al., 2024): Extends A-Shape by enabling full attention for all tokens to the last window's
(i) Video Understanding Tasks: These include ActNet- QA (Yu al., 2019), EgoSchema (Mangalam al., 2023), Next-QA (Xiao et al., 2021), Perception'Test (Patraucean et al., 2024), VideoDC (Lab, 2024), and VideoMME (Fu et al., 2024). These benchmarks span five categories, cover- ing tasks such as captioning and video question answering. Input lengths range from 110 frames (e.g. 20k) 256

---

MMInference: Accelerating Pre-filling for Long-Context VLMs via Modality-Awarn Permutation Sparse Attention
(a) All Textual Context
(b) Visual Context Inserted
(c) More Visual Context
(d) All Visual Context
Figure 6: Transition of sparse patterns from textual context visual context. (a) The vertical-slash pattern for all textual context. (b) Grid pattern appears when visual modality appended. (c) Grid pattern dominates.
queries. 5) Vertical-Slase Pattern (Jiang et al., 2024): Fo- cuses on specific tokens (vertical lines) and tokens at fixed intervals (slash lines). 6) VisionZip (Yang et al., 2024): A visual token compression method that reduces the number of visual tokens per frame by evaluating tokens based on their attention scores and discarding less important ones. Full de- tails on implementation, hyperparameters, and illustrations for our baselines can be found in Appendix C.
4.4. Mixed-Modality Needle In A Haystack
Beyond V-NIAH, we introduce a mixed-modality NIAH test to evaluate the performance of different sparse meth- ods on video-text inputs, Fig. 5c, 5d, and 14. Mixed- modality inputs lead to more pronounced performance degradation across all methods. However, by incorporating inter-modality sparse patterns, our method maintains perfor- mance close to full attention, especially when compared to MInference and ours w/o inter-modality. Notably, Tri-shape and MInference show significant drops at 1.8k frames (i.g. 440K tokens) and 2.7k frames (i.g. 660K tokens).
4.2. Long Video Understanding
Table presents the performance of different methods on video understanding tasks. The results show that: 1) Our method and MInference closely approximate full attention across all tasks while requiring only half the FLOPs of MInference. 2) Static sparse patterns, such A-shape and Tri-shape, perform reasonably well on most tasks but experience notable performance drop in multi-choice VQA tasks like EgoSchema. Additionally, the slight increase in query full attention in Tri-shape effectively improves performance. 3) Among SF patterns, the slash pattern better preserves performance. Even when using Si-eixed with only 2%-5% of FLOPs, it still maintains strong performance on most tasks.
4.5. Latency
25
FlashAttention-2
satency(ming
18-
Minference
MMinference
8.3x
10
1.6x
1.5x
300/120K
900/360K Num. of Frames / Context Windows
1800/720K
2700/1M
4.3. Video Needle In A Haystack
Figure End-to Latency.
Fig. 5a, 5b, and 13 show the performance of different mod- els V-NIAH, revealing notable differences in handling long-context video retrieval as the number of processed frames increases: 1) Our method achieves results nearly identical to full attention. 2) A-shape struggles with mid- context information even at 300 frames, while Tri-shape maintains full performance until 3.9k frames (i.g. 700K tokens) before sharp decline. 3) SF-fixed degrades 2.1k frames (i.g. 350K tokens), while SF-strided surpasses Tri- shape, holding performance until 4.5k frames (i.g. 825K tokens). 4) MInference preserves VLM retrieval well, with only slight degradation beyond 4.8K frames.
Fig. 7 and 16 present end-to-end and kernel-level latency across different context sizes. The grid pattern significantly outperforms the vertical-slash pattern in sparsity, achieving 2-3x speedup even 1M tokens. Additionally, the grid pattern achieves end-to-end speedup of 8.3x and kernel- level speedup of 12x.
4.6. Analysis
Transition of Sparse Patterns Across Modalities Since LLMs and VLMs exhibit different sparse patterns, we exam- ine the interplay between the Grid and Vertical-Slash pattern. As shown in Fig. 6, Llava-Video- 7B primarily uses Vertical- Slash pattern for purely textual inputs. However, once a visual input is appended, transitions to Grid pattern to
8

---

MMInference: Accelerating Pre-filling for Long-Context VLMs via -odality-Aware Permutation Sparse Attention
Table Performance (%) on video understanding tasks based on VideoChat- (Li et al., 2025) frames 512 with tokens.
VideoDC
ActNet-QA
EgoSchema
Next-QA
Perception
VideoMME
Model
Avg.
test
test
test
me
val
w/o sub.
w/ sub.
VidenChat-Flash
3.21
53.6
57.0
81.2
69.1
63.2
70.5
56.8
w/ MMInference
3.19
54.3
57.3
79.8
69.1
63.0
70.2
56.7
capture the geometric structure of the visual content. This struc-
5. Related Work
shift occurs at the modality boundary, creating tured arrangement of vertical and horizontal intervals. Such behavior highlights the need for distinct sparsity strategies in visual and mixed-modality contexts, rather than simply reusing sparse patterns from LLMs for VLMs.
Long-Context Vision Language Models Recent VLMs have extended their context length to support long multi- modal inputs (Zhang al., 2024a; Chen al., 2025; Wang et al., 2024b; Team et al., 2024), enabling applications such as long-video understanding (Fu et al., 2024; Xiao et al., 2021; Wang et al., 2024a; Bai et al., 2025), multi-modal retrieval (Zhang et al., 2024a), and multi-modal chain-of- thought reasoning (Qwen, 2024). For instance, Zhang et al. (2024a) transfer long-context capabilities from base I.I.Ms to vision tasks, Chen et al. (2025) introduce multi-modal sequence parallelism to accelerate video fine-tuning and Zhang et al. (2024b) emphasize the role of data calibration and synthetic data in boosting VLM performance.
0.9
0.8
Nltn
0.6
Indexing and Modality Region
Text Index on Text
0.5
Text Index Vision
Vision Index on Vision
10
Layer
Efficiency Optimization for VLMs While long-context VLMs achieve high accuracy, their high inference cost lim- its practical use in long-video scenarios. A common strategy is vision token compression lution by dropping or merging less important visual tokens (Bolya et al., 2023; Chen et al., 2024; Shen et al., 2024; He et al., 2024; Tu et al., 2025; Weng et al., 2024; Wen et al., 2024). RNN-Transformer hybrids are also used (Wang et al., 2024b) to balance efficiency and context length. However, these methods often assume inputs are long videos paired with short text, focusing solely on visual token optimization, while overlooking mixed-modality inputs critical for multi- turn interactions (Huang et al., 2024). Recently, Xu et al. (2025b) applied dynamic sparse attention to long-context VLMs, but their approach ignores modality-specifs induc- tive biases and is limited single-modality video tasks.
Figure 8: The sparse index does not effectively extrapolate from text to the visual modality. However, an index built within the same modality can generalize across modality boundaries.
video feature reso-
Sparse Index Across Modalities In Fig. 8, the sparse index achieves high recall for textual regions but fails to gen- eralize to visual ones. address this, we construct a sparse index from the visual modality and evaluate on separate visual segments, each separated by modality boundaries. Remarkably, this approach extrapolates effectively across all visual segments, even when interspersed with textual boundaries. As shown in Fig. 8, the sparse index achieves high recall in the textual but fails to generalize to the visual. To address this, we construct a sparse index using the visual modality and evaluate it across distinet regions of the visual modality, separated by modality boundaries. Remarkably, this approach successfully extrapolates to all visual regions even when interrupted by text-induced boundaries.
6. Conclusion
We propose MMInference, a modality-aware permutation sparse attention method that accelerates long-context VLMs. It features permutation bernutation-based grid sparse attention, Q- boundary/2D-boundee
Integrate with token compression methods As shown in Table 2, our method integrates seamlessly with token com- pression techniques, enabling near-lossless performance while supporting longer or higher-resolution video inputs. Specifically, VideoChat-Flash reduces tokens per frame from 196 to 16 at the ViT stage, while our method further applies sparse attention in the LLM decoder. Results demon- strate strong performance retention across benchmarks.
patterns for mixed-modality bound- aries, and Modality-Aware Sparse Attention Search Al- gorithm. Our optimized GPU kernels enable end-to-end acceleration. Experiments on video understanding tasks, V-NIAH and MM-NIAH using Llava-Vise Video and Long Vila demonstrate that MMInference preserves full-attention per- formance while achieving up to 8.3x speedup at 1M tokens.

---

MMInference: Accelerating Pre-filling for Long-Context VLMs via Modality-Aware Permutation Sparse Attention
Impact Statement
report. ArXiv preprint, abs/2407.10059, 2024, URL https:/ http:://aaxiv..rg//ee// /20.///.//2200..77555 10759.
This paper presents work whose goal to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
Dao, T. Flashattention-22 Faster attention with better paral-
lelism and work partitioning. ICLR, 2024.
Ding, H., Li, D., Su, R., Zhang, P., Deng. Z.,, Stoica, I., and Zhang, H. Efficient-vdit. Efficient video dif- fusion transformers with attention tile. arXiv preprint 25X2v:250..06/55, 2025.
References
Acharya, S., Jia, F., and Ginsburg, B. Star attention: Effi cient Ilm inference over long sequences. ArXiv preprint, abs/2411.17116, 2024. URL https: /ttp/xxxxxvv../////..... abs/2411.17112
Fu, C., Dai, Y., Luo, Y.. Li, L., Ren, S., Zhang, R., Wang, Z., Zhou, C., Shen, Y., Zhang, M., et al. Video-mme: The first-ever comprehensive evaluation benchmark of multi-modal Ilms in video analysis. ArXiv preprint, abs/2405.2 20075 2024. URL abs/ 0bs/2405.22 21075.
Bai, S., Chen, K., Liu, X., Wang. J., Ge, W., Song, S., Dang, K., Wang, P., Wang, S., Tang, J., et al. Qwen2. 5-vl
technical report. ArXiv preprint, abs/2502.1392.. 2025. URL http:: //apiii:///xxvvv.///a//aa org/ 2502 20t.://52....2.33... 13923.
Gao, S., Yang, J., Chen, L.,, Chitta, K., Qiu, Y., Geiger, A., Zhang, J., and Li, H. Vista: A generalizable driving world model with high fidelity and versatile controllabil- ity. In The Thirty- Anmual Conference on Neural Information Processing Systems, 2024. URL https: / //openreview net
Black, K., Nakamoto, M., Atreya, P., Walke, H. R., Finn, C., Kumar, A., and Levine, S. Zero-shot robotic manip- ulation with pre-trained image-editing diffusion models. In The Twelfth International Conference on Learning Representations, 2024. URL https:t/p//// / ope.reviee.ee..e fort/foru? www.ummiiiii 2id 1d-ccchhThhhi...
Hassani, A., Walton, S., Li, J., Li, S., and Shi, H. Neigh- borhood attention transformer. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 6185-6194, 2023.
Bolya, D., Fu, C.-Y., Dai, X., Zhang, P., Feichtenhofer, C., and Hoffman, J. Token merging: Your vit but faster. ICLR, 2023.
Cheang, C.-L., Chen, G., Jing, Y., Kong, T., Li, H., Li, Y., Liu, Y., Wu, H., Xu, J., Yang. Y., et al. Gr-2: A generative video-languugg-action model with web- scale knowledge for robot manipulation. ArXiv preprint, abs/2410.06158, 2024. URL https::///// /ttp/ia..vvvoo/////.. abbs/4100 06158.
He, Y., Chen, F, Liu, J., Shao, W., Zhou, H., Zhang, K., and Zhuang, B. Zipvl: Efficient large vision-languae models with dynamic token sparsification and kv cache com- pression. ArXiv preprint, abs/2410.08584 2024. URL https://arx:e org/ /0010/000000110008....
Hu, A., Russell, L., Yco, H., Murez, Z., Fedoseev, G., Kendall, A., Shotton, J., and Corrado, G. Gaia-1: A generative world model for autonomous driving. ArXiv preprint, abs/2309. 17080, 2023. URL https:// arxiv. wwx.iv.org/aaie www./ag.g///./ooooo///..../...ee attpaabb//33... 2209 2000..709..........
Chen, L., Zhao, H., Liu, T., Bai, S., Lin, J., Zhou, C., and Chang. B. An image is worth 1/2 tokens after layer 2: and--and-play inference acceleration for large vision- language models. ECCV, pp. 19-35, 2024. doi: 10.1007/ 978-3-031-73004-7 2.
Huang, M., Long, Y., Deng, X., Chu, R., Xiong, J., Liang, X., Cheng, H., Lu, Q., and Liu, W. Dialoggen: Multi- modal interactive dialogue system for multi-turn text-to- image generation. ArXiv preprint, wwt/aa//.///2///111 2024. URL
Chen, Y. Xue, F., Li, D., Hu, Q., Zhu, L., Li, X., Fang, Y., Tang, H., Yang. S., Liu, Z., He, Y., Yin, H., Molchanov, P.. Kautz, J. Fan, L., Zhu, Y., Lu, Y., and Han, S. VILA Scaling long-context visual language models for long videos. In The Thirteenth International Confer- ence on Learning Representations, 2025. URL https: //openreview. wet.iieww.eeeeeeeeeemmmem
http://aaxxiv..r//bba.a./. www/////aaaa...... 2203. 24000/0000. 08857.
Jiang, A. Q., Sablayrolles, A., Mensch, A., Bamford, C.,
Chaplot, D. S., Casas, D. d. I., Bressand, F., Lengyel, G., Lample, G., Saulnier, L., et al. Mistral 7b. ArXiv preprini, abs/2310.068255, 2023. URL https: aaxxiv.rgg/ bbss/2310.00
net serpenreeieew.nee/ooommiiiii www.:rrmmwiiiiiaaocccccacccoa.
Child, R., Gray, S., Radford, A., and Sutskever, I. Gener- ating long sequences with sparse transformers. ArXiv preprint, abs/1904. 10509, 2019. URL https:// arxiv. org. aas///b////// aataaass/..../ 10509.
Jiang, H., Li, Y., Zhang, C., Wu, Q. Luo, X., Ahn, S., Han, Z., Abdi, A. H., D., Lin, C.-Y., Yang, Y., and Qiu, L. MInference 1.0: Accelerating pre-filling for long- lontecontext L.Ms via dynamic sparse attention. In The Thihty-eighth
Chu, Y. Xu, J., Yang, Q. Wei, H., Wei, X., Guo, Z., Leng, Y., Lv, Y. He, J., Lin, J., et al. Qwen2-audio technical
10

---

MMInference: Accelerating Pre-filling for Long-Context VLMs via Modality-Aware Permutation Sparse Attention
Annual Conference on Neural Information Processing http:////eereeeeeeeeeeeee net./
Liu, Z., Lin, Y., Cao. Y., Hu, H., Wei, Y., Zhang, Z., Lin, S., and Guo, B. Swin transformer: Hierarchical vision transformer using shifted windows. ICCV, pp. 9992- 10002, 2021. doi: 10.1 10.109//CC44992.221100000
Systems, 2024. URL httpt:tt////c.
Forum?id-fPBACAN
Lab, L. Video detail caption, 2024.
URL
ht https://hhagingffc..o//aaaasss 1mms Lums-lab/ htt----aavviieeeeaaaaaaaeee
Lu, E., Jiang, Z.,, Liu, J., Du, Y., Jiang, T., Hong, C., Liu, S., He, W. Yuan, E., Wang, Y., et al. Moba: Mixture of block attention for long-context llms. arXiv preprint urXiv:2502.13/11 2025.
Lai, X., Lu, J., Luo, Y., Ma, Y., and Zhou, X. Flexpre- fill: A context-aware sparse attention mechanism for efficient long-sequence inference. In The Thirteenth International Conference on Learning Representations, n forum?
Maaz, M., Rasheed, H. A., Khan, S., and Khan, F. Video- chatgpt: Towards detailed video understanding via large vision and language models. ACL, pp. 12585-12602, 2024. doi: 10. 1C20A//I1O22AAALLLLLOOOO
2025. URL
id=OfjIlbelrf.
Li, X., Wang, Y., Yu, J., Zeng, X., Zhu, Y., Huang, H., Gao, J., Li, K., He, Y., Wang, C., et al. Videochat- flash: Hierarchical compression for long-context video modeling. ArXiv preprint, abx/2501.005//// 2025. URL https:/ / /aaiiviii.v wtw./bs/////ooooo.o.o..o....e.e/ 2501 2000./005400..
Mangalam, K., Akshulakov, R., and Malik, J. Egoschema: A diagnostic benchmark for very long-form video language understanding. NeurlPS, 2023.
Patraucean, V., Smaira, L., Gupta, A., Recasens, A., Mar- keeva, L., Banarse, D., Koppula, S., Heyward, J., Ma- linowski, M., Yang, Y., Doersch, C., Matejovicova, T., Sulsky, Y., Miech, A., Fréchette, A., Klimczak, H., Koster, R., Zhang. J., Winkler, S., Aytar, Y., Osindero, S., Damen, D., Zisserman, A., and Carreira, Perception test: A diagnostic benchmark for multimodal video models. NeurlPS, 2023.
Li, Y., Huang, Y., Yang, B., Venkitesh, B., Locatelli, A., Ye, H., Cai, T., Lewis, P., and Chen, D. SnapKV: LLM knows what you are looking for before genera- tion. In The Tiihty-eighth Annual Conference on Neural Information Processing Systems, 2024. URL https: //openrevien net/ forum? iinmnidd--i doiioddppss.om 5GG005
LI, Y., Jiang, H., Wu, Q., Luo, X., Ahn, S., Zhang, C., Abdi, A. H., Li, D., Gao, J., Yang. Y., and Qiu, L. SCBench: A KV cache-centric analysis of long-context methods. In The Thirteenth International Conference on Learning Representations, 2025, URL https: openreview. net/ Eorum? htt.iidggggkkyyyyueek
Patraucean, V., Smaira, L.,, Gupta, A., Recasens, A., Mar- keeva, L., Banarse, D., Koppula, S., Malinowski, M., Yang. Y., Doersch, C., et al. Perception test: A diagnostic benchmark for multimodal video models. Advances in Neural Information Processing Systems, 36, 2024.
Prasad, A., Lin, K., Wu, J., Zhou, L., and Bohg. J. Consis- tency policy: Accelerated visuomotor policies via consis- tency distillation. ArXiv preprint, abs/aa05 070550 2024. URL wwt.thtp://// httpps://arxiv..// www.aiwww.w..aaaa..a..a.oeeeeeaa aabe////////// w20.aa////22.... 07503.
Li, Y., Liu, J., Zhang. T., Chen, S., Li, T., Li, Z., Liu, L., Ming, L., Dong, G., Pan, D., et al. Baichuan-omni-1.5 technical report. ArXiv preprint, abs/2501.15366 2025.
URL https::tp/// / //ax/vivi...////vv///a//////aavv www.v.oorrr abs/ 15368.
Qwen, T. Dao, ui and haziza, daniel and massa, francisco and sizov, grigory, 2023.
Liu, D., Chen, M., Lu, B., Jiang, H., Han, Z., Zhang, Q., Chen, Q. Zhang, C., Ding, B., Zhang, K., et al. Re- trievalattention: Accelerating long-context IIm inference via vector retrieval. ArXiv preprint, abs/2409. 10516, 2024a. URL https: httpp:://axxi....// wwtp:///g/aab///////// 10516.
URL
https:// //cp::////...../ 12/flashdecod seredeeooiigggg html.
Qwen, T. Qvq: To see the world with wisdom, 2024. WtLLhtsss//qwent http///wee...g.uu.bbb.... github.i./ble.. io/blog/ qvq 72b bebb--preieww..
Liu, L.. Qu, Z., Chen, Z., Tu, F., Ding. Y., and Xie, Y. Dynamic sparse attention for scalable transformer accel- eration. IEEE Trans. Computers, pp. 3165-3178, 2022. doi: 10. 00.1109/TC.2022.320022
Ribar, L., Chelombiev, L., Hudlass-Galley, L.. Blake, C., Luschi, C., and Orr, D. Sparq attention: Bandwidth- efficient I1m inference. ICML, 2024.
Liu, L., Yang, X., Lei, J., Liu, X., Shen, Y., Zhang, Z., Wei, P., Gu, J., Chu, Z., Qin, Z., et al. A survey medical large language models: Technology, application, trustworthiness, and future directions. ArXiv preprint, abs/2406.03712. 2024b. URL /tttttpss////......// //aaxiivvv..////// orrg/ abs/2406. 03712.
Shen, X., Xiong, Y., Zhao, C., Wu, L., Chen, J., Zhu, C., Liu, Z., Xiao, F. Varadarajan, B., Bordes, F., et al. Longvu: Spatiotemporal adaptive compression for long video-language understanding. ArXiv preprint, abs/2410.174344 2024. URL https: hattts:///rxiist //araaa.v..////////////////aaav. .xxiv.org/ abs/2410.1744

---

MMInference: Accelerating Pre-filling for Long-Context VLMs via -odality-Aware Permutation Sparse Attention
Team, G., Georgiev, P., Lei, V. I,, Burnell, R., Bai, L., Gulati, A., Tanzer, G., Vincent, D., Pan, Z., Wang, S., et al. Gemini 1.5: Unlocking multimodal understanding across millions of tokens of context. ArXiv preprint, abs/2403.05530,, 2024. URL htwps:ttt////e.ttm hatp::///axxv.org// abs/2403. 05530.
Xiao, G., Tian, Y., Chen, B., Han, S., and Lewis, M. Ef- ficient streaming language models with attention sinks. ICLR, 2024.
Xiao, J., Shang, X., Yao, A., and Chua, T.-S. Next-qa: Next phase of question-answeriig to explaining temporal actions. CVPR, pp. 9777-9786, 2021. doi: 10.1109/ CVPR46433.2021.00000
Tillet, P., Kung, H.-T., and Cox, D. Triton: an intermediate language and compiler for tiled neural network computa- tions. In Proceedings of the 3rd ACM SIGPLAN Interna- tional Workshop on Machine Learning and Programming Languages, pp. 10-19, 2019.
Xu, J., Guo, Z., He, J., Hu, H., He, T., Bai, S., Chen, K., Wang, J., Fan, Y., Dang, K., et al. Qwen2. 5-omni techni- cal report. ArXiv preprint, abs/2503.20215. 2025a. URL https: aariiv .awiivoorg/aaaa wwt.:oogggaaaaaaeeee 20215..
Tu. D., Vashchilenko, D., Lu, Y., and Xu, P. VL-cache: Sparsity and mowa KV cache compression for vision-language model inference acceleration. In The Thirteenth International Conference Learning Rep- resentations, 2025. URL / //pp///pppee...ee///ee/e. fert/oorm?? ? i d1 HM.HHMMMUUUUUU.
Xu, R., Xiao, G., Huang, H., Guo, J., and Han, S. Xat- tention: Block sparse attention with antidiagonal scor- ing. ArXiv preprint, abs/2503.16428, 2025b. URL https:/
/al:://rraa http//aaxivv....////v///../...aa www.vvorrr//aoo org/ attaab///5553 16428.
Yang. S., Chen, Y., Tian, Z., Wang, C., Li, J., Yu, B., and Jia, J. Visionzip: Longer better but not necessary vision language models. ArXiv preprint, abs/2412.04467,, 2024. URL https: arxiv org/ abs 2212. 04467.
Wang, P., Bai, S., Tan, S., Wang, S., Fan, Z., Bai, J., Chen, K., Liu, X., Wang, J., Ge, W., et al. Qwen2-vl: Enhancing lision-language model's perception of the world at any resolution. ArXiv preprint, abs/2409. 12191, 2024a. URL https:/ //axxiv. org/ abs/ 209.2449...0 12191.
Yu, Z., Xu, D., Yu, J., Yu, T., Zhao, Z., Zhuang, Y., and Tao, D. Activitynet- A dataset for understanding complex web videos via question answering. AAAI pp. 9127-9134, 2019. doi: 10.1609//ALL V13000131110300000111909993
Wang, X., Song, D., Chen, S., Zhang, C., and Wang, B. Longllava: Scaling multi-modal llms to 1000 images efficiently via hybrid architecture. ArXiv preprint, abs/2409.02889, 2024b. hRtpstts:///aa org// abs/2409. 02889.
Yuan, J., Gao, H., Dai, D., Luo, J., Zhao, L., Zhang, Z., Xie, Z., Wei, Y., Wang, L.., Xiao, Z., et al. Native sparse and natively trainable sparse attention. arXiv preprint arXiv:2502.1 1089, 2025.
attention: Hardware-aligge
Wang, X., Zhu, Z., Huang, G., Chen, X., Zhu, J., and Lu, J. Drivedreamer: Towards worl-dved world models for autonomous driving. In European Conference on Computer Vision, pp. 55-72. Springer, 2024c.
Zhang, P., Zhang, K., Li, B., Zeng. G., Yang, J., Zhang, Y., Wang, Z., Tan, H., Li, C., and Liu, Z. Long con- text transfer from language to vision. ArXiv preprint, abs/2406. 16852, 2024a. URL httpst/:: hatss///xxxvvoorr abs/
Wen, Y.. Cao, Q. Fu, Q., Mehta, S., and Najibi, M. Efficient vision-language models by summarizing vi- sual tokens into compact registers. ArXiv preprint, abs/2410.14072,, 2024. URL https://arxiv.. abs/2410. 14072.
Zhang, P., Chen, Y., Su, R., Ding, H., Stoica, I., Liu, Z.., and Zhang, H. Fast video generation with sliding tile attention. arXiv preprint arXiv:2502.04507, 2025.
Weng, Y., Han, M., He, H., Chang, X., and Zhuang, B. Longvlm: Efficient long video understanding via large language models. ECCV, pp. 453 2024. doi: 10.
Zhang, Y., Wu, J., Li, W., Li, B., Ma, Z., Liu, Z., and Li, C. Video instruction tuning with synthetic data. ArXiv preprint, abs/2410.02713,, 2024b. URL https: / //arxiv. org abs//bs/21112
1007/978-3-031-734144412
Wu, W., Wang, Y., Xiao, G., Peng, H., and Fu, Y. Retrieval head mechanistically explains long-conted factuality. In The Thirleenth International Conference on Learning Representations, 2025, http:: http///eeeeeeeeeeeee/eeeee net/forunt forum? i BdyBtBBBUUBB...........
Zheng, N., Jiang, H., Zhang, Q., Han, Z., Ma, L., Yang. Y., Yang, F., Zhang, C., Qiu, L., Yang, M., et al. Pit: Optimization of dynamic sparse deep learning models via permutation invariant transformation. In Proceedings of the 29th Symposium Operating Systems Principles, pp. 331-347 2023.
Xi, H., Yang. S., Zhao, Y., Xu, Li, Lin, Y., Cai, H., Zhang, J., Li, D., et al. Sparse videogen: Acceler- ating video diffusion transformers with sparsity. arXiv preprint arXiv:2502.01776, 2025.
12

---

MMInference: Accelerating Pre-filling for Long-Context VLMs via Modality-Aware Permutation Sparse Attention
A. Modality-Aware Sparse Attention Search Algorithm
In Algorithm 4, we detail the procedure for selecting the optimal sparse attention pattern for each attention head under constrained FLOPs budget. The algorithm jointly determines the best pattern and its configuration (e.g., stride size in grid attention, number of vertical/slash lines in VS pattern) to maximize accuracy. We first construct kernel-aware search space, where all candidate patterns have comparable real-world FLOPs based GPU kernel measurements- than theoretical estimates-to ensure practical efficiency.
We then evaluate each candidate using reference example and select the configuration that maximizes attention re- call, using the actual attention output as the objective. This recall-based scoring incorporates the V matrix and builds on Fttenttt (Dao, 2024), enabling end-to-end pattern selection with minimal memory overhead and improved performance.
Algorithm Modality-aware Sparse Attention Pattern Search
Input: K, E RSxd, inter-modality search space Pinter, intra- modality search space Pintra, modality type set m E Qm. optimized sparse pattern P
# Intra-modality sparse attention pattern search
for i + 1 to p0ml do
Pmi +- P 4- Pumi
(Q, K, V, .m:)
end for
# Cross-modality sparse attention pattern search for i + ddml |0ml for j 4- to [@ml
Pmi.m. & Kernel (Q. K, V, m,m, mj) P Pmimmmm
end for end for
# Inter-modality sparse attention pattern search for to Panter do P: f argmin (Isparse Q, 2 K, Vi attention Q K, V) P PUPu end for return
(a) K- B-Bonddary pattern.
(b) No-Boundary pattern.
Figure 9: Additional inter-mode titrr-todaltty sparse pattern.
13

---

MMInference: Accelerating Pre-filling for Long-Context VLMs via Modality-Aware Permutation Sparse Attention
Local Keeen Toxen
Inter
Inter
(a) A-shape
(b) SF-fixed
(c) SF-strided
Local Todken
Vertical
Slash
Bottom Taken
(d) Tri-shape
(e) Vertical-Slase (Minference)
Figure 10: The basclines of sparse attention in our experiments.
B. Pattern Analysis
B.1. Additional Mix-modality Pattern
In $2, explain how the grid pattern naturally arises from the geometric structure of vision inputs. Fig. 9 further illustrates two additional patterns in the mixed-modality search space: the K- K-Boundary and No-Boundary patterns. Notably, both patterns incur no additional cost compared to pure intra-modality attention, as their sparse indices can be computed across all rows without extra computation.
B.2. Additional Sparse Attention Pattern Visualization
We further analyze the sparse patterns in Qwen2.5-VL (Wang et al., 2024a) with dynamic resolution inputs and in VideoChat- Flash (Li et al., 2025) under visual token compression, across both video benchmark and mixed modality inputs, as shown Fig. and Fig.
mixed-modality
C. Experiment Details
C.1. Vision Language Models
We use two state-of-the-art VLMMs in our experiments: Long VILA (Chen et al., 2025) and Llava-Video (Zhang et al., 2024b). Llava-Video supports varying numbers of frames (32, 64, 110) for video understanding, and as reported, performance improves with more frames. Thus, we adopt the 110-frame variant for benchmarking. For LongVILA, we use the 256-frame version SeeeVVLA-256Frammm with 128K context length for video understanding benchmarks, and the IM-token version (LongVILA-1NM 1M), designed for retrieval tasks, for the V-NIAH evaluation.
14

---

MMInference: Accelerating Pre-filling for Long-Context VLMs via -odality-Aware Permutation Sparse Attention
Table 3: Hyperparameteess detail of baselines.
Method
Hyperparameters
A-shape
Sink 128, Local 4096
SF-fixed
Local token per frame, vline..trrie token pelken-perrree frame
SF-strided
Local = token-per framme vline-stride token-per frame
Tri-shape
Sink = 128, Local = 4096, Bottom = 128
MInference
Vertical.size E {1000, 2000, 40000,, Slash_size {1024, 2048, 4096, 6144)
VisionZip
dominant = 54, contextual = 10
C.2. Baselines
We include five sparse attention baselines in our experiments: A-shape (Xiao et al., 2024), SF-fixed (Child al., 2019), SF-strided (Child al., 2019), Tripshape (LI et al., 2025), MInference (Jiang al., 2024), and VisionZip (Yang et al., 2024). Fig. 10 illustrates the attention patterns of these baselines.
While VisionZip (Yang et al., 2024) is primarily visual token compression method-commpresing vision tokens using attention scores from the vision encoder before passing them to the LLM-it is included for comparison as reduces FLOPs the pre-filling stage and offers insight into token compression approaches.
C.3. A-shape and Vertical-Slash
A-shape and Vertical-Slash are used for intra-modality attention, alongside our newly proposed Grid pattern.
At inference time, we estimate the attention matrix online dynamically determine the spatial layout of sparse indices, conditioned on the assigned pattern and actual input. Sparse attention is then computed using our optimized GPU kernels. Note that while the masks for Vertical-Slate and Grid patterns dynamically generated, A-shape uses static mask, incurring no additional overhead beyond sparse computation.
A-shape head. A-shape is static sparse pattern that includes the first seven initial tokens along with a local attention window.
Vertical-Sland head. Due the continuity of vertical and slash lines, we matmul the last query vector Q Q[ and key vector K produce the estimated attention matrix A, which, in turn, is used to determine the indices for the vertical i, and slash i, lines. After obtaining the sparse indices for the vertical and slash lines, we convert them into sparse format i Using these sparse indices, we perform block-sparse calculations of the attention weights and attention output.
C.4. Permutation for the Grid Pattern and Across Modality
We illustrate how the permutation is applied to the Grid pattern and the Q-boundary and 2D-boundary patterns in Fig. 11 and Fig. 11.
(a) Before Permutation
Row-wise Permutation
(c) Column- wine Permutation
Figure 11: Permutation for the Grid Pattern. (a) Before permutation. (b) Row-wise permutation. (c) Column-wise permutation.
15

---

MMInference: Accelerating Pre-filling for Long-Context VLMs via Modality-Awanl Permutation Sparse Attention
(a) Mix-modality
(b) Q-wise Permutation
(c) K-wise Permutation
Figure 12: Permutation for mix-modality context. (a) Mix-modality, (b) Q-wise permutation. (c) K-wise permutation.
C.5. Search Space
Following (Jiang et al., 2024), set the target FLOPs to be the same 1 global tokens and 4k local window tokens in the A-shape pattern. Additionally, we use only one sample 25K tokens, which exhibits strong generalization and stability across different lengths and domains. The search time is approximately 15 minutes on a single A 100.. This pattern search is individually conducted for each model: Llava- Video-7B, LongVila-256Frre and Long Vila-illaMMMa The search space is shown in Table 4.
calibration set from the egoschema task with more than
D. Benchmark Details
We evaluate our method on several video understanding benchmarks that test different aspects of video comprehension:
EgoSchema EgoSchema (Mangalam al., 2023) is diagnostic benchmark for very long-form video language under- standing, structured as multiple-choice question answering task. The benchmark requires models to answer questions about egocentric videos by selecting from given options (labeled A through E). The evaluation can be performed either on the full set via submission to an evaluation server, or on a released subset of 500 questions for direct scoring.
Video-MME Video-MME (Fu et al., 2024) is a comprehensive multi-modal evaluation benchmark that tests MLLMs across diverse video types and temporal dimensions. spans primary visual domains with 30 subfields and includes videos ranging from 11 seconds to 1 hour duration. The benehmark comprises 900 videos totaling 254 hours, with 2,700 manually annotated question-answer pairs. It evaluates models' ability process not just video frames but also integrated multi-modal inputs like subtitles and audio.
NEXT-QA NExT-QA (Xiao et al., 2021) focuses advancing video understanding from basic description to explaining temporal actions. It features both multiple-chor and open-ended QA tasks that target three key aspects: causal action reasoning, temporal action reasoning, and common scene comprehension. The benchmark is specifically designed to evaluate models' ability to reason about actions beyond superficial scene descriptions.
Perception Test The Perception Test (Patraucean et al., 2023) perce evaluates perception and reasoning skills across video, audio, and text modalities. contains 11.6k real-world videos with an average length of 23 seconds, featuring perceptually interesting situations. The benchmark tests four key skills (Memory, Abstraction, Physics, Semanties) and various types of reasoning (descriptive, explanatory, predictive, counterfactual). Videos densely annotated with six types of labels: multiple-choice QA, grounded video QA, object tracks, point tracks, temporal action segments, and sound segments.
ActivityYet-QQ ActivityNet-QA (Yu et al., 2019) is large-scale VideoQA dataset consisting of 58,000 QA pairs on 5,800 complex web videos derived from the ActivityNet dataset. The benchmark is fully annotated and designed to test models' understanding of complex web videos through question answering. Unlike automatically generated datasets, ActivityNet-QU QA features numan-annotated questions and answers, making it particularly valuable for evaluating real-world video understanding capabilities.
16

---

MMInference: Accelerating Pre-filling for Long-Context VLMs via Modality-Aware Permutation Sparse Attention
Attention Type
Parameters
(frame_stride, True, False, False, 1024)
(frame_stride, False, True, False, 1024)
(frame stride, False, False, True, 1024)
(frame_stride, True, True, False, 1024)
(frame-stride, False, True, True, 1024)
(frame_stride, True, True, True, 1024)
Grid Attention
(stride, True, False, False, 1024)
(stride, False, True, False, 1024)
(stride, False, False. True, 1024)
(stride, True, True, False, 1024)
(stride, False, True, True, 1024)
(stride, True, True. True, 1024)
(128, 1024)
A-shape
(128, 2048)
(128, 4096)
(1000, 1024)
(1000, 2048)
(2000, 2048)
(1000, 3096)
(2000, 3096)
Vertical-Slash
(1000, 4096)
(2000, 4096)
(3500, 200)
(1000, 2500)
Tahle 4: The search space for each attention pattern: 1) Grid Attention: (stride, use hline, use vline, use slash, max stride); 2) A-shape:
(sink, local): 3) Vertical Vertical-Slash: Slash: (vertical size, slash size)
Video Detail Description (VideoDC) VideoDC (Lab, 2024) focuses on comprehensive video understanding through detailed descriptions. The benchmark consists of question-answer pairs generated with GPT-3.5, where questions prompt for detailed descriptions focusing main subjects, their actions, and background scenes. The evaluation assesses the quality and completeness of video descriptions generated by models.
E. Additional Experiments Results
E.1. Additional Video Needle A Haystack Results
we further present the results of the Video Needle A Haystack task with our baselines. The results of our method and full atttenton shown in Fig. 5.
E.2. Additional Mixed-Modalin Needle In A Haystack Results
We further present the results the Mixed-Modality Ncedle A Haystack task with our basclines and the inter-modality variant of our method. The results full atttenton and MMInference are shown in Fig. 5.
E.3. Latency Breakdown
As shown in Fig. 16, we present the hicro-benchmark results of various sparse attention methods across different context lengths.
17

---

MMInference: Accelerating Pre-filling for Long-Context VLMS via Modality-Aware Permutation Sparse Attention
LongVILA-1M w/ A-shape in VNIAH Recall 44.0%
LongVILA-1M w/ Tri-shape in VNIAH Recall 85.7%
1.0
Depth Percent()6)
20
00.8
Depth Percent(55)
20
0.8
40
0.6
0.6
60
-0.4
60
0044
80
80
0.2
0.0
-.00
300
600
48k
5.1k
5.4k
5.7k
6.0k
300
600
900
4.0K
5.1k
5.4k
5.7k
6.0k
Num. of Frames
Num. of Frames
(a) A-shape
(b) Tri-shape
LongVILA-1M w/ SF-fixed in VNIAH Recall 59.3%
LongVILA-1M w/ SF-strided VNIAH Recall 90.7%
1.0
1.0
Depth Percent(%6)
Depth Percente)))
40
40
60
00.4
0.4
0.2
0.2
100
100
300
500
900
300
600
900
Num. of Frames
Num. of Frames
(c) SF-fixed
(d) SF-strided
LongVILA-1M w/ Minference in VNIAH Recall 96.7%
Depth Percent(%)
-088
20
0.6
00.4
80
-0.0
300
600
900
12k
6.9k
Num. of Frames
(c) MInference
Figure Video Needle Haystack (Zhang et al., 2024a) results using Long Vila- Qwen2-7B-IM (Chen al., 2025).
E.4. VS Pattern vs. Grid Pattern
Both VS pattern and Grid pattern achieve strong performance video understanding and V-NIAH tasks. However, due to the grid attention pattern observed in VLMs, the overlap between blocks covered by diagonal lines in the VS pattern is minimal, reducing sparsity within the kernel. This explains why VS pattern exhibits significantly higher latency compared to Grid pattern. Additionally, leveraging permutation-bast optimization effectively reduces the number of blocks involved kernel computation, thereby lowering latency while maintaining comparable performance.
F. Sparse Attention in DiT
Recently, many efficient DIT methods (Hassani et al., 2023; Xi et al., 2025; Zhang et al., 2025; Xu et al., 2025b; Ding et al., 2025) have adopted sparse attention to accelerate long video generation. We note that these methods can also benefit from permutation- window attention in NATTEN can be converted into dense tensor core computation via permutation, as illustrated in Fig. 15. Similarly, the temporal head in Sparse VideoGen (Xi et al., 2025) and the anti-diagonal structure in Attention (Xu et al.,
transformations to achieve kernel-efficient implementations. For example, the 2D/3D sliding
18

---

MMInference: Accelerating Pre-filling for Long-Context VLMs via Modality-Aware Permutation Sparse Attention
LongVILA-1M w/ A-shape in MMNIAH Recall 43.3%
LongVILA-1M w/ Tri-shape in MMNIAH Recall 73.8%
Depth Percent()))
20
0.88
Depth Percent(%)
20
0.8
40
0.6
40
0.6
60
-0.4
0.491
80
80
-..0
300
690
900
3,nk
3,9k
4.2k
4.5
300
600
900
12k
15k
3.3k
3.8%
3.9k
4.2%
4.5k
Num. of Frames
Num. of Frames
(a) A-shape
(b) Tri-shape
LongVILA-1M Minference MMNIAH Recall 88.0%
LongViLA-1M MMInference w/o Inter in MMNIAH Recall 88.0%
1.0
1.0
Depth Percent(%))
Depth Percent(%)
20
0.8
40-
-0.6
0066
-0.4
-0.4
0.2
80
-0.2
100
100
300
600
900
3.98
6.2K
4.5k
300
600
200
1.2
3,34
3.6k
4.5K
Num. of Frames
Num. Frames
(c) MInference
(d) MMInference w/o Inter-modality
Figure 14: Mixed-Modality Needle In A Haystack results using Long VongViila--wee277B--. (Chen et al., 2025).
2025b) can be restructured through permutation to enable sparse loading with dense computation, significantly speeding up DiT inference, especially in long-context scenarios.
G. Kernel Implementation
As shown in Algorithms 5, 6, and provide implementation details of the FlashAttention-baasee kernels. The Grid-shape kernel in Algorithm 5 integrates block-sparse FlashDecoding (Qwen, 2023), which sparsifies the query loading, with block-sparse FlashAttention-2. which sparsifies the key loading. The Q-Boundary kemel in Algorithm 6 introduces sparsity
200
200
400
600
600
800
800
1000
1000
250
500
750
1000
250
500
750
1000
(a) Natten
(b) Permutated Natten
Figure Permutation- bassd implementation 2D/3D sliding window attention (Hassani al., 2023) enables efficient sparse attention optimization DiT architectures.
19

---

MMInference: Accelerating Pre-filling for Long-Context VLMs via -odality-Aware Permutation Sparse Attention
A-shape
NNN
Tri-sapee
Vertical-Slash
FlashAttention-2
Zizz
Grid
4000
2000
80
60
Latency
40
20
R
16K
32K
64K
128K
256K
512K
1M
Context Windows
Figure 16: The latency breakdown single attention kernel for four sparse attention patterns and Flash Attention (Dao, 2024) across different context windows in single A A100, including the index time for dynamic sparse approximation and huilding dynamic sparsity. At IM tokens, the latency for Grid is 358ms.
along the query dimension using FlashAttention-22 (Dao, 2024), while the 2D-Boundary kernel in Algorithm 7 applies sparsity along both the query and key dimensions.
Algorithm 5 Grid-Shapp Shape Flash Attention
Input: Q, K, E Sxds, block size B, stride size a, query start index Sq. key start index $
# Sparse load in K using FlashAttention
for i <- 1 to N do
Load Qchip + Q (ixx:((+))xBB B] E Bxdx
Scale
/ dh
Initialize O + (0) Bx) E BBxd,
Initialize O O (0) Sxda. Sxdx
Initialize
(- inf) B E B
Parallelized GPU
Initialize (0) R
Sparse load Q using FlashDecoding
# Loop K for to M, do
for i <- to N. do
Load Qcipp Q -it QixxB((++))x)xxttt E Bxda
Load Kehip +- k E E Bx
Initialize O + (0) (0)Rxd, E Bxds
Load Vaup < vbxx:((++))xxx)xxoosss E R Bxd,
Initialize m - (- inf) B E E
Initialize 1 < (0)* 8 E R.a
t QQ 2mp
< mask((S)
# Loop K
m max(m² max(mm, rowmax(8)) g
for +- 1 to M do
< minew
Load Kahip +- KD K(XB.(+D e 8xd,
P + exp(S)
Load Vesp + vbx E g Bxd,
I rowsum S))
S - Qchip KTT
f- exp(m' -)new)
S < mask S))
+ al' + lheew
m + max(m", rowmax(S)) E R miew
O + a + PVatip
end for
P exp(S)
Write outputs
1 <- rowsumn S))
O + diag(l') -0
+- exp(m' mi.w)
Save O; O
1 + al' Di
end for
O ~0 + PVaip
end for
Write outputs
O t- diag(!') ( Ohiip
Save O, + O
end for
20

---

MMInference: Accelerating Pre-filling for Long-Context VLMs via Modality-Aware Permutation Sparse Attention
Algorithm 6 Q-Boundary Flash Attention
Algorithm 7 2D--Boundary Flash Attention
Input: Q, V E _8xds block size B, modality index I. sparse attention kernel Opm.
Input: Q, K, V &Rd,, block size B, modality index Im sparse attention kernel Op..
Scale du
Scale
V 1
dn
Initialize - Sxd Rxdd
(x) E Sxd Initialize O f- +
Loop modality and parallelized in GPU for m ttext, vision, } do for i + to Nm do
# Loop modality and parallelized GPU for my E {text, vision, ...y do for i + 1 to Nm. do
Load index Ichip I [xxB((+))xBB R
Load index Tchip.q f [ex (ix:((xA)X)))
E RR"
m.
Load Cchip Q ap IR Bxds
Load Qchip +- Q Qlai.i
Bxd,
Initialize Chipp +- (0) Bxdn Bxd,
Initialize Chiip -- (0) Bxdn E R Bxd,
Initialize m < (- inf)* R
Initialize m + (- inf) E R
Initialize 1 - (0) E RB
Initialize (0) B R
Loop K using modality sparse attention
# Loop in K and modality for {text, vision, ...y do
O chipp m, 1 + Op... chip, K, V, Otip: m. I)
Write outputs modality index
for j < Mm., do
O chip &- d auup
Load index Lenip.k m.k
1bxB(++) B
Save O Jai +- Otipp
Load Kahip c K Laip Bxd,
end for
Load Vetip f- Vdipi, R Bxda
end for
Ochip: m. Op,, Qutip Ketips Vatp: Ochip: m.
end for
end for
Write outputs w/ modality index
Ochip d -'0 cap
Save O ddip. + O
end for end for
21

---

MMInference: Accelerating Pre-filling for Long-Context VLMs via Modality-Awars Permutation Sparse Attention
(a) Qwen2.5-VL on EgoSchema
(b) VideoChat EgoSchema
(c) Qwen2.5 VL on VideoMME
(d) VideoChat VideoMME
Figure 17: Visualization sparse attention patterns in Qwen2.5-VI. with dynamic resolution input and VideoChat-Flan with visual token compression across different benchmarks.
22

---

MMInference: Accelerating Pre-filling for Long-Context VLMs via Modality- AAaae Permutation Sparse Attention
(a) Qwen2.5-VE Mix-modality
(b) VideoChat on Mix Mix-modality
Figure 18: Visualization of sparse attention patterns in Qwen2.5-VT. with dynamic resolution input and FidsoChat-Flash with visual token compression with mix- modality inputs.
23


Reviews:
[{"review_id": "ZBkmweftKe", "reviewer": "Reviewer_Cdw6", "summary": "MAPSparse provides an innovative and effective solution for accelerating the pre-filling stage of long-context VLMs.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We greatly appreciate the reviewer’s thoughtful and constructive feedback. We respond to each of the comments and concerns below.\n\n1. ***\"Generalization of the patterns\"***\n\nWe evaluate our method across a broad range of multimodal tasks and VLMs, including open-domain question answering, multiple-choice question answering, video captioning, and video information retrieval. The models tested include Llava-Video and LongVILA, and our method consistently demonstrates strong performance across all these scenarios.\n\nWe additionally provide pattern analysis (shown in https://anonymous.4open.science/r/complementary-D5B2/) and experimental results (RTable.1) on the latest VLMs, Qwen2.5-VL [1] and VideoChat-Flash [2], further demonstrating the generalizability of both the observed patterns and our method across different models and tasks.\n\n2. ***\"Patterns in ViT\"***\n\nOptimizing tokens in ViT can help reduce prefilling latency, but ViT is not the primary bottleneck in long video processing for VLMs. As shown in Figure 1(a), ViT accounts for less than 2% of the total latency, while attention operations in VLMs dominate with over 95%. Nevertheless, MAPSparse is orthogonal to ViT optimization techniques such as VisionZip (shown in Table 1) and VideoChat-Flash [2]. We include an additional experiment based on VideoChat-Flash, and the results indicate that MAPSparse integrates well with token compression methods.\n\n| Model | VideoDC | ActNet-QA | EgoSchema | Next-QA | PerceptionTest | VideoMME (w/o sub) | VideoMME (w/ sub) | Avg. |\n|-|-|-|-|-|-|-|-|-|\n| VideoChat-Flash | 3.21 | 53.6 | 57.0 | 81.2 | 69.1 | 63.2 | 70.5 | 56.8 |\n| w/ MAPSparse | 3.19 | 54.3 | 57.3 | 79.8 | 69.1 | 63.0 | 70.2 | 56.7 |\n\nRTable 1. Performance of different methods on video understanding tasks using VideoChat-Flash.\n\n3. ***\"Generalization to other modalities\"***\n\nThank you for the suggestion. We conducted additional experiments on the text-only long-context benchmark SCBench [3], comparing MAPSparse with full attention, as shown in RTable 2. The results demonstrate that MAPSparse generalizes well across modalities and tasks. We will include the corresponding results in the next version.\n\n| Method | Retr.kv | En.Sum | En.QA | En.MC | ICL | Avg. |\n| - | - | - | - | - | - | - |\n| Full Attention | 52.0 | 38.3 | 25.1 | 65.9 | 54.1 | 47.1 |\n| MAPSparse | 47.0 | 36.6 | 23.6 | 62.6 | 62.9 | 46.5 |\n\nRTable 2. Performance of different methods on long-context benchmark SCBench using Llama-3.1-8B in 128K.\n\n4. ***\"Impact Statement\"***\n\nWe apologize for the misunderstanding. We followed the ICML [4] guidelines when writing the impact statement. Since our method does not alter the original VLMs outputs, it does not introduce any additional risks.\n\n[1] Qwen2.5-VL Technical Report, 2024.  \n[2] VideoChat-Flash: Hierarchical Compression for Long-Context Video Modeling, 2024.  \n[3] SCBench: A KV Cache-Centric Analysis of Long-Context Methods, ICLR 2025.  \n[4] https://icml.cc/Conferences/2025/CallForPapers", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "N/A", "experimental_designs_or_analyses": "Yes.", "relation_to_broader_scientific_literature": "N/A", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "### Strengths\n\n1. **Innovative Approach**: The paper introduces MAPSparse, a method that accelerates the pre-filling stage of long-context Vision-Language Models (VLMs) using Modality-Aware Permutation Sparse Attention. This approach significantly improves processing speed, achieving up to 8.3x and 1.7x speedups in a 1M-length context, surpassing FlashAttention-2 and MInference, respectively.\n\n2. **Integration of Theory and Practice**: The paper provides a detailed analysis of different attention head patterns (such as No-Boundary, K-Boundary, Q-Boundary, and 2D-Boundary) and introduces a modality-aware sparse attention search algorithm to optimize cross-modal and intra-modal sparse patterns. These improvements are not only theoretical breakthroughs but also show excellent performance in practical applications.\n\n3. **Comprehensive Experimental Validation**: The research utilizes two state-of-the-art long-context VLMs (Llava-Video and LongVila) and tests them on various video understanding tasks, including video captioning, video question answering, and video information retrieval. Additionally, a mixed-modal \"needle in a haystack\" task was designed to evaluate multimodal input performance, demonstrating that the method significantly enhances efficiency while maintaining high accuracy.\n\n4. **Strong Adaptability**: MAPSparse effectively addresses boundary issues between different modalities and maintains the continuity of sparse distribution across modalities, supporting more complex scenarios and larger datasets.\n\n### Weaknesses\n\n1. **Generalization ability of the method**: Although MAPSparse shows significant performance improvements, its algorithm implementation requires offline searching the optimal sparse patterns for each head. The authors did not show any experiments of the generalization ability of these patterns across datasets.\n\n2. **Generalization of the patterns to ViT**. All MLLM contains a ViT before feeding into LLM. Although it contributes little to the latency, but it decides how many tokens are fed into LLM. Will optimizing tokens in ViT better reduce the prefilling latency?\n\n3. **Specific Application Scenarios**: The paper primarily focuses on applications in video understanding and multimodal learning. Its applicability and effectiveness for other types of data or tasks, such as pure text or non-visual modalities, have yet to be fully explored.\n\n4. **Impact Statement**: \"There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.\" Maybe the authors could expand more.", "other_comments_or_suggestions": "See weakness.", "questions_for_authors": "See weakness.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "snXBFqDmCH", "reviewer": "Reviewer_NqbK", "summary": "This proposes a modality-aware permutation sparse attention method that accelerates long-context VLMs, called MAPSparse. It features permutation-based grid sparse attention, Q\u0002boundary/2D-boundary patterns for mixed-modality bound\u0002aries, and a Modality-Aware Sparse Attention Search Algorithm. Experiments prove the effectiveness.\n\n### Update After Rebuttal\nI'd like to thank the authors for the clear rebuttal, which solves most of my concern. Therefore, I maintain the original rating towards acceptance.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We greatly appreciate the reviewer’s thoughtful and constructive feedback. We respond to each of the comments and concerns below.\n\n1. ***\"it's better to report average latency and memory consumption in Table 1\"***\n\nThank you for the suggestion. We have updated Table 1 to include a dedicated column for end-to-end latency. Regarding memory usage, since all baselines consume similar memory except for VisionZip, we did not include a separate memory column. Below, we provide a table comparing the latency and average performance of MAPSparse with other baselines. The number of frames is fixed at 256, and all tests are conducted on a single A100 GPU.\nAs shown in Section 4.5, our method achieves greater speedup with longer video inputs and more frames.\n\n| Method | Prefill Latency (s) | Avg. Performance |\n| - | - | - |\n| *Llava-Video* (Full Attention) | 17.3 | 55.5 |\n| A-Shape | 12.0 | 53.1 |\n| Tri-Shape | 11.6 | 54.7 |\n| VisionZip | OOM | OOM |\n| MInference | 15.4 | 55.2 |\n| MAPSparse | 14.2 | 57.6 |\n\nRTable 1. Performance (%) of different methods on video understanding tasks evaluated.\n\n2. ***\"longer frames\"***\n\nThanks for the suggestion. Here we show the results of MAPSparse and the full attention baselines with various numbers of frames from 32 to 256. The results show that more frames can consistently improve the performance on video understanding tasks.\nMAPSparse improves system throughput by supporting more frames and higher QPS video inputs within the same latency constraints.\n\n| Method | Num. Frames | VideoMME (w/o sub) | VideoMME (w/ sub) |\n| - | - | - | - |\n| LongVILA (Full Attention) | 32 | 55.2 | 58.1 |\n| MAPSparse | 32 | 56.5 | 58.1 |\n| Full Attention | 64 | 59.1 | 62.0 |\n| MAPSparse | 64 | 58.4 | 62.4 |\n| Full Attention | 128 | 59.4 | 64.7 |\n| MAPSparse | 128 | 59.0 | 64.8 |\n| Full Attention | 256 | 60.1 | 65.1 |\n| MAPSparse | 256 | 60.0 | 65.5 |\n\nRTable 2. Performance (%) of different frame on video understanding tasks evaluated using LongVILA.\n\n3. ***\"meaning and how the recall rates are calculated\"***\n\nThe recall rate reflects how much of the original attention score is retained in the top-k sparse attention. It is computed by calculating the softmax scores over the top-k key vectors retrieved for each query vector, i.e., $\\text{softmax}(qK_{\\text{topk}}^T)$. We will update the paper to include a formal definition of the recall rate in the next revision.", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "Yes, it make senses.", "theoretical_claims": "Yes.", "experimental_designs_or_analyses": "Yes", "relation_to_broader_scientific_literature": "This work tries to accelerate the operation on top of other vision language models.", "essential_references_not_discussed": "No", "other_strengths_and_weaknesses": "Strength\n----------\n1. This work aims to optimize the long sequence for vision-language models, which is promising ane essential in current framework.\n2. The proposed method is proved to work well in two different methods for long video understanding.\n3. The problem is well analyzed with good comparisons.\n\nWeakness\n----------\n1. Because this work tries to optimize the operation in VLM, it's better to report average latency and memory consumption in Table 1 for better comparisons with other methods.\n2. An efficient operation in VLM should bring longer frames (or higher FPS), which is an essential for video understanding. The authors are recommended to provide a table that contains results and lantency with increasing frames.\n3. It's better to provide what is the meaning and how the recall rates are calculated in Section 2.1.", "other_comments_or_suggestions": "No", "questions_for_authors": "My questions are mainly focusing on the experiments and definition, as listed in weakness section.\n\n1. Because this work tries to optimize the operation in VLM, it's better to report average latency and memory consumption in Table 1 for better comparisons with other methods.\n2. An efficient operation in VLM should bring longer frames (or higher FPS), which is an essential for video understanding. The authors are recommended to provide a table that contains results and lantency with increasing frames.\n3. It's better to provide what is the meaning and how the recall rates are calculated in Section 2.1.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "uDRS90nRg9", "reviewer": "Reviewer_bbGN", "summary": "The paper addresses the computational bottleneck in long-context Vision Language Models (VLMs) during the pre-filling stage. The authors observe that attention in VLMs exhibits unique sparse patterns, particularly a \"Grid\" pattern in video inputs due to spatiotemporal locality. They also identify distinct modality boundaries in attention (No-Boundary, K-Boundary, Q-Boundary, and 2D-Boundary).\n\nBased on these observations, the authors propose MAPSparse, a permutation-based dynamic sparse attention approach that significantly reduces computation while maintaining performance. MAPSparse consists of three main components: 1) the Grid sparse attention pattern for intra-modality attention, 2) Q-Boundary and 2D-Boundary patterns for handling mixed-modality inputs, and 3) a Modality-Aware Sparse Attention Search Algorithm to optimize patterns for each attention head.\n\nExperiments on video understanding tasks, Video Needle in a Haystack (V-NIAH), and Mix Modality Needle in a Haystack (MM-NIAH) show that MAPSparse achieves up to 8.3× speedup over FlashAttention-2 and 1.7× over MInference at 1M token length while maintaining competitive performance.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We greatly appreciate the reviewer's recognition and thoughtful, constructive feedback. Below, we address each of the comments and concerns in detail.\n\n1. ***\"How stable are the identified patterns across different models and datasets\"***\n\nThank you for the suggestion. We have tested these patterns across various VLMs and a wide range of datasets including open-domain question answering, multiple-choice question answering, video captioning, and video information retrieval. Additionally, we provide further pattern analysis on two recent VLMs, Qwen2.5-VL [1] and VideoChat-Flash [2], to demonstrate that the attention patterns leveraged in our method are consistently observed across different models and tasks, see https://anonymous.4open.science/r/complementary-D5B2/. While we also observe other patterns, such as local window attention, these are in fact special cases of our existing patterns and can be effectively captured by our method.\n\n2. ***\"Typo issue\"***\n\nThank you for your careful review. We will fix this issue in the next version.\n\n[1] Qwen2.5-VL Technical Report, 2024.  \n[2] VideoChat-Flash: Hierarchical Compression for Long-Context Video Modeling, 2024.", "claims_and_evidence": "1. VLM attention exhibits unique sparse patterns compared to LLMs, including a Grid pattern.\n    - Evidence: Visualizations in Figures 2 and 5 demonstrate these patterns clearly. Section 2 provides quantitative analysis showing VLMs require only 5.78% of attention weights to recall 95% of total attention.\n\n2. Modality boundaries create distinct attention patterns that require specialized handling.\n    - Evidence: Figures 2b, 2c, and 3 visualize these boundaries, and the authors provide detailed analysis of how they affect attention.\n\n3. MAPSparse accelerates the pre-filling stage by up to 8.3× at 1M tokens while maintaining performance.\n    - Evidence: Comprehensive experiments on video understanding tasks (Table 1) and NIAH tasks (Figure 4) show strong performance. Figure 6 demonstrates the claimed speedups.", "methods_and_evaluation_criteria": "Methods:\n1. The analysis of attention patterns in VLMs (Section 2) establishes the foundation for the approach\n2. The MAPSparse framework (Section 3) is described algorithmically with pseudocode for each component\n3. Implementation details are provided, including how permutation is applied and how dynamic sparse indices are constructed\n\nEvaluation Criteria:\n1. Accuracy preservation: The authors compare performance on diverse video understanding tasks including video captioning, QA, and retrieval\n2. Computational efficiency: Both theoretical FLOPs reduction and actual runtime speedups are measured\n3. Scalability: Tests at different context lengths (from ~20K to 1M tokens)\n4. Comparison against baselines: The method is compared against multiple sparse attention approaches and token compression methods", "theoretical_claims": "The paper does not make significant novel theoretical claims. It's primarily an empirical investigation of attention patterns in VLMs and an engineering solution to accelerate computation. However, the observations about Grid patterns and modality boundaries add to the theoretical understanding of how VLMs process multi-modal information.", "experimental_designs_or_analyses": "The experimental design is thorough and well-executed.\n1. Two state-of-the-art long-context VLMs are used (Llava-Video and LongVila)\n2. Multiple video understanding benchmarks plus two NIAH tasks\n3. Several sparse attention methods and a visual token compression method\n4. The contribution of each component is evaluated, especially in the MM-NIAH task\n\nOne minor limitation is that the paper focuses primarily on accuracy and retrieval performance.  Additional evaluations like robustness would strengthen the analysis further.", "relation_to_broader_scientific_literature": "The paper positions its work well within the broader literature on VLMs and attention efficiency.", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "The visualizations are outstanding and provide clear insights into attention patterns. \nWhile the paper mentions implementation details of the attention pattern visualization, more detail could be provided in the main text.\nBesides, Are there additional attention patterns beyond those identified?", "other_comments_or_suggestions": "\"Spars Transformer\" on line 319 that should be \"Sparse Transformer\"", "questions_for_authors": "How stable are the identified patterns across different models and datasets? Are there additional attention patterns beyond those identified?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: MAPSparse offers good solution to a key bottleneck in long-context VLMs by introducing modality-aware sparse attention with strong empirical grounding. The paper is well-motivated and technically sound, demonstrating up to 8.3× speedup without compromising accuracy across diverse tasks and models. The rebuttal thoroughly addressed concerns on generalization, latency, and applicability, strengthening the paper's contribution. Overall, this work presents a solid advancement for efficient VLM inference, and AC and reviewers recommend acceptance.
Decision: Accept (poster)