PaperlayerView exact revision on arXiv

Source-linked AI summary

Script: Graph-Structured and Query-Conditioned Semantic Token Pruning for Multimodal Large Language Models

Zhongyu Yang, Dannong Xu, Wei Pang, Yingfang Yuan

arXiv:2512.01949v1cs.CV

TL;DR

Visual-token growth creates memory and latency costs, while existing pruning approaches may miss query-relevant content. Script combines graph-structured pruning with query-conditioned, diversity-aware selection. Across fourteen benchmarks, it consistently outperforms baselines, with reported speedup while retaining most original performance.

  • Problem

    Visual-token growth increases memory use and inference latency, while existing methods may overlook query-relevant tokens or rely on attention mechanisms with known limitations.

    Source: §1 · p. 2

  • Method

    Script combines graph-structured pruning for visual redundancy with query-conditioned semantic pruning using DPP-based selection.

    Source: §1 · p. 3

  • Results

    Across fourteen benchmarks, Script consistently overperforms other baselines and achieves up to 10× speedup while retaining 96.88% of original performance.

    Source: §1 · p. 3

  • Takeaways & Limitations

    Script’s plug-and-play, architecture-agnostic design requires no retraining or architectural changes to integrate into existing MLLMs.

    Source: §6 · p. 13

    2MAP for DPP is an NP-hard problem.

    Source: §4.3 · p. 10

Abstract

from arXiv · show

The rapid growth of visual tokens in multimodal large language models (MLLMs) leads to excessive memory consumption and inference latency, especially when handling high-resolution images and videos. Token pruning is a technique used to mitigate this issue by removing redundancy, but existing methods often ignore relevance to the user query or suffer from the limitations of attention mechanisms, reducing their adaptability and effectiveness. To address these challenges, we propose Script, a plug-and-play pruning method that requires no retraining and generalizes across diverse MLLMs. Script comprises two modules: a graph-structured pruning module that removes visually redundant tokens, and a query-conditioned semantic pruning module that preserves query-relevant visual information. Together, they enhance performance on multimodal tasks. Experiments on fourteen benchmarks across image and video understanding tasks show that Script consistently achieves higher model efficiency and predictive accuracy compared to existing pruning methods. On LLaVA-NeXT-7B, it achieves up to 6.8x prefill speedup and 10x FLOP reduction, while retaining 96.88% of the original performance.

1 Introduction

Large visual-token sequences increase memory use and inference latency, while existing pruning can miss query-relevant content. Script combines graph-structured redundancy removal with query-conditioned selection; the paper reports strong results across benchmarks.

1 Introduction

  • Visual-token growth compounds attention’s quadratic complexity, creating memory and latency bottlenecks in resource-constrained deployments.The paper identifies high-resolution and temporally extended visual inputs as particularly costly.Source: §1 · p. 2
  • Attention-based pruning can miss critical tokens, while similarity- and divergence-based methods select fixed subsets regardless of the query.These limitations can cause query-referenced objects to be omitted.Source: §1 · pp. 2–3
  • Script combines graph-structured pruning with query-conditioned semantic pruning to remove visual redundancy while retaining query-relevant tokens.The method is described as training-free and architecture-agnostic, with DPP used for query-aware selection.Source: §1 · p. 3
  • Across fourteen benchmarks, Script achieves up to 10× speedup while retaining 96.88% of original performance.The introduction also reports 88.9% token reduction with 99.88% accuracy on POPE.Source: Figure 2 · p. 2, §1 · p. 3

2 Related Work

Visual-token overhead motivates pruning, but existing approaches make trade-offs among plug-and-play use, architectural transfer, and query relevance. Script is presented as addressing these gaps through query-aware, model-agnostic, training-free pruning.

2 Related Work

  • Visual inputs can produce tens or hundreds of thousands of tokens, intensifying memory and compute demands in high-resolution and video settings.The paper notes that attention’s quadratic complexity aggravates this overhead.Source: §2 · p. 3
  • Existing strategies include pre-fusion compression, attention-based pruning, pre-language-fusion pruning, and similarity-based pruning, each with stated limitations.The cited limitations include retraining or structural changes, attention drift and backend compatibility, backbone coupling, and failure to account for query semantics.Source: §2 · p. 3
  • Few existing approaches combine query relevance, architectural generality, and training-free deployment; Script is described as combining these properties with visual diversity.The paper characterizes Script as explicitly query-aware, model-agnostic, and requiring no additional training.Source: §2 · p. 3

