SG-Nav: Online 3D Scene Graph Prompting for LLM-based Zero-shot Object Navigation

Authors: hang  yin
xiuwei  xu
zhenyu  wu
jie  zhou
jiwen  lu
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-02 17:55:11

Abstract: In this paper, we propose a new framework for zero-shot object navigation.
Existing zero-shot object navigation methods prompt LLM with the text of spatially closed objects, which lacks enough scene context for in-depth reasoning.
To better preserve the information of environment and fully exploit the reasoning ability of LLM, we propose to represent the observed scene with 3D scene graph. The scene graph encodes the relationships between objects, groups and rooms with a LLM-friendly structure, for which we design a hierarchical chain-of-thought prompt to help LLM reason the goal location according to scene context by traversing the nodes and edges.
Moreover, benefit from the scene graph representation, we further design a re-perception mechanism to empower the object navigation framework with the ability to correct perception error.
We conduct extensive experiments on MP3D, HM3D and RoboTHOR environments, where SG-Nav surpasses previous state-of-the-art zero-shot methods by more than \textbf{10\%} SR on all benchmarks, while the decision process is explainable. To the best of our knowledge, SG-Nav is the first zero-shot method that achieves even higher performance than supervised object navigation methods on the challenging MP3D benchmark.
Code of this project will be released in the final version.

Main paper: 
 introduction: 
 Object navigation, which requires an agent to navigate to an object specified by its category in unknown environment [3] , is a fundamental problem in a wide range of robotic tasks. Thanks to the advancements in deep learning and reinforcement learning (RL), modular-based object navigation approaches [6; 32; 48] have achieved impressive performance in recent years, which caches the visual perception results of the RGB-D observation into semantic map and learns a policy to predict actions according to this map. However, conventional methods rely on time-consuming training in simulation environment, which only works well on specific datasets and can only handle limited categories of goal object.In order to solve above limitations and enhance the generalization ability of object navigation, zeroshot object navigation has received increasing attention. In the zero-shot setting, the system does not require any training or finetuning before applied to real-world scenarios, and the goal category can be freely specified by text in an open-vocabulary manner. Since training data is unavailable, recent zero-shot object navigation methods [46; 52] leverage large language models (LLM) [36; 1] instead of RL agent to perform decision-making processes, where the extensive knowledge in LLM helps to address various common-sense reasoning problems in zero-shot. In these works, the LLM is required to select a frontier for the agent to explore the unobserved area. As LLM cannot perceive the Figure 1 : Different from previous zero-shot object navigation methods [46; 52] that directly prompt LLM with text of nearby object categories, we construct a hierarchical 3D scene graph to represent the observed environment and prompts LLM to fully exploit the structure information in the graph. Our SG-Nav preserves fine-grained scene context and makes reasonable and explainable decisions. environment visually, they select the categories of objects near each frontier to prompt LLM and rate the possibility of each frontier. While these approaches achieve zero-shot object navigation, there are still some drawbacks in their design: (1) they prompt LLM with only the text of nearby object categories, which is less informative and lacks scene context such as spatial relationship; (2) they let LLM directly output the possibility for each frontier, which is an abstract task and does not fully utilizes the reasoning ability of the LLM. As a result, their reasoning process is not explainable and the performance is far from satisfactory.In this paper, we propose a new object navigation framework namely SG-Nav, which fully exploits the reasoning ability of LLM for zero-shot navigation planning with high accuracy and fast speed. As shown in Figure 1 , different from previous LLM-based object navigation framework that prompts LLM with only text of object categories and directly outputs probability, SG-Nav represents the complicated 3D environment in an online updated hierarchical 3D scene graph and utilizes it to hierarchically prompt LLM for reliable and explainable decision making. Benefit from the scene graph representation, we further design a graph-based re-perception mechanism to empower the object navigation framework with the ability to correct perception error. Specifically, we first construct an online 3D hierarchical scene graph along with the exploration of the agent. Since there are many levels and nodes in the scene graph, it is challenging to build the scene graph in real time. To solve this problem, we propose to densely connect the newly detected nodes to previous nodes in an incremental manner. We design a new form of prompt to control the computational complexity of this dense connecting process linear to the number of new nodes, which is followed by a pruning process to discard less informative edges. With the 3D scene graph, we divide it into several subgraphs and propose a hierarchical chain-of-thought to let LLM perceive the structural information in each subgraph for explainable probability prediction. Then we interpolate the probability of each subgraph to the frontiers for decision making, which can be further explained by summarizing the reasoning process for the most related subgraphs. Moreover, we also notice that previous object navigation framework fails when detecting out a false positive goal object. So we propose a graphbased re-perception mechanism to judge the credibility of the observed goal object by accumulating relevant probability of subgraphs. The agent will give up goal object with low credibility for robust navigation. We conduct extensive experiments on MP3D, HM3D and RoboTHOR environments. Our SG-Nav achieves state-of-the-art zero-shot performance on all benchmarks, surpassing previous top-performance zero-shot method by more than 10% in terms of SR. SG-Nav can also explain the reason for its decision at each step, making it more practical in human-agent interaction scenarios. Figure 2 : Pipeline of SG-Nav. We construct a hierarchical 3D scene graph as well as an occupancy map online. At each step, we divide the scene graph into several subgraphs, each of which is prompted to LLM with a hierarchical chain-of-thought for structural understanding of the scene context. We interpolate the probability score of each subgraph to the frontiers and select the frontier with highest score for exploration. This decision is also explainable by summarizing the reasoning process of the LLM. With the scene graph representation, we further design a re-perception mechanism, which helps the agent give up false positive goal object by continuous credibility judgement.. DD-PPO [38] implicitly encodes the visual observation into latent code and predicts low-level actions. Follow-up works increase the performance by better visual representation [29; 43] , auxiliary tasks [44] and data augmentation [26] . However, since this kind of methods implicitly encode 3D scene and directly predict actions, which may fail to capture fine-grained context. The end-to-end RL also suffers from low sampling efficiency. To solve these problems, modular-based methods map the visual perception results to BEV or 3D map [49; 42; 41] and update it online. The agent learns where to navigate with this semantic map [6; 32; 48] . In persuit of open-vocabulary object navigation, COWs [11] and ZSON [25] align the goal to CLIP embedding [30] . L3MVN [46] and ESC [52] further utilize large language models for zero-shot decision making. Our SG-Nav is also a LLM-based zero-shot framework. But differently, we propose to construct 3D scene graph instead of semantic map to prompt LLM with hierarchical chain-of-thought and graph-based re-perception, which better preserves the scene context and makes the decision more robust.Large Pretrained Models for Robotics: Large pretrained language models [1; 36] and visionlanguage models [30; 20; 23; 20; 21] have received increasing attention in recent years, which is widely applied in embodied AI tasks including navigation [17; 11; 25; 46; 52; 35; 13; 51] , task planning [2; 7; 16; 27; 4; 39; 33; 40] , manipulation [22; 14; 15; 47] . It is observed that large vision-language models becomes a good hand in dealing with embodied AI problems due to its end-to-end processing of images and language. NLMap [7] leverages CLIP embedding [30] to build an open-vocabulary map for task planning. Voxposer [15] automatically generates code to interacts with VLMs [28; 18] , which produces a sequence of 3D affordance maps and constraint maps to guide the optimization of path planning. However, it is still hard to process streaming RGB-D video for vision-language models. To better make use of the observed 3D scenes, recent methods [52; 51] of navigation describe the scene in pure text and utilize it to prompt LLM. Our SG-Nav, instead, represents the 3D scene using scene graph, which preserves much more context information. The proposed hierarchical chain-of-thought and graph-based re-perception methods can also better exploit the potential of LLM for object navigation. 
