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

Embodied agents must explore partially observed environ-ments while maintaining reliable long-horizon memory. Existing graph-based navigation systems improve scalability, but they often treat un-explored regions as semantically unknown, leading to inefficient frontiersearch. Although vision-language models (VLMs) can predict frontiersemantics, erroneous predictions may be embedded into memory andpropagate through downstream inferences, causing structural error ac-cumulation that confidence attenuation alone cannot resolve. These ob-servations call for a framework that can leverage semantic predictionsfor directed exploration while systematically retracting errors once newevidence contradicts them. We propose Hypothesis Graph Refinement(HGR), a framework that represents frontier predictions as revisable hy-pothesis nodes in a dependency-aware graph memory. HGR introduces(1) semantic hypothesis module, which estimates context-conditioned se-mantic distributions over frontiers and ranks exploration targets by goalrelevance, travel cost, and uncertainty, and (2) verification-driven cas-cade correction, which compares on-site observations against predictedsemantics and, upon mismatch, retracts the refuted node together withall its downstream dependents. Unlike additive map-building, this allowsthe graph to contract by pruning erroneous subgraphs, keeping mem-ory reliable throughout long episodes. We evaluate HGR on multimodallifelong navigation (GOAT-Bench) and embodied question answering (A-EQA, EM-EQA). HGR achieves 72.41% success rate and 56.22% SPL onGOAT-Bench, and shows consistent improvements on both QA bench-marks. Diagnostic analysis reveals that cascade correction eliminates ap-proximately 20% of structurally redundant hypothesis nodes and reducesrevisits to erroneous regions by 4.5×, with specular and transparent sur-faces accounting for 67% of corrected prediction errors.