💻 computer science

FreqCache: Accelerating Embodied VLN Models with Adaptive Frequency-Guided Token Caching

This paper introduces FreqCache, a training-free framework that accelerates Vision-Language-Navigation models by leveraging frequency-domain analysis to overcome the limitations of existing visual-domain token caching methods, achieving a 1.59x speedup with negligible overhead.

Original authors: Zihao Zheng, Xingyue Zhou, Zhihao Mao, Songyu Sun, Lingyue Zhang, Yulong Ao, Yupu Feng, Qiongqiong Zhang, Yonghua Lin, Xiang Chen

Published 2026-04-28

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Zihao Zheng, Xingyue Zhou, Zhihao Mao, Songyu Sun, Lingyue Zhang, Yulong Ao, Yupu Feng, Qiongqiong Zhang, Yonghua Lin, Xiang Chen

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are teaching a robot to navigate a house based on spoken instructions like "Walk to the kitchen and turn left." To do this safely, the robot has to constantly look at the world, think about what to do next, and move. This "thinking" process is incredibly heavy on the computer's brain, making the robot slow and sluggish.

The paper introduces a clever trick called FreqCache to make this robot think faster without losing its way. Here is how it works, explained simply:

The Problem: The Robot's "Short-Term Memory"

To save time, computers often try to reuse old thoughts. If the robot sees a hallway that looks exactly the same as it did a second ago, it shouldn't need to re-calculate the whole picture; it can just say, "I've seen this before, I know what to do." This is called Token Caching.

However, the old ways of doing this were like trying to match photos by looking at the exact same spot on the photo.

The "Moving Camera" Problem: If the robot turns its head slightly, the whole picture shifts. Old methods would think, "This is a totally new picture!" and waste time re-calculating everything, even though it's just the same hallway seen from a slightly different angle.
The "Blind Spot" Problem: Robots need to be careful about edges (like the sharp corner of a table or a door frame) so they don't crash. Old methods were "edge-blind." They might think a door frame looks similar to the last second and decide to reuse that thought, leading the robot to walk right into the door.
The "Rigid Budget" Problem: Some rooms are simple (a long empty hallway), while others are messy (a living room full of toys). Old methods used a fixed rule for how much to save, regardless of how complex the room was. They would either save too little in a simple room (wasting time) or save too much in a complex room (risking a crash).

The Solution: FreqCache (The "Frequency" Detective)

The authors realized that instead of looking at the picture (the visual domain), they should look at the vibrations inside the picture (the frequency domain). Think of it like listening to a song instead of looking at the sheet music.

They built a system with three special tools:

1. The "Shift Detector" (Handling Viewpoint Migration)

The Analogy: Imagine a pattern on a rug. If you slide the rug one inch to the right, the pattern looks different if you only look at the corners. But if you look at the vibrations of the pattern, the "beat" stays exactly the same; only the timing of the beat shifts.
How it works: FreqCache looks at the "beat" (amplitude) of the image. It realizes, "Ah, the beat is the same, just shifted in time." It knows exactly how much the robot moved and aligns the old thoughts perfectly with the new view. It stops wasting time re-calculating things that just moved.

2. The "Edge Alarm" (Handling Critical Edges)

The Analogy: A smooth wall is like a low, steady hum. A sharp edge (like a door frame) is like a sudden, high-pitched screech.
How it works: FreqCache listens for those high-pitched screeches (high-frequency energy). If it hears a screech, it knows, "Wait, there's a sharp edge here! Do not reuse the old thought; we need to look at this fresh to avoid crashing." It automatically refreshes the memory for dangerous spots while keeping the safe, smooth spots cached.

3. The "Complexity Meter" (Handling Temporal Variation)

The Analogy: Imagine a room full of noise. A quiet hallway is like a single, clear note. A messy living room is like a chaotic orchestra playing many instruments at once.
How it works: The system measures the "chaos" (spectral entropy) of the room.
- Simple Room (Low Chaos): "This is easy! Let's reuse 80% of our old thoughts to go super fast."
- Complex Room (High Chaos): "This is messy and dangerous! Let's only reuse 20% and think hard about the rest to stay safe."
- This allows the robot to speed up in easy spots and slow down carefully in hard spots, all automatically.

The Results

By using these frequency-based tricks, the robot became 1.59 times faster (almost double the speed) without needing any extra training.

It didn't crash more often (accuracy stayed the same).
The extra "thinking" required to do these frequency checks was tiny (less than 3 milliseconds), so the speed gain was almost pure profit.

In short, FreqCache is like giving the robot a pair of glasses that lets it see the structure and danger zones of a room instantly, allowing it to skip unnecessary thinking steps while staying perfectly safe.

1. Problem Statement

Vision-Language-Navigation (VLN) models achieve high navigation accuracy but suffer from significant computational overhead due to repeated, expensive model inference at every timestep. While Token Caching (reusing visual token computations across time steps) is a promising training-free acceleration strategy, existing methods rely on visual domain similarity metrics which fail in embodied navigation scenarios due to three critical limitations:

Viewpoint Migration: Navigation involves continuous robot movement, causing spatial shifts in image patches. Visual domain methods rely on position-wise matching; when a patch moves (e.g., from coordinates $(i, j)$ to $(i+\Delta x, j+\Delta y)$ ), visual similarity drops drastically, causing the system to miss cacheable tokens and recompute them unnecessarily.
Edge Unawareness: Critical navigation decisions depend on fine-grained edges (e.g., door frames, obstacles). Visual similarity metrics often treat these edges as "stable" background if the global image is similar, leading to the erroneous caching of edge-related tokens. This causes the robot to miss dynamic obstacles, increasing collision risks.
Temporal Variation: Scene complexity fluctuates over time (e.g., moving from a simple hallway to a complex living room). Existing methods use static cache budgets, failing to adapt to these dynamic changes. They either waste computation in simple scenes or fail to refresh enough tokens in complex scenes.

