Conformal Prediction for Vision-and-Language Navigation in Discrete Graphs
Vision-and-Language Navigation (VLN) agents operating in unseen buildings commit to incorrect moves with high confidence and no internal signal of error, so early deviations compound into terminal navigation failures. A deployed agent needs a calibrated estimate of when to query a human operator before that happens. Conformal Prediction (CP) offers a distribution-free, finite-sample guarantee that the correct action lies in a prediction set at an operator-chosen risk level, but it was never validated on the concentrated, sequential softmax distributions that modern VLN transformers produce.
Standard CP scoring breaks on navigation for two structural reasons, not one. First, well-trained VLN policies are sharply concentrated (mean top-action probability 0.80-0.84 on R2R val-unseen), which pushes standard classification scores toward zero until the calibrated threshold stops responding to the risk level at all and collapses into uninformative singleton sets. Second, a navigation episode is a sequence: its steps are strongly dependent, so calibrating step-by-step violates the exchangeability assumption split CP requires, and the seen-to-unseen shift a deployed agent faces erodes coverage further still. Any fix has to hold across architecturally distinct backbones, generalise past the single benchmark it was tuned on, and translate into an operating rule that a human supervisor can actually act on.
Normalise any base nonconformity score by the policy's residual confidence, dividing by one plus that residual, and calibrate over the maximum score across an entire episode rather than per step. The rescaling is parameter-free, adds no trainable weights or inference latency, and restores the threshold's sensitivity to the operator-chosen risk level exactly where the raw score had saturated.
Proved the normalised score is an instantiation of sequence-level conformal calibration for variable-length discrete-graph navigation: under episode-level exchangeability alone, the prediction set covers the correct action over the whole trajectory at every risk level, holding regardless of how dependent the steps within an episode are. A learned weight variant satisfies the same guarantee at the cost of an extra calibration split, but contributes little once the confidence floor is in place.
Benchmarked across four transformer backbones spanning a wide success-rate spread and three base scores, maintaining valid coverage in every configuration tested. A threshold calibrated on one backbone transfers directly to every other backbone's test split, because the rescaling maps distinct policies onto a shared confidence scale, so a transferred threshold is a usable warm start for a new platform ahead of local recalibration.
Extended the evaluation to a remote object-grounding benchmark beyond the original navigation task, confirming the navigation-level guarantee holds under a genuinely different objective, while showing the object-grounding head needs a small in-distribution recalibration split under the same covariate shift. Closed the loop by wiring the prediction set into a help-seeking policy that queries a human operator only on the steps it flags, lifting navigation success substantially at a modest query rate and beating an uncalibrated confidence cutoff on the same operating budget.
Establishes that a single parameter-free rescaling, not a more complex temporal or learned correction, restores valid and risk-responsive uncertainty on overconfident navigation policies, with a proof that holds across architectures and generalises to a second benchmark. The closed-loop result turns a coverage guarantee into an operating rule: an operator answering only the flagged steps recovers most of the success gap to a fully supervised agent at a fraction of the query volume.