RS$^3$-Prune: Read-Sparse, Store-Sparse Token Pruning for Video Object Segmentation

Avilasha Mandal; Sarvesh Shashikumar

cs.CVAug 23, 2026

RS $^3$ -Prune: Read-Sparse, Store-Sparse Token Pruning for Video Object Segmentation

Authors: Avilasha Mandal, Sarvesh Shashikumar

Organizations: Attentive AI · Indian Institute of Technology Delhi

Abstract

We introduce RS $^3$ -Prune, a training-free token-pruning recipe that instantiates as a small set of inference time hooks atop existing video object segmentation (VOS) networks. Modern VOS models have converged on a common, expensive design: an image encoder produces a dense token grid for every frame, and a memory bank accumulates these tokens across all previously processed frames to condition future predictions. As a video grows longer, the resulting token budget governs both per-frame latency and peak GPU memory. Hence these models break on use cases such as --- long-form video or real-time deployment on memory-bounded accelerators. In this work we argue that the right axis along which to compress memory-bank VOS is the token budget itself. RS $^3$ -Prune operates in two precise locations within an arbitrary memory-bank VOS pipeline: at the boundary between the image encoder and the memory-attention readout, where we restrict the queries that participate in the cross-frame attention to only a small, geometrically informed subset; and at the boundary between the memory encoder and the memory bank, where we restrict which tokens are ever permitted to enter the bank to those that lie within the object's spatial extent. Over various established benchmarks, RS $^3$ -Prune delivers up to $38.8\%$ FPS speedup and reduces $13.1\%$ peak memory usage, while preserving a competitive $\mathcal{J}$ & $\mathcal{F}$ compared to the unmodified VOS networks.

Figures & tables

Figure 1: Overview of RS 3 -Prune. The standard memory- bank VOS pipeline (blue) passes all

mn

encoder tokens through memory attention

\mathcal{A}

and into the memory encoder

\Phi_{\mathrm{mem}}

. RS 3 -Prune inserts two training-free pruning operators (orange) at the two token boundaries. The read-side prune

\mathcal{K}_{r}

retains only tokens that lie within the spatial prior and carry high visual energy, reducing the query load on

\mathcal{A}

. The write-side prune

\mathcal{K}_{w}

retains only tokens anchored to first-occurrence object seeds before they are written to the memory bank

(\mathbf{K},\mathbf{V})

, controlling bank growth. Both pruning steps are applied to the frozen pretrained checkpoint with no retraining.

Figure 2: Read-side prune. Starting from the full $mn$ token grid, bounding boxes from the first-frame annotation are dilated and unioned to form a spatial prior. Token norms are computed as a proxy for visual energy, with higher-norm tokens (darker green) indicating visually salient regions. The final kept set $\mathcal{K}_{r}$ is the intersection of the spatial prior with the top-energy tokens; only these tokens participate as queries in the subsequent sparse memory attention over $(\mathbf{K},\mathbf{V})$ .

Figure 3: Write-side prune. For each seed frame — the first frame in which an object appears — per-object masks are decoded and unioned into a single seed mask. This union is pooled to the token grid to yield the kept index set $\mathcal{K}_{w}$ , which selects the tokens passed to the memory encoder $\Phi_{\mathrm{mem}}$ . Only these seed-anchored tokens are appended to the memory bank $(\mathbf{K},\mathbf{V})$ , preventing background clutter from accumulating in the bank across frames.

		Vanilla					RS 3 -Prune
Dataset	Model	$\mathcal{J}$	$\mathcal{F}$	$\mathcal{J}\&\mathcal{F}$	fps	vram	$\mathcal{J}$	$\mathcal{F}$	$\mathcal{J}\&\mathcal{F}$	fps	vram
DAVIS-17 [ 18 ]	STM [ 16 ]	0.775	0.828	0.802	37.6	1043	0.757	0.782	0.770	49.4	728
	XMem [ 7 ]	0.829	0.896	0.862	37.2	845	0.821	0.876	0.849	69.7	655
	Cutie [ 6 ]	0.847	0.911	0.879	23.8	436	0.841	0.895	0.868	75.6	424
	SAM2 [ 20 ]	0.858	0.906	0.882	9.6	1809	0.774	0.819	0.797	11.4	1791
	SAM3.1 [ 3 ]	0.529	0.590	0.560	8.70	7375	0.517	0.579	0.548	8.70	6154

