acceptodds
Under review as a conference paper at ICLR 2027

MPS: Relaxation-Free Solving for Blind Vision–Language Matching at Scale

Abstract

In blind vision–language matching, the goal is to recover the correspondence between the class representations of a vision encoder and those of a language encoder without access to a single paired example. The task is naturally posed as the minimization of the Gromov–Wasserstein distortion between the intra-modal distance kernels of the two modalities, an instance of the quadratic assignment problem. We treat this problem entirely within its combinatorial domain, so that the search never leaves the set of permutations and no relaxation, in the sense of losing tightness, is introduced at any stage. Reducing the fourth-order Lawler formulation to an equivalent Koopmans–Beckmann trace maximization removes the cost tensor whose size otherwise limits the problems that can be posed. Shifting the spectrum of each kernel then makes the objective convex, and its minorization–maximization analysis shows why a single search trajectory halts short of the optimum, while a closed-form identity for the entire exchange neighbourhood, obtained from a single matrix product, makes a population-based search affordable at scale. We prove monotone ascent, convergence of the objective sequence and finite termination of the iterates. On benchmarks extending well beyond the scales previously studied, where the dual approach no longer delivers its guarantee of optimality, our solver outperforms state-of-the-art and benchmark methods in distortion at every problem size, matches more classes correctly than the dual solver on average, and remains interruptible at any moment with a feasible matching in hand.

Primary area:
optimization
Keywords:
blind vision–language matching, combinatorial optimization, Gromov–Wasserstein distortion, multimodal representation alignment, quadratic assignment problem

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_fXzJOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes MPS (Memetic Primal Search), a combinatorial optimization method for blind vision-language matching without paired examples. It reformulates Gromov-Wasserstein distortion minimization as a quadratic assignment problem and combines spectral shifting, efficient exchange-neighborhood evaluation, and population-based recombination to improve matching solutions. Experiments across three datasets and multiple encoder configurations demonstrate lower distortion than the evaluated baselines, although absolute semantic matching accuracy remains limited.

Critical strengths
  1. Well-defined optimization problem. The paper studies blind correspondence recovery between independently trained vision and language encoders without paired supervision, presenting a mathematically precise formulation of a challenging problem.

  2. Efficient combinatorial optimization. The tensor-free formulation and closed-form exchange-neighborhood evaluation substantially reduce computational and memory requirements, enabling matching problems involving several hundred classes.

  3. Useful theoretical analysis. The spectral shifting argument establishes an objective-preserving convex extension, while the convergence analysis provides guarantees of monotonic improvement and finite termination under the stated conditions.

  4. Consistent optimization improvements. MPS achieves lower Gromov-Wasserstein distortion than the evaluated baselines across the reported problem sizes, including improvements over the factorized dual solver.

  5. Extensive empirical evaluation. The experiments cover multiple datasets, encoder configurations, and problem sizes, with additional studies on initialization, runtime budgets, and small-scale global optimality.

  6. Anytime feasibility. The method maintains a valid permutation throughout optimization, providing a practical advantage over approaches that may fail to return a feasible solution within the allocated computational budget.