approach: 
 In this section, we first provide the definition of zero-shot object navigation and introduce the overall pipeline of SG-Nav. Then we describe how to construct an open-vocabulary and hierarchical 3D scene graph online. Finally we show how to prompt the LLM with 3D scene graph to achieve context-aware and robust object navigation.Problem Definition. A mobile agent is tasked with navigating to an object o specified by its category c in an unknown environment. The agent receives streaming RGB-D video as input along with its exploration and decides where to go until it finds the goal object. In this subsection, we first provide formal definition of our 3D scene graph. Then we detail how to construct the scene graph in real time and online. We densely connect newly registered nodes (purple) to all other nodes by efficiently prompting the LLM. We divide the edges into long edges and short edges and prune less informative ones with different strategies.Hierarchical 3D Scene Graph. A 3D scene graph describe the 3D scene with nodes and edges between these nodes. We define three kinds of nodes: object, group and room, to represent the scenes in different graininess. Here group indicates a set of related objects, such as a dining table and its surrounding chairs, TV and TV cabinet. Edge can exist between any pair of nodes. If two nodes are not in the same level (e,g, chair and living room), the edge between them represents affiliation (i.e. this chair belongs to this living room). If two nodes are in the same level, the edge represents the relationship between them, which can be spatial relationship such as on the top of between close objects, or functional relationship between far away objects like a TV and its opposite sofa.Incremental Updating and Pruning. Since there are many objects in the environment and the relationship between them are complicated, building the scene graph for the whole scene is time-consuming. To enable real-time online construction of the 3D scene graph, we propose to incrementally update it across frames. That is, at each time t, we register new nodes N t from the RGB-D observation, and connect these nodes with the previous scene graph G t-1 to acquire G t .We adopt different strategy to acquire different level of nodes. For object nodes, we leverage online open-vocabulary 3D instance segmentation method [12] to acquire the 3D instance. Formally, at each time t, the method detects and segments objects from the RGB-D observation and synchronously reconstruct the 3D point clouds for the environment. These newly detected objects will be matched with object nodes detected from the previous t -1 frames and merged into them. Objects that do not match with any previous one will be registered as a new object node. Each object node has a semantic category and its confidence score. Then group nodes are computed based on all object nodes up to time t. If two object nodes are connected by an edge and their categories are related, we register a group for them. This process will iterate until no new node can be assign to this group. We pre-define a dictionary to tell which pair of categories are related by LLM, which is detailed in Section 6.2. For room nodes, we follow the same paradigm for acquiring object nodes, where room is regarded as instance and thus we can prompt the open-vocabulary 3D instance segmentation model with the room type.We also design different strategies to build edges between the nodes of different levels. We first connect high-level nodes with their affiliated low-level nodes. For room-object node pair, we think the object belongs to the room if the instance mask of this object on the point clouds is contained in the instance mask of this room. For room-group node pair, we connect them if all objects in this group belongs to the room. We do not additionally connect group and object nodes since the former is registered based on the latter.Then we connect related object nodes to build intra-level edges, as shown in Figure 3 . Note there is no intra-level edges between group and room nodes. For newly registered object nodes at time t, we first densely connect them with all object nodes, and then perform pruning to remove less informative edges. We combine m newly registered nodes and n previous nodes to form m(m + n) edges. For each edge, we can prompt LLM with the categories of connected nodes and ask LLM to infer their relationship. However, traversing all m(m + n) edges and feed prompts to LLM requires O(m(m + n)) computational complexity. To speed up the dense connecting process for real-time processing, we propose a new format of prompt: Predict the most likely relationships between these pairs of objects:[{(a, b)|a ∈ S n , b ∈ S n ∪ S p }],where S n and S p are the set of m newly registered nodes and n previous nodes. This enables LLM to generate relationships between all pairs of nodes in one-shot with much less computational cost, for which we provide theoretical derivation below.According to [37] , complexity of processing L tokens for LLM is O(L r ), where 1 < r ≤ 2. Suppose L pro and L res represent the number of tokens of the prompt and LLM's response respectively.Then the computational complexity of processing m(m + n) pairs of nodes for our method and the naive O(m(m + n)) method areT our = O ((L pro + m(m + n) • L res + m(m + n) • 2) r )andT naive = m(m + n) • O ((L pro + L res ) r ) respectively 2 .Since L pro ≫ 2 and L pro ≫ L res , we can approximately treat2 Lpro = 0 and Lres Lpro = α (α ≤ 0.01). Assume that 1 ≤ m ≤ 5, 1 ≤ n ≤ 100. We then compute the ratio between them:T our T naive = (L pro + m(m + n) • L res + m(m + n) • 2) r m(m + n) • (L pro + L res ) r < c m + n (1)where c is a small constant. Consequently, our method reduces the complexity from O(m(m + n))to O(m). In this way, the LLM can generate new edge proposals in fast speed.We further prune the dense connected edges to make the 3D scene graph more precise. We divide newly generated relationships into two categories: long-range and short-range. The basis for this division is whether there is a RGB-D image containing the two connected objects. If true, this edge is short-range, for which we can feed the RGB image to a vision language model (VLM) like LLaVA [23] and ask whether this relationship exists. Nonexistent ones will be pruned. Otherwise the edge is a long-range one. We design two standards to validate it: (1) the line connecting two objects is unobstructed and parallel to the wall of room; (2) these two object nodes belong to the same room node. Only edges meet with both standards can be preserved.In this subsection, we describe how to prompt LLM with the 3D scene graph at each step for decision making. Since directly predicting a is hard for LLM, we adopt Frontier-based Exploration (FBE) strategy to divide the decision into two part: (1) synchronous with the 3D scene graph, we build an online occupancy map to indicate explored, unexplored and occupied area in BEV, based on which we compute the frontiers of explored area. In order to further explore the environment, the agent must go through one of the frontier. So in high level, the LLM is only required to select one of the frontier which has the highest probability to find o; (2) once the frontier to be explore is chosen, we simply apply local policy like Fast Marching Method [34] for path planning and output a.Hierarchical Chain-of-thought Prompting. Different from previous methods [46; 52] that prompt LLM with only categories of objects near each frontier, we compute the probability P f ro of each frontier by prompting LLM with our 3D scene graph. At time t, we divide the scene graph G t into subgraphs, each of which is determined by an object node with all its parent nodes and other directly connected object nodes. For each subgraph, we predict P sub , the possibility of goal appearing near this subgraph. Then the probability P f ro i of the i-th frontier can be averaged by:EQUATION)where M is the total number of subgraphs and D ij is the distance between the center of the i-th frontier and the central object node of the j-th subgraph.In order to make the prediction of P sub accurate and explainable, we propose a hierarchical chainof-thought method to prompt LLM, which fully exploits the structure information contained in the subgraphs. Specifically, for each subgraph, LLM is first prompted with Predict the most likely distance between [object] and [goal], where [object] means the category of the central object node.Then we prompt LLM to ask question related to the navigation goal, with the prompt: Ask questions about the [object] and [goal] for predicting their distance. After obtaining the questions about goal, we prompt LLM to answer those questions according to the information of subgraph, with the prompt: Given [nodes] and [edges] of subgraph, answer above [questions]. Therefore, from those answers we get all the necessary information required for inferring the position of goal. Finally, we prompt LLM to summarize the conversation and predict P , with the prompt Based on the above conversation, determine the most likely distance between this subgraph and [goal]. And P sub can be simply computed by taking the inverse of the outputted distance. The LLM also summarizes the analysis process of the nearest 3 subgraphs to the selected frontier to explain the reason for decision.Graph-based Re-perception. Conventional object navigation framework does not take perception error into consideration. Once the agent detects out false positive objects of the goal category, it will not explore or perceive the environment any more and directly navigate to this object.To solve this problem, we enhance the current object navigation framework with graph-based reperception mechanism. When the agent detects out a goal object, it will approach to this object, observe it from multiple perspectives and accumulate a credibility score S. For the k-th RGB-D observation since this moment, we compute the credibility of it by:EQUATIONwhere C k is the confidence score of this goal object, D j is the distance between the central object node of the j-th subgraph and this object. The success condition for our re-perception mechanism is:EQUATIONwhere N max is a pre-defined maximum number of steps. If succeed, the agent will navigate to this goal object without any further exploration or perception. Otherwise, it will give up this object and continue the exploration.Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof? Answer: [Yes] Justification: We provide the full set of assumptions as well as a complete proof in Section 6.3. Guidelines:• The answer NA means that the paper does not include theoretical results.• All the theorems, formulas, and proofs in the paper should be numbered and crossreferenced. • All assumptions should be clearly stated or referenced in the statement of any theorems.• The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch to provide intuition. • Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material. • Theorems and Lemmas that the proof relies upon should be properly referenced. 
