Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: This paper aims to construct approximate conditional coverage models using KNN (which approximates a transformer model). By firstly partitioning the data and then applying CP conditioned on the label and the partition they derive an algorithm which allows them to obtain approximate conditional coverage guarantees.
strength_and_weaknesses: Strengths:
- The paper looks at a new way to use CP in the transformer setting.
- But firstly, they can construct a novel method by approximating the transformer using a KNN and then subsequently using this approximation to perform CP.


Weakness:
- Unfortunately, the paper is very poorly written. I barely understand the method even as a person that has published in CP before.
- For example, I don't understand the data partitioning 4.1.2. there is no intuition on what is happening, and the notation seems non-understandable. q_t is defined as a feature but then it is also a function(q_t(k-1)) ? Could the authors please add a simple example for the reader to understand the intuition behind it?
- There is no explanation on Venn Arber in the paper. 4.3 is not self contained and it is hard to understand what is happening without having knowledge on this from the get go. A paper should be self contained or at least should intuition on what is happening in the algorithm.
- Also the notion of memory layer is not well explained in the paper at all hence assuming this knowledge from the reader.
- Following all of the above I have big difficulties reading this paper and getting any intuition on what the paper is trying to achieve.
- The experiments are also explained barebones and I don't understand the main message behind it. what does "Only the VENN-ADMIT sets consistently obtain acceptable singleton set coverage across datasets".
clarity,_quality,_novelty_and_reproducibility: Overall I think the paper is poorly written and hard to understand the main message. I have laid out the problems I encountered in the review above and hope that the authors could add more intuition into their paper. 
summary_of_the_review: I believe the paper has to be rewritten significantly in order to be accepted. As someone who has published in the field of CP before it is even hard for me to understand what is happening in this paper. Hence I recommend the authors to add additional intuition into their paper to make their goal as well as methodology clearer.

If they authors are able to update the script with clarity I would be willing to raise my score.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper proposes a new approach for prediction set construction for transformer networks, which is mainly designed to obtain approximate conditional coverage. The proposed approach is evaluated in NLP classification tasks to show its efficacy. 
strength_and_weaknesses: **Strengths**:
* Extensive evaluation on NLP tasks

**Weaknesses**:
* A proposed approach is unclear (e.g., due to not well-defined terms)
* A proof on coverage guarantee is missing
* An interpretation on empirical coverage results is unusual. 



(Weakness 1)
The Method section is unclearly written. First, “ADMIT” prediction sets and “Venn-ADMIT Predictor” are not well defined — probably either adding simplified algorithm blocks in the main paper (instead of Appendix) or defining the prediction sets for each type may help. Moreover, the description on Venn Predictor is missing, but pointing to an external reference; I think the paper needs to be self-contained by providing a brief summary. 

(Weakness 2)
I think the main claim of this paper is that the proposed approach achieves a conditional coverage guarantee. However, its proof is missing. Considering that the conformal prediction work mainly focuses on proving correctness guarantees, this work needs rigorous proofs on the conditional guarantee. Otherwise, this work only provides empirical evidence, which is interesting, but not enough.

(Weakness 3)
Table 4 and 5 show the empirical coverage of baselines and also the proposed approach. Given alpha=0.1, the empirical coverage of conformal prediction is around 0.1 (mainly because the empirical coverage of conformal prediction sets is usually evaluated, assuming that it is conditioned on a calibration for practical reasons); thus, baseline coverage results look okay with me. I cannot see why 0.88 or 0.89 empirical coverage is bad for baselines.

clarity,_quality,_novelty_and_reproducibility: (Clarity) As mentioned in Weaknesses, the method section is unclear. 

(Quality) The proposed approach does not come with a rigorous guarantee on conditional coverage. 

(Novelty) The proposed approach is the combination of known approaches; but the combination seems novel. However, empirically, the proposed approach looks as good as baselines (as mentioned in Weaknesses), so I’m not sure if the novelty is meaningful. 

summary_of_the_review: I think that the method section writing needs to be improved, the conditional coverage guarantee of the proposed approach needs to be proved, and the proposed approach requires to outperform the baseline (in terms of conditional coverage) to show its efficacy. Thus, currently, I vote for rejection.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This work introduces a new conformal prediction-based approach for constructing calibrated predictive intervals. The improvements are from the reliability of KNN-based approximation and a novel Venn predictor. The proposed approach is evaluated on large scale sequence modeling tasks.
strength_and_weaknesses: 1. I am confused why the proposed method makes sense. Usually, such new algorithms should be justified through proper theoretical guarantee from a statistical perspective. For example, predictive inference-based methods should at least provide results on valid (unconditional) coverage and conditional coverage.

2. Why is the proposed method still valid under distribution shift? Previous works need to assume the knowledge of the exact form of shifting to guarantee the exchangeability, while in this work there is no such assumption.

