VLN-NF: Feasibility-Aware Vision-and-Language Navigation with False-Premise Instructions

1. Problem Definition

Vision-and-Language Navigation (VLN) tasks typically assume that natural language instructions are feasible and that the target object exists in the specified environment. However, in real-world deployments, users often provide instructions with false premises (e.g., "Pick up the plate on the table" when the plate is actually in the car).

Current VLN agents face two main challenges when encountering such instructions:

1. Hallucination: Agents may invent the existence of the object or find a similar-looking object that isn't the target.
2. Premature Termination: Agents may give up too early without sufficient evidence, or conversely, search indefinitely.
3. Lack of Explicit Abstention: Standard benchmarks do not provide an explicit "NOT-FOUND" action, forcing agents to either fail silently or hallucinate success.

The paper addresses the gap in 3D partially observable environments where an agent must not only navigate to a target room but also perform evidence-gathering exploration to verify the absence of a target and explicitly output NOT-FOUND.

2. Methodology

The paper introduces three core components: a new dataset/benchmark, a novel evaluation metric, and a hybrid navigation framework.

A. The VLN-NF Dataset

• Construction Pipeline: The authors developed a scalable pipeline to convert feasible VLN instances (from the REVERIE dataset) into infeasible ones.
  1. LLM Rewriter: Replaces the original target object with a plausible but absent alternative (e.g., changing "cup" to "stool" in a room where no stool exists). The LLM ensures the instruction remains linguistically natural.
  2. VLM Verifier: Uses a Vision-Language Model (VLM) with open-vocabulary detection to scan the target room and verify that the new target object is indeed absent.
  3. Quality Control: Human evaluation on a 5% subset showed <2% error rates, confirming the dataset's reliability.
• Structure: Each episode consists of a pair: one feasible instruction (FOUND) and one infeasible instruction (NOT-FOUND), sharing the same environment and starting point.

B. Evaluation Metric: REV-SPL

Standard metrics like Success Rate (SR) and Success weighted by Path Length (SPL) are insufficient because they reward reaching a room but do not penalize premature stopping or insufficient exploration. The authors propose REV-SPL (Reach–Explore–Verify SPL):

• Reach: Did the agent reach the target room?
• Explore: Did the agent cover a sufficient portion of the room? (Measured by object coverage).
• Verify: Did the agent make the correct decision (FOUND vs. NOT-FOUND)?
• Formula: It normalizes the exploration length against a reference protocol and penalizes unsupported "NOT-FOUND" predictions or premature termination.

C. The ROAM Framework

To solve the task, the authors propose ROAM (Room-Object Aware Movement), a two-stage hybrid framework:

1. Stage 1: Room-Level Navigator (Supervised)
   • Uses a supervised model (based on DUET) trained with weak supervision (room labels only) to navigate from the start point to the entry viewpoint of the target room.
   • This stage handles long-horizon navigation efficiently without needing dense exploration annotations.
2. Stage 2: In-room Explorer (LLM/VLM Driven)
   • Once inside the room, an LLM (e.g., GPT-3.5/4o) drives the exploration.
   • Semantic Context: Uses VLM captions and object detection to understand the scene.
   • FREE (Free-space Raycasting Estimation Engine): A plug-and-play module that segments the floor and uses raycasting to estimate the "clearance distance" (how far the agent can move in a direction before hitting an obstacle). This provides a geometric prior to guide the LLM toward larger, unsearched regions, compensating for the LLM's weak spatial reasoning.
   • Decision Logic: The agent continues exploring until it finds the object (FOUND) or satisfies a stopping criterion (e.g., full coverage or frontier exhaustion) to output NOT-FOUND.

3. Key Contributions

1. VLN-NF Benchmark: A new benchmark for false-premise instructions requiring evidence-grounded abstention, constructed via an LLM+VLM pipeline with high fidelity.
2. REV-SPL Metric: A composite metric that jointly evaluates room reaching, exploration coverage, and decision correctness, discouraging degenerate behaviors like early stopping.
3. ROAM Framework: A hybrid approach combining supervised room localization with LLM-driven, geometry-aware in-room exploration.
4. Empirical Validation: Demonstrated that existing SOTA methods fail significantly on this task, while ROAM achieves state-of-the-art performance.

4. Experimental Results

Experiments were conducted on the VLN-NF val_unseen split:

• Performance:
  • ROAM (GPT-3.5) achieved 6.1 REV-SPL, outperforming the best supervised baseline (DUET) by 45% (4.2 REV-SPL).
  • Pure LLM-based agents (NavGPT, SoM-Gemini) performed poorly (1.0–1.5 REV-SPL) due to difficulties in long-horizon room navigation under partial observability.
  • Map-guided LLMs (MapGPT) improved slightly (3.2 REV-SPL) but still lagged behind ROAM.
• Ablation Studies:
  • Removing the Room-Level Navigator caused performance to collapse (REV-SPL dropped from 5.6% to 0.8%), proving that LLMs alone cannot handle room-level navigation reliably.
  • Adding the FREE module improved REV-SPL from 5.6 to 6.1 by increasing object coverage (79.2% → 82.1%), validating the importance of geometric cues for exploration.
• Transferability: ROAM also improved performance on standard feasible VLN tasks (REVERIE), suggesting the exploration strategies are beneficial even when targets exist.

5. Significance

• Real-World Robustness: This work bridges the gap between idealized benchmarks and real-world robot deployment, where instructions are often unreliable. It forces agents to learn calibration and verification rather than blind obedience.
• Structured Reasoning: It demonstrates that a hybrid approach (supervised navigation + LLM reasoning + geometric priors) is superior to purely end-to-end LLM approaches for embodied tasks requiring spatial reasoning.
• Safety and Trust: By enabling agents to explicitly report "NOT-FOUND" based on evidence, the system reduces hallucinations and builds trust in human-robot interaction.
• Future Directions: The paper identifies the need for "recovery policies" (e.g., asking for clarification) as a next step after detecting a false premise.

In summary, VLN-NF and ROAM represent a significant step forward in making embodied AI agents more robust, truthful, and capable of handling the inherent uncertainty of human instructions in physical environments.