ENCP: Episode-Normalized Conformal Prediction for Vision-and-Language Navigation
Navigation agents often make confident wrong moves in unfamiliar buildings. Then early errors compound until the route fails. Therefore, a deployed agent needs a tested rule for asking a person for help. Conformal prediction uses calibration examples to form sets of actions with a chosen coverage target. However, it had not been validated on modern navigation transformers’ sharp probabilities across linked steps.
Standard conformal scores fail here for 2 reasons. First, trained policies assign 0.80–0.84 mean probability to their top action in R2R val-unseen. Scores then crowd near zero, so thresholds stop responding to the chosen risk. Second, route steps depend on each other, while split conformal prediction assumes exchangeable calibration units. Exchangeability requires that reordering those units leaves their probabilities unchanged. Moreover, deployment shifts from seen to unseen buildings.
A valid fix must work across model designs and transfer beyond 1 benchmark. It must also support a clear rule for seeking human help.
I rescale each nonconformity score, which measures how poorly an action fits the model’s prediction. I divide it by 1 plus the policy’s residual confidence. Then I calibrate using the maximum score across a whole episode. The method adds no weights or inference delay. Moreover, it restores sensitivity to the chosen risk level where raw scores had saturated.
I proved sequence-level conformal calibration for variable-length graph navigation using the rescaled score. Under episode-level exchangeability, the prediction sets cover correct actions across the full route at each risk level. Dependence between steps preserves this guarantee because calibration treats whole routes as units. A learnt weight also works, yet needs another calibration split. Moreover, it adds little after the confidence floor.
I tested 4 transformer backbones and 3 base scores. All 36 settings met their coverage target in the tests. Moreover, thresholds transferred across all backbone pairs because rescaling put the policies on 1 confidence scale. A transferred threshold can initialise a new platform before local calibration.
I extended the test to remote object grounding, where the agent locates an object at its destination. Navigation coverage held in tests under the new goal. However, object grounding needed a small local calibration split under the changed conditions. Then I connected prediction sets to a help-seeking policy. The agent asked a person only on flagged steps and raised success from 71% to 91%. Moreover, it beat an uncalibrated cutoff at the same query budget.
Rescaling without learnt parameters restored valid uncertainty estimates that respond to the chosen risk level. It needed no learnt or temporal correction. Moreover, the proof holds across model designs under its stated assumptions. Tests also showed transfer to a second benchmark. In closed-loop tests, a person answered only flagged steps. This recovered most of the gap to full supervision with far fewer queries.