Tools that explain vision-language models such as CLIP (a model that embeds images and text in one shared vector space) increasingly describe each image as a short weighted list of words. An image becomes "0.4 snow + 0.3 dog + 0.2 forest," and the explanation says the model decided "wolf" because of snow. These decompositions treat concepts as a bag of words: each concept adds its own contribution, and no explanation can say "the decision fires only when snow and a canine appear together." We propose to find such conjunctions directly. With a 15,000-word vocabulary there are about 10^8 candidate concept pairs per output class and about 10^12 triples, far too many to enumerate. Randomized tensor sketching compresses all of these products into a fixed-size vector. It uses Count Sketch, a hashing scheme that folds a huge sparse vector into a short one while keeping its large entries recoverable. Because each image activates only 10 to 30 concepts, the interaction structure is sparse, and sparse structure is exactly what Count Sketch recovers well.
The second half of the idea concerns the modality gap. Image and text embeddings in CLIP sit in separate regions of the shared space, and a text dictionary can only be used on images after some alignment step. We hypothesize that a crude alignment leaves directions of the gap unexplained. A sparse solver then covers those directions by recruiting pairs of concepts that jointly point along the gap. The result would be interactions that look meaningful but are geometric artifacts. If this is right, an interaction map does two jobs: it explains model decisions, and it measures how well a given alignment has handled the gap. In short, the proposal fits a sketched quadratic (and cubic) model of a classifier's output over sparse concept codes, decodes the few pairs that really interact, checks each one by editing the embedding, and asks how much of what it finds depends on how the gap was bridged.
Core Claim
Our first claim is that linear concept attribution systematically misses conjunctive decision structure in models that consume CLIP embeddings. Our second claim is that a Tensor Sketch of the concept-code outer product can recover the strongest interacting pairs and triples at vocabulary scale. Recovery should hold to a precision that we check against interventional ground truth, meaning measured changes in the model's output when concepts are removed. Our third, falsifiable claim is that a measurable fraction of the recovered "interactions" are gap artifacts. Under mean-centering alignment, the concept pairs involved will have summed text embeddings that align unusually well with the image-minus-text mean vector. This fraction should shrink under second-order (whitening) alignment. How it behaves when the gap is closed in training, or widened after training, is an open question that the experiments settle.
What the Prior Work Establishes
Two training-free decomposition methods supply the concept codes we build on. SpLiCE mean-centers image embeddings to handle the gap and then solves a non-negative LASSO against about 15,000 text concepts. It reports that 10 to 30 active concepts suffice, with CIFAR-100 zero-shot accuracy of 0.768 against 0.750 for dense CLIP. SCoCCA replaces mean-centering with canonical correlation analysis, a whitening that aligns second-order statistics across the two modalities. It reports a target probability gain under concept editing of 0.95 against SpLiCE's 0.36, with reconstruction cosine 0.99. Both methods are strictly additive. We keep their codes and their alignment choices as experimental factors, and we add what neither has: an interaction model over the codes. The 0.36 versus 0.95 gap is also our motivating evidence that the alignment step changes what the concept codes mean.
The geometry of the gap motivates the artifact hypothesis. Mind the Gap shows that the gap arises from narrow, differently oriented embedding cones, which means it is not a pure translation. The same paper shows that shifting the gap is a tunable knob: CIFAR-10 zero-shot accuracy moves from 0.9013 to 0.9081, and denigration errors on FairFace for one group drop from 15.7% to 13.7% as the gap widens. Closing the Modality Gap Aligns Group-Wise Semantics takes the opposite stance. It trains the gap from 0.47 down to 0.03 and nearly doubles COCO clustering V-measure (from about 13.0 to 23.63). These two papers disagree about whether the gap should be closed, and neither measures what closing it does to concept-level explanations. Our gap-sweep experiment turns that disagreement into a concrete measurement.
Kernel Pooling supplies the core mechanism. It computes sketched feature products up to fourth order through FFT-based circular convolution of Count Sketches, with under 1% kernel approximation error, and reaches 86.2% on CUB-200-2011 against 84.1% for compact bilinear pooling. That work uses sketches as an opaque pooling layer and never decodes which feature pairs matter. We use the same algebra in the reverse direction: we fit coefficients in sketch space and then read out individual pairs. CRAFT (Fel et al.) constrains the design. It uses Sobol sensitivity indices over a small set of factorized concepts, which capture interaction only implicitly and only at small concept counts. It also shows that human-facing concept explanations can beat saliency on the Husky-vs-Wolf test (utility 1.53 against 1.34 for Grad-CAM). We treat Sobol-style estimates as a validation tool on the small set of pairs we recover, not as a competitor at vocabulary scale. The Tucker and tensor-ring sketching literature (Dong et al., Malik and Becker) supplies the general sketch-and-solve pattern, meaning compress, solve on the small version, then refine. That literature also offers a warning: one-pass sketches lose accuracy when the spectrum decays slowly. This is why we add an exact refit step after decoding.
Research Program
The method has three stages. In the first stage we compute non-negative sparse concept codes $w(x) \in \mathbb{R}^V$ for each image $x$ over a vocabulary of $V$ concepts. We do this under three alignments: SpLiCE-style mean-centering, SCoCCA-style whitening, and no alignment. The whitening covariance is estimated with a standard randomized range finder, which is an implementation convenience and not a claimed contribution.
In the second stage we choose a model $f$ to explain. This can be CLIP's own zero-shot class scores, or a small nonlinear classification head trained on frozen CLIP embeddings. We then fit its output for class $k$ as
$$f_k(x) \approx b_k + a_k^\top w + \beta_k^\top \phi(w), \qquad \phi(w) = \mathcal{F}^{-1}\big(\mathcal{F}(S_1 w) \odot \mathcal{F}(S_2 w)\big),$$
In this expression $S_1, S_2 \in \mathbb{R}^{m \times V}$ are independent Count Sketch matrices with hash functions $h_1, h_2$ and random signs $s_1, s_2$. $\mathcal{F}$ is the discrete Fourier transform, and $\phi(w)$ is the length-$m$ Tensor Sketch of the outer product $w \otimes w$, which is the construction used in Kernel Pooling. The linear part is fit first and the sketch is fit on the residual, so that additive effects do not leak into the interaction terms. A third Count Sketch extends the same construction to triples.
In the third stage we decode interaction coefficients from $\beta_k$. For a pair of concepts $i, j$, the estimate is
$$\hat B_{k,ij} = \operatorname{median}_{r}\; s_1^{(r)}(i)\, s_2^{(r)}(j)\, \beta^{(r)}_k\big[(h_1^{(r)}(i) + h_2^{(r)}(j)) \bmod m\big].$$
The median runs over $r$ independent sketch repetitions. It suppresses collisions for the usual Count Sketch reason: a large coefficient survives most repetitions, while a collision corrupts only a few. We decode only pairs that co-occur in the data. We then take the top candidates and refit their coefficients exactly by sparse regression to remove bias.
Every decoded pair is then tested by intervention. We remove concepts $i$, $j$, or both from the embedding, subtracting their weighted text directions in the aligned space and mapping back, as in SpLiCE's editing procedure. We rerun $f$ on the edited embeddings and compute the measured interaction contrast $\Delta_{ij} = f(z) - f(z_{\setminus i}) - f(z_{\setminus j}) + f(z_{\setminus ij})$, where $z_{\setminus i}$ denotes the embedding $z$ with concept $i$ removed. A decoded pair counts as real only if $\Delta_{ij}$ agrees with it on held-out images.
The gap analysis attaches to this pipeline. For each recovered pair we compute the cosine between $c_i + c_j$, the sum of the two concepts' text embeddings, and the gap vector $\mu_I - \mu_T$, the difference between the mean image embedding and the mean text embedding. We call pairs above a threshold calibrated on random pairs "gap-aligned." We then track the gap-aligned share and the interventional confirmation rate across the alignment methods. We also track them across a sweep of gap sizes: CLIP with the gap shifted smaller and larger as in Mind the Gap, and a COCO-trained model using the gap-closing objective of the group-wise semantics paper.
Baselines
The naive reference point is linear concept attribution with no interaction terms. We fit the same regression without $\phi$, on SpLiCE codes and on SCoCCA codes, with the same held-out split and the same amount of regularization tuning. This baseline defines how much output variance is left unexplained. The interaction model beats it if it explains significantly more held-out variance of $f$ and if its decoded pairs pass the interventional test at a rate well above random co-occurring pairs.
The strongest competitor at second order is explicit enumeration. This baseline lists every concept pair that co-occurs in the data as an explicit sparse feature, which is feasible because each image has only about 30 active concepts, and fits an L1-penalized regression exactly. This is essentially what the sketch approximates, so it is the fair upper bound on accuracy. It gets the same codes, data, and hyperparameter search budget, and we measure its wall-clock time and peak memory against ours. At second order the sketch "wins" only if it matches enumeration's precision at top-K within a few points while using fixed memory that does not grow with vocabulary size. At third order enumeration grows to roughly 4,000 triples per image and blows up in memory at ImageNet scale; there we compare against enumeration run on a subsample. For interaction recovery by any method, no reported result was found on Lacuna, so these numbers are new.
The strongest existing concept-editing method is SCoCCA. The file reports its target probability gain as 0.95, against 0.36 for SpLiCE, on ImageNet-500. We use its codes as input to our pipeline, and we also run its single-concept edits as the comparison for our pair edits. The question is whether jointly editing a decoded pair moves the target probability by more than the sum of the two single edits. Larger-than-additive movement would show that the interaction is real and that single-concept editing misses it.
We also run a Sobol baseline in the CRAFT style: second-order Sobol indices estimated over the top 25 concepts per class. It uses the same number of model evaluations that our interventional checks consume. This tests whether a cheap small-set method finds the same pairs we do.
The key ablation removes decoding. Here we keep the same interaction model but pick "interacting" pairs by co-occurrence frequency alone. Beating this ablation shows that the sketched coefficients carry information beyond the simple fact that two concepts often appear together.
Why not just…?
Why not just enumerate co-occurring pairs and run sparse regression? This alternative is a real threat at second order, and we do not argue around it. It is our strongest baseline, and if it is as cheap and as accurate as the sketch at order two, we will report that plainly. The case for sketching then rests on two things. First, at third order the number of explicit features per image grows about tenfold, and total distinct features grow further. Second, sketch memory is fixed as the vocabulary grows beyond 15,000 concepts. The scientific claims about the gap do not depend on which estimator wins. What changes is whether the sketch is the method or merely a convenience, and the order-three experiment decides this.
Why not just add compound phrases like "snowy wolf" to the SpLiCE vocabulary? A phrase atom describes a composition that appears in the embedding. It does not describe a decision rule that fires only when two separately present concepts co-occur. We test this directly: we give the linear baseline a vocabulary augmented with two-word compounds and check whether it recovers conjunctions that we planted in trained heads. If phrase atoms recover the planted conjunctions as well as our method does, the interaction model is unnecessary for those cases, and we will say so.
Why not just use Sobol or Shapley interaction indices, as CRAFT does? These indices are faithful by construction, but they need model evaluations that grow with the number of pairs. That limits them to a few dozen concepts, which is why CRAFT works with small factorized concept sets. Our pipeline screens all co-occurring pairs cheaply and hands a short list to interventional checks. The matched-budget Sobol baseline shows whether screening finds pairs that a small-set method misses because those pairs fall outside its top-25 concepts.
Why not just use whitening and assume the gap is handled? SCoCCA's 0.95 editing score suggests whitening already helps a great deal. But editing single concepts does not reveal whether the solver builds gap-direction pairs, and Mind the Gap's cone analysis says the mismatch between modalities extends beyond second-order statistics. Our gap-aligned-share measurement settles the question. If whitening drives that share to the level of random pairs, the artifact hypothesis is confirmed for mean-centering and dismissed for whitening.
Proposed Experiments
The decisive first check uses planted conjunctions. On MS COCO and Open Images V7 we define labels from the multi-label annotations as conjunctions, for example "person AND surfboard present," trained so that images with either concept alone count as negatives. We then train small nonlinear heads on frozen CLIP embeddings to predict these labels. Recovery rate of the planted pair among the top decoded interactions, compared with the linear baseline, explicit enumeration, and phrase-augmented SpLiCE, tells us whether the method works at all.
The second check measures unplanted structure on real models. For CLIP zero-shot classification on ImageNet-500 and CIFAR-100, and for the Husky-vs-Wolf diagnostic, we report held-out variance explained by linear, pairwise, and triple models. We also report the rate at which decoded pairs are confirmed by the interventional contrast $\Delta_{ij}$, and the correlation between $\hat B_{k,ij}$ and $\Delta_{ij}$. On Husky-vs-Wolf we specifically ask whether "snow" acts through a conjunction with canine concepts rather than additively.
The third check is the gap sweep. For each combination of alignment method and gap size (Mind the Gap shifts, and gap-closing training on COCO), we report the gap-aligned share of top pairs, the interventional confirmation rate, and zero-shot accuracy. The artifact hypothesis predicts a clear negative relation between gap-aligned share and confirmation rate, and a higher gap-aligned share under mean-centering than under whitening. If the gap-aligned share looks the same as for random pairs everywhere, the hypothesis is refuted, and the interaction findings stand on their own as explanations of model decisions.
We also report sketch dimension $m$ against decoding precision. We expect a plateau once $m$ exceeds a few times the number of true heavy interactions, the same kind of threshold behavior Yuan et al. found for sketched tensor-ring decompositions. Finally we report wall-clock time and memory against enumeration at second and third order.
References
- Interpreting CLIP with Sparse Linear Concept Embeddings (SpLiCE)
- SCoCCA: Multi-modal Sparse Concept Decomposition via Canonical Correlation Analysis
- Mind the Gap: Understanding the Modality Gap in Multi-modal Contrastive Representation Learning
- Closing the Modality Gap Aligns Group-Wise Semantics
- Kernel Pooling for Convolutional Neural Networks
- CRAFT: Concept Recursive Activation FacTorization for Explainability
- Practical Sketching Algorithms for Low-Rank Tucker Approximation of Large Tensors
- A Sampling-Based Method for Tensor Ring Decomposition
- Randomized Tensor Ring Decomposition and Its Application to Large-scale Data Reconstruction