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

1 Ablations for attention-based clustering: In practice, we find that the success rate is not very sensitive to this hyperparameter. We evaluate different choices and find the results reasonable, except for using only 1 layer. As the attention distribution is relatively uniform in the first layers. We set this threshold of using 1/10 layers to make a trade-off between latency and success rate.

2 CLIP Dependency: The core idea of semantics-aware retrieval is that we need to remove redundant information before giving the environment description to the LLM planner, thus leading to success rate improvement (Section 3.1 and 3.4). Here, we select CLIP to remove redundant information and select relevant groups because CLIP is widely used in semantic matching [1, 2, 3]. In fact, other semantic matching models can also be used and show reasonable performance (e.g.,all-mpnet-base-v2, all-MiniLM-L6-v2), showing the robustness of our method. We also compared our method with the position-based method (select groups according to average object distance) and the LLM-based method (remove redundant information and select final sub-goal both using LLM). For the position-based method, we evaluate both considering/not considering device memory capacity in memory retrieval, which is discussed in Line 223. Position-based method shows a low success rate as it does not consider semantics. And the LLM-based method shows high real-time latency because of the high computation cost, with no significant success rate improvement. This is because CLIP is enough to remove most of the redundant information and keep the most relevant groups. Even if a little redundant information is kept, the LLM planner can exclude them in sub-goal selection. So a light-weight semantic matching model is important.

3 Evaluation on efficient LLM inference methods: Our discrete memory caching method is similar to sparse attention methods. As there is no existing sparse attention method that focuses on navigation, we compare with general adaptive sparse attention methods. There is a core difference between general adaptive sparse attention and EfficientNav: EfficientNav clusters objects into different groups and calculates the attention of each group individually. This structured sparse approach can decouple the group order and KV cache computation of each group, thus enabling KV reuse when we retrieve different groups in navigation planning. However, for general adaptive sparse attention methods, their purpose is to minimize the difference between sparse attention and full attention, and accelerate the attention calculation. But without memory retrieval, even full attention shows a low success rate, as discussed in Section 3.1. At the same time, without discrete memory caching, these methods need to recompute the KV cache of the navigation map description because of map changes, thus showing longer real-time latency.

We conduct experiments to compare these sparse attention works with our method. Our method outperforms all the baselines. We will cite all these papers and compare them with EfficientNav in our final version.

4 Lack of real-world deployment: Although we did not evaluate on a real-world robot, we deployed our model on the computation platform (Jetson Orin) that is frequently used by real-world robots, as our method mainly solves the problem of high computation cost in prefilling by optimizing KV cache management. And we would like to clarify that simulation-based evaluation is also a widely used practice in object-goal navigation research, as seen in many prior works (e.g., [4, 5, 6]). Our experimental setup follows the same standard, ensuring fair comparison with existing methods while maintaining reproducibility.

5 Effectiveness of Discrete Memory Caching: only using discrete memory caching will not affect the success rate much, and the SR improvement is just a statistical deviation.

6 Effectiveness Attention-based memory Clustering: the planning performance is highly related to the objects selected for the planner. And the object selection is related to (1) how to cluster objects and (2) how to select groups.

As discussed in Line 322, in LLaVA planner baseline, we also cluster objects and select groups based on position, following [4, 7] (when not using selection, the success rate is only 36.7% caused by the redundant information). However, as the selected objects have poor correlation with each other, the success rate is still low whether using full attention or discrete attention. After attention-based memory clustering is used, objects in each selected group have high correlation, which helps the LLM to better understand the environment and reduces the impact of ignoring cross-attention at the same time, thus improving the success rate. When using semantics-aware memory retrieval, we can select the most related groups, which further improves the success rate. And our semantic-aware memory retrieval considers memory capacity, which is not considered by [4, 7], thus showing lower real-time latency. We will add the detailed explanation in our final version.

7 The changes of groups: We conduct object clustering based on both semantics and position. As discussed in Section 3.3, we use the LLM attention distribution to cluster the groups. When new objects are detected, we input the information of existing groups and the newly detected objects into LLM. The information contains both semantics and positions of the groups/objects. And we infer a few layers of the LLM and cluster object based on the attention score between newly detected objects and existing groups. This can reduce the difference between discrete attention and full attention. In conclusion, we use the attention of LLM itself to cluster the newly detected objects into different groups, both considering semantics and positions. We also evaluate clustering only based on position (cluster the new object into the nearest group) and semantics (use CLIP to calculate the similarity between new objects and existing groups), and we find our attention-based method achieves the best performance.

