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

TL;DR

CondVLN is a scene-graph-grounded benchmark for conditional instruction following in vision-language navigation. Its instructions name the goal only through conditions on the scene, so an agent must check each condition, take the branch the scene supports, and only then navigate. Every condition's truth is known by construction, so the benchmark separates verified successes from lucky ones. Our neurosymbolic reference agent does this; seven VLN agents reach the goal in a few percent of episodes, mostly without checking.

Two benchmark episodes played out by four agents each (Figure 3 of the paper). Paths run from orange (start) to purple (end); numbered badges are the condition objects in check order, the target marks the goal, and a tick appears when the neurosymbolic agent's path first enters the success radius of a condition object. The bottom row shows baselines reaching the goal without checking anything.

Abstract

Vision-language navigation (VLN) agents are evaluated on following route-like instructions toward a fixed goal. Real instructions often depend on what the agent observes: if a condition holds, follow one path, otherwise take another. Existing benchmarks do not control these conditions, so a failure cannot be traced to perception, grounding, navigation, or the conditional branching decision. We introduce CondVLN, a scene-graph-grounded benchmark for conditional instruction following in VLN. Its instructions are generated from verifiable 3D scene-graph predicates with controlled variation in branch depth, chain length, spatial composition, and evidence observability, and are scored by standard VLN metrics and two branch diagnostics, Branch Selection Accuracy and Conditional Success Rate. The benchmark covers AI2-THOR, Matterport3D, Gibson, and ReplicaCAD with 1,998 verified evaluation episodes. Seven VLN agents reach the named object in a few percent of episodes, even when the branch is resolved for them, and most of their successes bypass the required conditional branch, a failure that success rate and path length do not show. A neurosymbolic agent that verifies each condition explicitly raises navigation success up to 16× over the best baseline and follows the branch that the baselines skip. Ablations on identical episodes attribute the remaining gap to acquiring the evidence rather than to choosing the branch. Since the agent records each verdict with its evidence, every failure is assigned to a stage of the decision: the benchmark reports where an agent fails, not only whether it does.

Benchmark

Instructions are generated from 3D scene graphs: every condition is a scene-graph predicate whose truth is known by construction, conditions decide the destination, and they are composed through controlled nesting depth and chain length. Agents receive camera observations and the instruction text only. Branch Selection Accuracy (BSA) credits the condition objects an agent reaches in the order the instruction checks them; Conditional Success Rate (CSR) requires the goal and the full branch.

Benchmark statistics

generated instructions

verified episodes

objects

spatial relations

scenes

complexity categories

Benchmark statistics (Table 2 of the paper)

	ReplicaCAD	AI2-THOR	Gibson	MP3D	Total
Scenes	91	85	105	90	371
Objects	2,293	4,003	7,487	20,279	34,062
Object categories	41	127	55	146	274
Spatial relations	255,529	560,219	146,685	918,059	1,880,492
Generated instructions	3,549	5,100	6,283	5,020	19,952
Verified episodes	500	500	499	499	1,998
Mean reference path (m)	10.0	9.9	22.5	33.5	19.0
Episodes with subgoals	66%	69%	67%	66%	67%

Scene-graph size per environment

Instructions and verified episodes per environment

Mean reference path length (m)

Instructions are generated from six templates that vary nesting depth (1 to 3) and chain length (1 to 3 branches): simple, nested, deep nested, chain, long chain, nested chain. The released instructions are the templates rewritten into natural language by an open-weight model (Qwen3.8-27B) under a parse-back check that keeps the program of every sentence; the template split is released alongside. The verified evaluation sets are balanced across the six categories, and about two thirds of the episodes carry subgoals (condition objects the branch must visit).

Neurosymbolic reference agent

The neurosymbolic agent turns one instruction into a program and runs it in three stages:

1Parse. GPT-4.1 rewrites the instruction as an if/then/else program over scene-graph predicates.

2Search and verify. One condition at a time: sweep in place, detect, lift detections into a 3D memory, explore frontiers under a budget. An exhausted budget declares the condition false.

On the mapthe agent searches the kitchen for a coffee table, finds none before the budget runs out, and verifies the condition as false.

3Execute. Walk to the target the program selects and stop within the success radius.

On the mapwith the condition verified false, the program selects the else branch, and the agent walks to the light in the bathroom.

