Conformal Reasoning: Uncertainty Estimation in Interactive Environments

Authors: Eric Frankel, Shuyue Stella Li, Lillian J. Ratliff, Yulia Tsvetkov, Sewoong Oh, Pang Wei Koh
Primary area: foundation or frontier models, including LLMs
Keywords: Conformal Prediction, Uncertainty Quantification, LM Abstention, Interactive Reasoning

Abstract:
We introduce conformal reasoning, a principled method for models in interactive environments to reason about their uncertainty and decide whether to seek out more information or to return a prediction. The challenge with standard conformal prediction---a popular statistical framework for uncertainty estimation that constructs prediction sets with formal coverage guarantees---is that it relies on a fixed set of calibration data points. In interactive environments, however, the calibration trajectories require certain termination criteria determined a priori, introducing heuristic bias and/or circular dependency that break the assumptions needed for coverage guarantees. We address this issue by building on adaptive conformal inference techniques. On two real-world tasks on medical diagnosis and embodied question answering, we show that conformal reasoning empirically achieves its theoretical coverage guarantees---in contrast with standard conformal prediction approaches that can significantly over- or under-cover---while improving exploration efficiency by approximately 20% on both tasks.

Decision: reject
Reviewer scores: 3, 5, 5, 6

Reviews and discussion:
<thread>
creation date:
1730230833357

thread_type:
official_review

<thread_object>
creator: reviewer_wksu

<content>
summary:
This paper studies conformal prediction in a multi-turn setting, where an agent interacts with a user repeatedly, adjusting its predictions at each turn. The authors first identify two major limitations in traditional split conformal prediction (SCP): (1) SCP requires the prediction set at time $t$ to be the intersection of all previous sets, which can be overly restrictive, and (2) SCP calibrates a quantile using offline data specific to a certain policy and cutoff parameter, which may not generalize well out-of-sample due to distributional shifts. To address these challenges, the authors employ adaptive conformal prediction (ACP), which dynamically adjusts the quantile value as the environment changes and relaxes the restrictive assumptions in (1). The main contribution of this paper is the application of ACP in this multi-turn context, where it demonstrates better empirical performance over SCP in the authors' experiments.

strengths:
- Overall, the paper is well-written. The concepts and split and adaptive conformal prediction are clearly explained.

- Conformal prediction in this multi-turn setting is an important problem that has application in many settings (especially those that involves LLM).
    
- Computational experiments demonstrate favorable performance of the proposed method.

weaknesses:
- **Motivation.** I am not sure if I fully understand why the traditional SCP requires the assumption that the current prediction set should belong to the intersection of previous ones. This seems to be a design choice that can be avoided. I suggest the authors providing more contexts regarding why this is necessary to better motivate the application of ACP. 

- **Experiments.** For an applied paper like this, I suggest the authors consider the following points to strengthen their empirical contributions.

  - **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?
  - **Domain shift.** One of the motivations for applying ACP is to deal with domain shifts. However, this is not tested in the computational experiments.
  - **RP.** It is unclear to me why RP helps to improve \% answered, although the experiment results said so. It would be helpful if the authors could provide high-level intuition on the reason. 
  - **Efficiency.** It is unclear what the baselines are when the authors claim that conformal reasoning improves efficiency.

questions:
By breaking the connection between prediction sets constructed at consecutive steps, ACP and RP enhance flexibility in generating prediction sets. However, this approach might compromise interpretability. It would be interesting to know if the authors have considered this trade-off and have any insights on it. Additionally, it could be valuable to explore potential approaches that lie between these two extremes.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730467378095

thread_type:
official_review

<thread_object>
creator: reviewer_8aew

<content>
summary:
This paper considers the conformal reasoning problem in a multi-turn environment. The authors introduce the conformal reasoning problem and focus on the confidence set construction for this problem. They propose the adaptive conformal inference and refresh prediction as two main components. The efficacy of the proposed algorithm is verified via experimental results.

strengths:
1.	The paper introduces the problem formulate and the algorithm clearly.
2.	The authors provide theoretical analysis of the proposed method in Theorem 1.