3 Preliminary

The preliminary analysis frames pruning as selecting a compact visual-token subset that preserves performance while accounting for query relevance and token redundancy. Its empirical observations motivate graph-based redundancy estimation and query-conditioned, diversity-aware selection.

3 Preliminary

  • The preliminary section investigates visual redundancy and query-conditioned relevance in TextVQA and presents a theoretical formulation to inform Script’s design.Source: §3 · p. 4

3.1 Research Objective

  • Pruning seeks a subset of visual tokens that preserves model performance with fewer tokens, while accounting for query interactions and redundancy.The visual-token sequence is typically much longer than the textual query.Source: §3.1 · p. 4

3.2 Rethinking Visual Redundancy

  • Token similarity is highest nearby, declines until roughly distance 15, then rises at longer distances; adjacent pairs also more often exceed 0.5 similarity than random pairs.These observations indicate both local and long-range redundancy.Source: §3.2 · p. 5
  • Low-entropy neighborhoods coincide with high neighbor similarity, supporting cosine similarity as a proxy for local redundancy.The analysis relates local entropy to neighborhood compactness and finds an inverse relationship with cosine similarity.Source: §3.2 · p. 5
  • The even–odd bipartite graph estimates redundancy at lower computational cost than exhaustive computation; at 90% POPE pruning, accuracy is 84.49% versus 85.14%, with nearly three times the speed.It retains 93% IOU agreement with the exhaustive approach.Source: §3.2 · p. 5

3.3 Rethinking Query Relevance

  • Attention-based relevance can favor salient foregrounds while missing query-relevant background tokens, as in the flower example.This motivates explicitly query-aware relevance scoring.Source: §3.3 · p. 6

3.4 Rethinking Query-Relevant Visual Token Selection

  • The k-DPP kernel combines query relevance with pairwise visual similarity, favoring subsets that are both informative and diverse.The relevance scores use cosine similarity between visual tokens and the mean query embedding; the formulation assumes a symmetric positive-semidefinite similarity matrix.Source: §3.4 · pp. 6–7

4 Method

Script combines graph-structured pruning (GSP) to remove visually redundant tokens with query-conditioned semantic pruning (QCSP) to retain query-relevant tokens, then intersects their selections for the final subset.

4 Method

  • Script uses GSP to remove visual redundancy and QCSP to select query-relevant tokens, intersecting both outputs to form the final subset.If the intersection is too small, additional QCSP tokens are retrieved by increasing k.Source: §4 · p. 7, §4.3 · p. 10

4.1 Graph-Structured Pruning

  • GSP partitions visual tokens into two sets, connects them by cosine similarity, and ranks threshold-graph redundancy using degree and similarity with exponential weighting.The highest-scoring tokens are discarded according to the pruning ratio.Source: §4.1 · pp. 7–8

4.2 Query-Conditioned Semantic Pruning

  • QCSP scores tokens by cosine similarity to a mean-pooled query, then reweights visual similarity with normalized relevance for k-DPP selection of relevant, diverse tokens.The k-DPP subset is selected using approximate MAP inference and a Cholesky-based greedy algorithm.Source: §4.2 · pp. 9–10

4.3 Final Token Selection

  • GSP targets visual redundancy while QCSP captures query relevance; their intersection forms the final selection, supplemented with more QCSP tokens if needed.The supplement is obtained by iteratively increasing k when the intersection has fewer tokens than required.Source: §4.3 · p. 10

5 Experiments

Across image and video models and pruning budgets, Script outperforms baselines; ablations and an efficiency comparison further examine its modules and resource costs.

5.1 Experimental Settings

  • The evaluation spans four MLLMs, five pruning baselines, and fourteen image- and video-understanding benchmarks.The tested models include LLaVA 1.5, LLaVA-NeXT, Video-LLaVA, and InternVL3.Source: §5.1 · p. 11