Three oracles (resolved branch, condition truths in words, perfect perception) each solve one part of the task for the agent, so the ablations show which step fails: on single-room scenes mostly recognition, where a present object goes undetected and is declared absent; on real-scan houses mostly exploration, where the condition object never comes into view.

Trajectories of every agent

One panel per agent; paths are drawn from start (orange) to end (purple) as the episodes play. Success is scored where the agent stops (the dark end dot), so a path that crosses the goal circle and moves on does not count. Numbered badges mark the condition objects in check order, the target marks the goal, a tick marks a condition the agent verified in place, faded icons are the branches not taken, and a maroon condition count flags a success that checked nothing.

Episode 1 of 5

Gibson house, nested-chain instruction (Figure 3 top, Figure S2). The potted plant in the home office is present and the skateboard in the bathroom is not, so the branch ends at the kitchen sink 12.4 m away: the neurosymbolic agent verifies the plant, sweeps the bathroom for the skateboard, declares it absent and walks to the sink after 71 m. NaVid and SNav-7B stop at the plant, the other baselines never reach either room, and the trained policy wanders 203 m.

AI2-THOR, deep nested instruction (Figure 3 bottom, Figure S3). All three conditions hold and the trash bin lies 2.7 m from the start: CA-Nav is counted a success after drifting 3 m over the whole budget without approaching the laptop, the armchair or the baseball bat (maroon count); the neurosymbolic agent verifies the three objects in order and reaches the bin after 41 m; the trained policy also gets there, after 195 m of wandering.

AI2-THOR, nested instruction (Figure S4). Both conditions hold; only the neurosymbolic agent checks the dining table and the refrigerator before heading to the alarm clock. The trained policy passes both objects but turns away and ends far from the goal.

Gibson house, chain instruction (Figure S5). The first condition is a spatial relation (a toilet north-east of and above a cup): the neurosymbolic agent verifies the toilet and reaches the bed after 16 m; the trained policy also reaches the bed, but without entering the toilet's radius (maroon count); every baseline fails.

Gibson house, deep nested instruction (Figure S6). The bed in the bedroom is present and the bicycle is not, so the branch ends at the potted plant in the living room: the neurosymbolic agent verifies the bed, searches the bedroom for the bicycle and returns to the plant after 56 m; SNav-7B reaches the plant along the corridor without the bed check (maroon count); every other agent fails.

Dataset examples

One episode per instruction category in each environment: the neurosymbolic agent's camera view (left) next to its path on the floor plan (right), drawn with the conventions of Figure 3 (orange to purple = start to end, badges = condition objects in check order, target = goal, faded = branches not taken). A tick appears when the path first enters the success radius of a condition object, the rule by which the benchmark credits a checked condition; the agent's own verifier may accept the object a little earlier or later (it can reject a first view and come back), a perception cost that the paper's perception-oracle ablation prices. The AI2-THOR camera views are re-rendered in the AI2-THOR simulator at the agent's viewpoints for display; the agents saw Habitat's unlit render of the exported scenes. The other environments are shown as the agents saw them. Use the arrows, the dots, or the keyboard to switch environment.

Gibson

Simple conditional

Nested conditional

Deep nested conditional

Chain conditional

Long chain conditional

Nested chain conditional

Simple conditional

Nested conditional

Deep nested conditional

Chain conditional

Long chain conditional

Nested chain conditional

Simple conditional

Nested conditional

Deep nested conditional

Chain conditional

Long chain conditional

Nested chain conditional

Simple conditional

Nested conditional

Deep nested conditional

Chain conditional

Long chain conditional

Nested chain conditional

Main results

