CS Paper Radar

Calibrated Early Termination with Bounded Optimality Gaps for Constrained Vector Search

Xinyu Zhang, Jingze Li, Baihua Zheng, Weiwei Sun

cs.DB cs.IRcs.LG ·submitted 2026-11-12 01:15 UTC · v1
theorycode/data

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.

Comment
14 pages, 5 figures, 3 tables. Code available at https://github.com/zhangshea/CaST

Closest papers

Nearest neighbours by meaning across the whole index.

Per-Query Recall Guarantees for Approximate Nearest Neighbor Search in Dynamic Vector Databases

cs.DB ·2026-11-05 ·Woong-Kee Loh, Suan Lee
similarity 0.65
Abstract · 66 pages, 15 figures, 19 tables. Extended version of a paper submitted to ICDE 2027

Vector search now runs as an operator inside database systems, where a missed neighbor makes a query answer wrong, yet approximate nearest neighbor (ANN) indexes are tuned only for a target average recall. Tuned to an average recall of 0.99, indexes left 5-19% of in-distribution queries and, without a query log, up to 99.6% of out-of-distribution queries below it (more under updates) and changed a top-5-tag aggregate over the results for up to 27% of queries. In the spirit of approximate query processing, we present PQR-Search, a $k$-ANN operator that guarantees $\Pr[\mathrm{Recall}(q) < τ] \le δ$ for every query and, for $τ< 1$, $\mathbb E[\mathrm{Recall}(q)] \ge τ$. The probability is over a random rotation inside the index alone, so no distributional assumption is needed, only that queries and updates do not depend on it, and the guarantee holds after insertions and deletions without retuning. PQR-Search prunes 1-bit codes of rotated IVF residuals with exact error quantiles and predicts its cost without data-fitted constants. On 20 datasets of up to 100M vectors, failure rates stayed at most $δ$ in every audit, including the NeurIPS'23 streaming runbook, and the aggregate changed in at most 0.04% of trials. The guarantee costs 2.5$\times$ the single-query latency of HNSW tuned as above and 1.3$\times$ lower batch throughput (geometric means). PQR-Search was 26$\times$ faster than FAISS exhaustive search in batch, faster than IVF with $n_{\rm probe}$ chosen afterwards to meet the target on every test query, and 27-76$\times$ faster than PUFFINN, which also guarantees per-query recall.

0.20

VADER: Filtered Vector Search with Declarative Recall

cs.DB ·2026-09-29 ·Manos Chatzakis, Duo Lu, Helena Caminal, Yannis Chronis, Fatma Özcan +5 more
top venue similarity 0.63
Abstract · This paper appeared in VLDB 2027

Approximate filtered vector search (FVS), a core operation in many data management tasks that combine structured data with vector embeddings, exhibits increased complexity due to the characteristics of filtering predicates. Each predicate is defined by selectivity (i.e., the fraction of vectors that satisfy the predicate) and correlation (i.e., the relationship between the filter and the vector space), which can significantly affect search difficulty even for the same query vector. This poses a key challenge for users aiming to integrate vector search with structured data, as efficient execution often requires extensive manual tuning of algorithm parameters. In this paper, we present VADER, the first approach that eliminates hyperparameter tuning by introducing declarative recall for approximate filtered vector search. With declarative recall, users specify a desired recall target, and VADER executes FVS queries to meet this target without requiring manual configuration. VADER achieves this by employing a filter-aware recall predictor that generalizes across varying selectivities and correlations without explicit tuning, and by performing early termination once the predicted recall reaches the user-defined target. Through extensive experimental evaluation, we show that VADER achieves near-optimal early termination, while providing significant speedups of up to 53% faster and improved result quality of 28% compared to the best-performing baseline.

0.29

Learning Query Encoders Can Be Hard Even When Vector Retrieval Is Geometrically Easy

cs.IR cs.LG ·2026-10-02 ·Anders Wikum, Nina Mishra, Amin Saberi, Tal Wagner
similarity 0.61
Abstract