5.2 Results and Discussions

  • On LLaVA-1.5-7B, Script achieves 100.00% accuracy at 192 tokens and 89.51% under the most aggressive pruning, outperforming baselines.At 64 tokens, it retains 96.86% accuracy.Source: §5.2 · pp. 11–12
  • On LLaVA-NeXT-7B, Script reaches 62.80% accuracy and 95.98% relative performance with 160 tokens, outperforming baselines across pruning levels.At 640 tokens, it records 65.1% average accuracy and 99.88% relative performance.Source: §5.2 · p. 12
  • Video-LLaVA-7B retains 89.30% average accuracy at 90.5% token reduction, with Script outperforming other baselines across pruning levels.At 64×32 tokens, it achieves 95.00% accuracy and beats FastV by roughly 7 percentage points.Source: §5.2 · p. 12

5.3 Ablation study

  • At 97.3% pruning, the full configuration retains 92.19% of original accuracy using 2.7% of tokens, versus 91.19% for QCSP alone and 66.58% for GSP alone.Naive pruning averages 63.73% relative accuracy; the ablation uses 0.103 TFLOPs and retains 16 tokens on average.Source: Table 5 · p. 12, §5.3 · p. 12

5.4 Case study

  • The case study finds that DPP-based scores align more with query semantics than similarity-based scores, while lacking their diversity; GSP and QCSP are presented as complementary.The attention-based approach emphasizes globally salient regions but can overlook query-relevant backgrounds.Source: §5.4 · pp. 12–13, Figure 5 · p. 13

5.5 Efficiency Analysis

  • On POPE, Script cuts FLOPs 10× to 4.1T and prefill to 35ms (6.8× faster), while scoring F1 86.7 versus 86.8 uncompressed.It also reduces KV cache to 160MB and peak memory to 13.5GB.Source: Table 6 · p. 13, §5.5 · p. 13

6 Conclusion

Script selects a compact, query-conditioned subset of visual tokens, combining graph-based redundancy reduction and semantic selection. The appendix explains how determinants and DPPs formalize diversity in subset selection.

6 Conclusion

  • Script combines graph-structured filtering, query-conditioned relevance scoring, DPP-based diverse selection, and intersection-based fusion without retraining or architectural changes.The conclusion reports experiments across fourteen vision-language benchmarks and identifies audio and adaptive pruning schedules as future directions.Source: §6 · p. 13

A Notation Overview

  • The notation overview centralizes symbols for visual encoding, query representation, relevance scoring, similarity, DPP selection, structural pruning, and auxiliary constants.It is intended to reduce cross-referencing and support reproduction and further development.Source: A Notation Overview · p. 20, Table A.1 · p. 20

B.1 Notation.

  • The appendix assumes unit-norm feature vectors, so their inner products equal cosine similarities; the resulting similarity kernel is symmetric and positive semidefinite.These Gram-matrix properties support the DPP model discussed next.Source: §B.1 · p. 21

B.2 Determinant as a Diversity Objective

  • For a subset of feature vectors, the Gram-matrix determinant equals the squared volume they span, making it a diversity objective that favors spread-out vectors.The determinant reaches its maximum value of 1 when the unit vectors are mutually orthogonal.Source: §B.2 · pp. 21–22, §B.3 · p. 22

B.3 Diversity Upper Bound via Hadamard Inequality

  • For a Gram matrix of unit vectors, Hadamard’s inequality bounds the determinant by 1, with equality when the vectors are mutually orthogonal.If the subset size exceeds the feature dimension, its determinant is zero.Source: §B.3 · p. 22

B.4 Determinantal Point Processes and Diversity Maximization

  • A k-DPP assigns each size-k subset probability proportional to its Gram-matrix determinant, favoring geometrically diverse subsets; MAP inference seeks the subset with the largest determinant.The determinant is equivalent to the squared volume spanned by the selected vectors.Source: §B.4 · pp. 22–23

B.5 Redundancy Metrics and Determinant Bounds

The appendix relates determinant-based diversity to redundancy, then characterizes when MAP selection does or does not minimize redundancy and gives a greedy approximation guarantee.

B.5 Redundancy Metrics and Determinant Bounds

  • The AM–GM determinant bound is the redundancy-insensitive ceiling 1, while the refined tight envelope decreases with average similarity and is strictly tighter when that similarity is positive.The refined envelope is attained by the equicorrelation matrix.Source: §B.5 · p. 24, Figure B.1 · p. 25

