Beyond Quantile Methods: Improved Top-K Threshold Estimation for Traditional and Learned Sparse Indexes

Jinrui Gou, Yifan Liu, Minghao Shao, Torsten Suel

Abstract

Modern search engines utilize pruning algorithms like WAND or MaxScore to efficiently retrieve top-$k$ results. These algorithms rely on a score threshold to skip irrelevant documents. However, initial thresholds are often zero, leading to slow "warm-up" phases. This paper introduces a suite of techniques that leverage precomputed document prefixes and strategic index lookups to estimate a tight, safe initial threshold. Our methods significantly outperform traditional quantile-based approaches, achieving a Mean Under-prediction Fraction (MUF) of over 0.98 and substantially reducing query latency.

Introduction

Efficient top-$k$ retrieval is a cornerstone of modern information retrieval. Algorithms such as WAND and MaxScore use a dynamic threshold—the score of the $k$-th best document found so far—to prune the search space. A higher initial threshold allows for more aggressive pruning from the start of the query. Traditional "quantile methods" precompute $k$-th highest scores for terms or pairs but are often too conservative. This paper addresses the gap between these loose estimates and the ideal threshold, particularly for long queries and modern learned sparse indexes.

Proposed Methods

We propose a hierarchy of estimation methods designed to be "safe" (never overestimating the true score) while maximizing the estimated threshold:

  1. Remove Duplicates: Instead of a single value, we store a prefix of the top-$k$ document IDs and scores for term subsets. Merging these prefixes and counting unique documents yields a tighter estimate.
  2. Combine Scores: By storing individual term scores within prefixes, we can sum scores for the same document across different subsets, further increasing the estimate.
  3. Strategic Lookups: This is our most impactful innovation. We identify promising candidate documents from prefixes and perform a limited number of lookups in the main index to retrieve missing term scores. Despite the perceived cost of random lookups, they are extremely fast relative to the pruning gains.
  4. Random Sampling: For large $k$, we apply these techniques to a sampled index and scale the results to maintain efficiency.

Experimental Evaluation

We evaluated our methods on ClueWeb09B (50M documents) and MSMARCO (8.8M passages) using traditional (BM25, QLD) and learned sparse indexes (DocT5Query, DeepImpact).

Key Insights

  • The Power of Pairs: As shown in Figure 1, moving from single-term to pair-based prefixes provides a significant boost in MUF. Triples and quadruples offer diminishing returns relative to the extra storage space required.
  • The Impact of Lookups: Lookups are the primary driver of accuracy. Figure 4 demonstrates how the "Full Lookup" method dramatically outperforms simpler prefix merging techniques like "Remove Duplicate" or "Combine Score."
  • Robustness to Learned Indexes: Our techniques are particularly effective for learned indexes like DeepImpact, which typically have different score distributions that challenge traditional pruning methods.
Comparison of the proposed hierarchy of methods: Remove Duplicate, Combine Score, and Full Lookup.

Results

On ClueWeb09B ($k=10$), our "Lookups" method achieved an MUF of 0.982, compared to 0.910 for the baseline quantile method. When integrated into MaxScore, this improved threshold reduced query processing time by over 800 microseconds, far exceeding the 200-microsecond overhead of the estimation itself.

Conclusion

By combining precomputed prefixes with strategic index lookups, we provide a highly accurate and safe top-$k$ threshold estimation. This approach significantly accelerates query processing across both traditional and neural sparse indexes, narrowing the gap to ideal pruning performance. Future work will explore adaptive prefix selection and applications in distributed search environments.

Summary updated

BibTeX
@inproceedings{gou2024beyond,
  author = {Jinrui Gou and Yifan Liu and Minghao Shao and Torsten Suel},
  title = {{Beyond Quantile Methods: Improved Top-K Threshold Estimation for Traditional and Learned Sparse Indexes}},
  booktitle = {IEEE Big Data},
  year = {2024},
  doi = {10.1109/bigdata62323.2024.10825349},
}
Figure