On the Evaluation of Vision-and-Language Navigation Instructions

1 Introduction

• A dual-encoder model projects instructions and trajectories into a shared latent space to assess their compatibility without reference instructions.The independent encoders facilitate using contrastive and classification losses.Source: Figure 1 · p. 1, §1 · p. 2
• Speaker-Follower and EnvDrop instructions perform on par with or only slightly better than a template-based system, and far worse than human instructions in human wayfinding trials.The gap leaves headroom for better instruction generation, which may in turn improve agents’ wayfinding abilities.Source: §1 · p. 1
• Adding contrastive losses to pairwise classification improves AUC by 9–10%, while back-translation and trajectory and instruction perturbations also improve training.Round-trip back-translation paraphrases positive examples, and both kinds of perturbation provide hard negatives.Source: §1 · p. 2
• BLEU, ROUGE, METEOR, and CIDEr are ineffective for evaluating grounded navigation instructions; SPICE is recommended for system-level evaluation when references are available.SPICE correlates with human wayfinding performance and subjective instruction-quality judgments when scores are averaged over many instructions.Source: §1 · p. 2
• For individual-instruction scoring, the compatibility model most closely reflects human wayfinding performance, outperforming BERTScore and VLN agent-based scores.The paper also calls for validating textual metrics against human judgments in new domains.Source: §1 · p. 2

Navigation Instruction Generation

• Earlier route-instruction systems used map representations, while more recent work generates instructions to improve wayfinding agents.Earlier systems included interactive directions and advance instructions designed to withstand misinterpretation.Source: §2 · p. 2
• Speaker-Follower and EnvDrop generate R2R data-augmentation pairs from panorama sequences, producing approximately 170k new instruction-trajectory pairs from training environments.Both are attention-based sequence-to-sequence models.Source: §2 · p. 2

Vision-and-Language Navigation

• R2R is a common VLN dataset, and the paper notes related datasets including Touchdown, CVDN, REVERIE, and multilingual RxR.R2R includes train, validation-seen, and validation-unseen path splits.Source: §2 · p. 2

Text Generation Metrics

• Text-generation metrics used in image captioning are reference-based and do not specifically assess navigation instructions’ 3D trajectory grounding and sequencing.The reviewed metrics include BLEU, METEOR, ROUGE, CIDEr, SPICE, BERTScore, and BLEURT.Source: §2 · p. 2

Instruction-Trajectory Compatibility Models

• The compatibility model builds on Huang et al. (2019) but adds focal and contrastive losses, action and geometry features, and instruction perturbations for negative mining.Unlike Majumdar et al. (2020), it uses dual encoders rather than dense cross-attention, enabling minibatch-wide contrastive losses that improve AUC by 10%.Source: §2 · pp. 2–3

Results

• The evaluation covers Speaker-Follower and EnvDrop instructions for R2R validation-seen and validation-unseen trajectories, alongside Crafty, new human instructions, and three human-instruction perturbations.The respective models were trained on the R2R train split, and their generated instructions came from the model authors.Source: §3 · p. 3

Instruction Perturbations

• The three adversarial perturbations target incorrect directions, hallucinated entities, and repeated or skipped steps.Direction swaps change directional phrases; entity swaps exchange noun phrases; phrase swaps alter or reorder sentence subtrees.Source: §3 · p. 3

Wayfinding Task and Evaluation Metrics

• Each instruction is followed by three wayfinders using first-person panoramic views and graph-based movement controls.Evaluation includes navigation error, success rate, SPL, SDTW, subjective quality, visual-search cost, and completion time.Source: §3 · pp. 3–4

Results

• Human instructions perform best on path metrics and subjective quality and incur the lowest visual-search costs; Speaker-Follower is on par with Crafty, while EnvDrop is only slightly better.Both learned generators perform worse than even adversarially perturbed human instructions; time is the exception to human instructions’ dominance.Source: Table 1 · p. 4, §3 · p. 4
• Results summarize 11,886 wayfinding attempts by 37 English-speaking annotators, whose performance remained consistent over time without signs of adaptation.The consistency check helps contextualize the reported human-wayfinding comparisons.Source: §3 · p. 4

4.1 Model Structure

• The model encodes instructions and trajectories into a shared latent space and scores their compatibility using the cosine similarity of their representations.Instruction tokens are encoded with a bidirectional LSTM using BERT embeddings; a two-layer LSTM processes visual features along the trajectory.Source: §4.1 · pp. 4–5

4.2 Hard Negative Mining

• Hard-negative mining adds instruction perturbations and trajectory perturbations, including the newly introduced viewpoint swap.Training uses positive R2R instruction–trajectory examples, expanded with round-trip back-translation, and unmatched pairs as negatives.Source: §4.2 · p. 5

4.3 Loss Functions

• Training combines binary classification losses on diagonal scores with contrastive loss over minibatch rows and columns, using focal loss or cross-entropy for classification.The contrastive term excludes perturbed diagonal pairs; the combined objective weights the two loss types with β = 1.Source: §4.3 · pp. 5–6
• The ablation table reports final test AUC for models selected on validation data and best AUCs for six individual perturbations.Its models vary in whether they use paraphrased positives and path and/or instruction-perturbed hard negatives.Source: Table 2 · p. 6

5 Experiments