Critical weaknesses
  1. Insufficient motivation for the underlying matching objective. The paper adopts Gromov-Wasserstein distortion as the principal objective for blind vision-language matching, but does not sufficiently justify why minimizing discrepancies between intra-modal distance structures should reliably recover semantic correspondences. The Platonic Representation Hypothesis is cited, but its relevance to the particular independently trained encoders and class-level distance matrices used here requires stronger empirical or conceptual support.

  2. Insufficient justification of the Koopmans-Beckmann formulation. Although the reduction from the Lawler formulation is mathematically valid and standard, the paper emphasizes its computational advantages without sufficiently explaining its implications for the matching objective and the proposed optimization strategy. A clearer distinction between a mathematically equivalent reformulation and a genuinely new optimization contribution would improve the technical positioning.

  3. Ambiguity between solving and approximating the matching problem. The title and several statements suggest that the proposed approach solves blind vision-language matching, whereas the theoretical guarantees establish convergence only to an exchange-local optimum. The method does not guarantee recovery of a globally optimal permutation or correct semantic correspondence. The paper should consistently characterize MPS as an approximate combinatorial solver rather than imply that the original matching problem is solved exactly.

  4. Limited practical matching effectiveness. Despite consistently reducing Gromov-Wasserstein distortion, the reported semantic matching accuracy remains low, ranging from 7.21% to 2.85% across the problem-size bands in Table 2. This suggests that optimization quality alone may not resolve the fundamental correspondence problem, raising concerns about the practical significance of the improvements.

  5. Moderate methodological novelty relative to classical QAP optimization. The Koopmans-Beckmann formulation, spectral shifting, local exchange search, and memetic recombination build upon established optimization techniques. Although the simultaneous neighborhood evaluation is useful, the paper does not sufficiently distinguish its contribution from specialized QAP solvers and existing incremental exchange-evaluation methods.

  6. Overextended contribution statements. The introduction lists six separate contributions, several of which are closely related or describe consequences of the same underlying design. For example, the tensor-free formulation, efficient neighborhood evaluation, and scalability are interconnected, while convergence and anytime feasibility are related algorithmic properties. Consolidating these into a smaller number of substantive contributions would make the paper's novelty clearer.

  7. Insufficient explanation of missing experimental entries. Table 1 uses dashes for 2-opt and FHG at certain problem sizes without explicitly explaining their meaning in the table caption. Although the main text discusses solver failures and computational limits, it remains unclear from the table whether each missing value represents a timeout, failure to return a feasible solution, numerical issues, or an experiment that was not conducted. This distinction matters when interpreting the claimed scalability advantages.

  8. Insufficient discussion of experimental findings. The main paper provides extensive quantitative comparisons but relatively limited discussion of why the method succeeds or fails in different settings. In particular, the relationship between optimization distortion and semantic matching accuracy, the behavior of different encoder combinations, and the limitations of the underlying geometric matching assumption deserve more detailed interpretation. The Discussion and Limitations section is particularly brief relative to the technical and experimental content.

  9. Presentation and organization could be improved. The notation section occupies space in the main manuscript that could instead be used to strengthen the methodological motivation, experimental discussion, and explanation of failure cases. Moving detailed notation to the appendix and consolidating the contribution statements would make the narrative more focused.

  10. Incomplete comparison with specialized QAP solvers. Given that the method operates directly on a classical quadratic assignment formulation, runtime-matched comparisons against established memetic and robust tabu-search algorithms would help establish whether the proposed solver advances the broader combinatorial optimization literature.

  11. Limited generalization beyond class-level matching. The experimental protocol relies on class-level representations and assumes equal numbers of corresponding semantic categories. The method is not evaluated under partial overlap, missing categories, or instance-level correspondence, limiting its demonstrated applicability to more realistic blind alignment settings.

