One-sentence Summary

University of California at Santa Barbara proposes ASC, a two-parameter dynamic pruning scheme for cluster-based sparse retrieval that uses segmented maximum term weights to tighten rank score bound estimation and achieve probabilistic rank-safeness guarantees, improving relevance competitiveness while maintaining low latency on single-threaded CPUs as demonstrated on MS MARCO and BEIR benchmarks.

Key Contributions

• ASC is a two-parameter pruning control scheme for cluster-based sparse retrieval that skips index portions at cluster and document levels during inference to target high relevance competitiveness.
• It improves rank score bound estimation through cluster-level maximum weight segmentation and applies threshold-driven pruning with a probabilistic guarantee on rank-safeness competitiveness.
• Experiments on MS MARCO and BEIR show that ASC improves pruning accuracy and relevance competitiveness while delivering low latency on a single-threaded CPU.

Introduction

Fast and effective document retrieval matters for large-scale search and retrieval augmented generation, where sparse retrieval on CPUs offers an attractive low-cost alternative to dense approximate retrieval. Learned sparse models can be highly competitive, especially for out-of-domain search, but online inference still needs faster rank-score threshold pruning. Existing pruning methods such as MaxScore, WAND, and BMW are rank-safe, yet cluster-based bounds are often loose and threshold over-estimation can skip relevant documents without formal relevance safeguards. The authors introduce ASC, a two-parameter threshold control scheme that uses cluster-level maximum weight segmentation to sharpen cluster bounds and provide a probabilistic rank-safeness guarantee, enabling faster sparse retrieval while preserving high relevance.

Method

ASC Architecture and Retrieval Pipeline

The authors present a cluster-based approximate retrieval framework that reduces the cost of online search by making better pruning decisions at the cluster level. The method builds on a clustered inverted index in which a document collection is partitioned into $m$m clusters $C_i$Ci​, and posting lists are organized according to these clusters. During query processing, the system first estimates an upper bound for each cluster, orders the sparse clusters from the highest estimated bound to the lowest, and then traverses the clusters sequentially. At each visited cluster, the framework applies cluster-level pruning before entering document-level evaluation. If a cluster survives pruning, standard document-level skipping may still be used inside that cluster. This online workflow is governed by two parameters, $\mu$μ and $\eta$η, with $0 < \mu \leq \eta \leq 1$0<μ≤η≤1, which control aggressive skipping and probabilistic safety, respectively.

The overall online inference flow of the proposed scheme is shown in the framework diagram.

At the core of the baseline cluster-bound estimation is the cluster upper bound used by cluster-based Anytime Ranking. Given a query $Q$Q, the maximum possible rank score of any document in cluster $C_i$Ci​ is estimated as

where $w_{t,d}$wt,d​ is the weight of term $t$t in document $d$d. In standard cluster-based retrieval, a cluster may be skipped when this upper bound is not competitive with the current top-$k$k threshold $\theta$θ. A common relaxation is threshold over-estimation, where pruning uses an inflated threshold $\theta/\mu$θ/μ with $0 < \mu \leq 1$0<μ≤1. This allows the system to discard more low-scoring documents when the bound estimate is loose. However, uniformly applying over-estimation can be unsafe when the bound is already accurate, because relevant documents may then be incorrectly pruned.

The main weakness of the original cluster bound is that it can be overly loose when a cluster contains diverse document vectors. The term-maximum values are aggregated across all documents in the cluster, so the estimate can reflect the upper envelope of heterogeneous documents rather than the achievable score of any individual document. Reducing cluster size can improve tightness, but this introduces significant online overhead: more clusters require more bound computations, more maximum-weight lookups, and more derivation of essential query terms. Refer to the figure below, which compares bound tightness for different clustering-based retrieval schemes as the number of clusters changes.

The plotted tightness is the ratio between the actual maximum rank score in a cluster and the estimated cluster bound. A value closer to 1 means the bound is sharper, while a value closer to 0 means the bound is loose and pruning decisions are more conservative. The proposed method improves bound tightness by adding segment-level information to each cluster without materially increasing the number of clusters.

