SAFE-EQA: Semantic-Aware Efficient Exploration for Embodied Question Answering¶

Conference: ECCV 2026
Paper: CVF Open Access
Code: https://github.com/yjtang249/SAFE-EQA
Area: Robotics & Embodied AI
Keywords: Embodied Question Answering (EQA), Semantic-aware Path Planning, Traveling Salesman Problem (TSP), Topological Landmark Graph, Adaptive Replanning

TL;DR¶

To tackle the myopic wandering and prohibitive VLM query overhead inherent in greedy frontier-based exploration, SAFE-EQA casts embodied active exploration as an online semantic-aware Traveling Salesman Problem (TSP) over topological Voronoi landmarks, augmented with frontier-triggered adaptive replanning and hierarchical answering, matching or surpassing SOTA accuracy and exploration efficiency while slashing token consumption by 27.8%–45.6%.

Background & Motivation¶

In embodied AI, Embodied Question Answering (EQA) tasks an agent with navigating unseen 3D indoor environments, actively gathering informative visual observations, and answering open-ended natural-language questions. Unlike passive visual QA or exhaustive 3D reconstruction, EQA is inherently goal-oriented: an agent must combine commonsense semantic reasoning with spatial topology to rapidly identify and visit regions relevant to the query—such as checking a kitchen or dining area rather than a bedroom when asked "Is there a coffee mug on the kitchen table?"—to collect high-confidence decisive evidence within a constrained horizon.

However, existing exploration paradigms driven by Vision-Language Models (VLMs) suffer from severe efficiency and robustness bottlenecks. On one hand, most prevailing approaches rely on Frontier-Based Exploration (FBE), selecting next-hop targets from local explored-unexplored boundary frontiers through greedy, step-wise decisions. This myopic strategy lacks global topological awareness and long-horizon coordination, frequently causing agents to oscillate within dead ends, make discontinuous detours and backtracks, or miss key evidence altogether. On the other hand, querying VLMs at every step for next-goal selection and answer confidence incurs severe online inference latency (ranging from seconds to tens of seconds per call) and massive API token costs, presenting a prohibitive barrier to real-world edge deployment.

This paper tackles these challenges with a clear angle of attack: rather than making fragmented, myopic decisions over boundary frontiers, the agent should discretize the navigable space into global topological landmarks and organize long-horizon exploration as a continuous tour that balances geometric travel distance with task semantics. Core idea: formulate EQA exploration as an online Semantic-Aware Traveling Salesman Problem (TSP) over a topological Voronoi landmark graph, generating coherent multi-step local trajectories that drastically curb VLM interactions while coupling with frontier-triggered adaptive replanning and hierarchical graph-matched answering for efficient evidence acquisition.

Method¶

Overall Architecture¶

SAFE-EQA follows a two-stage pipeline: offline preprocessing and online multi-module coordinated exploration. During preprocessing, a Large Language Model (LLM) parses the input question $q$ to extract target entities and spatial relationships, constructing a Goal Graph that serves as high-level semantic guidance for exploration and termination. In the online exploration stage, the agent continuously processes RGB-D streams to update a 3D Scene Graph and a 2D occupancy map. A Voronoi Landmark Graph is incrementally built across free space, while LLM-based task relevance scoring on scene graph subgraphs yields a continuously updated 2D Semantic Map. The global planner solves a semantic-aware TSP over the landmarks to output multi-step trajectories. During navigation, an adaptive interrupt re-optimizes the route only when a high-priority frontier emerges, and the VLM is queried for answer prediction only after hierarchical graph matching successfully filters out irrelevant contexts.

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["Input Question q & RGB-D Observations"] --> B["Preprocessing: Goal Graph Construction<br/>LLM extracts entities and relations"]
    B --> C["Incremental Scene Construction<br/>3D Scene Graph + 2D Semantic Map + Voronoi Landmark Graph"]
    C --> D["Semantic-Aware TSP Routing<br/>Joint optimization of geodesic distance and semantic discount"]
    D --> E["Frontier-Triggered Adaptive Replanning<br/>VLM arbitrates high-priority frontier preemption"]
    E --> F["Multi-Step Trajectory Execution<br/>Smooth tracking with reduced query frequency"]
    F --> G["Hierarchical Graph Matching & Answering<br/>Coarse localization to LLM filter to VLM termination"]
    G -->|Insufficient confidence| C
    G -->|Confident answer| H["Output Final Answer & Terminate"]

Key Designs¶

