Accelerating Feature Conformal Prediction via Taylor Approximation

Thanks to the reviewer for the thoughtful comments. We will provide a detailed explanation.

Questions:

1.the paper is hardly accessible to those who are not familiar with FCP.

We thank the reviewer for the correction and clarification of the concepts presented in our paper. Since FFCP is a variant of FCP, the current presentation may pose difficulties for readers unfamiliar with FCP. We will revise the relevant descriptions in future versions to improve clarity and minimize potential confusion.

2.the denomination of "vanilla CP" is extremely confusing. The original CP is called transductive or ("full") CP, and if any CP method should be referred to as vanilla it should be that one. The authors compare against split (or "inductive") CP, and that's what the method should be called.

We sincerely apologize for the confusion caused in the reading. In future revisions, we will replace "Vanilla CP" with the more accurate term "split CP."

3.Algorithm 1 is a special case of split CP, it is not exactly split CP (despite the description). In general, split CP is defined for an arbitrary nonconformity measure, which takes as input a bag of examples + a new example, and outputs a real number.

We agree that Algorithm 1 essentially corresponds to the canonical form of split conformal prediction.

According to the original definition of split CP, it would strongly seem that FCP is a special case of split CP, in that it uses a specific form of nonconformity measure. Can you clarify?

Indeed, from the perspective of Full CP and split CP, FCP can be regarded as a special case of split conformal prediction, as it also partitions the dataset into a training set and a calibration set. The main innovation of FCP lies in how the non-conformity scores are computed during the calibration phase. In classical split CP, the non-conformity score is computed directly as $s = |Y - f(X)|$, and the prediction interval is constructed based on the quantile of these scores. In contrast, FCP similarly trains a model on the training set, but during calibration, it computes the non-conformity scores using Algorithm 2 presented in the paper. Specifically, it searches for an optimal feature representation that leads to a prediction close to the true label, and defines the score as $s_f = |v - h(X)|$. Then, the quantile $Q_{1-\alpha}$ of these scores is computed, which determines the conformal band radius. FCP further employs Band Estimation(incorporate techniques such as LiRPA) to estimate the output band length, and Band Detection (also using Algorithm 2) to evaluate coverage. Therefore, in essence, FCP is a variant of split CP, with the key distinction that it leverages information from the feature space in the computation of non-conformity scores.

The derivation between eq 5 and 6 should have been spelled out.

Thanks for reviewer's question. We provide a detailed approximation procedure below:

In FCP, the non-conformity score is originally defined as:

$$\inf\_{v \in \{v : g(v) = Y\}} ||v - h(X)||.$$

However, this is difficult to compute in practice. Therefore, FCP uses its Algorithm 2 to obtain a good approximation of the feature vector $v$, and then defines the score as:

$$\text{score} = ||v - h(X)||.$$

In Algorithm 2, the optimization objective is:

$$\min_v \|g(v) - Y\|^2.$$

We observe that directly optimizing over $v$ can be computationally complex. To simplify this, we consider a first-order Taylor expansion of $g(v)$ around $\hat{v} = h(X)$:

$$g(v) \approx g(\hat{v}) + \nabla g(\hat{v})(v - \hat{v}).$$

This implies:

$$g(v) - g(\hat{v}) \approx \nabla g(\hat{v})(v - \hat{v}),$$

and since we are reusing the FCP score form, we obtain:

$$||v - \hat{v}|| \approx \frac{|g(v) - g(\hat{v})|}{||\nabla g(\hat{v})||}.$$

This gives an approximate closed-form for the non-conformity score, bypassing the need for gradient-based optimization during inference. Moreover, in a certain sense, FFCP can be viewed as equivalent to FCP when using Algorithm 2 with the number of gradient steps $M = 1$.

In classification problems, isn't eq (5) going to be "0" a lot of the times? Indeed, if $g(\hat{v})=Y$, as one would hope most of the times for a decent classifier (features+head), then $\{\hat{v}\in v:g(v)=Y\}$ => eq 5 = 0. This means that "most of the times" the whole nonconformity measure computation can be skipped, leading to massive computational gains.

We thank the reviewer for the thoughtful question. Similar to FCP, FFCP is primarily designed for regression tasks, and the formulation presented in the main text reflects its application in the regression setting. However, we would like to emphasize that the feature-level techniques of FFCP is highly extensible and largely orthogonal to most existing conformal prediction methods, making it adaptable to a wide range of scenarios beyond regression.

