acceptodds
Under review as a conference paper at ICLR 2027

MultiHit principle for learned sparse retrieval: deterministic bounds on candidate volume and Top- survival

Abstract

Learned sparse retrieval such as SPLADE supports semantic search while retaining the efficiency of inverted indexes, but semantic expansion can make a query touch a large fraction of the corpus. We study whether the overlap structure across posting lists can be used as a filter to remove background documents before document scoring. We identify a MultiHit separation: as the required number of matched coordinates increases, the candidate set shrinks approximately exponentially while many highly ranked documents survive. This motivates an -of- filter that retains documents matching at least of the highest-weight query coordinates. Since SPLADE rankings are determined by weighted inner products rather than hit counts, however, it is nontrivial whether top-ranked documents still survive the filter. We characterize both sides of this separation using finite-corpus statistics. Intersection counts bound the candidate-set size without any distributional assumptions, while score-margin moments give lower bounds on overall Top- survival. We further formulate threshold selection as finite-sample risk control for future queries from the same distribution. Our end-to-end implementation on MS MARCO, DBpedia, and FiQA achieves – speedups over Naive, with substantially larger speedups in single-query latency over PISA, BMP, and Seismic when using 16 threads, while maintaining over 99% mean Top-1000 survival.

Primary area:
infrastructure, software libraries, hardware, systems, etc.
Keywords:
learned sparse retrieval, information retrieval, sparse representations, SPLADE

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_1dkDOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary
  • Introduce a-of-B filter: score only documents matching >=a terms of the top B query terms (sorted by weights). a is chosen from a small set of query.
  • Introduce Theorem 1: candidate-count lower/uper-bound from itersection totals
  • Introduce Theorem 2: lower bound on Top-K survival
  • Implement an engine that parallelize search within a query by scoring multiple doc tiles/blocks at once using multiple threads. The paper claims 1.47x-3.14x speed-up over Naive baseline implemented by the authors and 8–29× over baselines at 16 T/Q1 setting (1 query, 16 threads)
Critical strengths
  • The finding that increasing hit constraint can rapidly shrink the candidate set while still retain a good mount of top-k candidate is interesting.

  • The introduced filter is simple and easy to implement. It demonstrates a nice jump over the naive baseline.

  • Code is available at time of review.

Critical weaknesses
  • Unfair comparison: baselines (Seismic, BMP, PISA) are single-threaded per query. At 1 thread Seismic/BMP faster on MS MARCO. At 16T1Q (16 threads, 1 query), the proposed approach wins most likely just because it implements within-query parallelism while the baselines do not. Note that: under load, throughput-oriented serving engines typically run one query per core. Many engines implement single-threaded query processing algorithms by design choice, not because of incapability.

  • The comparison is done at one single operation point (k=1000 at high fidelity ~0.97-0.99), this make the comparison/conclusions biased to this one single data point. Suggest the authors to look at the Pareto-frontier curves to compare the methods at different efficiency/effectiveness trade-off points. One method performs well at k=1000 might not perform well at other top-k values.

Questions for authors
  • Q1: Seismic 16T/Q64 on Dev = 29.4 ms vs 4.29ms on TREC19, why is there a difference here?

  • Q2: Exhaustive Splade-v3 MRR@10 41.08 vs published ~40.2? Please explain

  • Q3: Please provide the comparison with Pareto-frontier (single-threaded and balanced T/Q)?

8 comments
AuthorsOpenReview ↗

Response to Weakness1 about Multithread: New Single-Thread Method

We sincerely thank the reviewer for pointing out the unfairness of comparing our 16T/Q1 implementation against retrieval engines that process each query using a single thread. Motivated by your criticism, we have completely removed multithreaded evaluations and related performance claims from the revised paper. Instead, we redesigned our index storage and introduced a new method, bitmap-MultiHit, repeating all system comparisons under a single thread (1T/Q1).

Bitmap-MultiHit now achieves the lowest single-threaded latency among all evaluated SPLADE retrieval methods, while preserving the original retrieval quality and maintaining substantial storage and memory advantages.

All methods use SPLADE-v3, Top-1000 retrieval, and 1T/Q1. Latency is measured in ms/query; F@1000 is reported as a percentage.

(a) MS MARCO

MethodDev Lat.Dev F@1000TREC19 Lat.TREC19 F@1000TREC20 Lat.TREC20 F@1000
Seismic (kNN=0)40.4299.6438.2099.5241.7299.52
Seismic-0 (bitmap)42.2699.6439.1099.5241.4699.52
Seismic (kNN=32)46.6799.8747.6999.7849.6499.81
Seismic-32 (bitmap)48.5399.8746.9199.7848.9399.81
BMP (b=8)37.6397.0439.2297.3439.8796.80
BMP (bitmap)37.8397.0437.8597.3438.9296.80
Naive174.37100.00171.20100.00174.39100.00
Naive (bitmap)109.11100.0087.51100.0088.34100.00
MultiHit58.3499.7360.44100.0060.1499.85
bitmap-MultiHit22.1999.7323.63100.0024.3499.85

(b) DBpedia-Entity

MethodLatencyF@1000
Seismic (kNN=0)40.3399.40
Seismic-0 (bitmap)41.7099.40
Seismic (kNN=32)57.0999.81
Seismic-32 (bitmap)56.4199.81
BMP (b=8)68.0596.75
BMP (bitmap)67.9896.75
Naive95.72100.00
Naive (bitmap)77.55100.00
MultiHit39.9599.39
bitmap-MultiHit18.0899.39

