History-Conditioned Spatio-Temporal Visual Token Pruning for Efficient Vision-Language Navigation

This paper proposes a training-free, plug-and-play spatio-temporal visual token pruning framework that significantly reduces computational latency for Vision-Language-Action based navigation while preserving high accuracy, as validated by both benchmark experiments and real-world deployment on a quadruped robot.

The Gist

Imagine you are trying to teach a robot dog how to navigate your house based on a voice command like, "Walk down the hall, turn left at the red backpack, and stop in front of the water fountain."

To do this, the robot uses a super-smart brain (a large AI model) that looks at the world through its eyes (cameras) and listens to your voice. However, there's a problem: this brain is too heavy.

Every time the robot looks at a new scene, the AI breaks the image into thousands of tiny puzzle pieces called "tokens." It tries to analyze every single piece at once, along with remembering every room it has seen in the past. This takes so much computing power that the robot moves in slow motion, like a turtle trying to run a marathon. By the time it decides where to step, the opportunity has passed.

This paper introduces a clever trick to make the robot fast again without making it "dumber." Here is how they did it, explained simply:

1. The Problem: The "Over-Thinker" Robot

Think of the robot's memory like a student taking a test.

• The Current View: The robot looks at the hallway right now.
• The History: The robot also remembers the kitchen it passed five minutes ago, the living room before that, and the front door.

The old way of doing things was to force the robot to stare at every single detail of the hallway and every single detail of the past rooms simultaneously. It was like trying to read a whole library of books while also trying to solve a math problem. The robot got overwhelmed, lagged, and couldn't react in real-time.

2. The Solution: The "Smart Editor"

The authors created a "Smart Editor" that sits in front of the robot's brain. This editor's job is to throw away the boring, useless information before the brain even sees it. But it has to be careful: if it throws away the wrong thing, the robot might walk into a wall.

They split the job into two parts:

Part A: The "Now" (Current View)

When the robot looks at the hallway right now, the editor uses a strategy called A-MMR (Adaptive Maximal Marginal Relevance).

• The Analogy: Imagine you are packing a suitcase for a trip. You don't want to pack 50 identical red shirts (redundancy), but you also don't want to pack nothing but socks (missing the main items).
• How it works: The editor picks the most important things first (like the "red backpack" or the "doorway"). Then, it looks for things that are different from what it already picked. It ensures the robot sees a mix of the most important landmarks and enough background context to know where it is, without seeing the same thing 100 times.

Part B: The "Then" (History/Memory)

This is the paper's secret sauce. The robot needs to remember the past, but it doesn't need to remember the past in high definition.

• The Analogy: Imagine you are telling a story to a friend. You don't need to describe the color of the wallpaper in the room you were in three years ago. You just need to remember, "I was in the kitchen, then I walked to the hall."
• How it works: The editor looks at what the robot is seeing right now (the "Query"). It asks the history: "Does this old memory help me understand where I am going now?"
  • If the robot is currently looking at a hallway, the editor keeps the memory of the "kitchen door" because it helps explain the path.
  • It throws away the memory of the "ceiling fan in the bedroom" because it's irrelevant to the current task.
  • It compresses the history into a tiny, efficient summary, saving massive amounts of brain power.

3. The Result: Fast, Smart, and Ready to Go

The best part? They didn't have to retrain the robot.
Usually, if you want to make an AI faster, you have to teach it all over again, which takes weeks and huge computers. This method is "plug-and-play." It's like putting a turbocharger on a car without rebuilding the engine. You just snap it on, and the car goes faster.

What happened when they tested it?

• Speed: The robot became much faster. It could process instructions in real-time.
• Accuracy: Even when they threw away 90% of the visual data (keeping only the top 10%), the robot was still better at navigating than other methods. It didn't get lost; it just stopped wasting time on useless details.
• Real Life: They tested this on a real Unitree Go2 robot dog. The dog could follow instructions like "Go past the trash can and stop at the bike" in a real office environment without lagging or crashing.

Summary

Think of this paper as teaching a robot to stop overthinking.
Instead of trying to memorize every leaf on every tree it has ever seen, the robot learns to focus on the "signs" (landmarks) that matter for the current task and summarizes its past journey into a quick mental note. This allows it to run, jump, and navigate the real world instantly, just like a human would.

Technical Summary

Here is a detailed technical summary of the paper "History-Conditioned Spatio-Temporal Visual Token Pruning for Efficient Vision-Language Navigation."

1. Problem Statement

Vision-Language Navigation (VLN) enables embodied agents (robots) to follow natural language instructions in visually grounded environments. Recent Vision-Language-Action (VLA) models have shown strong performance in this domain but suffer from high computational costs due to their transformer-based architectures. This creates a latency bottleneck that hinders real-time, closed-loop decision-making on physical robots.

While vision token pruning (reducing the number of visual tokens processed) is a common acceleration technique, existing methods are largely designed for single-image or reactive settings. They fail to address the unique spatio-temporal structure of VLN, where agents rely on historical observations (not just the current frame) to make long-horizon decisions. Current pruning strategies often treat all frames uniformly or ignore the specific redundancy patterns between past and present views, leading to significant performance degradation under aggressive pruning ratios.