For example, in classification tasks, we adopt an alternative version of our method, termed FFRAPS, which is better suited for classification. The detailed implementation is provided in Section 5.3.1 and Appendix B.7, where Algorithm 5 illustrates how the feature-level techniques of FFCP are incorporated into classification tasks under the RAPS framework. In contrast, the version discussed in the main body of the paper is tailored for regression problems, where the goal is to estimate continuous-valued prediction bands.

The empirical results are not as clearcut as the authors describe them. There are cases where FCP is better, cases where FFCP is better, and also cases were split CP is better. In general, split CP is often one order of magnitude faster than FFCP, while its performance (length) isn't too far from it. The authors should consider rephrasing the final message to convey this.

We understand the reviewer's concern, and we would like to offer the following clarifications:

First, the band length computed by FCP is inherently an approximation, as it is derived by mapping a region from the feature space back to the output space using methods such as LiRPA. This process introduces potential instability in practice, which may lead to degraded performance compared to Vanilla CP. For instance, Table 2 shows that FCP underperforms on datasets like FB1 and BIKE due to such variability.

Second, FFCP can be viewed as an efficient approximation of FCP. While it significantly reduces the computational burden, its performance remains comparable to that of FCP. In particular, as shown in Table 2, FFCP outperforms FCP on more than half of the evaluated datasets.

Lastly, since FFCP relies on the quality of the trained model, it may exhibit instability in rare cases. In such scenarios, its performance is generally on par with that of Vanilla CP.

Finally, the comparison should include Full CP, which should in principle achieve the best information coverage (split CP is on the other hand: it has the worst one). There are methods to speed up its computation, which should make it feasible to run this comparison [a.,b,c]

We sincerely thank the reviewer for the thoughtful suggestion. Since FFCP is designed as a fast variant of FCP, and FCP itself can be viewed as a specific instance of split CP, our comparisons have primarily focused within the split CP framework.

The main reason we did not include comparisons with full CP methods is due to their substantial computational overhead. Full CP typically requires retraining or refitting the model multiple times, which becomes impractical for complex tasks such as image segmentation or image classification. Therefore, implementing full CP in such settings poses significant challenges.

That said, we fully agree that including full CP in standard regression settings would provide a more comprehensive and objective comparison across CP methods. We will include these results in the next version of our paper.

Dear reviewer,

We would like to check if there are any further concerns about our article and rebuttal. We are glad to answer additional questions if there is anything unclear. Also, we humbly hope you could consider updating the overall rating if the previous issues have been fixed.

Thank you for your support.

We would like to thank the reviewer for the time and effort spent in reviewing our paper and we will address these concerns and provide our solutions in detail:

Weaknesses:

The paper is slightly incremental. While the context is new, approximating a nonlinear map with its linearization is a standard technique. The feature space map of [1] is also based on a linear relaxation.

We thank the reviewer for the insightful question. Here, we would like to clarify the motivation behind FFCP. We believe the contributions of FFCP lie primarily in two aspects:

1. FFCP, as a variant of FCP, significantly reduces computational overhead while maintaining performance comparable to FCP.

2. FFCP exhibits strong extensibility. Its feature-level technique is largely orthogonal to most existing CP methods, allowing it to be seamlessly integrated into classical frameworks such as CQR, RAPS, and LCP—as demonstrated in the experiments presented in this paper.

It is true that linear relaxation is a widely used technique for approximating nonlinear operators. In the context of FCP [1], the incorporation of feature space information occurs primarily through two key steps: (a) mapping from the output space to the feature space; and (b) mapping back from the feature space to the output space.

We believe the reviewer is referring to the linear relaxation used in step (b), which is implemented via LiPRA. Our experiments with FFCP suggest that leveraging feature space information can significantly benefit CP-based models. However, in practical deployment, we observed that

Step (a) requires gradient descent to find the optimal feature representation.

Step (b) relies on LiPRA for the backward mapping.

Both procedures introduce considerable computational overhead. Our goal was to retain the benefits of using feature space information while substantially reducing computational cost, ideally without sacrificing predictive performance.

