STEP-Nav: Spatial-Temporal Efficient Visual Token Pruning for Vision-and-Language Navigation with Large Language Models

Yantao Lu, Shiqi Sun, Ning Liu, Bo Jiang, Ying Zhang, J. Chen, Chenglie DuAAAI 2026 · DOI

TL;DR

STEP-Nav is a new framework that slashes the computational cost of Vision-and-Language Navigation (VLN) by pruning up to 66.7% of visual tokens while maintaining over 95% of the original model's performance. It achieves this through a dual-pronged approach: spatially removing irrelevant regions (like the sky or distant backgrounds) and temporally filtering redundant video frames, all while using a specialized fine-tuning strategy to keep the navigation logic sharp.

What Problem Does This Paper Address?

Vision-and-Language Navigation (VLN) is the "holy grail" of embodied AI: a robot must navigate an unseen environment by following natural language instructions (e.g., "Walk past the table and turn left at the couch"). Modern state-of-the-art systems use Large Language Models (LLMs) to process these instructions alongside sequences of ego-centric images.

However, there is a massive efficiency bottleneck. High-resolution, high-frequency video generates a mountain of "visual tokens" for the LLM to process. Most of these tokens are useless for navigation:

  1. Spatial Redundancy: Large portions of an image—like the ceiling, the sky through a window, or a distant wall—don't help the robot decide whether to turn left or right.
  2. Temporal Redundancy: In a high-frame-rate video, consecutive frames are nearly identical, providing little new information.

Existing pruning methods often focus on texture or general image classification, which fails to account for the specific geometric and task-oriented needs of a navigating robot.

Methods

The authors introduce STEP-Nav, which tackles redundancy at three levels:

  • Spatial-level Pruning: The system evaluates each image patch using two metrics:
  • Content-aware: It looks at attention weights from the transformer to see which patches the model "cares" about.
  • Distance-aware: Using depth data, it prioritizes closer objects. A chair two feet away is more critical for navigation than a mountain five miles away.
  • Temporal-level Pruning: It calculates the cosine similarity between the global descriptors of consecutive frames. If a new frame is too similar to the previous one (meaning the robot hasn't moved much or the view hasn't changed), the frame is dropped before it ever reaches the LLM.
  • Distortion-aware Fine-tuning: Pruning tokens can "confuse" a pre-trained model. To fix this, the authors use a specialized training loss that forces the model’s internal representations of the pruned input to align with the representations it would have had with the full input. This ensures the model retains its "common sense" even with sparse data.

Datasets

The researchers evaluated STEP-Nav on several industry-standard benchmarks:

  • R2R (Room-to-Room): Navigation in discrete environments (Matterport3D simulator).
  • RxR (Room-Across-Room): A more complex, multilingual dataset with longer paths and more detailed instructions.
  • VLN-CE: A version of R2R set in continuous environments (Habitat simulator), which is much closer to real-world physics.
  • Real-world Deployment: They also tested the system on a physical Scout-Mini robot equipped with an Azure Kinect camera and LiDAR to prove the method works outside of simulations.

Key Insights and Ideas

  • Navigation is Geometric: Unlike standard image recognition, navigation is inherently about proximity. By incorporating a "distance-aware" score, STEP-Nav recognizes that "near" is usually "important."
  • Feature Alignment is Crucial: You can't just cut tokens and hope for the best. The "Distortion-aware" loss is the key to aggressive pruning; it essentially trains the model to "fill in the blanks" mentally, maintaining high Success Rates (SR) and Success weighted by Path Length (SPL).
  • Generalizability: The method isn't tied to one specific LLM. It showed consistent gains across different model scales, including NavGPT-2 (based on Flan-T5) and Navid-CE.

Key Results

  • Efficiency: STEP-Nav reduced the number of visual tokens by 66.7% (and up to 88.9% in some tests).
  • Performance Retention: On the R2R benchmark, the model retained over 95% of its original performance. For example, using the Navid-CE base, it achieved a 35.3% SPL with 66.7% pruning, compared to 35.9% with no pruning at all.
  • Outperforming Baselines: STEP-Nav consistently beat other popular pruning methods like ToMe (Token Merging) and VisionZip, especially at high sparsity levels where other methods' accuracy tended to "crash."
  • Real-world Success: In physical office and bedroom environments, the pruned model maintained a success rate of 80-91%, proving the "sim-to-real" transfer is robust.

Limitations and Future Work

The authors identify one major area for improvement: the textual branch. While they aggressively pruned visual tokens, the long-form natural language instructions can also be redundant or contain "fluff" that doesn't contribute to navigation.

Future work will likely explore "cross-modal pruning," where the system decides which visual tokens to keep based specifically on what the text instruction is looking for (e.g., if the instruction says "walk to the fridge," the system could prune everything that doesn't look like a kitchen or a fridge).

Summary updated

Abstract

Vision-and-Language Navigation (VLN) plays a critical role in tasks of embodied AI, particularly in unseen environments following natural language instructions. Recent advancements leverage large language models (LLMs) to improve the accuracy and generalizability of VLN systems by encoding image sequences as dense token representations. However, this tokenization approach incurs substantial computational overhead due to two key inefficiencies: 1) ego-centric camera views often include navigation-irrelevant re- gions (e.g., sky or distant backgrounds), and 2) high-frame-rate image sequences introduce temporal redundancy. To address these challenges, we propose Spatial-Temporal Efficient Visual Token Pruning (STEP-Nav), a unified frame- work that simultaneously prunes redundant visual tokens and fine-tunes VLN models to preserve navigation performance. In particular, STEP-Nav incorporates a distance- and content-aware token evaluation mechanism to remove irrelevant tokens at the spatial level, along with temporal level similarity-based filtering to reduce redundancy across sequential frames. To ensure pruning does not harm task performance, we introduce a distortion-aware fine-tuning strategy that aligns pruned-token representations with their full-token counterparts while maintaining navigation accuracy. Experiments on the R2R and RxR benchmarks using Navid-CE and NavGPT-2 as base models demonstrate that STEP-Nav preserves over 95% of the performance while reducing 66.7% of tokens, outperforming existing token pruning baselines.
BibTeX
@inproceedings{lu2026step,
  author = {Yantao Lu and Shiqi Sun and Ning Liu and Bo Jiang and Ying Zhang and J. Chen and Chenglie Du},
  title = {{STEP-Nav: Spatial-Temporal Efficient Visual Token Pruning for Vision-and-Language Navigation with Large Language Models}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2026},
  doi = {10.1609/aaai.v40i29.39588},
}
Figure