Table 1: Main results of RS 3 -Prune across five VOS benchmarks. Consistent with SOTA VOS evaluation metrics, we report

\mathcal{J}

\mathcal{F}

and the

\mathcal{J}\&\mathcal{F}

score, and to display the efficiency and lower resources utilised, we report the FPS and VRAM used. VRAM is measured in MB . Green marks a gain. — indicates that STM cannot handle new object emergence in middle of the video sequence, a characteristic of YT-VOS. bold fps / vram in the RS 3 -Prune block marks improvement over Vanilla

Dataset	Method	SAM2	SAM3.1	STM	XMem	Cutie
DAVIS-17 [ 18 ]	Vanilla	.882 9.6/1809	.560 8.7/7375	.802 37.6/1043	.862 37.2/845	.879 23.8/436
	SparseViT [ 5 ]	.508 12.4/2324	.545 8.5/7175	.647 22.5/1730	.791 46.0/1207	.808 80.2/638
	DynamicViT [ 19 ]	.041 12.5/2324	.392 8.5/7175	.612 44.8/1730	.554 68.7/1207	.798 33.1/638
	VLTP [ 4 ]	.133 12.1/2905	.012 8.5/7175	.275 45.5/1730	.291 74.8/1207	.553 32.5/638
	RS 3 -Prune	.797 11.4/1791	.548 8.7/6154	.770 49.4/728	.849 69.7/655	.868 75.6/424
SA-V [ 20 ]	Vanilla	.465 9.1/2317	.468 3.7/8543	.506 32.2/1327	.613 65.8/859	.639 74.1/501

Table 2: Comparison against efficient token-reduction baselines.

\mathcal{J}\&\mathcal{F}

(top) / fps - vram in MB (bottom) for each method-backbone pair. All baselines are image-domain token-reduction methods with no object- or video-level prior.

Model	Config	$\mathcal{J}\&\mathcal{F}$	fps	vram (MB)
STM [ 16 ]	V	0.802	37.6	1043
	R	0.735	40.4	873
	R $+$ W	0.770	49.4	728
XMem [ 7 ]	V	0.862	37.2	845
	R	0.851	56.1	698
	R $+$ W	0.849	69.7	655

Table 3: Read-side vs. write-side ablation on DAVIS-17 [ 18 ] val. R = read-side prune only; R+W = full RS 3 -Prune. On XMem and Cutie, the read-side prune delivers most of the speedup; adding the write-side prune yields a further

\sim

25% FPS gain and a further VRAM reduction over the read-side-only row (6% on XMem, 2.5% on Cutie) at negligible

\mathcal{J}\&\mathcal{F}

cost. On SAM2 and STM, the write-side prune acts as an accuracy/efficiency knob: on SAM2 it trades 1.5

\mathcal{J}\&\mathcal{F}

points for +12% FPS; on STM it improves

\mathcal{J}\&\mathcal{F}

by 3.5 points while delivering the largest VRAM reduction in the suite (30.2% relative to Vanilla).

$\rho$	$\mathcal{J}\&\mathcal{F}$	fps	vram (MB)	$\|\mathcal{K}_{r}^{(t)}\|_{\mathrm{max}}$
$0.2$	0.846	74.0	648	819
$0.3$	0.849	69.7	655	1228
$0.5$	0.852	58.4	681	2048
$0.7$	0.853	49.1	712	2867
Vanilla ( $\rho{=}1.0$ )	0.862	37.2	845	4096

Table 4: Keep-ratio sweep on XMem [ 7 ] (DAVIS-17 [ 18 ] )

\mathcal{J}\&\mathcal{F}

stays within a

0.7

point band (

0.846

–

0.853

) across

\rho\in[0.2,0.7]

