PaperlayerView exact revision on arXiv

Source-linked AI summary

It's a (Blind) Match! Towards Vision-Language Correspondence without Parallel Data

Dominik Schnaus, Nikita Araslanov, Daniel Cremers

arXiv:2503.24129v2cs.CVcs.LG

TL;DR

The paper asks whether vision and language representations can be matched without parallel data. It formulates blind alignment as a quadratic assignment problem, proposes a solver heuristic, and studies existing models across datasets. The study reports non-trivial matches for some instances, while noting that arbitrary embeddings and some classes cannot yet be matched reliably.

  • Problem

    The conformity between vision and language models remains poorly understood, including whether their representations can be aligned without parallel data.

    Source: §1 · p. 1

  • Method

    The paper formulates unsupervised alignment as a quadratic assignment problem using pairwise similarities, develops a solver heuristic, and selects subsets of matching problems.

    Source: §1 · p. 2, §4.1 · p. 4, §4.2 · p. 5

  • Results

    The study establishes feasibility of non-trivial vision-language matches for some problem instances, and demonstrates an unsupervised classifier with non-trivial accuracy.

    Source: §1 · p. 2, §7 · p. 8

  • Takeaways & Limitations

    The findings support the possibility of semantic image recognition without paired supervision, as shown by the proof-of-concept classifier.

    Source: §1 · p. 2

    Some classes have different representations across vision and language, so they cannot be matched reliably; arbitrary embeddings cannot yet be matched with existing models.

    Source: §6 · p. 8

Abstract

from arXiv · show

The platonic representation hypothesis suggests that vision and language embeddings become more homogeneous as model and dataset sizes increase. In particular, pairwise distances within each modality become more similar. This suggests that as foundation models mature, it may become possible to match vision and language embeddings in a fully unsupervised fashion, i.e. without parallel data. We present the first feasibility study, and investigate conformity of existing vision and language foundation models in the context of unsupervised, or "blind", matching. First, we formulate unsupervised matching as a quadratic assignment problem and introduce a novel heuristic that outperforms previous solvers. We also develop a technique to find optimal matching problems, for which a non-trivial match is very likely. Second, we conduct an extensive study deploying a range of vision and language models on four datasets. Our analysis reveals that for many problem instances, vision and language representations can be indeed matched without supervision. This finding opens up the exciting possibility of embedding semantic knowledge into other modalities virtually annotation-free. As a proof of concept, we showcase an unsupervised classifier, which achieves non-trivial classification accuracy without any image-text annotation.

1. Introduction

The paper studies whether vision and language representations can be matched without parallel data, motivated by possible geometric conformity between the modalities. It formulates blind matching as a quadratic assignment problem and reports non-trivial matches across some model and dataset instances.

1. Introduction

  • The paper frames blind matching as finding vision-language correspondence without any parallel data, extending beyond prior alignment work using a few correspondences.The prior work described here pursued dense alignment from a few correspondences.Source: §1 · p. 1
  • The motivation draws on the platonic representation hypothesis, which posits that textual and visual representations of the same concepts converge to geometrically similar latent spaces.The passage also reports that alignment grows with larger models and training corpora.Source: §1 · pp. 1–2
  • The authors formulate matching as a quadratic assignment problem using only within-modality pairwise distances, and propose a solver extension and criteria for selecting matching subsets.They report that their solver leads to better optima and tighter bounds than previous heuristics.Source: §1 · p. 2
  • The study finds non-trivial vision-language matches across some problem instances and uses this feasibility to demonstrate unsupervised image classification.The study includes 33 vision and 27 language models across four datasets.Source: §1 · p. 2

2. Related work

Prior work studies cross-modal alignment with some supervision, shared embedding spaces, or methods such as Gromov-Wasserstein distance. The paper distinguishes its focus as matching vision and language models without parallel data or parameter training.

