acceptodds
Under review as a conference paper at ICLR 2027

Semantic MinHash: Bringing MinHash to Embeddings

Abstract

MinHash and locality-sensitive hashing (LSH) provide reusable signatures and bucket-based candidate generation for set similarity, but classical set MinHash does not directly capture the semantic geometry of dense embeddings. We present Semantic MinHash (\method), which constructs a distance-annotated set for each embedding using shared sampled references and takes the minimum-distance index directly as its hash value. Repeated selections produce a discrete signature that brings the MinHash processing pattern to embedding retrieval, similarity graphs and duplicate screening. Building on nearest-reference winner-take-all selection, we derive an exact finite-reference collision law with shared-order ties, conditional locality and candidate-precision guarantees, and a maximum-load bound based on reference coverage and concentration. Experiments on text, image and multimodal embeddings demonstrate selective candidate generation: data references reduce mean candidate fractions on eight datasets against an equally tuned spherical-reference control, while semantic screening and complete-task comparisons establish practical benefits at the evaluated operating points. These results connect embedding-to-set construction, collision analysis and empirical task performance, providing a common basis for applying minimum-index signatures and LSH to semantic embeddings.

Primary area:
unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords:
MinHash, embedding, locality-sensitive hashing

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_MzRiOpenReview ↗
Rating
2
Confidence
4(+1)
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper proposes a SMinHash, which represents embeddings by repeatedly sampling a shared reference set and recording the index of the nearest reference in each set. The paper establishes a finite reference conflict expression that incorporates shared order relations, conditional locality, and candidate word accuracy guarantees, as well as a bound that correlates reference coverage and concentration with bucket load. Experimental results show that this method achieves higher candidate word selectivity compared to spherical reference control.

Critical strengths
  • This paper clearly distinguishes between fixed-pair collision probability, geometric locality, candidate precision, and fitted bucket concentration. Its handling of shared order relationships and counterexamples demonstrate that data-derived references do not necessarily produce balanced buckets, providing relevant evidence.
  • Experimental results show that on the QQP dataset, SMinHash retains approximately 99.48% of cosine positive sample pairs while allowing 0.338% of independent background probe sample pairs. Furthermore, reporting recall failures, full execution costs, and adverse results enhances the credibility of the evaluation.
Critical weaknesses
  • Despite its length and complexity, this paper offers limited methodological innovation. For example, Equation (1) explicitly applies WTA hashing to negative reference distances. However, distance feature interpretation, binary MinHash specialization, and a strict order collision expression already exist in the cited WTA work. Similarly, Section 5, with its specified full-pool, row-by-row setting, is essentially equivalent to single-probe DFLSH. In essence, this paper enhances its contribution through a large amount of additional analysis. Therefore, in my opinion, this extension considering relevant factors and its associated analytical improvements do not represent a sufficiently significant improvement compared to existing methods.
  • The experimental results did not yield satisfactory performance improvements. SMinHash failed to achieve the 95% recall target in all three fits across four of the eight datasets, particularly on the DBpedia and COYO datasets, where, despite its superior performance, it still fell short of the quality target (Table 18). Furthermore, regardless of whether SMinHash completed the task, its graph construction speed was slower than Flat and IVF-Flat, and it exceeded the release budget on the GIST and NYTimes datasets (Table 11). While the proposed SMinHash outperforms in some experimental results, its applicability is limited. Specifically: (1) the cost of constructing additional connections is reduced on the COCO and Deep datasets; (2) both are essentially the same on the SIFT dataset; (3) IVF is superior on the NYTimes dataset; and (4) IVF is faster during the query phase on all four datasets (Table 12). Therefore, in summary, while the experimental results show some improvement, there is a lack of clear, usable practical application value to compensate for the lack of theoretical innovation.
Questions for authors
  • Of the reported selected operating points, is there any that can provide quantitative guarantees of locality, candidate accuracy, or workload based on Theorem 3.3, Corollary 3.4, or Proposition 3.2?
  • Regarding the join results of COCO and Deep, can the authors demonstrate whether the overall cost advantage still exists when the recall is comparable and the index building cost is amortized across repetitive workloads?