(c) FiQA

MethodLatencyF@1000
Seismic (kNN=0)14.2899.11
Seismic-0 (bitmap)14.0299.11
Seismic (kNN=32)33.6199.55
Seismic-32 (bitmap)33.5499.55
BMP (b=8)40.8598.12
BMP (bitmap)43.3298.12
Naive1.96100.00
Naive (bitmap)1.70100.00
MultiHit1.7999.13
bitmap-MultiHit0.7699.13

Why F@1000? Due to space limitations, we report F@1000, which measures the fraction of exhaustive SPLADE Top-1000 documents preserved by each method. It directly corresponds to our theoretical ranking-preservation objective and clearly distinguishes the methods.

Performance improvements. We retain the original Q1–Q3 parameter-selection strategy and operating points: (B,a)=(8,2)(B,a)=(8,2) on MS MARCO and DBpedia-Entity, and (10,2)(10,2) on FiQA. These parameters were not retuned for bitmap optimization, and retrieval quality remains unchanged.

Bitmap-MultiHit is 2.21–2.63× faster than the original MultiHit and 2.24–4.92× faster than bitmap-Naive. On MS MARCO and DBpedia-Entity, it outperforms Seismic (kNN=0) by 1.62–2.23× and BMP by 1.64–3.76×. On FiQA, it is 13.07× faster than PISA MaxScore, the fastest external baseline. TREC19/20 results are included in the revised manuscript.

Storage and memory. Bitmap optimization adds only 10–14% storage. Our index remains 2.14–9.17× smaller than Seismic-H and 2.16–2.78× smaller than BMP, while their peak RSS is 1.79–4.25× and 4.24–8.87× ours, respectively.

Implementation and ablation. We cache posting lists as bitmaps, count hits word by word, and represent candidates as masks. Scoring still processes nonempty tiles and maintains the global Top-1000. We also implement bitmap variants of Seismic and BMP: Seismic's visited hash set is replaced with a bitset indexed by vector offsets, and BMP uses a bitmap to skip empty score buckets.

Bitmap optimization accelerates MultiHit by 2.21–2.63× and Naive by 1.15–1.97×, but barely affects Seismic or BMP. This is because bitmap operations directly accelerate MultiHit's hit counting, whereas Seismic relies primarily on clustered traversal, summary pruning, and forward-index scoring, and BMP on score bounds and block processing.

More detailed results have been added to the revised PDF, and the corresponding code is being updated.

Bitmap-MultiHit also preserves the original filtering rule, theoretical motivation, and retrieval quality. We sincerely appreciate your criticism, which led to a substantial improvement in our implementation and evaluation method.

We hope these new results address your concern about the fairness and practicality of our system comparison and encourage you to reconsider your assessment.

AuthorsOpenReview ↗

Response to Weakness2 and Q3: Adding Pareto-frontier curves

We thank the reviewer for requesting Pareto-frontier comparisons. We have added a new subsection, "Efficiency–Quality Trade-off," and included the requested Pareto plots across five query sets in the revised manuscript.

For fairness, we follow the published Pareto evaluations of Seismic and BMP, using the same parameters and search ranges as their original experiments.

For MultiHit, we deliberately explore lower-quality operating points by fixing the original (B,a)=(8,2)(B,a)=(8,2) and truncating posting lists to 5–200 thousand entries, without applying Q1–Q3 to retune the parameters.

The new plots show that MultiHit achieves higher ranking quality at low latency across all five query sets, outperforming Seismic and BMP in the low-latency region.

Although the result seems good, this comparison is not entirely favorable to MultiHit. Posting-list truncation greatly changes the underlying data distributions, so the original (8,2)(8,2) is not necessarily optimal for these new settings. We intentionally avoid testset-specific retuning to maximize the Pareto frontier, since doing so would neither establish a generalizable parameter-selection rule nor further support our Q1–Q3 theory.

We emphasize that the requested Pareto-frontier comparison is an engineering evaluation, and is not related to our Q1--Q3 theoretical contributions. Our core MultiHit filter has only two parameters, (B,a)(B,a), whereas Seismic provides 6 tuning options, including n_postings, centroid_fraction, summary_energy, query_cut, heap_factor, and n_knn, and BMP exposes block size, early termination (α\alpha), query-term pruning (β\beta), and many other quantization options.

To keep our theoretical analysis simple and obtain direct theoretical guarantees (to our knowledge, no prior work on learned sparse retrieval jointly establishes theoretical bounds on candidate contraction and Top-K survival), we deliberately avoid adding generic optimizations, such as kNN graph expansion, vector quantization, clustering and so on. We just do not want to add them, rather than our method can not be combined with them.

We sincerely hope the reviewer will reconsider the assessment and update their rating according to our theory and the newly added experiments.

We inspected src/pylib/mod.rs, lines 664–709, in the historical GitHub commit (ba2a...), as well as the official pyseismic-lsr 0.5.2 source distribution. The batch_search() function contains the following code ...

Thanks for inspecting the code. Pls note that batch_search only parallelize across queries (one query/thread). Whether or not the implementation has other issues, your method uses multiple threads per query, so the comparison conflates algorithmic efficiency with parallelization strategy. You configuration also set number of threads > number queries which further amplifies this bias.