1. Semantic-Aware TSP Routing: Decoupling Global Exploration into a Semantically Discounted Tour To overcome the fragmented trajectories and frequent omissions of greedy frontier stepping, SAFE-EQA extracts a 2D Voronoi graph over the explored free space to form an anchor landmark graph $L_t = \{l_{t,i}\}$, connected by navigable geodesic paths. Redundant candidate vertices within 1.2 m of existing landmarks or previously visited agent poses are systematically pruned. To inject task semantics into route planning, the 3D scene graph is partitioned into connected components, each scored by an LLM for question relevance $\tau_i \in [0, 1]$, and smooth-fused into the 2D unoccupied space to create a continuous semantic map $S(p)$. Instead of purely minimizing physical travel distance, each candidate landmark $\pi_i$ is assigned a normalized semantic score $s_i$, defining a semantic discount factor $\lambda_i = 1 - w_{sem} \cdot s_i$. The tour optimization is formalized as a weighted Traveling Salesman Problem: $$\mathcal{TSP}(p_r, \Pi) = \min_{\Pi} \sum_{i=1}^{n-1} \left[ \lambda_i \cdot \mathrm{dist}(\pi_{i-1}, \pi_i) \right]$$ When a landmark exhibits high task relevance, its effective edge cost $\lambda_i$ is heavily discounted, guiding the optimal global sequence to prioritize task-relevant rooms without inducing erratic backtracking.

2. Frontier-Triggered Adaptive Replanning: Local Top-k Optimization and Frontier Preemption Rigid execution of a static global TSP tour cannot promptly react to sudden, critical visual cues appearing at newly unblocked thresholds. To reconcile long-horizon global coherence with local responsiveness, SAFE-EQA introduces an adaptive replanning mechanism. The system maps detected frontiers $F_t$ to their nearest landmarks. When new candidate frontiers emerge near the current position, the agent extracts their directional snapshots alongside the view of the currently planned next landmark, packaging them into a single prompt for a lightweight VLM priority assessment. If the VLM deems a new frontier more promising than the current waypoint, its associated landmark is designated as the new reference point $p_r$, triggering replanning; otherwise, the agent continues along its scheduled path. To prevent erratic global trajectory reshuffling, TSP re-optimization is restricted to a local subset $L_s$ containing the top-$k$ priority landmarks, scored via distance damping and Sigmoid-scaled semantic relevance: $$Pri_i = \frac{s_i^\alpha}{(d_i + \epsilon)^\beta}$$ Solving the semantic TSP exclusively on $L_s$ yields a refined local sub-tour $\Pi_s$, which is seamlessly concatenated with the intact remainder of the visitation queue $\Pi_{t-1}$. This guarantees millisecond-level responsiveness to emergent evidence while preserving global route smoothness.

3. Hierarchical Graph Matching & Answering: Two-Stage Gating to Prevent Redundant VLM Invocations Conventional EQA frameworks invoke an expensive vision-language model at nearly every step to evaluate answer confidence, creating an enormous latency and cost bottleneck. SAFE-EQA introduces a Hierarchical Answering Module that executes coarse-to-fine filtering. In the coarse stage, the agent periodically performs cross-graph matching between the question-derived Goal Graph $G_{goal}$ and the online 3D Scene Graph $G_{scene}$ via open-vocabulary embedding similarities, extracting target anchor nodes and their $k_n$-hop structural neighborhoods $G'_{scene}$. In the fine stage, an LLM evaluates the node labels in $G'_{scene}$ against question $q$ to detect candidate target instances $T_{scene}$. Only when $T_{scene} \neq \emptyset$, the system retrieves compact visual snapshots from an incrementally maintained Minimal Keyframe Set $K$ (built via co-visibility clustering) and invokes the VLM for answer generation. Anchor nodes that fail to produce a confident answer are placed in a dormant state until their scene graph topology updates, effectively eliminating redundant queries.

Key Experimental Results¶

Main Results¶

The authors conduct comprehensive evaluations across three standard HM3D benchmarks: OpenEQA (A-EQA split, 184 open-ended questions), EXPRESS-Bench (174 complex indoor scenes), and HM-EQA† (adapted from multiple-choice to open-ended answering by removing distractor choices). Performance is evaluated using LLM-Match accuracy (0–100 score), path-length-weighted exploration efficiency (LLM-Match SPL), and total LLM/VLM token usage.

Dataset	Metric	SAFE-EQA (Ours)	3D-Mem (CVPR'25)	Fine-EQA (ICCV'25)	Relative Gain vs Baseline
OpenEQA	LLM-Match (↑) LLM-Match SPL (↑) Token Consumption (↓)	56.4 53.9 10,585.8	52.6 42.0 19,488.7	43.8 26.6 -	+3.8 pts +28.3% efficiency -45.7% tokens
EXPRESS-Bench	LLM-Match (↑) LLM-Match SPL (↑) Token Consumption (↓)	63.3 53.5 14,991.5	67.5 50.3 23,270.1	51.4 28.1 -	Competitive (-4.2) +6.4% efficiency -35.6% tokens
HM-EQA†	LLM-Match (↑) Token Consumption (↓)	59.2 16,214.1	59.0 22,461.7	44.2 -	+0.2 pts -27.8% tokens

Ablation Study¶

Ablation experiments isolate the contributions of the semantic-aware TSP formulation and the Priority Assessment (PA) module.

Table 1: Ablation on Path Planning Strategy (OpenEQA) | Planning Configuration | Planning Mechanism | LLM-Match SPL (↑) | Token Consumption per Scene (↓) | |---|---|---|---| | Distance-only TSP | Solves TSP solely on geodesic distances over landmarks | 45.7 | 14,376.9 | | Semantic-aware TSP (Ours) | Applies semantic discount $\lambda_i$ to prioritize promising regions | 53.9 (+17.9%) | 10,585.8 (-26.4%) |

