Filtered ANN as a Phase Transition: When Selectivity-Estimation Error Causes Plan Regret

• URL: http://arxiv.org/abs/2606.16341v1
• Date: Mon, 15 Jun 2026 07:44:58 GMT
• Title: Filtered ANN as a Phase Transition: When Selectivity-Estimation Error Causes Plan Regret
• Abstract summary: 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.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: A filtered approximate-nearest-neighbor (ANN) query returns the k nearest vectors among those satisfying an attribute predicate P of selectivity s. The best execution strategy -- pre-filter, post-filter, or in-filter -- changes with s, so a system must estimate s and choose. We model this as an argmax over a landscape with phases (regions where each strategy wins) separated by boundaries, and show that selectivity-estimation error produces plan regret -- recall lost versus the oracle strategy -- only in the critical regions around those boundaries. The regret is a wedge of log-width equal to the multiplicative estimation error epsilon and height equal to the local cliff |V'(s*)| epsilon; the flip-margin 1/|V'(s*)| is the condition number of a sibling cardinality-estimation study reappearing as the local boundary theory. The two phase boundaries follow from independent mathematics: order statistics place the post-filter cliff at s ~ k/K, and site percolation places the in-filter cliff at s_c ~ 0.83/M for graph degree M (corpus-size independent). Criticality exists only under a constrained budget B < sqrt(k n). Under pre-registered decision rules we confirm, on synthetic sweeps and real SIFT1M, that regret concentrates ~290x at the boundary and that the regret curves obey a finite-size scaling collapse onto one universal wedge across two decades of corpus size. 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. The contribution is a characterization, not a new index. Code and the full pre-registration are public.

Related papers

• When Does Low-Bit Quantization Preserve the Decisions of Vector Search? [13.71460633144793]
  Low-bit quantization can achieve high recall on some vector representations and fail sharply on others.<n>We study quantized vector search at the level of the comparisons consumed by ranking and graph-pruning algorithms.<n>Across learned, classical, and synthetic embeddings, standardized exact margins predict held-out ranking and pruning flip rates substantially better than global rank correlation.
  arXiv  Detail & Related papers  (2026-09-09T08:06:50Z)
• Constrained Online Learning with Noisy Constraint Values [55.29259818039367]
  Under common feasibility, our LEDGER algorithm attains $O(sqrt T)$ expected regret and $O(sqrtTlog(eT))$ expected budget violation.<n>Neither a Slater condition, independence between feedback channels, nor an absolute constraint-value bound is needed.
  arXiv  Detail & Related papers  (2026-09-07T01:38:41Z)
• Optimal Stratified Allocation for Rare-Event Onset Forecasting in Dependent Sequences [2.2632368327435732]
  We study estimation of total risk from a subsample K n under designs allocating K0 and K1 draws to the two strata.<n>We derive the exact finite-population variance of the weighted risk estimator under class-conditional sampling without replacement.
  arXiv  Detail & Related papers  (2026-09-03T19:38:01Z)
• Self-Normalized Inference for Constant-Stepsize Temporal-Difference Learning under Markovian Sampling [9.271408028342496]
  Constant-stepsize temporal-difference (TD) learning is attractive for policy evaluation, but inference from a single Markov trajectory must account for serial dependence and a stepsize-dependent stationary target.<n>We establish a functional central limit theorem whose covariance retains the multiplicative component induced by the random TD matrix and the stationary iterate error.<n>Experiments on FrozenLake and Garnet illustrate stationary-target coverage, RR target correction, and the finite-sample behavior of the horizon-indexed design.
  arXiv  Detail & Related papers  (2026-08-11T13:19:28Z)
• The Cost of Adaptivity: Matching Lower Bounds Across Learning Problems [1.0742675209112622]
  We formalize nuisance adaptation via a slice-normalized minimax ratio.<n>We also define the cost of expanding from one preannounced Gaussian query to arbitrary post-hoc inspection.
  arXiv  Detail & Related papers  (2026-08-09T17:19:11Z)
• When Does q-error Predict Plan Regret? Three Regimes of Cardinality-Estimation Error [0.0]
  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.
  arXiv  Detail & Related papers  (2026-06-14T05:06:30Z)
