{"id":"fb22bc5f-262f-4146-ade0-a7ea9c1431f3","arxiv_id":"2506.05497","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":5,"one_line_summary":"CPQ builds conformal prediction sets for black-box LLMs by stopping queries when the estimated missing-mass derivative is small and thresholding a Good-Turing based score, with a fallback EE label for unseen correct answers.","lead":"This paper introduces CPQ, a conformal prediction method for black-box generative models where prediction sets are built from a limited number of queried samples. It connects the problem to the classical missing mass, proposes a query-stopping rule based on a new derivative estimator, and reports lower fallback-set usage than two LLM conformal baselines.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3.2's optimality claim is false: thresholding the proposed score cannot express the optimal set even when the large-λ ordering condition holds.","rationale":"The central claim is the optimal set mapping and query policy; Theorem 3.2 is the basis for the score used in Algorithm 1. The reader correctly identifies that the score ignores λ unless a large-λ condition is imposed. My stress-test shows the problem is even more fundamental: the theorem fails on a finite deterministic counterexample that satisfies the reader's large-λ ordering condition, because the proof's LP relaxation is not equivalent to the original integer set-selection problem. Thus the theorem is false as stated, not merely incomplete. The finite-sample coverage guarantee in Theorem 4.1 relies only on exchangeability and is unaffected, so the algorithm likely remains coverage-valid but loses its advertised optimality. The empirical results may still show practical gains, but they cannot justify the optimality principle. The paper should either derive a correct score that depends explicitly on λ and prove the threshold form, or present the method as a valid heuristic. This supports the existing REJECT verdict.","tokens_in":1027,"tokens_out":1451,"duration_ms":175643,"concrete_test":"Enumerate the single-input instance above and compare the optimum of (4) with every threshold set generated by S(x,y) from Theorem 3.2. If, as computed, the optimum {EE,A} is not reproducible by any q*, Theorem 3.2 is refuted. Also solve the LP relaxation (7) on the same instance to verify that its optimum uses a fractional EE mass, confirming the relaxation gap. This requires only hand enumeration or a small LP solver and directly settles the concern.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The reader's diagnosis is correct but the failure is deeper. Appendix A.2 relaxes (4) to an LP, invokes Neyman-Pearson, and asserts integrality by assuming no ties. That equivalence fails even when the large-λ condition holds. Concrete counterexample: one input x, seen labels A and B, λ=100, α=0.1, p(A)=0.15, p(B)=0.05, p(EE)=0.8. Feasible sets and costs: {} cost 0, {A} cost 1, {B} cost 1, {A,B} cost 2, {EE} cost 100, {EE,A} cost 101 (coverage 0.95), {EE,A,B} cost 102. Only {EE,A} and {EE,A,B} meet the 0.9 coverage requirement, so the optimum is {EE,A} with cost 101. The theorem's score gives S(A)=0.85, S(B)=0.95, S(EE)=1.20; thresholding yields only {A}, {A,B}, or {A,B,EE}, never {EE,A}. The ordering condition p(B)=0.05 > p(EE)/λ=0.008 holds, so the theorem is false as stated even under the proposed sufficient condition. The LP relaxation is not equivalent to the integer problem; the optimal set map need not be a threshold rule. Since Algorithm 1 uses this score, the paper's central optimal-mapping claim is unsupported.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces CPQ, a conformal prediction framework for black-box generative models in a query-only setting. It formalizes an optimization problem over a query policy T and a set map f that balances coverage, informativeness, and query budget, with a special fallback label EE representing the unseen remainder of the label space. The paper derives two principles: the optimal query policy is characterized by a threshold on the missing-mass derivative, and the optimal set map is claimed to be a threshold rule on a conformity score involving the missing mass. A finite-sample algorithm is then proposed, using Good–Turing estimators for the missing mass and its derivative, together with split conformal calibration. Experiments on three open-ended LLM tasks compare CPQ with CLM and SCOPE-Gen, reporting lower EE fractions at matched query budgets.","tokens_in":23815,"tokens_out":7546,"duration_ms":100093,"significance":"If the optimality results were correct, this would be a valuable contribution: it would provide the first principled treatment of the coverage–informativeness–query-budget trade-off for generative models, with a clean connection to the classical missing-mass problem. The paper does have credible elements: the split-conformal coverage argument in Theorem 4.1 is standard and appears valid; the Good–Turing-based derivative estimator -2N_2/t^2 is a clean derivation; and the empirical comparison is systematic, with released code. However, the central optimal-mapping theorem, Theorem 3.2, is false as stated, and the finite-sample algorithm inherits the flaw. Since the advertised optimality is the main scientific claim of the paper, the contribution is not established despite the valid coverage guarantee.","major_comments":[{"comment":"Theorem 3.2 is false as stated. Consider a single input x with seen labels A and B, p(A)=0.15, p(B)=0.05, p(EE)=0.8, λ=100, and α=0.1. The feasible sets and costs are: {} cost 0, {A} cost 1, {B} cost 1, {A,B} cost 2, {EE} cost 100, {EE,A} cost 101, and {EE,A,B} cost 102; {EE,B} has coverage 0.85 and is infeasible. The optimum is {EE,A}. The score in Eq. (5) gives S(A)=0.85, S(B)=0.95, and S(EE)=1.20, so thresholding yields only {A}, {A,B}, or {A,B,EE}; it can never produce {EE,A}. This example also satisfies the large-λ ordering condition p(B)=0.05 > p(EE)/λ=0.008, so adding that condition to the theorem does not rescue it. Additionally, Appendix A.2 requires 1-p(EE|x)/λ > 1-p(y|x) for every seen label y, equivalently p(y|x)>p(EE|x)/λ, which is not stated in the theorem and need not hold when a seen label has very small probability.","section":"§3.2, Theorem 3.2, Eq. (5)"},{"comment":"The LP relaxation argument is invalid. The Neyman-Pearson reasoning applied to the relaxed problem (7) identifies an optimal fractional solution by benefit-to-cost ratios, but with a single coverage constraint the LP optimum generally requires a fractional final item, and its value can be strictly below the integer optimum. In the counterexample above, the LP selects A and B in full and a fraction 0.875 of EE, giving cost 2+87.5=89.5, which is cheaper than the integer optimum {EE,A} at cost 101 and is not an integer solution. Therefore the claimed equivalence between the relaxed problem (7) and the original integer problem (6) does not follow, and the conclusion that the optimal set map is a threshold rule does not follow.","section":"Appendix A.2, Eq. (7)"},{"comment":"Because Algorithm 1 constructs sets by thresholding the estimated score S with EE scored after every seen label, it cannot realize the optimal set map in the counterexample: including EE forces inclusion of all seen labels with score below the EE score, so it cannot output {EE,A} while excluding B. The paper's central claims of optimality — in the abstract, Section 3, and Section 5 — are therefore unsupported. Theorem 4.1 remains a valid split-conformal coverage guarantee for any score function, but it does not establish that CPQ optimally balances EE usage and set size.","section":"Abstract, §4, Algorithm 1"}],"minor_comments":[{"comment":"The theorem statement writes Δ(x,T*(x)-1), which is undefined when T*(x)=0; the corner case T*(x)=0 when Δ(x,0)≤β* is only discussed in the proof and should be included in the theorem statement.","section":"§3.1, Theorem 3.1"},{"comment":"There are several typos and inconsistencies: 'open-eneded', 'Datsets', 'out method', and 'compares' should be corrected; the method name is written as both SCOPE-Gen and Scope-Gen.","section":"§5, §6"},{"comment":"The clustering section says that cluster frequencies are scaled to form a valid probability distribution over seen and unseen clusters, but the precise scaling procedure is not specified; this is important because the missing-mass estimates and scores depend on these probabilities.","section":"§5, Clustering"},{"comment":"The claim that CPQ is constrained to the lowest average query budget used by the baselines is favorable to CPQ and should be justified or relaxed in the main text; the reader currently has to infer this from the appendix.","section":"Table 2"}],"recommendation":"reject","confidential_remarks":"The false Theorem 3.2 is load-bearing: the paper's advertised optimality of the set map is directly contradicted by a simple one-input counterexample, and the LP-relaxation proof does not fill the gap. The valid coverage theorem and the empirical comparisons are not enough to compensate for the failure of the main theoretical claim, and I do not see a local repair within the current framework."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things to know. First, the missing-mass framing for query-based conformal prediction is genuinely new and worth thinking about. Second, the paper's headline optimality result, Theorem 3.2, is false as stated, and the stress-test counterexample is correct: even when the large-λ ordering condition holds, thresholding the proposed score cannot express the optimal set map. The proof's LP-relaxation step is where it breaks; the relaxed problem is not equivalent to the integer problem, and the claim that Neyman-Pearson gives an integral solution is not valid here. This is load-bearing because the abstract and introduction sell the optimal set map as one of the two core algorithmic principles.\n\nWhat the paper does well: the connection between query stopping and the derivative of missing mass is a nice idea, and the estimator -2N2/t^2 is new, with synthetic experiments showing it tracks the true derivative more stably than naive finite differences. The finite-sample algorithm, combining Good-Turing missing-mass estimates with split conformal calibration, is plausible, and Theorem 4.1's coverage guarantee is standard and sound. The empirical comparison against CLM and SCOPE-Gen shows consistently lower EE fractions, which supports the practical promise of the approach even if the optimality story is wrong.\n\nSoft spots beyond the main error: the derivative estimator is heuristic; the derivation in Appendix C.1 relies on an approximation that is not quantified. The experiments use only two of the cited conformal baselines, omitting GPS and APIisEnough, which weakens the claim of significant gains over existing methods. The clustering procedure via LLaMA entailment is an extra source of noise, though the paper is transparent about it and the method is modular. I also think the authors' own limitation statement about noisy estimates in low-query regimes is fair and not a fatal issue.\n\nMy overall read: the coverage guarantee is solid, the framework is novel, and the empirical recipe is credible, but the central optimality theorem is unsupported. This is not a desk-reject-and-forget paper. The authors could fix it by using the correct score that involves λ, as your note suggests, or by honestly reframing the method as a heuristic with valid coverage and no optimality claim. I would send it to peer review with a clear expectation of major revision, because the kernel of a useful contribution is here and a good referee could help shape the revision.\n\nRecommendation: engage with it, but require the optimality claim to be either fixed or explicitly dropped before publication.","headline":"Novel missing-mass framework for query-based conformal prediction, but the central optimality theorem is false as stated and the method currently rests on a heuristic with only a coverage guarantee.","tokens_in":24381,"tokens_out":2538,"would_cite":false,"duration_ms":33443,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"For black-box generative models, conformal coverage can be built from sampling alone: the optimal query-stopping rule and the optimal prediction-set rule are both governed by the missing mass, the probability that the correct output has…","keywords":["conformal prediction","uncertainty quantification","missing mass","Good-Turing estimation","generative models","large language models","query oracle","prediction sets"],"falsifier":"Construct a synthetic label distribution over, say, 100 labels in which one label has probability strictly below $p(\\mathrm{EE}|x)/\\lambda$ while the rest are uniform, solve the constrained set-selection problem exactly with a Neyman-Pearson allocation, and compare with the paper's score threshold: the two rules must differ precisely on that rare seen label, showing the claimed optimal structure fails there. A second check is to compute the empirical EE fraction at the budgets used in the paper ($B = 7$ to $40$) and see whether any coverage level produces sets whose composition contradicts the threshold rule.","tokens_in":23288,"feed_emoji":"🎲","tokens_out":13946,"duration_ms":147745,"temperature":0.7,"pith_summary":"This paper works out how to do conformal prediction for generative models when the only access to the model is a query oracle: you can draw samples, but there are no logits, no geometric distances, and no structured label space to threshold. The central claim is that both decisions in such a pipeline — how many times to query each input, and which sampled outputs to place in the prediction set — are governed by a single classical quantity, the missing mass, defined as the probability that the correct output has not appeared among the samples drawn so far. The paper proves that an optimal query policy stops when the rate at which missing mass shrinks falls below a common threshold, and that an optimal prediction set is obtained by thresholding a score in which a special 'Everything Else' label carries the missing mass itself. These two principles are assembled into a finite-sample algorithm with distribution-free coverage guarantees, and on open-ended LLM tasks the algorithm produces far more informative prediction sets — far fewer unnecessary 'Everything Else' fallbacks — than existing conformal language-model methods at the same coverage and query budget. If the argument holds, any black-box generative model with a sampling interface gets principled uncertainty quantification with an explicit test-time query budget.","feed_headline":"Missing mass makes LLM prediction sets cover the unseen","feed_subtitle":"A conformal method for black-box generative models keeps coverage valid at any level without wasting queries.","key_machinery":"The load-bearing object is the missing mass $\\theta(x,t) = \\Pr[Y \\notin Z_t(x) \\mid X=x]$, the probability that $t$ independent queries at input $x$ have not produced the true label, together with its discrete derivative $\\Delta(x,t) = \\theta(x,t+1) - \\theta(x,t)$, which is negative and non-decreasing in $t$ — the diminishing-returns property that makes thresholding meaningful. Around it the paper builds three further pieces: the abstract label $\\mathrm{EE}$ ('Everything Else') representing $Y \\setminus Z(x)$, whose inclusion guarantees coverage but costs informativeness and is penalized by $\\lambda$; the conformity score with $S(x,y) = 1 - p(y|x)$ on seen labels and $S(x,\\mathrm{EE}) = 2 - p(\\mathrm{EE}|x)$ on the unseen remainder; and a Neyman-Pearson benefit-to-cost argument that converts the constrained set-selection problem into this threshold rule. In the finite-sample algorithm, $p(\\mathrm{EE}|x)$ is estimated by the Good-Turing singleton count $N_1/t$ and $\\Delta$ by the new doubleton estimator $-2N_2/t^2$, with the threshold $\\beta^*$ tuned to satisfy the query budget and $q^*$ set by split-conformal calibration.","core_discovery":"In the population regime where the query oracle matches the true conditional distribution, the paper establishes two structural results. First, with a fixed expected query budget, the expected missing mass $\\mathbb{E}_X[\\theta(X,T(X))]$ is minimized by a threshold rule on the discrete derivative $\\Delta(x,t) = \\theta(x,t+1) - \\theta(x,t)$: there is a single threshold $\\beta^*$ such that the optimal number of queries for input $x$ is the first $t$ where an additional draw stops reducing missing mass enough. Second, with the penalty $\\lambda$ on the fallback label sufficiently large, the optimal set map is a threshold on the conformity score $S(x,y) = 1 - p(y|x)$ for sampled labels and $S(x,\\mathrm{EE}) = 2 - p(\\mathrm{EE}|x)$ for the abstract 'Everything Else' label, where $p(\\mathrm{EE}|x)$ is exactly the missing mass; this reduces to the classical thresholding of $1 - p(y|x)$ when nothing is missing. The finite-sample algorithm replaces these population quantities with estimates — the Good-Turing count of singletons $N_1/t$ for the missing mass, and a newly derived doubleton estimator $-2N_2/t^2$ for its derivative — then calibrates the score threshold $q^*$ by split conformal quantiles, which gives distribution-free coverage even when the oracle differs from the truth. Taken together, the two results claim a query-based conformal method that is simultaneously optimal in its use of the query budget, its avoidance of uninformative fallbacks, and its set sizes, for any black-box generative model.","pith_inferences":["The doubleton estimator $-2N_2/t^2$ is a cheap, logit-free stopping signal that could transfer to other sampling pipelines — for instance deciding when to stop drawing responses for semantic-entropy or self-consistency checks in LLM systems, where stopping rules are currently heuristic.","Because the coverage proof only needs exchangeability of scores and never uses $\\pi \\equiv p$, the two-module design should tolerate mismatch between the query oracle and the calibration distribution; an explicit synthetic-shift experiment would test how much drift the $\\mathrm{EE}$ fallback absorbs.","The authors decouple the query policy from the set map and note this only approximates the joint optimum; an ablation that alternates the two optimization stages could quantify how much of the reported informativeness gain comes from the coupling they left out."],"forward_implications":["Any black-box generative model that can be sampled — with no logits, token probabilities, or internal scores — can be wrapped in a distribution-free coverage guarantee at any user-chosen level, including levels above the model's own few-shot accuracy.","The query budget becomes an explicit, tunable knob: calibrating $\\beta^*$ fixes the expected number of queries per input, so coverage, informativeness, and cost are set by the scalars $\\alpha$, $\\beta^*$, and $\\lambda$ independently.","At matched coverage and matched query budget, CPQ needs the 'Everything Else' fallback far less often than conformal language modelling baselines: on GSM8K at 95% nominal coverage, about 16% of CPQ sets contain $\\mathrm{EE}$, versus roughly 70% for CLM and 61% for SCOPE-Gen.","The optimal-score structure extends the classical result that minimal conformal sets threshold $1 - p(y|x)$: in an effectively infinite label space the missing mass enters through a single extra score value assigned to the unseen remainder.","A principled stopping rule replaces fixed per-input sample counts: querying continues exactly while an additional draw still reduces the estimated missing mass at a rate above the calibrated threshold."],"supporting_citations":[{"why":"Supplies the split-conformal exchangeability argument that grounds the distribution-free coverage guarantee of Theorem 4.1.","marker":"[7]"},{"why":"The conformal language modeling baseline that CPQ extends; its stopping-rule framing is the setting CPQ re-derives from missing mass, and it is the main experimental comparison.","marker":"[13]"},{"why":"The sequential greedy-filtering variant (SCOPE-Gen) used as the second baseline in the query-budget-matched comparisons.","marker":"[14]"},{"why":"Establishes that Good-Turing-style probability estimation is asymptotically optimal, justifying the missing-mass estimate that defines the EE score.","marker":"[18]"},{"why":"The classical result that optimal conformal sets threshold $1-p(y|x)$; Theorem 3.2 presents the missing-mass score as its generalization to infinite label spaces.","marker":"[32]"},{"why":"Good's original estimator of the probability of unseen species, the source of the singleton-based missing mass estimate $N_1/t$ used in the calibration module.","marker":"[58]"},{"why":"The Neyman-Pearson lemma, the benefit-to-cost selection argument at the heart of the proof that the optimal set map is a score threshold.","marker":"[68]"},{"why":"The infinite-dimensional optimization framework used to pass from the linear-program relaxation of the set-selection problem to the threshold solution.","marker":"[69]"},{"why":"The derivation of the Good-Turing estimator that the paper mirrors to obtain the novel missing-mass-derivative estimator $-2N_2/t^2$.","marker":"[70]"}],"fun_headline_variants":["Missing mass sets the optimal conformal query budget","Conformal sets that cover unseen outputs from black-box LLMs","Good-Turing powers conformal prediction for generative AI","Query-only conformal prediction leverages missing mass"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"Everything rests on the rule that places the 'Everything Else' label after all sampled answers being optimal, which the proof needs the penalty weight $\\lambda$ to be large enough that every sampled answer is more probable than the missing mass divided by $\\lambda$; on real query distributions a sampled answer can be rarer than that fraction, and then the true optimum would rank the unseen remainder ahead of it.","fun_headline_variants_meta":{"raw":{"variants":["Missing mass sets the optimal conformal query budget","Conformal sets that cover unseen outputs from black-box LLMs","Good-Turing powers conformal prediction for generative AI","Query-only conformal prediction leverages missing mass"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000336,"raw_usage":{"total_tokens":1984,"prompt_tokens":1190,"completion_tokens":794,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":806,"completion_tokens_details":{"reasoning_tokens":732}},"tokens_in":806,"tokens_out":794,"duration_ms":10546,"temperature":1.0,"reasoning_tokens":732,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T10:21:25.929643+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Construct a synthetic label distribution over, say, 100 labels in which one label has probability strictly below $p(\\mathrm{EE}|x)/\\lambda$ while the rest are uniform, solve the constrained set-selection problem exactly with a Neyman-Pearson allocation, and compare with the paper's score threshold: the two rules must differ precisely on that rare seen label, showing the claimed optimal structure fails there. A second check is to compute the empirical EE fraction at the budgets used in the paper ($B = 7$ to $40$) and see whether any coverage level produces sets whose composition contradicts the threshold rule.","supporting_citations":[{"cited_title":"Springer, 2005","cited_arxiv_id":null,"evidence_quote":"Supplies the split-conformal exchangeability argument that grounds the distribution-free coverage guarantee of Theorem 4.1."},{"cited_title":"Jaakkola, and Regina Barzilay","cited_arxiv_id":null,"evidence_quote":"The conformal language modeling baseline that CPQ extends; its stopping-rule framing is the setting CPQ re-derives from missing mass, and it is the main experimental comparison."},{"cited_title":"Conformal generative modeling with improved sample efficiency through sequential greedy filtering, 2025","cited_arxiv_id":null,"evidence_quote":"The sequential greedy-filtering variant (SCOPE-Gen) used as the second baseline in the query-budget-matched comparisons."},{"cited_title":"Always good turing: Asymptotically optimal probability estimation.Science, 302(5644):427–431, 2003","cited_arxiv_id":null,"evidence_quote":"Establishes that Good-Turing-style probability estimation is asymptotically optimal, justifying the missing-mass estimate that defines the EE score."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Good's original estimator of the probability of unseen species, the source of the singleton-based missing mass estimate $N_1/t$ used in the calibration module."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The Neyman-Pearson lemma, the benefit-to-cost selection argument at the heart of the proof that the optimal set map is a score threshold."},{"cited_title":"John Wiley & Sons, 1969","cited_arxiv_id":null,"evidence_quote":"The infinite-dimensional optimization framework used to pass from the linear-program relaxation of the set-selection problem to the threshold solution."},{"cited_title":"Lecture 11: The good–turing estimate","cited_arxiv_id":null,"evidence_quote":"The derivation of the Good-Turing estimator that the paper mirrors to obtain the novel missing-mass-derivative estimator $-2N_2/t^2$."}],"review_version":1}