Efficient vector retrieval requires both a corpus geometry that supports retrieving the right documents through vector similarity, and a query encoder that can embed queries near their desired documents in the embedding space. Recent work has studied geometric capacity through the lens of the minimum embedding dimension needed to realize all top-$k$ answer sets of $n$ documents. We study a different notion of geometric capacity--the maximum recall achievable for a frozen document index--and explore whether learned query encoders can reach this ceiling. On several real-world retrieval benchmarks, we show that retrieval quality of single-vector query encoders often lies far below what the document indices can support. Motivated by this observation, we give theoretical evidence that learning query encoders can be computationally hard. In particular, we construct a retrieval task that (1) admits a query encoder with perfect recall which is representable by a small one-hidden-layer ReLU network, but (2) any statistical-query learner (a class capturing learners that access training data through aggregate statistics) provably requires exponentially many statistical queries to achieve non-trivial recall advantage over the random baseline $k/n$. Taken together, our results suggest substantial unrealized geometric capacity in retrieval benchmarks and establish query encoder learnability as a possible barrier in embedding-based retrieval.

0.11

Learning How to Search for Plans with Exponentially Less Space

cs.AI ·2026-10-07 ·Dominik Drexler, Simon Ståhlberg, Markus Fritzsche, Blai Bonet
similarity 0.60
Abstract

Heuristic search for a plan can store exponentially many states, even when its heuristic is almost perfect. We instead learn search control, one specification per domain, written as an indexical policy: a generalized policy with registers that hold objects and modes that sequence its rules. We add the choose rule, which loads an object into a register and marks a backtracking point, where one candidate suffices; every other rule must work for all of its outcomes and needs no search. Our main result is that structural termination, which rules out infinite executions, also bounds every execution by a polynomial in the number of objects. A depth-first procedure then finds a plan in polynomial space, however large the state space, with no list of visited states. The cost is time, exponential only in the choice depth, the number of real choices along an execution. Any class that such a policy solves therefore lies in NP, and in P at constant choice depth. We learn these policies with a language model in a counterexample-guided loop that certifies termination, verifies the training tasks, and keeps the choice depth small. With the learned policies, the procedure solves 1,709 of 1,890 test tasks of the IPC 2023 Learning Track and the Autoscale Agile suite, more than LAMA, BFWS, and Levitron, and most of them within one second and 100 MiB.

0.32

Linear-Query Deterministic Approximation for Non-monotone Submodular Maximization under a Knapsack Constraint

cs.DS ·2026-09-22 ·Zihui Liu, Zhijie Zhang
similarity 0.60
Abstract · ISAAC 2026

Submodular maximization under a knapsack constraint (SMK) is a fundamental combinatorial optimization problem with broad applications across machine learning and data mining. Motivated by large-scale applications where query efficiency is paramount, we study non-monotone SMK and focus on deterministic algorithms with linear query complexity. Prior deterministic linear-query algorithms achieve at best a $1/5-\varepsilon$ approximation, falling short of the $1/4-\varepsilon$ ratio attainable by randomized algorithms. We close this gap by presenting a deterministic $(1/4-\varepsilon)$-approximation with $O(n\log^2(1/\varepsilon)/\varepsilon^2)$ queries. Our approach partitions the analysis based on the cost of the largest optimal element $r$: when the cost of $r$ is moderate, we refine the threshold-twin-greedy framework via residual-budget enumeration to tighten the analysis; when the cost of $r$ is large, we reduce the problem to bicriteria submodular maximization. As a secondary contribution, we obtain a $(1/2-\varepsilon, O(1/\varepsilon))$-bicriteria approximation with $O(n\log(1/\varepsilon)/\varepsilon^2)$ queries, improving over the previous $O(n^2/\varepsilon)$ query bound.

0.36

Post-Pruning vs. Early Stopping: Which Works Better for Link Prediction with AnyBurl?