3. Is it possible that the proposed is trading performance with computation? A time-complexity analysis is missed.
clarity,_quality,_novelty_and_reproducibility: The writing of this work is clear. However, the quality could be improved if the above mentioned issues could be properly address. The idea is novel. The reproducibility is not clear as the code is not provided, plus there is no paragraph of reproducibility statement as suggested by ICLR.
summary_of_the_review: The proposed method in this work is novel and shows promising empirical results. I would consider raising the score if my concerns could be addressed properly.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The authors propose a KNN-based Venn-predictor for improved approximate coverage for text and token classification tasks.
strength_and_weaknesses: Strengths:
- The paper addresses an important problem of improving approximate conditional coverage.
- It is generally ambitious to demand conditional coverage not only in neighborhoods but also depending on label _and_ the prediction set size. The later, in particular, is known to be difficult and sometimes hinders interpretation of uncertainty for individual examples.
- The introduction clearly states this motivation and I also like the short overview of the NLP tasks tackled.
- The paper includes experiments on several interesting datasets and Table 1 helps to get an overview of the tasks.

Weaknesses:
Writing:
In general, I feel that the method is very difficult to follow. This is mainly due to a missing high-level overview of how individual methods are put together, what is trained/calibrated on which set and how it comes together. It is made worse by an extremely confusing description of VENN predictors that are used on top of standard conformal prediction sets.
Individual comments:
- The paper seems to highlight to work on transformers, which is fine. However, I find that the method itself should be independent of the architecture, so I find this emphasize confusing at times. In my opinion, writing would benefit from assuming a general function that produces features for tokens or documents depending on the task. Or am I overlooking anything transformer-specific?
- I had difficulties following the KNN approximation introduced in 4.1. This is partly due to notation (is arg K min the K-minimum elements over I?) and some ambiguity how the parameters are actually learned. Moreover, the definition of q_t – the “count of consecutive sign matches” is not very intuitive. Is the argument really capital K, or should it be lower-case k? Why is q_t assumed to be useful?
- Based on the appendix, in 4.2, standard conformal calibration is used to obtain thresholds. This is not really clear from 4.2 and I feel the main paper would benefit from the algorithms and a discussion.
- There is no real introduction of VENN predictors which really makes 4.3 difficult if not impossible to follow without reading up on it. Footnote 1 is redundant and not helpful.
- Footnote 2 is also a bit vague. So leave-one-out-cross-validation is used to obtain a prediction set for each calibration set. But what implication does this have in terms of a coverage guarantee? Especially as it is stated to be explicitly different from cross-conformal or Jacknife+ conformal prediction.
- The third paragraph in 4.3 is entirely unclear to me – what are these augmented distributions and points?
- Footnote 4 is also a bit unmeaning.
- Tables 3, 4 and 5 are very packed and in my opinion poorly introduced/described. Throughout the text it remains unclear what exactly is shown and how I should read these tables in order to draw the same conclusions as the authors.

Method:
- The method requires an additional training set for the KNN, this is not really ablated or discussed. Compared to other methods working without the KNN, does that introduce a disadvantage?
- What is the intuition of the additional mass calibration?
- Regarding contributions, I am a bit unsure whether the main contribution is the combination of the KNN approach with conformal prediction and VENN predictors or whether there is any methodological contribution in the VENN predictors itself. Could the authors clarify? For me it looks like the main contribution is the combination of these approaches, but this combination is partly difficult to follow due to poor writing.
- What kind of guarantee do I get from this approach. Due to confusion of the leave-one-out conformal predictor, I am unsure whether a standard marginal or even class-conditional guarantee is obtained in addition to better empirical conditional coverage.

Experiments:
- In general, I do not understand how experiments are run. Are the reported numbers averaged across different KNN/cal/test splits on these datasets? If so, how many samples have been used and why not plot or report the variation in coverage and size?
- Why is RAPS applied on the transformer but VENN-ADMIT on the KNN? I am missing a KNN-based RAPS baseline and a discussion why VENN-ADMIT does not work directly on the KNN.
- In Table 3, I cannot really see where the “empirical behavior of the calibration points differs significantly”. Across most parts, numbers seem to be roughly similar across some labels. What am I supposed to compare?
clarity,_quality,_novelty_and_reproducibility: See above.
summary_of_the_review: I do not believe this paper to be ready for publications. This is mainly based on confusing writing, that makes it difficult to understand not only the method but also the provided guarantees and judge novelty and experiments.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper considers the problem of approximate conditional coverage for prediction sets obtained by conformal prediction when the predictor is a transformer network. This is a very important and challenging problem in general.

The main idea behind the Venn-ADMIT method to solve this problem is very good, but the paper is not well-written and it is very hard to understand as echoed by all the reviewers'.
- I had a hard time understanding the meaning of "Definition 2". It needs better justification because every proposition about the method's robustness is directly defined in the context of well-calibrated selective classifiers. So I was not able to understand the theoretical implications of the approach.
- The method for creating weak and well-calibrated selective classifiers should have been introduced and explained earlier.
- The paper has good empirical results, but based on my understanding, theoretical guarantees are weak.

The fact that even people working in conformal prediction are not able to understand the details, the paper definitely needs to be re-written for clarity and precision. This is the main reason for my recommendation to reject the paper. I think the research direction and the method is promising, and I strongly encourage the authors' to carefully think about the exposition and writing for resubmission. One additional point to make clear is what aspects of the method are specific to transformers and what precludes from generalization to other deep networks.
Decision: Reject