2. Related work

  • Zero-shot stitching typically assumes sparse ground-truth image-text pairs, while the paper's focus is fully unsupervised alignment.Prior stitching methods include relative representations, geometric distortion penalties, and affine transforms.Source: §2 · p. 2
  • Unlike prior cross-modal approaches described here, this study aligns vision and language models without parallel data and without parameter training.The related-work passage contrasts the paper with approaches for cross-lingual alignment and cross-modal alignment in model training.Source: §2 · p. 2
  • The related work groups general QAP heuristics into primal and dual methods, and identifies LocalCKA as approximating the task with a linear assignment problem.The passage also describes methods that combine primal and dual solvers.Source: §2 · p. 2
  • As the oracle assignment is increasingly shuffled, Mutual k-NN alignment decreases monotonically; the caption reports this pattern for all considered metrics.The authors use the pattern to justify the metrics in their optimization objective.Source: Figure 2 · p. 3

3. Preliminaries

The paper measures cross-modal alignment through pairwise relations within each modality. It reports that increasing assignment shuffling degrades Mutual k-NN alignment, supporting the use of these pairwise measures in optimization.

3. Preliminaries

  • For each class, the setup averages image and text embeddings from pretrained encoders, then L2-normalizes model outputs and the averaged embeddings.Pairwise similarity matrices are computed within the vision and language spaces.Source: §3 · p. 3
  • Alignment distortion is the sum of elementwise distances between vision and language pairwise similarity matrices, and the formulation can accommodate different measures.The paper notes that Gromov-Wasserstein distance, Mutual k-NN, and CKA are similarity measures, and uses negative inner products to formulate minimization as a distance objective.Source: §3 · p. 3
  • The shuffling experiment measures distortion after randomly permuting an increasing fraction of language embeddings and evaluates alignment with Mutual k-NN.The distortion is computed using the stated pairwise-distortion equations.Source: §3 · p. 3
  • Mutual k-NN alignment decreases strictly monotonically as language embeddings are increasingly shuffled, a pattern also confirmed across considered datasets and kernels.The reported example uses 100 random permutations per level on COCO Captions.Source: §3 · p. 3

4. Blind matching of vision and language

Blind matching is formulated as minimizing pairwise distortion over permutations, yielding a quadratic assignment problem. The section introduces a factorized solver and a way to identify subsets of classes where non-trivial matching is likely.

4. Blind matching of vision and language

  • The matching objective minimizes pairwise distortion over permutations, which is a QAP; the general problem is NP-hard and enumeration requires N! permutations.The formulation uses pairwise relations within the vision and language spaces.Source: §4 · p. 3, §4.1 · p. 4

4.1. The factorized Hahn-Grant solver

  • The solver transfers cost from the quadratic term to linear and constant terms through LAPs, redistributing leader values so later iterations can make further progress.The algorithm terminates when no improvement is possible; if a permutation solves all relevant LAPs, it is a global optimum.Source: §4.1 · p. 4
  • The factorized Hahn-Grant solver adds primal-solution search, reduces memory complexity from O(N^4) to O(N^3), and uses a faster LAP solver.It initializes with FAQ and 2-opt using the best result from 100 random seeds, and evaluates LAP assignments on the QAP objective.Source: §4.1 · p. 5

4.2. Finding optimal matching problems

  • A non-trivial match is not guaranteed for arbitrary category choices, but an optimized subset can make matching very likely even for problem sizes above 10.The authors state that matching accuracy varies substantially with category choice.Source: §4.2 · p. 5
  • Finding an optimal subset is framed as maximizing pairwise alignment subject to selecting exactly N classes, an instance of the p-dispersion-sum problem.The paper states that reasonable approximations can be found using Gurobi despite the problem's general NP-hardness.Source: §4.2 · p. 5

5. Experiments

Across small exact matches, selected larger class subsets, solver comparisons, and an unsupervised classifier, the experiments find non-trivial vision-language assignments without paired data. They also show that matching quality depends on reaching global optima, while successful larger matches cover selected subsets.

5. Experiments

  • The experiments comprise three studies and an application, using 32 vision and 27 language models across varied pretraining methods, architectures, and sizes.For matching, the setup averages image embeddings by class and language embeddings across prompts, then uses the Gromov-Wasserstein distance.Source: §5 · pp. 5–6

