ENCP: Episode-Normalized Conformal Prediction for Vision-and-Language Navigation Vicky Feliren1,2 , A. Taufiq Asyhari1 , Muhamad Risqi U. Saputra1
arXiv:2609.17499v1 [cs.LG] 15 Sep 2026
1 Monash University, Indonesia
Abstract—Uncertainty estimation for Vision-LanguageNavigation (VLN) models is a critical task since it can help identify ambiguous and unreliable predictions, enabling agents to make safer navigation decisions. As one of the most advanced uncertainty estimation frameworks, conformal prediction (CP) offers a promising approach for uncertainty estimation in VLN. However, given that VLN agent requires a sequence of steps, standard calibration in conformal prediction fails to provide coverage guarantee it promises over a dependent, variable-length VLN episode. To this end, we propose Episode-Normalized Conformal Prediction (ENCP), which rescales a nonconformity score by the policy’s residual confidence and calibrates one maximum score per episode. Under exchangeable calibration and test episodes, this construction covers the ground truth at every step with probability at least 1 − α, while allowing dependence among steps within an episode. Across four VLN policies and three nonconformity scores on R2R and REVERIE dataset, ENCP meets all reported empirical step-coverage targets on the seen-to-unseen evaluation. These results demonstrate that ENCP can provide model-agnostic uncertainty estimates, which might be useful for determining when a VLN agent should defer to a more capable predictor, including human assistance. Index Terms—vision-language navigation, conformal prediction, uncertainty quantification, human-robot interaction, safe autonomy
I. I NTRODUCTION Vision-and-Language Navigation (VLN) enables embodied agents to navigate physical environments using natural language instructions [1], [2]. Such capabilities have applications in assistive robotics, household robots, and autonomous systems operating in complex environments where agents must follow human instructions while adapting to their surroundings. Deploying these agents safely in real-world settings, however, demands reliable uncertainty estimation as sequential navigation inherently suffers from compounding errors: a single wrong turn corrupts subsequent visual feedback, forcing the agent to act on invalid environmental states [3]. While an uncorrected mistake merely degrades a benchmark score, continuing confidently while lost in physical spaces risks collisions or task failure. Consequently, agents must identify unreliable steps and request human intervention before errors accumulate [4]–[6]. This might requires simultaneously resolving linguistic ambiguity and visual uncertainty across dynamic trajectories (e.g., grounding “enter the second door”). Modern VLN policies achieve high navigation success [7]– [9], yet overall task completion metrics fail to indicate whether a specific action is trustworthy. Existing self-monitoring and help-request mechanisms recognize this limitation [10], [11],
2 SEACrowd
but they rely on empirical heuristics rather than formal calibration tied to a user-specified error rate. The policy’s largest softmax probability is often used to flag how certain the decisions, with smaller values indicating that the policy has no strongly preferred action; however, this value is not a calibrated probability that the selected action is incorrect. Because neural networks can be overconfident [12] and uncertainty estimates often deteriorate when the deployment environment differs from the training data [13], a cutoff has no distribution-free interpretation without a calibration argument. This matters in human–automation teams, where a useful warning should support appropriate reliance rather than encourage blind trust or constant intervention [14], [15]. Conformal Prediction (CP) is a statistical framework that converts point predictions into valid prediction sets. It returns a set of plausible actions at a user-chosen miscoverage (risk) level α, whose target coverage is 1 − α. A one-action set lets the agent proceed. A larger set tells it to ask. When the calibration routes and new routes are generated under the same conditions, CP guarantees that the set includes the correct choice at the requested rate. The policy’s probabilities need not be calibrated [16]–[18]. This act-or-ask interpretation has already made CP useful for robot planning and human assistance [19], [20]. In the standard CP, the coverage guarantee usually applies to a single prediction. However, this approach will not work for VLN since it does not ensure that the action deemed correct is included at every step along a route [16], [18]. Each action changes the agent’s state and therefore affects the observations and decisions that follow [3]. Using individual steps as calibration examples overlooks this dependence and provides no guarantee for the route as a whole. A further limitation arises when the policy assigns nearly all of its probability to one action. This motivates the need to design a bespoke CP that can ensure its coverage guarantee over a dependent, variable-length VLN episode. In this work, we propose Episode-Normalized Conformal Prediction (ENCP), a post-training conformal prediction method for VLN that leaves the underlying navigation policy unchanged. ENCP rescales each step-level nonconformity score by the policy’s residual confidence and calibrates one maximum normalized score per episode. Under exchangeability of the calibration and test episodes, the resulting prediction sets contain the ground-truth action at every step of a test episode with probability at least 1 − α, while allowing dependence among steps within an episode and accommodating
(a) A wrong action changes observations
(b) ENCP: Route-level coverage
“Pass the sofa; enter the second doorway.”
Calibration episodes
E1 sofa
1
Wrong turn
2
(c) Prediction-set size triggers help
ENCP Exchangeable episodes
E2 . . . En
Pr{at∗ ∈ Cα (xt ), ∀t} ≥ 1−α
Simultaneous route coverage
VLN agent
Prediction set
Next observation
Goal
Wide set prompts a query before resuming
Intended
Test episode
Teacher action in Cα (xt ) at every step
High confidence, wrong action
Compact set permits autonomous action
Softmax probabilities 0.82
Left Straight
VLN agent
Prediction set
Simulated operator
Teacher action
Goal
Act-or-ask rule |C̄α (xt )| ≤ τ permits autonomous action |C̄α (xt )| > τ prompts an operator query
Fig. 1: ENCP identifies when a navigation agent should ask for help before an error compounds. It calibrates complete episodes and triggers a query when the action set exceeds a chosen size budget. variable episode lengths. Episode-level calibration provides this coverage guarantee, whereas residual-confidence rescaling helps calibrated thresholds transfer across the evaluated policies. This work makes 3 contributions. • We show how standard, step-wise CP can fail to satisfy its coverage guarantee in VLN and measure when its action sets cease to reflect the miscoverage level α. • We develop ENCP, an episode-level calibration CP with a guarantee that covers the correct action throughout a complete route. • We evaluate ENCP against step-pooled CP using 4 VLN models and 3 nonconformity scores on the R2R and REVERIE datasets, examine coverage when calibration and test buildings differ, and use prediction-set size to decide when to request an action from a simulated ground-truth assistant. II. R ELATED W ORK Vision-and-language navigation. Room-to-Room (R2R) introduced instruction following on the Matterport3D navigation graph [1], [21], and VLN later expanded to continuous control [22] and remote object grounding in REVERIE (Remote Embodied Visual Referring Expression in Real Indoor Environments) [23]. Recurrent sequence models [24] preceded transformer policies such as DUET, HAMT, and Recurrent VLN-BERT [7]–[9], evaluated here. Learned helprequest heads detect ambiguous instructions [11]; however, their reported reliability is empirical, failing to provide a finitesample guarantee at a risk level chosen by the user. Uncertainty estimation. Bayesian approximations [25], deep ensembles [26], and selective prediction [27] yield uncertainty or abstention scores, while classical robotics represents and propagates probabilistic states [28]. These methods do not generally provide distribution-free finite-sample coverage at a chosen α.
Conformal prediction for decisions and sequences. Classification CP includes threshold scores (THR), adaptive prediction sets (APS), and rank-regularized adaptive prediction sets (RAPS) [29]–[31]. Beyond classification, CP covers LLM planning, model predictive control, and multi-agent motion planning [6], [20], [32]. Specifically, KnowNo uses predictionset size to request human help, calibrating weakest confidence over a fixed plan [19]. In contrast, ENCP calibrates maximum nonconformity over a episode-length VLN trajectory, whose action set can change at every step. Dependence and distribution shift. Standard split CP assumes exchangeable calibration and test units. Methods for nonexchangeable data can bound the resulting coverage loss [33], while conformal time-series methods allocate risk across a fixed horizon [34]. ENCP uses the complete episode as its calibration unit, so steps within an episode may depend on one another and no fixed horizon is needed. However, this design choice does not remove the distribution shift. R2R calibrates on seen buildings and evaluates on unseen buildings. Weighted CP can correct covariate shift when density ratios are available [35]. We report coverage under exchangeable splits and across the seen-to-unseen boundary. III. P ROBLEM F ORMULATION In this section, we formulate VLN as sequential classification in discrete graph, define the 3 nonconformity scores used in commonly used CP, and show why calibration over pooled steps does not yield trajectory-level coverage. An experimental condition is one policy–dataset pair. A. VLN as a discrete graph An episode is one attempt to follow an instruction L from a given start node. The agent moves on an undirected graph of panoramic Matterport3D viewpoints [21] and terminates by selecting STOP. At step t, let ot denote the current panorama,
p(a | xt ) = πθ (a | xt ),
a ∈ At ,
(1)
and define pmax (xt ) = maxa∈At p(a | xt ). We write pmax for pmax (xt ) when considering a step t. The action-set size varies with the local graph degree. For example, DUET’s global branch additionally considers the reachable frontier [9]. Section V treats each resulting episode as one calibration or test unit. B. Nonconformity scores and split-conformal calibration In conformal prediction, a nonconformity score measures how atypical a candidate output appears relative to a model’s prediction, with higher values indicating greater disagreement or lower confidence. In VLN, we instantiate this score as s(xt , a) and assigns larger values to actions that conform less closely to the policy output at xt . The score must be fixed before conformal calibration. For a labeled decision context (xt , at∗ ), its calibration score, the nonconformity score assigned to the ground-truth action, is s(xt , at∗ ). In this work, we use THR and the deterministic (U = 0) forms of APS and RAPS as standard non-conformity scores. Here, U ∼ Uniform(0, 1) is an auxiliary variable that randomizes the contribution of the candidate action’s probability mass; setting U = 0 removes this randomization. THR is the complement of the candidate probability [29]: sTHR (xt , a) = 1 − p(a | xt ).
(2)
APS orders actions by decreasing p(a | xt ), with ties resolved by a fixed rule. Let rankt (a) ∈ {1, . . . , |At |} denote the resulting position of action a. APS assigns to a the probability mass of all preceding actions [30]: sAPS (xt , a) =
∑
b∈At : rankt (b)<rankt (a)
p(b | xt ).
(3)
Thus the top-ranked action has score 0. RAPS adds a penalty beyond rank kreg [31]: sRAPS (xt , a) = sAPS (xt , a) + λ rankt (a) − kreg + , (4)
where [u]+ = max(u, 0); we use λ = 0.1 and kreg = 2. For standard split CP, let s1 , . . . , sn be exchangeable calibration scores for one fixed score function. Exchangeability in conformal prediction means that the joint probability distribution of a sequence of data points does not change when their order is permuted. Given a miscoverage level α ∈ (0, 1), set k = ⌈(n + 1)(1 − α)⌉. If s(k) denotes the k-th order statistic, the conformal threshold is ( s , k ≤ n, q̂(α) = (k) (5) +∞, k = n + 1.
The corresponding prediction set is Cα (xt ) = {a ∈ At : s(xt , a) ≤ q̂(α)}.
(6)
0.4
Split CP: calibrate pooled steps using base scores ENCP: calibrate one maximum score per episode
Split CP
0.3
Step-coverage margin
ht the preceding observation–action history, and At the admissible actions, comprising adjacent viewpoints and STOP. We write xt = (L, ot , ht , At ) for the complete decision context. Define the policy probability of action a by
ENCP
0.2 0.1 0.0 −0.1 −0.2
Below target
0.1
0.2
0.3
0.4
0.5
Requested miscoverage α
Fig. 2: Split CP undercovers across most settings, making its nominal risk level unreliable here. ENCP calibrates one maximum normalized score per episode and meets the target throughout. Negative values indicate undercoverage. If the calibration scores and the test score s(xt , at∗ ) are exchangeable, then P{at∗ ∈ Cα (xt )} ≥ 1 − α. C. Why split CP degenerates here
The pooled-step baseline CP treats each labeled step as an independent calibration unit. By (5), the resulting threshold does not exceed ε whenever at least k calibration scores are ≤ ε. For α = 0.30, APS and RAPS return only the policy’s maximum-probability action on DUET and HAMT, with THR exhibiting analogous behavior. Split CP similarly demonstrates undercoverage across the evaluated configurations (Figure 2). Moreover, modifying the policy’s probability calibration does not resolve this quantile-selection phenomenon (Section VII). Split CP assumes that calibration and test scores are exchangeable. However, exchangeability at the level of complete episodes does not generally entail exchangeability of the individual time steps obtained by pooling steps across episodes. Within an episode, time steps are statistically dependent due to their shared action–observation history; episode lengths may differ; and actions can causally influence subsequent observations, further violating step-wise exchangeability. Moreover, marginal coverage guarantees for a single time step do not imply simultaneous coverage across all time steps within an episode. Accordingly, the subsequent section defines a mapping from each episode to a single calibration score. IV. E PISODE -N ORMALIZED C ONFORMAL P REDICTION Standard CP calibration fails to provide coverage guarantees in sequential VLN due to intra-episode step dependencies and dynamic action spaces. To resolve this, Episode-Normalized Conformal Prediction (ENCP) derives its name from two core mechanisms: episode-level calibration, which collapses dependent trajectory steps into a single worst-case metric to restore finite-sample guarantees, and score normalization, which
adjusts nonconformity scores relative to step-varying policy confidence. ENCP can be implemented as either a parameterfree variant using raw policy probabilities or a learning-based variant that fits score weights prior to calibration (Figure 3). A. Confidence-adjusted score For any base score sbase ∈ {sTHR , sAPS , sRAPS } and fixed nonnegative weight rule w, ENCP defines snorm (xt , a) =
sbase (xt , a) . 1 + w(xt )
(7)
Here, xt denotes the decision context at step t, a ∈ At is a candidate action, sbase is the nonconformity score, w(xt ) is its confidence-dependent weight, and snorm is the resulting confidence-adjusted nonconformity score. a) Parameter-free weight: wpf (xt ) = 1 − pmax (xt ), sbase (xt , a) . spf norm (xt , a) = 2 − pmax (xt )
(8)
At a fixed step, every candidate shares the same positive denominator. The normalization therefore preserves the policy’s action ranking. It changes set membership through the effective threshold a ∈ Cα (xt )
⇐⇒
sbase (xt , a) ≤ q̂(α)[2 − pmax (xt )].
(9)
Thus, lower confidence increases the effective threshold and can admit more actions. Episode calibration addresses this remaining point mass by changing the calibration unit. b) Learning-based weight: The learning-based variant uses step features to predict the weight. We define φ (xt ) = H(pt ), pmax , p(1) − p(2) , log |At |, t/Tmax , α] , wψ (xt ) = softplus fψ (φ (xt )) ≥ 0,
(10)
Here, H(pt ) is entropy over the candidate actions, pmax is the largest action probability, and p(1) − p(2) is the top-two probability gap. The term log |At | is the log action-set size, t/Tmax is the normalized step index, and α is the requested miscoverage level. The network fψ has two ReLU hidden layers of width 32; its Softplus output keeps the denominator in (7) positive. We train the network to assign more weight to steps where the policy is confident but gives little probability to the groundtruth action. For each labeled step in fit subset H1 , the target is 1 − p(at∗ | xt ) yt = clip , 0, 10 . (11) 1 − pmax (xt )
is fixed before calibration, so H2 remains exchangeable with a test episode. Using H2 for both fitting and calibration would invalidate this split-conformal argument. B. One calibration score per episode For calibration episode e of length Te , ENCP computes s̃e = max snorm (xe,t , a∗e,t ). 1≤t≤Te
(13)
Every episode contributes one number, regardless of its length. We require exchangeability across episodes but make no such assumption about steps within an episode. For parameter-free ENCP, bounding the maximum bounds every step and gives simultaneous trajectory coverage (Theorem 1). The maximum is zero only when all step scores are zero. This condition makes a zero threshold less common than under step-pooled calibration (Proposition 1). C. Calibration and deployment Let r = n for the parameter-free variant and r = m = |H2 | for the learning-based variant, as in Figure 3. Relabel the corresponding episode scores as s̃1 , . . . , s̃r , and set k = ⌈(r + 1)(1 − α)⌉. ENCP uses ( s̃ , k ≤ r, q̂(α) = (k) (14) +∞, k = r + 1, where s̃(k) is the k-th order statistic. At a test step, thresholding produces the raw prediction set Cα (xt ) = {a ∈ At : snorm (xt , a) ≤ q̂(α)}.
The deployed set is ( Cα (xt ), Cα (xt ) ̸= ∅, C̄α (xt ) = {arg maxa∈At p(a | xt )}, otherwise,
(15)
(16)
where the fixed policy tie-breaking rule resolves the argmax. For help-seeking, an operator may choose a size budget τ and request assistance whenever |C̄α (xt )| > τ (Section VI-C). V. C OVERAGE G UARANTEE
This section proves coverage for parameter-free ENCP. For this purpose, before calibration, we freeze the navigation policy, a base score sbase , and wpf (xt ) = 1 − pmax (xt ). For episode Ei , let xi,t and a∗i,t denote the decision context and ground-truth action at step t, and let Ti = T (Ei ) ≥ 1. Throughout this section, snorm denotes the parameter-free score. The fixed episode-score map is sbase (xi,t , a∗i,t ) . (17) ϕ(Ei ) = s̃i = max 1≤t≤Ti 2 − pmax (xi,t )
1
Assumption 1 (Exchangeable episodes). The joint distribution of the n calibration episodes and one test episode, (E1 , . . . , En , En+1 ), is invariant under permutations of their indices. In particular, the assumption holds for i.i.d. episodes from one task distribution.
After fitting on H1 , we freeze wψ and estimate the conformal quantile on disjoint subset H2 . Conditional on H1 , the score
This assumption applies to complete episodes. Steps within an episode may depend on one another, episode lengths may
Clipping limits values caused by a denominator near zero. We then minimize 2 1 L (ψ) = wψ (xe,t ) − ye,t . (12) ∑ N1 (e,t)∈H
1 Offline calibration Calibration episode records
Policy probabilities and teacher actions for each calibration episode
Shared ENCP reduction
Choose one weight construction
A Parameter-free
Policy probabilities and teacher actions
All n episodes; no fitting
E1
3. Conformal quantile
2. Maximum within each episode
1. Normalize scores
w = 1 − pmax (xt )
q̂(α)
sbase snorm = 1+w
r = n (A); r = m = |H2 | (B) k = d(r + 1)(1 − α)e
B Learning-based E2
H1
. . .
fit
En
Feature vector φ (xt )
MSE target yt
Parameter-free guarantee (A). If episodes are exchangeable, steps within an episode may remain dependent, and P a∗n+1,t ∈ Cα (xn+1,t ) ∀t ≤ Tn+1 ≥ 1 − α.
frozen wψ
6–32–32–1 Softplus output
Episode score. s̃e = max snorm (xe,t , a∗e,t )
H2
1≤t≤Te
=⇒
calibrated q̂(α)
quantile
Teacher action
2 Deployment At a test step Navigation policy
State xt
Selected weight A
q̂
or
B
p(a | xt ), a ∈ At
Flow
Processing order
Markers
Teacher action
Set membership
a ∈ Cα
a∈ / Cα
a1
frozen wψ (φ (xt ))
Path A: weight and deployed q̂ Episode maximum
Calibrated q̂
Within size budget
Prediction set Cα
Normalized scores
1 − pmax
a3
a2
a5
a4
Cα (xt ) = {a ∈ At : snorm (xt , a) ≤ q̂(α)}
|C̄α | ≤ τ Autonomous action Exceeds size budget
|C̄α | > τ Operator query
Path B: held-out H2 episodes Apply frozen wψ to H2
Deployed C̄α = Cα when nonempty; otherwise use the policy argmax.
Fig. 3: ENCP calibrates one worst-step score per episode, then asks for help when the deployed set exceeds τ. vary, the navigation policy may be miscalibrated, and the scores may contain ties or point masses. For the test episode, let Tn+1
En+1 =
\
t=1
{a∗n+1,t ∈ Cα (xn+1,t )}
(18)
be the event that every ground-truth action is covered. Define simultaneous trajectory coverage Covtraj and step-averaged coverage Covstep by Covtraj = P(En+1 ), " # 1 Tn+1 ∗ Covstep = E ∑ 1{an+1,t ∈ Cα (xn+1,t )} . Tn+1 t=1
(19) (20)
Theorem 1 (Simultaneous trajectory coverage). Fix α ∈ (0, 1) and let k = ⌈(n + 1)(1 − α)⌉. Define q̂(α) as the k-th smallest value among the calibration scores s̃1 , . . . , s̃n , with q̂(α) = +∞ if k = n + 1. Under Assumption 1, P(En+1 ) ≥ 1 − α.
Proof. Let q̂ = q̂(α). By (15) and (17), En+1 = max snorm (xn+1,t , a∗n+1,t ) ≤ q̂ 1≤t≤Tn+1
= {s̃n+1 ≤ q̂}.
(21)
(22)
Because ϕ is fixed, the scores s̃1 , . . . , s̃n+1 are exchangeable. Suppose first that k ≤ n, and let u(k) be their k-th order statistic.
Removing s̃n+1 cannot decrease the k-th order statistic, so q̂ ≥ u(k) . The exchangeable-rank bound [18] gives k ≥ 1 − α. (23) n+1 If k = n + 1, then q̂ = +∞ and the probability is 1. Equation (22) now proves (21). Since Cα (xt ) ⊆ C̄α (xt ), the deployed set has at least the same coverage. P(s̃n+1 ≤ q̂) ≥ P(s̃n+1 ≤ u(k) ) ≥
Corollary 1 (Step-averaged coverage). Under Assumption 1, the threshold of Theorem 1 also satisfies Covstep ≥ 1 − α.
Proof. Let
Rn+1 =
1
Tn+1
∑ Tn+1 t=1
1{a∗n+1,t ∈ Cα (xn+1,t )}
be the covered-step fraction in the test episode. Pointwise, Rn+1 ≥ 1{En+1 }.
Taking expectations and applying Theorem 1 gives Covstep ≥ Covtraj ≥ 1 − α. Figure 4 evaluates parameter-free ENCP under the theorem’s premise and across the shifted benchmark split. Across 300 random within-pool splits, mean Covtraj differs from nominal by at most 0.0017 over the 6 reported conditions and 3 α levels. Coverage is lower in the seen-to-unseen comparison, where episode exchangeability is not assumed. The guarantee in Theorem 1 is marginal over the calibration and test episodes; it does not condition on a realized calibration
α = 0.30
-0.04
ET
DU
MT HA
rev
R-p
sc
R-o
ET
DU
(RE
V) M HA
EV)
T (R
Target 0.90
0.8 0.7
0.93
0.9
0.87
0.00 -0.02
1.0
0.84
0.02
0.86
0.04
Seen-to-unseen split
(b) Exchangeability premise
0.83
Trajectory-coverage margin
(a) Exchangeable splits (300 repetitions)
Exchangeable split
0.82
α = 0.20
Trajectory coverage at α = 0.10
α = 0.10
0.6
ET
DU
MT HA
rev R-p
sc
R-o
ET
DU
(RE
V)
EV)
T (R
M HA
Fig. 4: Parameter-free ENCP attains nominal trajectory coverage under episode exchangeability but not under seen-to-unseen shift. Error bars are empirical 95% ranges over 300 exchangeable splits; the shifted bars lie outside Theorem 1’s premise. sample [17]. Ties may make the bound conservative. The episode maximum avoids allocating α across time. Proposition 1 (Condition for a zero threshold). For parameter-free ENCP, all 3 base scores in Section III are nonnegative. For any calibration episode e, sbase (xe,t , a∗e,t ) = 0 for every t = 1, . . . , Te . (24) Consequently, q̂(α) = 0 exactly when at least k = ⌈(n + 1)(1 − α)⌉ of the n calibration episodes have zero score at every step. s̃e = 0
⇐⇒
Proof. The denominator 2 − pmax (xt ) lies in [1, 2], so normalization preserves zeros. A maximum of nonnegative numbers is zero exactly when every number is zero. The k-th order statistic is zero exactly when at least k observations are zero. The construction is the score-space counterpart of calibrating minimum confidence over a plan [19, Prop. 2], extended here to variable-length VLN episodes with changing action sets. Remark 1 (Scope under distribution shift). The guarantee is marginal under the episode law in Assumption 1. Seen and unseen buildings may induce different episode laws, and operator intervention changes the trajectory distribution. Section VI evaluates the seen-to-unseen setting. VI. E XPERIMENTS We calibrate on the R2R validation-seen, whose buildings occur in training, and test on validation-unseen (val-unseen) episodes from disjoint building scans [1]. We also experiment this in REVERIE [23] for a better generalization. We evaluate four VLNs from three architecture families: DUET [9], HAMT [8], and Recurrent VLN-BERT with PREVALENT and OSCAR initialization (R-prev and R-osc) [7]. Our runs reproduce each published val-unseen success rate to within one percentage point. We record prediction sets without changing the policy, except in the closed-loop study of Section VI-C. The remaining evaluations therefore retain the original policy’s success rate. Unless noted otherwise, ENCP uses the parameter-free score in (7). Base-score columns use the steppooled calibration analyzed in Section III-C.
The experiments report step coverage Covstep , the mean fraction of covered steps per episode. Set sizes include the argmax fallback, whereas coverage uses the set in (15); an empty raw set is uncovered. A. Restored α-sensitivity and step coverage Table I compares each base score with its ENCP counterpart at three miscoverage levels. Across both datasets, ENCP keeps Covstep above 1 − α for every reported backbone, score, and miscoverage level. The base scores for THR, APS, and RAPS undercover in every corresponding entry. Thus, episode calibration restores a usable response to α, but the larger ENCP sets show the cost of meeting the step-coverage target under the seen-to-unseen shift. B. Parameter-free and learning-based weights Table II compares the two weight constructions in Figure 3. One calibration half fits wψ ; both variants then estimate q̂ from the other half. This matched comparison isolates the effect of the weight. Table I uses all calibration episodes for the parameter-free variant because it requires no fitting. Neither procedure uses val-unseen data for fitting or calibration. Based on Table II, at α = 0.10, step coverage differs by at most 0.006 across the four R2R VLNs. The learned variant returns larger sets on all four, with the largest increase on DUET, from 6.83 to 7.63 actions. 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 learned target identifies confidently wrong steps, but learning changes where ENCP enlarges a set. We use the parameter-free variant for the main results because it gives comparable coverage with smaller sets and uses every calibration episode. C. Simulated ENCP help-seeking (DUET, R2R) We test one use of ENCP at deployment: the agent acts when |C̄α | ≤ τ and asks for help when |C̄α | > τ. A larger set therefore causes the agent to defer. This experiment simulates help-seeking without human operators. When ENCP requests help because |C̄α | > τ, the agent executes the ground-truth action supplied by the simulator instead of its policy-selected action. The simulator has access to the goal and complete navigation graph and is assumed to make no errors.
TABLE I: ENCP meets the step-coverage target across R2R and REVERIE; base CP undercovers. |C| is mean prediction-set size. Bold values satisfy the target coverage guarantee (1 − α). α=0.10 ENCP
Base VLN
Score
α=0.20
α=0.30 ENCP
Base
ENCP
Base
Covstep
|C|
Covstep
|C|
Covstep
|C|
Covstep
|C|
Covstep
|C|
Covstep
|C|
R2R val-unseen DUET
THR APS RAPS
0.854 0.850 0.859
2.6 2.7 2.6
0.965 0.965 0.972
6.7 6.7 5.7
0.729 0.723 0.725
1.4 1.6 1.5
0.936 0.934 0.928
6.1 6.0 4.0
0.608 0.621 0.621
1.0 1.0 1.0
0.897 0.899 0.879
5.2 5.2 3.1
HAMT
THR APS RAPS
0.883 0.881 0.883
2.4 2.4 2.7
0.943 0.943 0.936
3.8 3.8 3.6
0.726 0.720 0.721
1.3 1.3 1.3
0.888 0.888 0.875
3.1 3.1 2.6
0.608 0.626 0.626
1.0 1.0 1.0
0.825 0.818 0.820
2.3 2.2 2.0
R-prev
THR APS RAPS
0.873 0.874 0.892
2.7 2.7 3.1
0.972 0.972 0.985
4.5 4.5 4.8
0.756 0.758 0.758
1.6 1.7 1.6
0.951 0.950 0.964
4.2 4.2 4.4
0.653 0.650 0.650
1.2 1.2 1.2
0.924 0.924 0.923
3.9 3.9 3.7
R-osc
THR APS RAPS
0.886 0.883 0.891
3.1 3.0 3.2
0.971 0.971 0.988
4.5 4.5 4.8
0.736 0.736 0.739
1.7 1.7 1.7
0.938 0.939 0.962
4.1 4.1 4.4
0.624 0.619 0.620
1.1 1.2 1.2
0.907 0.908 0.928
3.7 3.7 3.9
REVERIE val-unseen, navigation head DUET
THR APS RAPS
0.871 0.869 0.830
5.3 5.4 3.7
0.975 0.976 0.964
8.8 8.8 7.1
0.692 0.703 0.663
2.7 3.0 2.2
0.932 0.933 0.879
8.1 8.1 5.0
0.521 0.539 0.536
1.2 1.5 1.4
0.898 0.897 0.802
7.6 7.6 4.0
HAMT
THR APS RAPS
0.929 0.928 0.924
4.3 4.3 4.2
0.990 0.990 0.990
5.3 5.3 5.2
0.834 0.836 0.855
3.3 3.3 3.4
0.975 0.976 0.978
5.1 5.1 5.0
0.718 0.718 0.704
2.3 2.3 2.2
0.943 0.944 0.962
4.7 4.7 4.8
TABLE II: The learned weight enlarges sets without a consistent stepcoverage gain. Results use R2R val-unseen, THR, and α = 0.10. Learning-based
VLN
Covstep
Covstep
DUET HAMT R-prev R-osc
0.968 0.952 0.973 0.970
|C|
6.83 3.95 4.56 4.49
0.974 0.949 0.971 0.971
|C|
7.63 4.01 4.60 4.63
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 τ to 8 raises success to 91.1% at a 32.3% ask rate, and querying on every non-singleton set reaches 98.8% at a 68.7% ask rate (Figure 5). Thus, ENCP set size can control how often the agent defers to assistance. This experiment does not select a deployment threshold. We sweep τ after observing val-unseen, and the same τ produces different ask rates for policies with different setsize distributions (Table I). The intervention also changes later observations, so the static ENCP coverage result does not certify the assisted trajectories. VII. D ISCUSSION What a large prediction set means. Table I reports both coverage and mean set size because coverage alone does not measure how often ENCP leaves many actions unresolved. For parameter-free THR, every admissible action enters the set exactly when q̂(α) ≥
1 − mina∈At p(a | xt ) . 2 − pmax (xt )
100
Success rate (%)
Parameter-free
(25)
Budget τ = 2 Budget τ = 7
90
At α = 0.50, most sets contain one action, limiting the ask rate
80 Budget τ = 15
70 0.0
0.2
No help (71.2)
0.4
Score and risk level THR, α = 0.10 THR, α = 0.30 THR, α = 0.50 APS, α = 0.10 APS, α = 0.30 APS, α = 0.50
0.6
Operator ask rate (fraction of steps)
Fig. 5: Simulation of ENCP help-seeking: when the prediction set exceeds the size budget, the simulator supplies the groundtruth action instead of the policy-selected action. The condition depends on the least probable admissible action, as well as the calibrated threshold and maximum policy probability. A full set signals that the size rule cannot select one action. It does not rank the candidates, so the policy still supplies their order. The different mean sizes |C| in Table I also show why one numerical size budget should not be assumed to have the same meaning across policies and datasets. Parameter-free and learned weights. Table II shows similar step coverage for the two weight constructions. In every displayed row, the parameter-free rule has the smaller mean set and requires no fitted weight model. This evidence supports using the parameter-free rule as the main ENCP variant in this paper. Table II compares one feature set, training target, and calibration split, so it does not rule out a more efficient learned
rule under another design. Coverage and efficiency. Figure 4 evaluates the stricter event that every ground-truth action in an episode is covered, whereas Table I reports the average fraction of covered steps and the corresponding mean set size. HAMT–REVERIE in Figure 4 is the only condition above the trajectory target when calibrating on validation-seen episodes and evaluating on validation-unseen episodes, although this point estimate carries no coverage guarantee because these episode sets are not exchangeable. Taking episode maximum protects the stricter event, but one difficult step can set the calibration score for the whole episode. The set sizes in Table I are therefore part of the result rather than a secondary diagnostic. Closed-loop interpretation. The THR and APS curves nearly coincide within each risk level, which indicates that the set-size trigger is not sensitive to the choice between these two scores in this simulation. The risk level has a larger operational effect. Raising α makes more sets singletons, which can improve the success rate at a comparable ask rate but also lowers the maximum attainable ask rate. Thus, τ cannot be read as a fixed operator budget, even for one policy. Limitations. The closed-loop study uses a simulated ground-truth assistant with access to the goal and complete navigation graph; no human operators were evaluated. Because the set-size threshold τ was swept on val-unseen, the resulting curve does not measure performance at a held-out deployment setting. Moreover, the same value of τ may produce different ask rates across VLN policies. ENCP also assumes a finite action space. Extending ENCP to continuous VLN [22] would require conformal scores for waypoints or continuous controls, together with a separate evaluation of human assistance. VIII. C ONCLUSION Step-pooled conformal prediction ignores within-trajectory dependence in VLN and can collapse to the argmax policy. ENCP instead calibrates one maximum normalized score per episode, providing route-level coverage of the teacher action with probability at least 1 − α under exchangeable episodes. Across R2R and REVERIE, ENCP responds as expected to α and meets the reported step-coverage targets. Learned weighting redistributes uncertainty but yields larger prediction sets, while parameter-free weighting provides a better coverage–setsize trade-off. Set size also serves as a practical help-seeking signal, with tighter budgets increasing oracle queries and improving success. For deployment, size budgets should be selected on held-out data, recalibrated under distribution shift, and validated with human operators. R EFERENCES [1] P. Anderson, Q. Wu, D. Teney, J. Bruce, M. Johnson, N. Sünderhauf, I. Reid, S. Gould, and A. van den Hengel, “Vision-and-language navigation: Interpreting visually-grounded navigation instructions in real environments,” in Proc. CVPR, 2018, pp. 3674–3683, arXiv:1711.07280. [2] Y. Zhang, Z. Ma, J. Li, Y. Qiao, Z. Wang, J. Chai, Q. Wu, M. Bansal, and P. Kordjamshidi, “Vision-and-language navigation today and tomorrow: A survey in the era of foundation models,” Trans. Mach. Learn. Res., 2024, arXiv:2407.07035. [3] S. Ross, G. Gordon, and D. Bagnell, “A reduction of imitation learning and structured prediction to no-regret online learning,” in Proc. AISTATS, vol. 15, 2011, pp. 627–635.
[4] D. Amodei, C. Olah, J. Steinhardt, P. Christiano, J. Schulman, and D. Mané, “Concrete problems in AI safety,” arXiv:1606.06565, 2016. [5] D. Hendrycks, N. Carlini, J. Schulman, and J. Steinhardt, “Unsolved problems in ML safety,” arXiv:2109.13916, 2021. [6] L. Lindemann, M. Cleaveland, G. Shim, and G. J. Pappas, “Safe planning in dynamic environments using conformal prediction,” IEEE Robot. Autom. Lett., vol. 8, no. 8, pp. 5116–5123, 2023, arXiv:2210.10254. [7] Y. Hong, Q. Wu, Y. Qi, C. Rodriguez-Opazo, and S. Gould, “VLN BERT: A recurrent vision-and-language BERT for navigation,” in Proc. CVPR, 2021, pp. 1643–1653. [8] S. Chen, P.-L. Guhur, C. Schmid, and I. Laptev, “History aware multimodal transformer for vision-and-language navigation,” in Proc. NeurIPS, 2021, pp. 5834–5847, arXiv:2110.13309. [9] S. Chen, P.-L. Guhur, M. Tapaswi, C. Schmid, and I. Laptev, “Think global, act local: Dual-scale graph transformer for vision-and-language navigation,” in Proc. CVPR, 2022, pp. 16 537–16 547, arXiv:2202.11742. [10] C.-Y. Ma, J. Lu, Z. Wu, G. AlRegib, Z. Kira, R. Socher, and C. Xiong, “Selfmonitoring navigation agent via auxiliary progress estimation,” in Proc. ICLR, 2019, arXiv:1901.03035. [11] S. S. Abraham, S. Garg, and F. Dayoub, “To ask or not to ask? detecting absence of information in vision and language navigation,” in Proc. WACV, 2025, pp. 7480–7489, arXiv:2411.05831. [12] C. Guo, G. Pleiss, Y. Sun, and K. Q. Weinberger, “On calibration of modern neural networks,” in Proc. ICML, vol. 70, 2017, pp. 1321–1330, arXiv:1706.04599. [13] Y. Ovadia, E. Fertig, J. Ren, Z. Nado, D. Sculley, S. Nowozin, J. V. Dillon, B. Lakshminarayanan, and J. Snoek, “Can you trust your model’s uncertainty? evaluating predictive uncertainty under dataset shift,” in Proc. NeurIPS, 2019, arXiv:1906.02530. [14] R. Parasuraman and V. Riley, “Humans and automation: Use, misuse, disuse, abuse,” Human Factors, vol. 39, no. 2, pp. 230–253, 1997. [15] J. D. Lee and K. A. See, “Trust in automation: Designing for appropriate reliance,” Human Factors, vol. 46, no. 1, pp. 50–80, 2004. [16] V. Vovk, A. Gammerman, and G. Shafer, Algorithmic Learning in a Random World. Springer, 2005. [17] J. Lei, M. G’Sell, A. Rinaldo, R. J. Tibshirani, and L. Wasserman, “Distributionfree predictive inference for regression,” J. Amer. Statist. Assoc., vol. 113, no. 523, pp. 1094–1111, 2018. [18] A. N. Angelopoulos and S. Bates, “Conformal prediction: A gentle introduction,” Found. Trends Mach. Learn., vol. 16, no. 4, pp. 494–591, 2023. [19] A. Z. Ren, A. Dixit, A. Bodrova, S. Singh, S. Tu, N. Brown, P. Xu, L. Takayama, F. Xia, J. Varley, Z. Xu, D. Sadigh, A. Zeng, and A. Majumdar, “Robots that ask for help: Uncertainty alignment for large language model planners,” in Proc. CoRL, vol. 229, 2023, pp. 661–682, arXiv:2307.01928. [20] K. Liang, Z. Zhang, and J. F. Fisac, “Introspective planning: Aligning robots’ uncertainty with inherent task ambiguity,” in Proc. NeurIPS, 2024, arXiv:2402.06529. [21] A. Chang, A. Dai, T. Funkhouser, M. Halber, M. Nießner, M. Savva, S. Song, A. Zeng, and Y. Zhang, “Matterport3D: Learning from RGB-D data in indoor environments,” in Proc. 3DV, 2017, pp. 667–676, arXiv:1709.06158. [22] J. Krantz, E. Wijmans, A. Majumdar, D. Batra, and S. Lee, “Beyond the nav-graph: Vision-and-language navigation in continuous environments,” in Proc. ECCV, 2020, pp. 104–120, arXiv:2004.02857. [23] Y. Qi, Q. Wu, P. Anderson, X. Wang, W. Y. Wang, C. Shen, and A. van den Hengel, “REVERIE: Remote embodied visual referring expression in real indoor environments,” in Proc. CVPR, 2020, pp. 9982–9991. [24] H. Tan, L. Yu, and M. Bansal, “Learning to navigate unseen environments: Back translation with environmental dropout,” in Proc. NAACL, 2019, pp. 2610–2621, arXiv:1904.04195. [25] Y. Gal and Z. Ghahramani, “Dropout as a bayesian approximation: Representing model uncertainty in deep learning,” in Proc. ICML, vol. 48, 2016, pp. 1050–1059, arXiv:1506.02142. [26] B. Lakshminarayanan, A. Pritzel, and C. Blundell, “Simple and scalable predictive uncertainty estimation using deep ensembles,” in Proc. NeurIPS, 2017, arXiv:1612.01474. [27] Y. Geifman and R. El-Yaniv, “Selective classification for deep neural networks,” in Proc. NeurIPS, 2017, arXiv:1705.08500. [28] S. Thrun, W. Burgard, and D. Fox, Probabilistic Robotics. MIT Press, 2005. [29] M. Sadinle, J. Lei, and L. Wasserman, “Least ambiguous set-valued classifiers with bounded error levels,” J. Amer. Statist. Assoc., vol. 114, no. 525, pp. 223– 234, 2019. [30] Y. Romano, M. Sesia, and E. J. Candès, “Classification with valid and adaptive coverage,” in Proc. NeurIPS, 2020, arXiv:2006.02544. [31] A. N. Angelopoulos, S. Bates, J. Malik, and M. I. Jordan, “Uncertainty sets for image classifiers using conformal prediction,” in Proc. ICLR, 2021, arXiv:2009.14193. [32] A. Dixit, L. Lindemann, S. X. Wei, M. Cleaveland, G. J. Pappas, and J. W. Burdick, “Adaptive conformal prediction for motion planning among dynamic agents,” in Proc. L4DC, vol. 211, 2023, pp. 300–314, arXiv:2212.00278. [33] R. F. Barber, E. J. Candès, A. Ramdas, and R. J. Tibshirani, “Conformal prediction beyond exchangeability,” Ann. Statist., vol. 51, no. 2, pp. 816–845, 2023. [34] K. Stankevičiūtė, A. M. Alaa, and M. van der Schaar, “Conformal time-series forecasting,” in Proc. NeurIPS, vol. 34, 2021, pp. 6216–6228. [35] R. J. Tibshirani, R. F. Barber, E. J. Candès, and A. Ramdas, “Conformal prediction under covariate shift,” in Proc. NeurIPS, 2019, arXiv:1904.06019.