weaknesses:
1.	The logic behind Section 4.1 is not clear. The authors claim that ``While much of the traditional conformal prediction literature assumes i.i.d. (or exchangeable) sampled data or a calibration set collected offline’’. However, the authors adopt the i.i.d. assumption in Theorem 1. If the non-stationary factors can be absorbed in $s_t$, then the convergence of $s_t$ to $s$ will be an unrealistic assumption in the setting considered by this work.
2.	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.
3.	Table 2 indicates that refresh prediction indeed sacrifices the specificity for the improvement of efficiency. It is beneficial to simulate and discuss the pareto frontier of the trade-off between these two factors.

questions:
Same as the weakness
</content>
</thread_object>

</thread>
<thread>
creation date:
1730562407561

thread_type:
official_review

<thread_object>
creator: reviewer_szhf

<content>
summary:
This paper presents conformal reasoning, a method to reason about uncertainty in interactive environments. 

Conformal reasoning builds upon two key techniques: (1) adaptive conformal inference that performs online uncertainty set prediction in the presence of distribution shifts, and (2) refresh prediction that design a new score function.

Experiments on medical information seeking and embodied question answering show the proposed method is better than existing baselines.

strengths:
- Well motivated problem of reasoning about uncertainty in interactive environments
- Good empirical performance
- Paper and method are well presented and easy to understand

weaknesses:
- Major weakness is limited novelty in the methods. The adaptive conformal inference is a straightforward application of the previous work, and the refresh prediction, as presented in the paper, is merely a new score function. So in this perspective the methodological contribution is quite limited.

- The ACI framework is a bit outdated now in the literature of online conformal prediction (with distribution shifts). In addition, several issues are known about ACI, including the requirement of parameter tuning in the algorithm. There are several recent algorithms that are theoretically more sound than ACI, such as:
  - Bastani, Osbert, Varun Gupta, Christopher Jung, Georgy Noarov, Ramya Ramalingam, and Aaron Roth. "Practical adversarial multivalid conformal prediction." Advances in Neural Information Processing Systems 35 (2022): 29362-29373.
  - Bhatnagar, Aadyot, Huan Wang, Caiming Xiong, and Yu Bai. "Improved online conformal prediction via strongly adaptive online learning." In International Conference on Machine Learning, pp. 2337-2363. PMLR, 2023.
  - Zhang, Zhiyu, David Bombara, and Heng Yang. "Discounted Adaptive Online Learning: Towards Better Regularization." In Forty-first International Conference on Machine Learning.
and the references therein.

- In the limitations section, the paper mentioned 

> convergence and stability of Conformal Reasoning is dependent on the choice of learning rate in adapting $\alpha_t$, requiring some hyperparameter tuning for the best performance

However, there are no ablation studies on the sensitivity of hyperparameter tuning. 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.

- It should be noted that the coverage guarantee is "asymptotic", and we do not when the coverage guarantee starts to hold, when using conformal prediction in the presence of distribution shifts.

questions:
Ablation studies are needed to study the sensitivity of hyperparameters on the performance of the algorithm.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730709089471

thread_type:
official_review

<thread_object>
creator: reviewer_1c1u

<content>
summary:
The paper introduces a method called conformal reasoning. It extends the algorithm of Ren et al. to an online, multi-turn setting, and makes the set construction more flexible (no more running intersection needed) by applying theory from adaptive conformal prediction. Experiments are shown on medical diagnosis and question answering datasets.

strengths:
* The english prose is written relatively well, and it was easy to follow. 
* I believe this problem setting is interesting and important to solve.
* Lifting the restriction of needing to take the running set intersection makes the algorithm of Ren et al. more practical.

weaknesses:
(1)
There are fundamental and serious issues with the idea of terminating when |C| = 1, as proposed in Figure 1. To be fair, these problems appear not just in this paper, but in the prior work of Ren et al. as well.   The issue is this: marginal coverage does _not_ guarantee coverage when |C|=1. The latter is a form of conditional coverage. Thus, on the termination event in Figure 1, the coverage guarantee provided by conformal prediction does _not_hold. That is, precisely on the event that the reasoning is deemed reliable (|C|=1), we cannot provide a reliability guarantee. (Formally, $\mathbb{P}(y \in C(x) \mid \|C(x)\| = 1)$ has no guarantee.)