, while fps drops by

1.5\times

and vram grows by

10\%

\rho

increases. The geometric prior already confines

\mathcal{K}_{r}

to the cells relevant to attention readout; higher

\rho

admits only background tokens. We adopt

\rho{=}0.3

throughout as the point that maximises efficiency at near-optimal

\mathcal{J}\&\mathcal{F}

Config	$D_{w}$	$\mathcal{J}\&\mathcal{F}$	fps	vram (MB)
Vanilla SAM2	—	0.882	9.6	1809
Read-side only	—	0.812	10.2	1805
+ write-side (aggressive)	12	0.785	13.6	1772
+ write-side (default)	24	0.797	11.4	1791

Table 5: Write-side dilation sweep on SAM2 [ 20 ] (DAVIS-17 [ 18 ] val ). Larger

D_{w}

keeps more positions per stored frame and trades FPS for

\mathcal{J}\&\mathcal{F}

. The

D_{w}{=}24

row is the configuration used in Table 1 .

Video Object Segmentation

Video object segmentation assigns pixel-level masks to objects across frames while preserving their identities through motion, occlusion, and change.

See all 114 papers

Unified Spatio-Temporal Token Scoring for Efficient Video VLMs
Mar 18, 2026Jianrui Zhang, Yue Yang, Rohun Tripathi +5Visual Token Pruning Efficient VLM Inference
University of Wisconsin-Madison · Allen Institute for AI
STAC: Selective Spatiotemporal Aggregation and Compression for Video Reasoning Segmentation
Jul 3, 2026Syed Ariff Syed Hesham, Yun Liu, Guolei Sun +4Video Reasoning Reasoning Segmentation
School of EEE, Nanyang Technological University, Singapore · Institute for Infocomm Research, A*STAR, Singapore · VCIP, CS, Nankai University, Tianjin, China +4
Video Patch Pruning: Efficient Video Instance Segmentation via Early Token Reduction
Apr 1, 2026Patrick Glandorf, Thomas Norrenbrock, Bodo RosenhahnVideo Instance Segmentation Visual Token Pruning
Institute for Information Processing (tnt), L3S - Leibniz University Hannover, Germany

Mar 18, 2026J/K move · Enter open · S save

Unified Spatio-Temporal Token Scoring for Efficient Video VLMs

Jianrui Zhang, Yue Yang, Rohun Tripathi, Winson Han+4

University of Wisconsin-Madison · Allen Institute for AI

Visual Token Pruning Efficient VLM Inference Temporal Video Understanding

Open paper AskPDF arXiv

Token pruning is essential for enhancing the computational efficiency of vision-language models (VLMs), particularly for video-based tasks where temporal redundancy is prevalent. Prior approaches typically prune tokens either (1) within the vision transformer (ViT) exclusively for unimodal perception tasks such as action recognition and object segmentation, without adapting to downstream vision-language tasks; or (2) only within the LLM while leaving the ViT output intact, often requiring complex text-conditioned token selection mechanisms. In this paper, we introduce Spatio-Temporal Token Scoring (STTS), a simple and lightweight module that prunes vision tokens across both the ViT and the LLM without text conditioning or token merging, and is fully compatible with end-to-end training. By learning how to score temporally via an auxiliary loss and spatially via LLM downstream gradients, aided by our efficient packing algorithm, STTS prunes 50% of vision tokens throughout the entire architecture, resulting in a 62% improvement in efficiency during both training and inference with only a 0.7% drop in average performance across 13 short and long video QA tasks. Efficiency gains increase with more sampled frames per video. Applying test-time scaling for long-video QA further yields performance gains of 0.5-1% compared to the baseline. Overall, STTS represents a novel, simple yet effective technique for unified, architecture-wide vision token pruning.

Abstract

Video Object Segmentation

Explore similar work

Unified Spatio-Temporal Token Scoring for Efficient Video VLMs

STAC: Selective Spatiotemporal Aggregation and Compression for Video Reasoning Segmentation

Video Patch Pruning: Efficient Video Instance Segmentation via Early Token Reduction