experiment: 
 In this section, we first describe our datasets and implementation details. Then we compare our SG-Nav with state-of-the-art object navigation methods in different settings. We further conduct several ablation studies to validate the effectiveness of our design. Finally we demonstrate some qualitative results of SG-Nav.We evaluate our method on three datasets: Matterport3D (MP3D) [5] , HM3D [31] and RoboTHOR [9] . MP3D is a large-scale 3D scene dataset, which is used in Habitat ObjectNav challenges. We test our Evaluation Metrics: We report three metrics including success rate (SR), success rate weighted by path length (SPL) and SoftSPL. SR is the core metric of object-goal navigation task, representing the success rate of successful navigation episode. SPL measures the ability of agent to find the optimal path. If success, SPL = optimal path length path length, otherwise SPL = 0. SoftSPL [8] measures the navigation progress and navigation efficiency of the agent. Higher is better for all the three metrics.Implementation Details: We set 500 as the maximal navigation steps. The farthest and closest perceived distances of the agent are 10m and 1.5m. Each step of the agent takes 0.25m, and each rotation takes 30 • . The camera of agent is 0.90m above the ground, and perspective is horizontal. The camera outputs 640 × 480 RGB-D images. We maintain a 800 × 800 2D occupancy map with the resolution of 0.05m, which can represent a 40m × 40m large-scale scene. In equation 4, the hypre-parameters N max is 10 and S thres is 0.8. For the verification of short edge, we adopt LLaVA-1.6 (Mistral-7B) [24] as the VLM for discrimination. We choose LLaMA-7B [36] and GPT-4-0613 as the LLM for our SG-Nav, which are discriminated by SG-Nav-LLaMA and SG-Nav-GPT.We compare SG-Nav and with state-of-the-art object navigation methods of different setting, including supervised, unsupervised and zero-shot methods in Table 1 . SG-Nav surpasses previous zero-shot methods by about 10% on all three benchmarks. We also notice that on the challenging MP3D dataset, SG-Nav even outperforms supervised methods including SemEXP and PONI. Note that the improvement of SR is larger than SPL, this is because our graph-based re-perception mechanism can help the agent give up false positive goal object, which can significantly increase the success rate. However, during the process the re-perception, the agent still needs to approach to the goal to observe it from multi views. So this strategy cannot reduce the length of path.We also compare per-category success rate of different zero-shot methods in Figure 4 . For all goal categories, SG-Nav outperforms other methods by a large margin, especially on categories that have more relationships with other objects such as fireplace and towel. Scene Graph and Re-perception. In Table 2 , we compare the design choices of scene graph (SG) and re-perception (RP). Without RP, SG-Nav will move to the goal once the detector finds a goal, even thought the goal is a false positive. Due to the complexity of the scene, it is common for detector to make mistakes, which leads to irreversible navigation. If we further remove the whole SG, our framework degenerates to a random exploration model. The agent randomly selects frontier, resulting in a significant performance degradation on all datasets.Room Node and Group Node. As shown in Table 3 , we compare the performance between different architectures of scene graph by ablating the design of group and room nodes. We remove the room or group node with the edges connected to it and obtain 4 different scene graph architecture. The removal of room node and group node results in 0.7% and 1.1% SR degradation on MP3D dataset respectively. We observe the group node is more important than room node, which is because the group nodes aggregate objects into a whole and thus reduce the redundant information and the complexity of scene graph.Efficiency of Scene Graph Construction. In Figure 5 , we show the speed of generating densely connected new edges for our proposed efficient prompt-based method and the naive O(m(m + n)) method. The naive method requires time consumption that is linear to the number of edges, while our efficient prompt significantly reduces the computational complexity.In Table 4 , we study the importance of different kinds of edges. The results validate that edges play an important role in our framework, which helps the hierarchical chain-of-thought better exploit the structural information contained in the environment. Step 1Step 16Step 64Step 80Step 104Step 31Step 70Step 101Step 110Step 115Step 190Stool Bedroom Furniture Bedroom Picture BedroomIn bedroom, if there are bed and chair, the cabinet will be here. Effects of CoT. In Table 5 , we demonstrate the importance of CoT prompting. "Text prompting" refers to directly converting the 3D scene graph into text and prompting the LLM. "Text prompt separately" means converting the nodes and edges into text individually. Additionally, we removed the edges between layers to further validate the necessity of hierarchical graph structure. The experimental results show that our CoT prompting can effectively exploit the structure information contained in the 3D scene graph.Chair Accumulate credibilityWe visualize the navigation process of SG-Nav in Figure 6 . The upper example shows that SG-Nav is able to explain the reason for its decision based on the nearest 3 subgraphs to the selected frontier.The lower example demonstrates that SG-Nav can accumulate credibility of the detected goal object and utilize it to judge the authenticity of this goal, which effectively corrects perception error.Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)? Answer: [Yes] Justification: The results in our paper can be reproduced by the readers. Guidelines:• The answer NA means that the paper does not include experiments.• If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not. • If the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable. • Depending on the contribution, reproducibility can be accomplished in various ways.For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed. • While NeurIPS does not require releasing code, the conference does require all submissions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. , with an open-source dataset or instructions for how to construct the dataset). (d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility.In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 
conclusion: 
 In this paper, we have proposed SG-Nav, a zero-shot object-goal navigation framework that prompts LLM with scene graph to inference the position of goal object. We first construct a hierarchical 3D scene graph online to preserve rich context information of the environment. To speed up the building of scene graph, we propose an incremental updating and pruning strategy, which first densely connects newly registered nodes to all nodes by efficiently prompting the LLM. Then we divide the edges into long-range and short-range to prune them with different strategies. At each step, we divide the scene graph into subgraphs and prompt LLM with hierarchical chain-of-thought to output the probability score of each subgraph. Then the score for each frontier can be acquired by simple interpolation, which is also explainable as we can summarize the decision process of LLM on each subgraph. With the graph representation, we further design a re-perception mechanism to empower SG-Nav with the ability to give up false positive goal objects and thus correct perception error. Extensive experiments on three datasets validate the great performance of SG-Nav and the effectiveness of our design.Potential Limitations. Despite of the great performance, SG-Nav still has several limitations: (1) SG-Nav relies on online 3D instance segmentation method for scene graph construction. Currently we adopt 2D vision-language model and vision foundation model to segment each frame and merge the masks across different frames, which is not end-to-end and 3D-aware. A stronger online 3D instance segmentation model will further boost the performance of SG-Nav. (2) SG-Nav can only handle object-goal navigation yet. However, due to the strong zero-shot generalization ability of LLM and the rich context contained in 3D scene graph, we believe SG-Nav can be further extended to more tasks such as image-goal navigation and vision-and-language navigation. 6 AppendixQuestion: Does the paper provide open access to the data and code, with sufficient instructions to faithfully reproduce the main experimental results, as described in supplemental material? Answer: [Yes] Justification: We have uploaded our code on MP3D dataset in the supplementary materials.We will release all code upon acceptance. It takes some time for us to clean the whole project and make the code easy to play with. Guidelines:• The answer NA means that paper does not include experiments requiring code. Guidelines:• The answer NA means that the paper does not include experiments.• The experimental setting should be presented in the core of the paper to a level of detail that is necessary to appreciate the results and make sense of them. • The full details can be provided either with the code, in appendix, or as supplemental material. 
overview: 
 In this appendix, we first provide the dictionary for grouping object nodes in Section 6.2. Then we provide the proof process and illustrated example on computational complexity of our efficient edge generation method in Section 6.3. Next we provide the complete prompts used in our approach in Section 6.4. Finally we provide more visualization results in Section 6.5.When registering a new group node, we need to judge whether two object categories are related. We use LLM to generate the relationship dictionary, as shown below:(Bed, Nightstand) (Wardrobe, Dresser) (Bookshelf, Chair) (Counter, Stove) ( Here we provide detailed proof for Eq (1) . As shown in Figure 7 , the computational complexity of processing m(m + n) pairs of nodes for the naive method is O(m(m + n)) and the time isT naive = m(m + n) • O ((L pro + L res ) r ). Complexity of our method is T our = O ((L pro + m(m + n) • L res + m(m + n) • 2) r ), where L pro ≫ 2 and L pro ≫ L res .So we can approximate that 2 Lpro = 0 and Lres Lpro = α (α ≤ 0.01). According to the actual scene graph, usually 1 ≤ m ≤ 5, 1 ≤ n ≤ 100. Then we compute the ratio as:EQUATIONSince 2 Lpro = 0, we have:EQUATIONSince α meets 0 < α ≪ 1, we can use the small value approximation principle ( 1+pα 1+qα ) r ≈ (1 + (p -q)α) r to simplify the equation:T our T naive < 1 m + n • 1 + m 2 + mn -1 • α r m (7)Then we use the prior 1 ≤ m ≤ 5 and 1 ≤ n ≤ 100 to scale the coefficient into a constant c. The coefficient monotonically increases with r, n and α:EQUATIONThe coefficient decreases first and then increases with m. It takes the maximum value when m is at its maximum:EQUATIONConsequently, we obtain the ratio:EQUATION)where c = 5.49. Our method reduces the complexity by(m + n) times, from O(m(m + n)) to O(m).So LLM generates relationship with O(m) complexity, which is much faster than the naive baseline.We provide the complete prompts of SG-Nav.Edge Connecting. In the edge connecting process, the complete prompt is as follows:You are an AI assistant with commonsense and strong ability to infer the spatial relationships in an indoor scene.You need to provide the possible spatial relationships between several pairs of objects. Relationships include ["next to", "above", "opposite to", "below", "inside", "behind", "in front of", ...].All the pairs of objects are provided in JSON format, and you should also response in JSON format. Here are 2 examples:1.Input:[{"object1": "chair", "object2": "table"}, {"object1": "monitor", "object2": "desk"}]Response:[{"relationships": "next to"}, {"relationships": "above"}] 2.Input:[{"object1": "sofa", "object2": "TV"}, {"object1": "plant", "object2": "chair"}]Response:[{"relationships": "opposite to"}, {"relationships": "behind"}]Now you predict these pairs of objects: [{"object1": {}, "object2": {}}, {"object1": {}, "object2": {}}, ...]where {} will be replace by the object categories.Hierarchical CoT. In the process of goal inference, we use the following prompts to let LLM predict the most likely position of goal.Step 1 (Predict Distance of Object):You are an AI assistant with commonsense and strong ability to infer the distance between two objects in an indoor scene.You need to predict the most likely distance of two objects in a room.You need to answer the distance in meters and give your reason. Here is the JSON format: Input:{"object1": "table", "object2": "chair"} Response:{"distance": 0.5, "reason": "Because there is always a chair next to the table."} Now predict the distance and give your reason: {"object1": {}, "object2": {}} where {} will be replace by the object.Step 2 (Ask Question):You are an AI assistant with commonsense and strong ability to infer the spatial relationships in an indoor scene.But you have insufficient information. You need to ask a question about the spatial relationship between the object and the goal in the following JSON format: Input:{"object": "sofa", "goal": "TV"} Response:{"question": "Is there a table next to the sofa?"} Now ask question: {"object": {}, "goal": {}} where {} will be replace by the object and goal.Step 3 (Answer Question):You are an AI assistant with commonsense and strong ability to answer question about the objects in an indoor scene.Given a graph scene of the scene, you need to answer the question in the following JSON format: Input:{"subgraph": {"nodes": ["sofa", "table", ...], "edges": ["sofa next to table", ...]}, "question": "Is there a table next to the sofa?"} Response:{"answer": "Yes"} Now answer question: {"subgraph": {}, "question": {}} where {} will be replace by the subgraph and question.Step 4 (Predict Distance of Subgraph):You are an AI assistant with commonsense and strong ability to infer the distance between a subgraph and a goal in an indoor scene.You need to predict the most likely distance of a subgraph and a goal in a room. You need to answer the distance in meters and give your reason.Here is the JSON format: Input:{"subgraph": {"nodes": ["sofa", "table", ...], "edges": ["sofa next to table", ...]}, "goal": "TV"} Response:{"distance": 2, "reason": "Because TV and sofa are on both sides of table."} Now predict the distance and give your reason: {"subgraph": {}, "goal": {}} where {} will be replace by the subgraph and goal.We further provide visualizations on the constructed scene graphs, the frontier scores along with the LLM reasoning output, and failure case to help comprehensive understanding of our approach.  
experiment statistical significance: 
 Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?Answer: [No] Justification: Error bars are not reported because it would be too computationally expensive.Guidelines:• The answer NA means that the paper does not include experiments. • If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics. • The authors should make sure to preserve anonymity (e.g., if there is a special consideration due to laws or regulations in their jurisdiction). 10. Broader Impacts Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? Answer: [NA] Justification: Our method is currently only used for academic research. Guidelines:• The answer NA means that there is no societal impact of the work performed.• If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact. • Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster. • The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology. • If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML). 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA] Justification: Our paper poses no such risks. Guidelines:• The answer NA means that the paper poses no such risks.• Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters. • Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images. • We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort. • We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution. • For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review. 
 
 Appendix: Step 31Step 70Step 101Agent Path GoalGo to the living room to find a chair because it is the designated seating area in most homes.The living room usually has a sofa next to table, because it is a common space for and spending time with family. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated. • The authors should reflect on the factors that influence the performance of the approach.For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon. • The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size. • If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.We provide detailed proof process and illustrated examples in Section 6.3. 


