Technical Summary: KODA – Contrastive Representation Comparison and Alignment for Vision-Language Foundation Models

1. Problem Statement

Vision-language foundation models (e.g., CLIP, SigLIP, BLIP) are central to modern multimodal systems, yet their representations are typically compared only through downstream task performance (e.g., retrieval accuracy, zero-shot classification). Such aggregate metrics fail to explain how different models structurally organize data or induce different groupings of image-text pairs.

Existing methods for interpretable embedding comparison, such as the SPEC framework, analyze kernel-difference matrices but do not explicitly enforce an asymmetric objective. Consequently, they may identify structures common to both embeddings or aggregate effects rather than isolating specific sample subsets that are weakly clustered under one representation but strongly clustered under another. This paper addresses the task of Contrastive Embedding Clustering: identifying sample subsets (or directions) that exhibit coherent structure in one embedding space while appearing diffuse or unstructured in a reference embedding space.

2. Methodology: KODA Framework

The authors propose KODA (Kernel Optimization for Discrepancy Analysis), a kernel-based framework formulated as a constrained optimization problem.

2.1. Core Optimization Formulation

Given two embeddings $A$ and $B$ inducing normalized kernel similarity matrices $K_A$ and $K_B$ on a reference dataset $\{x_i\}_{i=1}^n$, KODA seeks a direction $x \in \mathbb{R}^n$ that maximizes clustering under $K_A$ while being constrained to be weakly clustered under $K_B$. The problem is defined as:

$$\begin{aligned} \max_{x \in \mathbb{R}^n} \quad & x^\top K_A x \\ \text{s.t.} \quad & x^\top K_B x \leq \epsilon \\ & \|x\|_2^2 = 1 \end{aligned}$$

where $\epsilon > 0$ is a threshold controlling the degree of weak clustering allowed under the reference embedding $B$.

2.2. Efficient Solution via Spectral Characterization

Although the problem is non-convex, the authors show via KKT conditions that any optimizer $x^*$ satisfies a generalized eigenvalue equation:
$$(K_A - \lambda^* K_B) x^* = \nu^* x^*$$
where $\lambda^* \geq 0$ is a Lagrange multiplier. This allows KODA to solve the problem via a one-dimensional search over $\lambda$: for each $\lambda$, compute the leading eigenvector of $K_A - \lambda K_B$ and check if it satisfies the constraint $x^\top K_B x \leq \epsilon$.

To extract multiple discrepancy modes, KODA iteratively solves this problem, enforcing orthogonality to previously found directions using a projection matrix $P = I - UU^\top$.

2.3. Scalability via Covariance Blocks and Random Features

Direct eigendecomposition of $n \times n$ kernel matrices is computationally prohibitive for large datasets ($n \gtrsim 20,000$). KODA addresses this by leveraging explicit feature representations (e.g., Random Fourier Features for shift-invariant kernels).
If $K_A = \Phi_A \Phi_A^\top$ and $K_B = \Phi_B \Phi_B^\top$ with feature dimensions $d_1, d_2 \ll n$, the eigenvector computation for $K_A - \lambda K_B$ is reduced to an eigenproblem of size $(d_1 + d_2) \times (d_1 + d_2)$ involving covariance blocks:
$$M_\lambda = \begin{bmatrix} \Phi_A^\top \Phi_A & \Phi_A^\top \Phi_B \\ -\lambda \Phi_B^\top \Phi_A & -\lambda \Phi_B^\top \Phi_B \end{bmatrix}$$
This reduces complexity from $O(n^2)$ to $O(n(d_1+d_2))$, enabling application to large-scale datasets.

2.4. Extension to Multi-modal Embeddings

For paired data (e.g., image-text), KODA constructs a unified multimodal kernel using the product-kernel formulation:
$$k((u, v), (u', v')) = k_x(u, u') \cdot k_t(v, v')$$
where $k_x$ and $k_t$ are modality-specific kernels. The resulting kernel matrix is the Hadamard product of the unimodal kernel matrices ($K = K_x \odot K_t$). To handle the tensor-product feature space (which scales as $d_x d_t$), KODA employs Joint Random Fourier Features (RFF). This approximates the product kernel with a feature map of dimension $2r$, providing theoretical guarantees on the stability of the leading eigenspaces relative to the true product kernel.

3. Key Contributions

1. Contrastive Embedding Clustering Task: The paper formalizes the identification of sample subsets that are strongly clustered in one embedding but weakly clustered in another as a constrained optimization problem, distinct from global difference analysis.
2. KODA Algorithm: A kernel-based optimization framework that solves this task via a constrained quadratic program, admitting an efficient solution through structured spectral computations.
3. Scalable Implementation: The development of covariance-block reductions and joint random Fourier feature approximations allows KODA to scale to large vision-language datasets without explicit construction of massive kernel matrices.
4. Interpretable Discrepancy Directions: The method yields interpretable directions associated with specific sample subsets and modality interactions, facilitating targeted data curation and model alignment.

4. Experimental Results

The authors evaluated KODA on unimodal (ImageNet, FFHQ, AFHQ) and multimodal (MS-COCO) datasets using models including CLIP, DINOv2, BLIP, OpenCLIP, SigLIP, and SigLIP2.

• Discrepancy Discovery: KODA successfully identified consistent and interpretable discrepancy structures. For example, on FFHQ, it found directions where DINOv2 grouped samples coherently (e.g., specific facial attributes) while CLIP did not. On MS-COCO, it identified image-text pairs where BLIP formed clearer joint structures than CLIP (e.g., specific sports actions like baseball or surfing).
• Comparison with Baselines: In unimodal settings, KODA outperformed the SPEC baseline in finding multiple discrepancy modes. Quantitative metrics (Generalized Rayleigh Quotient) showed KODA's directions had significantly higher asymmetry scores (e.g., ~20x stronger at low constraint quantiles) compared to SPEC.
• Representation Alignment: The paper demonstrates that the sample subsets identified by KODA can be used for contrastive embedding alignment. Fine-tuning CLIP on KODA-selected slices (where CLIP was weak and DINOv2/BLIP was strong) significantly improved alignment metrics (AMI, NMI, ARI) on those specific slices, bringing the aligned model's geometry closer to the target model.
• Retrieval Analysis: On MS-COCO, the KODA-selected subset amplified the performance gap between models (e.g., CLIP vs. SigLIP), revealing that SigLIP maintained better retrieval performance on the specific discrepancy slices where CLIP struggled.

5. Significance and Limitations

Significance:
The paper claims that KODA provides a principled, unsupervised method for comparing foundation models beyond aggregate downstream metrics. By localizing discrepancies to specific sample subsets, it supports:

• Interpretability: Understanding where and why models differ structurally.
• Model Selection & Debugging: Identifying specific data slices where a model underperforms relative to a reference.
• Targeted Alignment: Using discovered discrepancy slices as actionable data for fine-tuning to align representations.

Limitations:
The authors note that KODA:

• Requires a shared reference dataset sampled from an underlying distribution.
• Focuses on unsupervised discrepancy discovery based on kernel-induced geometry, without leveraging labeled downstream tasks.
• Future work directions include extending the framework to unmatched datasets, supervised discrepancy notions, and stronger statistical guarantees for cluster interpretation.

The code is publicly available at https://github.com/yokiwuuu/KODA.