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

Hung-Ting Su; Ting-Jun Wang; Jia-Fong Yeh; Min Sun; Winston H. Hsu

cs.ROApr 12, 2026

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

Authors: Hung-Ting Su, Ting-Jun Wang, Jia-Fong Yeh, Min Sun, Winston H. Hsu

Organizations: National Taiwan University · DRIC · National Tsing Hua University

Abstract

Conventional Vision-and-Language Navigation (VLN) benchmarks assume instructions are feasible and the referenced target exists, leaving agents ill-equipped to handle false-premise goals. We introduce VLN-NF, a benchmark with false-premise instructions where the target is absent from the specified room and agents must navigate, gather evidence through in-room exploration, and explicitly output NOT-FOUND. VLN-NF is constructed via a scalable pipeline that rewrites VLN instructions using an LLM and verifies target absence with a VLM, producing plausible yet factually incorrect goals. We further propose REV-SPL to jointly evaluate room reaching, exploration coverage, and decision correctness. To address this challenge, we present ROAM, a two-stage hybrid that combines supervised room-level navigation with LLM/VLM-driven in-room exploration guided by a free-space clearance prior. ROAM achieves the best REV-SPL among compared methods, while baselines often under-explore and terminate prematurely under unreliable instructions. VLN-NF project page can be found at https://vln-nf.github.io/.

Figures & tables

Figure 1: A toy illustration of failure modes under unreliable instructions. For compactness, we visualize two separate single-target queries in the same scene (cup: feasible; plate: infeasible/absent in the kitchen). Left: Standard VLN (DUET+VLN) lacks an explicit NOT-FOUND output (hence “?” for plate). Middle: Adding NOT-FOUND to action space (DUET+VLN-NF) can lead to premature abstention. Right: Our proposed ROAM+VLN-NF performs evidence-gathering exploration and outputs the correct decisions.

Split	#Scans	#Pairs	#Instr.	# FOUND	#NF
Train	55	2,362	4,724	2,362	2,362
Val-seen	38	234	468	234	234
Val-unseen	10	718	1,436	718	718

Table 1: VLN-NF statistics. We use scan to denote a Matterport3D building (scan ID). Each pair consists of one original REVERIE instruction ( FOUND , feasible) and one generated VLN-NF instruction (NF, NOT-FOUND /infeasible), sharing the same scan, start viewpoint, and target room. Val-seen scans are a subset of the training scans.

Figure 2: We design a scalable pipeline to rewrite VLN instructions and generate NF ( NOT-FOUND , infeasible) ones. An LLM-based rewriter uses commonsense priors to generate physically plausible instructions (e.g., water the plant underneath the window → clean the couch underneath the window ), while a VLM-based verifier checks that the referenced target entity is absent from the scene, ensuring NF correctness (Sec. 3 ).

Figure 3: Overview of our two-stage framework, ROAM (Sec. 4 ). Left (Sec. 4.1 ): a room-level navigator trained with room labels only guides the agent to enter the target room. Right (Sec. 4.2 ): an LLM-based in-room explorer selects the next viewpoint using VLM captions as semantic context and a geometric coverage prior from FREE (Sec. 4.3 ) to favor headings that lead to larger unsearched regions.

Figure 4: FREE (Sec. 4.3 ) segments navigable floor regions from the current view using an open-vocabulary visual model and uses depth-based raycasting to estimate a free-space clearance

d_{\text{free}}

for each candidate direction. The resulting clearance cues are appended to the LLM prompt to encourage coverage-oriented exploration.

Setting	Method	Coverage	Len (reach)	Len (explore)	Reach SR	Reach&Decision SR	Reach SPL	REV-SPL
supervised	DUET	69.5%	13.1	7.8	53.8%	33.8%	37.0%	4.2%
unsupervised	NavGPT	59.1%	10.6	2.7	8.2%	5.4%	7.0%	1.0%
unsupervised	MapGPT	63.3%	13.3	3.5	30.0%	14.0%	18.2%	3.2%
unsupervised	SoM-Gemini-2.0-Flash	80.9%	10.0	14.2	39.4%	22.0%	28.9%	1.5%
hybrid	ROAM (Ours)-GPT-3.5	82.1%	11.2	9.9	58.6%	37.6%	44.1%	6.1%
hybrid	ROAM (Ours)-GPT-4o	82.8 %	12.8	22.0	62.6 %	41.4 %	45.4%	5.6%

Table 2: Comparison with baselines on VLN-NF val_unseen . We report our primary metric REV-SPL (Eq. 2 ), together with decomposed diagnostics, Reach SR , Reach&Decision SR , and Reach SPL . (Sec. 5.2 )

#	2 Stage	FREE	Coverage	Reach SR	R&D SR	Reach SPL	REV-SPL
(1)	✗	✗	75.7%	7.8%	4.4%	6.7%	0.8%
(2)	✓	✗	79.2%	59.4%	37.2%	44.2%	5.6%
(3)	✓	✓	82.1 %	58.6%	37.6%	44.1%	6.1%

Table 3: Ablation study of our ROAM framework using GPT-3.5 on the val_unseen split of VLN-NF .

#	2 Stage	FREE	Reach SR	Reach SPL	SR	SPL
(1)	✗	✗	8.1%	6.6%	9.2%	6.8%
(2)	✓	✗	62.0%	48.1%	42.0%	23.7%
(3)	✓	✓	64.0%	48.4%	45.2%	25.1%

