Breaking the Batch Barrier (B3) of Contrastive Learning via Smart Batch Mining

Raghuveer Thirukovalluru, Rui Meng, Ye Liu, Karthikeyan K, Mingyi Su, Ping Nie, Semih Yavuz, Yingbo Zhou, Wenhu Chen, Bhuwan Dhingra

Abstract

Contrastive learning typically requires massive batch sizes to ensure sufficient in-batch negatives, creating a computational bottleneck for high-resolution multimodal models. We present B3 (Breaking the Batch Barrier), a smart batch-mining strategy that employs graph clustering to group mutually strong negatives. By maximizing the quality of in-batch negatives, B3 achieves state-of-the-art performance on multimodal benchmarks with significantly smaller batch sizes and reduced compute compared to traditional methods.

Introduction

Contrastive learning (CL) relies on the principle of pulling positive pairs together while pushing negative pairs apart. To achieve high discriminative power, models require "hard negatives"—examples that are semantically distinct but superficially similar to the query. Traditionally, these are obtained either through explicit mining (computationally expensive) or by using massive batch sizes (memory intensive). B3 addresses this by asking: Can we construct standard-sized batches where examples inherently act as strong negatives for one another?

Methodology

The B3 pipeline moves away from random batch sampling toward a structured, graph-based approach.

The B3 pipeline: from teacher ranking to graph-based community detection and student model training.

The process involves four key steps:

  1. Teacher Ranking: A pretrained teacher model scores and ranks all examples in the training dataset against each query.
  2. Sparse Graph Construction: To avoid "false negatives" (valid positives not labeled as such), the algorithm discards the top $p$ most similar ranks. It keeps the next $m$ ranks to build a sparse similarity graph where edges represent a "preference" for being a strong negative.
  3. Community Detection: The METIS algorithm identifies equal-sized communities of mutually strong negatives. METIS is chosen for its $O(n)$ efficiency.
  4. Batch Assembly: Training batches are constructed by sampling from these cohesive communities, ensuring each batch is packed with high-quality negatives.

The authors also introduce B3++, which incorporates a small number of explicitly mined hard negatives and improved instruction prompts to help the model decouple diverse tasks.

Key Results

The core strength of B3 is its ability to maintain high performance even as batch sizes decrease. As shown in the comparison below, B3 consistently outperforms random batching across In-Distribution (ID) and Out-of-Distribution (OOD) tasks.

Performance comparison between B3 and random batching across different batch sizes.

Key findings include:

  • State-of-the-Art Performance: B3++ sets a new SOTA on the Massive Multimodal Embedding Benchmark (MMEB), outperforming previous best methods by +2.9 points at the 2B scale (68.1 avg) and +1.3 points at the 7B scale (72.0 avg).
  • Efficiency Gains: A B3-trained model with a batch size of just 64 outperformed the previous 2B SOTA model (LLaVE), which requires batch sizes 4 to 16 times larger.
  • Teacher Independence: The teacher model does not need to be state-of-the-art; even a 400M CLIP model provides sufficient signal for significant student gains.
  • Theoretical Backing: The authors provide mathematical proof that clustering mutually strong negatives tightly bounds the global contrastive loss.

Discussion and Limitations

The primary drawback of B3 is the extra time required for the offline preprocessing step (ranking the dataset). However, this step is highly parallelizable and only needs to be performed once. The resulting gains in training efficiency and model performance suggest that smart batch mining is a viable alternative to scaling hardware for contrastive learning. Future work will explore scaling B3 to text-only and more diverse multimodal scenarios.

Summary updated

BibTeX
@inproceedings{thirukovalluru2025breaking,
  author = {Raghuveer Thirukovalluru and Rui Meng and Ye Liu and Karthikeyan K and Mingyi Su and Ping Nie and Semih Yavuz and Yingbo Zhou and Wenhu Chen and Bhuwan Dhingra},
  title = {{Breaking the Batch Barrier (B3) of Contrastive Learning via Smart Batch Mining}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2025},
  url = {https://openreview.net/forum?id=M8zmlixh9y},
}
Figure