EfficientNav: Towards On-Device Object-Goal Navigation with Navigation Map Caching and Retrieval

AI summary

Overview

Research area: Embodied AI / robot navigation — specifically object-goal navigation (ObjNav) using large language models as planners, with a focus on on-device (edge) deployment and efficient KV-cache management.

Technical level: Intermediate. The paper assumes familiarity with LLM inference (prefill vs. decode, KV cache), attention mechanisms, and standard embodied navigation benchmarks, but the core ideas are explained in accessible terms.

Scope: The paper proposes EfficientNav, a system that makes zero-shot, LLM-planner-based object-goal navigation runnable on local devices by caching, clustering, and selectively retrieving navigation-map memory instead of re-processing the full map on every planning step.

What This Paper Is About

Object-goal navigation asks a robot to find a specific object (e.g., a TV, chair, or sofa) in an environment it has never seen, using only the category name as instruction. The state of the art handles this zero-shot by asking a giant cloud LLM such as GPT-4 to act as a high-level planner over an online-built navigation map. The problem: those models must run in the cloud (adding latency, privacy risk, and cost), while simply swapping in a smaller local LLM causes large success-rate drops and long planning delays — so the goal of this paper is to make small, local LLMs plan as well as, or better than, GPT-4 while running efficiently on a device.

Key Contributions

1. Discrete memory caching — instead of storing the KV cache of the entire navigation-map description (which exceeds device memory), the map's objects are clustered into groups whose KV caches are computed independently, so the cache no longer depends on group ordering and does not need recomputation when different groups are retrieved.
2. Attention-based memory clustering — the LLM's own attention distribution over the first few layers is used to decide which newly detected objects belong in which group, reducing the accuracy loss caused by ignoring cross-attention between separately cached groups.
3. Semantics-aware memory retrieval — a lightweight CLIP model (around 100M parameters) scores each group's relevance to the current goal, and group selection is formulated as a knapsack problem under the device's KV-cache memory budget, pruning redundant map information so smaller LLMs can focus.
4. Extensive evaluation on the HM3D benchmark showing 11.1% success-rate improvement over GPT-4-based baselines, plus 6.7× real-time and 4.7× end-to-end latency reductions over a GPT-4 planner.

Main Findings

• Accuracy beats GPT-4-based planners: EfficientNav-34b reaches 80.0 SR and 41.5 SPL on HM3D, compared with 68.9 SR / 36.0 SPL for LFG (GPT-4), an 11.1% SR and 5.5% SPL improvement. EfficientNav-11b (LLaMA3.2-11b) reaches 74.2 SR and 39.5 SPL.
• Large gains over an unassisted local LLM planner: versus the naive LLaVA-34b planner (42.7 SR, 21.0 SPL), EfficientNav achieves 37.3% SR and 20.5% SPL improvements.
• Large gains over learning-based navigation: EfficientNav reports 18.0% SR and 14.7% SPL improvements over the prior-art OVRL method, with no training cost.
• Latency reduction versus cloud planning: On NVIDIA A6000, the GPT-4 planner takes 5.80s real-time latency and 59.34s end-to-end, while EfficientNav-11b takes 0.35s and 12.70s, and EfficientNav-34b takes 0.87s and 12.51s — 6.7× and 4.7× reductions respectively.
• Latency reduction versus other local serving: versus the naive LLaVA planner, EfficientNav gives 8.8× (LLaMA3.2-11b) and 6.5× (LLaVA-34b) real-time latency reduction, and 3.7× and 4.4× end-to-end reductions. Versus vllm, it reports 6.5× and 5.1× real-time reductions and 3.1× and 3.8× end-to-end reductions.
• Prefilling is the dominant cost that gets eliminated: discrete memory caching reduces the prefilling time of planning by around 20×, and latency stabilizes across navigation steps instead of growing with map size.
• Each component adds value (ablation, LLaVA-34b): naive planner 42.7 SR / 21.0 SPL / 5.63s / 55.32s; + discrete memory caching 43.1 / 21.0 / 2.42s / 36.94s; + attention-based memory clustering 63.3 / 34.2 / 2.32s / 32.58s; + semantics-aware memory retrieval 80.0 / 41.5 / 0.87s / 12.51s. Clustering contributes the largest success-rate jump; retrieval contributes the largest latency drop.
• Robustness to memory budget: with LLaVA-34b, 16GB gives 74.7 SR / 37.3 SPL / 0.59s / 14.24s; 24GB gives 79.0 / 39.1 / 0.71s / 14.29s; 32GB gives 80.0 / 41.5 / 0.87s / 12.51s; 40GB gives 80.3 / 41.9 / 0.93s / 11.72s. Very small budgets hurt success rate and end-to-end latency; very large budgets slightly increase real-time latency through longer prompts.
• Sparse-attention methods are not a substitute: Minference scores 35.3 SR / 18.0 SPL / 3.88s and FlexPrefill 36.7 / 20.1 / 3.02s, versus EfficientNav's 80.0 / 41.5 / 0.87s — because sparse attention still needs KV recomputation when the map changes and does not prune irrelevant map content.
• Cache hit rate rises with memory budget: the proportion of selected groups already resident in device memory increases with budget and quickly reaches a high level, since group semantics change little between adjacent planning steps.