The sequence-length setting and FP16 model inference are most possible contributors to the observed differences. Given the time constraints of the rebuttal period and the cost of regenerating embeddings for the full corpus, we have not yet conducted controlled ablations to determine their individual contributions.

Thanks for your explanation. Please make sure you reproduce the same numbers in your next version.

Why F@1000? Due to space limitations, we report F@1000, which measures the fraction of exhaustive SPLADE Top-1000 documents preserved by each method. It directly corresponds to our theoretical ranking-preservation objective and clearly distinguishes the methods.

You can add multiple responses. I also suggest to add P50, P90 latency. Space limitation is not a good reason to not provide critical information.

Instead, we redesigned our index storage and introduced a new method, bitmap-MultiHit, repeating all system comparisons under a single thread (1T/Q1).

This is a new method that wasn't in the original manuscript. The rebuttal period is intended for authors to clarify and support the submitted work. It is not intended for introducing new methods or substantially changing the paper's core contributions, which cannot be adequately reviewed in the discussion period.

Reviewer_XVicOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper examines an approximate filtering rule for learned sparse retrieval (SPLADE models): an a-of-B filter, and then score the retained candidates. With this filter, we can reduce candidate volume wrt exhaustive top-k evaluation.

Critical strengths

Paper addresses a real and practical problem.

Critical weaknesses

This paper seems out of scope of ICLR. Why would the ICLR audience be interested in these findings? Would be more appropriate for WebConf (deadline around the same time) or SIGIR.

I don't think the proposed empirical results are compelling. As the authors stated themselves (~L401) - the approach only really shines at 16T/Q1. But is this a realistic condition in prod? Under this setting, you'll taking advantage of intra-query parallelism, but all the corpora are quite small. MS MARCO, the largest, is only 8.8M docs. In a prod setting, would you realistically use 16 threads to evaluate a single query? I'm not sure.

In addition, although the paper cites Won et al. (2025), it dismisses the related work out of hand for theoretical reasons... why? I'd like to see a fair, apples-to-apples empirical comparison with that work.

Questions for authors
  • Are you testing realistic settings?
  • Why ICLR (vs. WebConf, SIGIR, etc.)?
  • Why not evaluate against Won et al.?
9 comments
AuthorsOpenReview ↗

Response to the use of Multithread: Single-Thread Implementation Optimization by bitmap (No changes to method)

We sincerely thank the reviewer for questioning the necessity of allocating multi-threads to a single query, which has been removed from our paper. Motivated by your criticism, we redesigned the storage of index, introducing an optimized implementation named bitmap-MultiHit, and repeated experiments under a single thread. We apologize for placing too much emphasis on our theoretical contributions while paying insufficient attention to engineering optimization.

Bitmap-MultiHit achieves the lowest single-threaded latency among all evaluated SPLADE retrieval methods, while preserving the original retrieval quality and maintaining substantial storage and memory advantages.

All methods use SPLADE-v3, Top-1000 retrieval, and 1T/Q1. Latency is measured in ms/query; F@1000 is reported as a percentage.

(a) MS MARCO

MethodDev Lat.Dev F@1000TREC19 Lat.TREC19 F@1000TREC20 Lat.TREC20 F@1000
Seismic (kNN=0)40.4299.6438.2099.5241.7299.52
Seismic-0 (bitmap)42.2699.6439.1099.5241.4699.52
Seismic (kNN=32)46.6799.8747.6999.7849.6499.81
Seismic-32 (bitmap)48.5399.8746.9199.7848.9399.81
BMP (b=8)37.6397.0439.2297.3439.8796.80
BMP (bitmap)37.8397.0437.8597.3438.9296.80
Naive174.37100.00171.20100.00174.39100.00
Naive (bitmap)109.11100.0087.51100.0088.34100.00
MultiHit58.3499.7360.44100.0060.1499.85
bitmap-MultiHit22.1999.7323.63100.0024.3499.85

(b) DBpedia-Entity

MethodLatencyF@1000
Seismic (kNN=0)40.3399.40
Seismic-0 (bitmap)41.7099.40
Seismic (kNN=32)57.0999.81
Seismic-32 (bitmap)56.4199.81
BMP (b=8)68.0596.75
BMP (bitmap)67.9896.75
Naive95.72100.00
Naive (bitmap)77.55100.00
MultiHit39.9599.39
bitmap-MultiHit18.0899.39

(c) FiQA

MethodLatencyF@1000
Seismic (kNN=0)14.2899.11
Seismic-0 (bitmap)14.0299.11
Seismic (kNN=32)33.6199.55
Seismic-32 (bitmap)33.5499.55
BMP (b=8)40.8598.12
BMP (bitmap)43.3298.12
Naive1.96100.00
Naive (bitmap)1.70100.00
MultiHit1.7999.13
bitmap-MultiHit0.7699.13

The space is limited and we only list F@1000 that measures the fraction preserved of the exhaustive SPLADE Top-1000 documents. It is the strongest quality metric that most clearly differentiates these methods and directly corresponds to the ranking-preservation target of our theoretical analysis.

Performance. We keep the original Q1–Q3 parameter-selection strategy and settings: (B,a)=(8,2)(B,a)=(8,2) for MS MARCO and DBpedia-Entity, and (10,2)(10,2) for FiQA, without retuning for bitmap. Retrieval quality stays unchanged.