5.1. Small-scale matching

  • DINOv2 matches at 80% on CIFAR-10 and 100% on CINIC-10; pretraining strategy matters more than model size, with averages 5.3% and 7.6% above the second-best strategy.These small problems are exactly enumerable, and most tested models exceed the 10% random-permutation baseline.Source: Figure 4 · p. 6, §5.1 · p. 6

5.2. Larger-scale matching

  • For larger class subsets, accuracy declines as problem size grows; CLIP performs best in most cases, while DINOv2 declines more sharply on CIFAR-100.The results suggest language supervision aligns pairwise similarities, though self-supervised DINOv2 also learns aligned distances for some classes.Source: §5.2 · pp. 6–7, Figure 5 · p. 7

5.3. Solver comparison

  • Our solver reaches global optimality through size 40 and gives the best primal solutions most often on larger CIFAR-100 problems; on small problems, it and Gurobi always find the optimum.For larger problems over 40, Gurobi exceeds the 1.5-hour time limit; local solvers can minimize loss yet remain trapped in local minima.Source: §5.3 · pp. 7–8, Table 1 · p. 7, Figure 6 · p. 8

5.4. Application: Unsupervised classifiers

  • DINOv2 with All-Roberta-large-v1 reaches 51.1% classification accuracy, all considered models exceed the 10% random baseline, and results remain below supervised models.The proof of concept clusters image embeddings with K-Means and matches cluster centers to language embeddings without annotation.Source: §5.4 · p. 8

6. Discussion

The discussion finds non-trivial vision-language matching on tested problems, but not for arbitrary embeddings. Representation differences, ambiguous optima, and computational cost limit the scope.

6. Discussion

  • On tested datasets, most small problems and a subset of larger ones yield non-trivial matches, while some classes cannot be matched reliably.The authors report that some concepts are represented differently across modalities, and that the solver does not scale beyond the problem sizes studied.Source: §6 · p. 8
  • Matching arbitrary embeddings remains out of reach when concepts are modality-specific or symmetry creates multiple equivalent local minima.The discussion gives abstract concepts such as “freedom of speech” as an example of a concept that may appear in only one modality.Source: §6 · p. 8
  • O(N^5) computational complexity and a significant primal-dual bound at size 100 make reaching the global optimum infeasible for larger problems.The authors state that their solver does not scale to problems larger than those studied in Sec. 5.2.Source: §6 · p. 8
  • DINOv2 matches best in the small-scale experiment, whereas CLIP and DeiT perform better on CIFAR-100, especially for larger problems.The authors interpret this as DINOv2 representing broader concepts and CLIP and DeiT encoding fine-grained relationships better.Source: §6 · p. 8

7. Conclusion

The paper formulates blind vision-language alignment as a quadratic assignment problem and proposes a solver heuristic. Its experiments establish that non-trivial matching is feasible, with an unsupervised classifier as a proof of concept.

7. Conclusion

  • Blind vision-language alignment is formulated as a quadratic assignment problem using only pairwise similarities, and a new heuristic outperforms previous solvers.The paper identifies technical and empirical contributions to unsupervised alignment.Source: §7 · p. 8
  • The empirical study establishes the feasibility of non-trivial matching between pretrained vision and language models.The authors state that solving general and large-scale matching problems remains an open challenge.Source: §7 · p. 8
  • The proof-of-concept unsupervised classifier is presented as a first step toward applications of blind alignment.The paper describes further applications as avenues opened by the established feasibility.Source: §7 · p. 8

Supplementary Material

The supplementary material expands the metric, experiment, and solver analyses, and adds results across model and dataset combinations.

A. Overview

  • Appendix B shows that the QAP formulation accommodates Mutual k-NN, CKA, and Gromov-Wasserstein distance.Appendix G treats Gromov-Wasserstein optimal transport solvers as solvers for a relaxation of the QAP.Source: A. Overview · p. 11
  • Appendix C reports that distortion metrics decrease as shuffling increases and discusses why randomly initialized networks show a similar trend to pretrained networks.Source: A. Overview · p. 11
  • Appendix D compares the original and factorized Hahn-Grant solvers, including a correctness proof and an ablation of primal and dual estimate improvements.Source: A. Overview · p. 11
  • Appendices E and F detail experimental models and setups and report other combinations, including the greater apparent importance of pretraining than model size in small-scale alignment.Appendix F also reports that solver-comparison results hold across considered model and dataset combinations, including unsupervised classification.Source: A. Overview · p. 11

