Technical Summary: Ask When It Pays: Cost-Aware Open-Ended Interaction for Instance Goal Navigation

1. Problem Definition

The paper addresses Instance Goal Navigation (IGN), a task where an embodied agent must locate a specific object instance (e.g., "the red cup on the left") among distractors of the same category based on an underspecified natural language instruction. Unlike Vision-and-Language Navigation (VLN), which often specifies a path, or standard ObjectNav, where any instance of a category suffices, IGN requires resolving instance-level ambiguity.

The authors identify that perception and coarse instructions alone are often insufficient due to:

• Uncertain room boundaries.
• Multiple same-category instances acting as distractors.
• Routes leading to different but seemingly valid candidates.

While interaction with an oracle (a knowledgeable entity) is a natural mechanism for disambiguation, prior interactive methods suffer from two critical flaws:

1. Uniform Treatment of Queries: They treat lightweight clarification questions (e.g., "Is it red?") and high-information route guidance questions (e.g., "Which way?") identically.
2. Cost-Agnostic Evaluation: They allow agents to boost Success Rate (SR) by repeatedly asking high-information questions without penalizing the "cost" of interaction. This fails to distinguish between efficient ambiguity resolution and heavy reliance on oracle assistance.

The paper reframes interactive IGN as a cost-sensitive uncertainty-reduction problem, where an agent should only ask a question if the expected reduction in navigation uncertainty justifies the penalty associated with that specific question type.

2. Methodology

2.1 Question Utility Modeling and Taxonomy

To establish a cost-sensitive framework, the authors derive a question taxonomy and associated penalties from an information-gain-inspired analysis of existing human-authored navigation corpora (R2R, REVERIE, RxR, CVDN, SOON).

• Mining Process: A fixed-schema LLM scorer analyzes navigation records to identify cues that reduce target or spatial ambiguity.
• Taxonomy: Cues are collapsed into four distinct question types, each with a locked cost coefficient ($w_t$) derived from corpus statistics (importance, high-gain frequency, and ranking):
  1. Type 1 (Appearance): Resolves target identity among same-category instances ($w_1 = 0.182$).
  2. Type 2 (Region): Resolves the room or region to search ($w_2 = 0.162$).
  3. Type 3 (Direction/Route): Resolves branch, corridor, or layout direction ($w_3 = 0.240$).
  4. Type 4 (Confirmation): Verifies if a visible candidate is the target ($w_4 = 0.103$).
• Cost Logic: More informative question types (like Type 3) incur higher penalties to discourage over-reliance on oracle guidance.

2.2 Benchmark Construction

The authors construct a new interactive IGN benchmark in Isaac Sim to support this cost-sensitive evaluation:

• Grounded Answers: The oracle provides answers strictly tied to the question type (e.g., Type 3 answers are natural language route hints derived from occupancy maps and path renders, not metric coordinates or compass angles).
• Controlled Difficulty: Episodes are stratified into Easy, Medium, and Hard splits based on distractor count, same-room distractors, contextual ambiguity, and initial path distance.
• Metric: A Weighted Success Rate (WSR) is introduced. It discounts the success of an episode by the exponential sum of the costs of all questions asked:
  $$\text{Weighted SR} = \mathbb{1}_{d_e \le \tau} \exp\left(-\sum_{i=1}^{N_e} w_{\text{type}(q_{e,i})}\right)$$
  This metric ensures that an agent cannot simply "buy" success through excessive questioning.

2.3 TANDEM: Two-Stage Navigation with Disentangled Planning and Metric Grounding

The authors propose TANDEM, a modular zero-shot Multi-Modal Large Language Model (MLLM) navigator designed to operate under this protocol.

• Architecture:
  • Navigator (Planner): An MLLM that reasons over observations, symbolic spatial memory, and accumulated oracle facts. It decides when to ask, what to ask, and where to move. It outputs semantic decisions (Ask, Move, Stop) rather than metric actions.
  • Grounder: Maps the Navigator's semantic plan (e.g., "move to the living room") to a local waypoint on an $8 \times 8$ grid.
  • Deterministic Executor: Handles collision avoidance, motion control, and pose updates using raycasting and floor-plane geometry.
• Interaction Policy: The agent maintains a "Question Budget" and a "Fact Base." It queries the oracle only when the expected uncertainty reduction (based on unresolved cues) justifies the cost. The oracle never provides metric coordinates, preventing the agent from bypassing navigation.

3. Key Contributions

1. Formulation: Recasting interactive IGN as a cost-sensitive uncertainty-reduction problem, introducing a four-type question taxonomy with data-derived penalties.
2. Benchmark: A controllable instance-level IGN benchmark with grounded oracle answers, balanced difficulty splits, and the Weighted Success Rate metric to diagnose interaction efficiency.
3. Baseline: The TANDEM agent, a modular zero-shot MLLM baseline demonstrating that cost-aware interaction, structured spatial memory, and disentangled grounding improve navigation performance.

4. Experimental Results

Experiments were conducted on a fixed pool of 500 episodes (Easy/Medium/Hard) and validated on existing benchmarks (CVDN, SOON, REVERIE).

• Performance vs. Baselines: TANDEM significantly outperforms prior zero-shot agents (GTA, MapGPT, NavGPT, COIN) under the cost-aware protocol.
  • On the hard subset, TANDEM achieves 31.0% SR@1.5 and 21.4% WSR@1.5, surpassing the second-best method (GTA) by 9.3 points in SR@1.5.
  • Naive interaction (unconstrained questioning) often degrades performance as interaction costs accumulate, whereas TANDEM's selective querying maintains high efficiency.
• Ablation Studies:
  • Removing QA interaction drops SR@1.5 from 35.3% to 20.0%, indicating that even with complete initial descriptions, targeted interaction is crucial for resolving ambiguity.
  • Removing Spatial Memory reduces SR@1.5 to 28.0%, highlighting the importance of maintaining context about explored spaces.
  • Removing both components results in a naive zero-shot navigator (14.0% SR@1.5).
• Backbone Scaling: Performance scales consistently with MLLM strength (e.g., GPT-5.4 > Qwen3.5-8B > Qwen3.5-4B), suggesting that stronger reasoning capabilities directly translate to better navigation without necessarily increasing reliance on interaction.
• Interaction Analysis:
  • Timing: Type 1 (Appearance) and Type 2 (Region) questions occur early (first 30-40% of the episode) to ground the target. Type 3 (Direction) questions are uniform throughout, resolving spatial confusion at junctions. Type 4 (Confirmation) peaks late (around 80%) to verify the target.
  • Efficiency: TANDEM asks fewer questions on average than naive agents but achieves higher success. Type 3 questions are most effective in hard episodes, reducing search space uncertainty by up to 47.5%.

5. Significance and Claims

The paper claims that interaction is most useful when it is typed and selectively used, rather than being a generic fallback. By treating interaction as a cost-sensitive resource, the proposed framework:

• Prevents agents from "gaming" success rates through excessive querying.
• Demonstrates that structured spatial memory and cost-aware policies allow zero-shot MLLMs to navigate complex, ambiguous environments effectively without task-specific training.
• Provides a diagnostic tool (via WSR and question-type analysis) to distinguish between failures caused by target identity, spatial uncertainty, or inefficient oracle use.

The authors conclude that their approach offers a robust baseline for future research in embodied AI, emphasizing that efficient ambiguity resolution requires balancing the value of information against the cost of acquisition.