When a Robot Should Ask for Directions

A robot following natural-language instructions through a building faces a problem that autonomous driving solved differently: the compounding error. One wrong turn changes everything the robot sees next, forcing it to act on invalid environmental states. In a benchmark, a wrong turn lowers a score. In a physical building, it leads to a collision or a failed delivery. The robot needs to know, at each step, whether it is confident enough to proceed or should ask a human for help.

Vicky Feliren, A. Taufiq Asyhari, and Muhamad Risqi U. Saputra from Monash University propose a method called Episode-Normalized Conformal Prediction (ENCP) that gives vision-and-language navigation agents a formal, tunable way to decide when to act and when to defer. The key idea: calibrate uncertainty at the episode level, not the step level, and let the size of the prediction set serve as a help-seeking signal.

Why Standard Conformal Prediction Fails for Navigation

Conformal prediction is a statistical framework that converts point predictions into valid prediction sets. Given a miscoverage level alpha, it returns a set of plausible actions whose size the user can interpret: a one-action set means proceed, a larger set means ask. The framework guarantees that the set includes the correct action at the requested rate, without requiring the model's probabilities to be calibrated.

But standard conformal prediction assumes that calibration and test examples are exchangeable, meaning their joint distribution does not change when their order is permuted. In vision-and-language navigation, this assumption breaks at the step level. Each action changes the agent's state and affects the observations and decisions that follow. Steps within an episode are statistically dependent. Episode lengths vary. Using individual steps as calibration examples overlooks this dependence and provides no guarantee for the route as a whole.

The authors demonstrate this experimentally. When they pool steps across episodes and calibrate using standard split conformal prediction, the resulting threshold does not exceed small values whenever enough calibration scores are below epsilon. For alpha equals 0.30, the APS and RAPS scores return only the policy's maximum-probability action on DUET and HAMT. Split conformal prediction undercovers across most settings, making its nominal risk level unreliable. Modifying the policy's probability calibration does not resolve this quantile-selection phenomenon.

The ENCP Mechanism

ENCP addresses this with two core mechanisms. First, confidence-adjusted scoring. For any base nonconformity score, ENCP divides by a weight that depends on the policy's confidence. The parameter-free variant uses the complement of the maximum action probability as the weight. This normalizes each step's nonconformity score relative to how uncertain the policy is at that step. When the policy is confident, the denominator is close to one and the score is barely changed. When the policy is uncertain, the denominator increases and the effective threshold for inclusion in the prediction set rises, admitting more actions.

The normalization preserves the policy's action ranking at each step because every candidate shares the same denominator. It changes set membership through an effective threshold that depends on the policy's maximum probability at that step. Lower confidence increases the effective threshold, allowing more actions into the set when the policy is uncertain.

Second, episode-level calibration. For each calibration episode of any length, ENCP computes the maximum normalized score across all its steps. Every episode contributes exactly one number, regardless of how many steps it contains. The conformal threshold is then set from these episode-level scores. Under exchangeability of calibration and test episodes, this construction covers the ground truth at every step with probability at least one minus alpha, while allowing dependence among steps within an episode.

The formal guarantee is a theorem. If the calibration and test episodes are exchangeable, the event that every ground-truth action in the test episode is covered by the prediction set has probability at least one minus alpha. The proof uses the exchangeable-rank bound: the test episode's maximum score is compared to the order statistics of the calibration episodes' maximum scores, and the standard conformal argument applies to episodes rather than steps.

The Experiments: Four Policies, Two Datasets

The evaluation uses four VLN policies from three architecture families: DUET, HAMT, and Recurrent VLN-BERT with PREVALENT and OSCAR initialization. Three nonconformity scores are tested: THR (the complement of the candidate probability), APS (the probability mass of all preceding actions when ranked by decreasing probability), and RAPS (APS with a rank penalty beyond a regularization threshold). The datasets are R2R (Room-to-Room) and REVERIE (Remote Embodied Visual Referring Expression in Real Indoor Environments).

Calibration is performed on validation-seen episodes, whose buildings appear in training. Testing is on validation-unseen episodes from disjoint building scans. This creates a distribution shift that the exchangeability assumption does not cover, making the results a test of practical robustness rather than a verification of the theoretical guarantee.

The main result is that ENCP meets all reported empirical step-coverage targets on the seen-to-unseen evaluation. Across both datasets and all four policies, ENCP keeps step coverage above one minus alpha for every backbone, score, and miscoverage level. The base scores for THR, APS, and RAPS undercover in every corresponding entry. For example, at alpha equals 0.10 on R2R val-unseen with DUET, THR step coverage under split CP is 85.4% but ENCP achieves 96.5%. At alpha equals 0.30, THR coverage is 60.8% under split CP but 89.7% under ENCP.