B.Mutual k-NN and CKA as distortion metrics

This appendix shows how Mutual k-NN, CKA, and Gromov-Wasserstein fit the distortion-metric framework. In the reported small-scale comparison, Gromov-Wasserstein gives comparable or higher matching accuracy on both datasets.

B.Mutual k-NN and CKA as distortion metrics

  • The framework expresses a distortion function as modality-specific terms minus a product term, and accommodates Mutual k-NN, CKA, and Gromov-Wasserstein metrics.The appendix introduces unimodal kernel functions and a distance function as the components of the distortion metrics.Source: B.Mutual k-NN and CKA as distortion… · p. 11
  • Mutual k-NN measures average overlap between the modalities’ nearest neighbors, using top-k indices defined by highest inner product and excluding the sample itself.The appendix uses scaled indicator kernels and a negative inner product as the distortion function to recover the Mutual k-NN metric.Source: B.Mutual k-NN and CKA as distortion… · p. 11
  • With a linear kernel and negative inner product, the framework yields negative CKA [22] [30].The appendix derives the CKA kernels and shows the resulting distortion equals negative CKA.Source: B.Mutual k-NN and CKA as distortion… · pp. 11–12
  • On CIFAR-10 and CINIC-10, Gromov-Wasserstein distance yields comparable or higher matching accuracy than Mutual k-NN [17] and CKA [22].The comparison uses DINOv2 [36] and all-mpnet-base-v2 [43]; the caption identifies the datasets and metrics compared.Source: B.Mutual k-NN and CKA as distortion… · p. 12, Table 3 · p. 12

C. Shuffled vision-language alignment

Shuffling experiments show that vision-language alignment metrics track the degree of correspondence, including for randomly initialized networks and raw pixels. The factorized Hahn-Grant solver reduces memory needs and adds faster LAP solving and a primal heuristic while preserving the original solver’s bounds and LAP solutions under stated assumptions.

C. Shuffled vision-language alignment

  • Similarity decreases and distortion increases monotonically with more shuffling across the considered datasets and metrics, indicating stronger pairwise relations for semantically corresponding representations.The experiment uses 21 shuffling levels and averages over 100 random seeds per level.Source: C. Shuffled vision-language alignment · p. 12, Figure 7 · p. 13
  • Randomly initialized networks show the same decreasing alignment trend as pre-trained networks, with most empirical Lipschitz constants near one indicating approximate distance preservation.The paper attributes the trend to category-level pixel-distribution similarities that can dominate pairwise distances.Source: C. Shuffled vision-language alignment · p. 13, Figure 8 · p. 14, Figure 9 · p. 14

D.1. Proof of equivalence to Hahn-Grant solver

  • Under nonnegative symmetric factor matrices, the factorized and original algorithms produce the same lower bound and LAP solutions by maintaining equivalent cost sums and updates.The factorized version stores dual vectors in tensors U and V rather than updating C in place.Source: §D.1 · pp. 14–15

D. On the factorized Hahn-Grant solver

  • The factorized Hahn-Grant solver reduces memory requirements for factorized costs, reuses LAP assignments in a primal heuristic, and uses faster LAP solvers.The original Hahn-Grant solver iteratively improves the QAP dual bound by solving linear assignment problems.Source: Figure 10 · p. 15

D.1. Proof of equivalence to Hahn-Grant solver

  • Subtracting each factor matrix’s minimum permits running the algorithm on nonnegative matrices, and the offset is then subtracted from the final objective to recover the original optimum.The proof also notes that adding a constant to either factor matrix yields an equivalent optimization problem with an adjusted objective.Source: §D.1 · p. 15

D.2. Implementation details

The implementation uses custom LAP solvers and stopping criteria, while ablations assess factorization, LAP solver choices, LAP primal solutions, and primal heuristics. Their effects differ by problem size and by whether primal solutions or dual bounds are prioritized.

