The Limits of Binding in Dual Encoders

Kin Ian Lo

cs.LGAug 16, 2026

The Limits of Binding in Dual Encoders

Authors: Kin Ian Lo

Organizations: University College London

Abstract

Dual-encoder models such as CLIP score an image-caption pair by a single inner product of two independently computed unit vectors, and fail at binding, often scoring near chance when asked to distinguish "a red car and a blue dog" from "a blue car and a red dog". We give a mathematical account of when this failure is necessary and when it is contingent. Working within the ideal-encoder framework proposed by Kang et al., we first show the relevant axioms are satisfiable, so every impossibility must enter through an added, checkable hypothesis. We then prove three such obstructions. Depth: for recursive role-binding codes the swap margin obeys an exact law $m(D) = 2b^{-D}$ in the nesting depth D, with a finite-dimension version holding up to one explicitly flagged concentration estimate; the resolvable depth grows only logarithmically in the dimension and is single-digit at CLIP scale, the nesting depth of ordinary language. Objective: architecture-free throttle theorems showing that the contrastive objective's entire reward for binding is bounded by the rate at which training contrasts a caption against its own swap, a rate that vanishes at web scale, and that exactly reversed binding costs only that rate times the mean binding margin; both are verified in simulation. Geometry: a tight smoothness-binding frontier: the closer the two swap-related captions must embed to a shared paraphrase anchor, the smaller the binding margin can be, with an exact constant. Measuring its text-only diagnostic across 18 deployed text encoders, every model sits at roughly 25-35% of its ceiling, and the induced per-item ceiling tracks SugarCrepe's subset difficulty at r = 0.99. Binding failure in deployed dual encoders is thus not a dimension or smoothness limit today, but an incentive and code-structure limit, with a proved depth ceiling that remains once those are fixed.

Figures & tables

Panel of Figure 1 — Figure 1: Recursive role-binding (Definition L.1 ) and the depth law. A deep edit (orange) changes one summand among $b$ at its parent; each further level of normalized pooling multiplies its share of the root code by $1/b$ , so the discriminative margin decays geometrically with nesting depth — the recursive continuation of the $\Theta(1/k)$ single-level margin bound of Theorem E.7 .

Panel of Figure 2 — Figure 2: The depth ceiling, measured. (a) Swap margins sit on $2\cdot b^{-D}$ across three orders of magnitude (log scale; $N=65{,}536$ shown, where the products $m\cdot b^{D}$ are within $0.014$ of $2$ ; at smaller $N$ the deviations grow as the finite- $N$ term of Theorem 3.3 allows — Appendix L.4 ). (b) Resolvable depth (largest $D$ with margin above the $10/\sqrt{N}$ floor) follows $\lfloor\log_{b}(\sqrt{N}/5)\rfloor$ exactly, including the integer staircase — the $D^{*}=\Theta(\log N/\log b)$ ceiling of Corollary 3.4 .

Panel of Figure 3 — Figure 3: The model zoo against the frontier (the data of Table 1 ; axes to equal scale). Every deployed model sits in the narrow wedge between usage $\approx 0.25$ and $0.35$ , far below the $d=\mathrm{cap}$ line: no model is smoothness-limited. Scale, data, and objective move points along the wedge; only NegCLIP (star) climbs across it, by raising $d$ at roughly constant cap.

Appendix figures & tables13 assets

Supplementary material from the paper’s appendix.

Appendix

Panel of Figure 4 — Figure 4: The dual-encoder binding problem (Definitions B.1 – B.9 ). One image of the scene $s$ ; two captions with the identical word multiset , differing only in which attribute is bound to which object. Both towers embed into the unit sphere, and the deployed score is a single inner product. Every theorem in this paper is a statement about the margin $M(s)$ .