Conformal prediction methods have been developed for abstention, such as the conformal alignment algorithm of https://arxiv.org/abs/2405.10301, or the conformal selective classification subroutine of https://arxiv.org/abs/2110.01052. Such procedures _are_ able to guarantee $\mathbb{P}(y \in C(x) \mid \|C(x)\| = 1) \geq 1-\alpha$.

(2)
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.

The biggest issue is on page 7, where the score function is defined. We see $s(\bar x, y) = s(x_i^{min(t_{ans},T)},y)$. But $t_{ans}$ is unknown at $t=1$; so how can we expect to construct the prediction set at time $t=1$? That is: we can obviously define any score function we would like, as a function of the whole trajectory. The harder part, at least in this multi-turn setup, is inverting the test to get a sensible prediction set. Therefore, the form of the set should be written out, as it is for the baseline at the bottom of page 5.

There are also a number of typos in the math throughout. My general suggestion would be to cut down on the amount of notation and formalism as much as possible, to reduce to the minimal amount needed to convey the ideas.

Math typos:
* Bottom of page 5, definition of sets: $C^{\tau}$ does not seem to depend on $\tau$ except through $x^{\tau}$, which calls into question why it should have the second superscript.
* in the definition of SCP on page 5, the quantile function has been defined over measures, but it takes an empirical PDF as an argument earlier (these objects are of a different type)
* the conformal quantile isn’t the 1-alpha empirical quantile, it is the$ (1-\alpha)(1+1/n)$ empirical quantile due to the delta mass placed at infinity
* The correct notation for a set cardinality is not $\| \mathcal{C} \|$, but $|\mathcal{C}|$ (the former is normally reserved for a norm)

(3)
The paper could also use a more comprehensive literature review around methods for conformal prediction under feedback loops, for agents, and for decisions. There are many such papers. 

_______

Other typos, errors, and minor suggestions:

$\|y - f(x)\|$ is not bounded. (Conformal scores do not generally need to be bounded or non-negative.)

“originally designed to handle external distribution shifts in dynamic environments” not really. It was designed to handle arbitrary distribution shifts of any kind.

Figure 1: right-side of the right-most panel, I think that there is an error. The algorithm shouldn’t yet terminate because both A and B cross the red line, so the prediction set should be {A, B}. Maybe the bar for A should be lower.

“minimal prediction sets” -> “minimal size prediction sets”

“We emphasize that Theorem 1 holds for arbitrary score function” typo

“The main challenge of the task is for the Expert system to ask
information-seeking questions to expand Kt until the the Expert system is sufficiently” typo in Appendix A.

On pg. 7, why does $x_i$ appear in the definition of $s(\bar x, y)$? This must be a typo, given the way $\bar x$ is defined on pg 5 in terms of $x^i$.

Not sure why this is called conformal reasoning. Name does not reflect the nature of the method, which can be applied to any trajectories, and does not really include reasoning as a subroutine.

questions:
Main question: how is the set constructed when inverting the score on pg. 7?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732482499419

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Summary Rebuttal

comment:
We appreciate the reviewers' thoughtful questions regarding our submission.
We're grateful that many of the reviewers agreed with the significance and motivation of our problem setting, our strong empirical performance, and the overall practicality of our method.
Here, we highlight important changes in our revision, as well as address common questions that arose in the review process. Reviewer-specific questions will be addressed individually.

**Important Updates (highlighted in blue text in the revised paper)**

1. **Naming**: We realized that the confusion brought up by some of the reviewers regarding novelty is due to the overloading of the term "adaptive conformal inference (ACI)." Although our method builds upon techniques from online conformal prediction like ACI, it is fundamentally different as it *learns* the conformal threshold *offline*. This differs from ACI by eliminating the need for sequential feedback, i.e. receiving $Y_{t-1}$ before $X_t$, and making it possible for real-world deployment in settings where a ground-truth label is not readily available (e.g. medical diagnosis).  Therefore, we rename the component of our proposed method **"offline adaptation"**, which adapts high-level intuition from ACI to account for distribution shift. Moreover, our approach is compatible with more general types of online conformal methods; however, we largely appeal to ACI for its theoretical characterization in both adversarial and stochastic settings.

    - Additionally,we agree with some reviewers that Refresh Prediction can be viewed as an alternative score function, but it is only enabled through the use of offline adaptation; in particular, it accentuates that the proposed adaptive offline method is robust to flexible score functions and set constructions in contrast to standard split conformal methods. 

