RESCU: RELATIONAL SCENE CONSTRAINT UNDERSTANDING FOR ZERO-SHOT REFERRING IMAGE SEGMENTATION

Referring image segmentation asks a model to find the exact pixels an expression describes. Zero-shot methods almost universally reduce this to cross-modal retrieval: embed the expression and each candidate region in a shared CLIP space and take the best match. That formulation cannot represent relational constraints$-$left_of, between, negation $-$ because no single embedding-space comparison ever sees the joint configuration of target and anchor. We introduce ReSCU ($\text{Re}$lational $\text{S}$cene $\text{C}$onstraint $\text{U}$nderstanding), which builds an explicit relational scene graph over open-vocabulary proposals, parses the expression into a typed query, and evaluates it symbolically to produce a $\text{symbolic}$ hypothesis - then arbitrates it against a strong $\text{appearance}$ hypothesis obtained by prompting a modern promptable-concept segmenter (SAM3) directly with the raw expression. The key idea, Dual-Hypothesis Mask Arbitration (DHMA), is to trust the appearance branch by default and promote the symbolic hypothesis only when a gate calibrated on held-out data says the parse is trustworthy. We study three such gates, of increasing capacity: hand-set thresholds, a sparse learned classifier, and a denser one over an expanded feature set. The hand-set gate ($\text{lock A}$) sits at statistical parity with matched SAM3-text and does not transfer across datasets. A sparse logistic gate over 17 features ($\text{lock C}$), selected $\text{blind}$ (grid fixed a priori, scored on held-out data, test touched once), produces a significant win on RefCOCOg ($56.13$/$55.16$ val/test mIoU, $\Delta +2.54$/$+1.89$pp, CI excluding zero) that transfers frozen to RefCOCO ($\Delta +0.91$/$+0.86$pp) and RefCOCO+ ($\Delta +1.17$/$+0.93$pp). Replacing lock C's classifier with a denser gradient-boosted one over 27 features ($\text{lock D}$) nearly doubles the margin ($59.01$/$56.66$ mIoU, $\Delta +5.41$/$+3.38$pp, CI $[+2.78,+4.02]$ test) and still transfers frozen to RefCOCO ($\Delta +1.53$/$+1.30$pp) and RefCOCO+ ($\Delta +2.19$/$+1.15$pp). Both gates lead every published zero-shot RIS number we could verify, including HybridGL ($51.25$/$51.59$) and RefChess ($50.63$/$51.32$), and both help all four expression types, not only the relational one lock A targeted. An oracle upper bound sits $11.2$ points above lock A's baseline; lock C closes $$\begin{gathered} \approx \\ !23\% \end{gathered}$$ of that gap and lock D $$\begin{gathered} \approx \\ !48\% \end{gathered}$$, so roughly half remains unrealized under the best gate we found. Detection is not the bottleneck $-$ $96.5\%$ of gold targets survive to the proposal stage$-$but a frozen VLM used for spatial-edge prediction collapses to a single answer on $60/60$ held-out pairs, so our default edge backend stays geometric rather than learned. Lock D's larger gain also comes from intervening $3$-$4\times$ more often through a harder-to-audit model, so we keep lock C as a sparse, interpretable alternative alongside lock D's headline result, and view closing the remaining oracle gap as the natural next step.