Bitmap-MultiHit is 2.21–2.63× faster than the original MultiHit and 2.24–4.92× faster than bitmap-Naive. On MS MARCO and DBpedia-Entity, it outperforms Seismic (kNN=0) by 1.62–2.23× and BMP by 1.64–3.76×. On FiQA, it is 13.07× faster than PISA MaxScore, the fastest external baseline. TREC19/20 results are also included in the revised manuscript.

Storage and memory. Bitmap adds only 10–14% storage. Our index remains 2.14–9.17× smaller than Seismic-H and 2.16–2.78× smaller than BMP, while their peak RSS is 1.79–4.25× and 4.24–8.87× of ours.

More deatiled results have been updated to the new PDF version of our paper. The new codes will be updated, too.

Implementation and ablation. We cache posting lists as bitmaps, count hits word by word, and represent candidates as masks. Scoring still processes nonempty tiles and maintains the global Top-1000. For comparison, we replace Seismic's visited hash set with a bitset indexed by vector offsets, and use a bitmap in BMP to skip empty score buckets.

Bitmap speeds up MultiHit by 2.21–2.63× and Naive by 1.15–1.97×, but barely affects Seismic or BMP. This is because bitmap directly accelerates MultiHit's hit counting, while Seismic mainly relies on clustered traversal, summary pruning, and forward-index scoring, and BMP on score bounds and block processing.

We hope the reviewer will reconsider our work based on both its theoretical contributions and the improved single-thread performance. We sincerely appreciate this feedback, which helped us improve the system.

AuthorsOpenReview ↗

Summary of Responses to Reviewer XVic

1. Weakness 1 / Q2: Why ICLR?

The reviewer states that “This paper seems out of scope of ICLR” and suggests SIGIR or WebConf instead. We believe this judgment is overly subjective and overlooks our theoretical contributions.

ICLR is not limited to papers that introduce new representation models. Understanding and properly using the properties of existing learned representations is equally relevant.

We build our theory on "Conformal Risk Control. ICLR 2024", which studies how to provide statistical risk guarantees for the outputs of models, without involving representation learning, architectural modifications, or retraining.

Our main contribution is explaining an unlearned property of learned sparse representations and establishing theoretical guarantees for the retrieval method built on it, not merely implementing a faster retrieval engine. This directly fits ICLR's scope.

Finally, ICLR has also accepted retrieval research that just improves indexing or search algorithms without changing encoding models, including:

Adaptive Retrieval and Scalable Indexing for k-NN Search with Cross-Encoders (ICLR 2024) Pacmann: Efficient Private Approximate Nearest Neighbor Search (ICLR 2025)

2. Weakness 2 / Q1: Multithreading Is Unrealistic

The reviewer questions whether allocating 16 threads to one query is realistic.

We agree and have completely removed multithreaded evaluations and optimized our method using bitmap, which achieves the SOTA single-thread performance (at least 1.6x speedup) among all methods.

3. Weakness 3 / Q3: Comparison with Won et al.

The reviewer requests a fair comparison with Won et al. Won chooses different threshold empirically on different query.

Won's main method Won-40% preserves only 74.75% of ranking quality on average, compared with 99.62% for our MultiHit.

That's because Won did not provide guarantees on candidate-volume bounds, Top-K survival guarantees, or finite-sample risk control, while we do.

AuthorsOpenReview ↗

Please Give More Attention to Our Theoretical Contributions

Your review does not mention our theoretical contributions in its summary, strengths, weaknesses, or questions. Although you questioned the paper's relevance to ICLR, you did not identify any issues with the novelty or validity of our theoretical results.

Your concerns just focused on multithreading and comparison with Won et al.

We have now addressed all these concerns through revisions and additional experiments.

Since our main contribution is theoretical, we respectfully wonder whether your Confidence score of 3 accurately reflects the scope of your assessment. We hope you will adjust your confidence score.

We deliberately kept our method and writing simple, presenting only the most straightforward theoretical results to make them easy to understand for everyone. We have invested a lot of time and effort on it and it should be a drawback, like "It's so easy, so it should not be a paper to ICLR". Though our explanation about the theory limitation of Won's method, you may find that it's just far from easy.

We believe in Occam's razor. If you agree that our method is both simple and effective, and its theoretical guarantees are solid, and our work is meaningful, we sincerely ask you to raise your rating.

Reviewer_EFJiOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

Summary

The submission proposes MultiHit, an aa-of-BB filter for learned sparse retrieval: keep documents matching at least aa of the BB heaviest query coordinates. It proposes and assesses the accuracy of moment-based bounds on candidate volume CaC_a and Top-K survival (which do not feed into algorithm thresholds or policies). It also offers threshold aa selection based on Conformal Risk Control (CRC) and Learn-then-Test (LTT) calibration, which do fit into their proposed system. Authors describe a search implementation that filters candidates in parallel, leading to speedups over naive scoring.

Critical strengths