Methodology in Plain English

The system runs a repeating loop: RGB-D sensor data is turned into object detections and positions by a detection model (Grounding Dino), those detections are added to a graph-based navigation map, and an LLM reads the map plus the goal and picks the next sub-goal. If the target object appears in the map, it becomes the goal; otherwise the LLM picks a promising object to walk to and the loop repeats.

The efficiency work sits inside the LLM's cache. Rather than feeding the entire map as one long prompt and recomputing its key-value cache each step, the researchers split map objects into groups and precompute each group's cache separately. Because each group has its own cache, the planner can drop, reorder, or add groups without invalidating the rest of the cache — new objects are simply appended to the end of a group. Groups are formed by running only the first portion of the LLM (about 1/10 of its layers) and checking whether a new object's average attention to an existing group exceeds a threshold.

At each planning step, a small CLIP model scores how similar each group is to the goal, and a knapsack formulation selects the set of groups that maximizes relevance while staying within the device's KV-cache memory budget. Only ~40 tokens are decoded per planning step, so loading the cache once per step rather than repeatedly is a large saving. The clustering and selection overheads are reported as negligible because clustering only uses the first few layers and CLIP inference is far cheaper than LLM inference.

Evaluation used the HM3D dataset in the Habitat simulator, with four models (LLaVA-7b, LLaVA-13b, LLaVA-34b, LLaMA3.2-11b) on an NVIDIA A6000 GPU and a Jetson Orin, reporting success rate (SR), success rate weighted by path length (SPL), real-time latency, and end-to-end latency.

Why This Matters

Impact on research. The paper reframes the ObjNav bottleneck: rather than making LLMs bigger, it argues that map-context redundancy is the problem, and that selectively caching and retrieving map memory lets a small model outperform a cloud giant. It also demonstrates that general sparse-attention acceleration and ObjNav-specific memory management solve different problems.

Real-world applications.

• Home and service robots that must find a requested object (keys, medication, a specific appliance) without a network connection.
• Warehouse and logistics robots that need to locate items or stations while keeping operational data on premises.
• Assistive robots for elderly or disabled users, where continuous cloud video upload raises privacy concerns.
• Search-and-rescue or inspection robots operating where cellular or cloud connectivity is unavailable or unreliable.

Industry relevance. The 32GB memory constraint of a Jetson AGX Orin and the reported latency numbers position the work directly against the economics of cloud LLM inference — removing communication time, per-token API cost, and data-egress concerns. The paper notes its technique is orthogonal to and compatible with quantization, pruning, and knowledge distillation, which matters for chip and edge-platform vendors building an on-device navigation stack.

Future Directions

• Closing the remaining gap between LLM inference speed and that of much smaller models — the authors explicitly list this as a limitation and warn that EfficientNav should be used carefully where extremely low real-time latency is required.
• Extending the caching and retrieval approach beyond graph-based navigation maps to other forms of accumulating context, or to other embodied task types.
• Combining EfficientNav's memory management with quantization, pruning, or distillation to see whether the combination shifts the achievable memory/accuracy trade-off further (the paper notes the techniques are orthogonal but does not evaluate the combination).
• Investigating how robust the attention-based clustering thresholds and relevance thresholds are across environments, since the paper shows success rate is sensitive to the KV-cache memory budget and that too small a budget causes relevant groups to be dropped.

Target Audience

Robotics and embodied-AI researchers working on zero-shot navigation; edge-computing and systems researchers interested in KV-cache management for on-device LLM serving; and practitioners building navigation or object-search robots on memory-constrained hardware such as the NVIDIA Jetson AGX Orin, who need to decide between cloud offloading and local inference.

Authors’ abstract

Object-goal navigation (ObjNav) tasks an agent with navigating to the location of a specific object in an unseen environment. Embodied agents equipped with large language models (LLMs) and online constructed navigation maps can perform ObjNav in a zero-shot manner. However, existing agents heavily rely on giant LLMs on the cloud, e.g., GPT-4, while directly switching to small LLMs, e.g., LLaMA3.2-11b, suffer from significant success rate drops due to limited model capacity for understanding complex navigation maps, which prevents deploying ObjNav on local devices. At the same time, the long prompt introduced by the navigation map description will cause high planning latency on local devices. In this paper, we propose EfficientNav to enable on-device efficient LLM-based zero-shot ObjNav. To help the smaller LLMs better understand the environment, we propose semantics-aware memory retrieval to prune redundant information in navigation maps. To reduce planning latency, we propose discrete memory caching and attention-based memory clustering to efficiently save and re-use the KV cache. Extensive experimental results demonstrate that EfficientNav achieves 11.1% improvement in success rate on HM3D benchmark over GPT-4-based baselines, and demonstrates 6.7x real-time latency reduction and 4.7x end-to-end latency reduction over GPT-4 planner. Our code will be released soon.