It is true that some semantically related but spatially distant objects can be clustered in a group, e.g., objects in two different bathrooms. However, this is reasonable as these objects are usually both relevant/irrelevant to the current task. In the planning process, both the position and semantics of each selected object will be given to the LLM, and the LLM will analyze the environment and choose only one object as sub-goal. We will add a figure to show an example of grouping updating in our final version, as adding figures in rebuttal is not allowed.

[1]Wu, Xiaoshi, et al. "Cora: Adapting clip for open-vocabulary detection with region prompting and anchor pre-matching."

[2]Zhang, Beichen, et al. "Long-clip: Unlocking the long-text capability of clip."

[3]Dorbala, Vishnu Sashank, et al. "Clip-nav: Using clip for zero-shot vision-and-language navigation."

[4] Shah, Dhruv, et al. "Navigation with large language models: Semantic guesswork as a heuristic for planning."

[5] Long, Yuxing, et al. "Instructnav: Zero-shot system for generic instruction navigation in unexplored environment."

[6] Wu, Pengying, et al. "Voronav: Voronoi-based zero-shot object navigation with large language model."

[7]Zhang, Junbo, and Kaisheng Ma. "MG-VLN: Benchmarking Multi-Goal and Long-Horizon Vision-Language Navigation with Language Enhanced Memory Map."

1 Model architecture confusion: We use grounding-dino as our detection model. While the choice of detection model impacts the semantic map's accuracy, it does not affect the core contribution or the primary problem addressed in this paper. Here we choose 3 detection models to evaluate our system, and the final success rate does not change much. Note that we mainly focus on the planning process of object navigation, which represents the primary efficiency bottleneck, rather than the perception process. We will clearly explain this in our final version.

Here we re-explain the working process of our navigation system. First, as shown in Figure 2, using detection models in the navigation process, we can construct a navigation map and add newly detected objects into the map in each navigation step. The navigation map records the semantics and position of each object. Second, as shown in Figure 5, we use attention-based memory clustering to cluster each newly detected object into related groups. This can reduce the impact of ignoring cross-attention between different groups. Third, also shown in Figure 5, we retrieve groups related to the current goal object, and feed the information of these groups into the LLM planner as prompt. Then, we load the KV cache of related groups calculated by discrete memory caching to avoid re-computation, and the KV cache of newly detected objects in retrieved groups is calculated. Finally, the LLM planner generates the next sub-goal.

2 Basis for clustering groups: As discussed in Section 3.3, we use the LLM attention distribution to cluster the groups. When new objects are detected, we input the information of existing groups and the newly detected objects into LLM. The information contains both semantics and positions of the groups/objects. And we infer a few layers of the LLM and cluster object based on the attention score between newly detected objects and existing groups. This can reduce the impact of ignoring cross-attention between groups. In conclusion, we use the attention of LLM itself to cluster the newly detected objects into different groups, both considering semantics and positions. We also evaluate clustering only based on position (cluster the new object into the nearest group) and semantics (use CLIP to calculate the similarity between new objects and existing groups), and we find our attention-based method achieves the best performance.

3 Node represents: in this figure, one node does not represent only one object. To be specific, multiple objects related to one node only means that these objects are near the same place. It does not mean all these objects are at the center of the node. Instead, there is some distance between them, so we can visit different objects related to the same node separately. Many existing works use a similar representation manner [3, 4, 5, 7].

4 The way sub-goal is selected: the final sub-goal is selected by the LLM planner. To be specific, the sub-goal is determined in a two-step manner: first, we select the relevant groups. Second, we select a sub-goal in the relevant groups. Both steps are important because if we directly select the final sub-goal among all groups, the planning performance will drop because of the huge amount of redundant information, as discussed in Section 3.1.

For the first step, we use CLIP to select relevant groups for better efficiency, as the task of removing redundant information is much easier than finding a specific sub-goal. For the second step, we use LLM to select the final sub-goal among the relevant groups. We also evaluate the result when using CLIP or LLM in both steps. When both are using CLIP, the accuracy drops a lot, as CLIP has a lower reasoning ability than LLM. When both are using LLM, the real-time latency becomes very long, as LLM shows higher inference latency than CLIP. And there is no significant success rate gain, as the CLIP model is enough to select relevant groups.

5 Evaluation environment limited: we would like to clarify that EfficientNav is specially designed for indoor navigation. We highlight that indoor navigation is an important research area, and is adopted in many applications, such as household robots and healthcare robots. Many existing works also focus on indoor navigation [1, 2, 3, 4, 5, 6, 7]. And simulation-based evaluation is also a widely used practice in object-goal navigation research, as seen in many prior works (e.g., [1, 2, 3, 4, 5, 6, 7]). Our experimental setup follows the same standard, ensuring fair comparison with existing methods while maintaining reproducibility.