Strengths

  • Expected but clear and competent empirical starting point. Hit counts separate the exhaustive Top-KK from the background on SPLADE-v3, consistently across MS MARCO, DBpedia and FiQA (Table 1).
  • Reasonable insights. The weak-survivor fraction Pr⁡(0<X≤τ)\Pr(0<X\le\tau) and the query-tail analysis go beyond a survival rate. Authors show that FiQA and DBpedia lose more because score mass sits outside the top BB coordinates.
  • CRC and LTT are applied appropriately.
  • Simple, practical system. The index is 2.4–10× smaller than Seismic’s and about 3× smaller than BMP’s (I have not checked or run the code).
  • Visible intra-query parallelism: The per-document independence of the filter allows one query to use many threads, and 16T/Q1 latency is lower than for the baselines.
  • The paper reports where MultiHit shows no advantage (1T), where baselines win, and where BM25 loses fidelity.
Critical weaknesses

Weaknesses

Contribution and novelty

  • The theory is admittedly not original. Thm 1 is the discrete moment problem (Prékopa), and Thm 2 is Paley–Zygmund / Bertsimas–Popescu. The additions are the sampling estimator and the "score-margin" definition.

  • The aa-of-BB filter is a known primitive: TT-occurrence in set-similarity search (Sarawagi & Kirpal, Li–Lu–Lu), LSH collision counting (C2LSH), and minimum-should-match in Lucene. These are uncited. Won et al. 2025 is cited and also overlaps.

  • The scaling law a≈c+sln⁡(N/K)a\approx c+s\ln(N/K) is an empirical fit with no derivation, tested against a weak baseline.

Coherence of the paper

  • While Q1 and Q2 are useful to understand the a-of-B pruning process, they do not directly inform the implementation and its hyperparameter choices.

  • Section 2.3 is not connected to the earlier theory, despite the claim that Q1 and Q2 “meet” there. CRC/LTT use only empirical miss losses.

  • The system experiments use fixed (B,a)(B,a) from a mean-survival sweep. CRC/LTT have no connection with Theorems 1 and 2.

  • The rr/aa notation switch and CrC_r as both a set and a count are sloppy.

Motivation for the bounds

  • The submission never argues why distribution-free bounds are valuable. Query optimizers already use histograms, sketches and sampling for selectivity estimation, and there is no comparison against these (for example set-similarity selectivity estimators).

  • The bound is loose in places (Lr/CrL_r/C_r as low as 0.55), and exact CrC_r comes free from the counting pass the engine already runs.

Evidence quality

  • The 8–29× speedup is at 16T/Q1, where the baselines aren’t implemented to be parallel within a query. Naive on the authors’ own engine already beats them, so the filter’s own gain is 1.47–3.14×. Still useful, but not as dramatic.

  • At 16T/Q64 the advantage holds mainly on DBpedia and FiQA. On MS MARCO it is about 1.1–1.2×, and Seismic wins on TREC20.

  • Only K=1000K=1000 is evaluated at system level, where the filter is least aggressive. Small-KK regimes, where approximate methods are strongest, are untested.

  • Relevance metrics (nDCG, MRR) appear only for MS MARCO at one operating point. No aa vs. nDCG sweep is shown, and DBpedia and FiQA get recall and fidelity only.

  • The BM25 comparison is confounded, since it runs without Top-BB truncation, so the claim that SPLADE preserves ranking better than BM25 isn’t established.

Scope and fit

Nothing is learned or analyzed about representations, and the encoder dependence is touched on only briefly. This makes ICLR fit questionable. Perhaps SIGIR or WSDM or CIKM or SIGMOD or VLDB may be better fits.

Additional references

Questions for authors

Examples of problematic writing quality

Q1 and Q2 could have been worded better. The reduction of candidates cannot be accurately analyzed using independence or sparsity, but it is certainly explained qualitatively from imperfect correlations. "Shrink" with what? increasing aa? This should be made explicit. For Q2, the empirical quantity of interest is the loss of documents that rank highly under full s(q,d)s(q,d) scoring as one increases aa. "Why do top-ranked documents survive" is a bit too colloquial.

The introduction does not mention the choice of BB, though it affects the results considerably. Section 2.3 does discuss it (“Choosing BB first”) and Table 4 (left) searches (B,a)(B,a) jointly, but BB is ultimately set from the accuracy-latency trade-off of Top-BB query truncation rather than from the theory developed earlier. A sentence or two in the introduction on how BB is chosen, and why it is not covered by the analysis, would be welcome.

The terminology, MultiHit "phenomenon" vs "principle", can also be improved. You do not really have a significant "principle" there, it is a matter of differential rates of filtering relevant and irrelevant documents.

Through L105, we see "aa-of-BB" filtering, but on L106, (I hope I am getting this right, otherwise I have been confused all along!) aa seems to have changed into rr.

At first occurrence in the caption of Table 2, Lr−L_r^- and Ur+U_r^+ are undefined, as are LrL_r and UrU_r. Below, Theorem 1 defines LL and UU. How do these relate? Authors definitely need to clean up notation and smooth the def-use order.

L133 Authors might make clear why bounds free from distributional assumptions are so important. In practice, we can collect all kinds of statistics during indexing to make the bounds better, perhaps? Relational databases do this all the time to optimize query execution.

I could not find a place in the submission where the authors show how the effective bounds on CaC_a (or CrC_r) are being used to modify the query execution strategy to improve latency or throughput.

L185: “prove MultiHit filter will save as many documents as using Full SPLADE vectors” is hard to parse. Do you mean that the filter retains nearly all documents in the exhaustive full-SPLADE Top-K? Note also that “prove” overstates what Theorem 2 gives, since it is a lower bound computed from moments of that same Top-K.