Panel of Figure 5 — Figure 5: Same vocabulary, two parses (Remark B.6 ). An order variant of $c(s)$ and the swap $c(\sigma s)$ share the identical word multiset; they differ only in the binding (which colour attaches to which object). The invariance similarity requires —merge the order variants of $\mathcal{C}(s)$ (left)—and the invariance binding forbids —separate the swap class $\mathcal{C}(\sigma s)$ (right)—are indistinguishable at the vocabulary level. A bag-of-words map performs both at once (Theorem D.2 ); separating swaps requires reading the parse.

Panel of Figure 6 — Figure 6: What $(K_{k})$ demands, for one scene (the reduction opening this subsection). The single-object embeddings $\{\mathbf{t}(x)\}$ lie on the sphere; the scene’s image vector $\mathbf{i}(I_{s})$ acts as the linear functional $y\mapsto\langle\mathbf{i}(I_{s}),\,y\rangle$ —“height along the arrow.” Condition $(K_{k})$ requires this functional to rank every present object $x\in V(s)$ above every absent one, i.e. the dashed hyperplane $\langle\mathbf{i}(I_{s}),\,\cdot\rangle=\theta$ strictly separates $\{\mathbf{t}(x):x\in V(s)\}$ (teal, in the shaded accept-region) from its complement (grey). So “ $(K_{j})$ for all $j$ -scenes” is exactly “every $j$ -subset of the $M$ points is linearly separable”—a demand Radon’s theorem forbids once $j>\lfloor N/2\rfloor$ (Figure 7 is the same picture when separation fails ).

Panel of Figure 7 — Figure 7: The Radon impossibility (Proposition C.3 (i)) in its smallest instance: $N=2$ , $M=4=N+2$ object embeddings on the circle $\mathbb{S}^{1}$ . Radon’s theorem partitions them into $A$ and $B$ whose hulls (the two chords) intersect; no linear functional is therefore constant-sign on $\{\mathbf{t}(x_{1}),\mathbf{t}(x_{3})\}$ and opposite on the rest, so no image vector can rank the $2$ -scene $\{x_{1},x_{3}\}$ above its complement: $(K_{2})$ fails. In general the smaller Radon side has at most $\lfloor N/2\rfloor+1$ points, giving the threshold $k\leq\lfloor N/2\rfloor$ .

Panel of Figure 8 — Figure 8: Theorem D.2 (bag-of-words collapse). A pairing-blind text map sends both pairings to the same point—they share a word multiset—so the binding margin is exactly zero for every image encoder, dimension, and training. Contrast Figure 4 , where the two captions are distinct points; the whole “CLIP cannot bind” phenomenon is this one observation that a multiset function cannot distinguish rearrangements.

Panel of Figure 9 — Figure 9: Pooled factored codes and leakage (Section E ). (a) Each atom $(o_{j},a_{j})$ is bound by a Hadamard product $u(o_{j})\odot v(a_{j})$ ; the bound codes are summed and normalized to the caption embedding $\mathbf{t}(c)$ . (b) The code’s quality is set by leakage $\ell$ — the inner product a partial match (right object, wrong attribute) receives — against the exact-match gain $g$ . Random tied factored codes achieve $g=1$ , $\ell\approx 0$ ; additive (bag-of-words) codes sit at $\ell=\Theta(g)$ and cannot bind.

Panel of Figure 10 — Figure 10: The margin ceiling is $\Theta(1/k)$ (Theorem E.7 ). Marks: measured normalized margins of the tied factored sign code ( $N=4096$ , $M=K=40$ , 300 scenes per size) against swap, replace, and add negatives. Lines: the theoretical $2/k$ , $1/k$ , and $1-\sqrt{k/(k+1)}$ . Measured values sit on the predictions to plotting accuracy—in particular the exact add-margin form $1-\sqrt{k/(k+1)}$ , not the loose $1/(2(k+1))$ .

