{"id":"66765a62-00b3-4bea-bc3b-0f4ef2838c63","arxiv_id":"2608.10893","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Under bounded-ratio covariate shift, a certified coverage floor creates a two-resource sample-complexity map, with a provable impossibility over the full unknown-weight class.","lead":"Selective prediction systems only answer a chosen subset of questions. This paper proves that, under covariate shift, certifying both a target error bound and a minimum proportion of answered questions splits the sample cost into labeled source data and unlabeled target data, and it gives matching impossibility and achievability results.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The implementable Model-B′ certificate's validity requires w to be exactly constant on the pre-registered K-partition; any off-partition variation leaves an unestimated bias, so the practical two-resource map is conditional on an untestable structural premise.","rationale":"I read the paper's central claim as a three-model statement: a Model-B lower bound, a Model-A oracle achievability, and a Model-B′ implementable upper bound. The first two stand on their stated assumptions, and the cross-model match is meaningful because Theorem 6 rules out an unrestricted single-model law. The load-bearing step for deployment is Claim 3. Theorem 2's validity literally requires w to be K-measurable; the proof's bias term E_P[(ŵ−w)Sλ(η−α)] has no control once w has within-cell variation. Remark 16 and §4.5 concede that the guarantee then degrades to a K-projection with an additive bias not estimable from covariates, and Appendix G.9 shows true violations can occur while the certificate's own statistics fire zero alarms. Because Theorem 6 shows no unknown-weight procedure can be consistent over WB, exact K-measurability is not a removable technical convenience but the price of the implementable guarantee; a practitioner cannot verify it from the certificate's outputs. This matches the reader's weakest-assumption identification. It does not invalidate the theorem-level map, but it keeps the practical certificate conditional, so the reader's CONDITIONAL verdict is appropriate; I would not move it to ACCEPT or REJECT.","tokens_in":61215,"tokens_out":11545,"duration_ms":135985,"concrete_test":"Run the released B′ kernel on a synthetic family in WB with a pre-registered K but w not K-measurable: within each cell set w(x) = 1 + γ sin(2πKx), normalized to mean 1, and choose η negatively correlated with w − E_K[w] inside the accepted region, at the deterministic split sizes of Theorem 3 (n_r, m_f, n_w, m_w). Sweep γ from 0 to 0.1 over ≥10^4 replications and record the violation rate among certified outputs. If any γ > 0 yields a >δ violation rate while Algorithm 1's internal statistics certify, then Assumption 1 is load-bearing; if violations remain ≤δ up to a quantified γ*, an approximate validity margin can be stated.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Claim 3 (Theorem 2) is the only deployable upper bound, and its validity proof controls weight-estimation bias via the identity E_P[ŵSλ(η−α)] = G_Q(λ) + E_P[(ŵ−w)Sλ(η−α)], bounding the second term by r_λ = E_P[|ŵ−w|S_λ] ≤ ρ_λ. The event r_λ ≤ ρ_λ holds under Assumption 1 because w is exactly K-measurable and the histogram error concentrates. If w is not K-measurable, r_λ is at least the projection gap ‖w − E[w|K]‖_{1,A_λ}, which can be O(1) while every observable test statistic stays inside its bounds. Remark 16 concedes this bias is not estimable from covariates alone, and Appendix G.9 exhibits a WB world in which the certificate's own statistics fire no alarms yet true violations occur once the receding frontier crosses the operating point. Theorem 6 shows this is not an accident: over the unrestricted bounded-ratio class no unknown-weight procedure is consistent, so the entire implementable claim rests on K-measurability. The paper scopes this explicitly, but the consequence is that the headline 'two-resource sample complexity map' is not a statement about a real shift unless w is exactly stratified; the practical half of the map is conditional and cannot be verified from the certificate's own outputs.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper considers selective predictors under bounded-ratio covariate shift, where a deployment operator requires a certificate that the selection-conditioned risk R_Q(λ)≤α and the coverage floor C_Q(λ)≥β hold simultaneously. The central result (Theorem 1) is the Floor Certification Map: in the local regime defined by a regular frontier margin and slack s=β*(α,Q)−β, certification is governed up to constants and logarithms by the two-resource threshold s≍κ^{-1}√(β/n)+√(β/m)+ρ/κ, with n labeled source and m unlabeled target samples. The claim is organized into three model-tagged bounds: a Model-B (unknown weights) lower bound via Le Cam pairs, a Model-A (oracle weights) upper bound matching those rates, and a Model-B' (estimated weights under a pre-registered exact stratified-shift model) implementable upper bound with an explicitly priced nuisance. Theorem 6 shows that no unknown-weight procedure over the full bounded-ratio class is consistent at α=β=1/2, which justifies the cross-model formulation. The paper also reports pre-registered synthetic audits (a log-log bite slope of −2.002, a 1,024-cell validity audit with 0 violations for the formal arms) and a SQuAD→NewsQA feasibility audit whose certificate honestly refuses.","tokens_in":61414,"tokens_out":24767,"duration_ms":248811,"significance":"If the results are correct, the paper makes a substantial contribution: it is the first to index certification lower bounds by a coverage floor under covariate shift, to exhibit a labeled/unlabeled two-resource complexity map, and to prove an inconsistency theorem showing that some structural restriction on the shift weights is necessary for any implementable certificate. The lower-bound constructions are technically interesting (two Le Cam pairs with a shared base world; a lattice-independent hard instance at α=β=1/2), and the manuscript is exemplary in its scoping: Assumption 1, Remark 16, §4.5, and the Limitations section explicitly state that the Model-B' certificate is conditional on exact K-measurability, that off-partition bias is not estimable from covariates, and that a synthetic adversarial sweep exhibits violations off the K-measurable class. The pre-registered experimental protocol, the visible constants, and the released-code transparency are also strengths.","major_comments":[{"comment":"The empirical evaluation and practical constants are for the released kernel with the registered radius ρv2 (Eq. 8), while the power/sample-complexity guarantee of Theorem 3 is proved for the different radius ρλ (Eq. 6). Remark 14 explicitly states that the power statements are proved for (6) and that neither radius dominates. As a result, the bite-divergence experiment, the certification onsets, and the K-price sweep in Table 4—offered as evidence for the map's rates—do not directly follow from Theorem 3 for the procedure that was actually run. Please extend the power proof to ρv2, run the experiments with the analyzed radius ρλ, or explicitly qualify in §5.1 and §5.2 that the empirical rate-shape evidence is for a valid certificate whose power guarantee is not covered by the theorem as stated.","section":"§5.2, Remark 14, Theorem 3"},{"comment":"The deployable arm of the Floor Certification Map is valid only under Assumption 1's exact K-measurability of w. The paper is transparent about this in Remark 16 and Limitations(iv), and the stress-test concern about the untestable stratified premise therefore lands as a limitation rather than an internal inconsistency. Nevertheless, because Theorem 6 shows that no unknown-weight procedure over the full bounded-ratio class is consistent, this conditional assumption is the entire practical basis for the implementable upper bound. The abstract's opening sentence and Contribution (1) should state at the point of the claim that the implementable two-resource map applies to pre-registered exact stratified shifts, and should refer to Appendix G.9's off-partition sweep as a misspecification boundary of the certificate rather than a robustness failure. This is primarily a scoping and presentation revision, but it is load-bearing for how the headline result will be read.","section":"Abstract, Theorem 1 Claim 3, §4.5"}],"minor_comments":[{"comment":"The bottom rows list 'n_total = 220' and 'n_total = 222', which appear to be intended as powers of two (2^20 and 2^22); please format these entries unambiguously.","section":"Table 4"},{"comment":"The template displays ρ/κ as an additive term, but the paper proves this nuisance axis only sufficient and not necessary (Remark 1, Theorem 8); consider marking it with a qualifier such as '(sufficient)' in the display.","section":"Equation (1)"},{"comment":"The phrase 'formal demonstration escalates all' is unclear; please rephrase to describe what the demonstration arms show.","section":"Figure 1(a) caption"},{"comment":"The definitions of s0 and c0 are split between Definition 3 and the surrounding text; a single consolidated statement of the local-regime constants would help readers.","section":"Section 3, Definition 3"},{"comment":"The references to Remark 16 in §4.5 and Remark 17 near Assumption 1 are not visible in the provided text; please ensure these remarks are numbered and present in the final manuscript.","section":"Remarks 16 and 17"},{"comment":"The bite-divergence slope is estimated from 9 design points; the paper reports both OLS and bootstrap intervals, but it would be useful to state explicitly how the design points are chosen and whether the confidence interval accounts for the pre-registered band.","section":"Section 5.1"}],"recommendation":"major_revision","confidential_remarks":"The manuscript is long and self-referential, but the empirical transparency is a genuine strength. The main risk for the journal is that the headline practical map may be over-read without the K-measurability caveat; the revision should make the conditional status of the Model-B' arm part of the abstract's opening claim. I did not find evidence of citation manipulation; the heavy self-citation is to the authors' own registered program and is disclosed."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The thing to know: this paper proves a real lower-bound theory for coverage floors under covariate shift, and shows the problem splits into a labeled-source risk axis and an unlabeled-target floor axis. That two-resource map, with β-indexed rates and a localized accepted-region functional replacing global ESS, is not in the prior literature. The lower bound (Claim 1) and the inconsistency theorem (Theorem 6) look solid, and the paper is unusually explicit about what it does not prove.\n\nWhat is actually new: the coverage-floor-indexed lower bounds, the additive sample-complexity law, the cross-model necessity argument, and the priced nuisance for the implementable certificate. The experiments are pre-registered, the bite slope −2.002 matches the prediction, and the limitation statements are models of honesty. I also credit the explicit scoping of which parts are heuristic (Remark 11), which parts are only sufficient (the histogram B²K rate), and which parts are open (unknown-η nuisance necessity).\n\nThe soft spots are in the upper bound, and they are real but well-contained. Claim 3 (the deployable certificate) is valid only when the density ratio w is exactly constant on the pre-registered K-cell partition. As Remark 16 concedes, if w is not K-measurable you get a projection bias that covariates alone cannot estimate. The stress-test note is right about this, and the paper's own Appendix G.9 shows an off-partition perturbation that fires no alarms but drives true violations. So the practical half of the map is conditional on a structural premise that cannot be verified from the certificate's own outputs. That is not a hidden flaw, but it means the headline \"two-resource map\" applies to real shifts only under an exact-stratification belief. The lattice margin condition and the instance-dependent (rather than uniform minimax) within-model match are softer concerns, and the paper flags both.\n\nI would not reject this over those gaps. The lower-bound and impossibility legs are new, credible, and worth having in the literature; the implementable certificate is a conditional construction with its condition stated. The deferred proofs (Theorem 8, Corollary 2, the B′ power analysis) need referee checking, and the referee should push on whether the K-measurability assumption can be weakened or at least tested by a sensitivity diagnostic. But the central argument holds up.\n\nSend it to a serious theory venue. This deserves real refereeing, and with moderate revision — mainly tightening the presentation of what the implementable result does and does not certify — it would be a solid contribution. I'd take it to reading group and I'd cite it if I were working on selective risk control.","headline":"A genuinely new lower-bound theory for coverage-floor certification under covariate shift, with an implementable upper bound that is honest about its exact-stratification premise.","tokens_in":62021,"tokens_out":1694,"would_cite":true,"duration_ms":22569,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62C20","62G05"],"pacs":[],"model":"deepseek-v4-flash","headline":"A hard coverage floor turns selective certification into a two-resource sample-complexity problem, and the paper proves the split is unavoidable: no unknown-weight method matches it at any sample size.","keywords":["selective risk control","coverage floor","covariate shift","distribution-free certification","sample complexity lower bounds","certify-or-refuse","conformal risk control","feasibility frontier"],"falsifier":"A direct check of the map's additive form: on a fixed regular-margin world, measure minimal labeled budget $n_{\\min}$ at abundant $m$ and minimal unlabeled budget $m_{\\min}$ at abundant $n$, and verify the decoupled thresholds $n_{\\min}\\asymp\\beta/(\\kappa s)^2$ and $m_{\\min}\\asymp\\beta/s^2$ plus the additive corner on a dense $(n,m)$ grid — the paper's own 41-cell surface initially failed this separation test, recovering only at 635 cells, so the form is empirically load-bearing. Separately, hold the relative slack $s/\\beta$ fixed and shrink $\\beta$: the map predicts required samples grow as $1/\\beta$ (the floor creates the cost), whereas a floor-free view predicts bounded cost, a clean discriminating experiment.","tokens_in":60933,"feed_emoji":"🛡️","tokens_out":17074,"duration_ms":146376,"temperature":0.7,"pith_summary":"Selective predictors that certify a risk level can always satisfy the certificate by abstaining on almost everything; operators, however, need a guarantee that at least a $\\beta$-fraction of shifted target traffic is actually answered, with at most an $\\alpha$-fraction of answers wrong. This paper proves that once this coverage floor must be certified alongside the selection-conditioned risk, certification under bounded-ratio covariate shift acquires a feasibility frontier and a two-resource sample-complexity map, additive up to constants: the risk is paid in labeled source samples, the floor in unlabeled target samples. The claim matters because it is operational — at floor slack $s$ the certifiable region's corner traces $s \\asymp \\kappa^{-1}\\sqrt{\\beta/n}+\\sqrt{\\beta/m}$, telling an operator which data to buy — and because the paper proves the map is created by the floor, not by shift overlap: both lower-bound axes vanish as $\\beta\\to 0$. It also proves that no single-model law exists over the full bounded-ratio class: at $\\alpha=\\beta=1/2$, no unknown-weight procedure certifies at any sample size, so the matching across three information models (oracle weights, unknown weights, estimated weights on a pre-registered partition) is necessary rather than a convenience.","feed_headline":"Coverage floors, not data shifts, create the certification cost map","feed_subtitle":"Adding a hard automation floor splits sample cost: labeled source buys risk, unlabeled target buys coverage.","key_machinery":"The load-bearing mechanism is the feasibility frontier $\\beta^*(\\alpha,Q)$ — the largest coverage certifiable at risk $\\alpha$, defined as the largest $c$ with $\\varphi(c)\\ge 0$ for the budget functional $\\varphi(c)=\\alpha c-\\int_0^c \\eta_Q^*(u)\\,du$, where $\\eta_Q^*$ is the increasing rearrangement of the conditional loss under the target distribution; the frontier is a fractional-knapsack value from the generalized Neyman-Pearson lemma. The regular frontier margin $(\\kappa,s_0)$ makes the budget linear near the frontier, $\\varphi(\\beta^*-s)\\ge\\kappa s$, and this single inequality drives both the achievability margins and the near-quadratic divergence of required labeled samples (log-log slope $-2.002$ in the registered synthetic family). The lower bounds are Le Cam two-point pairs at bounded likelihood ratio — one pair flipping an inframarginal labeled slice for the $n$-axis, one moving target mass out of the safe block for the $m$-axis — while the upper bounds are empirical-Bernstein one-sided tests on the linearized risk $\\mathbb{E}_P[wS_\\lambda(L-\\alpha)]\\le 0$ and a variance-aware floor lower confidence bound, sharing one learn-then-test confidence budget over a pre-registered threshold lattice. The variance proxy on the upper side and the hard-slice geometry on the lower side both localize to the accepted region, surfacing $\\mathbb{E}_P[w^2S_\\lambda]$ as the complexity functional.","core_discovery":"On the paper's own terms, the central discovery is the Floor Certification Map (Theorem 1): under bounded-ratio covariate shift $w\\le B$ with a regular frontier margin $(\\kappa,s_0)$ and floor slack $s=\\beta^*-\\beta$ in the local regime, certifying that the selection-conditioned risk obeys $R_Q\\le\\alpha$ and the coverage obeys $C_Q\\ge\\beta$ costs $s\\asymp\\kappa^{-1}\\sqrt{\\beta/n}+\\sqrt{\\beta/m}+\\rho/\\kappa$ up to constants and logarithms, with the risk axis paid in labeled source samples $n$ and the floor axis in unlabeled target samples $m$. The map is delivered as three model-tagged bounds — a Model-B lower bound under unknown weights, a Model-A oracle-weight upper bound attaining the same rates, and a Model-B$'$ upper bound for estimated weights under a pre-registered exact stratified-shift model with an explicitly priced nuisance — rather than a single-model minimax law, and the paper proves (Theorem 6) that such a law is impossible: over the full bounded-ratio class no unknown-weight procedure matches at any sample size, witnessed at $\\alpha=\\beta=1/2$. The paper also establishes that the map is floor-created (both lower-bound axes vanish as $\\beta\\to0$), that the operative complexity proxy on both sides is the localized accepted-region second moment $\\mathbb{E}_P[w^2S_\\lambda]$ rather than global effective sample size (with a fixed-ESS separation theorem left open), that the implementable certificate is valid only under its stratified-shift model, and that it honestly refuses on a real SQuAD-to-NewsQA workload while its formal arms log zero violations in a 1,024-cell synthetic audit.","pith_inferences":["My inference: the steepest operational consequence of the map is the 'bite' curve — required labeled samples grow like $s^{-2}$ as the floor approaches the frontier, so the last few percentage points of coverage slack are disproportionately expensive; improving the router score (raising $\\kappa$) or renegotiating the service level is likely cheaper than buying marginal labeled data, a trade the pa","My inference: the practical bottleneck for real deployment is the stratified-shift premise, which the paper partially concedes (weights that are not exactly cell-constant degrade the guarantee to a projection bias that covariates alone cannot estimate); a testable extension is to measure certification frequency and violation rate as within-cell weight variation grows while projected cell masses ar","My inference: because the paper leaves the histogram nuisance rate $B^2K$ only sufficient, a natural next move is to replace the histogram ratio estimator with a smoother estimator that still admits a finite-sample localized $\\ell^1$ recovery bound; whether the $K$-premium can be eliminated is the open unknown-$\\eta$ edge the paper identifies.","My inference: the cross-model template likely transfers to other ratio-constrained certification problems, such as certifying recall at a precision floor under label shift or certifying a cost-per-accepted-item cap in routing systems, where a feasibility frontier and a labeled/unlabeled resource split should reappear with the same additive form."],"forward_implications":["At floor slack $s=\\beta^*-\\beta$, an operator can allocate budgets axis by axis: labeling more source data relaxes the risk requirement $n\\gtrsim\\beta/(\\kappa s)^2$, while unlabeled target draws relax the floor requirement $m\\gtrsim\\beta/s^2$, and when the estimated-weight nuisance binds, weight-block samples shrink the nuisance radius.","Risk-only certificates cannot make the operator's automation promise: without the floor, a certificate can be vacuously safe by abstaining on nearly all traffic, and both lower-bound axes vanish as $\\beta\\to 0$, so the two-resource law is created by the floor rather than by shift overlap.","No unknown-weight procedure can match these rates over the full bounded-ratio class at any sample size, witnessed at $\\alpha=\\beta=1/2$, so any implementable certificate must know the weights or restrict the shift model; the paper's pre-registered $K$-cell partition is one such restriction with an explicit price.","Certification cost is governed by the localized accepted-region second moment $\\mathbb{E}_P[w^2S_\\lambda]$ rather than a global effective sample size, so two shifts with identical global ESS can demand very different labeled budgets; the registered family-1 experiment shows required-$n$ tracking the localized functional (Spearman 0.936) and not global ESS (0.026).","The implementable certificate is valid where it fires but conservative: in the 1,024-cell audit it certifies 8 cells against 583 for the oracle-weight arm, with zero violations, and on a SQuAD-to-NewsQA workload it returns pre-deployment honest refusal with test-side attribution."],"supporting_citations":[{"why":"Supplies the empirical-Bernstein upper and lower confidence bounds that the risk test, the floor test, and the released nuisance radius all run on.","marker":"[Maurer and Pontil, 2009]"},{"why":"The learn-then-test shared-budget scheme that makes scanning the pre-registered threshold lattice free of extra selection error.","marker":"[Angelopoulos et al., 2021]"},{"why":"The linear-expectation reformulation that converts the ratio constraint $R_Q\\le\\alpha$ into the linearized test $\\mathbb{E}_P[wS_\\lambda(L-\\alpha)]\\le 0$ used by the certificate.","marker":"[Wang et al., 2025b]"},{"why":"The density-ratio reweighting under covariate shift that the bounded-ratio model and the weighted test statistics inherit.","marker":"[Tibshirani et al., 2019]"},{"why":"The Le Cam two-point minimax technique that the two-axis lower bound and the inconsistency proof are built from.","marker":"[Tsybakov, 2009]"},{"why":"The generalized Neyman-Pearson lemma underlying the frontier characterization as a fractional-knapsack budget problem.","marker":"[Dantzig and Wald, 1951]"},{"why":"The nearest distribution-free lower-bound theory, floor-free on one axis; the baseline that the $\\beta$-indexed lower bounds extend and compare against.","marker":"[Aldirawi et al., 2026]"},{"why":"SCoRE weighted e-values for selective risks; the equal-construction betting ablation the validity audit runs against the certificate's risk test.","marker":"[Bai and Jin, 2026]"},{"why":"The i.i.d. joint finite-sample certificate for selection-conditioned risk with an acceptance floor, whose validity half this paper explicitly does not claim as novel.","marker":"[Yu and Liu, 2026]"}],"fun_headline_variants":["Coverage floor splits costs: labeled risk, unlabeled floor","No unknown-weight procedure matches at any sample size","Certification cost map: two resources, one floor","Feasibility frontier emerges from coverage-floor certification"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The implementable certificate's validity rests on the density ratio being exactly constant on a pre-registered finite partition of the input space, and the paper concedes that when the true shift is not of that stratified form the guarantee degrades to a projection with an additive bias that covariates alone cannot estimate.","fun_headline_variants_meta":{"raw":{"variants":["Coverage floor splits costs: labeled risk, unlabeled floor","No unknown-weight procedure matches at any sample size","Certification cost map: two resources, one floor","Feasibility frontier emerges from coverage-floor certification"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000258,"raw_usage":{"total_tokens":1752,"prompt_tokens":1282,"completion_tokens":470,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":898,"completion_tokens_details":{"reasoning_tokens":407}},"tokens_in":898,"tokens_out":470,"duration_ms":5752,"temperature":1.0,"reasoning_tokens":407,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T14:49:45.457999+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"A direct check of the map's additive form: on a fixed regular-margin world, measure minimal labeled budget $n_{\\min}$ at abundant $m$ and minimal unlabeled budget $m_{\\min}$ at abundant $n$, and verify the decoupled thresholds $n_{\\min}\\asymp\\beta/(\\kappa s)^2$ and $m_{\\min}\\asymp\\beta/s^2$ plus the additive corner on a dense $(n,m)$ grid — the paper's own 41-cell surface initially failed this separation test, recovering only at 635 cells, so the form is empirically load-bearing. Separately, hold the relative slack $s/\\beta$ fixed and shrink $\\beta$: the map predicts required samples grow as $1/\\beta$ (the floor creates the cost), whereas a floor-free view predicts bounded cost, a clean discriminating experiment.","supporting_citations":[{"cited_title":"Empirical bernstein bounds and sample-variance penalization","cited_arxiv_id":null,"evidence_quote":"Supplies the empirical-Bernstein upper and lower confidence bounds that the risk test, the floor test, and the released nuisance radius all run on."},{"cited_title":"Conformal selective prediction with general risk control","cited_arxiv_id":null,"evidence_quote":"SCoRE weighted e-values for selective risks; the equal-construction betting ablation the validity audit runs against the certificate's risk test."},{"cited_title":"A Joint Finite-Sample Certificate for Adaptive Selective Conformal Risk Control","cited_arxiv_id":"2606.08517","evidence_quote":"The i.i.d. joint finite-sample certificate for selection-conditioned risk with an acceptance floor, whose validity half this paper explicitly does not claim as novel."}],"review_version":1}