{"id":"9acfe492-676d-4616-acee-68899f5f1857","arxiv_id":"2505.02284","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"Conformal prediction can turn a learned query optimizer's cost estimates into latency bounds with a user-chosen confidence level, enabling pre-execution verification and a search heuristic that improves planning time.","lead":"This paper wraps learned query optimizers with conformal prediction, a statistical method that turns model predictions into ranges with user-controlled confidence. It reports that the ranges are accurate on standard database benchmarks, and that using them to guide plan search can improve planning time and, for some queries, plan quality.","discovery_kind":"new_application","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Non-conformity scores pooled across partial-plan construction steps are not exchangeable, so the claimed per-plan 1-δ latency bound is not formally guaranteed.","rationale":"The reader's verdict identified intra-query dependence as the weakest assumption; I agree. This is the most load-bearing issue because the paper's headline contribution is a formal, user-controlled latency bound before execution. Without exchangeability, Equations 1-4 do not yield the stated guarantee; the empirical coverage is a marginal, pooled quantity that does not substantiate per-plan coverage. The concern is concrete and testable: per-step coverage would reveal the violation. The issue is addressable (e.g., define non-conformity per query, group by step, or use weighted conformal under non-exchangeability), so the appropriate editorial outcome remains a conditional accept rather than rejection. Since my concern aligns with the reader's weakest_assumption and does not change the assessment, the verdict is unchanged.","tokens_in":25070,"tokens_out":11092,"duration_ms":128191,"concrete_test":"Re-run the coverage evaluation of Section 6.2 (Balsa on JOB, δ=0.1) separately for each partial-plan step index (or partial-plan size / number of operators), and also separately for each test query, instead of pooling all steps. Under the exchangeability assumption, per-step and per-query coverage should be approximately 1−δ. If, for example, early-step coverage falls below 80% while late-step coverage exceeds 95%, the pooled C does not deliver the claimed per-plan probability, and the exchangeability concern is confirmed.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central claim (Equations 1-4) is a finite-sample conformal guarantee: for any plan, the actual latency t satisfies ĉ−C ≤ t ≤ ĉ+C with probability ≥ 1−δ. This is valid only if the test score R(0) is exchangeable with the calibration scores R(1),...,R(K). The framework pools non-conformity scores from all partial/complete plans in calibration queries into a single list (Section 3.3), and evaluates the resulting C on every operator/step of test queries (Section 6.2). These scores are not exchangeable: within a query, partial plans are generated sequentially by the same LQO, and the residual distribution varies with construction step (later steps contain more operators and different operator patterns). A vector containing multiple step-scores from the same query is not permutation-invariant, so the joint distribution of the pooled calibration scores plus a test score is not exchangeable. The paper asserts in Section 2.2 that the scores are i.i.d., but this is an assumption, not a demonstrated property; no evidence is provided that residuals at different steps share a common marginal or are independent. Consequently, Equation 4 is not a formal guarantee for a selected test plan. The reported empirical coverage is averaged over all test steps, which can hide per-step under-coverage; a pooled coverage near 0.9 is not evidence that the exchangeability requirement is satisfied.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper proposes a conformal prediction (CP) framework for learned query optimizers (LQOs). It defines a latency-cost non-conformity score, derives bounded latency ranges for partial and complete plans, extends the method to adaptive CP for distribution shift, and introduces an STL-based runtime verification module with a fallback to a traditional optimizer. It also proposes a CP-guided plan search algorithm. The evaluation covers three LQOs (Balsa, Lero, RTOS) and four workloads (JOB, TPC-H, CEB, JOBLight-train), reporting empirical coverage, violation detection and handling, plan quality, and planning time.","tokens_in":25294,"tokens_out":6795,"duration_ms":87095,"significance":"Conditional on the formal guarantees being valid, the paper addresses a genuine gap: LQOs are opaque and can produce tail-latency disasters, and existing robustness-oriented work such as Kepler and Roq does not provide per-plan formal latency guarantees. The paper's strengths include a clean problem formulation, the use of external adaptive-CP and STL machinery, an explicit lower bound on the calibration set size in Lemma 1, and a broad empirical study across multiple LQOs and workloads. The proposed framework could be a useful building block for production LQO deployment if the exchangeability assumption and the runtime-verification semantics are made sound.","major_comments":[{"comment":"The central finite-sample guarantee in Eq. (4) requires the test non-conformity score to be exchangeable with the calibration scores. The framework pools scores from all partial and complete plans in the calibration workload and then applies the resulting bound to every operator or pattern of test queries. However, partial plans within one query are generated sequentially by the same LQO and their residual distributions are likely to change with construction step, so the pooled score vector is not obviously exchangeable; the i.i.d. assertion in Section 2.2 is an assumption, not a demonstrated property. Consequently, Eq. (4) is not a validated per-step or per-plan guarantee as stated. The paper should either treat each query as a single calibration unit, use a blockwise conformal construction that accounts for intra-query dependence, or provide empirical evidence such as an exchangeability test and per-step coverage breakdowns.","section":"Sec. 3.3 and Eq. (2)-(4)"},{"comment":"Lemma 2 is worded as an 'only if' condition, but the proof establishes only sufficiency: if rho_phi(x_hat) > C, then P(X satisfies phi) >= 1 - delta. The sentence 'Otherwise, the resulting complete plan will cause a violation' is not a logical consequence; failure of the condition merely means the method cannot certify the plan, and the fallback may fire on plans that would have satisfied the constraint. In addition, Eq. (7) constructs x_hat using only the observed prefix and the next predicted step, whereas the STL specification G[0,N-1] phi in Section 2.3 requires all N steps; the paper does not define robust semantics for truncated signals or justify that rho_phi(x_hat) computed on this prefix upper-bounds or reflects the robustness of the full plan. The runtime verification claim needs a precise statement of what exactly is verified at each step.","section":"Sec. 4 and Lemma 2"},{"comment":"The reported 9.96% improvement across all test queries is a planning-time reduction in Section 6.6.2, and the 74.4% figure is also a planning-time improvement for a single query. The Abstract states this correctly as planning time, but the Conclusion says 'CP-guided LQOs show a 9.96% reduction in actual latency', which is not supported by the experiments. The execution-latency improvement is reported per query (up to 9.84x for Query 27b), not as an aggregate 9.96% reduction. The Abstract and Conclusion should be aligned so that each number is attributed to the metric actually measured.","section":"Abstract, Sec. 6.6.2, and Sec. 8"}],"minor_comments":[{"comment":"The text says the scores R(0),...,R(K) are i.i.d., but the proofs and the standard conformal argument only require exchangeability; please align the terminology throughout.","section":"Sec. 2.2"},{"comment":"The expression '1−δ/δ' in the lemma statement is ambiguous; it should be written as '(1−δ)/δ'.","section":"Sec. 3.1, Lemma 1"},{"comment":"The normalization constants f(c)=c/40 for Lero and f(c)=c/100 for RTOS are introduced without justification or sensitivity analysis; since these constants rescale the non-conformity scores and directly affect the tightness of C, a brief rationale or robustness check is needed.","section":"Sec. 6.1"},{"comment":"The legend labels for the least-popular patterns appear as garbled characters and should be fixed.","section":"Fig. 6"},{"comment":"The artifact URL is the placeholder 'URL_TO_YOUR_ARTIFACTS'; the actual artifact link must be provided for the artifact availability claim.","section":"Artifact availability"},{"comment":"The runtime verification validation uses 30 test queries and reports counts such as 27/30 and 28/30; this sample is too small to confirm a 90% coverage guarantee, and the paper should report confidence intervals or a larger evaluation.","section":"Sec. 6.4"}],"recommendation":"major_revision","confidential_remarks":"The paper's claimed novelty as the first CP-based verification framework for LQOs is plausible. The main formal concern is the exchangeability of pooled partial-plan scores, and the runtime verification section also needs a precise semantics for truncated signals. These issues are fixable within the manuscript's scope, but they are load-bearing for the central claims. Please also ensure the planning-time versus actual-latency wording in the conclusion is corrected before resubmission."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Hi [Name],\n\nQuick read on arXiv:2505.02284. The paper is the first to frame learned query optimizer verification as a conformal prediction problem, and the empirical work is real: they integrate with Balsa, Lero, RTOS, run JOB/TPC-H, and show coverage curves that track 1−δ. The CP-guided plan search idea is also genuinely new—using the CP upper bound as a search heuristic rather than just a monitor—and the reported plan quality gains on specific queries are suggestive, though selective.\n\nThe core CP machinery is standard, and they cite Lindemann, Cairoli, Cauchois, Zhao properly. The adaptive CP section reproduces known distribution-shift guarantees, and their experiments confirm that. Lemma 1 is a simple derivation of the calibration set size, fine.\n\nWhere it gets soft: the central coverage claim in Equations 3–4 treats each partial-plan score as exchangeable, but scores from the same query are generated sequentially by the same model and are correlated. The paper simply asserts i.i.d. in Section 2.2 and never tests for intra-query dependence. The stress-test note is right: the pooled empirical coverage over all steps can hide per-step under-coverage. This isn't fatal to the framework—you could treat each complete plan as the exchangeable unit, or use weighted conformal—but as written the headline guarantee is not formally established for per-operator bounds.\n\nSecond, Lemma 2 proves the forward direction (if ρ>C then violation is unlikely) but the online phase treats failure of ρ>C as a detected violation and triggers fallback. That's a reasonable heuristic, but it's not what the lemma says, and the paper doesn't flag the asymmetry.\n\nThird, the abstract/conclusion says 9.96% reduction in actual latency, but Section 6.6.2 reports 9.96% reduction in planning time. The plan quality gains are also reported only on the subset of queries that improved, with no aggregate measure. Those overclaims are easy to fix but need fixing.\n\nMinor: the Lero/RTOS cost normalizations (ĉ/40, ĉ/100) are fitted constants, and the artifact link is a placeholder.\n\nNet: this is a solid application paper with a real idea and honest experiments, but the formal guarantee needs either a stronger exchangeability argument or a weaker claim. With revisions addressing the per-step coverage and the overclaims, it could be a useful contribution. I'd send it to referees—they'll have enough to chew on without it being a waste of time.\n\nBest,\n[Your name]","headline":"Applies conformal prediction to learned query optimizers with real experiments, but the per-plan coverage guarantee rests on an exchangeability assumption the paper never tests, and the conclusion overstates a planning-time win as a latency win.","tokens_in":25862,"tokens_out":2562,"would_cite":false,"duration_ms":29052,"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":"This paper claims that conformal prediction can give learned query optimizers statistically guaranteed bounds on actual query latency before execution, and can detect or guide around slow plans during construction.","keywords":["conformal prediction","learned query optimization","runtime verification","latency bounds","distribution shift","adaptive conformal prediction","query plan search","signal temporal logic"],"falsifier":"Run a white-box LQO on a fixed workload, compute C from a calibration set, and measure on held-out queries whether at least 1-delta of actual latencies fall within predicted cost plus or minus C; coverage persistently below 1-delta, or a rank test rejecting exchangeability of the partial-plan scores, would falsify the central claim.","tokens_in":24814,"feed_emoji":"⏱️","tokens_out":6163,"duration_ms":72218,"temperature":0.7,"pith_summary":"The paper sets out to make learned query optimizers verifiable rather than taken on faith. It defines a latency-cost non-conformity score as the absolute difference between a plan's predicted cost and its actual latency, and applies conformal prediction so that, with a user-chosen probability 1-delta, a test plan's latency falls inside the interval predicted cost plus or minus an upper bound C. For white-box optimizers that build plans step by step, the same conformal construction is applied to the robustness of a temporal constraint, yielding an early check that flags a violating plan before it is completed. An adaptive version adjusts C when the workload shifts, and a CP-guided search uses the latency upper bound to steer plan construction. If the guarantees hold, users can specify confidence levels for latency constraints and detect or avoid slow plans without executing them.","feed_headline":"Conformal prediction gives query optimizers provable latency bounds","feed_subtitle":"A statistical wrapper verifies LQO plans before execution and catches slow plans early.","key_machinery":"The load-bearing object is the latency-cost non-conformity score R := |t - c_hat|, whose empirical quantile over a calibration workload becomes the upper bound C. Around it are the STL robustness measure rho_phi, used to express latency constraints and to compare the current partial plan estimate with the final complete plan, and the adaptive adjustment of the uncertainty probability through the distribution-shift correction of Equation 5. The CP upper bound is the mechanism that converts predicted costs into pre-execution latency intervals, and the comparison rho_phi(x_hat) > C is the mechanism that converts partial-plan prefixes into early violation signals.","core_discovery":"The central discovery is that verification of learned query optimizers can be formulated as a conformal prediction problem. For each plan define R := |t - c_hat|; taking C as the (1-delta)th quantile of the calibration scores yields the marginal guarantee P(c_hat - C <= t <= c_hat + C) >= 1 - delta, so the actual latency of an unseen plan has a bounded range before execution. For white-box LQOs that construct plans operator by operator, the paper verifies STL constraints on robustness values: with non-conformity score rho_phi(x_hat) - rho_phi(x), the condition rho_phi(x_hat) > C implies P(X satisfies phi) >= 1 - delta. The framework also adapts C under distribution shift and uses the upper bound c_hat + C as a heuristic in beam search, reporting plan quality improvements up to 9.84x and planning time reductions up to 74.4% for a single query.","pith_inferences":["Editorial extension: a natural next step is to apply the same conformal verification to other learned database components, such as cardinality estimators or cost models, wherever a measurable error between prediction and observation exists.","Editorial extension: the exchangeability assumption is most fragile for sequential partial plans within one query; if intra-query correlation is strong, block-wise or adaptive conformal schemes may be needed to preserve the stated coverage.","Editorial extension: the CP-guided search could double as a planning-time budget mechanism, pruning partial plans whose optimistic latency upper bound already exceeds the user's constraint."],"forward_implications":["Users can set a confidence level and receive pre-execution latency bounds for LQO-generated plans, making plan behavior auditable before spending execution time.","White-box LQOs can be stopped mid-construction when the current partial plan suggests a constraint violation, and the query can be re-planned by a traditional optimizer.","When workloads drift, adaptive CP preserves the nominal 1-delta coverage by inflating the bound according to an estimated distribution shift.","CP-guided plan search improves both plan quality and planning time, especially for moderately trained LQOs, and can restructure plans, for example from left-deep to bushy trees."],"supporting_citations":[{"why":"Supplies the split conformal prediction quantile construction that yields the upper bound C from calibration scores.","marker":"[2]"},{"why":"Provides the robust STL semantics used to express latency constraints and to compute robustness values for verification.","marker":"[17]"},{"why":"Shows how conformal prediction bounds the difference between estimated and actual STL robustness, the basis for Lemma 2.","marker":"[12]"},{"why":"Transfers CP-based STL runtime verification from cyber-physical systems to the LQO setting.","marker":"[29]"},{"why":"Provides the robust conformal prediction under distribution shift that the adaptive CP extension builds on.","marker":"[64]"},{"why":"Supplies the distribution-shift adjustment formula (Equation 5) used to recompute the uncertainty probability.","marker":"[37]"},{"why":"Balsa is the white-box LQO whose partial-plan construction is verified and guided by the CP framework.","marker":"[60]"},{"why":"Lero is the black-box LQO used to validate CP-based latency guarantees at plan level.","marker":"[65]"},{"why":"RTOS is the black-box LQO used to validate CP-based latency guarantees and distribution-shift adaptation.","marker":"[63]"},{"why":"The JOB workload provides the benchmark queries for calibration and testing in the evaluation.","marker":"[28]"}],"fun_headline_variants":["Conformal prediction verifies learned query optimizer plans pre-execution","CP-based verification catches slow LQO plans before they run","Learned query optimizers get provable latency guarantees via conformal prediction","Pre-run latency bounds for learned query optimizers using conformal prediction","Conformal prediction gives query optimizers tight bounds and faster planning"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The guarantees rest on the assumption that latency-cost error scores from calibration plans and test plans are exchangeable draws from one distribution; if sequentially generated partial plans within a query are correlated, or the workload shifts beyond the estimated amount, the stated 1-delta coverage is not assured.","fun_headline_variants_meta":{"raw":{"variants":["Conformal prediction verifies learned query optimizer plans pre-execution","CP-based verification catches slow LQO plans before they run","Learned query optimizers get provable latency guarantees via conformal prediction","Pre-run latency bounds for learned query optimizers using conformal prediction","Conformal prediction gives query optimizers tight bounds and faster planning"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000756,"raw_usage":{"total_tokens":3396,"prompt_tokens":1017,"completion_tokens":2379,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":633,"completion_tokens_details":{"reasoning_tokens":2290}},"tokens_in":633,"tokens_out":2379,"duration_ms":20753,"temperature":1.0,"reasoning_tokens":2290,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T00:56:06.851172+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run a white-box LQO on a fixed workload, compute C from a calibration set, and measure on held-out queries whether at least 1-delta of actual latencies fall within predicted cost plus or minus C; coverage persistently below 1-delta, or a rank test rejecting exchangeability of the partial-plan scores, would falsify the central claim.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the robust STL semantics used to express latency constraints and to compute robustness values for verification."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Transfers CP-based STL runtime verification from cyber-physical systems to the LQO setting."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Provides the robust conformal prediction under distribution shift that the adaptive CP extension builds on."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Lero is the black-box LQO used to validate CP-based latency guarantees at plan level."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"RTOS is the black-box LQO used to validate CP-based latency guarantees and distribution-shift adaptation."}],"review_version":1}