# Locality-Sensitive Hashing for Efficient Hard Negative Sampling in Contrastive Learning

arXiv: https://arxiv.org/abs/2505.17844 · HTML: https://mlsanity.com/paper/2505.17844/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 37 of its 50 references that are in the map.
- First posted on arXiv 23 May 2025.

## Builds on (most cited first, 30 of 37)

- [Learning Transferable Visual Models From Natural Language Supervision](https://mlsanity.com/paper/2103.00020/) (2021)
- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [RoBERTa: A Robustly Optimized BERT Pretraining Approach](https://mlsanity.com/paper/1907.11692/) (2019)
- [Sentence-BERT: Sentence Embeddings using Siamese BERT-Networks](https://mlsanity.com/paper/1908.10084/) (2019)
- [Representation Learning with Contrastive Predictive Coding](https://mlsanity.com/paper/1807.03748/) (2018)
- [DistilBERT, a distilled version of BERT: smaller, faster, cheaper and lighter](https://mlsanity.com/paper/1910.01108/) (2019)
- [Scaling Up Visual and Vision-Language Representation Learning With Noisy Text Supervision](https://mlsanity.com/paper/2102.05918/) (2021)
- [Dense Passage Retrieval for Open-Domain Question Answering](https://mlsanity.com/paper/2004.04906/) (2020)
- [A ConvNet for the 2020s](https://mlsanity.com/paper/2201.03545/) (2022)
- [Sigmoid Loss for Language Image Pre-Training](https://mlsanity.com/paper/2303.15343/) (2023)
- [FaceNet: A Unified Embedding for Face Recognition and Clustering](https://mlsanity.com/paper/1503.03832/) (2015)
- [MS MARCO: A Human Generated MAchine Reading COmprehension Dataset](https://mlsanity.com/paper/1611.09268/) (2016)
- [Approximate Nearest Neighbor Negative Contrastive Learning for Dense Text Retrieval](https://mlsanity.com/paper/2007.00808/) (2020)
- [In Defense of the Triplet Loss for Person Re-Identification](https://mlsanity.com/paper/1703.07737/) (2017)
- [Contrastive Learning with Hard Negative Samples](https://mlsanity.com/paper/2010.04592/) (2020)
- [Making Monolingual Sentence Embeddings Multilingual using Knowledge Distillation](https://mlsanity.com/paper/2004.09813/) (2020)
- [Deep Metric Learning via Lifted Structured Feature Embedding](https://mlsanity.com/paper/1511.06452/) (2015)
- [RocketQA: An Optimized Training Approach to Dense Passage Retrieval for Open-Domain Question Answering](https://mlsanity.com/paper/2010.08191/) (2020)
- [Multi-Similarity Loss with General Pair Weighting for Deep Metric Learning](https://mlsanity.com/paper/1904.06627/) (2019)
- [Debiased Contrastive Learning](https://mlsanity.com/paper/2007.00224/) (2020)
- [Sampling Matters in Deep Embedding Learning](https://mlsanity.com/paper/1706.07567/) (2017)
- [VIGOR: Cross-View Image Geo-localization beyond One-to-one Retrieval](https://mlsanity.com/paper/2011.12172/) (2020)
- [Wide-Area Image Geolocalization with Aerial Reference Imagery](https://mlsanity.com/paper/1510.03743/) (2015)
- [Lending Orientation to Neural Networks for Cross-view Geo-localization](https://mlsanity.com/paper/1903.12351/) (2019)
- [TransGeo: Transformer Is All You Need for Cross-view Image Geo-localization](https://mlsanity.com/paper/2204.00097/) (2022)
- [Learning Dense Representations for Entity Retrieval](https://mlsanity.com/paper/1909.10506/) (2019)
- [Sample4Geo: Hard Negative Sampling For Cross-View Geo-Localisation](https://mlsanity.com/paper/2303.11851/) (2023)
- [Practical and Optimal LSH for Angular Distance](https://mlsanity.com/paper/1509.02897/) (2015)
- [Fast Approximate Nearest Neighbor Search With The Navigating Spreading-out Graph](https://mlsanity.com/paper/1707.00143/) (2017)
- [Improved Embeddings with Easy Positive Triplet Mining](https://mlsanity.com/paper/1904.04370/) (2019)

## Abstract (arXiv)

Contrastive learning is a representational learning paradigm in which a neural network maps data elements to feature vectors. It improves the feature space by forming lots with an anchor and examples that are either positive or negative based on class similarity. Hard negative examples, which are close to the anchor in the feature space but from a different class, improve learning performance. Finding such examples of high quality efficiently in large, high-dimensional datasets is computationally challenging. In this paper, we propose a GPU-friendly Locality-Sensitive Hashing (LSH) scheme that quantizes real-valued feature vectors into binary representations for approximate nearest neighbor search. We investigate its theoretical properties and evaluate it on several datasets from textual and visual domain. Our approach achieves comparable or better performance while requiring significantly less computation than existing hard negative mining strategies.