Decision: This paper presents a zero-shot object navigation framework with a 3D scene graph to represent the observed scene.
Initially it received rating of 6654.
Most of the concerns were resolved during rebuttal and the Reviewer aSmS raised the score from rating of 5 to 6.
However, the Reviewer JsEs found the performace and novelty are not strong enough, and the rating was dropped from 4 to 3 after rebuttal.
The author provided detail response and additional experiments.
The AC carefully looked into this case and had discussion with the SAC.
Both the SAC and AC agree that the requested experiment results are qualified to support the argument of this paper, and the concerns from Reviewer JsEs are not significant enough to reject the paper.
The AC thus recommends acceptance for this paper.
The authors are urged to include the new experiments (e.g., ones with stronger LLMs) in the camera-ready version of the paper.

Reviews: review: paper_summary: paper_summary: This paper introduces a zero-shot object navigation framework using a 3D scene graph to represent the environment. It employs a hierarchical chain-of-thought prompt to LLMs for goal location navigation and includes a re-perception mechanism to correct errors. Experiments are conducted on MP3D, HM3D, and RoboTHOR.
strength_weakness: strength_weakness: - Although the paper claims to target open vocabulary (zero-shot) object navigation, the method uses some closed-set settings, such as a predefined relationship dictionary, which contradicts the open vocabulary premise.