To this end, we applied first-order Taylor approximations (which can indeed be viewed as a form of linear relaxation) to approximate both steps (a) and (b), thereby eliminating the need for gradient descent and LiPRA.

We found that even such a simple approximation leads to strong empirical performance, comparable to that of the original FCP method. This finding reinforces the value of feature-space guidance in CP while highlighting a more efficient way to leverage it.

The intervals are computed in the output space. The proposed approach is vanilla CP with a task-specific conformity measure. In the original CP formulation, the conformity score is not required to be $|f(X)-Y|$ as assumed in Algorithm 1.

As the reviewer correctly pointed out, FFCP constructs prediction sets in the output space. However, it is important to emphasize that, similar to FCP, FFCP also leverages feature information. From a constructional standpoint, FFCP follows the same conceptual pathway as FCP, mapping from the output space to the feature space and then back to the output space. By applying a first-order Taylor approximation during these two processes, FFCP achieves a significant simplification, resulting in an explicit and closed-form expression for the prediction band in the output space. This is a key advantage of FFCP over FCP: whereas FFCP allows for direct computation of the band length, FCP does not yield an explicit formulation, and thus its band length must be estimated through approximate procedures.

We acknowledge that there are various possible formulations for computing non-conformity scores in Algorithm 1. We will revise the corresponding description in the next version to reflect this more accurately

The paper's motivations are the computational costs of computing output space prediction intervals and their non-exactness. It would be useful to expand the explanation on page 2 with some details on how the mapping technique of Xu et al. works and how the proposed approach improves it.

We sincerely apologize for the confusion caused during reading. To clarify, we would first like to briefly explain the role of LiPRA (Xu et al.) in the context of our work.

LiPRA is fundamentally a framework for computing neural network output bounds via linear relaxation-based perturbation analysis techniques, such as CROWN and DeepPoly. Within FCP, LiPRA is used to compute the image of a feature space ball in the output space. Specifically, given Algorithm 2 in FCP, we obtain a feature space set of the form $\{g(v) : \|v - \hat{v}\| \leq Q_{1-\alpha}\}$, where $g$ is the prediction head, which is typically highly nonlinear. As a result, computing the corresponding band length in the output space lacks a closed-form expression.

However, with LiPRA, given a trained neural network $g$, a reference point $\hat{v} = g(X)$, and a radius $Q_{1-\alpha}$ determined via FCP's Algorithm 2 , we can construct the set $\mathcal{B}_v$ = { $v: ||v-\hat{v}|| \leq Q$ } and LiPRA allows us to approximate the corresponding output set $g(\mathcal{B}_v)$ = { $g(v) : v \in \mathcal{B}_v$ }. This provides an approximation to the prediction band in the output space.

In practice, however, this step introduces substantial computational overhead due to the complexity of the bound propagation and optimization procedures involved. To address this issue, FFCP adopts a first-order Taylor approximation to map the band length from the feature space to the output space. This significantly reduces computation while still preserving the core idea of leveraging feature-space uncertainty in conformal prediction.

Questions:

What do you mean by utilizing feature information in Vanilla CP? How does this relate to approximating conditionally valid CP sets?

In our work, utilizing feature information in Vanilla CP refers to our attempt to enhance Vanilla CP by incorporating feature-level information. Both FCP and FFCP can be viewed as extensions of Vanilla CP that leverage such information to improve performance.

Regarding approximating conditionally valid CP sets, we would like to clarify that the FFCP technique is not specifically designed to address conditional validity. A typical approach for achieving conditional coverage is LCP (Localized Conformal Prediction). However, the feature-level technique introduced in FFCP can also be integrated into LCP to improve its performance. The resulting method, FFLCP, demonstrates improved conditional coverage properties. Detailed implementation and empirical results are provided in Section 5.3.2 and Appendix B.6 (Algorithm 4).

What do you mean by square condition and expanding the differences between individual length quantiles in Theorem 4.2? How is stability in the feature and output spaces defined?

Due to our oversight, the statement of Theorem 4.2 was not clearly presented. The square conditions are intended to capture two key properties:

1. Expansion: We informally assume that the difference between the quantile and each individual score in the output space is smaller when measured in the feature space. This implies that performing the quantile operation (Step 4 in Algorithm 1 and Step 4 in Algorithm 2) does not compromise the effectiveness of the prediction bands, thereby supporting the efficiency of FFCP.