Questions for authors
  1. Justification of Gromov-Wasserstein distortion. Why is Gromov-Wasserstein distortion particularly appropriate for recovering semantic correspondences between independently trained vision and language encoders? Can the authors provide theoretical or empirical evidence that minimizing this objective correlates reliably with correct semantic matching?

  2. Applicability of the Platonic Representation Hypothesis. The introduction cites this hypothesis to motivate shared representational structure. However, how strongly does this hypothesis apply to the class-level embeddings considered here? Could the authors quantify the similarity between the original intra-modal geometries before optimization?

  3. Role of the Koopmans-Beckmann formulation. Beyond eliminating the fourth-order cost tensor, what additional insight or algorithmic advantage does this reformulation provide? Can the authors more clearly distinguish its established mathematical properties from the contributions introduced in this paper?

  4. Exact versus approximate optimization. Since MPS only guarantees convergence to an exchange-local optimum, can the authors clarify the use of terms such as "solving" and "relaxation-free" throughout the paper? In particular, the absence of a continuous relaxation should not be confused with global optimality or exact solution recovery.

  5. Interpretation of missing results. In Table 1, what exactly do the dashes for 2-opt and FHG represent? Were these methods unable to return feasible solutions, terminated by the time or memory limits, or simply not evaluated? Please clarify this in the table caption and provide the corresponding failure statistics where available.

  6. Relationship between distortion and matching accuracy. Why does the substantial improvement in optimization quality translate into relatively limited improvements in semantic matching accuracy? Could the authors analyze cases where MPS achieves lower distortion but fails to recover the correct class correspondence?

  7. Comparison with specialized QAP algorithms. How does MPS compare with established robust tabu-search and memetic QAP solvers under matched runtime budgets? Such comparisons would help clarify the methodological novelty and optimization advantages.

  8. Contribution of individual algorithmic components. Can the authors more explicitly separate the empirical contributions of spectral shifting, closed-form neighborhood evaluation, population-based search, and recombination? In particular, spectral shifting primarily supports the theoretical analysis rather than directly driving the reported exchange-based search.

  9. Experimental interpretation. Could the authors expand the discussion of why certain problem sizes or encoder configurations are more challenging? An analysis connecting geometric consistency, optimization behavior, and semantic accuracy would considerably strengthen the paper.

  10. Scalability and failure cases. How does MPS behave beyond the evaluated 365 classes, and what are its principal failure modes? Additional analysis of convergence speed, population diversity, and difficult matching instances would help characterize its limitations.

  11. Paper organization. Could the authors consolidate the six contribution statements into fewer central contributions and move the detailed notation to the appendix? The resulting space could be used to provide a more substantive discussion of the theoretical assumptions and practical implications of the experimental results.

  12. Realistic correspondence settings. Can the method accommodate unequal class sets, incomplete correspondences, or partially overlapping vocabularies? These cases would help establish its relevance beyond the controlled class-level matching protocol.

Reviewer_M49NOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes Memetic Primal Search (MPS), a population-based optimization algorithm for matching vision language models without paired examples. The goal consists of identifying correspondences between visual and textual class latent space representations by comparing their respective pairwise distance structures.

The authors reformulate the Gromov-Wasserstein objective as an equivalent quadratic assignment problem, avoiding the explicit cost of constructing a fourth-order tensor. They also introduce a spectral transformation that makes the continuous objective convex while preserving the optimal discrete assignments.

Their proposed solver combines a local search over pairwise exchanges with population-based recombination. They derive closed-form expression that allows all pairwise exchanges to be evaluated through a single matrix multiplication.

The method is evaluated on three datasets, with problem sizes reaching 365 classes. The authors report consistently lower matching distortion than the selected baselines, improved average matching accuracy relative to the dual solver, and the ability to return a feasible assignment at any point during optimization.

Critical strengths

1.The paper addresses a challenging combinatorial optimization problem. The tensor free representation and population based search are attractive for large dimensional applications. The empirical evaluation covers a substantially larger set of classes than previous work on this particular application, and the solver consistently achieves lower distortion than the evaluated alternatives. Its anytime property is also useful in computationally constrained settings.

  1. The manuscript provides explicit derivations of equivalence, spectral shifting, exchange neighbourhood evaluation, and convergence properties. The experiments include several datasets, encoder architectures, and additional quadratic-assignment benchmarks. The analysis of the dual solver's deteriorating bounds is informative and helps frame the practical limitations of the existing approach.
Critical weaknesses
  1. The computational advantage of the proposed algorithm is not sufficiently established.

The manuscript devotes considerable attention to spectral convexification and minorization/maximization. In Appendix D it is stated that the reported solver uses the original kernels and the exchange search, rather than the MM linearization iteration. Consequently, the main theoretical transformation does not seem to directly (or at least, uniquely) explain the performance of the algorithm.

Although the simultaneous matrix product formula is potentially useful, its O(N3)O(N^3) cost per refinement iteration should be compared with existing incremental delta implementations, which can update the complete neighbourhood in O(N2)O(N^2) operations after a swap. The current experimental comparison does not convincingly establish an advantage over these stronger optimization alternatives.

  1. The empirical evidence does not adequately isolate the source or practical significance of the improvements.