D.2. Implementation details

  • The implementation uses custom C++ forward-reverse auction and Jonker-Volgenant LAP solvers, stopping when dual-bound improvement is below ε = 1e-6 or the primal objective is within ε of the bound.The auction relaxation εauc starts at 0.1 and is multiplied by 0.9 each iteration to trade speed for solution quality.Source: §D.2 · pp. 15–16

D.3. Ablations

  • For size 100, the original solver does not finish its first iteration within two hours, while factorization slightly speeds computation and the Jonker-Volgenant solver gives the tightest bounds empirically.The experiments average five random seeds, with a two-hour limit at size 100 and a one-hour limit at size 40.Source: §D.3 · p. 16, Table 4 · p. 16
  • LAP primal solutions substantially improve primal solutions without changing the dual estimate, while primal heuristics improve primal solutions at the cost of slightly worse bounds.The auction algorithm gives slightly better results at size 40, whereas Jonker-Volgenant gives tighter bounds on large problems.Source: §D.3 · p. 16, Table 5 · p. 16

E. Experimental details

The experiments compare diverse vision and language encoders across four image datasets using precomputed, normalized embeddings and repeated random subsets. Matching is evaluated at small and larger scales, alongside an unsupervised classification setup.

Experimental details

  • The study uses 32 vision models and 27 language models spanning multiple architectures and pretraining strategies, evaluated on CIFAR-10, CINIC-10, CIFAR-100, and ImageNet-100.For ImageNet-100 it uses the validation split; the other datasets use their test splits.Source: E. Experimental details · pp. 16–17
  • Image-wise embeddings are normalized and averaged by class, while language embeddings are averaged over prompts; a uniformly sampled half of image embeddings is used per random seed.Embeddings are precomputed for each model and dataset, with GPUs used only for that precomputation.Source: E. Experimental details · p. 17
  • Small-scale matching enumerates permutations on CIFAR-10 and CINIC-10, while larger-scale problems use selected class subsets and the factorized Hahn-Grant solver under a one-hour limit.The larger-scale setup tests sizes 10 through 100 with ten class subsets and three random seeds per size.Source: E. Experimental details · p. 17
  • The classifier clusters image embeddings into prototypes with K-Means and matches cluster centers to language embeddings using the factorized Hahn-Grant solver.The evaluation uses a random half of vision embeddings and 20 random seeds on CIFAR-10.Source: E. Experimental details · p. 18

F. Evaluation results

Across the reported evaluations, the proposed solver enables non-trivial unsupervised classification and often finds globally optimal small-scale matches. DINOv2 leads matching accuracy across tested model combinations, while model size alone does not consistently improve alignment.

F.1. Comparison of vision and language models

  • DINOv2 achieves the highest matching accuracy across both tested datasets and language models, while larger model capacity shows no clear improvement in matching accuracy or Mutual k-NN.This capacity pattern is reported for CIFAR-10 and CINIC-10.Source: §F.1 · p. 18

F.2. Unsupervised classification: solver comparison

  • Our solver outperforms other solvers in classification and matching accuracy, yielding non-trivial unsupervised classification despite roughly 15% of images being assigned to incorrect K-means clusters.The authors report this as the first non-trivial unsupervised classification result, which previous local solvers did not achieve.Source: §F.2 · p. 18

F.3. Comparison of solvers on small-scale problems

  • The factorized Hahn-Grant solver and Gurobi find global optima for all reported small-scale problems, and for most combinations those optima also yield the best matching accuracy.For four experiments, the global optimum does not give the best matching accuracy.Source: §F.3 · p. 18
  • Matching accuracy is close to random for LocalCKA, OT, and FAQ in most cases, while the reported results identify a global solver as crucial for non-trivial matching.The authors also describe Gromov-Wasserstein distance as a proxy measure for blind matching.Source: §F.3 · p. 21

G. Optimal transport as QAP solver

  • With uniform source and target distributions, optimal transport is equivalent to relaxing the QAP with doubly stochastic matrices, enabling comparison with optimal-transport solver solutions.The equivalence is the basis for the paper’s OT solver comparison.Source: G. Optimal transport as QAP solver · p. 21
Loading 2503.24129v2…