2. Quantile Stability: This condition ensures that the quantile computed on the calibration set generalizes well to the test set, which is essential for maintaining valid coverage.

Under these two assumptions, we argue that the average band length of FFCP is theoretically smaller than that of Vanilla CP (split CP).

To empirically validate the Expansion condition, we provide supporting experiments in Appendix B.2. In the case of FFCP, the difference between each sample and its corresponding quantile in the output space is the same as Vanilla CP. Therefore, Figure 4(a) can be interpreted as the distribution of non-conformity score deviations in the output space, while Figure 4(b) shows the same deviations measured in the feature space. The numerical results indicate that the deviations in the feature space are significantly smaller than those in the output space, thereby confirming that the Expansion condition is satisfied.

Why are FCP and Vanilla's efficiencies so unstable in some cases?

We begin by analyzing the key factors that influence the performance of Vanilla CP, FCP, and FFCP:

1. Vanilla CP is the most basic method, and its performance primarily depends on a) the quality of the trained predictive model.

2. FCP is also affected by a)the quality of model training, but in addition, it is influenced by b)the optimization quality of the gradient descent procedure in FCP's Algorithm 2, and c)the quality of the LiPRA-based bound propagation.

3. FFCP (our method) does not rely on additional models or optimization procedures, so its performance depends solely on a)the quality of the predictive model.

The band length produced by FCP is an approximation obtained via a two-step mapping from the output space to the feature space and back. This approximation introduces instability, which may result in degraded performance compared to Vanilla CP. For example, in Table 2, FCP performs worse than Vanilla CP on datasets like FB1 and BIKE, likely due to such instability.

FFCP serves as an efficient approximation of FCP, achieving a substantial reduction in computational cost. Despite this simplification, FFCP achieves comparable performance to FCP. Notably, Table 2 shows that FFCP outperforms FCP in over half of the benchmark datasets.

As FFCP relies on the output of a pre-trained model, it can also exhibit instability under certain conditions. In such rare cases, its performance tends to align with that of Vanilla CP.

Dear Reviewer,

Thank you again for your thoughtful feedback and for taking the time to review our work. We would like to check if there are any remaining questions or points that need further clarification. We are more than happy to provide additional information if needed.

If you feel that our responses have adequately addressed the previous concerns, we would sincerely appreciate it if you could consider updating your overall evaluation of the paper.

Thank you once again for your time and support.

We are grateful for the reviewer's valuable feedback and recognition of our work. We will provide additional explanations below.

Weaknesses:

For example you can modify line 8 of the abstract from "leveraging a Taylor expansion" to "leveraging a first-order Taylor expansion".

We apologize for the confusion caused and truly appreciate the reviewer’s clarification. As you correctly pointed out, our method is based on a first-order Taylor expansion, and we agree that the description should be more precise and rigorous. We will revise the corresponding statements in the next version to avoid any misunderstanding.

My only main concern is about the performances of FFCP compared to FCP. It is cool that the performance do not degrade much, which is a good motivation for the faster method. However, I find it quite surprising that, in some settings, the performance do actually increase for the faster linearized method. I would expect the performance to at most stay the same when the first order Taylor approximation is applied.

Can the author discuss how is it possible that the faster linarized model with FFCP in some settings performs better that the original not-linearized model with FCP? I find this effect very counterintuitive. Do the authors have some explanation of this effect?

We believe this phenomenon arises from the fact that the band length producted by FCP is not an exact value. Since FCP computes the band in the feature space and then maps it back to the output space, the resulting length is inherently an approximation rather than a directly computed quantity. Specifically, FCP relies on gradient descent during the calibration phase to identify optimal feature representations and employs LiRPA techniques during the test phase. Both procedures involve approximations and can introduce substantial variability. As shown in our experimental results, FCP may even underperform Vanilla CP in certain cases. The performance of FCP is highly sensitive to the number of gradient descent iterations and the choice of hyperparameters in LiRPA, both of which require careful tuning.

In contrast, FFCP circumvents the costly bidirectional mapping steps and features an explicit computational structure in the output space, resulting in greater stability. This often allows FFCP to outperform FCP in terms of predictive performance under practical settings. However, we acknowledge that if optimal parameters for FCP’s optimization steps can be identified, it typically achieves the best coverage-performance trade-off across most scenarios. In this sense, FCP remains superior on average in terms of predictive guarantees, while FFCP's primary advantage lies in its substantial reduction in computational cost.

