When Does q-error Predict Plan Regret? Three Regimes of Cardinality-Estimation Error

• URL: http://arxiv.org/abs/2606.15600v1
• Date: Sun, 14 Jun 2026 05:06:30 GMT
• Title: When Does q-error Predict Plan Regret? Three Regimes of Cardinality-Estimation Error
• Abstract summary: Cardinality-estimation (CE) research ranks estimators by qerror.<n>We give a measurement-driven account of when qerror is a good proxy and when it is not.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Cardinality-estimation (CE) research ranks estimators by q-error, yet it is well known that q-error is an imperfect proxy for query-plan quality. We give a measurement-driven account of when it is a good proxy and when it is not, and why. Modeling plan selection as an argmin over a piecewise-linear cost landscape, we find that plan regret (the cost of the chosen plan relative to the optimal, under true cardinalities) is governed by plan-cost geometry in a regime-dependent way. (i) For small errors, a true-point condition number kappa predicts regret and out-predicts q-error; its predictive power decays to zero as error grows, as a local linearization must. (ii) For large errors -- where deployed learned estimators operate -- an estimator-independent average-case sub-optimality measure ACS-infinity predicts which queries are regret-prone (Spearman rho ~ 0.54 on STATS-CEB), while q-error is nearly uninformative at the query level (rho ~ 0.05). (iii) The worst case is Haritsa's maximum sub-optimality (MSO). The three are one cost-ratio spectrum under three weightings. We prove a limit law ACS-infinity = sum_k r_k pi_k with cardinality-independent combinatorial weights, and validate every claim on STATS-CEB and JOB-light with four released estimators under pre-registered decision rules, and confirm on real PostgreSQL runtime that ACS-infinity predicts regret where q-error does not. The contribution is conceptual and empirical -- an average-case companion to worst-case robust query optimization, and a characterization of when an accuracy metric tracks plan quality -- rather than a new estimator. Code and the full pre-registration are public.

Related papers

• Knowing When to Ask for Help: Bayesian Self-Escalation in Hierarchical LLM Agents [0.0]
  Current agent systems decide delegation before reasoning begins.<n>We study a third regime: an agent that recognises, during its own reasoning, that it is unlikely to succeed.
  arXiv  Detail & Related papers  (2026-08-25T05:35:07Z)
• Decision Kernels for Quantum Error Mitigation: Why Accuracy Gains Need Not Improve Downstream Decisions [0.0]
  We develop a theory of finite-shot QEM for downstream decisions.<n>We prove quotient factorization, gap-law minimality, a marginal no-go theorem, a QEM pullback theorem, and a fixed-allocation shot-level converse.
  arXiv  Detail & Related papers  (2026-07-03T02:35:57Z)
• YUKTI: From Natural-Language Situations to Robust, Verifiable Decisions An Uncertainty-Typed Proposition IR, Assumption-Robust Pareto Frontiers, and a Regret Certificate [0.0]
  We show that YUKTI routes each stage to an exact, nonlinear, or evolutionary solver.<n>We prove a bound making rho an exact factor of decision regret, add auditable traceability, and synthesize a benchmark-faithful data foundation.<n>We validate three ways: under controlled misspecification the robust compromise cuts mean and tail regret by over 90% versus a naive point plan; and on a regulated commercial decision we optimize inside a lawful action space and price the downside in euros.
  arXiv  Detail & Related papers  (2026-06-22T09:29:13Z)
• Filtered ANN as a Phase Transition: When Selectivity-Estimation Error Causes Plan Regret [0.0]
  We show that selectivity-estimation error produces plan regret -- recall lost versus the oracle strategy -- only in the critical regions around those boundaries.<n>A real approximate index does not mis-locate the boundary, but a biased cost model opens a persistent miscalibration band that estimation-error robustness cannot fix.
  arXiv  Detail & Related papers  (2026-06-15T07:44:58Z)