The cost of meeting the coverage target is larger prediction sets. The mean set size under ENCP ranges from about 3 to 9 actions depending on the policy and dataset, compared to 1 to 5 under split CP. This is the expected trade-off: the sets must be large enough to contain the correct action at the required rate, especially under the distribution shift from seen to unseen buildings.

Set Size as a Help-Seeking Signal

The practical use of ENCP is as a trigger for human assistance. When the prediction set exceeds a size budget tau, the agent asks for help instead of acting. The authors simulate this on DUET with R2R by replacing the policy's action with the ground-truth action whenever the set exceeds tau.

Without help, DUET succeeds on 71.2% of episodes. Querying on sets larger than 15 actions raises success to 76.9% at a 6.4% ask rate. Lowering tau to 8 raises success to 91.1% at a 32.3% ask rate. Querying on every non-singleton set reaches 98.8% at a 68.7% ask rate. The relationship between set size and success is monotonic: larger sets correspond to lower-confidence steps where the policy is more likely to be wrong.

The simulation uses a hypothetical ground-truth assistant with access to the goal and complete navigation graph, so it measures the upper bound on what help-seeking can achieve. Real human operators would be slower and make mistakes. But the result demonstrates that prediction-set size is a meaningful uncertainty signal that can control the frequency and timing of deferral.

Parameter-Free vs. Learning-Based Weights

ENCP supports two weight constructions for the confidence-adjusted score. The parameter-free variant uses the complement of the maximum action probability. The learning-based variant fits a small neural network to predict step features including policy entropy, maximum probability, top-two gap, log action-set size, normalized step index, and the miscoverage level alpha.

Comparing the two at alpha equals 0.10 on R2R with THR, step coverage differs by at most 0.006 across the four VLN policies. The learned variant returns larger sets on all four, with the largest increase on DUET from 6.83 to 7.63 actions. But this added set size does not produce a consistent coverage gain: coverage rises on DUET and R-osc but falls on HAMT and R-prev. The parameter-free rule provides comparable coverage with smaller sets and uses every calibration episode for threshold estimation rather than splitting calibration data between weight fitting and threshold estimation.

What Happens Under Distribution Shift

The theoretical guarantee requires exchangeable episodes. Seen and unseen buildings in R2R violate this assumption because the building layout, viewpoint graph, and instruction patterns differ. The authors report coverage under this shift as a measure of practical robustness rather than a claim of theoretical validity.

Figure 4 in the paper evaluates parameter-free ENCP under exchangeable splits (within the same pool) and under the seen-to-unseen split. Across 300 random within-pool splits, mean trajectory coverage differs from nominal by at most 0.0017 over six reported conditions and three alpha levels. Coverage is lower in the seen-to-unseen comparison, where the exchangeability assumption does not hold. The authors report these results transparently: the shift degrades coverage, but ENCP still provides substantially better coverage than split conformal prediction under the same shift.

Limitations and Practical Considerations

The closed-loop study uses a simulated ground-truth assistant, not human operators. The tau threshold was swept on val-unseen, so the resulting curve does not measure performance at a held-out deployment setting. The same tau value produces different ask rates across VLN policies because their set-size distributions differ. ENCP assumes a finite action space, and extending it to continuous VLN would require conformal scores for waypoints or continuous controls.

The larger prediction sets under ENCP are a cost, not a bug. They reflect the uncertainty that the model actually has, made explicit through calibration. A policy that claims 99% confidence but is wrong 30% of the time is less useful than a policy that admits uncertainty and defers when unsure. ENCP makes this admission formal and tunable.

For deployment, size budgets should be selected on held-out data, recalibrated under distribution shift, and validated with human operators. The set-size trigger is model-agnostic: the same ENCP framework works across DUET, HAMT, and Recurrent VLN-BERT with different base scores, producing calibrated uncertainty estimates that the policies themselves do not provide.

Calibrated Uncertainty for Embodied Agents

ENCP shows that conformal prediction can provide distribution-free uncertainty estimates for sequential navigation tasks, but only if the calibration unit matches the dependence structure of the task. Step-level calibration fails because steps are dependent. Episode-level calibration works because it collapses dependent steps into a single worst-case metric. The resulting prediction sets are larger than step-pooled sets, but they come with a formal guarantee that the sets contain the correct action at every step of a complete route.

The practical implication is that VLN agents can use prediction-set size as a reliable signal for when to defer to a more capable predictor, including human assistance. The framework is model-agnostic, requires no changes to the underlying policy, and provides a user-chosen miscoverage level that determines the frequency and timing of help-seeking. For embodied agents operating in physical spaces where errors compound and wrong turns have real consequences, this kind of calibrated uncertainty is not a nice-to-have. It is a safety requirement.

Read the paper on arXiv