- In the experiments, the target objects chosen (on MP3D and HM3D) are the same as those in regular ObjectNav settings, where the objects are common. This seems to undermine the method's capability in handling open vocabulary objects.

- The proposed 3D scene graph is defined with objects, groups, and rooms. There is a related work for ObjectNav that also constructs a similar graph with objects, zones, and scene nodes. I suggest that authors can compare their graph construction with this work and include it in the references to enrich the paper.
[1] Hierarchical object-to-zone graph for object navigation, ICCV 21.
questions: questions: - How is the accuracy of the 3D scene graph validated?

- The chain-of-thought method to prompt LLM is interesting. Are there other methods to prompt LLM? Comparing different prompt methods could make the experimental results more solid.

- Is the zero-shot object definition meant to be training-free, or does it mean that the target is not predefined? While the problem definition mentions open-vocabulary, Figure 1 and the selected object categories in the experiments are still common objects.

- I would like to see some failure cases. What are the reasons behind these failures?
limitations: limitations: The authors discuss potential limitations in the conclusion section.
paper_summary: paper_summary: This paper propose to use 3D Scene Graph Prompt in LLM-based Zero-shot Object Navigation, which fully use information of whole scene and is explainable. Also it propose prune-based method to accelerate the construct of graph. Enough expriments show the superority of the method and the effectiveness of each modules.
strength_weakness: strength_weakness: 1.VLM and is needed for Short Edge Pruning which may increase the time consumption of model to construct graph.