2. Methodology: The FreqCache Framework

The authors propose FreqCache, a framework that shifts token caching logic from the visual domain to the frequency domain. They leverage the inherent mathematical properties of frequency analysis to solve the three challenges above.

The framework consists of three core modules:

Module I: Migration-Aware Token Cache Establishment

Problem Solved: Viewpoint Migration.
Mechanism: Utilizes the Fourier Shift Theorem, which states that spatial translation in the image domain corresponds to a linear phase shift in the frequency domain, while the amplitude spectrum remains invariant.
Implementation:
- Computes the 2D Fast Fourier Transform (FFT) of consecutive frames.
- Calculates similarity based on the amplitude spectrum ( $Sim_{freq}$ ), which remains high even if the viewpoint shifts.
- Uses phase correlation to calculate the precise spatial displacement $(\Delta i, \Delta j)$ between frames.
- Generates an alignment mask to identify which tokens have shifted but are still structurally identical, allowing them to be reused despite positional changes.

Module II: Edge-Information-Related Token Identification

Problem Solved: Edge Unawareness.
Mechanism: Exploits the fact that edges correspond to high-frequency components in the spectrum, while smooth backgrounds correspond to low frequencies.
Implementation:
- Applies block-wise 2D Discrete Cosine Transform (DCT) and a high-pass filter to isolate high-frequency energy.
- Calculates the energy spectrum $E(i,j)$ for each patch.
- Uses a statistically adaptive threshold (based on mean and standard deviation of energy) to identify patches with critical edges.
- Action: Tokens containing high-frequency energy (edges) are forced to refresh (evicted from cache), preventing the reuse of potentially dangerous obstacle information.

Module III: Temporal Adaptive Cache Budget Determination

Problem Solved: Temporal Variation.
Mechanism: Uses Spectral Entropy as a proxy for scene complexity.
- Simple scenes (e.g., hallways) have concentrated low-frequency energy $\rightarrow$ Low Spectral Entropy.
- Complex scenes (e.g., living rooms) have diffuse high-frequency energy $\rightarrow$ High Spectral Entropy.
Implementation:
- Calculates spectral entropy $\Psi_t$ for the current frame.
- Maps entropy to a dynamic reuse ratio $\alpha_t$ using a monotonically decreasing exponential function: $\alpha_t = \alpha_{min} + (\alpha_{max} - \alpha_{min})e^{-\Psi_t}$ .
- Result: Aggressive token reuse in simple scenes (low entropy) and conservative reuse (high refresh rate) in complex scenes (high entropy).

System Implementation

Hardware: Implemented on NVIDIA GPUs using PyTorch and CUDA.
Parallelism: The framework runs three parallel processes:
1. VLN Model Inference (Tensor Cores).
2. Frequency Domain Processing (FFT/DCT/Entropy on CUDA Cores).
3. Token Selection and Synchronization.
Overhead: The frequency processing adds negligible latency (< 2.54ms per step) compared to the savings from caching.

3. Key Contributions

Theoretical Insight: The paper reveals that the frequency domain is superior to the visual domain for VLN token caching. It demonstrates that frequency properties (amplitude invariance to translation, high-frequency edge isolation, and spectral entropy for complexity) directly address the specific failure modes of visual-domain caching.
FreqCache Framework: A novel, training-free, plug-and-play framework that integrates migration-aware alignment, edge-aware eviction, and entropy-driven budget adaptation.
Hardware Optimization: A detailed system-level implementation on GPUs that overlaps frequency analysis with model inference, ensuring the frequency modules do not become a bottleneck.

4. Experimental Results

Experiments were conducted on the R2R-CE dataset using an InternVLA-N1 (7B parameter) model.

Speedup: FreqCache achieves a 1.59× speedup in inference time (reducing latency from 637ms to 401ms per step).
Accuracy: It maintains high navigation performance with negligible degradation:
- Oracle Success (OS): 76.0% (Highest among all methods).
- Success Rate (SR): 63.0%.
- Success weighted by Path Length (SPL): 57.2%.
Comparison:
- Outperforms the SOTA visual-domain method (VLN-Cache) which suffers from accuracy drops due to viewpoint migration and edge errors.
- Outperforms a "Naive Frequency" baseline (which only uses amplitude similarity without edge/entropy logic) by a significant margin, proving the necessity of the three specific modules.
Ablation Study:
- Removing Module I (Migration) caused a 2.8% drop in SR.
- Removing Module II (Edges) caused a 4.2% drop in SR and increased collision risk.
- Removing Module III (Adaptive Budget) reduced efficiency, showing that static budgets are suboptimal.

5. Significance

FreqCache represents a paradigm shift in optimizing embodied AI models. By moving from spatial/visual heuristics to frequency-domain analysis, it solves the fundamental mismatch between static caching strategies and dynamic navigation environments.

Safety: It explicitly prevents the caching of critical edge information, directly addressing safety concerns in robotics.
Efficiency: It enables real-time deployment of large VLMs on robots by drastically reducing inference latency without retraining the model.
Generalizability: The approach is training-free and modular, suggesting it can be applied to other embodied AI tasks involving temporal visual streams.