Conformal Reasoning: Uncertainty Estimation in Interactive Environments

Thank you for your thoughtful review. We appreciate your acknowledgment of our strengths, including the well-written prose, the importance of the problem, and strong computational experiments. We address your concerns below, as well as in the revised manuscript.

1. Motivation of traditional SCP set construction.

why the traditional SCP requires the assumption that the current prediction set should belong to the intersection of previous ones.

For a given test sequence $(x^1, \dots, x^t)$ through time $t$, Ren et al. (2024) aim to use split conformal prediction to construct a conformal set that uses the information in the entire sequence of a scenario, $(x^0, \dots, x^T)$, to determine the non-conformity score of the test scenario. To do so, they define a score corresponding to a single timestep as $s_y^t(x^t)$; this is similar to a typical non-conformity score used in single-timestep conformal prediction. Subsequently, they define the non-conformity score of the entire sequence $(x^1, \dots, x^T)$ as the maximum non-conformity score across all timesteps in the sequence, or $s_y(x^1, \dots, x^T) = \max_{1\leq t \leq T} s_y^t(x^t).$ In other words, this is a worst-case bound on the non-conformity score of the test scenario. As a result, they create a sequence-level prediction set that attains $1-\alpha$ marginal coverage across the dataset by using the quantile of these worst-case non-conformity scores $\hat{q}\_{\alpha}$. However, this score is technically defined as a function of the entire sequence; at test time, however, the agent only has access to the sequence up to the current timestep. To render this score applicable at test time, using the previously defined quantile $\hat{q}_{\alpha}$, the prediction set at time $t$ is given by

$C_t(x^t) = \lbrace y \in \mathcal{Y} : s_y(x^1, \dots, x^t) \leq \hat{q}_{\alpha}\rbrace.$

In turn, they demonstrate that for all time $t\in [T]$ the sequence-level prediction set will be contained in $C_t(x^t)$, and in fact that the sequence-level prediction set can be written as the intersection of the prediction sets at each timestep, or $C(x^1, \dots, x^T) = \bigcap_{t=1}^T C_t(x^t).$ Accordingly, this worst-case construction helps ensure that the sequence-level prediction set---which with high probability contains the true label $y$---will be a subset of the prediction set at any single timestep. However, for the reasons we articulate below (Point 4), this worst-case construction may be too conservative. Additionally, we provide empirical results that SCP with other set construction methods fail in Figure 2 of the paper. We will take care to clarify this point in the revised manuscript.

2. Calculation of Coverage

It's unclear to me how the coverage metric was calculated. Specifically, did you calculate the coverage for every time step or only do this at the final step?

Our coverage metric is calculated as follows: for each test point, we write that the point has been covered by the prediction set if the final step prediction set contains the true label. More formally, $\text{Coverage} = \frac{1}{n} \sum_{i=1}^n \boldsymbol{1}[y_i \in C_T(x_i^T)]$, where $T$ is the final prediction step. We will make this explicit in the revised manuscript.

3. Domain shift.

One of the motivations for applying ACP is to deal with domain shifts. However, this is not tested in the computational experiments.

While ACI was initially introduced for the explicit purpose of adapting to distribution shifts, we note that in subsequent work, adaptive conformal-style approaches have also been characterized for online i.i.d. data. However, in practice, much of the data collected for interactive tasks is non-i.i.d., even when the agent's policy is stationary (or fixed a priori). In particular, implicit heuristics in how calibration data is collected in interactive settings---for example, the maximum sequence length, the agent's stopping threshold---can lead to non-i.i.d. data and accordingly non-exchangeable non-conformity scores, much less data coming different distributions (e.g. heterogeneous types of medical questions or household navigation scenarios). Part of the intuition in our approach is to correct for non-i.i.d data by leveraging the ability to adapt $\alpha_t$ over the potentially heterogeneous calibration set. Accordingly, even though the data used for calibration is non-i.i.d., adaptive conformal methods can still empirically provide coverage guarantees, even when we keep the learned $\alpha$ fixed when deploying at test time. We make this underlying motivation more explicit in the revised manuscript.

