Capacity-Limited Vouching Graphs for Filtering Web Image-Text Data

Models like CLIP learn to match images with text by training on billions of image-caption pairs scraped from the web. Many of those captions do not describe the picture. Some are wrong, some are off-topic, some are boilerplate. The strongest recent noise detectors judge a pair by asking its neighbors: do images that look like this one come with captions that read like this one? The trouble is that the web is full of near-copies. A stock photo reposted a thousand times with the same watermark caption, or a shop page template stamped onto varied product shots, creates dense clusters that vouch for one another. A neighbor-consensus detector then counts repetition as agreement.

We propose to treat "who vouches for whom" as something to optimize rather than fix in advance. Each pair is a node in a nearest-neighbor graph. We learn continuous edge weights (how much each neighbor's testimony counts) jointly with continuous inclusion weights (how likely each pair is to be kept for training). Two rules shape the result. Every sample has a fixed vouching budget, and so does every recipient. Near-duplicates are barred from vouching for each other and are instead pushed to share inclusion mass. The relaxed inclusion weights are used directly as sampling probabilities during CLIP pretraining, so they never need to be rounded to keep/drop decisions.

Core Claim

Neighbor-consensus filtering beats pointwise image-text similarity on web data. Its remaining failure is that redundancy and hub samples inflate consensus. A continuous relaxation of a capacity-constrained vouching graph, solved jointly with sample inclusion, removes that failure without any external target dataset. On DataComp this should improve over both static neighbor consensus and a two-stage "consensus score plus deduplication" pipeline at the same data budget.

The claim is falsifiable at the level of its key ingredient. If removing the capacity and duplicate constraints does not hurt, the proposal is wrong, even if the method is competitive overall.

Where This Sits

Three strands of prior work motivate the idea.

LEMoN shows that neighbor consensus works. It scores a pair by the image-text distance plus how far the captions of the image's nearest neighbors sit from the caption, and symmetrically for text neighbors. It beats CLIP similarity by over 3% AUROC on classification and up to 6.3% on captioning error detection. Its graph is static, its terms are combined with fixed weights, and it produces a hard ranking. Nothing in it discounts neighbors that are copies of each other. That is the gap we target.

SDM and Group-MATES show that samples must be selected as a group. SDM finds that pointwise scoring over-selects redundant high scorers and drops rare concepts. Group-MATES finds that individual utility diverges from group utility once samples interact through redundancy ("cancellation"). Both solve the group problem discretely. SDM uses greedy submodular matching against an ImageNet target, and its authors leave target-free selection open. Group-MATES uses 10,000 discrete clusters, a trained influence oracle, and language data. We keep their lesson about redundancy but drop the external target and the discrete greedy loop.

A third group supplies the method. VIB-GSL learns denoised graph structure by relaxing edges with Gumbel-Softmax, a trick that replaces a hard random choice with a smooth, temperature-controlled approximation. DGA makes budgeted edge edits differentiable with Gumbel top-k sampling and reports a 6x speedup and 11x memory reduction over discrete bi-level attacks. PRCut turns a combinatorial graph cut into a bound trainable by mini-batch gradient descent. Controlling Continuous Relaxation for Combinatorial Optimization addresses how relaxed subset solutions behave when mapped back to discrete choices.

All of these work on citation graphs or small benchmarks. None addresses web pretraining data. The known weakness of relaxation, the "snapping" gap where rounding soft weights breaks the optimized solution, mostly disappears in our setting: a data sampler can consume probabilities directly.

The Objective

Each web pair $i$ has frozen image and text embeddings from an off-the-shelf CLIP. We build a sparse edge set $E$ from each sample's $k$ nearest image neighbors and $k$ nearest text neighbors. Each edge carries an agreement score $a_{ij}$ that follows LEMoN's logic. If $j$ is an image neighbor of $i$, $a_{ij}$ is the text-text cosine between their captions. If $j$ is a text neighbor, $a_{ij}$ is the image-image cosine.

Pairs that are near-identical in both modalities form a separate duplicate set $D$. Duplicate pairs are removed from $E$, so copies cannot vouch for each other.

We solve

$$\max_{m,\,W}\; \sum_{(i,j)\in E} W_{ij}\, m_i m_j\, a_{ij} \;-\; \lambda \sum_{(i,j)\in D} m_i m_j \;+\; \tau H(W).$$

The variables and constraints are as follows. Here $m_i \in [0,1]$ is the inclusion weight of sample $i$, and the weights sum to the data budget $B$. $W_{ij} \ge 0$ is how much of $i$'s vouching budget goes to neighbor $j$. Each row of $W$ sums to one, so every sample spends one unit of testimony. Each column sums to at most $c$, so no hub sample can be vouched for by everyone. $\lambda$ sets how strongly duplicates must share inclusion mass. $H(W)$ is the entropy of $W$, and $\tau$ is a temperature that keeps $W$ smooth.

Given $m$, the $W$-step is an entropically regularized transport problem, which is a smooth relaxation of a capacity-limited matching. It is solved by Sinkhorn-style row and column rescaling on the sparse edge set. Given $W$, the $m$-step is projected gradient ascent onto the budgeted box.

The first term rewards kept samples that are vouched for by other kept samples. That makes the problem non-submodular, so greedy selection loses its usual guarantees. This is the concrete reason to use a continuous relaxation here rather than to relabel a greedy method. After convergence, $m$ becomes the sampling distribution for CLIP training at budget $B$.

Research Program

The work has three parts.

First, we build the graph machinery at DataComp small (12.8M pool) and medium (128M pool) scale. This covers approximate $k$-NN over precomputed CLIP embeddings, sharded sparse Sinkhorn, and mini-batch projected ascent over graph partitions. We measure wall-clock cost against CLIP similarity scoring and against captioning-based filtering.

Second, we run controlled noise studies on the LEMoN suite (MSCOCO, Flickr30k) with LEMoN's synthetic corruptions. We add one new corruption that isolates our hypothesis: injected clusters of near-duplicate or templated mismatched pairs. The prediction is that static consensus degrades as cluster size grows, while the capacity-limited graph does not.

Third, we train CLIP models on the resulting subsets under the fixed DataComp protocol. We also run sensitivity sweeps over $k$, $c$, $\lambda$ and the temperature $\tau$, since temperature sensitivity is a known weakness of these relaxations.

Baselines

The naive reference points are training on a random subset of the pool at the same budget, and pointwise CLIP-similarity (CLIPScore) thresholding at the best-performing keep fraction. Sieve reports CLIPScore peaking at about 30% of the data. All methods use the same pool, the same CLIP embeddings for scoring, the same DataComp training recipe and compute, and the same sweep of budgets. Beating CLIPScore is necessary but not interesting.

The strongest competitor on the precise question, whether learned vouching beats fixed vouching, is LEMoN applied as a data filter. We reimplement it on the same $k$-NN graph and tune its combination weights and keep fraction with the same number of trials we give our hyperparameters. It detects the same kind of noise we target, so any gain over it isolates the learned graph. LEMoN reports 41% versus 32.5% precision over CLIP similarity in its top-200 Flickr30k audit, plus the AUROC gains above. We found no reported result on Lacuna for LEMoN as a DataComp pretraining filter. We therefore produce that number ourselves. Beating it means a higher DataComp 38-task average at matched budget, and higher AUROC on the duplicate-cluster corruption.

The strongest existing filters we compare against are these three.

Sieve, which scores alt-text against BLIP-generated captions in text space, reports a 2.6% gain over CLIPScore on the 38-task average at medium scale and 1.7% at large scale. Matching Sieve's margin over CLIPScore at medium scale without running a captioner is our target. Combining the two is a secondary experiment.

SDM reports 35.2% ImageNet zero-shot accuracy at DataComp-medium, but it selects toward an ImageNet target. We report its number on ImageNet and on the 38-task average, and treat the latter as the fair comparison for a target-free method.

We run Group-MATES only as a conceptual reference, since its public code (facebookresearch/Group-MATES) and reported gains are for language pretraining on DCLM.

For context, DataComp reports 79.2% ImageNet zero-shot for DataComp-1B at ViT-L/14. That figure is at a scale we do not claim to reach.

The key ablations are:

  • the full objective with $c=\infty$ and duplicate edges allowed to vouch, which leaves only a learned but unconstrained graph;
  • the constraints kept but with $W$ frozen to uniform over neighbors, which leaves only static capacity-aware consensus;
  • the relaxed $m$ rounded to a hard top-$B$ set instead of used as sampling probabilities.

The first two ablations must both lose to the full method for the core claim to stand.

Why not just…?

Why not just threshold CLIPScore? Prior work already documents why it falls short. Sieve shows CLIP-based filtering inherits the encoder's blind spots and is beaten by 2.6% at medium scale. SDM shows it over-selects redundant samples and drops concept-critical ones. LEMoN shows neighbor consensus beats it on error detection. We include it only as the floor.

Why not just run LEMoN, then deduplicate and cap each cluster? This is the real threat. A two-stage pipeline of consensus scores, semantic deduplication and per-cluster quotas addresses both noise and redundancy with no optimization at all. The difference is ordering. In the pipeline, duplicates have already inflated the consensus scores before deduplication runs. In our objective, a sample's credibility depends on whether its vouchers survive selection, and on vouchers that are not copies of it. We run this pipeline with the same tuning budget. If it matches us on DataComp and on the duplicate-cluster corruption, we will report that the relaxation is unnecessary.

Why not just use greedy submodular selection with consensus-weighted coverage? Coverage alone is submodular and greedy handles it well. The mutual-vouching term is not submodular, so greedy loses its guarantee, and it runs sequentially rather than as parallel sparse updates. We compare against lazy-greedy facility location weighted by LEMoN scores at the small scale, where it is affordable, and report both accuracy and wall-clock.

Why not just recaption the images? Sieve shows captioner-based checks help. But captioning every image in a pool is far more expensive than embedding operations, and captioners strip rare entities and context from web text, as Kuznetsova et al. observe for web captions. We treat recaptioning as complementary: we test whether adding our weights on top of Sieve still helps.

Why not just reweight each sample's loss by its consensus score? Soft per-sample weights without a learned graph test whether "soft instead of hard" explains any gain. We run LEMoN scores passed through a tuned temperature as sampling probabilities. If this matches the full method, the gain comes from softness, not from the graph.

Decisive Checks

Three results decide the proposal.

The first is the injected duplicate-cluster experiment on MSCOCO and Flickr30k. Detection AUROC is plotted against cluster size for LEMoN, the unconstrained-graph ablation and the full method. The core claim predicts that LEMoN's curve falls while ours stays flat.

The second is DataComp small and medium. We report the 38-task average, ImageNet zero-shot accuracy and retrieval at matched budgets against LEMoN, LEMoN plus deduplication, and Sieve. A win over LEMoN plus deduplication at medium scale is the result that justifies the relaxation.

The third is a human audit of 200 pairs that our method removes but LEMoN keeps, and 200 the reverse. It checks whether the removed pairs are actually templated or duplicated noise, rather than rare but valid concepts.