Paper deep dive
CertBind from Multimodal Connectivity to Certifiable Retrieval Decisions
Shuheng Cao, Zhenhao Zhang, Ruiqi Chen, Renjie Cao, Weijia Zhang, Siyu Zhang, Jiaxin Liu, Xiangyu Zeng, Haotian Geng, Fan Gu
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 92%
Last extracted: 8/10/2026, 2:31:19 AM
Summary
The paper introduces CertBind, a multiscale theory for certifiable composition of frozen multimodal connector graphs. It addresses the challenge of maintaining retrieval performance when lightweight connectors expand cross-modal reach. CertBind operates at four scales: node (task identification via native anchors), edge (screening via contract-aware conformal ranks and Holm control), path (recovery via overlap-aware budgets and clean calibration), and query (retrieval certification via covered top-k candidate sets). The system classifies routes as Direct, Certified, or Abstain, demonstrating high recovery rates and no-harm values in evaluations.
Entities (9)
Relation Signals (10)
CertBind → classifies → Abstain
confidence 95% · returns Abstain for unresolved queries
CertBind → classifies → Direct
confidence 95% · CertBind therefore retains supported routes as Direct
CertBind → classifies → Certified
confidence 95% · returns Certified for decisive recovery
CertBind → uses → Holm's procedure
confidence 92% · Holm’s procedure at level δs controls the probability of at least one clean-edge false flag
CertBind → operatesatscale → Query Scale
confidence 90% · At the query scale, this radius yields a covered top-k candidate set
CertBind → operatesatscale → Edge Scale
confidence 90% · At the edge scale, contract-aware conformal ranks provide graph-wide family-wise error control.
CertBind → operatesatscale → Path Scale
confidence 90% · At the path scale, an overlap-aware budget and clean calibration yield a finite-sample recovery radius
CertBind → operatesatscale → Node Scale
confidence 90% · At the node scale, native anchors establish the exact task identification boundary
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Lightweight connectors make frozen multimodal encoders composable at the representation level. Deployment exposes a second problem at the level of task decisions. A connected route can expand cross-modal reach while changing an established native retrieval capability. We introduce CertBind, a multiscale theory of certifiable composition for frozen multimodal connector graphs. At the node scale, native anchors establish the exact task identification boundary under the stated chart model. At the edge scale, contract-aware conformal ranks provide graph-wide family-wise error control. At the path scale, an overlap-aware budget and clean calibration yield a finite-sample recovery radius under declared conditions. At the query scale, this radius yields a covered top-k candidate set that becomes a point certificate when its size equals k. CertBind therefore retains supported routes as Direct, sends only flagged routes to recovery, returns Certified for decisive recovery, and returns Abstain for unresolved queries. The evaluated C-MCR shared route reduced native CLIP R@1 from 0.524 to 0.290. The production fallback recovered 0.963 +- 0.002 of clean retrieval, while the passing branch recorded a no-harm value of 1.000. CertBind extends multimodal composability from connected representations to certifiable task decisions.
Tags
Links
- Source: https://arxiv.org/abs/2608.06516v1
- Canonical: https://arxiv.org/abs/2608.06516v1
Trouble viewing inline? Open PDF directly →
Full Text
41,817 characters extracted from source content.
Expand or collapse full text
CertBind from Multimodal Connectivity to Certifiable Retrieval Decisions Shuheng Cao1,∗, Zhenhao Zhang5,7,∗, Ruiqi Chen2,∗, Renjie Cao3,†, Weijia Zhang4,†, Siyu Zhang1,†, Jiaxin Liu5,†, Xiangyu Zeng6,†, Haotian Geng7,†, Fan Gu8,‡ Abstract Lightweight connectors make frozen multimodal encoders composable at the representation level. Deployment exposes a second problem at the level of task decisions. A connected route can expand cross-modal reach while changing an established native retrieval capability. We introduce CertBind, a multiscale theory of certifiable composition for frozen multimodal connector graphs. At the node scale, native anchors establish the exact task identification boundary under the stated chart model. At the edge scale, contract-aware conformal ranks provide graph-wide family-wise error control. At the path scale, an overlap-aware budget and clean calibration yield a finite-sample recovery radius under declared conditions. At the query scale, this radius yields a covered top-k candidate set that becomes a point certificate when its size equals k. CertBind therefore retains supported routes as Direct, sends only flagged routes to recovery, returns Certified for decisive recovery, and returns Abstain for unresolved queries. The evaluated C-MCR shared route reduced native CLIP R@1 from 0.5240.524 to 0.2900.290. The production fallback recovered 0.963±0.0020.963± 0.002 of clean retrieval, while the passing branch recorded a no-harm value of 1.0001.000. CertBind extends multimodal composability from connected representations to certifiable task decisions. Introduction Frozen multimodal encoders provide strong but fragmented representations across image, text, audio, and video. Lightweight connector maps make these encoders composable without rebuilding a universal model. Existing systems either synthesize a common space or attach new modalities to a preserved base space (Wang et al. 2023; Zhang et al. 2024; Wang et al. 2024, 2025). This progress establishes representation-level composability across frozen spaces and creates multiple routes to downstream tasks. More broadly, multimodal models are increasingly evaluated by decision-level capabilities such as explicit affordance reasoning and action-region grounding (Wang et al. 2026). A released connector checkpoint makes the decision-level deployment problem visible. On the same native CLIP image-to-text workload, the evaluated C-MCR shared route reduced R@1 from 0.5240.524 to 0.2900.290. A route can expand multimodal reach without becoming the right replacement for an established native route. Connector composition must therefore support expansion and preservation as distinct deployment decisions. Decision-level certifiability is multiscale because a retrieval output inherits ambiguity from the graph that produced it. At the node scale, graph consistency leaves a residual target gauge relative to a fixed native gallery. At the edge scale, heterogeneous connector contracts require graph-wide calibration. At the path scale, shared failure incidence determines the value of overlapping routes. At the query scale, the observed boundary margin determines whether recovered scores support a point top-k output. Each scale resolves a different ambiguity and supplies the evidence required by the next. CertBind develops a multiscale theory of certifiable composition from graph structure to retrieval decisions. At the node scale, native anchors identify task-relevant target coordinates. Contract-aware screening determines whether the registered direct edge remains supported. A majority path-transversal budget and clean calibration recover flagged queries through failure-diverse paths. A covered top-k candidate set then certifies decisive outputs and retains set-valued uncertainty otherwise. The resulting preservation-first policy maps the reached certificate level to one deployment action. Supported routes return Direct, flagged routes enter recovery, decisive recovery returns Certified, and unresolved queries return Abstain. Figure 1 follows this progression from graph structure to the final retrieval decision. This work makes three contributions to certifiable multimodal composition over frozen connector graphs. 1. Certifiable composition from graph consistency to native task scores. We separate representation connectivity from native task identification by exposing the residual target gauge. We characterize task-score identification, establish the exact universal anchor rank, and bound registration error under noisy anchors. 2. A multiscale certificate chain from edges to queries. Contract-stratified conformal ranks and Holm control graph-wide clean-edge false flags. A majority path-transversal budget quantifies robustness under shared failures across overlapping routes. Together, these results yield a covered top-k candidate set and an end-to-end error decomposition. 3. Preservation-first action and graph design. A three-state rule maps supported routes, decisive recovery, and unresolved queries to Direct, Certified, and Abstain. The exact path budget is a quota-cover integer program, while edge-disjoint paths yield a polynomial Menger certificate. Released-system cases quantify the operational stakes of preservation, expansion, and recovery. Full proofs, computational details, and additional deployment records appear in the supplement. Figure 1: CertBind certifies multimodal composition across node, edge, path, and query scales. (A) At the node scale, native anchors fix the target gauge when they span the declared task subspace. (B) At the edge scale, conformal ranks calibrate contract-aware evidence, Holm controls graph-wide decisions, and supported edges retain the registered direct route as Direct. (C) At the path and query scales, flagged edges enter overlap-aware recovery. CertBind returns Certified when the covered top-k candidate set contains k items and Abstain otherwise. Related Work Unified spaces and connector graphs. ImageBind, LanguageBind, and UniBind construct broad shared representations (Girdhar et al. 2023; Zhu et al. 2024; Lyu et al. 2024). C-MCR and Ex-MCR connect frozen contrastive spaces, while FreeBind and OmniBind fuse or route among multiple spaces (Wang et al. 2023; Zhang et al. 2024; Wang et al. 2024, 2025). Multi-Way Alignment constructs a jointly consistent universe from matched samples (Achara et al. 2026). These systems establish representation-level composability and support broad downstream utility. CertBind starts from the resulting frozen graph and studies the task decisions supported after deployment. Representation identifiability and stitching. Linear identifiability, CKA, model stitching, relative representations, and modality-gap analyses study when learned spaces share geometry or communicate (Roeder et al. 2021; Kornblith et al. 2019; Bansal et al. 2021; Moschella et al. 2023; Liang et al. 2022; Huh et al. 2024). Together, these analyses establish geometric comparability between learned representation spaces. CertBind specializes the remaining chart ambiguity to native-gallery retrieval, where native anchors determine whether the declared task scores are identified. Robust recovery and conformal inference. Cycle-edge message passing recovers corrupted group-valued relative measurements (Lerman and Shi 2022). Noisy-correspondence methods repair sample pairs during training (Huang et al. 2021). Coordinate medians provide classical clean-majority robustness (Huber and Ronchetti 2009). Conformal ranks provide finite-sample calibration (Vovk et al. 2005). Holm’s step-down procedure controls family-wise error under arbitrary dependence among valid marginal tests (Holm 1979). CertBind carries robust recovery and calibrated uncertainty through shared path failures and observed task margins to a retrieval decision. Prior work has established multimodal connectivity, representation comparison, robust recovery, and calibrated inference. CertBind develops this decision layer as a multiscale theory linking native task identification, graph-wide screening, overlap-aware recovery, and query-level retrieval certification. Setting, Threat Model, and Certificate Semantics CertBind associates node, edge, path, and query scales with distinct observables, assumptions, and certificates. Routes and calibration roles are fixed before any candidate outcomes are observed. Let G=(V,E)G=(V,E) be a directed connector graph. Node v contains a frozen encoder with space v⊆ℝdvX_v ^d_v. Edge e=(u,v)e=(u,v) is a deployed map Te:u→vT_e:X_u _v. The formulation admits nonlinear and noninvertible maps. A declared path family uvP_uv provides via outputs yp(q)=Tp(q)y_p(q)=T_p(q) for query q. The direct output is y0(q)=Tuv(q)y_0(q)=T_uv(q). Before screening, a predeclared anchor operator vA_v constructs the graph-side matrix B=v(A)B=A_v(A) from fixed routes and aggregation rules. The operator and the native anchor matrix A are frozen before candidate outcomes. The identification analysis writes B=R∗A+EB=R_*A+E. Thus E contains the total graph-side anchor discrepancy. The fitted target registration is also frozen before screening. Henceforth yp(q)y_p(q) denotes the registered output of route p. An edge that passes screening returns its registered direct output without routing-layer modification. A flagged edge is replaced only at the routing layer. CertBind uses the standard coordinate median and averages the two central order statistics for even sample sizes in each coordinate. The via fallback is y^(q)=cmedyp(q):p∈uv. y(q)=cmed\y_p(q):p _uv\. (1) Each edge receives a predeclared audit contract ξe=(fu,fv,du,dv,e,e,R~v,e,De,ne,νe). _e=(f_u,f_v,d_u,d_v, map_e, norm_e, R_v,P_e,D_e,n_e, _e). (2) Its fields specify the encoder families, dimensions, connector class, normalization, frozen registration, route family, score functional, owner count, and owner law. A bounded owner-level score aggregates direct–via disagreement De(Oi,ξe)∈[0,B],Ae=1ne∑i=1neDe(Oi,ξe),D_e(O_i, _e)∈[0,B], A_e= 1n_e _i=1^n_eD_e(O_i, _e), (3) where OiO_i is the statistical owner cluster. Cycle residual and ranking agreement are optional diagnostics. Four certificate scales. A structural observation is invariant along a gauge orbit of graph parameterizations. Node-scale task identification asks when every orbit member induces the same native-gallery scores. Edge-scale screening controls false connector flags under a calibration law. Path-scale recovery combines path incidence and clean-path calibration to bound the recovered target. Query-scale retrieval certification guarantees a task decision for a particular recovered query. Split discipline. Anchor owners, screening-control owners, path-calibration owners, and each future query owner occupy separate roles. Conditional on the frozen registered design, screening controls and candidate audit owners are independent of the path-calibration sample and future query owner. Path-calibration owners and the future owner follow the exchangeable deployment law. Strata, routes, and thresholds are fixed independently of candidate outcomes. Let Q and GvG_v denote the spans of possible target-space queries and native gallery vectors, and let W=Q+GvW=Q+G_v. For an unknown target gauge R, exact task-score identification requires ProjGv(R−I)ProjQ=0.Proj_G_v(R-I)Proj_Q=0. (4) The universal result below specializes to the common conservative choice Q=Gv=WQ=G_v=W. All top-k operators use one fixed deterministic rule for score ties. Scale Observable input Required assumption Output Node identification native anchor pairs orthogonal chart model on declared W with anchor rank and conditioning fixed gauge or impossibility witness Edge screening owner-level audit scores from clean contract strata within-stratum exchangeability and optional bad-edge separation graph-wide false-flag control and miss bound Path recovery flagged edge and declared path incidence fewer bad edges than κ1/2 _1/2 with calibrated clean-path residuals radius around the clean target Query certificate recovered output and native gallery bounded gallery norms with the calibrated radius event covered kC_k and Certified when |k|=k|C_k|=k Table 1: Each graph scale resolves an ambiguity left by the preceding scale and produces the evidence required for the next deployment decision. The threat model separates three adversarial surfaces across the certificate chain. Gauge ambiguity changes target coordinates while preserving the graph’s structural observations. Edge corruption can make every route touching a bad edge arbitrary. Ordinary approximation error remains on routes containing no corrupted edge. Under the stated rank conditions, native anchors resolve gauge ambiguity before redundancy is evaluated. Screening power requires failure separation, and graph redundancy operates only after native anchors establish task semantics. Node-Scale Task Identification from Native Anchors At the node scale, certifiable composition requires a target chart that preserves native task scores. A graph may remain internally consistent while the chart rotates relative to a fixed native gallery. Native anchors determine when this residual gauge becomes irrelevant to the declared task. Although CertBind accepts arbitrary maps, the impossibility result already arises within a restricted submodel. Assume a perfectly consistent target node admits an orthogonal chart and structural observations determine its output only up to R∈(W)R∈ O(W) on an r-dimensional task subspace W. Let native anchors be columns of A=[a1,…,am]A=[a_1,…,a_m] and define Stab(A)=R∈(W)∣Rai=ai∀i.Stab(A)=\R∈ O(W) Ra_i=a_i\ ∀ i\. (5) Theorem 1 (Task identification and anchor complexity). Let S=span(A)S=span(A) and U=S⟂∩WU=S ∩ W. Under the chart model 1. native scores for query span Q and gallery span GvG_v are identifiable if and only if Eq. (4) holds for every R∈Stab(A)R (A). 2. Stab(A)=IS⊕(U)Stab(A)=I_S O(U). Consequently, task scores are identifiable if and only if Q⊆SQ S or Gv⊆SG_v S. 3. in the universal case Q=Gv=WQ=G_v=W, identifiability holds if and only if rank(A)=rrank(A)=r. When rank(A)<rrank(A)<r, a residual reflection preserves every structural observation and anchor but reverses a valid two-item native ranking. 4. suppose m≥rm≥ r, rank(A)=rrank(A)=r, and ‖E‖op≤ηA\|E\|_op≤ _A. For R~=BA† R=BA ∥R~−R∗∥op,W≤ηAσr(A)=:δA.\| R-R_*\|_op,W≤ _A _r(A)=: _A. (6) For a unit query observed as R∗qR_*q, the fixed registration R~⊤R∗q R R_*q is within δA _A of q. Proof idea. Score invariance is equivalent to ⟨(R−I)q,g⟩=0for all q∈Q,g∈Gv. (R-I)q,g =0 all q∈ Q,\ g∈ G_v. (7) This is Eq. (4). Every R∈Stab(A)R (A) fixes S pointwise. Orthogonality preserves U, and every element of (U) O(U) extends to a residual gauge. If either task span lies in S, the score change vanishes. Conversely, suppose both spans have nonzero projections onto U. Choose q∈Qq∈ Q and g∈Gvg∈ G_v with nonzero residual components. An orthogonal action on U can change their inner product. Its identity extension on S changes the task score while fixing every anchor. This proves the finite task-specific criterion. The universal condition follows by taking Q=Gv=WQ=G_v=W. For noisy anchors, full row rank gives AA†=IWAA =I_W. Therefore R~−R∗=(R∗A+E)A†−R∗=EA†. R-R_*=(R_*A+E)A -R_*=EA . (8) Submultiplicativity and ‖A†‖op=1/σr(A)\|A \|_op=1/ _r(A) prove Eq. (6). Multiplication by the unit vector R∗qR_*q gives the registered-query bound. The supplement gives the reflection construction and complete proofs. Design consequence. The theorem gives the exact identification boundary. Task identification depends on anchor coverage of the query or gallery span. Universal identification requires full rank on W, while noisy stability depends on anchor conditioning rather than anchor count alone. Under rank deficiency, σr(A)=0 _r(A)=0 and the universal finite bound is unavailable. At full rank, the stability radius scales as 1/σr(A)1/ _r(A). A redundant anchor cluster can therefore be less stable than a smaller, well-conditioned spanning set. An offline selector should maximize the smallest singular value on the declared task subspace subject to acquisition cost. If task queries and galleries occupy smaller spans, Eq. (4) can certify them without fixing irrelevant target directions. Proposition 1 (Optimal bounded-norm anchor geometry). Suppose m≥rm≥ r and ‖ai‖2≤1\|a_i\|_2≤ 1. Then σr(A)2≤m/r _r(A)^2≤ m/r. Equality holds exactly when AA⊤=(m/r)IWAA =(m/r)I_W and every anchor has unit norm. For a fixed operator-norm discrepancy budget ηA _A, a unit-norm tight frame minimizes the bound in Eq. (6). Edge-Scale Contract-Aware Graph-Wide Screening With node-scale task identification fixed, edge-scale screening asks which registered direct connectors remain supported under their audit contracts. Contract strata define the calibration populations, while graph-wide multiplicity control protects clean registered routes. Connector edges are rarely exchangeable across all architectures. The audit stratum s(e)s(e) is the predeclared equivalence class of the complete contract ξe _e. Edges share controls only when every contract field matches. Each control Aj(s)A_j^(s) is a complete owner-aggregated score generated under that contract. Write s=(A1(s),…,AMs(s))D_s=(A_1^(s),…,A_M_s^(s)). Define ps(a)=1+∑j=1MsAj(s)≥aMs+1,pe=ps(Ae),p_s(a)= 1+ _j=1^M_s1\A_j^(s)≥ a\M_s+1, p_e=p_s(A_e), (9) and, for a frozen batch of L edges, τs=supa∈[0,B]∣ps(a)>δs/L. _s= \a∈[0,B] p_s(a)> _s/L\. (10) An under-populated stratum returns Abstain. Theorem 2 (Stratified conformal screening and graph-wide control). Suppose a clean candidate score and the clean controls are exchangeable conditional on its predeclared stratum. 1. pep_e is conditionally super-uniform with ℙ(pe≤α∣s(e))≤αP(p_e≤α s(e))≤α. 2. Holm’s procedure at level δs _s controls the probability of at least one clean-edge false flag by δs _s. Candidate-edge dependence is unrestricted. 3. The smallest attainable p-value is 1/(Ms+1)1/(M_s+1). Rejection at level α requires Ms≥⌈1/α⌉−1M_s≥ 1/α -1. 4. every edge that passes Holm satisfies pe>δs/Lp_e> _s/L and therefore Ae≤τsA_e≤ _s. 5. conditional on the clean controls, suppose the nen_e bad-edge owner scores are independent in [0,B][0,B] and satisfy 1ne∑i=1nebad[De(Oi,ξe)∣s]≥τs+Δ. 1n_e _i=1^n_eE_ bad[D_e(O_i, _e) _s]≥ _s+ . (11) Then ℙbad(pass∣s)≤exp(−2neΔ2/B2).P_ bad(pass _s)≤ (-2n_e ^2/B^2). (12) The first three claims follow from the candidate rank among Ms+1M_s+1 exchangeable scores and the standard Holm step-down argument. For the fourth claim, every unrejected ordered p-value exceeds the threshold at the first failed Holm step. That threshold is at least δs/L _s/L. Hence a pass implies pe>δs/Lp_e> _s/L, which gives Ae≤τsA_e≤ _s by Eq. (10). Conditional on sD_s, define μe,s:=1ne∑i=1ne[De(Oi,ξe)∣s]. _e,s:= 1n_e _i=1^n_eE[D_e(O_i, _e) _s]. Since pass⊆Ae≤τs\pass\ \A_e≤ _s\, the mean-separation assumption and Hoeffding’s inequality give ℙbad(pass∣s) _ bad(pass _s) ≤ℙbad(Ae−μe,s≤−Δ∣s) _ bad (A_e- _e,s≤- _s ) (13) ≤exp(−2neΔ2B2). ≤ \! (- 2n_e ^2B^2 ). Thus the screening power statement uses the same pass event as the deployed Holm procedure. The screening theorem supplies the edge-scale evidence required by preservation-first routing. Under within-contract exchangeability, it controls graph-wide clean-edge false flags for the frozen batch. Detecting a bad edge additionally requires the stated conditional mean separation. Equation (10) connects that separation directly to the implemented Holm decision. At marginal level 0.050.05, rejection requires at least 1919 clean controls. The first Holm threshold for L edges can require substantially more. Multiple captions, frames, or segments from one item are aggregated before the concentration claim. Holm permits dependence across candidate edges because it needs only marginal super-uniformity. The family-wise guarantee applies to one frozen deployment batch of L hypotheses. Each later batch requires a new predeclared family with its own error budget. Screening resolves the edge action by returning supported routes as Direct and sending flagged routes to path-scale recovery under a separate certificate. Path-Scale Recovery and Query-Scale Retrieval Certification At the path scale, a flagged edge activates alternative routes whose value depends on shared failure incidence rather than route count. The certificate measures how many corrupted edges can contaminate a majority of declared paths. Let F⊆EF E be corrupted edges. A declared path is contaminated when it intersects F. For m=||m=|P|, define C(F) C_P(F) =|p∈:p∩F≠∅|, =|\p :p∩ F≠ \|, (14) κ1/2() _1/2(P) =minF|F|:C(F)≥⌈m/2⌉. = _F\|F|:C_P(F)≥ m/2 \. (15) Overlapping paths earn robustness only when more bad edges are required to contaminate half the route family. For example, ten routes sharing one external edge have κ1/2=1 _1/2=1, whereas five edge-disjoint routes have κ1/2=3 _1/2=3. Thus κ1/2 _1/2 converts shared failure incidence into the strict clean-majority condition required by coordinate-median recovery. A separate clean calibration split contains native targets yi∗y_i^* and the outputs of the same fixed, anchor-registered path family used at deployment. Define owner residuals Zi=maxp∈‖yi,p−yi∗‖∞,Z_i= _p \|y_i,p-y_i^*\|_∞, (16) and let ε^δp _ _p be the split-conformal upper order statistic at rank ⌈(N+1)(1−δp)⌉ (N+1)(1- _p) (or +∞+∞ when that rank exceeds N). The path budget establishes structural recoverability, while the clean split calibrates a finite-sample radius. The chain then enters the query scale by converting this path evidence into a covered top-k candidate set. Theorem 3 (Calibrated sparse-graph prediction set). Fix a declared via-edge corruption budget b<κ1/2()b< _1/2(P). Assume future clean-path residuals are exchangeable with the N calibration owners. Also assume the realized corrupted via-edge set satisfies |F|≤b|F|≤ b. Define ρ:=dε^δp.ρ:= d\, _ _p. (17) Under the joint law of the path-calibration sample and one future owner, ℙ(‖y^−y∗‖2≤ρ)≥1−δp.P(\| y-y^*\|_2≤ρ)≥ 1- _p. (18) Let the gallery contain J vectors with norm at most one and fix 1≤k<J1≤ k<J. Write sj=⟨y^,gj⟩s_j= y,g_j . Define ℓj=sj−ρ _j=s_j-ρ and uj=sj+ρu_j=s_j+ρ. Let τk _k be the kkth largest lower endpoint and set k=j∣uj≥τk.C_k=\j u_j≥ _k\. (19) For the clean native set Sk∗=Topk(y∗)S_k^*=Top_k(y^*), ℙ(Sk∗⊆k)≥1−δp.P(S_k^* _k)≥ 1- _p. (20) Let S^k=Topk(y^) S_k=Top_k( y) and let γ^k γ_k be its observed boundary gap. Then |k|=k⟺γ^k>2ρ. _k =k γ_k>2ρ. (21) Define Certified by this equivalent condition. Then ℙ(Certified∩S^k≠Sk∗)≤δp.P (Certified∩\ S_k≠ S_k^*\ )≤ _p. (22) When |k|>k _k >k, the method returns kC_k and abstains from a point top-k output. Proof idea. The inequality |F|<κ1/2()|F|< _1/2(P) leaves a strict majority of F-free paths. On the conformal event, every such path lies in the coordinate box centered at y∗y^* with radius ε^δp _ _p. Both central order statistics lie in that box in every coordinate. Their coordinate median therefore lies within the radius in Eq. (17). For every gallery item, Cauchy–Schwarz gives |⟨y^−y∗,gj⟩|≤ρ.| y-y^*,g_j |≤ρ. (23) Hence its clean score lies in [ℓj,uj][ _j,u_j]. At least k items have lower endpoint at least τk _k. An item outside kC_k has upper endpoint below τk _k and cannot enter Sk∗S_k^*. This proves Eq. (20) on the conformal event. All intervals have the same radius, so τk=s(k)−ρ _k=s_(k)-ρ and k=j∣sj≥s(k)−2ρ.C_k=\j s_j≥ s_(k)-2ρ\. (24) It has size k exactly when s(k+1)<s(k)−2ρs_(k+1)<s_(k)-2ρ. This is Eq. (21). On the coverage event, a certified set contains Sk∗S_k^* and has the same cardinality. It must equal Sk∗S_k^*. Therefore a certified error can occur only when coverage fails, proving Eq. (22). The supplement proves the interval minimality statement. At the path scale, the theorem maps the budget and calibration to a recovery radius. At the query scale, it maps that radius to a covered top-k candidate set. The output becomes point-valued when the observed margin reduces this set to k items. The statistical certificate chain leaves two routes to an incorrect non-abstaining output. A separated bad direct edge can pass screening, or a query certificate can fail when its covered radius event fails. Corollary 1 (End-to-end error decomposition). Conditional on the screening controls, consider one bad direct edge that satisfies the separation in Theorem 2. Let the path-calibration sample and future query owner follow the joint law in Theorem 3, independently of the screening data. Then ℙ(wrong non-abstaining output∣s)≤e−2neΔ2/B2+δp.P(wrong non-abstaining output _s)≤ e^-2n_e ^2/B^2+ _p. (25) A wrong Direct output requires a bad-edge pass. A wrong Certified output requires failure of the covered radius event. The union bound gives Eq. (25). Separately, Holm controls the graph-wide probability of changing any clean direct route by δs _s. The corollary closes the statistical chain at the returned query output. At the path scale, the corruption budget is sharp in the path-output model. An adversary with budget κ1/2 _1/2 can choose an edge set that contaminates at least half the paths and can drive the coordinate median unbounded. For cosine retrieval, normalization adds the deterministic factor in the supplement. If r selected paths are edge-disjoint, κ1/2=⌈r/2⌉ _1/2= r/2 . Maximizing r gives directed edge connectivity by Menger’s theorem (Menger 1927). Failure diversity, rather than route count, therefore becomes the next graph-design objective. Computation, Route Planning, and Preservation-First Decision Rule The path budget defines a graph-design objective, while the multiscale chain maps the reached certificate level to one of three actions. For fixed path-edge incidence Hpe=e∈pH_pe=1\e∈ p\ and costs ce≥0c_e≥ 0, the weighted exact budget is minz,h _z,h ∑eceze _ec_ez_e (26) s.t. hp≤∑eHpeze,∑php≥⌈m/2⌉, h_p≤ _eH_pez_e, _ph_p≥ m/2 , (27) ze,hp∈0,1. z_e,h_p∈\0,1\. (28) The weighted explicit-incidence problem is NP-hard by reduction from set cover (Karp 1972). Equation (28) gives an exact offline formulation of this optimization problem. Edge-disjoint routes provide a polynomial-time certificate for deployment planning. A deployment planner should maximize κ1/2 _1/2 or its weighted analogue subject to hop, latency, and edge-quality constraints. State Condition Meaning Direct edge passes Holm-adjusted screen exact routing-layer preservation after frozen registration Certified edge flagged, prerequisites hold, and |k|=k|C_k|=k point top-k output with Eq. (22) Abstain |k|>k|C_k|>k or another check is unavailable covered candidate set kC_k when available Table 2: CertBind maps the certificate level reached by the deployment chain to one of three actions. The deployment log records the complete audit contract, anchor rank, σr(A) _r(A), conformal p-value, Holm threshold, declared budget, path radius, covered top-k candidate set, observed margin, and final state. By construction, the fallback aggregation excludes the registered direct-edge output. Add-only insertion freezes old encoders, maps, registrations, route sets, and thresholds. This rule therefore gives exact zero drift on retained routing layers. The preservation-first rule operationalizes this chain by retaining supported routes as Direct and sending flagged routes to recovery. Recovery becomes Certified only when the query-scale candidate set contracts to k items. Otherwise, the output is Abstain, with the covered top-k candidate set when available. Deployment Evidence for Certifiable Composition Released checkpoints and recorded protocols expose three operational demands of certifiable composition. Table 3 organizes the corresponding evidence as preservation, expansion, and preserve-or-recover behavior. Purpose Recorded comparison Outcome Preservation C-MCR native route CLIP I→ R@1 0.5240.524 Preservation C-MCR shared route CLIP I→ R@1 0.2900.290 Expansion Clotho, C-MCR T→ R@1 0.1680.168 Expansion Clotho, Ex-MCR T→ R@1 0.1800.180 Expansion Clotho, towers only T→ R@1 0.2420.242 Expansion Clotho, graph+Ex T→ R@1 0.2670.267 Routing Production fallback clean recovery 0.963±0.0020.963± 0.002 Routing Passing branch measured no-harm 1.0001.000 Table 3: Evidence for preservation, expansion, and preserve-or-recover routing under released checkpoints and recorded protocols. Native-route preservation. On the native CLIP image-to-text workload, the evaluated C-MCR shared route changed R@1 from 0.5240.524 to 0.2900.290. This comparison identifies native preservation as a separate deployment target. Cross-modal expansion. On the disjoint 245-clip Clotho subset, the original maps were applied without edge refitting. C-MCR and Ex-MCR reached text-to-audio R@1 values of 0.1680.168 and 0.1800.180, respectively. Towers alone reached 0.2420.242, while adding Ex-MCR as optional graph evidence reached 0.2670.267. Preserve-or-recover routing. Across three seeds, the production via-only fallback recovered 0.963±0.0020.963± 0.002 of clean retrieval, while the passing branch recorded no-harm 1.0001.000. A separate five-family blind-median stress suite included the direct output and recovered 0.9830.983–0.9890.989. Together, these cases separate native preservation, cross-modal expansion, and selective recovery. From Multimodal Connectivity to Certifiable Composition Multimodal composability extends beyond representation connectivity to the task scores induced by a composed graph. Graph consistency describes relative structure, while native anchors determine whether that structure preserves fixed native-gallery scores. A connector can therefore remain internally coherent while changing an established retrieval route. This distinction makes task identification the node-scale prerequisite for native preservation. A related distinction between literal information preservation and downstream recoverability also appears in lossy text compression, where strategically deleted content may be reconstructed by an LLM (Zou et al. 2026). CertBind addresses a different problem: it does not reconstruct omitted content, but certifies whether connector-induced representation uncertainty preserves a fixed native retrieval decision. Calibration is part of composition design because each statistical certificate is indexed by its deployment population. Contract strata determine where edge ranks are valid, while owner units and route families determine path calibration. Broader strata can violate exchangeability, whereas narrower strata reduce attainable p-value resolution. Control collection and route design must therefore be planned together. For median recovery, the relevant unit of graph redundancy is shared failure incidence rather than route count. Paths that share one edge repeat outputs without adding protection against that edge. The majority path-transversal budget converts this failure structure into both a recovery criterion and a route-planning objective. In CertBind, a recovered representation becomes a certified retrieval output only when its uncertainty clears the query’s observed top-k boundary. The calibrated radius induces a covered top-k candidate set whose size depends on the observed margin. Well-separated queries support a point certificate, while boundary-adjacent queries remain set-valued and return Abstain. Certification is therefore a property of the query decision rather than aggregate fallback accuracy. Task-relevant symmetries provide a route beyond orthogonal charts for certifiable composition. The present identification result studies orthogonal gauges because inner-product retrieval is invariant to a common orthogonal change. Other connector families induce different task-relevant symmetry groups, whose stabilizers determine the corresponding identification condition. Noncompact and nonlinear actions require separate identification and estimation results. Scope and Ethical Considerations The guarantees are indexed by explicit deployment conditions at each certificate scale. The declared anchor condition identifies native task scores under the orthogonal chart model. Within-contract exchangeability establishes clean-edge validity, while independent owner clusters and conditional mean separation give the miss bound. The path theorem permits arbitrary outputs on routes touching corrupted edges when the declared edge budget remains below κ1/2 _1/2. Exact budget computation may require offline integer optimization, while edge-disjoint paths provide a polynomial certificate. The certificate chain also determines the evidence recorded for each deployment decision. Before automatic recovery, an operator declares the task subspace and native gallery. The record identifies native anchors, their conditioning, connector contracts, route incidence, calibration populations, and owner-level path residuals. Any missing required field maps the affected query to Abstain. CertBind supports auditable deployment decisions and retains human-governed escalation for unresolved queries. Deployment records contain connector and calibration metadata and should receive the same access controls as model artifacts. The reported empirical record covers released checkpoints under the stated protocols. Conclusion Lightweight connector graphs make frozen multimodal systems composable at the representation level. CertBind extends this composability to the decision level through a multiscale certificate chain spanning native task identification, contract-aware graph-wide screening, overlap-aware recovery, and finite-sample top-k certification. An exact node-scale identification boundary, graph-wide edge control, sharp path robustness, and finite-sample query coverage provide the formal basis for this chain. Its preservation-first policy retains supported routes, certifies decisive recovery, and records unresolved queries as Abstain. Connectivity is a property of the graph. Certifiability is a property of the task decision. References A. Achara, T. Gaintseva, M. Mahaut, P. Chakraborty, V. S. Johansson, M. Barsbey, E. Rodolà, and D. Crisostomi (2026) Multi-way representation alignment. arXiv preprint arXiv:2602.06205. Cited by: Unified spaces and connector graphs.. Y. Bansal, P. Nakkiran, and B. Barak (2021) Revisiting model stitching to compare neural representations. In NeurIPS, Cited by: Representation identifiability and stitching.. R. Girdhar, A. El-Nouby, Z. Liu, M. Singh, K. V. Alwala, A. Joulin, and I. Misra (2023) ImageBind: one embedding space to bind them all. In CVPR, Cited by: Unified spaces and connector graphs.. S. Holm (1979) A simple sequentially rejective multiple test procedure. Scandinavian Journal of Statistics 6 (2), p. 65–70. Cited by: Robust recovery and conformal inference.. Z. Huang, G. Niu, X. Liu, W. Ding, X. Xiao, H. Wu, and X. Peng (2021) Learning with noisy correspondence for cross-modal matching. In NeurIPS, Cited by: Robust recovery and conformal inference.. P. J. Huber and E. M. Ronchetti (2009) Robust statistics. 2 edition, Wiley. Cited by: Robust recovery and conformal inference.. M. Huh, B. Cheung, T. Wang, and P. Isola (2024) Position: the platonic representation hypothesis. In ICML, Cited by: Representation identifiability and stitching.. R. M. Karp (1972) Reducibility among combinatorial problems. In Complexity of Computer Computations, R. E. Miller and J. W. Thatcher (Eds.), p. 85–103. Cited by: Computation, Route Planning, and Preservation-First Decision Rule. S. Kornblith, M. Norouzi, H. Lee, and G. Hinton (2019) Similarity of neural network representations revisited. In ICML, Cited by: Representation identifiability and stitching.. G. Lerman and Y. Shi (2022) Robust group synchronization via cycle-edge message passing. Foundations of Computational Mathematics 22 (6), p. 1665–1741. Cited by: Robust recovery and conformal inference.. W. Liang, Y. Zhang, Y. Kwon, S. Yeung, and J. Zou (2022) Mind the gap: understanding the modality gap in multi-modal contrastive representation learning. In NeurIPS, Cited by: Representation identifiability and stitching.. Y. Lyu, X. Zheng, J. Zhou, and L. Wang (2024) UniBind: llm-augmented unified and balanced representation space to bind them all. In CVPR, Cited by: Unified spaces and connector graphs.. K. Menger (1927) Zur allgemeinen kurventheorie. Fundamenta Mathematicae 10, p. 96–115. Cited by: Proof idea.. L. Moschella, V. Maiorca, M. Fumero, A. Norelli, F. Locatello, and E. Rodolà (2023) Relative representations enable zero-shot latent space communication. In ICLR, Cited by: Representation identifiability and stitching.. G. Roeder, L. Metz, and D. P. Kingma (2021) On linear identifiability of learned representations. In ICML, Cited by: Representation identifiability and stitching.. V. Vovk, A. Gammerman, and G. Shafer (2005) Algorithmic learning in a random world. Springer. Cited by: Robust recovery and conformal inference.. H. Wang, S. Wang, Y. Zhong, Z. Yang, J. Wang, Z. Cui, J. Yuan, Y. Han, M. Liu, and Y. Ma (2026) Affordance-r1: reinforcement learning for generalizable affordance reasoning in multimodal large language models. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 40, p. 9738–9746. External Links: Document Cited by: Introduction. Z. Wang, Z. Zhang, X. Cheng, R. Huang, L. Liu, Z. Ye, H. Huang, Y. Zhao, T. Jin, P. Gao, and Z. Zhao (2024) FreeBind: free lunch in unified multimodal space via knowledge fusion. In ICML, Cited by: Introduction, Unified spaces and connector graphs.. Z. Wang, Z. Zhang, M. Hong, H. Zhang, L. Liu, R. Huang, X. Cheng, S. Ji, T. Jin, H. Zhao, and Z. Zhao (2025) OmniBind: large-scale omni multimodal representation via binding spaces. In ICLR, Cited by: Introduction, Unified spaces and connector graphs.. Z. Wang, Y. Zhao, X. Cheng, H. Huang, J. Liu, L. Tang, L. Li, Y. Wang, A. Yin, Z. Zhang, and Z. Zhao (2023) Connecting multi-modal contrastive representations. In Advances in Neural Information Processing Systems, Cited by: Introduction, Unified spaces and connector graphs.. Z. Zhang, Z. Wang, L. Liu, R. Huang, X. Cheng, Z. Ye, W. Lin, H. Liu, H. Huang, Y. Zhao, T. Jin, S. Zheng, and Z. Zhao (2024) Extending multi-modal contrastive representations. In Advances in Neural Information Processing Systems, Cited by: Introduction, Unified spaces and connector graphs.. B. Zhu, B. Lin, M. Ning, Y. Yan, J. Cui, H. Wang, Y. Pang, W. Jiang, J. Zhang, Z. Li, W. Zhang, Z. Li, W. Liu, and L. Yuan (2024) LanguageBind: extending video-language pretraining to n-modality by language-based semantic alignment. In ICLR, Cited by: Unified spaces and connector graphs.. Y. Zou, J. Tong, and J. Li (2026) Text-preserving lossy text compression: a study of strategic deletion and llm reconstruction. External Links: 2605.29000 Cited by: From Multimodal Connectivity to Certifiable Composition.