Triangle-Consistent Dense Alignment for Vision-Language Models

Contrastive vision-language models such as CLIP learn to tell what is in an image, but they are poor at saying where it is. Their training only asks a whole image to match a whole caption, so nothing forces the scores between individual image patches and text labels to be coherent with each other. This proposal treats that incoherence as something measurable. Take three kinds of distances: between image regions, between text labels, and between regions and labels. If the model's local alignment were sound, these three would fit together as one geometry and obey the triangle inequality, the rule that a detour is never shorter than the direct path. We expect CLIP-derived dense score maps to break this rule often and in a specific way. A background patch that looks nothing like a car can still sit close to the word "car" while a nearby patch that clearly is a car sits farther away.

The proposal has two parts. First, we measure triangle-inequality violations in the joint region–label distance graph and test whether they predict segmentation errors. Second, we repair them at inference time with a cheap convex projection. The projection finds the nearest region–label distance matrix that, together with fixed region–region and label–label distances, forms a valid pseudometric, meaning a distance that obeys symmetry and the triangle inequality but may put distinct points at zero distance. The repair plugs into existing open-vocabulary segmenters without retraining the backbone. Its main effect is to suppress the "extraneous high-response" failure, where irrelevant background regions win a label. It does this through a geometric rule rather than a tuned threshold.

Core Claim

Let $P$ be the regions of an image (patches or mask proposals) and $T$ the candidate text labels. Let $d_P$ be a metric on regions, $d_T$ a metric on labels (for example, chordal distance between normalized text embeddings), and $D(p,t)$ the cross-modal distance produced by the segmenter. The union $P \cup T$ forms a pseudometric only if every mixed triangle holds. For any regions $p,q$ and label $t$, this means

$$|D(p,t) - D(q,t)| \;\le\; d_P(p,q) \;\le\; D(p,t) + D(q,t),$$

with the symmetric conditions holding for any labels $t,s$ and one region $p$ when $d_T$ is used. The left inequality says a label's score map must be 1-Lipschitz, that is, it cannot jump between two regions faster than those regions differ. This bounds noise without blurring across boundaries where $d_P$ is large. The right inequality is the one that matters for spurious matches. Two regions that are very different cannot both be close to the same label. So if one region is confidently a car, a background region that is far from it in $d_P$ is pushed away from "car".

Our claim is that violations of this inequality family are a concrete, per-image signature of the global–local gap. We also claim that projecting onto the feasible set improves open-vocabulary segmentation more than the obvious fixes: normalizing features, smoothing over an affinity graph, or slack-variable optimal transport. The gain should be largest on large, fine-grained vocabularies.

Relation to Prior Work

Three works motivate the problem. Recover and Match names the extraneous high-response failure in multi-label recognition. It handles the failure with Knowledge-Constrained Optimal Transport, a patch-to-label matching whose relaxed marginals let background mass go to a slack state. The capacity bounds are heuristic, the method has no metric guarantee, and it never produces masks. We target the same failure in dense segmentation, and the mechanism that suppresses background is the triangle inequality rather than a capacity budget. Side Adapter Network (SAN) closes much of the global–local gap by having a small side network propose masks and classifying those masks through a frozen CLIP. Classification still uses unconstrained inner products, and it reaches only 12.4 mIoU on the 847-class ADE20K split. SAN is our host model, not our competitor in kind. DenseCLIP computes dense pixel–text score maps from CLIP features with context-aware prompts. Its score maps are exactly the kind of unconstrained $D$ we propose to measure and repair.

Several works supply methods. An Inductive Bias for Distances builds networks, Deep Norms and Wide Norms, that satisfy the triangle inequality by construction. It reports that unconstrained networks fit dense training data slightly better but generalize worse when data is sparse. We reuse its Wide Norm construction to learn the region metric $d_P$, so the projection's guarantee rests on a true metric. Sinkhorn Distances and Convex Distance Operator Transport (CDOT) show that transport-based discrepancies can be made metric and convex. CDOT reports that its convexity costs it sharp assignments and that it scales as $O(n^3)$. Those two findings constrain our design: we do not transport mass between patches and labels at all. Instead we project a distance matrix, which keeps sharp decisions wherever $d_P$ separates regions and costs $O(n^2 |T|)$. PLOT matches multiple prompts to a patch grid with Sinkhorn transport for few-shot classification. It shows transport can live inside a CLIP adaptation loop, but it imposes no consistency between patches and outputs no masks. Sub-Embedding Robust Wasserstein aligns heterogeneous metric spaces with provable guarantees but only at the level of whole images and captions. Finally, LRP shows that average precision hides which kind of error a detector makes. We borrow its error decomposition, separating false-positive regions from missed regions and loose boundaries, to check that our gains come from where the mechanism predicts.

Research Program

The first component is the diagnostic. For a frozen model we compute $D$ from normalized region and label embeddings, compute $d_P$ and $d_T$, and record, per image, the total amount by which mixed triangles are violated. Within-modality cosine-based distances are already metric, so every violation comes from the cross-modal block. This is the precise sense in which the gap is "global–local". We then test whether per-image violation mass predicts per-image segmentation error and, more specifically, false-positive pixel area.

The second component is the repair. Holding $d_P$ and $d_T$ fixed, we solve