4. Refresh prediction and answer rate.

The general intuition around refresh prediction is that it acts as a flexible method for constructing prediction sets that are more responsive to the test sequence. For example, consider the following scenario:

In the EQA task, an autonomous agent is tasked with answering a question about its environment with four possible answers; WLOG, assume the correct answer is $y_1$.

If the intersection-based method for constructing prediction sets is used, at an early timestep, the agent may produce a prediction set that does not contain the correct answer, e.g., $\{y_2, y_3, y_4\}$. However, after further interaction with the environment, even if the agent's prediction set at a later timestep is exclusively the correct label $\{y_1\}$, the final prediction set will not contain $y_1$, since the conformal set at time $t$ is defined as $C(x^t)=\cap_{i=1}^t C_i(x^i)$ at test time. In contrast, refresh prediction considers only the prediction set at each timestep; accordingly, the agent can "rediscover" the correct answer $y_1$ at later timesteps by "refreshing" its prediction set.

Moreover, using the intersection-based method for constructing prediction sets defines its non-conformity score as the maximum (worst-case) non-conformity score across all timesteps, which may be too conservative. In contrast, refresh prediction's non-conformity score is the non-conformity score at the final timestep in the sequence, whether the result of encountering the maximum sequence length or by choosing a specific label. As a result, refresh prediction tends to be less conservative than the intersection-based method, particularly when the agent encounters information that is indicative of the correct label.

5. Efficiency / metric benchmarks.

It is unclear what the baselines are when the authors claim that conformal reasoning improves efficiency.

In our experiments, we compare our approach against split conformal prediction (SCP); additionally, when ablating different components of our approach (e.g. RP), we similarly compare against SCP with RP. Moreover, each of our metrics mentioned in our manuscript is applicable to any prediction set-based method used in our interactive problem settings.

Thank you for your helpful response. We aim to answer your questions in the comments below in addition to the revised manuscript.

Logic behind Section 4.1 is not clear

