Calibrated Early Termination with Bounded Optimality Gaps for Constrained Vector Search

Xinyu Zhang, Jingze Li, Baihua Zheng, Weiwei SunarXiv 2026 · arXiv

Efficient vector search is the engine room of modern AI, powering everything from product recommendations to Retrieval-Augmented Generation (RAG). But there is a persistent tension: how do you stop a graph search early enough to save compute without sacrificing the accuracy of the results?

A new paper, "Calibrated Early Termination with Bounded Optimality Gaps for Constrained Vector Search," introduces CaST (Calibrated Staircase Termination). It moves beyond heuristic stopping rules to provide a framework that guarantees exact answers with a user-defined probability while staying remarkably close to the theoretical minimum search cost.

TL;DR

CaST is a principled framework for early termination in constrained vector search that guarantees an exact answer with probability $1-\varepsilon$. By framing the search for an optimal stopping rule as a linear program over an order polytope, the authors derive "staircase" rules that are within 13% of the theoretical class optimum and significantly faster than existing calibrated baselines.

What Problem Does This Paper Address?

Graph-based indexes like HNSW or DiskANN find the nearest neighbors of a query by traversing a proximity graph. In many real-world scenarios, these searches are constrained. For example, a travel site might want the 10 nearest hotels but limit the results to no more than two from the same hotel chain.

The search stops when a candidate list stops improving, but this offers no formal guarantee that the "exact" constrained answer has been found. Stopping too late wastes expensive CPU cycles; stopping too early leads to "risk"—the probability of returning an incorrect answer.

Existing "learned" termination methods typically target average recall, which is a poor proxy for the probability of getting the exact answer. Furthermore, even if a rule is calibrated to a specific risk level, we usually have no idea how much better a different rule could have performed. This paper tackles both: providing a risk guarantee and bounding the "optimality gap."

Figure 1: A constrained 2-NN query example showing how early termination can lead to incorrect results.

Methods

The authors' approach, CaST, relies on several clever mathematical insights:

  1. The Monotone Interface: Instead of letting a stopping rule see everything, they define a restricted "interface." The rule observes a running minimum of a learned score (indicating how likely the search is to be complete) and a flag indicating if the $k$ required items have been found.
  2. The Order Polytope: They restrict themselves to "monotone" rules—rules that are more likely to stop as the score decreases or the answer fills up. This constraint transforms the search for the best rule into a linear program over an order polytope.
  3. Staircase Rules: They prove that the optimal rules in this class are "staircase rules," where the stopping threshold for the score changes (usually relaxes) as the search progresses through checkpoints.
  4. Calibration via Binomial Tests: To ensure the $1-\varepsilon$ guarantee holds on unseen data, they use fixed-sequence binomial tests. This allows them to pick the best rule from a candidate chain while rigorously controlling the failure probability.
  5. Lagrangian Duality for Optimality Gaps: By using Lagrangian weak duality, they calculate a lower bound on the cost of any rule in their class. This lets them say, "Our rule costs $X$, and no rule in this class can cost less than $Y$," giving a concrete bound on how much room for improvement remains.
Fig. 2. Overview of the approach. FIT fixes the score model and the buckets of the declared interface. The monotone class yields a linear program over an order polytope, and SEL computes its nested chain of staircases. CAL selects ˆfm by fixed-sequence tests, and EVAL bounds its cost and the class optimum, which gives the ratio on the joint confidence event. Online, the search reads only the interface and a table of 2J thresholds.

Datasets

The authors evaluated CaST on four large-scale public corpora:

  • Amazon: 1M items (Sports and Outdoors reviews).
  • arXiv: 1M items (metadata snapshot).
  • YFCC-10M: 9.8M images (filtered search dataset).
  • YouTube-8M: 1M video features.

These datasets cover various embedding types (MiniLM, CLIP) and constraint types (category caps).

Key Insights and Ideas

  • Exactness vs. Recall: The paper shifts the goalpost from "high average recall" to "guaranteed exactness." This is crucial for applications where the "ground truth" constrained answer is the only acceptable result.
  • The Power of Monotonicity: By assuming that "better" observations should lead to a higher probability of stopping, the authors turn an intractable search space of $e^{266}$ possible rules into a structured optimization problem solvable via dynamic programming.
  • Data-Dependent Bounds: The optimality gap isn't a theoretical constant; it's calculated per dataset and risk level. This gives engineers a "confidence meter" for their search configuration.

Key Results

  • Near-Optimality: Across risk levels from 0.03 to 0.10, CaST's search cost was at most 1.132× the theoretical class optimum at 95% confidence.
  • Superior Speed: At a common risk target ($\varepsilon = 0.05$), CaST outperformed all other calibrated baselines, which were 4.8% to 45.5% slower in mean search time.
  • Robustness: The "staircase" shape of the rule proved more efficient than simple fixed budgets or single-threshold rules. It effectively "spends" its risk budget on the most difficult queries while terminating easy ones early.

Limitations and Future Work

  • Interface Dependency: The optimality gap is relative to the declared interface. If the features provided to the rule (the score model) are weak, the rule might be "optimal" within its class but still perform poorly compared to a rule with better features.
  • Labeling Cost: Calibration requires knowing the "completion time" (when the exact answer was first reached) for a set of validation queries, which requires expensive full-scan ground truth.
  • Future Directions: The authors suggest exploring richer interfaces (e.g., looking at the distribution of distances in the candidate list) and extending the framework to other types of approximate search beyond graph indexes.

Summary updated

Abstract

Vector search over learned embeddings is the retrieval layer of recommendation and retrieval-augmented generation, and many applications cap how many answer items one category may contribute. Graph indexes answer a query by best-first traversal, and where it stops determines its cost and whether its answer is exact. We study early termination for such constrained $k$-nearest-neighbor ($k$-NN) queries, with plain $k$-NN as a special case, and seek the cheapest stopping rule whose answer is exact with probability at least $1-\varepsilon$. Learned early-termination methods instead target average recall, which does not guarantee exact answers. Multiple testing can calibrate any parameterized stopping rule to our target, but it cannot tell how much a better rule with the same risk and observations would save. Answering this needs a lower bound on the optimum of a rule family too large to enumerate, valid for the query population. Our key idea is to declare the observations a rule may use and to consider every rule monotone in them. Risk-constrained stopping then becomes a linear program over an order polytope, whose Lagrangian minimizers form a nested chain of staircase rules computed exactly by dynamic programming. Fixed-sequence binomial tests along this chain calibrate our rule, CaST, whose failure probability is at most $\varepsilon$ with confidence $1-δ$. Lagrangian weak duality bounds the optimum of the declared class from below at all risk levels at once, without a union bound over the rules. On two datasets of one million items each, CaST replayed on logged searches costs at most 1.132 times the class optimum for risk levels from 0.03 to 0.10, at 95% joint confidence per setting. Larger savings thus need a rule outside the class. At a common risk target on held-out queries, CaST is faster than every other calibrated rule we time, which take 4.8% to 45.5% more mean time.
BibTeX
@misc{zhang2026calibrated,
  author = {Xinyu Zhang and Jingze Li and Baihua Zheng and Weiwei Sun},
  title = {{Calibrated Early Termination with Bounded Optimality Gaps for Constrained Vector Search}},
  year = {2026},
  eprint = {2611.16148},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.16148},
}
Figure