1 comment

Thanks for your review and comments.

A1: Even good coverage can send many objects to the same reference; Proposition 3.2 exposes the two sources through reverse-neighbor concentration plus the number of uncovered objects. Continuous counterexamples further rule out duplicates or distance ties as necessary explanations of concentration: with ambient dimension 257, N=65,536, ψ\psi=1024, and T=100, at least one coordinate bucket among the 100 rounds contains more than 95% of the objects with probability greater than 0.999 over the joint data and encoder draws. A separate construction shows that sparse true threshold output can coexist with quadratic candidate work.

A2: The new experiments add joint checks of achieved quality and complete cost. In Table 4, all three Deep99 fits meet the quality-matching rule, and SMinHash has lower mean total cost at every measured reuse count, with construction reuse measured directly. COCO, DBpedia, and COYO, three of the datasets that failed in the original table, plus Deep all reach actual returned Recall@10≥95% at the new band-OR T=50 points (Table 23). Semantic screening supplies a complementary use. On identical MiniLM representations, both methods retain at least 99% of cosine-positive QQP pairs in every fit, while SMinHash produces approximately 37.2 times fewer candidates than embedding hyperplanes. On MRPC it retains more human positives with about one quarter of the candidates (Table 39). This reduces pairs reaching an existing semantic decision rule; Table 2 further demonstrates actual query and retained-state benefits in the evaluated hashing pipeline.

A3: We have not established guarantees certifying useful locality, candidate precision, or the execution budget for the selected retrieval/join points.

A4: Mean total cost remains lower at all three measured reuse counts, with the benefit narrowing as reuse increases. SMinHash/IVF-Flat mean edge recalls are 99.141%/99.106%; every fit reaches 99%, each gap satisfies the predeclared 0.5-percentage-point tolerance, and every output has precision 1. One actual construction plus K=1/4/16 complete joins costs 0.545/0.797, 2.030/2.315, and 8.009/8.455 s, respectively (Table 4). Every repetition regenerates complete outputs without caching final edge sets; SMinHash is faster in all three fits at K=1 and 4, and in two fits at K=16. Per-fit results appear in Table 32.

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

This manuscript presents Semantic MinHash (SMinHash), a hashing framework that constructs discrete signatures by selecting the nearest references from shared reference sets. The manuscript develops theoretical results on finite-reference collision probabilities, locality conditions, and bucket loads, followed by empirical evaluation on text, image, and multimodal embeddings. The results show improved candidate selectivity over spherical-reference controls, while the practical efficiency gains over established vector search methods remain limited.

Critical strengths
  1. The paper provides a systematic theoretical analysis of finite-reference collision probabilities, locality conditions, and bucket-load behavior, offering useful insights into reference-based hashing.

  2. The experimental evaluation is broad and includes multiple retrieval and similarity-processing tasks. The authors also report infeasible configurations and negative results, improving the transparency of the evaluation.

Critical weaknesses
  1. The algorithmic novelty requires further clarification. The core SMinHash construction is closely related to existing winner-take-all (WTA) and nearest-reference hashing approaches, and the paper also notes similarities with single-probe DFLSH under certain settings. The authors should more clearly distinguish SMinHash from prior hashing methods and substantiate its unique methodological contributions.

  2. The theoretical guarantees have limited practical predictive power. The locality and candidate-precision guarantees rely on distribution-dependent assumptions, while the maximum-bucket-load bounds can be substantially looser than empirical observations. The paper does not sufficiently demonstrate how these theoretical results can guide parameter selection or accurately predict performance at the chosen operating points.

  3. The practical efficiency advantage should be further demonstrated. Although SMinHash substantially reduces the candidate fraction, this reduction does not consistently translate into lower end-to-end query latency, especially at large scale. The authors should analyze the computational overhead of candidate generation and clarify under which workloads SMinHash provides an actual runtime advantage.

  4. Further validation is needed to establish generalization and reproducibility. Some benchmark splits were previously inspected, while certain timing experiments were conducted under shared-device conditions. These factors weaken the evidence for generalization to unseen distributions and reduce the reliability of runtime comparisons. Evaluation on genuinely untouched data and under controlled hardware conditions would strengthen the evidence for the method's robustness and practical applicability.