The ablation in Table S2 evaluates the advantage over multi-start and iterated local search at N=100N=100, using only four draws. Appendix F uses inner product kernels for these experiments, whereas the principal evaluation uses Euclidean distance kernels. Unclear to this reviewer whether the same relative advantage holds in the main experimental setting, especially for N≥150N \geq 150.

Furthermore, some competing methods terminate after a single local-search trajectory, whereas MPS continues exploring for a much longer computational budget. Stronger budget-matched multi-start and memetic baselines are needed.

The improvements in distortion are relatively small against the strongest baseline, and the absolute matching accuracy remains low. For example, Table 2 reports 2.85% accuracy for MPS in the 151–300-class band, although this is substantially above chance. The practical significance of reducing distortion without achieving much higher matching accuracy requires further discussion.

Questions for authors
  1. Since Appendix D states that the main solver does not use the MM linearization step, could the authors clarify which theoretical components directly contribute to the observed performance? Does the spectral shift play any operational role beyond motivating the analysis?

  2. Could the authors extend the multi-start versus recombination ablation to Euclidean-distance kernels at larger problem sizes (particularly N≥150N \geq 150)? This seems important because the existing ablation uses a different kernel and only four draws at N=100N=100.

  3. How consistent are the reported improvements across independent random seeds? Could the authors report variability and confidence intervals for the strongest comparisons?

Reviewer_Tuj6OpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies blind vision–language matching, aiming to recover correspondences between visual and textual class representations without paired examples. It proposes Memetic Primal Search (MPS), which combines population-based search, pairwise-exchange local refinement, and recombination to minimize Gromov–Wasserstein distortion. The method uses a tensor-free trace formulation and a matrix-based evaluation of candidate exchanges to handle problems involving several hundred classes. Experiments report consistently lower distortion than the evaluated baselines an improvements in matching accuracy.

Critical strengths
  1. The problems being studied is important and relatively under-studied, matching unsupervised image-text pairs have strong potential in modern VLM application as many existing training data contains noise, or sometimes paired data are hard to obtain.

  2. The presentation of this paper is clear, and the writing is easy to follow.

  3. This paper chooses a theoretical-centered approach, offers a more principled and non-herustic perspective, which is generally more appreciated in this area. The theoretical results and properties appears to be correct with coarse checking.

  4. While this area has not been well-explored, this paper still considered many relevant baselines, such as GW-OT.

Critical weaknesses
  1. One of the major issue of this paper is the lack of technical novelty, as most of the theory and techniques used in this paper are already well-known.

  2. The paper overlooks closely related work. The convexity argument is largely anticipated by [1] for Euclidean-kernel matching, the solver is not compared against strong memetic QAP baselines such as Benlic & Hao [2], and the cross-modal motivation omits Li et al. [3], who already link vision–language Gromov–Wasserstein distance to cross-modal learnability and downstream VLM performance.

  3. The paper emphasizes reducing naïve exchange-neighbourhood evaluation from O(N^4) to O(N^3). However, established QAP implementations maintain swap costs incrementally in O(N^2) per iteration [4]. A dense matrix multiplication may still be faster in practice, but this needs direct timing comparisons against efficient incremental implementations.

  4. It is not clear how many trials of solvers with different random seed are used, given the inherent randomness of MPS.

[1] (Probably) Concave Graph Matching, NeurIPS 2018.

[2] Memetic Search for the Quadratic Assignment Problem,ESWA 2015.

[3] Rethinking Model Selection in VLM Through the Lens of Gromov-Wasserstein Distance, CVPR 2026.

[4] An Efficient Implementation of the Robust Tabu Search Heuristic for Sparse Quadratic Assignment Problems, EJOR 2011.

Questions for authors

It is also well-known that, the choice of different layer representations matters greatly for the resulting VLM as well as representation matching, did the authors investigate the influence of which layer to extract representation, verifying the robustness of MPS?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.