Model	ReplicaCAD				AI2-THOR				Gibson				Matterport3D
Model	SR	SPL	BSA	CSR	SR	SPL	BSA	CSR	SR	SPL	BSA	CSR	SR	SPL	BSA	CSR
NaVid	0.2	0.0	12.5	0.0	1.8	0.9	13.6	0.8	2.0	1.2	12.0	0.6	1.4	0.5	7.7	0.8
NaVILA	0.2	0.0	10.4	0.2	5.2	2.9	26.4	2.8	1.2	1.0	7.7	0.8	2.2	1.4	7.0	0.6
CA-Nav	0.8	0.5	11.8	0.6	2.6	1.6	13.9	1.4	1.0	0.6	6.3	0.6	0.6	0.4	5.2	0.6
Open-Nav	0.8	0.5	10.9	0.6	6.0	3.0	27.0	3.6	1.6	1.2	8.8	1.0	2.0	0.8	5.7	0.6
VLN-Zero^†	0.6	0.5	11.3	0.4	3.6	2.2	14.7	1.4	1.0	0.8	4.9	0.4	0.8	0.7	4.1	0.2
StreamVLN	0.4	0.4	14.0	0.2	3.2	2.2	22.3	2.0	4.8	3.9	12.8	2.8	1.8	1.4	7.1	0.6
SNav-7B	2.0	1.3	18.3	1.2	5.4	2.0	26.5	3.4	4.0	3.2	12.8	2.0	2.4	2.3	8.5	0.8
Trained policy (ours)	6.4	2.4	37.0	3.4	12.0	3.3	65.0	8.6	6.4	2.0	25.8	3.8	2.4	0.6	15.5	1.0
Neurosymbolic agent (ours)	33.0	5.2	71.5	25.8	30.0	4.7	74.9	27.0	8.0	1.5	29.3	6.0	3.0	0.5	21.2	2.4

Shading per column:bestsecondthird. VLN-Zero^†: goal marker, distance readout and map crop removed.

Table 3. Seven VLN agents reach the named object in a few percent of episodes, and most of their successes on branching episodes bypass the required branch. The neurosymbolic agent leads every column except SPL on the two real-scan environments.

Model	Base		Logical Depth Sweep				Chain Length Sweep
	d=1, ℓ=1		d=2, ℓ=1		d=3, ℓ=1		d=1, ℓ=2		d=1, ℓ=3
	BSA	CSR	BSA	CSR	BSA	CSR	BSA	CSR	BSA	CSR
NaVid	7.53	0.30	8.43	0.30	13.02	0.00	12.50	0.60	16.27	1.51
NaVILA	9.64	1.51	9.34	0.30	13.62	0.60	14.58	1.79	18.37	0.30
CA-Nav	9.34	2.11	7.38	0.60	8.83	0.30	11.31	1.19	12.35	0.30
Open-Nav	12.95	2.71	9.34	0.90	13.02	1.80	15.48	1.49	17.47	1.51
VLN-Zero^†	7.23	0.60	5.27	0.30	9.08	0.30	11.31	0.89	12.35	0.30
StreamVLN	11.45	1.20	10.24	1.20	13.82	1.20	16.07	1.19	19.88	2.11
SNav-7B	14.46	2.41	14.31	1.51	17.12	1.20	16.37	2.98	21.08	2.11
Trained policy (ours)	32.23	6.02	32.68	3.31	34.73	2.99	38.69	3.87	41.27	5.12
Neurosymbolic agent (ours)	46.08	19.88	47.59	15.66	47.26	14.07	53.87	15.48	50.30	12.95

Table S5 of the supplement. Branch selection accuracy and conditional success rate per complexity cell: the baselines show no trend over depth or chain length, while the neurosymbolic agent leads every cell and keeps its BSA within an eight-point band as the logic deepens.

Episode outcomes per agent, and the causes of the neurosymbolic agent's failures (% of the 1,998 episodes)

Outcomesgoal reached after the branchgoal reached, branch skipped (bypass)branch completed, goal missedbranch and goal both missed

Causes of the agent's failurescondition misjudgedright object, wrong instancetarget never foundstopped outside the radius

Outcome classes of every agent come from the branch-subset analysis of the supplement (Table S10): the goal reached after visiting the condition objects of the correct branch, the goal reached without them (a bypass), the branch completed without the goal, or neither. The third bar, drawn under the agent's non-success part at the same scale, splits the episodes that did not reach the goal by the first failing stage read from its decision log (Table S7); bypass episodes reached the goal and are not failures, so they are not in it.

BibTeX

@inproceedings{anonymous2027condvln,
  title     = {If, Then, Otherwise: Diagnosing Conditional Branching in Vision-Language Navigation},
  author    = {Anonymous},
  booktitle = {Under review},
  year      = {2027}
}

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

Abstract

Benchmark

Benchmark statistics

Neurosymbolic reference agent

Trajectories of every agent

Dataset examples

Main results

BibTeX

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