B.6 Global Optimality of the MAP Subset

  • In general, a k-DPP MAP subset need not minimize either maximum-pair or average redundancy.The section’s example shows that maximizing the determinant does not generally minimize either measure.Source: §B.6 · p. 24

B.7 Approximation via Greedy MAP Inference

  • Exact k-DPP MAP inference is NP-hard; greedy maximization of the regularized log determinant has a (1 − 1/e) approximation guarantee, but no general redundancy guarantee is claimed.Translating the guarantee to maximum or average redundancy requires additional structure in the kernel.Source: §B.7 · p. 25

B.8 Sufficient Condition for Equivalence

  • Under the stated equicorrelation condition, the MAP subset simultaneously maximizes geometric diversity and minimizes redundancy.In this setting, maximum and average similarity coincide, and the determinant decreases as similarity increases.Source: §B.8 · pp. 25–26

B.9 Summary.

The appendix relates determinant-based DPP selection to geometric diversity and redundancy minimization, with the latter guaranteed under an equicorrelation condition. It also describes the models used in the study, including LLaVA variants, LLaVA-Video, and InternVL3.

B.9 Summary.

  • Maximizing det(LS) favors nearly orthogonal subsets and reduces worst-case and average redundancy, but a general MAP solution provides envelope constraints rather than guaranteeing redundancy minimization.The equivalence between maximizing det(LS) and minimizing ρmax and ρavg requires additional structure, notably the equicorrelation condition.Source: §B.9 · p. 26
  • Under the equicorrelation condition, the MAP solution both maximizes geometric diversity and minimizes redundancy, linking the DPP objective to Script’s selection principle.The kernel remains positive semidefinite when query-conditioned relevance weights vary across tokens.Source: §B.9 · pp. 26–27
  • When exact MAP inference is infeasible, greedy maximization of log det(I + LS) provides constant-factor guarantees for the regularized determinant.The appendix presents this as a practical strategy that preserves much of the global optimum’s diversity.Source: §B.9 · p. 26
  • Script applies determinant maximization to a query-conditioned multimodal setting to favor diverse, complementary visual tokens.The theoretical discussion also connects the query-conditioned kernel to relevance, diversity, and redundancy reduction in empirical summarization and retrieval.Source: §B.9 · pp. 26–27

C.1 Model Architectures

  • LLaVA-1.5 uses a CLIP visual encoder, Vicuna, and an MLP connector, producing 576 visual tokens from 336×336 images.It uses a broader instruction-tuning dataset and higher image resolution than the original LLaVA framework.Source: §C.1 · p. 28
  • LLaVA-NeXT adds dynamic resolution up to 4× and concatenates tokens from independently encoded sub-images; experiments fix inputs at 672×672, yielding 2,880 tokens.The visual encoder remains unchanged from LLaVA-1.5.Source: §C.1 · p. 28
  • LLaVA-Video uses SlowFast frame sampling, SigLIP, and 2×2 pooling; sampling 64 frames yields 10,816 visual tokens.The design is intended to model both spatial and temporal aspects of video input.Source: §C.1 · p. 28
  • InternVL3 retains a ViT-MLP-LLM architecture and adds native multimodal pretraining and Variable Visual Position Encoding for extended multimodal contexts.The passage also describes supervised fine-tuning and mixed preference optimization.Source: §C.1 · p. 28

C.2.1 General Image Benchmarks

The appendices catalogue the image, text-oriented, and video benchmarks and describe prior pruning approaches and evaluation settings. Reported results on InternVL3 and larger LLaVA models favor Script, with sensitivity tests identifying robust configuration choices.

C.2.1 General Image Benchmarks

  • The image benchmarks cover general VQA and perception, including VQAv2, GQA, VizWiz, POPE, MME, MMBench, MM-Vet, and HallusionBench.The descriptions span compositional reasoning, unanswerable questions, hallucination, perception and cognition, and integrated multimodal skills.Source: §C.2.1 · pp. 28–29