In line 505 you write "where H is any function". This sound too strong and honestly feels wrong. Are you sure that you didn't miss some regularity conditions?

We apologize for the confusion caused by our oversight. To clarify, $H$ refers to $\mathcal{H}(v, X)$, which denotes the length of the prediction interval in the output space for a sample $X$, given a length $v$ in the feature space. Specifically, for FFCP, this is defined as $\mathcal{H}(v, X) = Q_{1-\alpha} \cdot \| \frac{\partial f(X)}{\partial h(X)} \|$. Thus, $\mathcal{H}$ is not an arbitrary function; rather, it has a well-defined and principled form. We will revise the description in the next version to improve clarity and correctness.

in Line 130, does it mean that the set of indexes $[n]$? Or am I missing something here?

We apologize for the confusion，this should indeed be $\mathcal{I}$, and the use of $n$ is a typo.

in Line 204 and 205 there is a clear repetition that could be avoided in Line 495 there is a typo: "which adjusted" should be "which is adjusted" in Line 505 there is a typo: "then the features" should be "then if the features", right?

We sincerely thank the reviewer for their careful and thorough review, and for dedicating substantial time and effort to our paper. The issues mentioned above were caused by our oversight, and we will promptly correct these errors.

Questions:

Why didn't the authors include the code for reproducibility in the supplementary material?

We regret any confusion this may have caused. We have organized the codebase on GitHub and will make it publicly available in the next version.

Dear Reviewer JJoX,

Can you reply to authors' rebuttal?

AC

We appreciate the reviewer's insightful comments. We will address these issues one by one.

Weaknesses:

insufficient contribution. the paper essentially proposes a faster (first degree taylor) approximation to an...

We understand the reviewer's concern, but we would like to clarify that the core advantages of FFCP lie in two aspects:

1. As a variant of FCP, FFCP significantly reduces computational cost while effectively leveraging feature space information. As a result, it consistently outperforms Vanilla CP (i.e., split CP) and achieves performance comparable to FCP.

2. The feature-level technique in FFCP is highly extensible and largely orthogonal to existing CP methods. It can be readily integrated into various frameworks, including CQR, RAPS, and LCP—and consistently improves performance, as demonstrated in our experiments.

While our method leverages a first-order Taylor expansion, it aims to address the core challenge of efficiently utilizing feature space information. FCP improves predictive performance by incorporating feature representations but suffers from high computational costs due to gradient descent and LiPRA. In contrast, FFCP approximates the feature mapping using gradient information, avoiding costly computations while retaining the benefits of feature-guided conformal prediction. It also provides a closed-form prediction band, improving interpretability.

From the perspective of extensibility, we have applied the FFCP technique to CQR, RAPS, and LCP (among others), and observed consistent performance improvements over the original models.

i think calling the original split conformal prediction algorithm as "vanilla" is a bit ...

Thanks for the reviewer’s reminder, we will make the necessary corrections in the next revision.

Questions: Experiment section

why is the performance not compared to other feature-based scaled CP methods? You cite Seedat et al...

Thanks for your constructive suggestion, we have supplemented the results by including those from the referenced literature.

Table A：Results of SSCP and FFCP

In terms of runtime, SSCP incurs substantially higher computational overhead, requiring the training of two additional networks, and is approximately 2 to 50 times slower than FFCP. In all cases, FFCP also achieves shorter band length. This may be attributed to SSCP’s stronger reliance on the base model’s predictive quality and the effectiveness of its auxiliary network training.

For FFCP, we select the shortest band length among all layers."...

Thanks for the reviewer’s question. This may be due to our lack of clarity in the paper. FFCP method records the total computation time for each layer, and then selects the layer that achieves the best results.

why does Vanilla CP has the exact same numbers as FFCP on ...

We sincerely apologize for the confusion caused by our unclear presentation, and we would like to take this opportunity to clarify the issue.First, regarding FFCP, the prediction band takes the form in Eq (8), where $Q_{1-\alpha}=\{\|f(X)-Y\|/\|\nabla g(v)\|\}$ When we evaluate the final (top) layer, the prediction function satisfies $g(\cdot)=f(\cdot)$, and hence $\nabla g(v)=\frac{\partial f(X)}{\partial g(v)}=\frac{\partial f(X)}{\partial f(X)}=\mathbf{1}$. As a result, in this case, FFCP degenerates to the same form as Vanilla CP, meaning their performance is equivalent. This explains why the results of FFCP and Vanilla CP are identical on certain datasets in Table 2.