Table 2: Ablation on Priority Assessment (EXPRESS-Bench, Long Trajectories > 25m) | Configuration | Mechanism Description | Avg. Trajectory Length (m, ↓) | Token Consumption per Scene (↓) | |---|---|---|---| | w/o PA (No adaptive frontier preemption) | Strictly follows scheduled landmarks; ignores emergent frontiers | 39.4 (+20.5%) | 35,921.3 | | w. PA (Adaptive priority assessment, Ours) | Evaluates frontier snapshots via VLM to interrupt and re-route | 32.7 (-17.0%) | 38,753.2 (+7.9%) |

Key Findings¶

Semantic discounting is critical for exploration efficiency: Compared to vanilla distance-only TSP routing, factoring in semantic relevance boosts SPL from 45.7 to 53.9 (+17.9%) on OpenEQA, while lowering token usage by 26.4% as the agent pinpoints target rooms much faster without wandering aimlessly.
Priority Assessment pays negligible overhead for massive path reduction: In challenging long-horizon environments (> 25 m), enabling PA introduces a modest 7.9% token increase for image arbitration, but avoids massive detours when doors or corridors suddenly appear, shortening average travel distance from 39.4 m to 32.7 m (-17.0%).
Runtime breakdown reveals an edge-friendly computing profile: Lightweight local TSP optimization takes a mere 0.31 seconds per solve, while costly VLM answering (11.88 s/call) and frontier assessment (4.32 s/call) are triggered sparingly (0.24 and 0.18 calls per step), dismantling the latency bottleneck of embodied foundation agents.

Highlights & Insights¶

Harmonizing Topological Landmarks with Continuous TSP Routing: Instead of equating semantic exploration with local greedy frontier selection, SAFE-EQA formulates exploration as a global traveling salesman tour over Voronoi skeleton graphs, simultaneously ensuring full structural coverage and semantic focus.
The "Execute Long Steps, Interrupt on Surprises" Philosophy: Generating multi-step trajectories suppresses network latency and inference jitter, while lightweight visual frontier arbitration retains immediate agility when unexpected openings appear in unknown scenes.
Modular, Reusable Scene-to-Goal Graph Gating: The coarse-to-fine filtering paradigm—matching goal graphs against 3D scene graphs before accessing minimal keyframes—is navigation-agnostic and directly transferable to Embodied-RAG, object retrieval, and mobile robot inspection.

Limitations & Future Work¶

Dependence on 3D Scene Graph Fidelity: Open-vocabulary 2D instance segmentation errors can accumulate when back-projected into 3D, distorting subgraph connectivity and corrupting LLM semantic relevance scores in low-light or reflective conditions.
Sim-to-Real Discrepancies: Benchmarking is conducted in Habitat-Sim across HM3D meshes under simplified motion kinematics, neglecting physical wheel slippage, dynamic obstacles, door-opening interactions, and localization drifts encountered by physical robots.
Future Directions: Future investigations could integrate lightweight on-device vision models to perform self-supervised landmark refinement and distill the VLM frontier arbitrator into compact local models to further minimize operational latency.

vs 3D-Mem (CVPR 2025): 3D-Mem focuses primarily on hierarchical scene memory representation and co-visibility keyframe indexing, yet still relies on myopic stepwise goal selection; SAFE-EQA inherits its compact keyframe storage strengths while overhauling the navigation core into a global semantic TSP tour, achieving superior SPL efficiency (53.9 vs 42.0 on OpenEQA).
vs Explore-EQA (arXiv 2024): Explore-EQA depends on dense frontier sampling and per-step confidence polling; SAFE-EQA establishes a Voronoi landmark skeleton and enforces graph-matching answering gates, reducing VLM token consumption by over 45%.
vs VoroNav (ICML 2024) / CogNav (ICCV 2025): While VoroNav and CogNav utilize Voronoi graphs for object-goal navigation (ObjectNav), SAFE-EQA adapts Voronoi representations to open-ended EQA by coupling topological nodes with continuous semantic discount weights inside a dynamic TSP solver.

Rating¶

Novelty: ⭐⭐⭐⭐☆ [Elegant reframing of EQA exploration into a semantically discounted TSP over Voronoi topological landmarks with adaptive frontier interruption]
Experimental Thoroughness: ⭐⭐⭐⭐⭐ [Extensive cross-benchmark evaluations on OpenEQA, EXPRESS-Bench, and HM-EQA covering accuracy, path efficiency, token costs, and module-level ablations]
Writing Quality: ⭐⭐⭐⭐⭐ [Clear motivation, rigorous mathematical formulation, clean diagrammatic workflows, and well-substantiated empirical conclusions]
Value: ⭐⭐⭐⭐☆ [Provides an impactful, resource-conscious, and latency-friendly blueprint for real-world embodied autonomous exploration systems]