Hypothesis Graph Refinement: Hypothesis-Driven Exploration with Cascade Error Correction for Embodied Navigation

Peixin Chen; Guoxi Zhang; Jianwei Ma; Qing Li

cs.CVApr 5, 2026

Hypothesis Graph Refinement: Hypothesis-Driven Exploration with Cascade Error Correction for Embodied Navigation

Authors: Peixin Chen, Guoxi Zhang, Jianwei Ma, Qing Li

Organizations: Harbin Institute of Technology · Beijing Institute for General Artificial Intelligence · Peking University

Abstract

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 $\mathcal{F}_{t}$ 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 ( $I_{\mathrm{pred}}$ ) and actual ( $I_{\mathrm{actual}}$ ) semantics; if $\Delta_{\mathrm{sem}}>\theta$ , 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 $>\theta_{\text{refute}}$ ), the system traces the dependency DAG and removes the entire erroneous subgraph, including all descendant hypothesis nodes.

	Full Validation Set		Subset
Method	SR $\uparrow$	SPL $\uparrow$	SR $\uparrow$	SPL $\uparrow$
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 $\uparrow$	SPL $\uparrow$	LLM $\uparrow$	LLM $\uparrow$
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 $\uparrow$
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.

Blind LLMs (no visual input)
Method	LLM-Match $\uparrow$	LLM-Match SPL $\uparrow$
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 $\uparrow$
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 $\uparrow$	SPL $\uparrow$
Full ( $\Delta_{c}+\Delta_{f}+\Delta_{o}$ )	87%	74%	72.41	56.22
Drop $\Delta_{c}$ (no category)	78%	71%	70.88	54.31
Drop $\Delta_{f}$ (no CLIP)	83%	68%	71.22	55.07
Drop $\Delta_{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.

$\theta_{\text{refute}}$	Refutation Rate	Precision	Recall	SR $\uparrow$	SPL $\uparrow$
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

\theta_{\text{refute}}

		Geometry-only		HGR (full)
VLM Backbone	Pred. Acc.	SR	SPL	SR $\uparrow$	SPL $\uparrow$
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 $\uparrow$	SPL $\uparrow$	LLM $\uparrow$	LLM $\uparrow$
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
$\lambda_{d}$	Travel cost weight (Eq. 2)	0.15
$\lambda_{h}$	Uncertainty bonus weight (Eq. 2)	0.10
$r_{\text{context}}$	Spatial context radius for $\mathcal{O}_{\text{local}}$	3.0 m
$\omega_{c}$	Category mismatch weight	0.4
$\omega_{f}$	Feature divergence weight	0.3
$\omega_{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.

Panel of Figure 7 — 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”).

Embodied Navigation

Embodied navigation studies how robots perceive, map, and move through environments to reach goals and follow instructions.

See all 138 papers

CGFM-Nav: Cognitive Graph-Field Memory for Semantic-Guided Lifelong Multimodal Embodied Navigation
Aug 29, 2026Yuxiang Xiao, Xibei Chen, Xin Zhou +3Embodied Navigation Vision-Language Navigation
Department of Mechanical Engineering, National University of Singapore, Singapore
Hierarchical 3D Scene Graph Construction and Belief-based Planning for Semantic Navigation
Jun 30, 2026Bing Wu, Zuyao Chen, Changwen ChenBelief-Space Planning Embodied Navigation
The Hong Kong Polytechnic University
Explore Like Humans: Autonomous Exploration with Online SG-Memo Construction for Embodied Agents
Apr 21, 2026Xu Chen, Shichao Xie, Zhining Gu +7Embodied Navigation Semantic Mapping
Amap, Alibaba Group, China.

Aug 29, 2026J/K move · Enter open · S save

CGFM-Nav: Cognitive Graph-Field Memory for Semantic-Guided Lifelong Multimodal Embodied Navigation

Yuxiang Xiao, Xibei Chen, Xin Zhou, Jie Chen+2

Department of Mechanical Engineering, National University of Singapore, Singapore

Embodied Navigation Vision-Language Navigation Graph-Based Agent Memory Multimodal Graph Learning

Open paper AskPDF arXiv

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.

Abstract

Embodied Navigation

Explore similar work

CGFM-Nav: Cognitive Graph-Field Memory for Semantic-Guided Lifelong Multimodal Embodied Navigation

Hierarchical 3D Scene Graph Construction and Belief-based Planning for Semantic Navigation

Explore Like Humans: Autonomous Exploration with Online SG-Memo Construction for Embodied Agents