Graph-index search learns when to stop: CaST holds constrained vector search within 1.132× of its class optimum
Synopsis
Constrained vector search with per-category caps previously relied on a fixed visit budget or on stopping rules trained for average recall, neither of which guarantees an exact answer. CaST restricts stopping rules to a monotone class over a declared interface, calibrates them with fixed-sequence binomial tests, and derives a lower bound on the class-optimal cost via Lagrangian weak duality. On two datasets of one million items each, its replayed cost is at most 1.132 times the class optimum for risk levels 0.03 to 0.10 at 95% confidence, and at a 0.05 risk target its mean latency is lower than every other calibrated rule timed.
Interpretation
Constrained nearest-neighbor queries on graph indexes now have a calibratable early-termination rule that stops each query by its own search progress rather than giving every query one visit budget. A fixed visit budget must reach the quantile of completion times to be safe; on the HNSW graphs for Amazon and arXiv, the risk-calibrated budgets are 6,781 and 5,978 visits, 7.1 and 5.8 times the median completion time over 10,000 evaluation queries. At a 0.05 risk target, CaST averages 4,166 and 3,780 visits on Amazon and arXiv, against 6,789 and 5,987 for the fixed-budget rule, with both near the target failure rate.
The stopping rule reads only a declared interface: bucketed running minimum of a learned score plus a flag for whether the answer is full, with rules required to be monotone in those observations. Earlier learned early-termination methods target average recall, and high average recall does not guarantee a high probability of the exact constrained answer; DARTH at a 0.95 average-recall target returns the exact constrained answer for only 71% and 68% of queries. Over this monotone class, risk-constrained stopping becomes a linear program over an order polytope whose Lagrangian minimizers form a nested chain of staircases computed exactly by dynamic programming, then calibrated along the chain by fixed-sequence exact binomial tests.
The same structure yields a lower bound on the class-optimal cost, so a calibrated rule's cost can be compared with the best rule of its class rather than reported as a bare number. Earlier calibration methods control the risk of a selected parameter but give no lower bound on how much a better rule with the same risk and observations could save. For risk levels 0.03 to 0.10 at 87.5% joint confidence per setting, the maximum ratio per setting ranges from 1.082 to 1.128; at 95% confidence these maxima rise by at most 0.004, to 1.132.
Perspective
The results cover in-memory search on a single machine with unfiltered traversal and fixed capacity settings; the guarantees hold for queries drawn like the labeled samples, and a query shift or index update calls for recalibration on new calibration queries.
The class-optimal lower bound covers only rules restricted to the declared interface; a clairvoyant rule that knows each query's completion time is 2.8 to 3.3 times cheaper than the empirical class optimum at 0.05, which upper-bounds what richer observations could gain at the same checkpoints. On YFCC-10M, 3.9% of queries do not complete within 32,768 visits, so only risk levels 0.05 to 0.10 are evaluated there.