2.The Incremental Updating and Pruning may have some issue. (See in Question.)
questions: questions: 1.In line 39-41, the author mentions previous methos are abstract and unexplainable. Please explain this viewpoint in more detail and show how your method solve this problem.

2.Will the already constructed scene graph vary based on changes in perspective? (For example, in the previous timestamp when A and B objects did not appear in the same image, Long Edge Pruning is required, while in the next time when A and B appear in the same image, Short Edge Pruning is required, the scene graph may be differnet). Does using Incremental Updating and Pruning ignore this change and result in cumulative errors.
limitations: limitations: None
paper_summary: paper_summary: The paper proposes a 3D scene graph prompting strategy and designs a hierarchical chain-of-thought prompt for improving LLM-based zero-shot object navigation. The 3D scene graph is incrementally updated and pruned to reduce the computational complexity. A re-perception mechanism is also introduced to correct the perception error. Experimental results on MP3D, HM3D, and RoboTHOR environments show the superiority of the proposed method over the competitors.
strength_weakness: strength_weakness: 1 The approach utilizes the LLM to predict the possible relationships between objects, and possible distances between object and goal. However, this information may be various in different scenes. What if the prediction is inconsistent with the real scene? Would it largely impact the navigation success? I suggest the author give more results and analyses about this. 

2 Although Figure 6 gives the visualization of the navigation process, the author did not provide the visualization for the sequential frontier scoring and reasoning output of LLM. It would be better to present this visualization to help further understand the advantages of the approach.

3 There are some recent works surpassing the reported compared methods, e.g., L3MVN (IROS 2023), VoroNav (ICML 2024), OpenFMNav (NAACL 2024), and VLFM (ICRA 2024). The authors should add them to the table for a more complete comparison and analysis.
questions: questions: See details in the weaknesses.
limitations: limitations: Limitations have been discussed.
paper_summary: paper_summary: This paper presents a new framework for zero-shot object navigation. Unlike previous methods that only provide objects in close proximity, this paper constructs a scene graph that captures the relationships between objects, groups, and rooms. 
This scene graph allows for a more comprehensive understanding of the environment by the navigation system, enabling it to make decisions based on a wider context rather than immediate surroundings. This method significantly improves the robustness and versatility of the navigation system, making it more effective in a variety of settings.
strength_weakness: strength_weakness: 1. The use of scene graphs is not very new in the field of navigation. I think it's important to discuss the use of the scene graph in navigation in related work.
   
2. I think the authors should take some LLM-based object Navigation method as baseline in the experiments to compare with the proposed method. The authors mention in the abstract that the previous LLM based navigation method promotes LLM with the text of spatially closed objects. Yet no comparison is made in the experimental section, which hardly demonstrates the superiority of the scene context. For example, "L3MVN: Leveraging Large Language Models for Visual Target Navigation" shows comparable success rate than the proposed method in HM3D benchmark, which is also mentioned in the Line 77.
   
3. The way LLM utilizes the scene graph is still through text prompt, which makes me think that the authors have overpacked it as "LLM friendly structure" a little bit. I think here the usage of the scene graph is just a prompt design and doesn't reflect the hierarchy of the scene graph very well. I consider this reference to be the basis on which I made this judgment: "SayPlan: Grounding Large Language Models using 3D Scene Graphs for Scalable Robot Task Planning".
questions: questions: 1. Line 198， I think a hint that $a$ is an action would be clearer. In addition, why is it said that direct prediction of action by LLM is difficult? Any references or experiments to prove this?
limitations: limitations: The authors discuss limitation very well.

Comments: comment: We appreciate the reviewer for the positive feedback. We will add experiments on uncommon categories for a more comprehensive evaluation.

We will also continue to improve our work and release the code. If the reviewer has any follow-up questions, we are happy to discuss!
Thanks for the response. The reply addresses my concerns regarding whether the proposed method benefits only pre-defined objects. Therefore, I decide to maintain my previous rating. 

Additionally, considering that this work focuses on an open-vocabulary object setting, I understand the authors' choice to use a consistent task setting for fair comparison with previous work. However, I suggest including evaluations on uncommon object categories in the final version to further strengthen the paper.
Thanks for the reviewer's timely reply. We answer the questions as below.

**1. Navigation performance cannot be improved when LLM reasoning performance is improved**

We have mentioned before that we can construct more detailed and larger 3D scene graph to prompt LLM. In this case, the reasoning task for LLM will be harder and thus stronger LLM may perform better. We now conduct experiments to validate this. 
We relax the condition for edge pruing to increase the number of edges in the scene graph. Then we use this more complex scene graph to prompt LLaMA-7B and GPT-4 respectively. We name this setting as SG-Nav-Complex and run experiments on MP3D. Due to time constraints, we only use 40% of the validation set. As shown below, the performance gap between LLaMA-7B and GPT-4 widen from 0.1 to 0.5 on SR, which means the performance of SG-Nav can be improved by using stronger LLM. In the future, we can construct more detailed 3D scene graph to further exploit the reasoning ability of LLM. We thank the reviewer for this constructive advice and will add this experiments in the revised version of our paper.
|  | **SR** | **SPL** |
|--|:--:|:--:|
|SG-Nav (LLaMA)|40.1|16.0|
|SG-Nav (GPT-4)|40.2|16.0|
|Gap|**0.1**|**0.0**|
|SG-Nav-Complex (LLaMA)|39.3|15.7|
|SG-Nav-Complex (GPT-4)|39.8|15.9|
|Gap|**0.5**|**0.2**|

**2. LLaMA-2-7B and LLaMA-3-8B**

We think the reviewer's statement "With these small-volume models with stronger reasoning, the performance of other methods is improved, but not SG-Nav. " may not be exactly correct. To the best of our knowledge, none of the LLM-based ObjectNav methods currently use LLaMA-2-7B or LLaMA-3-8B. L3MVN, VoroNav and OpenFMNav adopt RoBERTa, GPT-3.5 and GPT-4 (GPT-4V) respectively.

**3. The performance of L3MVN**