[1] Shah, Dhruv, et al. "Navigation with large language models: Semantic guesswork as a heuristic for planning."

[2] Long, Yuxing, et al. "Instructnav: Zero-shot system for generic instruction navigation in unexplored environment."

[3] Wu, Pengying, et al. "Voronav: Voronoi-based zero-shot object navigation with large language model."

[4]Chen, Jiaqi, et al. "Mapgpt: Map-guided prompting with adaptive path planning for vision-and-language navigation."

[5]Zhang, Sixian, et al. "Hierarchical object-to-zone graph for object navigation."

[6]Sun, Leyuan, et al. "Leveraging Large Language Model-based Room-Object Relationships Knowledge for Enhancing Multimodal-Input Object Goal Navigation."

[7]Zhou, Gengze, Yicong Hong, and Qi Wu. "Navgpt: Explicit reasoning in vision-and-language navigation with large language models."

• Thank you to clarify the model architecture and some details of model design, experiments.
• I will raise score to BA in this time.

1.1 Limited number of goal objects: we appreciate the reviewer's attention to our experimental setup. However, we would like to clarify that our work actually evaluates six object categories (toilet, TV, chair, sofa, bed, and plant), strictly following the setting in the HM3D dataset (in our paper, we only show three of the goals at Line 243 as an example). In addition, to show the robustness of our method, we show the success rate of each individual object goal here. As our method is actually open-vocabulary, we further evaluate 4 more object goals (table, door, sink, lamp) to show our generalization. The result shows that our method achieves a high success rate on all object goals.

1.2 MapGPT evaluation: we also evaluate MapNav on the HM3D ObjNav dataset. According to the following table, our method achieves 14.5% SR and 6.3% SPL improvements over MapGPT, as our method removes redundant information in the prompt using semantics-aware memory retrieval. We also achieve 7.0x real-time latency reduction by using memory caching and retrieval.

2 Lack of robot deployment: We utilize a Jetson Orin as the compute device, a common choice for on-board computing hardware in robotics, and conduct experiments within the Habitat simulator. Specifically, the simulator runs on a separate computer, sending sensor data to the Jetson Orin, which hosts the LLM planner. The Jetson Orin then generates the plan and transmits it back to the separate computer, forming a closed-loop system. We would like to clarify that simulation-based evaluation is a widely used practice in object-goal navigation research, as evidenced by many prior works (e.g., [1, 2, 3]). Our experimental setup follows the same standard, ensuring fair comparison with existing methods while maintaining reproducibility.

3 Evaluation on sparse attention approaches: the goals of general adaptive sparse attention and EfficientNav are different: EfficientNav clusters objects into different groups and calculates the attention of each group individually. This structured sparse approach can decouple the group order and KV cache computation of each group, thus enabling KV reuse when we retrieve different groups in navigation planning. However, for general adaptive sparse attention methods, their purpose is to minimize the difference between sparse attention and full attention and accelerate the attention calculation. But without memory retrieval, even full attention shows a low success rate, as discussed in Section 3.1. At the same time, without discrete memory caching, these methods need to recompute the KV cache of the navigation map description because of map changes, thus showing longer real-time latency.

We conduct experiments to compare these sparse attention works with our method. Our method outperforms all the baselines. We will cite all these papers and compare them with EfficientNav in our final version.

4 Lack of references: we thank the reviewer for their valuable suggestion to refer to these foundational works.

HOZ innovatively proposes a hierarchical object-to-zone (HOZ) graph to provide coarse-to-fine guidance for navigation robots in unseen environments, which is constructed from scene, zone, and object nodes, updated online based on real-time observations.

Based on HOZ, HOZ++ cleverly introduces an adaptive graph structure and heterogeneous graph fusion for the graph to further enhance object navigation performance.

LROGNav enhances navigation efficiency by integrating common-sense knowledge of object-to-room relationships extracted from large language models using both positive and negative chain-of-thought promptings, and by training a multi-channel Swin-UNet with multimodal inputs.

We also find a paper called Imagine Before Go, which introduces a Self-supervised Generative Map (SGM) and improves exploration efficiency by learning explicit contextual relationships between objects and environments through self-supervised training. It leveraging both episodic observations and general knowledge from Large Language Models to generate unobserved regions of local semantic maps.