$$\hat D = \arg\min_{D'} \; \|D' - D\| \quad \text{subject to all mixed triangle inequalities for } P \cup T,$$

which is a convex problem because the constraints are linear in $D'$. Under the max-norm, the Lipschitz part separates per label. The classical McShane–Whitney upper and lower envelopes give a closed-form starting point. We then enforce the remaining constraints with a few rounds of cyclic projection, which parallelizes on a GPU. We also apply a scale $L$ to $d_P$, so that $L$ trades fidelity to the original scores against consistency, and we sweep it. We run the repair at two operating points. On SAN's roughly hundred mask proposals it is negligible in cost. On a training-free CLIP patch grid of about a thousand patches, we restrict it to each image's top-scoring labels to keep the $n^2$ term affordable.

The third component is the region metric, which carries the whole method. A metric on spatial position alone is wrong, because the right-hand inequality would then forbid two distant cars from sharing a label. We compare three choices. The first is distance between intermediate-layer CLIP features, which is training-free. The second is distance between mask-pooled side-network features. The third is a Wide Norm metric trained on COCO-Stuff to predict whether two regions share a ground-truth segment. This last choice is guaranteed to obey the triangle inequality and uses no ADE20K labels.

Baselines

The naive reference point is the host model as published. That is SAN classifying masks with its CLIP inner products, plus a training-free dense CLIP map in the style of DenseCLIP's pixel–text scores for the patch-level setting. The strongest existing number is SAN's 12.4 mIoU on ADE20K-847 reported in SAN. We re-run SAN from its released configuration on the same hardware, trained only on COCO-Stuff, and report our reproduced number next to the published one. Beating it means a gain over the reproduced SAN that holds across three seeds of the region-metric training and exceeds the seed spread. Every variant adds the same post-processing compute budget and none touches the backbone.

The strongest competitor in kind is slack-variable optimal transport in the spirit of Recover and Match. It re-assigns SAN's region–label scores with Sinkhorn matching that includes a dummy background column, and it gets the same validation tuning budget for its entropy and slack parameters as we give $L$. Recover and Match itself reports a 5.0% zero-shot mAP improvement on NUS-WIDE and an F1 gain of over 15% on PA100K. No reported result was found on Lacuna for any patch-level OT reassignment on ADE20K, so we build this baseline ourselves.

Two ablations isolate the key ingredient. The first replaces the projection with a random-walk diffusion of scores over the same $d_P$ graph, at matched iterations. This separates "consistency" from "using a good affinity". The second keeps only the Lipschitz half of the constraints or only the lower-bound half, to show which inequality suppresses false positives.

Why not just…?

Why not just L2-normalize the features and use cosine distance, which is already a metric? Normalization makes each within-modality block metric. It also tames the high-norm tokens that Recover and Match blames for spurious matches. But it says nothing about whether region–label distances agree with region–region distances, because the cross block of an image tower and a text tower is not jointly constrained. The diagnostic runs entirely on normalized features. If violation mass is near zero there, this proposal is wrong and we will say so. That is the first thing we measure.

Why not just smooth the score maps over a patch-affinity graph, like a conditional random field or affinity propagation? This is the real threat, because it uses the same ingredient, a good region similarity. Our argument is that diffusion averages scores across neighbors whether or not they were consistent. Diffusion therefore blurs boundaries and cannot push a lone background region away from a label that a dissimilar region owns. The projection changes only scores that violate an inequality. The matched-compute diffusion ablation settles this. If diffusion matches the projection on mIoU, false-positive area and boundary quality, the triangle framing adds nothing and we will report that.

Why not just train SAN longer or with a better mask head? More supervision on COCO-Stuff improves the proposals but not the classification geometry. The fine-grained 847-class failures are largely confusions on correctly shaped masks. The repair is orthogonal and costs no training of the host. We test this by applying it to SAN checkpoints of different strengths. A constant or growing gain argues for orthogonality, and a gain that vanishes on stronger hosts argues against.

Why not use metric transport such as CDOT directly between patches and labels? CDOT itself reports diffuse plans and cubic cost, both of which are bad for sharp pixel decisions at thousands of patches. We include it only at the mask-proposal scale, where $n$ is about a hundred, as a reference.

Proposed Experiments and Decisive Checks

The host models are trained on COCO-Stuff and evaluated zero-shot on ADE20K-847 and ADE20K-150, plus NUS-WIDE multi-label mAP to connect to Recover and Match. We report mIoU, a boundary F-score, and an LRP-style split of errors into false-positive area, missed area and boundary looseness. For context, DenseCLIP's 43.5% mIoU on ADE20K-150 is a closed-set supervised result and is not a comparable open-vocabulary baseline.

Three outcomes decide the proposal. First, per-image violation mass must correlate with per-image error and especially with false-positive area. Without this, the diagnostic claim fails. Second, the projection must beat both reproduced SAN and the slack-OT baseline on ADE20K-847, with the gain concentrated in false-positive area as the lower-bound inequality predicts, and the lower-bound-only ablation must recover most of it. Third, the projection must beat matched diffusion on boundary F-score while at least matching it on mIoU. A secondary check is the sweep over $L$ and the region-metric choice. The Wide Norm region metric should help more on rare ADE20K classes than an unconstrained learned affinity, which would echo the sparse-data advantage reported by Pitis et al..