C.2.2 Text-Oriented Benchmarks

  • Text-oriented evaluation includes TextVQA, AI2D, ChartQA, and OCRBench, covering embedded text, diagrams, chart reasoning, and OCR tasks.ChartQA includes human-written and generated questions requiring visual, logical, or arithmetic reasoning.Source: §C.2.2 · p. 29

C.2.3 Video Benchmarks

  • Video benchmarks include long-video understanding, temporal reasoning, and multimodal QA, with MLVU, MVBench, LongVideoBench, and Video-MME.The described datasets range from short clips to videos as long as two hours and include multiple-choice and open-ended questions.Source: §C.2.3 · p. 30

C.3.1 Text-based Methods

  • Prior methods use text attention or selected text tokens as raters, CLIP image–text similarity, visual self-attention and clustering, or maximum minimum distance to guide pruning.FastV prunes low-attention tokens; SparseVLM selects relevant instruction tokens as raters; TRIM ranks by CLIP similarity; VisionZip combines dominant and contextual tokens; DivPrune maximizes minimum pairwise distance.Source: §C.3.1 · p. 30, §C.3.2 · p. 30, §C.3.3 · p. 30

D.1 Script for advanced open-source MLLM

  • With 90% of visual tokens removed, Script retains 83.9% of original performance on InternVL3, 3% above second-best FastV; with 77.8% removed, it retains 97.64% on LLaVA-1.5-13B and 99.95% on LLaVA-NeXT-13B.The authors report Script as best across reduction ratios on InternVL3 and across pruning strategies on the larger LLaVA models.Source: Table D.1 · p. 31, §D.1 · p. 32, Table D.2 · p. 32

C.4 Implementation Details

  • Evaluations use official LLaVA implementations and preprocessing, zero-shot image settings, 64 sampled video frames, and lmms-eval; experiments standardize decoding and average three runs.The appendix also reports review of dataset and model licenses and limits usage to noncommercial academic research.Source: §C.4 · p. 31, §C.5 · p. 31, Table C.1 · p. 31

D.3 Hyperparameter sensitivity & guidance.

  • Across τ ∈[0.1, 0.9], average relative performance remains above 95%; τ = 0.3, γ = 5, and kernel S′ are the reported default settings.The authors report that S′ outperforms S and that τ = 0.3 yields the strongest overall results.Source: Table D.4 · p. 33, §D.3 · p. 33

D.4 Overlap analysis between GSP and QCSP.

GSP and QCSP select tokens using complementary criteria, and their overlap changes with the retention budget. The appendices also report statistical comparisons and visualizations of query relevance and retained regions.

D.4 Overlap analysis between GSP and QCSP.

  • The GSP–QCSP overlap is 66.7% when retaining 192 tokens and 97.3% when retaining 16 tokens; QCSP contributes more as pruning becomes more aggressive.The overlap never reaches 100%, so QCSP also serves as a fallback for meeting the token budget.Source: §D.4 · p. 34
  • GSP captures structural redundancy that QCSP alone may overlook, while QCSP ensures query relevance and increasingly shapes selections under tighter token budgets.The authors characterize the modules’ interaction as balancing efficiency and accuracy.Source: §D.4 · p. 34

D.5 Statistical Significance Experiments

  • On LLaVA-Next-7B, paired one-sided t-tests and Wilcoxon signed-rank tests across 20 runs report p-values below α = 0.05 for Script’s comparisons with other methods.The tests evaluate the null hypothesis that Script performs the same as the other methods against the alternative that it performs better.Source: Table D.6 · p. 34, §D.5 · p. 34

E.1 Case study

  • Figures E.1 and E.2 visualize relevance scores and retained tokens against textual instructions, with reported maps highlighting regions tied to object-presence and counting queries.The accompanying discussion presents these correspondences as showing how pre-trained models focus on task-specific visual regions.Source: Figure E.1 · p. 35, §E.1 · pp. 35–36, Figure E.2 · p. 36

E.2 Redundancy Visualization Across Thresholds

Patch redundancy is estimated from cosine similarity to spatial neighbors, and the threshold controls how selectively the maps mark patches. Mid-range settings retain redundancy information while leaving distinctive structures available; aggressive filtering may discard subtle contextual cues.