Panel of Figure 11 — Figure 11: The smoothness–binding frontier. (a) Proof geometry of Theorem G.3 (i) (drawn as a great-circle section): both caption classes lie in the spherical cap of cosine-radius $1-\delta$ about the pairing-neutral anchor $\bar{t}_{s}$ ; any two points of the cap are at distance $\leq 2\sqrt{2\delta}$ , and by Cauchy–Schwarz no unit image vector can extract a larger margin from them (Corollary G.5 is exactly this picture). (b) The induced Pareto region: pairs $(\delta,M)$ below the curve are achievable (Theorem G.3 (ii) saturates it), pairs above are impossible for any encoder, dimension, or training. Kang et al.’s exact collapse is the $\delta=0$ endpoint. The measured CLIP B/32 point sits at $25\%$ of its cap—far inside; the dashed segment is the unused smoothness budget (§ H ). The open circle sits on the curve at $2\sqrt{2\cdot 0.112}=0.947$ ; the table of § H reports the mean of per-quartet caps, $0.936$ —a Jensen gap.

Panel of Figure 12 — Figure 12: The per-item ceiling (Corollary G.4 ) on SugarCrepe, $14$ models, $66{,}598$ decisions. (a) Accuracy by within-model $d$ -decile, pooled: monotone from near-chance to $0.93$ ; $73\%$ of all errors lie below the median $d$ . The low end is the theorem (small $d\Rightarrow$ margin within noise); the high end is permitted-and-observed, not implied. (b) Pooled subset accuracy against subset mean $d$ : the benchmark’s canonical difficulty ordering—swaps hardest—is the statement that same-vocabulary negatives have small ceilings.

Panel of Figure 13 — Figure 13: The three-obstruction map (Section 10). Binding faces four obstructions. Three are contingent and can be engineered away—enlarge $N$ past $2k$ (geometry, Prop. C.3 ), choose a low-leakage factored code (structure, § E ), and supply swap negatives with pair coverage (data, § F ). The fourth, the smoothness frontier $M(s)\leq 2\sqrt{2\delta}$ (Thm G.3 ), binds every encoder, dimension, and training: it is terminal. The measurements (§ H ) place today’s models far short of it, which is why the contingent obstructions govern the near term and the frontier is the limit that remains.

Panel of Figure 14 — Figure 14: The throttle, schematically. With universal capacity the optimum $S^{*}$ binds — but its pairing-blind average and even its exact binding reversal sit within a loss sliver whose width is set by the swap-contrast rate $(\pi+\pi_{\mathrm{impl}})$ . Training pressures larger than the sliver, not the objective, decide the binding behaviour of the selected solution.

Panel of Figure 15 — Figure 15: Verification of Theorems K.1 – K.4 (noise $0.6$ ). Both gaps are exactly linear in $\pi$ . The toy sits in a low-separation regime, so unmatched contrasts contribute the $\pi$ -independent offsets $c_{1},c_{0}$ ; the decomposition $\mathrm{gap}(\pi)=c+\pi(\text{matched difference}-c)$ recovers the theorems’ matched constants precisely: $0.290+c_{1}=0.476$ vs. predicted $\log 2-\mathbb{E}[\ell(M^{*})]=0.477$ , and $1.261+c_{0}=1.943$ vs. predicted $\mathbb{E}[M^{*}]=1.949$ (Monte-Carlo error $\approx 0.005$ ). At noise $0.25$ : $0.5445$ vs $0.5460$ and $1.9455$ vs $1.9511$ .

Panel of Figure 16 — Figure 16: The refuted conjecture. Across disconnected exposure components the factored code of an unseen pair is identified only up to sign — but the swap decision compares templates with different supports , and a sign-agnostic matcher decides it without ever resolving the gauge. Coverage (both atoms seen), not connectivity, is the true information threshold.

Compositional Reasoning in VLMs

See all 22 papers

Sep 20, 2026

BindCLIP: One Balanced Coupling For Compositional Vision Language Scoring