Table 6 presents a different setting where the base model is under-trained. In this case, feature representations are less reliable, and FFCP tends to perform similarly—or even worse—than Vanilla CP. Due to our oversight, only results from Layer 3 were reported. We have updated the results in Table B by selecting the best-performing layer, which confirms that FFCP underperforms when the model is not sufficiently trained.

Table B: Untrained model Length on FFCP $full version$

Unsupported Claims

even just comparing to FCP, it is unclear from table 2 ...

As the reviewer correctly pointed out, FFCP does exhibit slightly inferior performance compared to FCP in a few cases. However, its primary advantage lies in the substantial reduction of computational cost, making it a practical trade-off between runtime efficiency and predictive performance. Within our framework, we define "comparability" as the ability of FFCP to either outperform or closely match the performance of FCP across a wide range of datasets. As shown in Table 2, FFCP achieves superior performance on more than half of the evaluated benchmarks.

Furthermore, unlike FCP, which estimates band length via an implicit and approximate procedure that may lead to instability, FFCP provides a closed-form expression for the prediction band. This enables exact and efficient computation, enhancing both interpretability and robustness. For these reasons, we argue that directly comparing the band lengths of FCP and FFCP on a single dataset may be misleading. A more appropriate evaluation should consider the relative performance across multiple datasets to assess the overall effectiveness and efficiency of FFCP.

I'm not sure Figure 2 shows the qualitative result...

Apologies for the confusion. In Figure 2, our intention was to illustrate that FFCP produces visually sharper edges in segmentation tasks, rather than claiming “sharper uncertainty bands.” We will revise this statement in the next version of the paper to avoid ambiguity.

Regarding the quantile computation, FCP adopts an image-level approach, where each image is treated as a single data point during calibration，and the $\infty$-norm $||Y-\hat{Y}||\_\infty=\max\_{i \leq d}\|y\_i-\hat{y}\_i\|$ is used to define the non-conformity score. In contrast, FFCP computes quantiles in a pixel-level manner, as highlighted in Remark 1, treating each pixel as an individual data instance.

We believe that uncertainty estimation in image segmentation is more appropriately measured at the pixel level. Therefore, we updated the quantile computation accordingly. This change led to clearer visual boundaries in the prediction masks. (For completeness, we also experimented with applying FFCP under the image-level quantile computation, but the results were suboptimal.)

Limitations:

What are the failure cases of the method?

We sincerely thank the reviewer for their comprehensive evaluation of our paper. In the case of FFCP specifically, since the calibration step involves division by the gradient norm, issues may arise when the gradient is very small. We recognize these limitations and view them as important directions for future improvement of our work.

How does it compare to other locally-scaled CP methods in different data setups?

We expand on LCP-related models in Appendix B.6, showing that the feature-level technique of FFCP can be extended to other CP frameworks. For instance, we introduce FFLCP as an extension of LCP for group coverage, and Table 12 demonstrates that FFLCP consistently outperforms LCP across datasets. Overall, the FFCP feature-based approach is largely orthogonal to existing CP methods, making it a broadly applicable enhancement for improving performance via feature information.

to what extent are the expressivity of FCP limited in FFCP? ...

We believe that both FCP and FFCP produce connected prediction regions in regression tasks. This stems from two key observations: (1) the feature space region is typically assumed to be bounded. (2) the prediction head $g$ is a continuous function.

Under these assumptions, the pre-image set $\{ v : g(v) \in \mathcal{C} \}$ for a connected set $\mathcal{C} \subset \mathbb{R}^d$ (such as a prediction interval) remains connected. While FCP may allow more flexible or complex shapes within the connected region due to the implicit nature of its band estimation (e.g., via LiPRA), FFCP yields prediction intervals with explicit structure resulting from its first-order Taylor approximation. This structural constraint limits the expressivity of FFCP compared to FCP, but it also brings substantial computational benefits and interpretability. Thus, neither FCP nor FFCP produces disjoint prediction intervals in standard regression settings.