{"id":"ee4b08c8-7abe-4716-a977-7cea8d5ff561","arxiv_id":"2608.07139","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"OCPQ achieves expected coverage at least beta minus O(T^{-1/3}) and O(T^{2/3}) regret in online conformal prediction with query-only label access and no feedback from deployed sets.","lead":"OCPQ is a new method for online conformal prediction that works when the model never finds out whether its own predictions were correct. Instead of feedback, it asks for the right answer on a small random fraction of rounds, and still gives a formal guarantee on how often its sets contain the truth.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3's high-probability regret/coverage proof applies Hoeffding to history-dependent averages; expected-coverage Corollary 1 appears sound.","rationale":"The reader's verdict is CONDITIONAL, and my read does not move that verdict. The primary advertised guarantee -- expected coverage at least beta - O(T^{-1/3}) under an oblivious stream with expected T^{-1/3} queries -- is justified by Theorem 1 plus Theorem 2, and I could not identify a flaw in that chain. The more serious issue is the high-probability claim. The proof of Theorem 3 invokes Hoeffding's inequality on sequences that are not independent: the algorithm's actions are sampled from history-dependent distributions, so their rewards form an adapted process, not an i.i.d. sample, and r2 is a ratio over a random, history-dependent set of query rounds. This is the same concern the reader flagged as a 'concentration gap.' It does not overturn the expected-coverage result, but it does mean the paper's advertised high-probability regret and coverage bounds are not rigorously established as written. A repair may be possible via Azuma or Freedman inequalities, but that is not supplied. Since the expected-coverage central claim stands, CONDITIONAL remains the appropriate verdict, pending either a corrected high-probability proof or a softening of that claim to expectation-only.","tokens_in":34229,"tokens_out":17123,"duration_ms":160776,"concrete_test":"Independently re-derive Theorem 3 by replacing the two Hoeffding applications with martingale concentration (e.g., Azuma-Hoeffding or Freedman's inequality) on the adapted sequences R(A_t,t) - E[R(A_t,t) | F_{t-1}] and on the query-subset averages defining r2; if the resulting regret bound has a slower rate or an extra logarithmic/constant factor, revise Theorem 3 and Corollary 2 accordingly. Alternatively, simulate OCPQ on the hard-shift adversary from Appendix Figure 5d with T = 100000 and at least 1000 seeds, and compare the empirical tail probability P(regret > 2 T^{5/6+delta/2}) with the claimed confidence bound; a large mismatch would confirm the concentration gap.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central expected-coverage claim, Corollary 1, is supported by the expectation-only arguments of Theorems 1 and 2, and I do not see a flaw in those proofs. The load-bearing weakness is in the high-probability companion result, Theorem 3, which the paper advertises as a contribution and which is the sole basis for Corollary 2. In the Appendix proof of Theorem 3, Hoeffding's inequality is applied to the quantities r1 = R_{T,pi}/T and r2 = (1/Q) * sum_{t: a_t=query} sum_{m in M} P_{m,t} R(m,t), as if these were averages of independent bounded variables. They are not: the actions A_t are sampled from distributions P_{m,t} that depend on all previous observations, so the reward sequence R(A_t,t) is adapted rather than independent, and the query times defining r2 are random and history-dependent. Hoeffding's inequality controls deviations of sums of independent variables from their unconditional mean; Azuma-Hoeffding would control deviations from the sum of conditional means, but the proof does not set up such a bound. The step E[r1] = (1-epsilon)E[r2] is also used as an exact identity even though Q is random and appears in a denominator. Therefore the probability expression in Eq. (8) is not established as stated. This matters because Theorem 3 and Corollary 2 are the paper's advertised finite-horizon high-probability guarantees; if the concentration step cannot be repaired, those guarantees are unproven. The expected-coverage guarantee remains unaffected, since it requires only the expectation bound from Theorem 1.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces OCPQ, an online conformal prediction method for a 'beyond feedback' protocol: on each round the learner either outputs a prediction set or queries the true label, but never both, so no deployed prediction is ever evaluated. The problem is reduced to a finite partial-monitoring game whose actions are prediction thresholds plus a query action, and OCPQ adapts the label-efficient forecaster of Cesa-Bianchi, Lugosi, and Stoltz (2004) to this setting. The main theoretical claims are an expected regret bound of O(T^{2/3}) (Theorem 1), a reduction from regret to coverage (Theorem 2), an expected coverage guarantee p_cover >= beta - O(T^{-1/3}) at an expected query fraction T^{-1/3} (Corollary 1), and high-probability versions of the regret and coverage bounds (Theorem 3 and Corollary 2). Experiments on distribution-shift benchmarks and on LLM safety-monitoring prompts with adversarial rewrites illustrate the coverage-efficiency trade-off and compare with full-feedback ACI.","tokens_in":34531,"tokens_out":13079,"duration_ms":116143,"significance":"The expected-coverage guarantee in Corollary 1 is a meaningful and clearly stated contribution: it provides finite-horizon coverage control for online conformal prediction when deployed prediction sets produce no feedback, at the price of an O(T^{-1/3}) coverage deficit and an O(T^{-1/3}) query rate. I checked the key algebra of Theorems 1 and 2 and found the expected-regret and regret-to-coverage arguments sound: Lemma 1 establishes the unbiasedness of the estimator, and the derivation of Corollary 1 from the two theorems is valid. The paper is also honest about its modeling assumptions, explicitly acknowledging the oblivious-adversary restriction and the fact that queries count as miscoverage events. The experimental section is substantial and includes a realistic LLM safety-monitoring application. However, the advertised high-probability result (Theorem 3 and Corollary 2) is not proven as written, because the concentration argument applies Hoeffding's inequality to history-dependent random variables and combines dependent probability events by multiplication.","major_comments":[{"comment":"The proof of Theorem 3 is invalid as written. Hoeffding's inequality is applied to r1 = R_{T,pi}/T and to r2 = (1/Q) * sum_{t: a_t=query} sum_{m in M} P_{m,t} R(m,t), but these are not averages of independent bounded random variables: the action A_t at time t is sampled from a distribution P_{m,t} that depends on all previous observations, and the terms inside r2 share the same history and are divided by the random quantity Q. Consequently the displayed inequalities such as P(E[R_{T,pi}]/T - lambda >= r1) and P(r2 - E[r2] >= lambda) <= exp(-2 Q lambda^2) do not follow. In addition, the proof uses the identity E[r1] = (1-epsilon) E[r2] as exact, but this does not follow by linearity of expectation because the denominator Q in r2 is random and correlated with the numerator. Finally, the final probability in Eq. (8) is obtained by multiplying two success probabilities for events that are not independent; a union bound would give a sum of failure probabilities, not a product. As a result, Theorem 3 and Corollary 2 are not established. This is load-bearing because these high-probability guarantees are explicitly listed among the paper's contributions and are used to argue that OCPQ has no pathologically high variance.","section":"Appendix: Proofs, Theorem 3"}],"minor_comments":[{"comment":"The sign of the 2*T^{-1/4} term in the coverage bound in the appendix is inconsistent with the main-text version and with the derivation from Theorem 3: it should be minus, not plus.","section":"Appendix: Corollary 2"},{"comment":"In the expansion of tilde{R}_{T,pi} - R_{T,pi}, the line containing 'T*(r2 - r2)' should read 'T*(r2 - r1)'; as printed it is a typo that obscures the argument.","section":"Appendix: Proofs, Theorem 3"},{"comment":"The statement that the distribution of hat{X}_{A_t,t} 'only depends on epsilon, x_t, y_t, and C' is imprecise because hat{X} also depends on the action A_t. The needed independence between P_{m,t} and hat{X}_{m,t} holds because the query indicator at time t is independent of the history that determines P_{m,t}; the proof should say this explicitly.","section":"Appendix: Proofs, Theorem 1"}],"recommendation":"major_revision","confidential_remarks":"The expected-coverage result (Corollary 1) appears sound and is the paper's main contribution. The blocking issue is confined to the high-probability companion result; if the authors repair Theorem 3 with a martingale-based concentration argument or appropriately downgrade it to a conjecture, I would be supportive. The paper fits the scope of the journal and the experiments are relevant."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThe core result here is real. OCPQ is the first OCP method I know of that gets finite-horizon expected coverage guarantees without any feedback from deployed prediction sets, at the cost of an O(T^{-1/3}) coverage deficit and an expected T^{-1/3} query rate. The reduction to a partial monitoring game is clean, and the adaptation of the label-efficient forecaster is honest—they cite Cesa-Bianchi, Lugosi, and Stoltz rather than pretending a new generic rule. I checked Theorem 1 and Corollary 1; the unbiased-estimator step and the regret-to-coverage conversion are sound. The experiments, especially the WildGuardMix LLM safety-monitoring study, are sensible and well described, though no code is released.\n\nThe soft spot is Theorem 3, the high-probability regret bound, and its Corollary 2. The appendix proof applies Hoeffding's inequality to r1 = R_{T,π}/T and r2 = (sum over query rounds of P_{m,t}R(m,t))/Q as though they were averages of independent bounded variables. They are not: the action distributions P_{m,t} depend on the entire past, and Q is random and appears in the denominator. The identity E[r1] = (1−ε)E[r2] is also not exact with a random denominator. This means the claimed high-probability guarantee is not established as stated. Azuma-Hoeffding or a uniform-convergence argument might repair it, but as written it's a genuine gap. The expected-coverage guarantee is unaffected, so the paper's main advertised result survives.\n\nThis is a solid theoretical paper with one load-bearing proof flaw. The authors are transparent about the oblivious-adversary assumption and about expectation-based coverage. The citation pattern looks appropriate; self-citations are to work they build on directly.\n\nSend it to a serious referee. I'd want the high-probability proof repaired or downgraded to a conjecture before acceptance, but the expected-coverage result alone is a sufficient contribution. Worth a reading-group session.","headline":"Strong expected-coverage result for a genuinely new query-only OCP setting; the high-probability companion proof has a real concentration gap that needs fixing.","tokens_in":35099,"tokens_out":4134,"would_cite":true,"duration_ms":34726,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q32","62G15"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper shows that online conformal prediction can keep a user-specified coverage guarantee even when no deployed prediction set is ever evaluated, by querying the true label on only an expected $T^{-1/3}$ fraction of rounds.","keywords":["online conformal prediction","partial monitoring games","label-efficient learning","coverage guarantees","adversarial data streams","uncertainty quantification","query-or-predict protocol","regret bounds"],"falsifier":"Run OCPQ on a stream produced by an adaptive adversary that makes each label depend on whether the learner queried or predicted on previous rounds, for example by selecting the lowest-probability class under $C$ precisely on rounds that follow a query; if the expected coverage falls below $\\beta - O(T^{-1/3})$ for large $T$, the oblivious-stream assumption is the reason and the central guarantee does not hold.","tokens_in":33985,"feed_emoji":"🎯","tokens_out":8354,"duration_ms":71152,"temperature":0.7,"pith_summary":"Online conformal prediction normally works by feedback: after the learner emits a prediction set, it sees the label or a coverage signal and updates the set size for future rounds. This paper studies the stricter protocol in which the learner must choose between predicting and querying, so a deployed set is never evaluated directly. It shows that the protocol is still tractable: OCPQ, an adaptation of the label-efficient exponentially weighted forecaster, queries only an expected $T^{-1/3}$ fraction of rounds and still guarantees expected coverage at least $\\beta - O(T^{-1/3})$ for any chosen $\\beta\\in[0,1]$, against any oblivious data stream of length $T$ and any black-box classifier. The practical point is that labels harvested from abstention or deferral rounds, rather than from prediction outcomes, are enough to keep uncertainty quantification honest.","feed_headline":"OCPQ keeps coverage with only T^{-1/3} label queries","feed_subtitle":"No deployed set is ever evaluated, yet the coverage shortfall stays O(T^{-1/3}).","key_machinery":"The load-bearing objects are the auxiliary reward function $R(m,t)$ and the inverse-probability estimator $\\hat{X}_{m,t}$. For threshold $m$ on round $t$, $R(m,t)=0$ if the true label is outside the set $\\Gamma_C(x_t,m)$, and otherwise $1-m(1-\\beta)$; the query action always gets reward zero. When a query is made, $R(m,t)$ is revealed for all $m$ simultaneously, and the update $\\hat{Z}_{m,t+1}=\\hat{Z}_{m,t}+\\hat{X}_{m,t}$ with $\\hat{X}_{m,t}=1-\\frac{1-R(m,t)}{\\epsilon}$ on query rounds keeps cumulative reward estimates unbiased (Lemma 1). The exponentially weighted mix over thresholds then drives regret to the optimal $\\Theta(T^{2/3})$ rate for this partial monitoring game.","core_discovery":"The paper's central claim is Corollary 1: on any oblivious stream $z^T$, for any classifier $C$, any finite threshold set $\\mathcal{M}\\ni\\{0,1\\}$, and any target $\\beta\\in[0,1]$, the OCPQ algorithm with $\\epsilon=T^{-1/3}$ and $\\eta=T^{-2/3}\\sqrt{\\ln|\\mathcal{M}|}$ satisfies $\\mathbb{E}[p_{\\mathrm{cover}}]\\ge \\beta - (2\\sqrt{\\ln|\\mathcal{M}|}+1)/T^{1/3}$, while querying an expected $T^{-1/3}$ fraction of rounds. The algorithmic step is to treat prediction thresholds as experts and the query action as an observation-only arm; a query reveals the auxiliary reward $R(m,t)$ of every threshold at once, and inverse-probability weighting keeps the cumulative estimates unbiased. The resulting $O(T^{2/3})$ expected regret is converted into coverage by noting that the always-safe threshold $m=1$ collects $\\beta$ per round, so low regret forces coverage close to $\\beta$.","pith_inferences":["A data-dependent query rate is a natural follow-up: the proof only needs $\\epsilon$ tuned to $T$, so a scheme that lowers $\\epsilon$ as the best-threshold estimate stabilises could reduce label cost while preserving the $O(T^{-1/3})$ deficit, although the authors do not analyse this.","Because the guarantee is relative to the best threshold in a fixed finite grid $\\mathcal{M}$, an adaptive grid that refines around the current favourite should improve efficiency without extra queries; the sensitivity experiments suggest diminishing returns beyond about 64 thresholds.","The sigmoidal coverage-versus-$\\beta$ curves reported in the experiments imply that calibration of $\\beta$ is delicate; a practical extension would be a short burn-in phase to estimate the inflection point before committing to $\\beta$.","If the adversary is made adaptive, I would expect the unbiased estimator argument in Lemma 1 to break, so the paper's coverage bound should be read as tied to the oblivious-stream model rather than as a fully adversarial guarantee."],"forward_implications":["Every black-box classifier gains a finite-horizon coverage guarantee even though no deployed prediction set is ever evaluated.","Users can set the target coverage through $\\beta$ and, since the deficit term is explicit, can inflate $\\beta$ to compensate for finite $T$.","The $O(T^{2/3})$ expected regret is asymptotically optimal for the induced partial monitoring game when $\\beta<1$, so this protocol cannot be solved at a faster rate by any algorithm.","The coverage lower bound also holds with high probability, by Theorem 3 and Corollary 2, not only in expectation.","Only an expected $T^{-1/3}$ fraction of rounds requires a label, making the method suited to settings where labels are expensive or arrive only through deferral."],"supporting_citations":[{"why":"Supplies the label-efficient exponentially weighted forecaster whose update rule OCPQ adapts so that a query replaces a prediction.","marker":"Cesa-Bianchi, Lugosi, and Stoltz (2004)"},{"why":"Gives the partial-monitoring classification used to show that the $T^{2/3}$ regret rate is optimal for this game.","marker":"Lattimore and Szepesvari (2018)"},{"why":"Provides the ExO algorithm used as the empirical partial-monitoring baseline and the optimisation viewpoint for comparison.","marker":"Lattimore and Szepesvari (2019)"},{"why":"Serves as the full-feedback adaptive conformal benchmark against which OCPQ's coverage-efficiency frontier is compared.","marker":"Gibbs and Candès (2021)"},{"why":"Represents the bandit-feedback OCP approach that OCPQ extends to the no-feedback setting.","marker":"Wang and Qiao (2024)"},{"why":"Establishes the semi-bandit OCP baseline that also cannot handle the query-or-predict protocol.","marker":"Ge, Bastani, and Bastani (2025)"},{"why":"Offers an adversarial semi-bandit OCP algorithm and an alternative reward/loss construction that OCPQ's auxiliary reward is compared with.","marker":"Yang, Kim, and Park (2026)"},{"why":"Relates no-regret learning to online conformal coverage and motivates the regret-to-coverage reduction.","marker":"Ramalingam, Kiyani, and Roth (2025)"}],"fun_headline_variants":["OCPQ: coverage with only T^{-1/3} queries, no feedback","Coverage without prediction feedback: query T^{-1/3} rounds","OCPQ: no feedback, still high coverage with sparse queries","Query a fraction, cover the label: OCPQ does it","OCPQ: T^{-1/3} queries, coverage gap O(T^{-1/3})"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The data stream is fixed in advance: the inputs and labels cannot respond to the learner's past queries or predictions, and every query must return the exact true label.","fun_headline_variants_meta":{"raw":{"variants":["OCPQ: coverage with only T^{-1/3} queries, no feedback","Coverage without prediction feedback: query T^{-1/3} rounds","OCPQ: no feedback, still high coverage with sparse queries","Query a fraction, cover the label: OCPQ does it","OCPQ: T^{-1/3} queries, coverage gap O(T^{-1/3})"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000681,"raw_usage":{"total_tokens":3148,"prompt_tokens":1055,"completion_tokens":2093,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":671,"completion_tokens_details":{"reasoning_tokens":2006}},"tokens_in":671,"tokens_out":2093,"duration_ms":13601,"temperature":1.0,"reasoning_tokens":2006,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-10T14:07:57.145644+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run OCPQ on a stream produced by an adaptive adversary that makes each label depend on whether the learner queried or predicted on previous rounds, for example by selecting the lowest-probability class under $C$ precisely on rounds that follow a query; if the expected coverage falls below $\\beta - O(T^{-1/3})$ for large $T$, the oblivious-stream assumption is the reason and the central guarantee does not hold.","supporting_citations":[],"review_version":1}