Questions for authors
  1. What are the key algorithmic differences between SMinHash and existing hashing methods? Please clarify its main methodological contributions.

  2. Can the authors provide recall–latency and recall–memory Pareto comparisons under comparable hardware, tuning budgets, and retrieval-quality targets? In particular, under what practical workloads does SMinHash offer an advantage despite its relatively high query time at large scale?

  3. How tight and practically informative are the proposed theoretical bounds at the selected operating points? Please compare the theoretical predictions with empirical collision probabilities, candidate fractions, and maximum bucket loads.

1 comment

We thanks for your review and feedback.

A1: The revised introduction centers the contribution on concrete analytical results. Proposition 3.1 gives an exact collision expression including distance ties under shared random order for an arbitrary fixed finite reference pool. Proposition 3.2 upper-bounds maximum coordinate-bucket load by reverse-neighbor concentration plus the number of uncovered objects. Continuous, duplicate-free, distance-tie-free counterexamples show that neither data references nor uniform single-input marginal labels ensure balanced fitted buckets; a separate construction yields quadratic candidate work despite sparse true output. These results respectively address probability computation, load conditions, and invalid generalizations.

A2: The three theoretical objects require separate comparisons. Table 19 calibrates fixed-pair probabilities on four datasets, ten reference resolutions, and 512 independent encoders per setting. Mean absolute errors are 0.101–0.109 percentage points for single-round collision, 0.388–0.561 for band admission, and 0.087–0.294 for count admission. This supports the exact probability law and its admission-rule amplification. Geometric diagnostics are much more conservative: averaging across fixed neighbor pairs and reference resolutions on Deep96 gives exact single-round probability 0.515 but margin lower bound only 9.238×10−710^{-7}; these are not uniform deployment-domain constants. At ψ\psi=1024, three-fit mean maximum-bucket fractions are 0.883%–1.544%, compared with primary bounds of 5.088%–18.275%.

A3: The new experiments identify two benefits. First, SMinHash and IVF-Flat pass the predeclared achieved-quality matching rule in all three fits of the complete 100k Deep96 join at the 99% target: total costs including construction, verification, and output are 0.545±0.048 s/0.797±0.028 s (Table 4). Second, comparing SMinHash with embedding hyperplanes at the 99% validation-selected band-OR retrieval points on Deep96, both methods use 1,000 nominal bits, identical embeddings, and the same FP64 verifier. The largest per-fit recall gap is 0.37 percentage points; complete 1,000-query times are 0.0541±0.0093 s/0.3569±0.0011 s, with 185.566/288.784 MB of logical retained GPU state (Table 2).

A4: New results timing starts after observed GPU-idle admission. Methods are compared serially on the same GPU within each fit, with full warmup, counterbalanced order, and eight measurements per method; occupancy samples show no foreign GPU compute process, and CPU threads are fixed at eight.

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

The paper claims to bring MinHash-style signatures to dense embeddings. For T=100 hash functions, a min-hash signature H represents a dense vector as a tuple of discrete value. Candidates come from band-OR (any band matches) or collision-counting.

Overall, The SMinHash method claims to be a common minimum-index signature / LSH framework for embedding retrieval, graphs, joins and duplicate screening, with an exact collision law and diagnostic theory. Data-derived references improve selectivity over spherical references.

Critical strengths

Fast search or comparison is quite important in many applications.

Critical weaknesses

