{"id":"008a0bd3-8d00-4c8d-8032-6565c94bafd9","arxiv_id":"2505.19001","paper_version":2,"verdict":"REJECT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":4,"one_line_summary":"DARTH learns to predict a query's current recall during HNSW/IVF search and stops early at a user-specified target, achieving speedups up to 14.6x on HNSW and 41.8x on IVF, yet 13-15% of queries miss the target.","lead":"DARTH is a system that stops approximate nearest-neighbor searches early once a machine-learned model predicts the user's target recall has been reached, giving large speedups on HNSW and IVF indexes. A generalist should care because it attacks the practical pain of tuning ANN search parameters for a desired recall, but the paper's own data show 13-15% of queries still miss the declared target.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Paper's own evaluation reports ~15% of queries terminating below Rt (Fig 7, Sec. 4.2.3) and nonzero RQUT, while Sec. 2.3 promises recall at least Rt with high probability; no confidence bound or safety margin is defined for the stopping rule.","rationale":"The reader's weakest assumption identifies the recall predictor's generalization as the crux; my analysis agrees and sharpens it: the failure is not merely generalization to OOD queries but the absence of any calibration or confidence interval around the point prediction used for the stopping decision. The paper's own Figure 7 and Section 4.2.3 quantify approximately 15% of queries terminating below R_t on the default workload, and Figure 13 shows nonzero RQUT for DARTH even relative to the plain-index ceiling. Because the headline contribution is 'declarative recall' and the objective in Section 2.3 includes 'with high probability,' this documented miss rate is a direct contradiction unless 'high probability' is allowed to be as low as 0.85, which is never stated. The paper is otherwise a careful empirical systems contribution with public code, extensive datasets, and useful comparisons; the issue is specifically that the central guarantee is overclaimed. A revised claim framed as average recall, or the addition of a calibrated safety margin with quantified miss probability, would substantially address the concern. My verdict therefore remains aligned with the reader's REJECT: no change is needed to the reader's assessment.","tokens_in":29331,"tokens_out":3820,"duration_ms":26349,"concrete_test":"Run DARTH on 10 independent 1K-query workloads, freshly sampled from the same benchmark query sets, for SIFT100M and DEEP100M at k=50 and R_t in {0.90, 0.95}; record the fraction of queries whose final result set has recall below R_t and the minimum recall achieved. If any workload has more than 1% of queries below R_t, the stated 'with high probability' guarantee is falsified as written. Optionally, repeat the experiment with a validation-calibrated stop threshold R_t + delta; if RQUT drops to near zero while speedups remain, the flaw is repairable, but as published the claim needs revision.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim depends on a threshold decision: DARTH stops when the GBDT point prediction R_p is at least R_t, and the paper asserts this delivers recall >= R_t with high probability for each query. That inference requires the predictor's errors at the decision boundary to be negligible in both directions, especially overestimation of true recall, because overestimation causes premature termination below target. The reported predictor quality (MAE around 0.027, R2 around 0.88, Table 5) does not support such a per-query guarantee: an average error of a few recall points at the boundary directly translates into a material fraction of under-target results. The paper's own Figure 7 and Section 4.2.3 state that roughly 15% of queries do not meet the target on the default SIFT100M workload, and Figure 13 shows nonzero RQUT for DARTH on hard workloads. Section 2.3 defines the objective as achieving recall at least R_t 'with high probability' but never quantifies that probability, and Section 1 claims DARTH 'is always able to meet the user-declared recall targets.' These statements are internally inconsistent with the reported measurements. As published, the evidence supports DARTH as a strong average-recall optimizer, not as a declarative per-query recall guarantee. This is a load-bearing concern because the entire framing and headline contribution is the declarative guarantee; without it, the paper reduces to an empirical early-termination heuristic with good average behavior.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"DARTH proposes to augment HNSW and IVF searches with a GBDT-based recall predictor that is invoked at adaptively chosen intervals; the search terminates as soon as the predicted recall reaches a user-declared target R_t. The paper claims that this is the first declarative-recall solution via early termination, that it meets targets 'always' or 'with high probability,' and that it does so with speedups up to 14.6x for HNSW and 41.8x for IVF while performing about 5% more distance calculations than a per-query oracle optimum. The evaluation covers five datasets, recall targets 0.80-0.99, varying k, noisy and out-of-distribution workloads, and multiple quality measures including RQUT, RDE, NRS, P99, and Worst 1%.","tokens_in":29659,"tokens_out":7147,"duration_ms":64913,"significance":"If the per-query declarative guarantee were established, DARTH would be a significant contribution: it directly targets a practical pain point of ANNS parameter tuning, adapts to per-query hardness, and its speedup claims are substantial. The engineering is careful: the code is public, training-data generation takes minutes, the adaptive interval method reduces predictor calls to 6-11 per query, and the near-optimal distance-calculation claim in Figure 8 is well supported. However, as presented, the evidence supports an effective average-recall early-termination optimizer rather than a declarative per-query recall guarantee. The paper's own data show a material fraction of queries terminating below R_t, which is the load-bearing gap. The novelty claim depends on the guarantee, so resolving this gap is essential.","major_comments":[{"comment":"The paper's central guarantee is not delivered by the reported experiments. Section 1 states that DARTH 'is always able to meet the user-declared recall targets,' and Section 2.3 defines the objective as achieving recall at least R_t 'with high probability' without quantifying that probability. Section 4.2.3 and Figure 7 report that roughly 15% of queries terminate below R_t on the default SIFT100M workload, and Figures 13 and 20 report nonzero RQUT values for noisy and OOD workloads. These statements are internally inconsistent. The authors must either (a) define a formal coverage guarantee such as P(recall >= R_t) >= 1 - delta, calibrate the stopping rule to satisfy it, and report achieved coverage across all workloads, or (b) explicitly re-scope the contribution to average-recall optimization and remove the 'declarative' and 'always' claims.","section":"Sections 1 and 2.3 vs. Section 4.2.3 and Figure 7"},{"comment":"The stopping rule is a point-prediction threshold: DARTH terminates when the GBDT prediction R_p is at least R_t. With predictor MAE around 0.027 and R^2 around 0.88 (Table 5), errors at the decision boundary are common enough that a material fraction of queries terminate below target, as Figure 7 shows. No analysis quantifies the probability of overestimation at the boundary, and no safety margin or uncertainty estimate is used. The manuscript needs either a calibrated lower confidence bound on recall as the stopping criterion, or an explicit bound on the under-coverage probability; otherwise the connection between 'predicted recall >= R_t' and 'true recall >= R_t' is unsupported.","section":"Section 3.2.1 and Algorithm 1, lines 24-31"},{"comment":"For the T2I100M OOD workload, the predictor achieves MSE=0.029, MAE=0.079, and R^2=0.54. The text claims that DARTH 'consistently meets and surpasses all recall targets' (Figure 18a), but Figure 20 shows nonzero RQUT and even acknowledges that LAET achieves lower RQUT at R_t=0.95. With a predictor of this accuracy, the per-query guarantee is particularly implausible. Please report exact RQUT and achieved recall distributions for every R_t and k on T2I100M, and reconcile these numbers with the declarative-guarantee claim.","section":"Section 4.2.9 and Table 5"},{"comment":"The robustness comparison for noisy queries is informative, but the claim that DARTH 'reaches recall very near to the declared R_t across the entire range of noise values' is only meaningful in the regime where R_t is attainable. Figure 11 shows the plain-HNSW maximum recall falling below 0.90 for noise above roughly 10-12%, so for higher noise levels the declared target cannot be met by any method. The paper should state the attainable-recall condition explicitly in the main text and report RQUT separately for the attainable and unattainable regimes, since the latter cannot by construction satisfy the declared target.","section":"Section 4.2.7 and Figure 11"}],"minor_comments":[{"comment":"The x-axis label 'GLOVE100' is inconsistent with the dataset name GLOVE1M used in Table 2 and elsewhere.","section":"Section 4.2.2, Figure 6"},{"comment":"The y-axis label 'MSE (10^2)' is ambiguous; the MSE values discussed in the text are around 0.003, so the plot scale and the parenthetical factor should be clarified.","section":"Section 4.1.1, Figure 3"},{"comment":"The adaptive interval formula should specify how non-integer values of p_i are handled, since Algorithm 1 uses 'i_dis mod p_i' and p_i is described as a number of distance calculations.","section":"Equation (1)"},{"comment":"Calling DARTH 'essentially parameter-free' is misleading: i_pi and m_pi are set from training-query statistics, and the GBDT hyperparameters (100 estimators, learning rate 0.1) are fixed choices. 'Heuristic-selected hyperparameters' would be a more accurate description.","section":"Section 3.2.2"},{"comment":"The sentence 'indicating that the majority of queries achieve a recall that surpasses, yet remains close to, the corresponding recall target, since roughly 15% of the queries do not meet the target' is confusing as written and should be rewritten; more importantly, the 15% figure should be reconciled with the guarantee claims made earlier in the paper.","section":"Section 4.2.3"},{"comment":"The comparison of 'queries DARTH can answer before LAET is tuned' is not a standard quality or speed comparison; the experimental protocol should state what setup costs are included for each method, including DARTH's 10K-query training-data generation and predictor training.","section":"Section 4.2.5 and Figure 9"}],"recommendation":"major_revision","confidential_remarks":"The paper is within the scope of a data-management venue and the experimental infrastructure is strong, but the headline claim of a declarative per-query recall guarantee is directly contradicted by the reported RQUT values and the 15% under-target fraction in Figure 7. I would encourage the editor to require either a calibrated coverage guarantee or an explicit re-scoping of the contribution before considering acceptance."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"DARTH is a solid empirical systems paper with an overclaimed headline. The new combination is real: a GBDT that predicts current recall during HNSW/IVF search, plus an adaptive invocation schedule for early termination. It works about as advertised on average, delivering speedups of 6-14x on HNSW and up to 41x on IVF while staying within about 5% of the per-query optimal distance count. The evaluation is extensive, the datasets are standard, the code is public, and the comparisons against REM and LAET are fair, including tuning overhead. That part deserves credit.\n\nThe soft spot is the central claim. Section 2.3 defines the goal as achieving recall at least Rt with high probability, and the Introduction says DARTH is always able to meet declared targets. Yet the paper's own Section 4.2.3 and Figure 7 report roughly 15% of default queries terminate below Rt, and Figure 13 shows nonzero RQUT on hard workloads. No confidence bound is quantified, no safety margin is defined, and the predictor's MAE of about 0.03 means boundary errors translate directly into under-target results. The stress-test note holds up on reading: the evidence supports DARTH as a strong average-recall optimizer with better tail behavior than the competition, not as a per-query declarative guarantee.\n\nThe adaptive interval formula (Eq. 1) is presented without derivation. It is plausible, but the linear dependence on (Rt - Rp) is not justified beyond intuition. That is a minor point compared with the guarantee gap.\n\nThe reader's REJECT is slightly harsh because the empirical work is strong and the fix might be as simple as rewording the claim, adding a calibrated safety margin, or reporting a statistical guarantee over a validation set. But the load-bearing flaw is real: the headline contribution as written is not supported by the paper's own measurements. I would send this to peer review, with the expectation of major revision. It deserves serious referee time; the method is novel and the experimental practice is above average. A revised version that either quantifies the guarantee, adds a margin, or repositions the contribution as average-recall optimization would be acceptable.","headline":"A well-executed empirical early-termination method whose own data contradict the headline declarative-recall guarantee: ~15% of queries miss the target and no confidence bound is given.","tokens_in":30193,"tokens_out":1557,"would_cite":true,"duration_ms":17073,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"DARTH terminates ANN searches early, per query, the moment a trained model predicts the user's target recall has been reached, cutting search time by up to 14.6x on HNSW and 41.8x on IVF while meeting the declared recall target.","keywords":["approximate nearest neighbor search","declarative recall","early termination","HNSW","IVF","gradient boosting","recall prediction","query hardness"],"falsifier":"Run DARTH with a target recall of 0.90 on a held-out query workload that includes 20% Gaussian-noise-corrupted queries and compute the fraction of queries whose true recall falls below 0.90 (RQUT). If that fraction exceeds a user-specified threshold (e.g., 5%) for a workload where the plain index can reach 0.99 recall on every query, the early-termination guarantee would be violated.","tokens_in":1736,"feed_emoji":"⚡","tokens_out":2159,"duration_ms":36018,"temperature":0.7,"pith_summary":"DARTH claims that approximate nearest neighbor search can honor a user-declared recall target, such as 0.90, without per-dataset parameter tuning by stopping each query at the moment its recall reaches the target. The method integrates an early termination loop into popular ANNS algorithms like HNSW and IVF, driven by a Gradient Boosting Decision Tree that predicts current recall from search-progress and nearest-neighbor-distance features. Because each query stops at its own predicted crossing point, easy queries terminate early while hard queries search longer, adapting to query hardness automatically. The authors report that on five standard datasets DARTH meets or exceeds targets such as 0.80-0.99 with average speedups of 6.8x for HNSW and 13.6x for IVF, while performing on average only 5% more distance calculations than the per-query optimal stopping point. The appeal is that applications declare the quality they need and get it without experimenting with algorithm-specific parameters.","feed_headline":"Ann search stops when recall target is met, per query","feed_subtitle":"A trained predictor triggers early termination, cutting HNSW time up to 14.6x and IVF up to 41.8x.","key_machinery":"The load-bearing component is the recall predictor: a GBDT model (100 trees, trained with LightGBM in about 1-5 minutes) that takes eleven input features -- three index features ($n_{step}$, number of distance calculations, number of result-set inserts), three nearest-neighbor distance features (first, closest, and k-th/furthest NN distances), and five NN distance statistics (average, variance, median, 25th and 75th percentiles) -- and outputs an estimate $\\hat{R}$ of the current recall. The other key mechanism is the adaptive prediction interval formula $pi = mpi + (ipi-mpi)\\cdot(R_t - \\hat{R})$, which shrinks the interval between predictor calls as the predicted recall nears the target, balancing prediction overhead against termination accuracy.","core_discovery":"DARTH establishes that declarative recall in ANNS can be achieved at run time by early termination, rather than by offline tuning of index or search parameters. Its central claim is that a small set of search features -- the search step count, number of distance calculations, insertion count, and statistics of the distances of the nearest neighbors found so far -- suffice to train a GBDT that accurately estimates a query's current recall at any point during the base-layer search. The search stops as soon as the predicted recall reaches the target $R_t$, with the prediction invoked at adaptively chosen intervals so that the model is consulted more frequently as the predicted recall approaches the target. The authors claim this is the first early-termination method that natively supports any target recall attainable by the index, requires no hyperparameter tuning (a heuristic sets the interval parameters from training queries), and remains robust for harder and out-of-distribution query workloads, in contrast to fixed-parameter competitors.","pith_inferences":["A natural extension the authors do not explore is using the same predictor to serve multiple recall targets simultaneously, since a single invocation supports all $R_t$ values below the predicted recall; the query could return different result sets to different consumers with different targets.","One could test whether the feature set transfers across datasets out-of-the-box: if a predictor trained on one dataset's queries generalizes to another index built on the same data distribution, the per-dataset training cost could be amortized further.","The adaptive interval formula is linear in $(R_t - \\hat{R})$; an asymmetric or learned schedule might reduce the observed miss rate without increasing the number of predictor calls.","The 5%-above-optimal distance count is an average; for queries where the predictor is overconfident, the method stops below the target, so production deployments would likely combine DARTH with a small safety margin on the target or a fallback completion policy."],"forward_implications":["Applications can specify a recall target directly, so tuning effort shifts from per-dataset parameter search to a one-time predictor training on about 10K sample queries.","Search performance automatically concentrates effort on hard queries; easy queries stop early, so average latency drops while worst-query recall quality stays close to the target.","Because the termination decision is per-query, the method can be layered on existing HNSW and IVF implementations with only a few lines of search-loop modification, and the same feature set extends to other graph-based ANNS methods.","The near-optimal distance count (5% above the per-query optimal) implies that, on average, the gain from early termination is close to the theoretical best for the tested workloads.","The method's robustness on noisy and out-of-distribution queries suggests that declarative recall could be offered as a service-level objective in production vector databases without re-tuning per workload shift."],"supporting_citations":[{"why":"Defines the HNSW graph algorithm and its efSearch parameter; DARTH modifies its base-layer search loop.","marker":"[62]"},{"why":"Provides the FAISS library and the IVF index implementation that DARTH integrates with for the IVF experiments.","marker":"[29]"},{"why":"LightGBM is the specific GBDT library used for the recall predictor, chosen for its single-input inference speed.","marker":"[58]"},{"why":"The learned adaptive early termination method (LAET) is the main early-termination baseline that DARTH compares against and improves upon.","marker":"[60]"},{"why":"Supplies the SIFT dataset and the standard benchmark query workloads used to train and evaluate the predictor.","marker":"[56]"},{"why":"VDTuner is the representative declarative-recall by parameter-tuning baseline that DARTH outperforms without tuning.","marker":"[101]"}],"fun_headline_variants":["Stop ANN search when recall target is met, per query","DARTH predicts recall, stops search early per query","Early termination per query: DARTH hits recall targets, cuts time","Adaptive early stop: DARTH meets recall targets, speeds ANNS","Per-query recall prediction enables early termination in ANN search"],"cache_read_input_tokens":32256,"weakest_assumption_plain":"The recall predictor trained on 10,000 sample queries must generalize well enough to every future query -- including harder and out-of-distribution ones -- that stopping when the predicted recall reaches the target actually means the true recall has reached it.","fun_headline_variants_meta":{"raw":{"variants":["Stop ANN search when recall target is met, per query","DARTH predicts recall, stops search early per query","Early termination per query: DARTH hits recall targets, cuts time","Adaptive early stop: DARTH meets recall targets, speeds ANNS","Per-query recall prediction enables early termination in ANN search"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000247,"raw_usage":{"total_tokens":1562,"prompt_tokens":983,"completion_tokens":579,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":599,"completion_tokens_details":{"reasoning_tokens":492}},"tokens_in":599,"tokens_out":579,"duration_ms":5769,"temperature":1.0,"reasoning_tokens":492,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T14:21:44.189578+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run DARTH with a target recall of 0.90 on a held-out query workload that includes 20% Gaussian-noise-corrupted queries and compute the fraction of queries whose true recall falls below 0.90 (RQUT). If that fraction exceeds a user-specified threshold (e.g., 5%) for a workload where the plain index can reach 0.99 recall on every query, the early-termination guarantee would be violated.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The learned adaptive early termination method (LAET) is the main early-termination baseline that DARTH compares against and improves upon."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Supplies the SIFT dataset and the standard benchmark query workloads used to train and evaluate the predictor."},{"cited_title":"VDTuner: Automated Performance Tuning for Vector Data Management Systems","cited_arxiv_id":"2404.10413","evidence_quote":"VDTuner is the representative declarative-recall by parameter-tuning baseline that DARTH outperforms without tuning."}],"review_version":1}