2. Methodology

The authors propose a training-free, plug-and-play spatio-temporal visual token pruning framework tailored specifically for VLA-based VLN. The method distinguishes between "current" and "history" frames, applying different pruning strategies to each to preserve critical navigation information while reducing redundancy.

The framework consists of four main stages:

A. Feature Extraction and Importance Computation

• Input: Both history frames and the current frame are encoded by the VLA's vision encoder.
• Base Importance ($I_{base}$): Instead of averaging attention scores, the method computes the cosine similarity between the global [CLS] token and spatial patch tokens. This highlights semantically salient regions (e.g., goals, obstacles).
• Normalization: Attention weights are normalized to a $[0, 1]$ range to serve as the base importance score.

B. Token Selection for Current Frame (Spatial Pruning)

• Strategy: Adaptive Maximal Marginal Relevance (A-MMR).
• Mechanism: Unlike standard MMR that relies on hard-coded splits, A-MMR uses a unified iterative formulation. At each step, it selects a token that maximizes a trade-off between:
  1. Semantic Importance: High base attention scores ($I_{base}$).
  2. Spatial Diversity: Low similarity to already selected tokens ($1 - \max sim$).
• Goal: To ensure the selected subset captures high-attention foreground objects while maintaining a diverse representation of the background context.

C. Token Selection for History Frames (Spatio-Temporal Pruning)

• Strategy: Query-Guided Re-weighting followed by A-MMR.
• Mechanism:
  1. Query Generation: The tokens selected from the current frame serve as queries ($Q$).
  2. Spatio-Temporal Relevance ($R$): For each history token, the method calculates its maximum similarity to any token in the current query set $Q$. This measures how relevant the historical memory is to the current view.
  3. Re-weighting: The final importance score for history tokens is modulated: $I_{final} = I_{base} \cdot (\alpha + (1-\alpha) \cdot R)$. This prioritizes history tokens that are both originally salient and currently relevant.
  4. Selection: A-MMR is applied to these re-weighted history tokens to construct a compact, non-redundant memory pool.

D. Action Prediction

• The pruned token sets (current and history) are fed into the projector and LLM of the VLA model to predict the navigation action sequence (e.g., Turn Left, Move Forward).
• Key Feature: The method requires no retraining or modification of pretrained model parameters, ensuring the integrity of the original representations.

3. Key Contributions

1. Novel Problem Formulation: The paper addresses the under-explored challenge of pruning tokens in history-conditioned VLN, explicitly modeling the spatio-temporal relationship between past and present views.
2. Training-Free Framework: Introduces a plug-and-play solution that distinguishes between spatial selection (current frame) and spatio-temporal compression (history frames) without fine-tuning the VLA model.
3. A-MMR Strategy: Proposes an Adaptive Maximal Marginal Relevance strategy that dynamically balances semantic saliency and diversity, outperforming static or text-guided pruning baselines.
4. Real-World Validation: Successfully deploys the method on a Unitree Go2 quadruped robot running on edge hardware (NVIDIA Jetson Thor), demonstrating low-latency performance in physical environments.

4. Experimental Results

The method was evaluated on standard benchmarks (Room-to-Room [R2R] and Room-Across-Room [RxR]) and compared against state-of-the-art pruning baselines: SparseVLM, DivPrune, and VisPruner.

• Performance (Accuracy):
  • Under a 90% pruning ratio on R2R, the proposed method achieved an SPL (Success weighted by Path Length) of 36.36%, significantly outperforming SparseVLM (31.08%), DivPrune (18.55%), and VisPruner (29.27%).
  • It maintained superior performance even as pruning ratios increased, showing robust preservation of critical visual information.
• Efficiency (Latency & Throughput):
  • At 90% pruning, the method reduced CUDA inference latency from 231.34 ms (unpruned) to 213.40 ms.
  • It achieved the highest inference throughput (4.68 FPS) among all pruning methods.
  • While DivPrune had lower FLOPs, it suffered from poor navigation accuracy, highlighting that the proposed method achieves a better accuracy-efficiency trade-off.
• Ablation Studies:
  • Confirmed that both diversity and semantic importance are necessary; using only one leads to performance degradation.
  • Found that token merging (keeping pruned tokens by merging them) is ineffective for VLN and often degrades performance compared to direct discarding, likely due to blurring fine-grained landmarks.
• Real-World Deployment:
  • On the Unitree Go2 robot, pruning reduced average inference time for a batch of actions from 1.43s to 1.25s, enabling smoother, continuous motion with minimal pauses.

5. Significance

This work bridges the gap between large-scale multimodal foundation models and the strict latency requirements of real-time embodied robotics. By acknowledging that VLN is a history-conditioned task, the authors developed a pruning strategy that is far more effective than generic vision acceleration techniques. The training-free, plug-and-play nature of the solution makes it highly practical for deployment on existing VLA systems without the cost of retraining. The successful deployment on a quadruped robot validates that these efficiency gains translate directly to reliable, low-latency operation in the physical world, paving the way for more agile and responsive autonomous agents.