• The experiments evaluate classification on val-unseen and val-seen splits, data augmentation against random sampling, and metric correlations at both instance and system levels.The correlation analysis includes standard textual metrics, model-based scores, and assessments over all systems as well as model-generated instructions.Source: §5.1 · p. 6, §5.2 · p. 7, §5.3 · p. 8

5.2 Data Augmentation for VLN

• Compatibility-ranked Speaker-Follower instruction-trajectory pairs consistently outperform random samples of the same size when used to train VLN agents.The figure reports the advantage across tested fractions; the difference is greater when training uses only augmented paths.Source: Figure 2 · p. 7, §5.2 · p. 8

5.1 Instruction Classification

• The best classification model achieves 73.7% test AUC and consistently outperforms the prior-work benchmark by a large margin.It combines contrastive and focal loss, paraphrased instructions, BERT embeddings, and trajectory and instruction perturbations.Source: §5.1 · p. 7
• Using only instruction perturbations, only path perturbations, or no perturbations performs considerably worse than the best classification model.Trajectory perturbations score higher than instruction perturbations; Phrase Swap is the hardest task and Random Walk the easiest.Source: §5.1 · p. 7

5.3 Correlation with Human Wayfinders

• At the system level, SPICE shows the desired correlation with human wayfinding outcomes, while BLEU, ROUGE, METEOR, and CIDEr show no correlation.Model-based approaches also lack the desired correlation and have wide confidence intervals for the evaluated systems.Source: Table 3 · p. 8, §5.3 · pp. 8–9, Figure 3 · p. 9
• The compatibility score shows the strongest correlation among metrics when scoring individual instructions, particularly for model-generated instructions, performing similarly to an ensemble of three VLN agents.SPICE has high variance and does not correlate with wayfinder performance at the instruction level.Source: §5.3 · p. 9

• BLEU, CIDEr, METEOR, and ROUGE are ineffective for grounded navigation instructions, while SPICE is the exception.Source: §6 · p. 9
• The instruction-trajectory compatibility model outperforms existing automatic metrics on instance-level evaluation without requiring reference instructions.The model can be used as a reward function, GAN discriminator, or filter for data augmentation.Source: §6 · p. 9
• For model selection with reference instructions, the paper recommends SPICE; in other scenarios, it recommends learned instruction-trajectory compatibility.Source: §6 · p. 9

• EnvDrop and Speaker-Follower score highest, while human instructions score poorly and Crafty scores lowest.Source: A Automated metric scores for all… · p. 12
• Human instructions score on par with perturbed instructions, despite automated scores diverging significantly from human wayfinding performance.Source: A Automated metric scores for all… · p. 12
• BLEU, CIDEr, and ROUGE score human instructions poorly compared with neural net models.Source: Table 4 · p. 12, A Automated metric scores for all… · p. 12

• Crafty uses a Hidden Markov Model to select objects as reference landmarks for wayfinding.Source: B Crafty Details · p. 12
• Its four components are the Appraiser, Walker, Observer, and Talker.Source: B Crafty Details · p. 12

• The Appraiser treats panoramas as documents and visible object categories as words, then computes per-category inverse document frequency scores.Source: §B.1 · p. 12

B.2 Walker

• Given a path and initial heading, the Walker computes panorama entry and exit headings, retrieves visible objects, and represents source-to-goal motion in tuples.Source: §B.2 · p. 12

B.3 Observer

• The Observer’s environment-specific HMM models panorama-object emissions and object-to-object transitions, then uses Viterbi to infer an object sequence for the path.The model favors fixation on nearby salient objects across steps and transitions toward connected objects.Source: §B.3 · p. 12

B.4 Talker

• The Talker uses templates to turn Walker motion sequences and Observer object observations into English instructions for each step.Source: §B.4 · p. 12

B.4.1 Low-level templates

• Single-step templates cover movement, a fixated object, and its relation to the agent; movement phrases are sampled by direction type and object orientation is expressed with matching phrases.Direction types include UP and DOWN based on relative pitch.Source: §B.4.1 · pp. 12–13

B.4.2 High level templates

• Start, intra-panorama, and inter-panorama templates respectively verify position, pair movement with object orientation, or add object verification while moving between panoramas.Source: §B.4.2 · p. 13
• Multi-step templates collapse repeated actions and describe movement relative to the fixated object’s direction at the last action.Source: §B.4.2 · p. 13
• Crafty’s instructions are more verbose than human instructions but are often easy to follow when the environment offers good, visually salient landmarks.Source: §B.4.2 · p. 14

C Human Rater Performance Over Time

• Across all 9 datasets, human rater performance showed no systematic drift, indicating no overall self-correction affecting the wayfinding results.The authors describe these results as reliable and robust over time.Source: C Human Rater Performance Over Time · p. 14, Figure 5 · p. 15
• For Direction Swap, Entity Swap, and Phrase Swap, human performance also showed no significant systematic drift over time.These method-specific averages had greater uncertainty because they used fewer data points.Source: C Human Rater Performance Over Time · p. 14, Figure 6 · p. 15
• The analysis normalized each rater’s scores over time and averaged examples in bins to examine performance trends.Figure 5 used 50-example bins; Figure 6 used 15-point bins for each rater before aggregation.Source: Figure 5 · p. 15, Figure 6 · p. 15