Our method EfficientNav improves the efficiency of LLM-based object goal navigation by navigation map caching and retrieval. Different from these works, our method focuses on the computation and management of KV cache for the navigation map description. We use discrete memory caching to decouple the context order and KV cache computation. For object grouping, we use attention-based memory clustering to reduce the impact of ignoring cross-attention. These methods enable KV cache reuse and significantly accelerate the prefilling stage of LLM planning.

We will cite all these papers and compare them with EfficientNav in our final version.

5 Writing unclarity: we apologize for the writing unclarity. Here we re-explain how the LLM semantic space and 2D map are associated. First, as shown in Figure 2, using detection models in the navigation process, we can construct a navigation map and add newly detected objects into the map in each navigation step. The navigation map records the semantics and position of each object. Second, as shown in Figure 5, we use attention-based memory clustering to cluster each newly detected object into related groups. This can reduce the impact of ignoring cross-attention between different groups. Note that the clustering process is based on the LLM attention, which is not directly determined by the object position on the map. Third, also shown in Figure 5, we retrieve groups related to the current goal object, and feed the information of these groups into the LLM planner as prompt. Then, we load the KV cache of related groups calculated by discrete memory caching to avoid re-computation, and the KV cache of newly detected objects in retrieved groups is calculated. Finally, the LLM planner generates the next sub-goal. We will fix our writing in the final version.

[1] Shah, Dhruv, et al. "Navigation with large language models: Semantic guesswork as a heuristic for planning."

[2] Long, Yuxing, et al. "Instructnav: Zero-shot system for generic instruction navigation in unexplored environment."

[3] Wu, Pengying, et al. "Voronav: Voronoi-based zero-shot object navigation with large language model."

Thank you again for your supportive comments during the discussion phase and your kind indication to raise our score—we truly appreciate your recognition of our work.

As the scoring system remains open for a short while longer, the updated score might not have been reflected in the system yet. If this was intentional, we completely understand, but we just wanted to check in case it was an oversight. Once again, we truly appreciate your valuable comments and your willingness to support our paper.

Please feel free to disregard this note if you've already processed the update. We’re grateful for your time and consideration throughout this review process.

1 Related work referring: we thank the reviewer for their valuable suggestion to refer to these foundational works. SayNav novelly uses a grounding mechanism, building a 3D scene graph of the explored environment as input to LLMs, for generating feasible and contextually appropriate high-level plans for navigation. Our method EfficientNav improves the efficiency of LLM-based object goal navigation by navigation map caching and retrieval. Different from SayNav, our method focuses on the computation and management of KV cache for the navigation map description. We use discrete memory caching to decouple the context order and KV cache computation, which enables KV cache reuse. And we also use attention-based memory clustering to reduce the impact of ignoring cross-attention. We will cite these papers and compare them with EfficientNav in our final version.

2 Retrieval using knowledge graph: a knowledge graph can be used to augment our method, while our CLIP-based method is also necessary. Existing works attempt to use a knowledge graph to embed prior knowledge, such as object relationships, to guide the navigation in unseen environments. In the navigation process, a knowledge graph can provide correlated objects as auxiliary information to locate the target object [1, 2]. However, our CLIP-based method is still necessary in the following aspects:

(1) Better generalization: knowledge graph requires manually curated or statistically learned object co-occurrence priors. And the navigation performance is highly related to the built knowledge graph, limiting generalization to unseen objects/scenes. Some works combine knowledge graphs with online learning, while the graph is still based on a fixed initial graph [3]. While our CLIP-based method can enable zero-shot matching after large-scale pre-training. And our navigation map is totally built from scratch, which can better adapt our method to new scenes.

(2) High flexibility in similarity computation: in existing works, the knowledge graph is mainly used to evaluate the relationship between different objects. However, the CLIP-based method has higher flexibility, which can both evaluate object-object similarity and object-group similarity. Especially, the group is dynamic in our method, which further shows the flexibility of the CLIP-based method.

At the same time, Knowledge Graph Methods have their own strength:

(1) Better efficiency: CLIP requires text encoding and similarity computation, which will introduce extra latency. While a knowledge graph only queries a precomputed graph. However, in indoor navigation scenes, the number of groups and objects is not too large, and the latency caused by CLIP is not the bottleneck. So we use a CLIP-based method to pursue a higher success rate. We will consider using a knowledge graph in our future work for larger-scale navigation. Thank you for your insightful comments.

[1]Yang, Wei, et al. "Visual semantic navigation using scene priors."

[2]Xu, Nuo, et al. "Aligning knowledge graph with visual perception for object-goal navigation."

[3]Zhang, Sixian, et al. "Hierarchical object-to-zone graph for object navigation."