We reproduce the performance of L3MVN (Zero-Shot, with RoBERTa-large) on all three benchmarks. As shown below, SG-Nav outperforms L3MVN on five metrics and is only slightly lower in HM3D SR. So generally, we believe the overall performance of SG-Nav is greater than L3MVN. Note that MP3D and RoboTHOR are more challenging than HM3D, which shows SG-Nav is especially superior on complicated and challenging scenarios.
|  | **MP3D-SR** | **MP3D-SPL** | **HM3D-SR** | **HM3D-SPL** | **RoboTHOR-SR** | **RoboTHOR-SPL** |
|--|:--:|:--:|:--:|:--:|:--:|:--:|
|L3MVN|35.5|14.7|**50.4**|23.1|42.2|22.8|
|SG-Nav|**40.2**|**16.0**|49.1|**24.3**|**47.5**|**24.0**|

**4. Difference with SayPlan**

We agree with the reviewer that SayPlan can conduct object search tasks. However, SayPlan is based on a given scene graph. It focuses on task planning, rather than exploration. Even if SayPlan can be adapted to online scene graph is created online, it cannot directly output **where and how to explore the unknown scenes and predict the actions for agent**. Therefore, we think SayPlan can only search objects within the given scene graph because it does not focus on how to explore unseen objects.

We think SayPlan and SG-Nav target at different tasks and it is promising to combine them for more complicated embodied tasks. But for ObjectNav, SayPlan cannot replace SG-Nav. We appreciate the reviewers' in-depth insights on SayPlan. We will cite this paper and add detailed comparison in the revised version.

**5. Experiments on scene graph construction**

We have conducted experiments to validate the effectiveness of our efficient graph construction method in Figure 5 of our paper. In each navigation step, edge generation is the most time-consuming step, which takes 0.11s on average, accounting for 57.5% of the total time. With the proposed method, our SG-Nav is much faster than conventional method like ConceptGraphs.

We have also provided some qualitative results of the generated 3D scene graph. Please refer to the attached PDF file in the global rebuttal.

**6. The usage of CoT**

We do not deny that “In many cases, CoT is a default way to use LLM, such as OpenFMNav”. However, the CoT prompting in SG-Nav is not naïve. Take OpenFMNav for instance, its novelty mainly lies on the usage of several different LLM/VLM to break down the navigation process, rather than design of prompts. While in SG-Nav, we design CoT prompts that make LLM explore the graph structure, which is very different from conventional text-only CoT. Therefore, we believe our method is a simple (but not naive) and effective way for LLM-based 3D scene graph understanding. 

**In fact, we view the simplicity of CoT prompting as an advantage rather than a shortcoming**. It is easy to implement and achieves satisfactory results on a number of diverse benchmarks. We believe that for exactly that reason our framework is likely to be welcomed by the community. We would also like to note that both reviewer zzdn and aSmS recognize CoT prompting as interesting and well-motivated, which can serve as a starting point for future methods. 

Thanks again for the constructive comments. We are happy to answer further questions as timely as we can.
We appreciate the reviewer for the positive feedback. Your constructive comments and suggestions are indeed helpful for improving the paper.

We will continue to improve our work and release the code. If the reviewer has any follow-up questions, we are happy to discuss!
Thanks for the authors' further clarification. The response has resolved my confusion, so I decide to keep the score of 6.
I appreciate the authors' responses. But I still have some concerns. I'll try to respond to authors' reply in as timely as I can.

The authors claim that "LLM only needs to understand the structure information contained in 3D scene graph and follow the proposed sub-reasoning processes, which is a much easier task with more formatted input." However, current LLMs are very capable of reasoning and do not require the authors to intentionally make reasoning less difficult. The biggest limitation of SG-Nav is that navigation performance cannot be improved when LLM reasoning performance is improved; while other methods can be improved. I think this limitation is significant because LLM options can be more flexible when it comes to real-world deployments. I agree with the authors that GPT-4 is slow and expensive when deployed in real environments; therefore small volume LLM is something that should be prioritized. However, LLaMA-7B is not the only small-volume LLM; considering the timing of the release and the NeurIPS submission deadline, I think LLaMA-2-7B and LLaMA-3-8B should also be considered. These two LLMs are stronger than LLaMA-7B. With these small-volume models with stronger reasoning, the performance of other methods is improved, but not SG-Nav. From this perspective, SG-Nav does not have a performance advantage over other methods of the same type when deployed in the real world. Further, L3MVN uses RoBERTa-large, which is smaller than LLaMA-7B in SG-Nav, but it still outperforms SG-Nav on HM3D. ln terms of performance and required computational resources, L3MVN is more suitable to be deployed in real environments than SG-Nav.

I am very grateful to the author for discussing SayPlan in detail. Regarding SayPlan, I should point out that SayPlan also conducts object search tasks (e.g., "Find me something non-vegetarian"), so the comparison is fair if focusing only on that task. In the SayPlan's prompts, they also provide relationships between nodes and edges to represent a hierarchical structure. SayPlan does utilize an already pre-established scene graph, but I don't think this is a significant limitation since scene graph creation can be done in the environment along with the agent. SayPlan can be easily migrated to a mode where the scene graph is created online. 

If the authors consider an efficient online 3D scene graph construction method to be a contribution, I suggest the authors should perform ablation experiments on it (e.g., comparing it to other online graph building algorithms) to reflect its contribution and advantage. 

I don't deny that the hierarchical chain-of-thought prompting method in SG-Nav works, but I have reservations about whether "designing a CoT prompt" is novel. In recent years, with the development of LLM, CoT techniques have been widely and extensively studied and applied. In many cases, CoT is a default way to use LLM, such as OpenFMNav and SayPlan. Moreover, Prompts in OpenFMNav, with stronger LLM, have better navigation performance. This seems to indicate that OpenFMNav's prompts are more promising compared to structured graph prompts.
Thanks for the reply. We explain the question as below:

The purpose of pre-defining a dictionary is **only to improve navigation efficiency**, which is **irrelevant to the performance**. Because we can save the relationships between common objects into the dictionary to save the time for LLM prediction.

Even if we do not pre-define any category and start with an empty dictionary, the performance of SG-Nav will not change. In this way, it will be slower in the early episodes. But as more and more scenes are explored, the dictionary will gradually accumulate and cover common categories, and then SG-Nav will become faster. So the role of the pre-defined dictionary is to skip the early episodes and make SG-Nav efficient even at the beginning. It **does not affect the zero-shot ability** of SG-Nav.
Many thanks for the detailed rebuttal. The responses have addressed some of the concerns.