L191: The "score margin" XB,a(q,d)=∑i=aBzi/s(q,d)X_{B,a}(q,d)=\sum_{i=a}^{B} z_i / s(q,d) might be described as the fraction of the full score carried by the document’s aa-th through BB-th largest contributions among the selected coordinates. Here z1≥⋯≥zBz_1\ge\dots\ge z_B are sorted per document, so this is not the same as the contribution of the query’s aa-th through BB-th heaviest coordinates. The paper could state the sorting explicitly. Also, the denominator s(q,d)s(q,d) includes all query coordinates, so XX also depends on score mass outside the top BB. A small XX can therefore reflect weak additional hits, or a large query tail. Defining the margin relative to the truncated score ∑i≤Bzi\sum_{i\le B} z_i, or reporting the two effects separately, would make the interpretation clearer.

8 comments
AuthorsOpenReview ↗

Factual Errors and Overlooked Evidence

We respectfully wish to correct several statements in the review that are inconsistent with the original submission. We believe these omissions are important because they directly affect the assessment of our theoretical contribution and presentation.

1. Lucene's minimum-should-match was already cited.

The reviewer states that minimum-should-match in Lucene is not cited. However, the original Related Work explicitly discusses and cites it, including the Apache Lucene reference.

We acknowledge that the other classical references deserve more attention. We have therefore expanded Related Work to include all 12 papers suggested by the reviewer. However, the specific claim that Lucene was not cited is factually incorrect.

2. The original manuscript already includes tail-query evaluation.

Although the original Table 5 reports mean ranking fidelity rather than bad-query rates, Table 4 (Right) explicitly evaluates tail-query behavior. It reports held-out bad-query percentages for CRC and LTT-FS over 20 random splits with 100 calibration queries.

For example, on MS MARCO Top-10, CRC gives a 10.11% bad-query rate, whereas LTT-FS reduces it to 0.81%, illustrating the cost of stronger tail-risk control.

We agree that these results should have been connected more clearly to the system evaluation, but tail-query analysis was not absent from the original manuscript.

3. The confidence-adjusted notation in Table 2 was already explained.

The reviewer states that Lr−L_r^- and Ur+U_r^+ are undefined. However, the original Table 2 caption explicitly states that they include 95% confidence margins, satisfying Lr−≤Lr,Ur+≥Ur.L_r^-\le L_r,\qquad U_r^+\ge U_r.

The caption also explains the sampling budgets, repetitions, and confidence interpretation.

We acknowledge that Theorem 1 uses L,UL,U rather than Lr,UrL_r,U_r, making their correspondence less clear. We have unified the notation in the revision. Nevertheless, the meanings of the confidence-adjusted bounds were already explained in the original caption.

4. "Nothing is learned or analyzed about representations."

This statement overlooks a substantial part of our paper. Our research specifically investigates a property of learned sparse representations that is not explicitly optimized during training: SPLADE learns vectors for weighted inner-product ranking, yet their binary support structure also enables effective hit-count filtering.

The original submission already provides several analyses:

  • Table 1: Reveals a distinctive property of SPLADE's learned sparse representations: highly ranked documents tend to match multiple high-weight query coordinates, while background documents rarely do. This separation emerges even though SPLADE is trained for weighted ranking, not hit counting.

  • Theorem 1 and Table 2: Characterize the intersection structure of learned sparse supports.

  • Theorem 2 and Table 3: Connect SPLADE's learned impact weights with its binary support structure.

  • Figure 1: Examines how this property varies across three SPLADE encoders.

These are analyses of learned representations themselves. Our paper does not train a new encoder, but understanding the properties of learned representations is also an important part of representation-learning research.

We appreciate the reviewer's attention to presentation, and we have made further revisions for clarity. However, we hope these corrections will be considered when assessing the original paper's theoretical content and completeness.

AuthorsOpenReview ↗

Misunderstandings and our explanation

We thank the reviewer for the detailed comments. However, we find many criticisms arise from a misunderstanding of our research and the relationship between our theoretical and experimental results.

1. The connection between Q1, Q2, and Q3 is direct

We respectfully disagree that “Section 2.3 is not connected to the earlier theory, despite the claim that Q1 and Q2 ‘meet’ there.” They study the same efficiency–fidelity trade-off:

  • Q1: What candidate-volume reduction do we gain by increasing aa?
  • Q2: How much exhaustive Top-K ranking fidelity do we lose?
  • Q3: How should we choose parameters from limited observations while controlling that loss?

Q1–Q2 explain the filtering mechanism, while Q3 provides a practical method for the same trade-off discussed in Q1 and Q2.

2. Q1–Q3 Directly Guide Our System Evaluation

We respectfully disagree with the reviewer's statements that “Q1 and Q2 never feed the method” and “CRC/LTT are never used end-to-end,” as well as the claim that “I could not find a place in the submission where the authors show how the effective bounds [...] are being used to modify the query execution strategy to improve latency or throughput.”

Q1: Why we choose a=2a=2 in experiments?

Table 1 shows that, at B=10B=10 and K=1000K=1000, increasing aa to 3 further reduces candidates to 11.24%, but survival drops to 96.74%, below our 99% target. Since a=1a=1 is naive, **a=2a=2 is the smallest threshold and offers the best efficiency–quality trade-off **.

