Embodied agents must explore partially observed environments while maintaining reliable long-horizon memory. Existing graph-based navigation systems improve scalability, but they often treat unexplored regions as semantically unknown, leading to inefficient frontier search. Although vision-language models (VLMs) can predict frontier semantics, erroneous predictions may be embedded into memory and propagate through downstream inferences, causing structural error accumulation that confidence attenuation alone cannot resolve. These observations call for a framework that can leverage semantic predictions for directed exploration while systematically retracting errors once new evidence contradicts them. We propose Hypothesis Graph Refinement (HGR), a framework that represents frontier predictions as revisable hypothesis nodes in a dependency-aware graph memory. HGR introduces (1) semantic hypothesis module, which estimates context-conditioned semantic distributions over frontiers and ranks exploration targets by goal relevance, travel cost, and uncertainty, and (2) verification-driven cascade correction, which compares on-site observations against predicted semantics and, upon mismatch, retracts the refuted node together with all its downstream dependents. Unlike additive map-building, this allows the graph to contract by pruning erroneous subgraphs, keeping memory reliable throughout long episodes. We evaluate HGR on multimodal lifelong navigation (GOAT-Bench) and embodied question answering (A-EQA, EM-EQA). HGR achieves 72.41% success rate and 56.22% SPL on GOAT-Bench, and shows consistent improvements on both QA benchmarks. Diagnostic analysis reveals that cascade correction eliminates approximately 20% of structurally redundant hypothesis nodes and reduces revisits to erroneous regions by 4.5x, with specular and transparent surfaces accounting for 67% of corrected prediction errors.
Figures & tables
Figure 1: Overview of Hypothesis Graph Refinement (HGR). The hypothesis graph separates observed nodes (purple, verified regions) from hypothesis nodes (green, probabilistic frontier predictions), enabling a hypothesis-verification-correction cycle. (Left) Given the query “ What is inside the basket? ”, observed nodes provide confirmed scene context, while hypothesis nodes project semantic distributions onto unexplored frontiers, guiding the agent toward the most likely location of the target object. (Right) Upon arrival, the agent verifies each hypothesis against actual observations. If the prediction is confirmed, the hypothesis node transitions to an observed node; if refuted, cascade correction retracts the erroneous node and all its downstream dependents, preventing error propagation through the graph.
Figure 2: Architecture of HGR. (Left) Frontiers Ft detected from the occupancy map are fed to a VLM reasoner for semantic hypothesis module , which estimates categorical distributions and generates hypothesis nodes linked to observed nodes via spatial and dependency edges. Upon visitation, cascade correction compares predicted ( Ipred ) and actual ( Iactual ) semantics; if Δsem>θ , the refuted node and all its dependents are removed. (Right) Running example on a floor plan. Graph Refinement marks confirmed hypotheses promoted to observed nodes; Graph Refinement (Shrinking) shows where cascade correction prunes erroneous subgraphs, contracting the graph.
Figure 3: Semantic Hypothesis Module. Left: Traditional frontier representation treats unexplored regions as undifferentiated boundaries. Right: HGR projects probabilistic semantic distributions onto frontiers as hypothesis nodes, enabling goal-directed exploration.
Figure 4: Cascade Correction Example. A VLM misidentifies a mirror reflection as a bedroom entrance, generating hypothesis nodes for inferred furniture. Upon reaching the mirror and detecting a prediction violation (residual >θrefute ), the system traces the dependency DAG and removes the entire erroneous subgraph, including all descendant hypothesis nodes.
Full Validation Set
Subset
Method
SR ↑
SPL ↑
SR ↑
SPL ↑
ConceptGraph [ 8 ]
61.2
44.3
67.8
48.1
3D-Mem w/o memory [ 31 ]
58.6
38.5
66.2
44.1
3D-Mem [ 31 ]
62.9
44.7
69.1
48.9
HGR (Ours)
64.14
50.1
72.41
56.22
Table 1: Performance on GOAT-Bench. HGR achieves the highest success rate and path efficiency on both the full validation set (2,780 subtasks) and the evaluation subset (278 subtasks).
Category
Language
Image
Method
SR
SPL
SR
SPL
SR
SPL
ConceptGraph [ 8 ]
65.3
44.7
55.0
38.9
64.0
52.8
3D-Mem [ 31 ]
79.2
55.8
61.9
46.0
65.2
44.2
HGR (Ours)
80.9
60.3
69.8
54.5
68.2
61.7
Table 2: Performance by Target Modality on GOAT-Bench Subset.
Figure 5: Cumulative Success Rate vs. Episode Steps. HGR reaches navigation targets earlier than baselines due to hypothesis-driven frontier selection, while 3D-Mem and ConceptGraph require more steps for exhaustive geometric search. The gap widens in later steps as cascade correction prevents error accumulation.
GOAT (Subset)
A-EQA
EM-EQA
Configuration
SR ↑
SPL ↑
LLM ↑
LLM ↑
HGR (full system)
72.41
56.22
55.9
58.3
w/o Semantic hypothesis
67.71
50.02
48.4
50.5
w/o cascade correction
68.61
51.12
49.6
52.9
Local delete only
70.85
53.67
52.3
55.9
w/o both (geometry only)
63.42
45.33
43.3
45.2
Table 3: Ablation Study. Component contributions on the GOAT-Bench subset and question-answering benchmarks. “Local delete only” removes the refuted node without cascade propagation along the dependency DAG.
Method
Prediction Acc.
Latency (s)
SPL ↑
VLM (GPT-4o)
0.68
0.80
56.22
Heuristic (co-occurrence)
0.52
0.02
52.13
Hybrid (entropy-gated)
0.64
0.35
55.41
Table 4: Hypothesis Prediction Methods. Trade-offs between prediction accuracy and computational cost on GOAT-Bench subset.
Method
LLM-Match ↑
LLM-Match SPL ↑
Blind LLMs (no visual input)
GPT-4o
35.9
—
Question Agnostic Exploration
LLaVA-1.5 Frame Captions
38.1
7.0
Multi-Frame
41.8
7.5
VLM-Guided Exploration
Table 5: Performance on A-EQA (184-question subset). HGR achieves the highest answer quality and exploration efficiency.
Method
Avg. Frames
LLM-Match ↑
Blind LLM (GPT-4)
0
35.5
ConceptGraph Captions
0
34.4
Frame Captions
0
38.1
Multi-Frame
3.0
48.1
HGR (Ours)
3.1
58.3
Human (Full trajectory)
Full
86.8
Table 6: Performance on EM-EQA. HGR achieves the highest answer quality with comparable memory footprint.
Figure 6: Qualitative Comparison: Mirror-Induced Prediction Error. Left: HGR detects the prediction violation and removes the erroneous subgraph via cascade correction. Right: 3D-Mem retains erroneous nodes with lowered confidence, leading to repeated misnavigation.
Appendix figures & tables10 assets
Supplementary material from the paper’s appendix.
Appendix
Property
ESC
SCOPE
ReVoLT
Tiny Moves
HGR
Semantic frontier scoring
✓
✓
✓
✓
✓
Persistent graph memory
–
–
✓
–
✓
Dependency tracking (DAG)
–
–
–
–
✓
Cascade error correction
–
–
–
–
✓
Non-monotonic graph update
–
–
–
–
✓
Appendix
Table 7: Comparison with commonsense-guided exploration methods.
Residual Configuration
Precision
Recall
SR ↑
SPL ↑
Full ( Δc+Δf+Δo )
87%
74%
72.41
56.22
Drop Δc (no category)
78%
71%
70.88
54.31
Drop Δf (no CLIP)
83%
68%
71.22
55.07
Drop Δo (no object IoU)
85%
66%
71.04
54.85
Appendix
Table 8: Per-term ablation of the prediction residual. Dropping any single term reduces refutation precision or recall, confirming that all three signals provide complementary information.
θrefute
Refutation Rate
Precision
Recall
SR ↑
SPL ↑
0.30
42%
68%
91%
66.2
49.8
0.35
37%
74%
88%
68.1
51.6
0.40
33%
79%
83%
70.0
53.4
0.45
29%
84%
78%
71.5
55.1
0.50
24%
87%
74%
72.41
56.22
0.55
20%
90%
67%
71.8
55.5
Appendix
Table 9: Threshold sensitivity for θrefute .
Geometry-only
HGR (full)
VLM Backbone
Pred. Acc.
SR
SPL
SR ↑
SPL ↑
GPT-4o
0.68
63.42
45.33
72.41
56.22
InternVL2-8B
0.57
63.42
45.33
69.15
52.08
LLaVA-1.5-13B
0.51
63.42
45.33
67.82
50.41
Appendix
Table 10: HGR with different VLM backbones on GOAT-Bench subset. The hypothesis-cascade framework provides consistent gains even with weaker open-source VLMs.
Component
Shared
Method-Specific
VLM backbone (GPT-4o)
✓
Habitat 3.0 simulator
✓
Low-level controller (DD-PPO)
✓
Occupancy map construction
✓
Geodesic path planner
✓
Step budget (500 steps)
✓
Appendix
Table 11: Shared vs. method-specific components across all evaluated methods.
GOAT (Subset)
A-EQA
EM-EQA
Method
SR ↑
SPL ↑
LLM ↑
LLM ↑
No correction
68.61
51.12
47.5
51.8
Soft decay only
69.42
52.30
48.8
53.1
Soft decay + revisit penalty
70.17
53.05
49.6
53.9
Local delete only
70.85
53.67
52.3
55.9
Cascade correction (HGR)
72.41
56.22
55.9
58.3
Appendix
Table 12: Cascade correction vs. soft confidence decay with revisitation penalty.
Symbol
Description
Value
λd
Travel cost weight (Eq. 2)
0.15
λh
Uncertainty bonus weight (Eq. 2)
0.10
rcontext
Spatial context radius for Olocal
3.0 m
ωc
Category mismatch weight
0.4
ωf
Feature divergence weight
0.3
ωo
Object IoU weight
0.3
Appendix
Table 13: Hyperparameters used in all experiments.
Component
HGR
3D-Mem
Frontier detection + occupancy map
12 ms
12 ms
VLM hypothesis generation (per frontier)
0.80 s
—
VLM calls per episode (avg.)
18.3
12.1
Total VLM time per episode
14.6 s
9.7 s
Exploration scoring
2 ms
1 ms
Prediction residual test
45 ms
—
Appendix
Table 14: Wall-clock time breakdown per GOAT-Bench episode (avg. over 278-subtask evaluation subset).
Metric
HGR
3D-Mem
ConceptGraph
Peak nodes per episode
34.2
41.7
38.5
Final nodes per episode
28.6
41.7
38.5
Peak edges per episode
52.1
58.3
71.2
Nodes removed (cascade)
5.6
0
0
Memory footprint (MB)
8.2
12.4
15.7
Appendix
Table 15: Average graph statistics over GOAT-Bench episodes.
Figure 7: Qualitative Failure Cases of HGR. We visualize four typical failure patterns: (a) Object confusion caused by detector errors and lack of feature extraction; (b) Loss of visual details due to long observation distances; (c) State misjudgment caused by suboptimal viewpoints or missing subtle visual cues; and (d) Misunderstanding of spatial predicates (e.g., “between”).
Vision-and-Language Navigation (VLN) requires agents to reason over accumulated observations while continuously exploring unseen regions. However, existing environment representations often struggle to jointly support explicit semantic memory and continuous exploration guidance. To address this challenge, we propose Cognitive Graph-Field Memory (CGFM), a persistent multimodal scene representation that couples explicit relational memory with continuous spatial intuition. CGFM organizes objects, spatial relations, and visual observations into a multimodal scene graph, enabling target retrieval and long-horizon reasoning across navigation tasks. When no reliable target match is identified, graph-based evidence is projected into a goal-conditioned semantic-frontier field to guide exploration toward semantically promising frontiers and regions. Building upon CGFM, we introduce CGFM-Nav, a foundation-model-based framework for lifelong multimodal navigation that integrates task-relevant subgraph selection, VLM reasoning, and verification feedback into a closed decision loop. Preliminary experiments on GOAT-Bench show that, under the same Qwen3-VL-8B backbone, CGFM-Nav improves the overall success rate from 53.2% to 63.0% and SPL from 30.0% to 39.6%, demonstrating the effectiveness of combining explicit semantic memory with semantic-guided exploration.
Yuxiang Xiao, Xibei Chen, Xin Zhou +3
Department of Mechanical Engineering, National University of Singapore, Singapore
Semantic navigation is a fundamental task for embodied agents operating in unseen environments, requiring both semantic understanding and long-term decision-making. Recent foundation models have empowered agents with rich semantic priors for this task. However, without structured global representations, decision-making often falls back on local observations and greedy strategies, resulting in inefficient exploration and myopic behaviors, especially in long-distance navigation. To address these challenges, we propose a zero-shot semantic navigation framework. Our method incrementally maintains an online Hierarchical 3D Scene Graph (HSG) to form a multi-granular semantic topology over objects, zones, and regions, serving as a compact state abstraction for global planning. Building on this memory, we introduce a hierarchical belief-based planning framework that fuses semantic priors with exploration evidence on the HSG, and performs finite-horizon rollouts on an HSG-based simulator to explicitly estimate the long-term expected returns of candidate macro-actions. This enables globally consistent decisions and reduces redundant backtracking. Extensive experiments in high-fidelity simulation environments across multiple tasks and datasets demonstrate that our method outperforms existing state-of-the-art methods, particularly in long-distance scenarios, where our approach improves SR and SPL by an average of 9.4% and 5.0%, respectively.
Constructing structured spatial memory is essential for enabling long-horizon reasoning in complex embodied navigation tasks. Current memory construction predominantly relies on a decoupled, two-stage paradigm: agents first aggregate environmental data through exploration, followed by the offline reconstruction of spatial memory. However, this post-hoc and geometry-centric approach precludes agents from leveraging high-level semantic intelligence, often causing them to overlook navigationally critical landmarks (e.g., doorways and staircases) that serve as fundamental semantic anchors in human cognitive maps. To bridge this gap, we propose ABot-Explorer, a novel active exploration framework that unifies memory construction and exploration into an online, RGB-only process. At its core, ABot-Explorer leverages Large Vision-Language Models (VLMs) to distill Semantic Navigational Affordances (SNA), which act as cognitive-aligned anchors to guide the agent's movement. By dynamically integrating these SNAs into a hierarchical SG-Memo, ABot-Explorer mirrors human-like exploratory logic by prioritizing structural transit nodes to facilitate efficient coverage. To support this framework, we contribute a large-scale dataset extending InteriorGS with SNA and SG-Memo annotations. Experimental results demonstrate that ABot-Explorer significantly outperforms current state-of-the-art methods in both exploration efficiency and environment coverage, while the resulting SG-Memo is shown to effectively support diverse downstream tasks.