- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 1
- Soundness
- 2
Read review
Paper summary
This paper studies online conformal retrieval in a semi-bandit setting. Specifically, for the returned retrieval candidate set, the learner can get the ground truth if the downstream hits the truth, which can be used to update the threshold.
To maintain the coverage guarantee at each step, this paper proposes a counterfactual update: the returned set overrides the proposed set entirely while continuing to monitor historical coverage.
The paper also provides related theorems and provides empirical evaluations on some real datasets, e.g., SQuAD and Natural Questions
Critical strengths
- The idea is straightforward and easy to follow.
- The authors provide many sensitivity analyses on the parameters.
Critical weaknesses
- The theorems are presented in a simple almost-sure way, without a finite bound to show the convergence rate.
- The setting is pretty ideal (line 43): this simplification is too naive because the retrieval task may miss the ground truth, so CP in practice cannot provide the guarantee. This setting paves the way for your Proposition 1.
- The authors cue the notion, i.e., protected(ion) or unprotected, multiple times at the beginning but defer the explanation. This makes the reading confusing.
Questions for authors
- Now that this is online conformal work and the author claims the per-step accumulative coverage guarantee, can you provide the online coverage trajectory for all experiments?
- Line 012: Does the retrieval return the feedback, or does the downstream work on the retrieved doc reveal the feedback?
- Lines 150-151: What kind of mechanism provides the assumed hit/miss feedback and identifies the correct document before the next update? For example, does this require a user annotation or a downstream verification system? When protection returns the entire set, the inclusion guarantees that the correct document is present, but what mechanism identifies it?
3 comments
Thanks for the response. Could authors provide the revision to support all your claims?
Thank you for asking to see the revision. The accompanying manuscript brings the proofs, experimental results and coverage curves into one PDF. The following locations correspond to the six points in your review.
W1. How fast do protection and document cost converge? Both the expected fraction of protected queries and the expected absolute error in average returned-set size decay as under the stated i.i.d. conditions. The comparator is the best feasible fixed threshold. Proposition 3 (p. 30) first bounds the expected number of protected queries over any horizon by separating random fluctuations from the learner's initial and subsequent deviations from the target. This step does not require independent queries. Theorem 2 (p. 31) then gives the rate for fixed scores, a unique target quantile with positive local slope, locally Lipschitz coverage and cost, and steps with . The proofs are in Appendices C.1–C.2 (pp. 30–32). The initialization enters explicitly in Eq. (22) on p. 32.
W2. What if retrieval misses every relevant document? At any prefix, the number of misses above budget is at most the number of protected returns whose entire pool lacks a relevant document. Appendix C.3 (pp. 32–34) proves this pathwise result. Proposition 4 also bounds expected protection and misses when the conditional pool-miss probability on protected rounds stays below the target miss rate by a fixed margin. On 10,000 natural Quora queries, top-51 recall was 95.04%. We reached 90.91% mean coverage at 18.04 documents/query. Twelve of 20 orders met the 90% target at every prefix. In the other eight, even returning all 51 documents missed the target at exactly the same 161 prefixes. The last was at query 79 and the largest excess was two misses (Tables 30–31 and Fig. 5, pp. 35–36).
W3. What does protection change? The opening paragraph of Section 1 (p. 1) now distinguishes the set selected by the threshold from the set actually returned. If one more miss could exceed the budget, protection returns the full pool. The returned outcome counts toward coverage, while the original proposal's outcome updates the threshold (Eqs. (3)–(4), p. 4).
Q1. Where can I see coverage throughout each experiment? Table 4 (p. 19) links each batch to its full-sequence and first-100-query curves (Figs. 7–35, pp. 37–65). Counterfactual updates meet the target at every prefix in the original positive-containing pools. For distribution switches, Fig. 30 (p. 60) measures coverage from the original start. Figure 31 (p. 61) restarts the count at the switch to show local adaptation. The prefix guarantee applies to the full sequence. Figure 36 (p. 66) shows both Table 3 update rules for all 20 seeds and all three nested horizons. These replays reproduce the Table 3 endpoints exactly. Figure 37 (p. 67) shows the five coefficients replayed on development order 12345.
Q2. Who supplies feedback, and when? An external annotator or downstream verifier judges relevance. The abstract (p. 1) names the verifier, and our experiments use reference labels. The learning-rate result assumes accurate feedback before the next update (Section 3.1, p. 3). When feedback is delayed, Proposition 5 (p. 34) proves that counting every pending return as a possible miss preserves the prefix bound even with out-of-order arrivals. With perfect pool recall, this gives the original coverage target at every prefix.
Q3. How is a relevant document identified after a full-pool return? In the designated-label setting the annotator identifies the relevant document. In the natural-pool experiment we use reference labels to check the returned ranking until its first relevant document, or exhaust the set on a miss. Because the proposal is a prefix, that result determines whether the proposal hit even if several documents are relevant (Section 4.3, pp. 4–5). Every query needs a returned hit or miss. Only a protected query can require distinguishing a hit inside the proposal from a hit elsewhere in the pool. On the same natural Quora orders this rule required 3.52 ranked document checks/query, compared with 5.68 for full-pool returns (Table 30, p. 36).
Response to Reviewer mtMr
Thank you for your review. We have added protection and cost bounds that include initial adaptation, plus a coverage bound with an explicit pool-miss term. In a new Quora experiment without inserted positives, we obtain 90.9% overall coverage at 18.04 documents/query. We also clarify how external verification supplies relevance feedback.
W1. Finite-time convergence beyond almost-sure guarantees
Under the iid conditions below, expected protection frequency and absolute average-cost error are O(T−β/2). The cost comparator is the best feasible fixed threshold, and the bounds include initial adaptation. Let α be the target miss rate, NT the number of protection triggers, and pt the proposal-miss probability conditional on the pre-query history. Define DT=∑t=1TE∣pt−α∣. With positive-containing pools and accurate, immediate feedback, we prove, without iid, ENT≤[4(1+T)+2DT]/α. The bound separates fluctuations from adaptation through DT. For pool size at most K, expected protection cost is at most KENT/T documents/query above the learner's own proposals.
The O(T−β/2) rate assumes iid queries, fixed scores, a unique target quantile, positive local coverage slope and local Lipschitz coverage/cost. Steps satisfy ηt=ct−β, c>0, 1/2<β<1, with initialization included in the constants. The threshold second-moment rate follows the form of Angelopoulos et al. (2024), Proposition 2. Our added step transfers that rate to protection and returned cost.
W2. Coverage when candidate pools miss the relevant document
With imperfect recall, excess prefix misses are bounded by protected full-pool misses: Mt≤⌊αt⌋+Et. Here Mt counts actual misses and Et protected full-pool misses. A full-pool miss still identifies a nested proposal miss.
The natural-pool experiment uses Quora BM25 top-51 pools, with a relevant document present for 95.0% of 10,000 queries, across 20 fixed orders. The 90% target holds at every prefix in 12/20 orders. The other eight have 161 violating prefixes, last at query 79, with at most two excess misses. Six first violations occur in queries 1–9, and two at 14 and 23. Full-pool returns fail at the same prefixes, identifying candidate availability as the constraint at those prefixes.
Furthermore, expected protection and misses remain controlled when the conditional pool-miss probability satisfies ρt≤ρˉ<α on protected rounds. Here ρt uses the same pre-query history as pt. The W1 trigger bound then uses denominator α−ρˉ and retains DT, and EMT≤⌊αT⌋+ρˉENT. This applies, for example, to iid queries with a fixed retriever whose population miss rate is below α.
W3. Define protection before using the term
We now define the proposal as the threshold-selected set returned by the unprotected learner. Protection returns the full pool when another miss would exceed the budget. Returned outcomes control coverage. Proposal outcomes drive learning.
Q1. Coverage trajectories for every online experiment
Counterfactual updates meet the target at every prefix in all original positive-pool settings. We computed per-query cumulative coverage and first-100-query views for every Table 4 batch. Coverage after switches uses the original sequence start. Table 3 replays cover both rules, 20 seeds and three nested horizons and exactly reproduce its endpoints. We also replayed five coefficients at seed 12345. Natural-pool trajectories show the early departures quantified in W2.
Q2. Is feedback supplied by retrieval or downstream verification?
External annotation or downstream verification supplies feedback. Retrieval selects documents, while the external mechanism checks relevance. Our learning analysis uses accurate, immediate feedback.
For delayed feedback, we added a conservative coverage guard: count every pending return as a miss, and return the proposal only if that count plus one fits the miss budget. With accurate feedback on arrival, arbitrary delays and out-of-order arrivals preserve Mt≤⌊αt⌋+Et. Perfect pool recall gives Et=0 and every-prefix coverage.
Q3. How is the relevant document identified after protection?
External annotation or verification identifies relevance. Our experiments use reference labels. A verified first relevant position or miss determines every nested proposal's outcome, including with multiple relevant documents. Every query needs returned hit/miss feedback. Only protected rounds can need an extra proposal-hit judgment. On natural pools this requires 3.52 document checks/query versus 5.68 for full-pool returns, showing that smaller returned sets also reduce label-inspection cost.