The paper claims to bring semantic comparison to min-hash, but there are some prior work, for instance the uncited work: Sim-Min-Hash: An efficient matching technique for linking large image collections (ACM Multimedia 2013, https://dl.acm.org/doi/abs/10.1145/2502081.2502152). That was an early paper adding a notion of similarity into MinHash, so the claim of bringing MinHash to similarity/geometry should be positioned against it, not just against WTA / DFLSH / Voronoi hashing.

Scale is modest, not a first. the paper Sim-Min-Hash already operated in 2013 on 2 billion local descriptors and one million images. This paper's main experiments are on 100k vectors, with a single scaling study to 10M global embeddings. That is not a step forward in scale for MinHash-style matching. The comparison is if anything flattering to the old work, since local descriptors are far more numerous than global image embeddings.

Finally, T is very high and costly. T=100 signatures involves a high memory footprint compared to ANN methods (like IVFFlat or derivative) and a high encoding cost. This encoding cost is a major reason query time loses to Flat/IVF despite fewer candidates, and it limits practicality in most applications.

Overall, selectivity does not guarantee the fastest full pipeline, and the guarantees require distribution-dependent conditions.

The method also requires a post-verification, which is not necessarily the case for competing techniques like those based on binarization of quantization.

Questions for authors

Please address my concerns in case I have misunderstood something.

Also please comment on how the method is expected to become useful when considering very large scale where this kind of technique is really needed (billion to trillions of vectors).

2 comments

Thanks for your review and suggestions.

A1: We have added this precedent to the revised related work and distinguished its object of analysis precisely. Sim-Min-Hash represents an image as a set of local descriptors, combining MinHash selection of quantized visual words with similarity between retained descriptors for set matching. Our signature records the nearest-reference index directly for an individual global embedding. The earlier work establishes similarity-aware MinHash-style set matching; our analysis studies the probability and load behavior of this single-vector reference-index mechanism.

A2: Our scaling study tests the quality of a fixed model as the database grows. It does not claim a scale record. The two billion local descriptors support set matching over one million images, whereas our 9.99M count denotes individual global vectors; these different units do not directly rank scalability. Retaining the parameters, references, and queries selected at 100k, and recomputing ground truth at 9.99M, gives 99.18% Recall@10 with 3.096% candidates (Table 21). This supports reuse of a fixed signature model; complete query costs remain in the same table. The revised main text makes this experimental purpose and the counting units explicit.

A3: We tested signature length and encoding attribution separately. In the predeclared T=25/50/100 ablation, T=50 reaches 95% actual returned Recall@10 in all twelve cases across four datasets and three fits (Table 23). On DBpedia1536 and COYO2048, we hold configurations and complete outputs fixed and counterbalance live-encoding and cached-signature queries. Removing online hashing yields mean within-fit median paired total-latency reductions of 0.805%–2.012% (Table 28). Thus, encoding does not explain the dominant query cost in these added execution configurations.

A4: Retaining the verifier makes the signature a screening layer before an existing semantic decision rule: signatures select candidates, and original vectors perform the target threshold decision or ranking. Its usefulness should be evaluated after paying verification cost. In Deep99, mean edge recall is 99.141%, and every output edge satisfies the frozen FP64 threshold ground truth. Table 4 includes this verification and complete output, compared with IVF-Flat at close achieved recall. It therefore demonstrates a complete-cost benefit that already pays for verification. Direct scoring of compressed representations is also a valid design; each pipeline should be charged for its own scoring and storage at its achieved quality.

A5: With references and parameters fixed, per-object encoding does not grow with the database object count, allowing signatures to be reused for screening and joins. Existing task evidence includes WDC's complete 5,000-by-200,000 pair space: with both methods exceeding 95% official-match recall in every fit, candidate fractions are 6.225%/31.423% (Table 39). This is blocking over one billion possible pairs, not a database of one billion objects. At larger object counts, feasibility depends on concentration, candidate work, and workspace; the coverage/concentration analysis explains why data references alone cannot ensure these properties. That scale also requires validated partitioning and external-memory or distributed system (such as Spark).

I thank the authors for their response, especially the clarification regarding prior work. However my concern about the practical interest of the method at scale remains. 10M vectors is very small for an indexing algorithm. I therefore maintain my score.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.