Q2: Why do these operating points preserve ranking?

Table 3 evaluates our exact system settings: (8,2)(8,2) on MS MARCO and DBpedia-Entity, and (10,2)(10,2) on FiQA. Their average observed survival is 99.41%, with an average theoretical lower bound of 94.22%. Moreover, FiQA achieves only 97.27% survival at (8,2)(8,2), compared with 99.19% at (10,2)(10,2). This directly explains why FiQA requires a larger BB.

Q3: How do we select these parameters? (B=8, a=2)

As explicitly stated in Section 2.3, “We first jointly tune (B,a)(B,a) under target survival to see BB's influence to aa. We then fix BB and formulate choosing aa as a finite-sample risk-control problem.”

Table 4 (Left) performs this joint search. At K=1000K=1000, (8,2)(8,2) gives the smallest candidate fractions averaging 9.17% under the 99% survival target. On FiQA, however, B=8B=8 permits only a=1a=1, retaining 63.25% of candidates, whereas (10,2)(10,2) reduces this to 43.83%.

Table 4 (Right) further demonstrates finite-sample calibration using 100 queries and 20 random splits. At K=1000K=1000 and B=10B=10, LTT-FS selects a=2a=2 most frequently on MS MARCO and DBpedia-Entity. On FiQA, CRC most often selects a=2a=2 (17/20), while the more conservative LTT-FS selects a=1a=1 (18/20). We adopt the CRC operating point for its practical filtering benefit, claiming the expected-risk criterion rather than the stronger LTT-FS tail guarantee.

We have now made the theory-to-system connection explicit in the revised Implementation section.

Therefore, Q1 identifies the effective hit threshold, Q2 explains ranking preservation and the need for a larger BB on FiQA, and Q3 selects the operating points through joint parameter analysis and finite-sample risk control. These conclusions directly guide our system evaluation.

3. Distribution-free bounds are not intended to replace exact online counting.

The reviewer questions the value of our bounds because exact candidate counts are available during retrieval. However, the distribution of queries can substantially change posting-list intersections and inner-product score distributions. Counting itself only reveals the candidate volume for a particular query; it does not explain the underlying distribution or why highly ranked documents survive. Moment analysis is therefore essential: Q1 uses two binomial intersection moments to bound candidate contraction, while Q2 uses the mean and second moment (equivalently, the mean and variance) of score margins to bound Top-K survival.

4. The criticism of the BM25 comparison is incorrect.

The reviewer claims that “The BM25 comparison is confounded, since it runs without Top-B truncation.” However, this criticism reverses the effect of query truncation.

BM25-MultiHit is already the fastest method in Table 5, averaging only 18.34 ms/query across three datasets at 1T/Q1. Its problem is not the speed, but ranking quality: its average F@1000 is only 77.06%, compared with over 99% for SPLADE methods. So it's not necessary for BM25 to use Top-B query truncation for speedup at the cost of greater ranking quality loss.

We hope the reviewer will reconsider the paper based on its central contribution: understanding why learned sparse representations support count-based filtering, establishing bounds on candidate contraction and Top-K survival, and providing reliable threshold calibration from limited data.

AuthorsOpenReview ↗

Response to "Evidence quality": New Single-Thread Method

We sincerely thank the reviewer for pointing out that our original speedups relied on parallelism, whereas the baselines were not designed to parallelize individual queries. Motivated by this feedback, we redesigned our index storage and introduced a new implementation, bitmap-MultiHit, repeating the system experiments under a single thread (1T/Q1). We apologize for placing too much emphasis on our theoretical contributions while paying insufficient attention to single-thread engineering optimization.

Bitmap-MultiHit now achieves the lowest single-threaded latency among all evaluated SPLADE retrieval methods, while preserving the original retrieval quality and substantial storage and memory advantages.

All methods use SPLADE-v3, Top-1000 retrieval, and 1T/Q1. Latency is measured in ms/query; F@1000 is reported as a percentage.

(a) MS MARCO

MethodDev Lat.Dev F@1000TREC19 Lat.TREC19 F@1000TREC20 Lat.TREC20 F@1000
Seismic (kNN=0)40.4299.6438.2099.5241.7299.52
Seismic-0 (bitmap)42.2699.6439.1099.5241.4699.52
Seismic (kNN=32)46.6799.8747.6999.7849.6499.81
Seismic-32 (bitmap)48.5399.8746.9199.7848.9399.81
BMP (b=8)37.6397.0439.2297.3439.8796.80
BMP (bitmap)37.8397.0437.8597.3438.9296.80
Naive174.37100.00171.20100.00174.39100.00
Naive (bitmap)109.11100.0087.51100.0088.34100.00
MultiHit58.3499.7360.44100.0060.1499.85
bitmap-MultiHit22.1999.7323.63100.0024.3499.85

(b) DBpedia-Entity

MethodLatencyF@1000
Seismic (kNN=0)40.3399.40
Seismic-0 (bitmap)41.7099.40
Seismic (kNN=32)57.0999.81
Seismic-32 (bitmap)56.4199.81
BMP (b=8)68.0596.75
BMP (bitmap)67.9896.75
Naive95.72100.00
Naive (bitmap)77.55100.00
MultiHit39.9599.39
bitmap-MultiHit18.0899.39

(c) FiQA