We welcome your question on the intuition around Section 4.1, and we agree that the discussion could be more clear. Here, we hope to characterize the expected behavior of $\alpha_t$ over the course of the interaction. In the i.i.d. setting, we expect $\alpha_t$ to converge as the agent interacts with the environment. While our setting retains that same assumption---that is, that the scenarios sampled are i.i.d. from the distribution over our scenarios---the trajectories created under an agent's exploratory policy can appear to be heterogenous. More concretely, although scenarios $\xi$ and $\xi'$ are sampled from the same distribution, the trajectories $\bar x_\xi = (x^0,\dots, x^T)$ and $\bar x_\xi' = (x'^0,\dots, x'^T)$ may be quite different because of the randomness in the agent's policy and differences in the scenario, such as the target question. An analogous way of viewing this is with respect to time series: while two time series $\{X_t\}$ and $\{X_t'\}$ may be sampled from the same distribution, their trajectories may have significant differences. As a result, using offline adaptation can better address this heterogeneity in the trajectories.

Theorem 1 is a result from the existing works where the setting is different from the proposed multi-turn task. It is encouraged to derive the analysis of the algorithm for the setting proposed in this work.

We argue that the setting used in Theorem 1---that of an online setting---is nonetheless a natural setting to characterize, even for our approach. In Angelopoulos et al. (2024), the authors prove a general result across arbitrary distributions of covariate label pairs that arrive in an online fashion. In our setting, we treat our covariates as the sequences of states of an agent interacting with its environment, with the corresponding label as the ground truth answer desired by the agent. Because of this construction, we can nonetheless apply the same results from adaptive conformal inference to our setting. We clarify this point in the revised manuscript.

Moreover, even in the non-i.i.d. setting, we reference the result from Gibbs and Candes (2021) that characterizes finite-sample convergence of the adaptive procedure under Markovian data; accordingly, even in settings where the data distribution explicitly changes relative to the standard stochastic setting, we can still characterize reasonable convergence results of $\alpha_t$. Proving similar results for other notions of data dynamics is an interesting direction for future work.

discuss the pareto frontier of the trade-off between these two factors

We appreciate your question on the tradeoffs between specificity and efficiency, particularly in the context of refresh prediction, and agree with the need to clarify this point in the revised manuscript. By construction, refresh prediction will have less specificity than the intersection-based method, as it only uses the prediction set at the final timestep; in contrast, the intersection-based method can only produce successively smaller prediction sets at each time step. However, because the score function of the intersection-based method is defined as the maximum non-conformity score across all timesteps, it is generally much more conservative relative to the prediction sets produced by refresh prediction.

To further clarify this point, we plot the Pareto frontier of the intersection-based method and refresh prediction in the revised manuscript across various choices of $\alpha$. These results are available in Appendix C. In fact, across different levels of target coverage, refresh prediction tends to improve the Pareto frontier relative OA alone.

We appreciate your review and hope to clarify your concerns in the comments below and in our revised manuscript.

Major weakness is limited novelty in the methods

While we agree that adaptive conformal inference is not new, to our knowledge, its application as a method for selecting $\hat q$ on data collected offline is novel, both in standard settings for conformal prediction as well as in interactive settings.

• Indeed, we are not aware of other work that applies adaptive conformal inference on a calibration set to learn a reasonable $\alpha_t$ for the agent to use at test time; in turn, this helps eliminate some of the dependencies seen similar work in interactive settings that overly rely on human-in-the-loop feedback, such as [1]. Additionally, the use of adaptive conformal inference to learn $\alpha_t$ enables our approach to overcome the presence of non-i.i.d. data in the calibration set in interactive reasoning tasks. We emphasize this point more clearly in the revised manuscript.

• Second, while we agree that refresh prediction is not in itself novel --- indeed, it is one particular formulation for the score function --- its application is only enabled by using online conformal prediction techniques for offline calibration. Moreover, empirically, its application in interactive settings enables stronger performance in a number of metrics relative to the intersection-based method while maintaining the same coverage guarantees.

• As mentioned in the overall response and reflected in the revised manuscript, we also introduce Guided Reasoning, which enables the use of the conformal prediction set within the agent's exploration process, as well as a third benchmark, Twenty Questions, to further demonstrate the benefits of our approach. In particular, we demonstrate that our approach enables the use of the conformal prediction set within the agent's policy, which to our knowledge has not been done in similar work. Moreover, the superior performance of Guided Reasoning relative to split conformal prediction emphasizes the utility and novelty of our approach.

• Finally, we introduce several metrics beyond coverage and set size that help characterize the usefulness of our approach; in particular, these metrics (% answered, efficiency) are unique to interactive settings instead of single-turn settings typical of conformal prediction. These metrics more broadly are useful for evaluating the success of different types of conformal algorithms in interactive settings.

ACI framework is a bit outdated now in the literature

We agree that ACI is relatively outdated given recent work (especially those cited by the reviewer). However, in our work, we sought to use ACI as a simple, understandable, and easy-to-implement demonstration of our approach's benefits. Due to the nature in which our approach "consumes" the ACI method, other adaptive and online learning methods can easily be swapped in. Indeed, as a testament to this fact, we provide additional results using the adaptive frameworks from Zhang et al. (2024) and Bastani et al. (2022) in Appendix C of our revised manuscript on the EQA task. Despite the differences in these methods---for instance, minimizing different notions in regret, or striving for multicalibration---these methods are similarly effective in our problem setting. An interesting question for future work is characterizing the relationship between different types of online convex optimization approaches and their effectiveness in learning $\alpha$ from offline data; this question inherently is tied to online algorithms that can achieve "best of both worlds" guarantees on stochastic and adversarial data.

If the performance of the algorithm is very sensitive to the hyperparameters, then it is unclear if the proposed method is actually better than baselines in a statistical sense

To further clarify the importance of the step size decay hyperparameter, we demonstrate the performance of our proposed approach against the step size decay hyperparameter in the revised manuscript. First, different choices of step sizes yielded similar terminal values of $\alpha_t$, indicating that our problem setting is robust given reasonably selected step sizes. Second, ablating the rate of decay for our learning rate similarly suggests flexibility in choosing the decay; nonetheless, selecting decay rates that are too small or too large suffer the equivalent variability of ACI or static nature of traditional offline conformal methods. Finally, the success of different types of online conformal prediction methods, which in general are more robust to the hyperparameters that induce variability in ACI, similarly accentuates the robustnesss of our approach.

[1] Ren AZ, Dixit A, Bodrova A, Singh S, Tu S, Brown N, Xu P, Takayama L, Xia F, Varley J, Xu Z. Robots that ask for help: Uncertainty alignment for large language model planners. arXiv preprint arXiv:2307.01928. 2023 Jul 4.

Literature Review on Feedback Loops and Decision-Making

We expanded our literature review on methods for conformal prediction under feedback loops and decision-making. In particular:

• We now incorporate a broader review of conformal prediction techniques applied to interactive tasks, including recent works on feedback shifts and trajectory-specific methods.
• We additionally characterize the broader literature of online conformal approaches and our relationship to their empirical and theoretical characterizations.
• We emphasize how our approach builds upon these foundational methods to address unique challenges in dynamic, multi-turn environments.

These additions, included in Section 2, highlight the broader significance of our work and its relationship to the state of the art.

Other Minor Suggestions and Typographical Errors

We appreciate your detailed feedback on smaller issues and have incorporated your suggestions:

• Updated “minimal prediction sets” to “minimal size prediction sets.”

• In Figure 1, the termination criteria demonstrated is the traditional criteria without refresh prediction -- this means that if an option has ever been eliminated in a previous turn (e.g. A was below the red line in turn 1), then it cannot be "recovered" even if its probability exceeds the threshold in a future turn. This is also one of our motivations to propose the Refresh Prediction technique to allow for more fault-tolerant set prediction. We have updated the caption to clarify this point.

• Addressed the inconsistency in how $\bar{x_i}$ appears in the score function definition, as it was indeed a typo.

• Provided a brief justification for calling our method “Conformal Reasoning,” emphasizing its novel combination of prediction set construction and interactive decision-making.

We have significantly revised the manuscript to address the issues you raised, including clarifying theoretical limitations, improving mathematical formalism, expanding the literature review, and correcting typographical errors. Furthermore, we have clarified the distinctions between our work and alternative approaches (e.g., hypothesis testing methods), highlighting the practical benefits of our approach in real-world scenarios.

We kindly request you to consider these improvements when reassessing your evaluation of the manuscript. Your feedback is extremely invaluable, and we thank you again for helping us refine and improve this work.

Thank you for your thoughtful and detailed review. We greatly appreciate your recognition of the clarity and importance of our problem setting and your constructive comments on the theoretical and methodological aspects of the paper. Below, we address each of your points carefully and outline the changes made to the manuscript in response to your feedback. We hope that these revisions address your concerns and encourage you to raise your score for our work.

Theoretical Limitations of Termination at $\left| C\right| = 1$

We fully agree with your observation that the marginal coverage guarantee does not apply when the prediction set size is exactly 1. As you noted, this is indeed a limitation of our approach as well as of related prior works (e.g., Ren et al.). In the revised manuscript, we explicitly clarify that our approach does not seek to achieve conditional coverage for such cases. Instead, we emphasize that our goal is to guarantee marginal coverage over the prediction set at termination.

Key points addressed in the revision:

• We provide additional discussion in Section 5 to highlight that our empirical results demonstrate strong marginal coverage even when $\left|C\right|$ = 1.

• We contrast our approach with the hypothesis testing-based methods you suggested (e.g., Conformal Alignment), which have distinct objectives and naively do not produce actionable prediction sets at termination time. By allowing predictions to terminate at $|C| = 1$, we offer a more practical approach that enables higher efficiency (albeit, with no guarantees on the "correctness" of the prediction) than continuing to the maximum sequence length as well as retaining the utility of outputting a prediction set.

Conformal prediction methods have been developed for abstention

The two hypothesis testing-style approaches mentioned in the review are an interesting alternative to our approach, and we agree that this is an interesting direction for future work. However, a notable limitation of these hypothesis testing approaches is that naively controlling the selective classification error does not yield a meaningful prediction set. In particular, in both Learn-then-Test and Conformal Alignment, the authors compute conformal $p$-values for each test point and use these $p$-values to determine whether the model's prediction should be used and elicited or abstained from. Accordingly, a hypothesis testing approach to our set of interactive tasks would not lead to prediction sets, but it is interesting to make the connection in future work. In contrast, a prediction set-based method like ours offers a terminal prediction set that can be used to aid a human practitioner that may be more useful in practice.

Our approach, to a limited extent, interpolates between these two approaches. In particular, for Ren et al. (2024) to achieve a correct $1-\alpha$ coverage guarantee, their construction requires them to terminate at the maximum allowed timestep for their specific scenario; while not achieving conditional coverage, this algorithmic approach would provide a marginal guarantee, at the expense of the efficiency at test time. In contrast, the aformentioned risk control approaches ensure that terminating at a prediction set of size one would provide a valid conditional coverage guarantee, but at the cost (in a naive implementation) of not offering any terminal prediction set that might aid a human practitioner. Here, we empirically demonstrate that we do in fact retain marginal coverage for the final prediction set at termination time, whether that be because of the prediction set size or the maximum sequence length. Moreover, our approach offers a more efficient alternative to the approach of Ren et al. that goes to the maximum sequence length, as we enable the agent to terminate at a prediction set of size one when appropriate. Finally, should the agent not be able to terminate at a prediction set of size one, our approach still offers a terminal prediction set that can be used to aid a human practitioner.

We appreciate the feedback and have added the above discussion to the end of Section 2 of the revised paper.

The mathematical details of the paper are unclear, largely due to many typos. It is also overly formal in some sections, while being under-developed in critical parts.

We appreciate your detailed feedback on mathematical clarity and the noted typographical errors. In the revised manuscript, we have simplified and clarified the mathematical descriptions, particularly in Section 4, to reduce unnecessary formality while maintaining rigor, and we have corrected all identified typos.

Firstly, the typo in the norm vs set cardinality remains.

So sorry -- we were initially confused when you mentioned the issue with using the norm vs. set cardinality and looked for it in the text; it didn't occur to us that the issue was in the figure. We have fixed that in the current revision.

Secondly, I am confused as to what the role of the termination criterion is. My main worry is that, if your goal is to take some action (with guarantees) on the event that the cardinality is 1, those guarantees would be invalidated by the loss of conditional coverage, as we discussed.

Regarding conditional guarantees and the termination criteria, we hope to clarify that our goal is to not to ensure conditional coverage if $|C|=1$; rather, we aim to provide marginal coverage across our entire algorithmic process. Our termination criteria is empirically motivated: we would ideally like to end exploration as long as the model is reasonably confident in the correct answer. In particular, for a given scenario and trajectory $(x_\xi^0,\dots, x_\xi^{t})$, where $t=\min(T, t_{ans})$, we hope to provide achieve coverage

Accordingly, our guarantee is marginal over our entire collection of trajectory termination times $t_\xi$. Additionally, we emphasize that the algorithmic approach used for learn $\alpha_t$ is exactly that used at test time; that is, they have the same termination criterion.

Moreover, consider the coverage guarantee from Ren et al. if done correctly, that is, if they let each test sequence run to maximum scenario length. Their failure to achieve a coverage guarantee comes from the fact that if they continued beyond the timestep at which they get |C|=1, their conformal set could be entirely empty, which would not cover the true labely $y$. As a result, the SCP approach from Ren et al. overcovers relative to the actual target coverage level. Alternatively, in our approach, by explicitly adapting $\alpha_t$ to whether coverage was attained -- that is, if we overcover at that time step, we will make $\alpha_{t+1}$ larger and the quantile "less restrictive" -- we are able to better mitigate the overcoverage phenomenon present in SCP.