Table 4: ROAM (GPT-3.5) on REVERIE val_unseen.

Error source	Share
Room-reaching failure	55.7%
Perception/grounding uncertainty	31.0%
Exploration-control failure	13.3%

Table 5: Error-source decomposition of decision-level false NOT-FOUND predictions made by ROAM (GPT-3.5) on feasible ( FOUND ) episodes in VLN-NF val_unseen.

Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 5: Most occurred objects for NOT-FOUND instructions.

Figure 6: On the left, Grounding DINO detects the door frame. On the right, during raycasting, the process stops when encountering the door frame’s bounding box to avoid estimating incorrect distances (Note the red line indicating a distance of 2.8 meters).

th	ROAM	MapGPT	Retained
	R&D / REV	R&D / REV	episodes
85%	37.6 / 6.1	14.0 / 3.2	100.0%
90%	37.6 / 6.1	15.4 / 3.7	83.8%
95%	37.8 / 6.5	14.2 / 3.3	76.1%

Appendix

Table 6: Sensitivity to the minimum reference-coverage threshold. Each cell reports Reach&Decision SR / REV-SPL (both in %). This analysis varies only the retained evaluation subset (i.e., stricter evaluability filtering), while keeping agent trajectories unchanged. The retained-episodes column is reported relative to the 0.85 retained set.

Metric	Filtering only	Final VLN-NF
Words: Jaccard@50 $\uparrow$	0.887	0.852
Words: Spearman $\rho$ @50 $\uparrow$	0.942	0.863
Words: JS $\downarrow$	0.0106	0.0148
Objects: Spearman $\rho$ $\uparrow$	0.985	0.859
Objects: Cosine sim. $\uparrow$	0.998	0.958
Objects: JS $\downarrow$	0.0017	0.0414

Appendix

Table 7: Distribution-shift analysis for strict filtering and final NF construction. “Filtering only” compares full REVERIE against the retained REVERIE subset after QC filtering. “Final VLN-NF ” compares full REVERIE against the final post rewrite/verify benchmark. Higher is better for Jaccard, Spearman, and cosine similarity; lower is better for JS and TV.

VLN Benchmarks

See all 14 papers

FloorPlan-VLN: A New Paradigm for Floor Plan Guided Vision-Language Navigation
Mar 18, 2026Kehan Chen, Yan Huang, Dong An +5Vision-Language Navigation Embodied Navigation
New Laboratory of Pattern Recognition (NLPR), Institute of Automation, Chinese Academy of Sciences and School of Artificial Intelligence, University of Chinese Academy of Sciences, China · AMap, Alibaba Group · BAAI +2
Learning to Retrieve Navigable Candidates for Efficient Vision-and-Language Navigation
Feb 17, 2026Shutian Gu, Chengkai Huang, Ruoyu Wang +1Vision-Language Navigation Retrieval-Augmented Generation
University of New South Wales, Sydney, Australia · Macquarie University, Sydney, Australia · Data61, CSIRO, Sydney, Australia
If, Then, Otherwise: Diagnosing Conditional Branching in Vision-Language Navigation
Aug 18, 2026Seoyoung Lee, Neel P. Bhatt, Pranay Samineni +8Vision-Language Navigation
The University of Texas at Austin · Collins Aerospace

Mar 18, 2026J/K move · Enter open · S save

FloorPlan-VLN: A New Paradigm for Floor Plan Guided Vision-Language Navigation

Kehan Chen, Yan Huang, Dong An, Jiawei He+4

New Laboratory of Pattern Recognition (NLPR), Institute of Automation, Chinese Academy of Sciences and School of Artificial Intelligence, University of Chinese Academy of Sciences, China · AMap, Alibaba Group · BAAI+2

Vision-Language Navigation Embodied Navigation

Open paper AskPDF arXiv

Existing Vision-Language Navigation (VLN) task requires agents to follow verbose instructions, ignoring some potentially useful global spatial priors, limiting their capability to reason about spatial structures. Although human-readable spatial schematics (e.g., floor plans) are ubiquitous in real-world buildings, current agents lack the cognitive ability to comprehend and utilize them. To bridge this gap, we introduce FloorPlan-VLN, a new paradigm that leverages structured semantic floor plans as global spatial priors to enable navigation with only concise instructions. We first construct the FloorPlan-VLN dataset, which comprises over 10k episodes across 72 scenes. It pairs more than 100 semantically annotated floor plans with Matterport3D-based navigation trajectories and concise instructions that omit step-by-step guidance. Then, we propose a simple yet effective method FP-Nav that uses a dual-view, spatio-temporally aligned video sequence, and auxiliary reasoning tasks to align observations, floor plans, and instructions. When evaluated under this new benchmark, our method significantly outperforms adapted state-of-the-art VLN baselines, achieving more than a 60% relative improvement in navigation success rate. Furthermore, comprehensive noise modeling and real-world deployments demonstrate the feasibility and robustness of FP-Nav to actuation drift and floor plan distortions. These results validate the effectiveness of floor plan guided navigation and highlight FloorPlan-VLN as a promising step toward more spatially intelligent navigation.

Abstract

VLN Benchmarks

Explore similar work

FloorPlan-VLN: A New Paradigm for Floor Plan Guided Vision-Language Navigation

Learning to Retrieve Navigable Candidates for Efficient Vision-and-Language Navigation

If, Then, Otherwise: Diagnosing Conditional Branching in Vision-Language Navigation