cs.LO ·2026-10-21 ·Thomas Eiter, Davide Soldà, Hai Xia
similarity 0.60
Abstract

Rule-based link prediction combines symbolic and statistical artificial intelligence methods by inductively learning a set of rules from a knowledge graph (KG), with the aim of completing the graph when a query cannot be answered from the KG alone. Several systems have been proposed, and while they perform well on classical benchmarks, even compared with embedding-based systems, many of them produce a large number of rules. This compromises scalability in the query-answering phase, especially under strong hardware constraints. In this work, we investigate the behavior of AnyBurl, a state-of-the-art rule learner for link prediction, to determine whether running it for a given time and then pruning the learned rules yields better query-answering performance at test time than a simpler approach that stops rule generation earlier.

0.29

Canopy: Exploiting Piecewise Smooth Tree Priors for Multi-Fidelity Bandits

cs.LG cs.AI ·2026-09-24 ·Michael Jerge, Suman Jana
theory similarity 0.59
Abstract

Many LLM inference problems, including model routing, prefix-cache management, prompt trimming, and test-time search, can be viewed as optimization over a tree. This structure arises naturally from autoregressive generation: every prefix defines a node, and its continuations form a subtree below it. Internal nodes of the tree provide cheap but biased estimates of a region's value, while leaf evaluations are expensive but accurate. Hierarchical bandit methods can exploit this structure, but typically require a specific smoothness schedule to be specified in advance, even though real objectives are often only piecewise smooth and their optima may lie near sharp boundaries. We introduce CANOPY, a multi-fidelity tree bandit that learns where the smoothness prior is valid rather than assuming it globally. CANOPY uses cheap random-path probes to construct an online certificate of local aggregation bias, then directs expensive leaf evaluations toward cells where the certificate detects a smoothness violation. We prove fixed-budget and regret guarantees whose additional cost is additive in the number of discontinuities, recovering the smooth-tree rate when no violations are present and approaching structure-blind search as violations become dense. Across routing, top-$k$ identification, test-time search, caching, and prompt trimming, CANOPY consistently improves matched-budget performance, including $2.9\times$ higher top-10 recall on a 1000-model pool, $1.6\times$ more SWE-bench Verified issues resolved than best-of-$N$, and $3.6\times$ lower median time-to-first-token with prefix caching.

0.17

Less can be More: Relieving RAG Bottlenecks via Evidence Frontloading and Pressure-Adaptive Budgeting

cs.CL cs.IR ·2026-08-25 ·Weibin Cai, Reza Zafarani
similarity 0.59
Abstract

Existing methods for improving Retrieval-Augmented Generation (RAG) efficiency mainly optimize downstream LLM generation, such as context compression or serving optimization. However, RAG is an end-to-end system, and its bottleneck can shift between upstream reranking and downstream generation under different serving loads and reranking budgets.In this paper, we first empirically characterize this shifting-bottleneck behavior and show that upstream reranking can become the dominant bottleneck under high query rates or large reranking budgets. Reducing the reranking budget can relieve this bottleneck, but it may also drop supporting evidence and degrade recall. To address this problem, we propose \textbf{\textsf{PACE}} (\textbf{P}rioritized \textbf{A}daptive \textbf{C}overage of \textbf{E}vidence), a training-free framework that combines \textit{evidence frontloading} with \textit{pressure-adaptive budgeting}. \textsf{PACE} first reorders candidates by marginal evidence coverage, prioritizing documents that are query-relevant, complementary, and useful for forming multi-hop evidence chains. We show that this objective is monotone submodular, giving greedy selection a $(1-1/e)$ approximation guarantee. \textsf{PACE} then dynamically adjusts the reranking budget according to the relative pressure of the reranker and the LLM. Experiments on three multi-hop QA datasets and online serving simulations show that \textsf{PACE} improves evidence recall, reduces p95 latency under ranking-heavy workloads. More importantly, the two components together reveal that \textit{less can be more}: an evidence-dense top-ranked candidates enable higher final recall with fewer reranked documents.

0.36