Segmented Cluster Maximum Weights and Two-Level Pruning

The proposed method segments each cluster into $n$n smaller groups during offline index construction. Let each cluster $C_i$Ci​ be divided into segments

using random uniform partitioning. For each segment, the index stores the maximum weight contribution of each query term within that segment. For query $Q$Q, the segment bound for segment $S_{i,j}$Si,j​ is

From these segment bounds, the framework derives two cluster-level summaries:

and

The maximum segment bound provides a tighter upper bound than the full-cluster $BoundSum$BoundSum because it restricts the term-maximum aggregation to a smaller document subset. The average segment bound provides additional information about the overall distribution of segment scores inside the cluster. Intuitively, if one segment has a high bound but most segments have much lower bounds, the cluster is more heterogeneous and the maximum bound may be less reliable. If the average segment bound is close to the maximum segment bound, the cluster is more internally consistent, and the bound estimate is likely tighter.

During query processing, the cluster is pruned when both segment-based conditions are satisfied:

and

The first condition uses $\mu$μ to allow aggressive skipping, similar to threshold over-estimation. The second condition uses $\eta$η to prevent overly aggressive pruning when the cluster as a whole appears promising. If a cluster is not pruned, document-level traversal continues, and a document $d$d may be skipped when its on-the-fly bound satisfies

Thus, $\mu$μ mainly controls cluster-skipping aggressiveness, while $\eta$η controls the safer threshold used for retaining potentially valuable clusters and documents. When $\eta = 1$η=1, the framework is designed to be probabilistically safe, relying on the uniform partitioning of documents into segments.

The indexed structure and pruning behavior can be understood through the cluster pruning example below.

The figure illustrates clustered posting lists for several query terms, together with segment-level maximum term weights. Each cluster contains multiple segments, and the relevant query term maxima from those segments are combined to estimate segment bounds. The example compares pruning decisions under different control settings. With a fixed current top-$k$k threshold, the method can decide whether a cluster should be pruned, and the same document-level threshold can also remove low-score documents inside retained clusters.

The stored segment maxima require extra index space, but the design keeps this overhead manageable by storing only nonzero maximum weights in sparse form. In practice, the segment maxima can be represented using compact quantized weights because their role is to guide pruning rather than to reproduce exact ranking scores.

Tightness-Aware Pruning Control

The segmented formulation is useful not only for producing tighter bounds but also for detecting when a cluster should not be pruned. The method observes that the gap between $MaxSBound(C_i)$MaxSBound(Ci​) and $AvgSBound(C_i)$AvgSBound(Ci​) serves as a practical indicator of bound reliability. When the maximum segment bound is much larger than the average segment bound, the cluster likely contains only a few high-scoring pockets, and the maximum bound may overestimate most documents in the cluster. In that situation, aggressive pruning guided by $\mu$μ is more acceptable. Conversely, when the average and maximum segment bounds are close, the cluster is likely internally consistent, and pruning would risk removing documents whose scores are uniformly close to the retained bound.

This behavior is reflected in the formal pruning property: cluster-level pruning should not occur when the estimated bounds are already tight. Specifically, pruning is avoided when either the maximum segment bound remains above the aggressive threshold, or the difference between the maximum and average segment bounds is small:

This condition ensures that clusters with high-quality bound estimates are less likely to be discarded merely because a small value of $\mu$μ makes the upper-bound threshold more restrictive. Refer to the figure below, which shows the relationship between bound tightness and the ratio $AvgSBound/MaxSBound$AvgSBound/MaxSBound.

As the ratio approaches 1, the estimated bound becomes tighter and more stable, and the cluster is increasingly unlikely to be pruned. The segmentation therefore acts as a diagnostic signal: it tells the system when aggressive skipping is appropriate and when the estimate should be trusted more conservatively. Since the underlying document-to-segment assignment is random uniform partitioning, each document within a cluster has an equal chance of falling into any segment. This supports the average segment bound as a statistically grounded indicator of the cluster’s overall score distribution, enabling the method to approximate rank-safe behavior while still allowing efficient cluster skipping.

