Filtered ANN as a Phase Transition: When Selectivity-Estimation Error Causes Plan Regret Madhulatha Mandarapu∗
Sandeep Kunkunuru†
arXiv:2606.16341v1 [cs.LG] 15 Jun 2026
VaidhyaMegha Private Limited, India https://samyama.ai/ June 2026
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 arg max 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 logwidth equal to the multiplicative estimation error ε and height equal to the local cliff |V ′ (s⋆ )| ε; 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 sc ≈ 0.83/M for graph √ degree M (corpus-size independent). Criticality exists only under a constrained budget B < kn. Under pre-registered decision rules we confirm, on synthetic sweeps and real SIFT1M, that regret concentrates ∼ 290× 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.1
1
Introduction
Production vector search rarely runs unconstrained: a query asks for the k nearest vectors among those satisfying a predicate P (e.g. category=’shoes’ AND price<100). The predicate’s selectivity s = |XP |/n (the fraction of the n-vector corpus passing P ) spans near-0 to near-1, and the right execution strategy moves with it [Patel et al., 2024, Gollapudi et al., 2023, Simhadri et al., 2024]—bad estimates yield bad plans, the vector-search echo of relational query optimization [Leis et al., 2015]: pre-filter (materialize XP , then search within it) wins at low s; post-filter (run unfiltered ANN, drop violators) wins at high s; and an in-filter traversal that respects P during search targets the middle. A deployed system must estimate s and pick a strategy—exactly the access-path-selection problem of Selinger et al. [1979], now over a recall/latency objective. Vespa compares an estimated ∗
[email protected] [email protected] 1 https://github.com/samyama-ai/filtered-ann-regret †
1
hit-ratio against two thresholds [Vespa Team, 2023]; AlloyDB switches strategy mid-query on a bad estimate; and a recent learned planner predicts the plan from predicate statistics [Gan and Wang, 2026]. Strategy selection from an estimate is, in short, established practice. What is not established is a quantitative account of when, how badly, and how universally a wrong estimate hurts. We provide one, by recognizing the structure underneath: filtered-ANN strategy selection is a phase-transition system. Selectivity is an order parameter; the strategies are phases; and—this is the organizing observation—estimation error causes regret only in the critical regions around the phase boundaries. Deep inside a phase the best strategy dominates by a wide margin, so even a badly wrong estimate picks correctly (regret ≈ 0); near a boundary the two strategies are nearly tied, so a small error flips the choice and pays the local cliff. Robustness is criticality. Contributions. 1. A phase-diagram model of filtered-ANN strategy selection whose two boundaries have closedform locations from independent mathematics: the post-filter cliff at s ≈ k/K from order statistics (§3), and the in-filter cliff at sc ≈ 0.83/M from site percolation (§3, §5)—empirically corpus-size-independent, refining the folklore log n/M . 2. A criticality law (§4): selection regret is a wedge of log-width ε (the multiplicative estimation ⋆ error) and height |V ′ (s⋆ )| ε; the flip-margin 1/|V ′ (s √ )| is a condition number [Mandarapu and Kunkunuru, 2026]. A constrained-budget law B < kn delimits when any of this matters. 3. A finite-size scaling collapse (§5): across two decades of corpus size and all error magnitudes, regret curves collapse onto one universal wedge—selection regret is scale-invariant, to our knowledge a new observation for vector search. 4. An honest model-mismatch result (§5): a real approximate index does not mis-locate the boundary (the criticality picture holds on real ANN), but a biased cost model opens a persistent miscalibration band that estimation-error robustness cannot remove. Everything is validated on synthetic sweeps and real SIFT1M under pre-registered decision rules. We claim a characterization, not a new index or planner; §6 credits the substantial prior art this builds on.
2
Problem and Model
A query is (q, P, k): return the k vectors nearest q among XP = {x : P (x)}, with s = |XP |/n. We measure quality by recall@k at a fixed compute budget B (distance evaluations, hardwareindependent), and define strategy-selection regret as the recall@k lost by the chosen strategy relative to the oracle-best strategy under the true s. Write M (a, s) for the recall of strategy a ∈ {pre, post, in} at selectivity s. A planner sees an estimate ŝ = s · Q (a multiplicative error; ε = | ln Q| is the log error, the q-error of Moerkotte et al. [2009]) and picks aŝ = arg maxa M (a, ŝ); the oracle uses the true s. The regret is ∆R = M (a⋆ (s), s) − M (aŝ (ŝ), s) ≥ 0. Strategy objectives under budget B. Pre-filter materializes XP (cost ∝ sn): exact when sn ≤ B, else a random B-subset is scanned, giving M (pre, s) = min(1, B/(sn)), decreasing in s and indifferent to any correlation between P and q. Post-filter examines the unfiltered top-K (we identify the budget with the candidate-list size, K = B) and keeps the eligible ones, giving M (post, s) increasing in s (§3). The value gap V (s) = M (pre, s) − M (post, s) changes sign at a boundary s⋆ . 2
3
The Phase Diagram
Post-filter cliff (order statistics). Rank the corpus by distance to q; the unfiltered top-K is a prefix of that ranking, and the true filtered top-k are the first k eligible points. Under an uncorrelated predicate each ranked point is eligible i.i.d. with probability s, so the eligible count in the top-K is E ∼ Binomial(K, s), and because a prefix recovers the first min(k, E) eligible points exactly, E[min(k, Binomial(K, s))] M (post, s) = , (1) k a sigmoid in s with knee at s ≈ k/K (mean eligible Ks = k). Eq. (1) is exact for the uncorrelated model, independent of geometry; it is our reproduction gate. In-filter cliff (percolation). A graph index (HNSW/Vamana [Malkov and Yashunin, 2020, Subramanya et al., 2019]) is navigable as a whole, but restricting greedy search to the eligible nodes XP is site percolation: keeping an s-fraction of a degree-M navigable graph, a giant connected component—hence a reachable target—survives only above a threshold sc . The connectivity folklore reads sc ∼ log n/M ; we measure the giant-component (navigability) threshold and find sc ≈ 0.83/M , independent of n (§5). The relevant random-graph theory is that of k-nearest-neighbor / geometric graphs [Penrose, 2003]. Constrained budget. Pre-filter √ is exact for s ≤ B/n and post-filter saturates for s ≳ k/B; these “good” regions√overlap iff B ≥ kn. So a second transition, in the budget, separates a free-lunch regime (B ≥ kn: both √ strategies near-perfect over a band, estimation error harmless) from a contested regime (B < kn: a gap where neither end-strategy is good—the literature’s “middle regime”). Criticality, and everything below, lives in the contested regime.
4
Regret Is Critical
A threshold planner picks pre iff ŝ < s⋆ , so it mis-picks iff s and ŝ = sQ straddle s⋆ , i.e. iff | ln s − ln s⋆ | < ε on the appropriate side. Hence: Proposition 1 (Flip-margin law). To first order near a boundary s⋆ , the mis-pick (flip) region has log-width equal to the estimation error ε, and the regret inside it is ∆R(s) ≈ |V ′ (s⋆ )| | ln s − ln s⋆ |, rising to a peak ≈ |V ′ (s⋆ )| ε. The half-width of the band in which a unit log-error is dangerous is the flip-margin 1/|V ′ (s⋆ )|. Width is set by the estimation error; height by the boundary sharpness |V ′ (s⋆ )|. The flip-margin is exactly the per-decision condition number of the sibling cardinality-estimation study [Mandarapu and Kunkunuru, 2026]: its smooth-argmin condition number reappears here as the local theory of each phase boundary, while percolation and order statistics supply the global phase structure—an average-case companion to worst-case robust query processing [Haritsa, 2020]. Two consequences we test: (i) interiors are safe (∆R ≈ 0); (ii) rescaling x = (ln s − ln s⋆ )/ε and y = ∆R/(|V ′ (s⋆ )| ε) should collapse all curves—across error magnitudes and corpus sizes—onto one universal wedge.
5
Experiments
Setup. All hypotheses, thresholds, and decision rules were frozen before any results (a dated, pre-data amendment sharpened the flip-margin prediction). The controlled n-sweep uses 3
clustered-Gaussian corpora (only n varies); SIFT1M [Jégou et al., 2011] is the real-geometry anchor. Post-filter recall is averaged over random predicate draws (a single √ draw on clustered data is overdispersed versus Eq. (1)); budgets are in the contested regime B < kn; k = 10; statistics use ≥ 1000 query samples per cell. Code, data scripts, tests (29), and the pre-registration are public. H0 / H2: criticality. Eq. (1) reproduces on real rankings (gate passed). The regret is sharply critical (Fig. 1): at n ∈ {105 , 106 , 107 } and on real SIFT1M, interior mean ∆R = 0.0005, a ∼ 290× concentration at the boundary, one-sided flip-width linear in ε (slope 0.97), and peak √ ∝ |V ′ (s⋆ )| ε (Spearman ρ = 1.0) —confirming Proposition 1. The crossover scales as s⋆ ∼ 1/ n (0.010 → 0.0032 → 0.0010); SIFT1M lands on the synthetic n = 106 point.
Figure 1: The two phases (left) and the regret double-wedge (right): regret concentrates at s⋆ and is ≈ 0 elsewhere; over/under-estimation each open a danger zone on one side. A near-boundary mis-pick costs up to ∼ 0.35 recall@10. H3: scaling collapse. Under the Proposition 1 rescaling, regret curves from all (n, Q) cells collapse onto one universal wedge (Fig. 2): within-bin RMSE 0.015 (≤ 0.05), a 15.7× reduction in inter-curve spread, over two decades of n. Selection regret is scale-invariant.
4
Figure 2: Finite-size scaling collapse. Left: raw regret wedges differ in width/height across error magnitude and n. Right: rescaling by ε and |V ′ (s⋆ )|ε collapses all of them onto one universal curve. H1b: percolation. Building a navigable small-world graph (nearest-neighbor plus long-range links, so it is one component at s = 1) and measuring the giant-component fraction of G[XP ] across n ∈ {104 , 3·104 , 105 } × M ∈ {8, 16, 24, 32}, the in-filter cliff is a sharp percolation transition at sc ≈ 0.83/M , independent of n (Fig. 3; fit slope in ln M is −0.91, in ln ln n is −0.20, R2 = 0.998). This refines the pre-registered log n/M to the giant-component law that actually governs navigability. In the phase diagram the in-filter boundary is thus a horizontal line at s ≈ 0.83/M , while the post √ cliff (k/K) and the crossover (1/ n) move with scale.
Figure 3: The in-filter cliff is a site-percolation transition. Left: sc vs degree M on log–log, all corpus sizes on the 0.83/M line. Right: sc · M is flat in n. Model mismatch (beyond the frozen tests). Is the wedge an artifact of a perfect-model threshold selector? We test with a real approximate HNSW post-filter and with a controlled cost-model bias b (Fig. 4). The real index does not mis-locate the boundary: at ef= B its induced 5
crossover matches the analytic one to within grid resolution, so the criticality picture holds on real ANN. But a biased model (s⋆ off by ±20–40%) opens a persistent miscalibration band—regret present even at ε = 0 (a perfect per-query estimate), peak ∆R ≈ 0.13–0.34—that robustness to estimation noise cannot fix. There are thus two failure modes: the transient ε-wedge at the boundary, and a persistent calibration band from model bias.
Figure 4: Left: a real approximate HNSW post-filter tracks the analytic model; the crossover does not move (no leak). Right: a +30% cost-model bias opens a persistent regret band at the boundary, present even with a perfect per-query estimate.
6
Related Work and Novelty
Prior art (credited, not claimed). The three strategies and the hard middle regime are established [Patel et al., 2024, Gollapudi et al., 2023, Zuo et al., 2024, Yao et al., 2025, Simhadri et al., 2024]; selectivity-threshold strategy selection—including two-threshold (hysteresis) selection— is deployed [Vespa Team, 2023, Wang et al., 2021, Gan and Wang, 2026]; and graph connectivity under node deletion (M ≳ log n/s) is folklore [Gollapudi et al., 2023, Penrose, 2003]. We originate none of these. Our delta (modest, conceptual). (i) The quantitative criticality of selection regret and the flip-margin law (Proposition 1)—error-sensitivity made precise, which we did not find published; (ii) the finite-size√scaling collapse showing selection regret is scale-invariant; (iii) the constrainedbudget law B < kn delimiting when estimation error matters; (iv) the percolation in-filter law sc ≈ 0.83/M tied to strategy regret, and the model-mismatch result separating the transient wedge from a persistent calibration band. The lens—estimation error → decision regret → regime structure—is shared with our cardinality-estimation study [Mandarapu and Kunkunuru, 2026], of which this is the vector-search instance.
7
Limitations and Honest Findings
The regret experiment uses a threshold/cost-based selector; given such a selector the wedge’s support is partly definitional, which is exactly why we ran the model-mismatch test—it shows the wedge is real on approximate ANN and that the larger, persistent danger is model calibration, not estimation 6
noise. We characterize two phases (pre/post) for the regret experiment and the in-filter phase structurally; folding all three into one regret selector, the full adversarial correlated-predicate sweep, and a derived hysteresis rule are future work. This is a characterization of when an accuracy proxy tracks plan quality, not a new index or planner, and the novelty is correspondingly modest (§6).
8
Conclusion
Filtered-ANN strategy selection is a phase-transition system. Selectivity-estimation error causes plan regret only in the critical regions around phase boundaries whose locations follow from percolation and order statistics, whose regret obeys a flip-margin (condition-number) law, and whose curves collapse onto one scale-invariant wedge. The danger that robustness cannot reach is cost-model calibration. We hope the pre-registered, reproducible harness is useful to the systems that make this choice millions of times a second.
References Zhuocheng Gan and Yifan Wang. Efficient filtered-ANN via learning-based query planning. arXiv preprint arXiv:2602.17914, 2026. Siddharth Gollapudi, Neel Karia, Varun Sivashankar, Ravishankar Krishnaswamy, Nikit Begwani, Swapnil Raz, Yiyong Lin, Yin Zhang, Neelam Mahapatro, Premkumar Srinivasan, Amit Singh, and Harsha Vardhan Simhadri. Filtered-DiskANN: Graph algorithms for approximate nearest neighbor search with filters. In Proceedings of the ACM Web Conference (WWW), 2023. doi: 10.1145/3543507.3583552. Jayant R. Haritsa. Robust query processing: Mission possible. Proceedings of the VLDB Endowment, 13(12), 2020. doi: 10.14778/3415478.3415561. Hervé Jégou, Matthijs Douze, and Cordelia Schmid. Product quantization for nearest neighbor search (ANN_SIFT1M dataset). http://corpus-texmex.irisa.fr/, 2011. Viktor Leis, Andrey Gubichev, Atanas Mirchev, Peter Boncz, Alfons Kemper, and Thomas Neumann. How good are query optimizers, really? Proceedings of the VLDB Endowment, 9(3):204–215, 2015. doi: 10.14778/2850583.2850594. Yu A. Malkov and D. A. Yashunin. Efficient and robust approximate nearest neighbor search using hierarchical navigable small world graphs. IEEE Transactions on Pattern Analysis and Machine Intelligence, 42(4): 824–836, 2020. doi: 10.1109/TPAMI.2018.2889473. Madhulatha Mandarapu and Sandeep Kunkunuru. When does q-error predict plan regret? three regimes of cardinality-estimation error, 2026. arXiv preprint; code at https://github.com/samyama-ai/ ce-metric-eval. Guido Moerkotte, Thomas Neumann, and Gabriele Steidl. Preventing bad plans by bounding the impact of cardinality estimation errors. Proceedings of the VLDB Endowment, 2(1):982–993, 2009. doi: 10.14778/ 1687627.1687738. Liana Patel, Peter Kraft, Carlos Guestrin, and Matei Zaharia. ACORN: Performant and predicate-agnostic search over vector embeddings and structured data. In Proceedings of the ACM on Management of Data (SIGMOD), 2024. doi: 10.1145/3654923. arXiv:2403.04871. Mathew Penrose. Random Geometric Graphs. Oxford University Press, 2003. doi: 10.1093/acprof:oso/ 9780198506263.001.0001.
7
P. Griffiths Selinger, M. M. Astrahan, D. D. Chamberlin, R. A. Lorie, and T. G. Price. Access path selection in a relational database management system. In Proceedings of the ACM SIGMOD International Conference on Management of Data, 1979. doi: 10.1145/582095.582099. Harsha Vardhan Simhadri, Martin Aumüller, Amir Ingber, Matthijs Douze, George Williams, Magdalen Dobson Manohar, Dmitry Baranchuk, Edo Liberty, Frank Liu, Ben Landrum, et al. Results of the big ANN: NeurIPS’23 competition. arXiv preprint arXiv:2409.17424, 2024. Suhas Jayaram Subramanya, Devvrit, Rohan Kadekodi, Ravishankar Krishnaswamy, and Harsha Vardhan Simhadri. DiskANN: Fast accurate billion-point nearest neighbor search on a single node. In Advances in Neural Information Processing Systems (NeurIPS), 2019. Vespa Team. Query time constrained approximate nearest neighbor search. https://blog.vespa.ai/ constrained-approximate-nearest-neighbor-search/, 2023. Jianguo Wang, Xiaomeng Yi, Rentong Guo, Hai Jin, Peng Xu, Shengjun Li, Xiangyu Wang, Xiangzhou Guo, Chengming Li, Xiaohai Xu, et al. Milvus: A purpose-built vector data management system. In Proceedings of the ACM on Management of Data (SIGMOD), 2021. doi: 10.1145/3448016.3457550. Mingyu Yao, Qiyu Zhang, Yuxiang Liu, Wei Yang, Pengjie Zhao, Ziqi Wei, and Gao Cong. UNIFY: A unified index for range-filtering approximate nearest neighbor search. Proceedings of the VLDB Endowment, 18, 2025. Chaoji Zuo, Miao Qiao, Wenchao Zhou, Feifei Li, and Dong Deng. SeRF: Segment graph for range-filtering approximate nearest neighbor search. In Proceedings of the ACM on Management of Data (SIGMOD), 2024. doi: 10.1145/3639324.
8