{"id":"c9f9df3e-ecef-4865-bf88-eee9c5647732","arxiv_id":"2507.12497","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"P-COQS builds differentially private conformal prediction sets by replacing the calibration quantile with a binary-search privatized quantile, yielding approximate coverage with a computable error bound.","lead":"This paper builds a privacy-preserving version of conformal prediction, a tool that lets AI models output a set of likely answers instead of a single guess. The new method, P-COQS, uses a private binary search on calibration scores, runs much faster than the leading alternative, and produces smaller prediction sets while keeping coverage close to the target.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Proposition 1's rank-error guarantee is not established: per-query count-error bounds do not imply final quantile rank error τ; small errors can push the binary search across a score gap, and Theorem 2 inherits the gap.","rationale":"The reader's weakest assumption is exactly the rank-error transfer, and my reading agrees: Proposition 1's proof establishes at most a high-probability bound on each count query; it does not establish the final quantile rank error. The two-point score configuration shows this is not a pedantic gap: small count errors can flip a decision at a dense side of the data, and binary search can then terminate on the wrong side of a large gap, producing rank error proportional to the gap size. The proposed experiment directly tests whether the violation probability exceeds the β budget. If it does, the central coverage theorem is unsupported and the headline comparison to ExponQ rests on an unproven guarantee. I also note the paper's claimed exact equivalence between pure ε-DP and ε-zCDP is not correct as stated, but the rank-error transfer is the more fundamental issue because it affects the method's own guarantee rather than only the baseline calibration. If the proposed test confirms the failure, the manuscript should be rejected or require a substantially revised algorithm and proof; if it does not, the missing proof still needs to be supplied.","tokens_in":21249,"tokens_out":24801,"duration_ms":316668,"concrete_test":"Run Algorithm 1 with ncal=3000, r=2700, scores 0^2700 followed by 0.9^300, a=0, b=1, δ=1e-10, ρ=100, β=0.01; Proposition 1 gives τ≈5.5. Take 10^5 independent noise draws; in each draw record qDP and the rank #{s_i ≤ qDP}. Compute the empirical probability P(|rank-r| > τ). If it exceeds 0.01, Proposition 1 and the Theorem 2 bounds fail as stated. For a baseline, repeat with uniform scores s_i=i/(ncal+1); the baseline should show the method near its target and isolates the effect of the score gap.","verdict_should_be":"REJECT","load_bearing_attack":"Proposition 1 is the load-bearing step: its rank-error statement is what Theorem 2 converts into coverage bounds. The proof bounds each noisy count by τ and then unions over N calls, but it never proves that a binary search with per-query errors τ returns a final midpoint whose rank is within τ of r. The implication is false. For example, take ncal=3000, r=2700 (α=0.1), 2700 scores at 0 and 300 scores at 0.9, a=0, b=1. A negative query error at the root (true count r, noisy count r-1) sends the search to the right half; a few more negative errors on queries below 0.9 drive the interval close to 0.9, and the final midpoint can land just above 0.9. Then all 3000 scores are at or below qDP, so the rank error is 300, while every query deviation can be far below the τ≈5.5 given by the formula for ρ=100, β=0.01. The union bound cannot distinguish this bad run from a good one. Separately, Theorem 2 states deterministic coverage inequalities, but Proposition 1 only holds on an event of probability 1-β; the theorem silently drops this conditioning. The missing transfer from count errors to final rank error is exactly the weakest point identified by the reader.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes P-COQS, a differentially private conformal prediction method that computes the calibration quantile with an adaptation of Huang et al.'s binary search with noisy range counts. The authors state a zCDP guarantee and a rank-error bound (Proposition 1), derive approximate coverage bounds for the resulting prediction sets (Theorem 2), and compare P-COQS with the exponential-mechanism method of Angelopoulos et al. on simulated and benchmark data.","tokens_in":21536,"tokens_out":13646,"duration_ms":164100,"significance":"If the theoretical results were valid, P-COQS would be a valuable contribution: it has a simple zCDP composition argument, a fixed number of binary-search iterations, and the experiments suggest smaller and more informative prediction sets than ExponQ while empirically staying near the target coverage. The paper also provides a useful template for deriving approximate coverage bounds from a DP quantile subroutine. Unfortunately, the load-bearing rank-error transfer is false as stated, and the privacy-budget equivalence used to compare with ExponQ is incorrect; the main theoretical and comparative claims therefore need substantial reworking.","major_comments":[{"comment":"The proof of Proposition 1 bounds the deviation of each noisy count by tau and takes a union bound over the N calls, but it never proves that a binary search in which every query has error at most tau returns a midpoint whose rank is within tau of r. The implication is false for continuous scores with ties. For example, with ncal=3000, alpha=0.1 (so r=2700), 2700 scores equal to 0 and 300 scores equal to 0.9, a=0, b=1, delta=10^-10, rho=100 and beta=0.01, we have N=34 and tau is approximately 1.7. Suppose every noisy count equals the true count minus 1; each per-query error is 1<tau, yet queries below 0.9 return 2699<r and move the left endpoint upward, while queries above 0.9 return 2999>=r and move the right endpoint downward. The final midpoint can then lie just above 0.9 with positive probability, in which case all 3000 scores are at or below qDP and the rank error is 300. Thus Proposition 1's rank-error statement is not merely unproved; it is false.","section":"Section 4, Proposition 1"},{"comment":"Theorem 2 is stated as a deterministic coverage inequality, but Proposition 1 guarantees the rank-error bound only on an event of probability at least 1-beta. The proof silently conditions on that event, and the line 'by Proposition 1 we have that Algorithm 1 outputs a private quantile qDP with rank error tau ensuring that sr-tau <= sr <= sr+tau' does not make sense as written. A correct statement would have to condition explicitly on the good-noise event and would carry an additional beta term for the failure event. As it stands, the theorem overstates the guarantee, and the subsequent discussion and Remark 2 treat the bounds as unconditional.","section":"Section 4, Theorem 2"},{"comment":"The assertion that a mechanism satisfies (epsilon,0)-DP if and only if it satisfies epsilon-zCDP is incorrect. The standard relationship is that pure epsilon-DP implies (epsilon^2/2)-zCDP, and rho-zCDP implies approximate (epsilon,delta)-DP with epsilon = rho + 2*sqrt(rho log(1/delta)). Because ExponQ is pure epsilon-DP and P-COQS uses Gaussian noise analyzed in rho-zCDP, fixing epsilon_CP in Tables 1-4 and in the benchmark experiments does not hold the two methods to the same privacy guarantee. The comparative privacy-utility claims and the numerical example in Remark 2 therefore rest on an invalid equivalence.","section":"Section 3.2 and Section 5"}],"minor_comments":[{"comment":"The notation u = b-a/delta should be u = (b-a)/delta; as written, the formulas for N and tau are ambiguous and can be negative for small delta.","section":"Section 4, Equation (2) and surrounding text"},{"comment":"The tail bound is written with 'tau >= sigma sqrt(2 ln(2N/beta))' but Proposition 1 then treats tau as a fixed value; the proof should clarify whether tau is an upper bound or an equality for the reported numbers.","section":"Section 4, Proof of Proposition 1"},{"comment":"The expression 'sr-tau <= sr <= sr+tau' is nonsensical; the intended statement is presumably about the rank of qDP among the sorted scores, and it should be written correctly.","section":"Section 4, Proof of Theorem 2"},{"comment":"The text defines ceil(v) as 'the smallest integer greater than x'; this should be 'greater than or equal to x'.","section":"Section 3.1"},{"comment":"There are several typos and garbled phrases, including 'respresents', 'prediciton', 'non-comformity', and 'Hence, the latter implies the former' in Section 3.2, which should be corrected.","section":"Throughout"}],"recommendation":"reject","confidential_remarks":"The central rank-error proposition is false as stated, and the DP-to-zCDP conversion used for all experimental comparisons is wrong. These are load-bearing issues that cannot be repaired with local edits; a resubmission would need a redesigned algorithm or a genuinely different utility argument, as well as a reworked privacy-budget comparison."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"First, the thing to know: adapting Huang et al.'s binary search for DP quantiles to continuous conformity scores is a reasonable idea, and the empirical section is genuinely useful. But the theoretical foundation does not hold as written. Proposition 1 does not establish a rank error τ for the output quantile. The union bound controls each noisy count individually, but binary search decisions can accumulate errors. A few negative count errors at midpoints just below a cluster of large scores push the interval past the cluster, and the final midpoint can have rank error far larger than τ. The stress-test example is correct: with 2700 scores at 0, 300 at 0.9, and r=2700, per-query noise of a few can land the output near 0.9, putting all 3000 scores at or below it. Since Theorem 2 leans entirely on Proposition 1's rank error, the coverage guarantee is unsupported. Theorem 2 also drops the conditioning: Proposition 1 holds with probability at least 1−β, but the theorem states unconditional deterministic bounds.\n\nThe second problem is the claimed exact equivalence between pure ε-DP and ε-zCDP. That is wrong. Pure ε-DP implies (ε²/2)-zCDP, not ε-zCDP. Using the same numeric budget for ExponQ (ε) and P-COQS (ρ) gives P-COQS a weaker privacy guarantee, so the empirical comparison is not privacy-matched.\n\nWhat the paper does well: the experiments are broad—simulations plus CIFAR-10, ImageNet, CoronaHack—and show P-COQS is fast (tens of iterations vs. ExponQ's optimization overhead) and often delivers tighter sets. The adaptation is clear. But no code is released, which hurts reproducibility.\n\nThis paper is for people working on differentially private conformal prediction. The method has potential, but the gap between the headline claims and what is proven is large. The authors would need a real analysis converting per-query noise into rank error, or a different mechanism with a provable rank guarantee, plus a correct privacy accounting, plus code, before the central claims can stand.\n\nRecommendation: send it to peer review, because the question is worthwhile and the flaws are not beyond repair, but ask for a major revision. A referee should insist on a correct proof of Proposition 1 and a fair privacy comparison.","headline":"The core idea has merit, but the central privacy-utility guarantee and the empirical comparison rest on two unproven steps; the paper needs major theoretical repair.","tokens_in":22058,"tokens_out":6313,"would_cite":false,"duration_ms":77289,"reading_group":"maybe","serious_thinker":"no","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims that conformal prediction can be made differentially private by reading off the calibration quantile from a noisy binary search instead of sorting the scores.","keywords":["differential privacy","conformal prediction","zero-concentrated differential privacy","private quantile estimation","randomized binary search","prediction sets","uncertainty quantification","calibrated nonconformity scores"],"falsifier":"Take the paper's own worked example, scores on $[0,1]$, $\\delta = 10^{-10}$, $\\rho = 0.1$, $\\beta = 0.01$, $n_{\\mathrm{cal}} = 3000$, $\\alpha = 0.1$, and run P-COQS many times on simulated scores from a known distribution. The paper claims coverage between roughly $0.885$ and $0.915$ with probability at least $0.99$; check whether the empirical coverage across runs violates that band more often than $\\beta$, and whether the released quantile's rank error exceeds $\\tau \\approx 45$ more often than $1\\%$ of runs. A systematic violation would show that the rank-error bound has not transferred to the continuous-score binary search, and Theorem 2 would not hold as stated.","tokens_in":21026,"feed_emoji":"🔒","tokens_out":13408,"duration_ms":138461,"temperature":0.7,"pith_summary":"This paper claims that conformal prediction can be made differentially private without inflating the reported quantile: instead of sorting the calibration scores and adding noise that must be corrected upward, one runs a noisy binary search on the score interval and releases the midpoint it converges to. The resulting procedure, P-COQS, is $\\rho$-zCDP because the Gaussian noise added to each range count is scaled to the number of search iterations. The paper's main theoretical result, Theorem 2, bounds the coverage of the resulting prediction sets between $1-\\alpha-\\tau/(n_{\\mathrm{cal}}+1)$ and $1-\\alpha+(\\tau+1)/(n_{\\mathrm{cal}}+1)$, where $\\tau$ is the rank error of the private quantile, which holds with probability at least $1-\\beta$. If those guarantees hold, privacy-protected uncertainty sets can be produced in tens of binary-search iterations, at empirical coverage close to the nominal $1-\\alpha$ level, with smaller sets than the leading exponential-mechanism alternative.","feed_headline":"Private prediction sets shrink with a noisy binary search","feed_subtitle":"Private binary search on calibration scores gives near-target coverage with smaller sets than inflation-based methods.","key_machinery":"The load-bearing object is the noisy range-count oracle $\\mathrm{NoisyRC}([a,\\mathrm{mid}], S)$ inside Algorithm 1, a fixed-iteration binary search over the score interval $[a,b]$ that replaces each exact count of calibration scores below a midpoint with a Gaussian-perturbed count of variance $\\lceil\\log_2((b-a)/\\delta)\\rceil/(2\\rho)$. The variance is scaled to the number of search iterations so that, by sequential composition of zero-concentrated differential privacy, the entire search, and therefore the released quantile $q_{\\mathrm{DP}}$ used as the conformal threshold, satisfies $\\rho$-zCDP. The second ingredient is the rank error $\\tau$ of Proposition 1, which is the quantity that carries the utility analysis: it measures, with probability at least $1-\\beta$, how far the private quantile's rank can sit from the target rank $r = \\lceil (1-\\alpha)(n_{\\mathrm{cal}}+1) \\rceil$, and it is exactly the term that appears in both coverage bounds of Theorem 2.","core_discovery":"Stated on the paper's own terms: the randomized binary-search quantile method of the prior work the paper adapts carries over to continuous nonconformity scores, and that carry-over is enough to make conformal prediction private. Algorithm 1 narrows an interval $[a,b]$ on the score scale, and at each midpoint calls a noisy range count $\\mathrm{NoisyRC}([a,\\mathrm{mid}], S) = \\mathrm{card}(S\\cap[a,\\mathrm{mid}]) + \\mathcal{N}\\bigl(0, \\lceil\\log_2((b-a)/\\delta)\\rceil/(2\\rho)\\bigr)$. Since each count has $\\ell^1$-sensitivity $1$ and there are $N = \\lceil\\log_2((b-a)/\\delta)\\rceil$ iterations, composition of zero-concentrated differential privacy makes the whole search $\\rho$-zCDP; Proposition 1 then asserts that the returned midpoint has rank error $\\tau = \\sqrt{\\lceil\\log_2 u\\rceil/\\rho \\cdot \\log(2\\lceil\\log_2 u\\rceil/\\beta)}$ with probability at least $1-\\beta$, where $u = (b-a)/\\delta$. Theorem 2 converts that rank error into two-sided coverage bounds for the prediction set $\\{Y : s(X_{\\mathrm{test}},Y,\\hat{f}) \\le q_{\\mathrm{DP}}\\}$, trading the exact $\\ge 1-\\alpha$ guarantee of non-private conformal prediction for a quantifiable approximation. The empirical claim that motivates the trade is that the method targets the nominal coverage across simulations, CIFAR-10, ImageNet, and CoronaHack while returning prediction sets that are smaller than the current private alternative.","pith_inferences":["Because the only data-touching component is the noisy count oracle, a natural extension is to swap that oracle for a local-DP or distributed count mechanism, which would extend private conformal prediction to federated calibration without re-deriving the coverage argument.","The two-sided coverage bound means a practitioner can detect wasteful over-coverage as well as under-coverage; the paper does not emphasize this, but the bound could be used as a diagnostic for automatic privacy-budget allocation across multiple calibration searches.","The rank error $\\tau$ grows with the size of the score interval $[a,b]$, so clipping nonconformity scores to tighter bounds before the search would buy accuracy for free, a cheap modification the experiments do not explore.","The simulation evidence points to a small-sample regime (calibration sizes around $n \\le 200$ with a DP-trained model) where P-COQS visibly under-covers; a hybrid that applies a small fixed inflation to the private quantile only in that regime would trade a little efficiency for the guaranteed lower bound."],"forward_implications":["Releasing prediction sets through P-COQS carries $\\rho$-zCDP with no additional privacy cost beyond the calibration-quantile search itself, since the prediction set is a post-processing of the private quantile.","Users can compute explicit coverage bounds for their own settings: with probability at least $1-\\beta$, the true coverage lies between $1-\\alpha-\\tau/(n_{\\mathrm{cal}}+1)$ and $1-\\alpha+(\\tau+1)/(n_{\\mathrm{cal}}+1)$, so the worst-case coverage loss is known in advance rather than hidden behind an inflation hyperparameter.","The search runs in $N = \\lceil \\log_2((b-a)/\\delta)\\rceil$ iterations, which in the paper's benchmarks reduces conformal-prediction runtime by roughly two orders of magnitude relative to the binning-and-inflation alternative.","Because no quantile inflation is applied, prediction sets come out smaller: across simulations, CIFAR-10, ImageNet, and CoronaHack, the paper reports average set sizes closer to the non-private conformal baseline while empirical coverage targets $1-\\alpha$.","Coverage slack $\\tau/(n_{\\mathrm{cal}}+1)$ shrinks as calibration size and privacy budget $\\rho$ grow, so the approximate guarantee tightens exactly in the regimes where private conformal prediction is most useful."],"supporting_citations":[{"why":"Supplies the PrivQuant randomized binary-search quantile algorithm that Algorithm 1 adapts to continuous scores, including the rank-error bound that Proposition 1 transfers.","marker":"(Huang et al., 2021)"},{"why":"The private conformal prediction baseline (ExponQ) and the experimental protocol that the paper replicates; it also frames the calibration-data privacy problem P-COQS addresses.","marker":"(Angelopoulos et al., 2022)"},{"why":"Defines zero-concentrated differential privacy and the sequential composition property used to scale the per-iteration noise into the $\\rho$-zCDP guarantee of Algorithm 1.","marker":"(Bun and Steinke, 2016)"},{"why":"Establishes the conformal prediction framework and the exchangeability-based coverage argument on which Theorem 2 builds.","marker":"(Vovk et al., 2005)"},{"why":"The split-conformal calibration construction, with a held-out calibration set and a quantile of nonconformity scores, that P-COQS embeds the private search into.","marker":"(Lei et al., 2015)"},{"why":"Provides the zCDP-to-$(\\epsilon,\\delta)$-DP conversion used in the experiments to compare P-COQS and ExponQ under identical privacy guarantees.","marker":"(Near and Abuah, 2021)"},{"why":"The exponential mechanism that underlies the ExponQ baseline, making the comparison in the experiments possible.","marker":"(McSherry and Talwar, 2007)"}],"fun_headline_variants":["Private binary search shrinks conformal prediction sets","DP conformal: noise in the search, smaller sets out","Private quantile search: coverage targeted, sets minimized","Slight under-coverage, much smaller private sets","Noisy quantiles: private conformal sets with less waste"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The entire coverage guarantee rests on one carried-over step: the claim that the noisy binary search returns a quantile whose rank is within $\\tau$ of the target rank, which the paper's Proposition 1 asserts from the integer-domain algorithm it adapts, bounding the noise in each individual count without showing that the search decisions confine the final midpoint to that rank error.","fun_headline_variants_meta":{"raw":{"variants":["Private binary search shrinks conformal prediction sets","DP conformal: noise in the search, smaller sets out","Private quantile search: coverage targeted, sets minimized","Slight under-coverage, much smaller private sets","Noisy quantiles: private conformal sets with less waste"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000979,"raw_usage":{"total_tokens":4277,"prompt_tokens":1182,"completion_tokens":3095,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":798,"completion_tokens_details":{"reasoning_tokens":3016}},"tokens_in":798,"tokens_out":3095,"duration_ms":29879,"temperature":1.0,"reasoning_tokens":3016,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-06T17:04:34.256029+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Take the paper's own worked example, scores on $[0,1]$, $\\delta = 10^{-10}$, $\\rho = 0.1$, $\\beta = 0.01$, $n_{\\mathrm{cal}} = 3000$, $\\alpha = 0.1$, and run P-COQS many times on simulated scores from a known distribution. The paper claims coverage between roughly $0.885$ and $0.915$ with probability at least $0.99$; check whether the empirical coverage across runs violates that band more often than $\\beta$, and whether the released quantile's rank error exceeds $\\tau \\approx 45$ more often than $1\\%$ of runs. A systematic violation would show that the rank-error bound has not transferred to the continuous-score binary search, and Theorem 2 would not hold as stated.","supporting_citations":[],"review_version":1}