2. **Guided Reasoning**: 
To demonstrate the theoretical flexibility of our offline adaptation approach, we show that it is robust to both 1) novel score functions and 2) temporally dependent reasoning paths by proposing Refresh Prediction and Guided Reasoning, respectively. 
We add Guided Reasoning to our revision to show that the robustness of offline adaptation is not limited to switching score functions but rather a more fundamentally wide set of modifications. 
In contrast, SCP does not enable either Refresh Prediction because of the restrictiveness in its construction, nor can it leverage Guided Reasoning because using the prediction set in the subsequent reasoning path would break the independent assumption. 

3. **20 Questions**: We have strong empirical evidence that the proposed method improves model performance on critical, high-stakes tasks such as clinical reasoning and embodied question answering. In order to strengthen our results in response to some of the reviewers' concerns regarding performance and trade-offs between specificity and efficiency, we have added the 20 Questions task to demonstrate the effectiveness of Conformal Reasoning (and in particular, Guided Reasoning), especially in settings where the size of the label set is large.
Moreover, our results indicate that the tradeoff between efficiency and specificity is task-dependent.
We explore these results further in Section 7 of the revision.

Below are our results on the Twenty Questions task, and we also show that GR significantly improves accuracy in Figure 3 of the revised paper.

| Target Coverage | Refresh Prediction | Guided Reasoning | Empirical Coverage | \% Answered ↑ | Specificity (\%) ↑ | Efficiency (\%) ↑ |
|--|--|--|--|--|--|--|
| 0.9 | ✗ | ✗ | 90.5 ± 1.1 | 0.1 ± 0.2 | 52.6 ± 1.4 | 4.0 ± 0.4 |
|  | ✓ | ✗ | 88.4 ± 2.0 | 5.7 ± 1.4 | **67.6** ± 1.4 | 7.9 ± 0.8 |
|  | ✗ | ✓ | 92.3 ± 1.9 | 2.5 ± 1.6 | 59.3 ± 2.9 | 6.5 ± 0.8 |
|  | ✓ | ✓ | 92.0 ± 2.0 | **8.1** ± 1.6 | 63.4 ± 4.5 | **10.2** ± 1.5 |
| 0.8 | ✗ | ✗ | 83.2 ± 3.1 | 0.5 ± 0.4 | 62.4 ± 2.1 | 4.6 ± 0.5 |
|  | ✓ | ✗ | 82.7 ± 4.6 | 10.8 ± 2.1 | 77.5 ± 2.5 | 8.9 ± 1.1 |
|  | ✗ | ✓ | 82.9 ± 2.0 | 3.8 ± 1.0 | 68.7 ± 1.0 | 7.3 ± 0.6 |
|  | ✓ | ✓ | 79.2 ± 3.9 | **16.0** ± 3.3 | **79.5** ± 3.5 | **12.4** ± 0.5 |
| 0.5 | ✗ | ✗ | 53.4 ± 3.8 | 2.5 ± 0.5 | 79.5 ± 0.4 | 4.8 ± 0.5 |
|  | ✓ | ✗ | 52.5 ± 3.6 | 38.9 ± 4.5 | 93.7 ± 2.0 | **14.3** ± 1.2 |
|  | ✗ | ✓ | 54.5 ± 3.4 | 15.2 ± 3.0 | 86.0 ± 0.4 | 7.6 ± 1.0 |
|  | ✓ | ✓ | 50.3 ± 5.0 | **43.0** ± 2.8 | **94.0** ± 0.7 | 13.2 ± 1.0 |
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper 'Conformal Reasoning: Uncertainty Estimation in Interactive Environments' was reviewed by 4 reviewers who gave it an average score of 4.75 (final scores: 3+5+5+6). The reviewers found the ideas rather well presented in the paper, the analysis insightful, and the experiments interesting. On the other hand, the novelty was seen as limited, the experiments should have covered more setups and ablations, and some parts of the paper were confusing. Overall, the reviewers see that the paper does not quite meet the bar for acceptance in its current form.