ENCP: Episode-Normalized Conformal Prediction for Vision-and-Language Navigation
Navigation agents often make confident wrong moves in unfamiliar buildings. Early errors then compound until the route fails. A deployed agent needs a calibrated rule for asking a person for help. Conformal prediction can guarantee that the correct action lies in a prediction set at a chosen risk level. It had not been validated on the sharp, sequential probabilities produced by modern navigation transformers.
Standard conformal scores fail here for two reasons. First, trained policies put 0.80–0.84 mean probability on their top action in R2R val-unseen. Scores then crowd near zero, and thresholds stop responding to the chosen risk. Second, steps within a route depend on each other, while split conformal prediction assumes exchangeable calibration units. Deployment also shifts from seen to unseen buildings. A valid fix must work across model designs, transfer beyond one benchmark, and support a clear human-help rule.
I normalise each nonconformity score by dividing it by one plus the policy's residual confidence. Calibration uses the maximum score for a whole episode. The method adds no weights or inference delay. It restores sensitivity to the chosen risk level where the raw score had saturated.
I proved that the normalised score gives sequence-level conformal calibration for variable-length graph navigation. Under episode-level exchangeability, the prediction set covers the correct action across the full route at every risk level. Dependence between steps does not break the guarantee. A learned weight also works but needs another calibration split and adds little after the confidence floor.
I tested four transformer backbones and three base scores. All 36 settings met their coverage target. Thresholds also transferred across all backbone pairs because the rescaling put different policies on one confidence scale. A transferred threshold can initialise a new platform before local calibration.
I extended the test to remote object grounding. The navigation guarantee held under the new goal, while object grounding needed a small local calibration split under shift. I then connected the prediction set to a help-seeking policy. It asked a person only on flagged steps, raised success from 71% to 91%, and beat an uncalibrated cutoff at the same query budget.
One parameter-free rescaling restored valid, risk-sensitive uncertainty without a learned or temporal correction. The proof holds across model designs, and the result transfers to a second benchmark. In closed-loop tests, a person answered only flagged steps and recovered most of the gap to full supervision with far fewer queries.