Experiment

Experiments on MS MARCO, TREC, and BEIR with sparse retrieval models evaluate ASC’s cluster-segmented pruning against exact MaxScore, Anytime Ranking, and IOQP under controlled relevance-loss budgets. Results show ASC preserves effectiveness while substantially reducing latency, especially at small retrieval depths and when probabilistic cluster bounds are used. Additional tests confirm benefits across different sparse models, out-of-domain benchmarks, segmentation strategies, and combinations with early termination or static index pruning.

The example shows online cluster-level pruning decisions for four retrieval clusters under different bounds and threshold settings. With the same threshold, Anytime keeps three clusters, Anytime with mu equals 0.9 keeps two clusters, and ASC with mu equals 0.9 and eta equals 1 keeps clusters 2 and 4 while pruning clusters 1 and 3. The text recommends eta equals 1 for probabilistic safeness and varying mu from 1 to 0.5 to trade efficiency against effectiveness, while lower eta can reduce latency when relevance loss is acceptable. Pruning outcomes differ across Anytime, Anytime mu equals 0.9, and ASC for the same set of clusters, showing sensitivity to the pruning method. ASC can keep a different subset of clusters than the Anytime baseline, indicating that probabilistic cluster pruning can redirect retrieval work during online search.

The reported comparison of SPLADE based retrieval methods on MS MARCO passages shows the same relevance results across the listed top ten methods. The main differences are efficiency related, including latency and the reported cluster proportion. ASC has the fastest reported mean and 99th percentile latency while using a lower cluster proportion than Anytime Ranking. ASC preserves the same reported relevance results as exact search and other baselines while reducing latency. ASC reaches the lowest reported mean and 99th percentile latency among the compared SPLADE methods.

At fixed MRR@10 loss budgets, ASC provides the lowest absolute query latency among the compared methods, while keeping recall competitive as the allowed loss tightens. IOQP achieves the strongest recall at stricter loss levels, but its latency grows sharply under tighter budgets. Anytime-mu shows comparatively stable latency, yet remains much slower than ASC across the tested settings. ASC stays in the single digit millisecond latency range across all loss budgets. IOQP latency increases substantially as the allowed MRR@10 loss becomes smaller. Anytime-mu requires longer latency than ASC while not offering comparable recall gains.

Retrieval latency increases as the requested result depth grows, but ASC remains the fastest method under safe pruning across the tested depths. IOQP shows much higher latency at small depths, and the relative efficiency differences among methods generally decrease as depth increases. Allowing a small relevance-loss budget lowers latency for the unsafe pruning configurations, illustrating a tradeoff between speed and guaranteed retrieval quality. ASC has the lowest safe-pruning latency across shallow and deep retrieval settings. The relative efficiency gap between ASC and the compared baselines becomes smaller at larger retrieval depths. Unsafe pruning with a small loss budget can reduce latency compared with safe settings.

For sparse retrieval at depth 10 with no time budget, the same MRR and recall are retained across exact, MaxScore, Anytime, and ASC for both uniCOIL and LexMAE. ASC has the shortest mean retrieval time, showing that cluster-aware pruning can preserve retrieval quality while reducing CPU retrieval time. The speedup is especially useful for LexMAE, whose baseline retrieval costs are higher than those for uniCOIL. ASC keeps effectiveness aligned with other depth 10 methods for both tested sparse models. ASC provides the fastest retrieval among the compared no time budget methods. LexMAE starts from a higher baseline retrieval time and therefore shows a larger relative opportunity for acceleration.

Experiments evaluate online cluster-aware pruning on SPLADE retrieval with MS MARCO, examining pruning decisions, latency under fixed relevance-loss budgets, different retrieval depths, and sparse retrieval with uniCOIL and LexMAE. The results show that ASC makes different online pruning choices from Anytime baselines and can preserve reported relevance while reducing retrieval latency. Across settings, ASC remains the fastest or among the fastest methods, especially under safe pruning and shallow depths, while competing methods either incur higher latency or provide limited recall advantages under tighter loss budgets.