E.2 Redundancy Visualization Across Thresholds

  • At τ = 0.1, nearly all patches are marked redundant, so the mask preserves information but distinguishes little repetitive from unique content.As τ rises to 0.3 and 0.5, flat or repetitive textures remain marked while irregular patches increasingly drop out.Source: §E.2 · p. 37
  • Around τ = 0.5, homogeneous regions remain marked as redundant while edges, boundaries, and irregular textures are less often included.This leaves distinctive features available for recognition or further processing while still capturing redundancy for compression.Source: §E.2 · p. 37
  • At τ = 0.7 and especially 0.9, maps become very sparse, isolating distinctive patches but potentially discarding subtle, semantically useful context.The map’s redundancy markings also form spatially contiguous clusters across thresholds.Source: §E.2 · p. 37
  • The error analysis distinguishes failures from limited CLIP text–visual alignment from failures caused by inadequate CLIP visual representations.The former can leave GSP correct but QCSP incorrect; the latter can make both modules incorrect.Source: Figure E.4 · p. 38
  • Mid-level thresholds, around τ ≈0.5, offer a compromise between filtering redundant clusters and retaining structural diversity, while high thresholds risk losing context.The maps are computed from each patch’s average cosine similarity with its 8-connected neighbors and binarized at multiple thresholds.Source: §E.2 · pp. 37–38

E.3 Error Analysis

The error analysis separates failures into base-LLM reasoning limits, text–visual misalignment, and compounded pruning errors. It concludes that Script often preserves accuracy while query-specific signals can still be underused or lost.

E.3 Error Analysis

  • Preserved remote-control tokens did not prevent an incorrect prediction, illustrating a reasoning failure in associating visual evidence with query semantics.Both GSP and QCSP assigned relatively high retention scores to the remote-control token, but the final prediction remained incorrect.Source: §E.3 · pp. 38–39
  • QCSP favored chair tokens while GSP scored tokens more diffusely, yet the model incorrectly inferred a person, exposing text–visual misalignment.The example links confusion between the concept “person” and visually similar chair regions to insufficiently nuanced cross-modal grounding.Source: §E.3 · p. 39
  • Misleading scores from both GSP and QCSP caused the warning sign to be pruned or overlooked, producing an error at the pruning stage.Unlike downstream reasoning failures, this cumulative pruning error suppresses evidence the LLM cannot recover from.Source: §E.3 · p. 39
  • The cases distinguish base-model reasoning limits, grounding misalignment, and pruning-error propagation; query-specific signals may still be underused or lost.The categories are distinct but complementary, and may overlap.Source: §E.3 · p. 39

F Limitations and Future Work.

The paper identifies boundaries in model access, modality coverage, architecture sensitivity, and threshold selection. It also presents efficiency as a potential aid to deployment while noting that efficiency alone does not address misuse or misinformation risks.

F Limitations and Future Work.

  • Script requires access to encoded visual tokens during inference, limiting deployment to open-source MLLMs rather than closed systems such as ChatGPT, Gemini, and Claude.The authors state that intermediate visual features are inaccessible in those proprietary systems.Source: F Limitations and Future Work · p. 39
  • The evaluation covers vision–language inputs with text and visual tokens, not audio, depth, or IMU modalities.The authors leave pruning for these other modalities to future investigation.Source: F Limitations and Future Work · p. 39
  • Qwen2.5-VL and InternVL3 show greater performance degradation than the LLaVA series at the same pruning ratio, possibly because they already compress visual tokens.The authors identify adaptation to such optimized architectures as future work.Source: F Limitations and Future Work · p. 39
  • The threshold τ remains manually selected rather than adaptively determined, although sensitivity analysis found relatively stable performance across a wide range.The authors provide default recommendations and suggest automated or learning-based threshold selection as future work.Source: F Limitations and Future Work · pp. 39–40

G Broader Impacts

  • The authors say reduced computational overhead and deployment costs may facilitate MLLM use on resource-constrained mobile and edge platforms.They frame broader accessibility and scalability as potential benefits.Source: G Broader Impacts · p. 40
  • Improved computational efficiency does not itself mitigate MLLM risks such as harmful-content generation or misinformation dissemination.The authors call for continued research and policy development for responsible and safe use.Source: G Broader Impacts · p. 40
Loading 2512.01949v1…