HSGNav: Hypothesis Scene Graphs for Multi-Scale Lifelong Navigation under Object Relocation

Kaiyao Liao, Qingfeng Li, Chen Chen, Qing Sun, Ningbo Gu, Xiaoze Wu, Haochen Zhao, Ying Li, Jianwei NiuarXiv 2026 · arXiv

TL;DR

HSGNav introduces the Hypothesis Scene Graph (HSG), a dual-layer memory structure that separates stable 3D furniture "entities" from revisable surface-object "hypotheses." This allows assistive robots to efficiently track and relocate tiny items (like an apple) across long-term deployments without the brittle requirement of building full 3D geometry for every small object.

What Problem Does This Paper Address?

Imagine asking a robot to "find my glasses." In a typical home, that robot might have seen them on the coffee table an hour ago. But if you moved them to the nightstand, most current navigation systems fail in one of two ways:

  1. Stale Memory: They keep searching the coffee table because their internal 3D map says the glasses are part of that location's geometry.
  2. Scale Insensitivity: Small objects often produce noisy depth data or intermittent detections, causing them to be filtered out of 3D maps entirely or incorrectly merged into the furniture they sit on.

Existing "lifelong" navigation benchmarks often focus on static scenes or large furniture. HSGNav tackles the reality of multi-scale navigation under object relocation, where robots must find everything from a couch to a coin, even as the environment changes.

Methods

The core innovation is the Hypothesis Scene Graph (HSG). Instead of a "flat" graph where every detection is a 3D node, HSG creates two levels:

  • Entity Level: Persistent 3D furniture (tables, counters) that serve as spatial anchors.
  • Hypothesis Level: Revisable records of small objects found on those anchors. These don't require independent 3D geometry; they are essentially "visual evidence" linked to a piece of furniture.
Figure 2. Overview of HSGNav. Streaming RGB-D observations build a two-level HSG: persistent 3D entities serve as anchors, while on-surface objects are represented as revisable hypotheses linked to them. SAMR retrieves scale-appropriate visual evidence for the target. When retrieval fails, OCE selects a new observation goal; CGN executes the selected goal, and BDV verifies retrieved targets using fresh views. New observations and SAMR add or enrich hypotheses, while BDV invalidates contradicted descriptions and removes hypotheses with no valid descriptions remaining. Dashed plus and trash icons denote hypothesis updates propagated to the HSG.

Building on this structure, the HSGNav system employs three key mechanisms:

  1. Scale-Adaptive Memory Retrieval (SAMR): Uses a Vision-Language Model (VLM) to intelligently filter the graph. If you're looking for a "refrigerator," it looks at entities; if you're looking for a "lemon," it focuses on surface hypotheses.
  2. Belief-Driven Verification (BDV): When the robot reaches a remembered location and the target is missing, it doesn't just give up or rebuild the whole map. It locally invalidates that specific hypothesis, instantly cleaning its memory.
  3. Observation-Complete Exploration (OCE): If the target isn't in memory, the robot doesn't just wander into new rooms. It prioritizes "under-observed" surfaces—checking the tops of tables it has passed but hasn't looked at closely yet.

Datasets

The authors evaluate HSGNav on:

  • GOAT-Bench: A standard benchmark for lifelong navigation in static scenes.
  • FAROS-Bench (Find And Re-find Objects across Scales): A new, more challenging benchmark introduced in this paper. It features 210 subtasks where objects of varying scales (tiny, small, large) are relocated mid-episode, forcing the robot to update its memory to succeed.
Overview of the FAROS-Bench, illustrating the interleaving of static and dynamic tasks with object relocations.

Key Insights and Ideas

  • Decoupling Geometry from Evidence: The "aha moment" is realizing that for small objects, we don't need a perfect 3D mesh; we just need to know which surface they were seen on and what they looked like. This prevents the "fusion" errors that plague traditional 3D scene graphs.
  • Local vs. Global Revision: By anchoring hypotheses to stable furniture, the robot can "delete" a moved object from its mind without affecting its understanding of the room's layout.
  • Surface-First Exploration: In a home, small objects are almost always on surfaces. Prioritizing the inspection of tabletops over exploring distant hallways significantly boosts the success rate for finding "tiny" targets.

Key Results

HSGNav sets a new state-of-the-art (SOTA) on both benchmarks:

  • GOAT-Bench: Achieved a 71.2% Success Rate (SR), outperforming the previous best (3D-Mem) by 2.1%.
  • FAROS-Bench: The performance gap was even wider here. HSGNav achieved an overall 58.1% SR, nearly doubling the performance of baselines on "dynamic" tasks where objects had been moved.
  • Efficiency: HSGNav is significantly leaner, requiring roughly half the VLM calls and one-sixth the images compared to 3D-Mem, making it more viable for real-time robotics.
Comparison of evidence retention and revisit rates, showing HSGNav's superior memory management.

Limitations and Future Work

The current system relies on stable furniture anchors. If a person moves a chair or a table, the spatial reference for the hypotheses attached to it might break. The authors suggest that a natural next step is to develop methods to maintain and reassociate these hypotheses even when the "anchor" entities themselves are relocated. Additionally, while the system uses VLMs effectively, the computational cost of frequent VLM calls remains a hurdle for low-power mobile robots.

Summary updated

Abstract

In real homes, assistive robots must repeatedly locate targets from large furniture to tiny tabletop items, as people move objects between household surfaces. Uniformly instantiating detections at different scales as 3D objects can be brittle for small on-surface items; without explicit object-state validation, stale entries may persist after scene changes. Our key insight is to separate persistent 3D furniture entities from revisable surface-object hypotheses, retaining their visual evidence without requiring independent object geometry. We formalize this design as the Hypothesis Scene Graph (HSG), which preserves small-object evidence and supports local revision without rebuilding the stable entity topology. Building on HSG, HSGNav uses this separation for multi-scale lifelong navigation: retrieval selects entity or hypothesis evidence according to target scale, exploration acquires additional surface observations, and verification confirms target presence or invalidates contradicted hypothesis records. Because existing lifelong benchmarks such as GOAT-Bench rarely require mid-episode memory invalidation or multi-scale search, we introduce FAROS-Bench (Find And Re-find Objects across Scales) for mid-episode relocation of surface objects and multi-scale find goals. Experiments show that HSGNav performs competitively on GOAT-Bench while substantially outperforming prior methods on FAROS-Bench.
BibTeX
@misc{liao2026hsgnav,
  author = {Kaiyao Liao and Qingfeng Li and Chen Chen and Qing Sun and Ningbo Gu and Xiaoze Wu and Haochen Zhao and Ying Li and Jianwei Niu},
  title = {{HSGNav: Hypothesis Scene Graphs for Multi-Scale Lifelong Navigation under Object Relocation}},
  year = {2026},
  eprint = {2611.10547},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.10547},
}
Figure