{"id":"07509fe7-d5b8-4c70-a832-2cfc9f250d9c","arxiv_id":"2412.10701","paper_version":1,"verdict":"CONDITIONAL","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":5,"one_line_summary":"New threshold estimation methods combining quantile precomputation with early termination and index lookups improve top-k score estimates, cutting the gap to the ideal MUF by large fractions on standard and learned sparse indexes.","lead":"This paper proposes new methods to estimate the score of the k-th best search result before running the full query, making search query processing faster. The methods improve on existing quantile-based estimates, especially for long queries and for newer learned sparse indexes, at some extra memory and time cost.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Safety of Combine Scores/Lookups depends on non-negative term scores; this is unstated and fails for standard QLD log-likelihood, one of the paper's four rankers.","rationale":"The reader's weakest_assumption is the right one. The safety of the entire quantile-plus-prefix framework reduces to the inequality Σ_{t∈s} sc(t,d) ≤ Σ_{t∈q} sc(t,d) for any subset s of the query q. That inequality is immediate for non-negative term scores and false in general for signed scores. The paper's Section III presents Combine Scores and Adding Lookups as safe without stating this condition. This is not merely a formal nicety: the standard QLD score is a sum of log probabilities, whose per-term values are negative. If the authors used PISA's standard QLD scorer, Q4_k's max-over-subset estimate would not be a lower bound and the reported MUF would mix overestimates into a measure that excludes them. If instead they used a positive reparameterization, that is an undocumented modeling choice that affects every claimed safety result. The concrete check settles which case holds. I do not see a reason to reject the paper: BM25 and DeepImpact/DocT5Query impacts are non-negative, and the MUF gains there are large enough to survive the omitted sign assumption. But the safety guarantee and the QLD experiments are conditional, exactly as the reader's CONDITIONAL verdict states.","tokens_in":12085,"tokens_out":13420,"duration_ms":136243,"concrete_test":"Inspect the QLD scorer used in the code (PISA 'ql' scorer) and dump per-term impact values for a sample of postings. Then run Q4_k and the proposed method on the QLD index with k=10 and k=100 over the 10k TREC queries, comparing each estimate to the exact top-k threshold computed by a safe disjunctive algorithm. If any estimate exceeds the exact threshold, the zero-overestimate claim is false for QLD; if all impacts are non-negative, add the explicit assumption and re-run the same check to verify.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Section III describes Combine Scores and Adding Lookups as safe lower-bound estimators. The proof obligation is: for every docID d appearing in a prefix, the accumulated score (sum of retrieved term scores) must not exceed sc(q,d). This holds only if all term impacts sc(t,d) are non-negative; otherwise missing terms can only lower the true total, so a partial sum can be an overestimate. The paper never states this assumption. It matters beyond theory: QLD is one of the four rankers in Figures 6 and 9. With the standard Dirichlet query-likelihood score sc(q,d)=Σ_t log((tf+μP(t|C))/(|d|+μ)), every per-term contribution is negative, so max-over-subset quantile estimates are upper bounds, not lower bounds, and the zero-overestimate claim cannot hold as stated. If the implementation uses a positive reparameterization (e.g., moving the doc-length prior out of the per-term impact), that reparameterization must be stated and its effect on the precomputed postings documented. As written, the safety guarantee—and therefore the MUF comparison, which excludes overestimates—is conditional on an unverified sign assumption.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies top-k threshold estimation, i.e., estimating the score of the k-th highest document for a disjunctive query, and proposes three enhancements over quantile-based baselines: Remove Duplicates, Combine Scores, and Adding Lookups, plus an optional random-sampling wrapper. The methods store prefixes of high-scoring documents for query-term subsets and combine scores with accumulator structures and inverted-index lookups. The evaluation on ClueWeb09B and MSMARCO under BM25, QLD, DocT5Query, and DeepImpact reports MUF improvements (e.g., from 0.917 to 0.986 for k=10 on ClueWeb09B, and from 0.786 to 0.953-0.971 for long queries), reduced space for practical configurations, and faster MaxScore query processing when the estimates are used as initial thresholds.","tokens_in":12301,"tokens_out":12920,"duration_ms":125274,"significance":"If the safety guarantee holds, the paper offers a practical advance in threshold estimation, with a clear algorithmic idea and an unusually broad experimental matrix spanning two datasets and four ranking functions, including learned sparse indexes. The lower-bound arguments for Remove Duplicates and Combine Scores are clearly reasoned under the standard non-negativity assumption, and the paper is the first to evaluate threshold estimation on DocT5Query and DeepImpact indexes, which is a useful contribution for the learned-sparse-retrieval community. The main gaps are that the non-negativity hypothesis underlying the safety proof is never stated, and the evaluation omits a standalone sampling baseline and observed overestimate rates for sampling variants; both are needed to fully support the paper's central claims.","major_comments":[{"comment":"The zero-overestimate guarantee for the prefix-based methods requires the implicit assumption that every per-term impact sc(t,d) is non-negative. This assumption is not stated in Section II or III, and it fails for the standard Dirichlet query-likelihood scorer sc(q,d)=sum_t log((tf_{t,d}+mu P(t|C))/(|d|+mu)), where each term contribution is negative for typical parameters. With negative term impacts, a partial sum over a subset of query terms can exceed the full query score, so the accumulated estimate can overestimate the true threshold. Since QLD is one of the four rankers in Figures 6 and 9, and MUF is by definition averaged only over queries that do not overestimate, the QLD results are not interpretable as reported. The authors must either state the non-negativity assumption and verify it for each of BM25, QLD, DocT5Query, and DeepImpact, or document the exact positive reparameterization of QLD used in their implementation, and they should report observed overestimation rates for QLD.","section":"Section III (Combine Scores and Adding Lookups), Figures 6 and 9"},{"comment":"The experiments compare only against the Q4_k quantile baseline, not against a standalone random-sampling estimator, even though Section II presents sampling from [11] as a competitive state-of-the-art method and the abstract explicitly positions the work relative to sampling-based methods. Because the claimed contribution is to go beyond quantile methods against the state of the art, the omission of a sampling baseline leaves the relative claim unsupported. At minimum, the sampling-integrated variant should be compared with plain sampling at the same target overestimation probability, and the observed overestimate rate should be reported for both.","section":"Section IV (comparison protocol)"},{"comment":"When the sampling wrapper is used, MUF values are reported without any table of observed overestimation rates. MUF is defined as an average over queries that do not overestimate, so a high MUF can coexist with a nontrivial overestimate rate; the paper currently only states the a priori target probability of 0.01% used to choose k'. Reporting the observed overestimation rate for each sampling configuration is necessary to judge the accuracy/safety trade-off and to compare fairly with the zero-overestimate prefix-based methods.","section":"Section IV (Figures 5, 8, and 9)"}],"minor_comments":[{"comment":"The acronym MUF is defined both as 'Mean Under prediction Fraction' and later as 'Mean Underestimation Rate'; please use one consistent definition and expansion.","section":"Section II"},{"comment":"The table header contains 'Clueweb09a'; this should be 'ClueWeb09B'.","section":"Table I"},{"comment":"The statement that 'precise definitions of these configurations will be made available as part of the dataset release' gives no artifact identifier or URL; please include the configuration parameters in the paper or a supplement for reproducibility.","section":"Section IV-B"},{"comment":"There are small typos: 'ALLookups' should be 'All lookups', and the table captions say 'in nanosecond' where 'nanoseconds' is intended.","section":"Section IV (setup and Tables II-III)"},{"comment":"The text says the BM25 ClueWeb09B speedup is 'more than 800 us', but the table row shows 7626-6833=793 us; please correct the rounding or the text.","section":"Section IV (Table IV)"},{"comment":"Adding error bars or confidence intervals for the MUF values would help assess the stability of the reported differences, particularly in Figure 5 where some curves are close.","section":"Figures 1-9"}],"recommendation":"major_revision","confidential_remarks":"I do not see a circularity problem: Q4_k is the natural published baseline from the authors' own prior work, and the reported improvements are not algebraically forced. The main risk is the unstated non-negativity assumption for term impacts, which is easy to fix by stating it and either verifying it for QLD or documenting a positive reparameterization. The paper is within scope for an IR systems venue, but the safety claim and the missing sampling comparison should be addressed before publication."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Dear Colleague,\n\nThis is a solid, incremental paper on top-k threshold estimation. The headline result is real: by combining quantile prefixes with score accumulation and index lookups, they push MUF from about 0.89–0.92 up to 0.98–0.99 for k=10 on BM25, and the effect survives on learned sparse indexes like DeepImpact. The paper is honest that the final method is essentially the early-termination idea from [20] applied to threshold estimation; that does not make the contribution invalid, just modest.\n\nWhat is genuinely new is the first systematic evaluation of threshold estimation on learned sparse indexes, across four ranking functions (BM25, QLD, DocT5Query-expanded BM25, DeepImpact). The experimental work is thorough: two datasets, a practical space-reduction section, actual CPU timings, and a MaxScore integration that shows a real, if small, end-to-end speedup. The Remove Duplicates and Combine Scores intermediates are simple extensions of quantile stores, and the paper does not oversell them; the lookups component is the workhorse.\n\nThe soft spots are real but not disqualifying. First, the safety argument for Combine Scores and Lookups assumes non-negative term impact scores, and the paper never says this. Standard QLD with Dirichlet smoothing assigns negative per-term scores, so for one of the four rankers the lower-bound claim does not hold as written unless the implementation uses a positive reparameterization. The authors need to state the assumption, or explain the reparameterization, before the safety guarantee can be checked. Second, there are no error bars or significance tests; the reported MUF differences are point estimates. Third, despite sampling being cited as competitive, there is no standalone sampling baseline in the comparison; the hybrid is evaluated, but not pure sampling. Fourth, no code or configuration files are released, although the text says precise definitions will be part of a dataset release.\n\nNone of these sink the central empirical claim for BM25 and DeepImpact, where term scores are non-negative. The paper is a competent, useful advance in a well-studied subfield, and the learned-sparse evaluation will be cited. It deserves a serious referee; the main revisions are to clarify the sign assumption, add some measure of variance, and include a pure sampling baseline.\n\nRecommendation: send to peer review.","headline":"Solid, incremental paper: the MUF gains are real, especially via lookups, and the learned-sparse evaluation is new, but the safety argument silently assumes non-negative term scores and QLD breaks that assumption as stated.","tokens_in":12849,"tokens_out":3250,"would_cite":true,"duration_ms":29537,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"By merging precomputed per-subset score prefixes and performing bounded index lookups, top-k threshold estimation lifts MUF from 0.917 to 0.986 on ClueWeb09B for k=10, and the same methods improve learned sparse indexes.","keywords":["top-k threshold estimation","quantile methods","learned sparse indexes","Mean Under-prediction Fraction","MaxScore query processing","inverted index lookups","prefix merging","BM25"],"falsifier":"Run Combine Scores with lookups on an index whose scoring function contains a negative term weight, compare each estimate against an exact top-k computation, and check whether any estimate exceeds the true k-th score; even one overestimate refutes the safety claim. For the standard non-negative scorers, instrument the algorithm and count overestimates over the TREC Terabyte query set; the paper's claim is zero overestimates for the non-sampling variants, so a single observed overestimate would also be a falsifier.","tokens_in":11881,"feed_emoji":"🔍","tokens_out":7667,"duration_ms":63057,"temperature":0.7,"pith_summary":"This paper tries to establish that top-k threshold estimation — predicting the score of the k-th ranked document before running the query — can be made far more accurate than quantile-based methods by spending a little extra time and space on document-level information. Starting from precomputed per-term and per-subset quantile scores, the authors store sorted prefixes of the top documents for each selected term subset, then merge those prefixes while combining per-term scores and performing a bounded number of inverted-index lookups for missing scores. On ClueWeb09B with k=10, the mean under-prediction fraction (MUF) improves from 0.917 with the best quantile method to 0.986 with an access budget of 1k and 100 lookups; on queries with six or more terms it improves from 0.786 to 0.953–0.971. The same recipe works on learned sparse indexes built with DocT5Query expansion and DeepImpact, where score distributions differ strongly from BM25. If the claim holds, query processors such as MaxScore can start from a much tighter initial threshold and answer disjunctive top-k queries faster without risking overestimates.","feed_headline":"Search threshold estimates jump from 91.7% to 98.6% of ideal","feed_subtitle":"Merging precomputed term-score prefixes with index lookups also speeds up learned sparse search.","key_machinery":"The load-bearing object is a budgeted prefix-merge estimator over precomputed subset prefixes. For frequent term subsets (singles, pairs, and some triples) the index stores a conjunctive top-scoring prefix: each entry is a docID plus the term scores for every term in the subset, sorted by total subset score. At query time, the estimator scans these prefixes up to an access budget ab, accumulates combined scores per docID, and then performs up to lb lookups into the inverted index to fill in missing term scores; the result is backed up by the best quantile lower bound. The merging step removes duplicate docIDs and the lookup step recovers contributions from terms whose subsets were not stored, which is what turns a coarse quantile bound into a near-exact threshold. The whole construction inherits the safety of quantile lower bounds as long as all term impact scores are non-negative.","core_discovery":"The central discovery is that the accuracy lost by quantile methods is recoverable information: the identity of the documents behind the stored threshold scores and the way their term-level contributions add up. Quantile methods keep only one number per term subset; this paper keeps, for each selected subset, a sorted prefix of its highest-scoring documents together with all per-term scores, and turns threshold estimation into a budgeted merging problem. A query estimate is obtained by walking these prefixes in decreasing total score, accumulating per-document scores in a hash table, removing duplicate documents, and optionally looking up missing term scores in the inverted index; the k-th highest accumulated score is the answer. Because every stored subset is contained in the query, each partial sum is a lower bound on that document's full query score, so the estimate is safe — it never exceeds the true threshold, provided term scores are non-negative. The experiments show this closes most of the gap to the ideal MUF of 1.0, with the largest gains on long queries and on learned sparse indexes.","pith_inferences":["The paper leaves implicit that the method effectively converts threshold estimation into a budgeted top-k execution over compressed per-subset lists, so any future improvement in accumulator-based top-k merging should transfer directly to estimation accuracy at fixed budgets.","Because pairs dominate the gains and triples/quadruples add little, a plausible extension is adaptive subset selection: choose prefix types based on query-length distribution and available space rather than all co-occurring subsets from a log.","The success on DeepImpact suggests the technique may extend to other learned sparse models with query-dependent weights, such as SPLADE or uniCOIL, once their query-time weights are decomposed into per-term impacts; the paper notes they require additional ideas but does not test them.","One could test a per-query adaptive lookup budget that allocates lb according to query length or number of available prefixes, since the paper shows long queries benefit most and lookup cost per estimate is only 20–40 nanoseconds."],"forward_implications":["For k=10 on ClueWeb09B with BM25, MUF improves from 0.917 (Q4_k) to 0.986 with ab=1k and lb=100, and MaxScore average query time drops from 7626 to 6833 microseconds; for k=100 the time drops from 10024 to 9155 microseconds.","On long queries with six or more terms, where quantile methods degrade most, the k=10 MUF jumps from 0.786 to 0.953 with ab=200 and to 0.971 with ab=500.","For learned sparse indexes, DeepImpact k=10 MUF improves from 0.885 to 0.952 and MaxScore time drops from 3668 to 3415 microseconds, so the approach transfers beyond BM25-style scores.","For large k (1000), small and medium prefix structures give little benefit alone, but adding sampling at s=0.02 or s=0.05 with a 0.01% overestimate target restores substantial gains.","Lookups matter more than duplicate removal or score combination: the biggest single jump in accuracy comes from performing inverted-index lookups, and lb at half of ab still gives decent results."],"supporting_citations":[{"why":"Supplies the quantile method Q4_k and the sampling baseline that define the accuracy bar the new methods are compared against.","marker":"[11]"},{"why":"Supplies the unsafe early-termination candidate-generation approach whose budgeted score accumulation the new estimators generalize.","marker":"[20]"},{"why":"Supplies the threshold-aggregation (TA) paradigm of combining sorted lists and random lookups underlying Combine Scores and Lookups.","marker":"[19]"},{"why":"Supplies the DeepImpact learned sparse index whose unusual score distributions the paper evaluates on.","marker":"[22]"},{"why":"Supplies the DocT5Query document expansion used to build one of the learned sparse indexes tested.","marker":"[21]"},{"why":"Defines the MUF evaluation measure and the similarity-score-prediction context that frames the problem.","marker":"[8]"},{"why":"Supplies the MaxScore algorithm whose query latency is measured with the new threshold estimates.","marker":"[2]"}],"fun_headline_variants":["Top-k threshold estimates hit 98.6% of ideal accuracy","Beyond quantiles: threshold estimation nears perfection","Safe merging boosts top-k threshold estimates to 98.6%","Learned sparse search gets faster with safer threshold guesses","New method closes gap to ideal top-k threshold estimation"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that all term impact scores are non-negative (and that every stored subset is contained in the query), so a sum over a subset of terms can never exceed a document's full query score; with negative term weights the accumulated estimate could overshoot the true threshold and the safe/no-overestimate property would collapse.","fun_headline_variants_meta":{"raw":{"variants":["Top-k threshold estimates hit 98.6% of ideal accuracy","Beyond quantiles: threshold estimation nears perfection","Safe merging boosts top-k threshold estimates to 98.6%","Learned sparse search gets faster with safer threshold guesses","New method closes gap to ideal top-k threshold estimation"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000665,"raw_usage":{"total_tokens":3033,"prompt_tokens":937,"completion_tokens":2096,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":553,"completion_tokens_details":{"reasoning_tokens":2015}},"tokens_in":553,"tokens_out":2096,"duration_ms":13762,"temperature":1.0,"reasoning_tokens":2015,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T15:42:15.811529+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Combine Scores with lookups on an index whose scoring function contains a negative term weight, compare each estimate against an exact top-k computation, and check whether any estimate exceeds the true k-th score; even one overestimate refutes the safety claim. For the standard non-negative scorers, instrument the algorithm and count overestimates over the TREC Terabyte query set; the paper's claim is zero overestimates for the non-sampling variants, so a single observed overestimate would also be a falsifier.","supporting_citations":[{"cited_title":"A comparison of top- k threshold estimation techniques for disjunctive query processing,","cited_arxiv_id":null,"evidence_quote":"Supplies the quantile method Q4_k and the sampling baseline that define the accuracy bar the new methods are compared against."},{"cited_title":"Fast first-phase candidate generation for cascading rankers,","cited_arxiv_id":null,"evidence_quote":"Supplies the unsafe early-termination candidate-generation approach whose budgeted score accumulation the new estimators generalize."},{"cited_title":"Optimal aggregation algorithms for middleware,","cited_arxiv_id":null,"evidence_quote":"Supplies the threshold-aggregation (TA) paradigm of combining sorted lists and random lookups underlying Combine Scores and Lookups."},{"cited_title":"Learning passage impacts for inverted indexes,","cited_arxiv_id":null,"evidence_quote":"Supplies the DeepImpact learned sparse index whose unusual score distributions the paper evaluates on."},{"cited_title":"From doc2query to doctttttquery,","cited_arxiv_id":null,"evidence_quote":"Supplies the DocT5Query document expansion used to build one of the learned sparse indexes tested."},{"cited_title":"Accelerated query processing via similarity score prediction,","cited_arxiv_id":null,"evidence_quote":"Defines the MUF evaluation measure and the similarity-score-prediction context that frames the problem."},{"cited_title":"Query evaluation: strategies and optimizations,","cited_arxiv_id":null,"evidence_quote":"Supplies the MaxScore algorithm whose query latency is measured with the new threshold estimates."}],"review_version":1}