In the response, the authors mentioned, "When SG-Nav receives object categories that have not been saved before, we simply prompt LLM to generate the relationship and update the dictionary." Does this imply that the proposed method mainly benefits pre-defined categories? If so, although the method can accommodate open vocabulary, the actual focus of the paper still revolves around pre-defined categories. This limits the method's generalizability, especially since it aims at zero-shot object navigation.
We thank the reviewer for the reply. The reviewer still have two concerns, for which we provide our answers as below. (With less than two days to go, we're not providing experimental results.)

**1. SG-Nav is unable to obtain performance boost when using a stronger LLM**

The reviewer may think that the reason why SG-Nav achieves similar performance when using Llama-7B and GPT-4 resepctively is due to our method cannot fully exploit the reasoning ability of LLM. However, we should point out that this view is not correct. Other state-of-the-art LLM-based method, like OpenFMNav, prompts LLM with very long and complex scene context. In this way, LLM needs to analyze the complex and unstructured text, which requires very strong reasoning and analyzing ability. So using GPT-4 will lead to better performance that Llama-7B. While in our SG-Nav, we prompt the LLM with the subgraph by using chain-of-thought. In this way, LLM only needs to understand the structure information contained in 3D scene graph and follow the proposed sub-reasoning processes, which is a much easier task with more formatted input. With our chain-of-thought promting, even Llama-7B is able to fully understand the scene context and achieve comparable performance with GPT-4. In future work, **we can construct more detailed and larger 3D scene graph to prompt LLM**. In this case, smaller LLM may not have the ability to fully exploit the large 3D scene graph, and LLM with stronger reasoning ability will achieve better performance. 

Moreover, we should highlight that **the ability to achieve high performance with only Llama-7B is a huge advantage of our method**. Just as the reviewer comments in the strength part: “The experimental results show that there is no significant difference between the results of LLaMA-7B and GPT-4, indicating that the method can work in small-volume LLMs, which is friendly to the demand of computational resources.” Note that in real world application, the navigation framework may need to be deployed on the robot agent. In this case, using GPT-4 as the LLM will be very slow and expensive. On the contrary, Llama is open-sourced and there are many works focusing on how to improve the efficiency of Llama for better deployment. So we think Llama-7B will be a good choice for real robots.

**2. Lack of novelty**

The reviewer thinks SG-Nav lacks novelty because recent works such as SayPlan conducts in-depth study on the integration between LLM and scene graph. However, we think this judgement is unfair. 

First, **SayPlan studies a totally different task with ours**. In their work, they assume a pre-constructed 3D scene graph is avaible and mainly focus on task planning. While in SG-Nav, we propose to build an online 3D scene graph to prompt LLM for navigation reasoning. 

Second, **the novelty of SG-Nav includes an efficient online 3D scene graph construction method, a hierarchical chain-of-thought prompting method and a re-perception mechanism**. We propose an online 3D scene graph-based navigation framework, rather than just focusing on how to let LLM understand a given 3D scene graph. In terms of the chain-of-thought prompting, we have explained its novelty in the rebuttal. We also notice that reviewer zzdn thinks our chain-of-thought prompting is interesting.
We appreciate the reviewer for the positive feedback. Your constructive comments and suggestions are indeed helpful for improving the paper. Also, many thanks for raising the score.

We will continue to improve our work and release the code. If the reviewer has any follow-up questions, we are happy to discuss!
Thanks to the authors for providing additional quantitative and qualitative results. Most of my concerns are addressed and I am happy to raise my score. I sincerely suggest the authors add these results and analysis to their revised versions, which are helpful for improving the paper further.
Thanks to the author for the reply. I appreciate the author's detailed discussion of the scene graph based navigation approach. Here are my questions.

On the HM3D website(https://aihabitat.org/datasets/hm3d/), the authors of HM3D compare in detail the differences between MP3D, RoboTHOR and HM3D. As we can see from the table, HM3D is not the "simplest" as the authors claimed. 

I am grateful to the authors for their detailed comparison of other LLM-based approaches. But this raises more questions. For a fair comparison, the authors performed all methods with LLaMA-7B. **I think this is fair but not reasonable.** As seen in the paper, the performance of the authors' method under GPT-4 and under LLaMA-7B is very similar (almost identical). This means that LLM's improved reasoning is hardly a gain for the authors' methods. However GPT-4 or other stronger open source LLMs are not inaccessible in real world. In a real deployment, it is unlikely that users would be able to forcibly restrict the model used for navigation to LLaMA-7B, and they would be perfectly reasonable to use a stronger model for stronger performance - but the authors' methods are unable to show that stronger LLMs result in stronger performance. But for baselines, for example, OpenFMNav achieves better results with GPT-4 and is superior to the author's SG-Nav-GPT-4 in HM3D. 
Moreover, the authors of L3MVN used the RoBERTa-large model and achieved better results than in the table shown by the authors and is superior to the author's SG-Nav-GPT-4 in HM3D. I think it is unreasonable for the authors to use LLaMA-7B instead of RoBERTa-large because the two are not pre-trained in the same way probably not in line with the motivation of the authors of L3MVN. And the number of RoBERTa-large parameters is much smaller than that of LLaMA-7B. 
In summary, the authors did not adequately test the potential of all methods under reasonable conditions. So I don't think the author's comparison is reasonable. 

I thank the authors for the additional experiments on The usage of hierarchy in SG-Nav. One of my concern is that building a scene graph relies heavily on LLM's predictions (Line 172-176), and using a scene graph relies heavliy on LLM's predictions (Line 213-223). With LLM highly involved in navigation, theoretically the navigation performance should be affected by the reasoning ability of LLM, however, the authors show that the experiments with GPT and LLaMA-7B show that the navigation performance is almost independent of the reasoning ability of LLM, can the authors do some analysis on this? Why do GPT-4 and LLaMA behave almost indistinguishably in the navigation of this graph structure?

My other big concern is that even if scene structure is used as part of the prompts, the novelty is limited as the method is largely a prompt engineering. I consider the authurs' method lacking in novelty, in large part because of recent new developments in the integration between LLM and scene graph. For example, in SayPlan, the LLM can choose to collapse nodes in the scene graph that are irrelevant to the task and unfold nodes that are relevant.

In short, the authors' use of graph structure as prompts for LLM lacks novelty and has some limitations. These limitations suggest that the authors' method is unable to obtain navigation performance improvements with LLM performance improvements. Therefore, the authors' method cannot exceed the performance of the same type of method when both use GPT-4. I think these limitations are a big disadvantage, because nowadays, with the development of LLM, there are more and more models with smaller size and more reasoning power, which other methods can benefit from, but the author's method cannot. Taking all these considerations into account, I keep my rating.