• 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)
• The 99% Success Paradox: When Near-Perfect Retrieval Equals Random Selection [1.2647816797166167]
  We introduce Bits-over-Random (BoR), a measure of retrieval selectivity that reveals when high success rates mask random-level performance.<n>We show that when the expected coverage ratio $left(fracK cdot barR_qNright)$ exceeds 3-5, the baseline dominates and selectivity collapses.<n>These findings suggest reporting BoR alongside traditional metrics and reconsidering depth choices when additional retrieval provides negligible selectivity gains.
  arXiv  Detail & Related papers  (2026-05-14T00:19:57Z)
• The Extrapolation Cliff in On-Policy Distillation of Near-Deterministic Structured Outputs [52.709361620508595]
  ListOPD brings a student to in-domain with an 8B-SFT baseline at one-fifth the parameters.<n>On Amazon Fashion, three pre-registered tests--a fine-grid cliff interval test, and a small-clip cross-prediction--fall within their locked prediction windows--with the small-clip value matching the closed-form prediction below grid resolution.
  arXiv  Detail & Related papers  (2026-05-09T06:48:00Z)
• Closing the Approximation Gap of Partial AUC Optimization: A Tale of Two Formulations [121.39938773554523]
  The Area Under the ROC Curve (AUC) is a pivotal evaluation metric in real-world scenarios with both class imbalance and decision constraints.<n>We present two simple instance-wise minimax reformulations to close the approximation gap of PAUC optimization.<n>The resulting algorithms enjoy a linear per-iteration computational complexity w.r.t. the sample size and a convergence rate of $O(-2/3)$ for typical one-way and two-way PAUCs.
  arXiv  Detail & Related papers  (2025-12-01T02:52:33Z)
• Learning to Cover: Online Learning and Optimization with Irreversible Decisions [50.5775508521174]
  We define an online learning and optimization problem with discrete and irreversible decisions contributing toward a coverage target.<n>In each period, a decision-maker selects facilities to open, receives information on the success of each one, and updates a classification model to guide future decisions.<n>The goal is to minimize facility openings under a chance constraint reflecting the coverage target, in an horizon regime characterized by a large target number of facilities.
  arXiv  Detail & Related papers  (2024-06-20T23:00:25Z)
• Resampled Confidence Regions with Exponential Shrinkage for the Regression Function of Binary Classification [0.0]
  We build distribution-free confidence regions for the regression function for any user-chosen confidence level and any finite sample size based on a resampling test.<n>We prove the strong uniform consistency of a new empirical risk based approach for model classes with finite pseudo-dimensions and inverse Lipschitz parameterizations.<n>We also consider a k-nearest neighbors based method, for which we prove strong point boundswise on the probability of exclusion.
  arXiv  Detail & Related papers  (2023-08-03T15:52:27Z)
• Optimal PAC Bounds Without Uniform Convergence [11.125968799758436]
  We provide optimal high probability risk bounds through a framework that surpasses the limitations of uniform convergence arguments. Our framework converts the leave-one-out error of permutation invariant predictors into high probability risk bounds. Specifically, our result shows that certain aggregations of one-inclusion graph algorithms are optimal.
  arXiv  Detail & Related papers  (2023-04-18T17:57:31Z)
• Variance-Dependent Regret Bounds for Linear Bandits and Reinforcement Learning: Adaptivity and Computational Efficiency [90.40062452292091]
  We present the first computationally efficient algorithm for linear bandits with heteroscedastic noise. Our algorithm is adaptive to the unknown variance of noise and achieves an $tildeO(d sqrtsum_k = 1K sigma_k2 + d)$ regret. We also propose a variance-adaptive algorithm for linear mixture Markov decision processes (MDPs) in reinforcement learning.
  arXiv  Detail & Related papers  (2023-02-21T00:17:24Z)
• DeepStrip: High Resolution Boundary Refinement [60.00241966809684]
  We propose to convert regions of interest into strip images and compute a boundary prediction in the strip domain. To detect the target boundary, we present a framework with two prediction layers. We enforce a matching consistency and C0 continuity regularization to the network to reduce false alarms.
  arXiv  Detail & Related papers  (2020-03-25T22:44:48Z)

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.