Global vision--language similarities compress an image and a caption into one vector, preserving semantics but not which word corresponds to which region or how those regions are arranged; a model can recognize every word and object yet prefer a compositionally incorrect caption. We argue that a frozen encoder retains this association structure, so the problem is to read it rather than to rebuild it beside the pretrained similarity. We introduce BindCLIP, a pairwise scorer built on one latent object: a balanced token--patch--depth optimal-transport coupling that places both candidate captions and several visual depths in a single plan. Semantic, entity, order, and spatial evidence are read as energies of this state, and exchanging the candidates permutes the plan, making the score exactly antisymmetric. A geometric refinement inside the coupling contracts moves that the candidates and the visual depths do not support. No task label, parser, relation inventory, or detector is used. One checkpoint and one inference path improve the official What'sUp, ARO, and SugarCrepe benchmarks over frozen global CLIP, with the strongest transfer on the relation splits. Controls rule out patch access and caption-length shortcuts, and an inference-time lesion localizes spatial arrangement to the coupling.

Liuyang Song, Yi Zhang, Zhongyi Deng +2

Peking University · Dongguan University of Technology · Sichuan Agricultural University

Vision-Language Models Vision-Language Grounding Vision-Language Alignment Compositional Representation Learning

Ask PDF

May 29, 2026

How can embedding models bind concepts?

Humans easily determine which color belongs to which shape in multi-object scenes, an ability known as concept binding. Vision-language embedding models such as CLIP struggle with binding: they recognize individual concepts but fail to represent which concepts form which objects. Although CLIP behaves like a bag-of-concepts model in cross-modal retrieval, object information is recoverable from its image and text embeddings separately. We study this tension through the binding function, which maps concepts to scene embeddings. We find that scene embeddings decompose additively into object representations, explaining why uni-modal probes can recover object information. However, CLIP's binding function is high-complexity, which likely prevents the image and text encoders from learning a shared binding mechanism that generalizes to unseen concept combinations. We then ask whether this limitation is fundamental. We show that it is not. In controlled transformer models trained from scratch, binding generalization emerges with sufficient data coverage. These models learn low-complexity binding functions characterized by multiplicative interactions between concepts, enabling systematic generalization. Code is publicly available at https://github.com/oshapio/binding-concepts-complexity.

Arnas Uselis, Darina Koishigarina, Seong Joon Oh

University of Tübingen, Tübingen · 2KAIST AI

Multimodal Embedding Vision-Language Alignment Compositional Generalization

Ask PDF

Jul 25, 2026

Similarity Is Not Logic: Factored Inference for Dual-Encoder Vision-Language Models

Dual-encoder vision-language models (VLMs) expose a similarity interface that enables zero-shot retrieval but fails compositional constraints: queries like "umbrella and no person" retrieve images containing both, even when concept detection is reliable. We trace this to an interface-level Bag-of-Concepts effect, where similarity scores approximate mean pooling of concept evidence regardless of operators. Although operator-dependent signals exist in text embeddings, they are too weak or misaligned to affect rankings. Fine-tuning does not reliably resolve this failure because the dominant bottleneck is how similarity aggregates evidence rather than what encoders represent. We propose factored inference, which separates evidence extraction from constraint execution, and introduce LCSE (Logic-Constrained Score Editing), a training-free method that executes constraints externally using concept scores from frozen encoders. We also introduce FACTOR-Bench, where LCSE achieves 85.5% accuracy versus 73.2% for the best fine-tuned baseline, 90.7% when applied to SigLIP 2, and improves NegBench COCO MCQ accuracy from 27.2% to 65.2% while preserving retrieval performance.

Sultan Alshehri, Zhantao Yang, Han Zhang +1

Carnegie Mellon University, Pittsburgh, PA, USA.

Vision-Language Models VLM Reasoning Vision-Language Retrieval VLM Inference Compositional Reasoning in VLMs

Ask PDF

Abstract

Compositional Reasoning in VLMs

Explore similar work

BindCLIP: One Balanced Coupling For Compositional Vision Language Scoring

How can embedding models bind concepts?

Similarity Is Not Logic: Factored Inference for Dual-Encoder Vision-Language Models