• Instance-Optimal Estimation with Multiple LLM Judges on a Budget [84.31744861038106]
  We formalize this question as *budgeted heteroskedastic multi-judge estimation*.<n>Given $K$ prompt-response pairs, $J$ judges with known costs, and unknown query-judge variances, the goal is to estimate a bounded score vector while minimizing an $ell_p$-error.<n>We prove that EST-IVWE matches the oracle IVWE rate up to lower-order terms in the budget.
  arXiv  Detail & Related papers  (2026-05-22T08:26:08Z)
• Bandit Convex Optimization with Gradient Prediction Adaptivity [56.816177049016794]
  We investigate whether optimistic gradient predictions can improve worst-case regret guarantees in a prediction-adaptive manner.<n>The key idea is a novel variance-reduced gradient estimator whose variance scales with the prediction error rather than the gradient norm.<n>We establish an information-theoretic lower bound that scales as $(sqrtmathbbE[S_T])$, providing a fundamental characterization of the best achievable prediction-adaptive regret.
  arXiv  Detail & Related papers  (2026-05-21T08:57:38Z)
• COIN: Uncertainty-Guarding Selective Question Answering for Foundation Models with Provable Risk Guarantees [51.5976496056012]
  COIN is an uncertainty-guarding selection framework that calibrates statistically valid thresholds to filter a single generated answer per question.<n>COIN estimates the empirical error rate on a calibration set and applies confidence interval methods to establish a high-probability upper bound on the true error rate.<n>We demonstrate COIN's robustness in risk control, strong test-time power in retaining admissible answers, and predictive efficiency under limited calibration data.
  arXiv  Detail & Related papers  (2025-06-25T07:04:49Z)
• One Sample is Enough to Make Conformal Prediction Robust [53.78604391939934]
  We show that conformal prediction attains some robustness even with a forward pass on a single randomly perturbed input.<n>Our approach returns robust sets with smaller average set size compared to SOTA methods which use many (e.g. around 100) passes per input.
  arXiv  Detail & Related papers  (2025-06-19T19:14:25Z)
• Conformal Prediction Beyond the Seen: A Missing Mass Perspective for Uncertainty Quantification in Generative Models [20.810300785340072]
  Conformal Prediction with Query Oracle (CPQ) is a framework characterizing the optimal interplay between these objectives.<n>Our algorithm is built on two core principles: one governs the optimal query policy, and the other defines the optimal mapping from queried samples to prediction sets.
  arXiv  Detail & Related papers  (2025-06-05T18:26:14Z)
• Correctness Coverage Evaluation for Medical Multiple-Choice Question Answering Based on the Enhanced Conformal Prediction Framework [2.9599960287815144]
  Large language models (LLMs) are increasingly adopted in medical question-answering (QA) scenarios.<n>LLMs can generate hallucinations and nonfactual information, undermining their trustworthiness in high-stakes medical tasks.<n>This paper proposes an enhanced Conformal Prediction framework for medical multiple-choice question-answering tasks.
  arXiv  Detail & Related papers  (2025-03-07T15:22:10Z)
• Prune 'n Predict: Optimizing LLM Decision-making with Conformal Prediction [7.843594672029363]
  incorrect outputs pose significant risks in high-stakes domains like healthcare and finance.<n>We propose emphconformal revision of questions (CROQ), which revises the question by narrowing down the available choices to those in the prediction set.<n>We also propose CP-OPT, an optimization framework to learn scores that minimize set sizes while maintaining coverage.
  arXiv  Detail & Related papers  (2024-12-31T17:33:12Z)
• A Universal Error Measure for Input Predictions Applied to Online Graph Problems [57.58926849872494]
  We introduce a novel measure for quantifying the error in input predictions. The measure captures errors due to absent predicted requests as well as unpredicted actual requests.
  arXiv  Detail & Related papers  (2022-05-25T15:24:03Z)
• Regret-Optimal Filtering [57.51328978669528]
  We consider the problem of filtering in linear state-space models through the lens of regret optimization. We formulate a novel criterion for filter design based on the concept of regret between the estimation error energy of a clairvoyant estimator. We show that the regret-optimal estimator can be easily implemented by solving three Riccati equations and a single Lyapunov equation.
  arXiv  Detail & Related papers  (2021-01-25T19:06:52Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.