MethodLatencyF@1000
Seismic (kNN=0)14.2899.11
Seismic-0 (bitmap)14.0299.11
Seismic (kNN=32)33.6199.55
Seismic-32 (bitmap)33.5499.55
BMP (b=8)40.8598.12
BMP (bitmap)43.3298.12
Naive1.96100.00
Naive (bitmap)1.70100.00
MultiHit1.7999.13
bitmap-MultiHit0.7699.13

Why F@1000? Due to space limitations, we report F@1000, which measures the fraction of exhaustive SPLADE Top-1000 documents preserved by each method. This metric directly corresponds to the ranking-preservation objective of our theoretical analysis and clearly distinguishes the methods.

Performance. We retain the original Q1–Q3 parameter-selection strategy and operating points: (B,a)=(8,2)(B,a)=(8,2) on MS MARCO and DBpedia-Entity, and (10,2)(10,2) on FiQA. No parameters were retuned for bitmap optimization, and retrieval quality remains unchanged.

Bitmap-MultiHit is 2.21–2.63× faster than the original MultiHit and 2.24–4.92× faster than bitmap-Naive. On MS MARCO and DBpedia-Entity, it outperforms Seismic (kNN=0) by 1.62–2.23× and BMP by 1.64–3.76×. On FiQA, it is 13.07× faster than PISA MaxScore, the fastest external baseline. TREC19/20 results are also included in the revised manuscript.

Storage and memory. Bitmap optimization increases storage by only 10–14%. Our index remains 2.14–9.17× smaller than Seismic-H and 2.16–2.78× smaller than BMP. Their peak RSS is 1.79–4.25× and 4.24–8.87× ours, respectively.

Implementation and ablation. We cache posting lists as bitmaps, count hits word by word, and represent candidates as masks. Scoring still processes nonempty tiles and maintains the global Top-1000. For a fair comparison, we also introduce bitmap variants of Seismic and BMP: Seismic's visited hash set is replaced with a bitset indexed by vector offsets, while BMP uses a bitmap to skip empty score buckets.

Bitmap optimization accelerates MultiHit by 2.21–2.63× and Naive by 1.15–1.97×, but barely changes Seismic or BMP. This is because bitmap operations directly accelerate MultiHit's hit counting, whereas Seismic mainly relies on clustered traversal, summary pruning, and forward-index scoring, and BMP on score bounds and block processing.

The revised PDF includes these results and implementation details, and the corresponding code is being updated.

We have therefore directly addressed the reviewer's concern: our performance advantage no longer depends on intra-query parallelism. We hope the reviewer will reconsider the practical contribution of MultiHit alongside our theoretical analysis. We sincerely appreciate this feedback, which helped us substantially improve the system.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Summary of Responses to All Reviewer Comments

We sincerely thank all three reviewers for their detailed feedback. Up to date, we have addressed all the weaknesses and questions raised by the reviewers.

About experiment, we have made 4 major improvements.

  1. Reviewers XVic and 1dkD questioned the practicality of our multithread speedups. We removed all about multithread comparisons and optimized the hit-counting component of the original MultiHit algorithm using an additional bitmap index, which now achieves the fastest single-threaded performance among all evaluated SPLADE methods, with 1.70–13.07× speedups over the fastest external baselines (including the P50/P90 latency per query, see the data in our latest response to Reviewer 1dkD).

  2. Reviewers EFJi and 1dkD questioned the limited efficiency–quality evaluation. We added Pareto-frontier curves across five query sets, demonstrating MultiHit's better performance against Seismic and BMP in the low-latency region.

  3. Reviewer XVic requested a direct comparison with Won et al. We implemented their method under the same evaluation setting and showed that MultiHit preserves 99.62% versus 74.75% of exhaustive Top-1000 documents on average.

  4. Reviewer 1dkD questioned Seismic's multithread latency and the 0.88% MRR@10 difference in MS MARCO dev against official SPLADE-v3 on huggingface. We solved both issues: discovered and corrected a bug in Seismic's official multithreaded interface, and clarified the differences between our sparse-vector generation settings (512-token, FP16) and the official model configuration (256-token).

About theory,

  1. Two of the three reviewers (XVic and 1dkD) do not mention our theory in their raised weaknesses and questions.

  2. Reviewer EFJi's criticisms of our theoretical limitations was already explicitly acknowledged in the original manuscript, including the conservativeness of two-moment bounds (Section 2.2, L251–257 in the original pdf) and the empirical nature of the scaling law (Section 2.4). Moreover, Reviewer EFJi's assessment contains numerous factual errors and misunderstandings of our work.

Therefore, our core theoretical results remain unchanged.

Strengths

As acknowledged by the reviewers, our paper addresses a real and practical problem, identifies an interesting property of learned sparse representations, and proposes a very simple but really efficient retrieval method. Reviewer EFJi also explicitly recognizes that "CRC and LTT are applied appropriately," while Reviewer 1dkD confirms that our code was available during the review.

Our contributions go beyond engineering improvements. To our knowledge, we are the first to jointly establish candidate-volume bounds and Top-K survival bounds for learned sparse representations.

With the revised implementation, MultiHit also achieves the fastest single-threaded performance among all evaluated SPLADE retrieval methods and better efficiency–quality trade-off in the low-latency region, while maintaining over 99% Top-1000 fidelity and the lowest storage and memory usage.

Codes of revised implementation are now available in the Supplementary Material.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.