Grounding a complex sentence in an image means picking one detected object for each noun phrase. In "the man holding a book near the lamp," that is a box for the man, one for the book and one for the lamp, chosen so that every stated relation holds between the chosen boxes. Written this way, grounding is a constraint-satisfaction problem. Each phrase is a variable, the candidate boxes are its possible values, and each relation is a scored constraint between two variables. Current structural grounding models solve this problem only approximately. They use neural message passing, cross-attention, or continuous optimal-transport relaxations, and none of these comes with a guarantee that the returned assignment is the best one. Our claim is that this approximation is unnecessary for most real queries. The cost of solving the problem exactly is governed by the treewidth of the query graph: treewidth measures how far a graph is from being a tree, and the query graph is the small graph of phrases and relations. It is not governed by the dense and messy graph of visual objects. If the query graphs are close to trees, exact inference costs about $k\,m^{w+1}$ operations for $k$ phrases, $m$ candidate boxes and width $w$, which is affordable at benchmark scale.
The proposal makes three linked contributions. We will measure the width of real query graphs once coreference ("his hat") and distinct-entity constraints ("two men") are added. We will build an exact dynamic-programming grounder that uses the same learned scores as existing models, and train it end-to-end with exact gradients. We will also map the complexity frontier honestly. Without distinctness constraints, tree-shaped queries are solvable in polynomial time. Once distinct phrases must map to distinct boxes, even path-shaped queries are NP-hard. That regime is fixed-parameter tractable in query size, meaning it is fast whenever the query is small, but it provably admits no lossless polynomial-size preprocessing. Proposal pruning in that regime therefore has to be measured rather than assumed safe.
Core Claim
The relevant structure for compositional grounding is the query graph plus a small number of cycle-closing edges. It is not the scene graph. Two factors decide accuracy on complex queries once the unary and pairwise scorers are fixed. One is whether those cycle-closing constraints are enforced. The other is whether inference over them is exact. This yields one measurable quantity, which we call the grounding laminarity gap: the accuracy lost when the cyclic query constraint graph is forced into a tree before inference. A dependency parse is laminar, meaning its constituents nest hierarchically. Coreference, shared objects and distinctness requirements introduce crossings that break that nesting. The name borrows from Packing multiway cuts in capacitated graphs, which defines the laminarity gap as the unavoidable load increase when a crossing family of cuts is uncrossed into a nested one. Here it serves as a measurement lens, not a theorem transfer.
Concretely, given query graph $Q=(V_Q,E_Q)$, candidates $C$ with $|C|=m$, a unary scorer $s_u(c)$ for phrase $u$ and box $c$, and a pairwise scorer $s_{uv}(c,c')$ for relation $(u,v)$, we solve
$$\hat{a}=\arg\max_{a:V_Q\to C}\ \sum_{u\in V_Q}s_u(a(u))+\sum_{(u,v)\in E_Q}s_{uv}(a(u),a(v))\quad\text{s.t. } a(u)\neq a(v)\ \text{for } (u,v)\in D,$$
where $D$ is the set of query-node pairs that must refer to distinct objects.
Why this, and why now
Two lines of structural grounding motivate the gap. Learning Cross-Modal Context Graph for Visual Grounding parses sentences into phrase graphs and matches them against an object-proposal graph using a learned graph similarity network. Its global matching step is what lifts Flickr30K Entities accuracy to 76.74%, yet that step is a heuristic optimizer. Towards Complex-query Referring Image Segmentation: A Novel Benchmark introduces RIS-CQ and DUMOGA. DUMOGA aligns dependency trees with scene graphs and reaches 24.4 mIoU, where the attention-only LAVT reaches 10.84. Both papers show that structure helps. Neither asks whether their optimizer finds the best structured answer, and neither says what the tractable structure is. Joint Multimodal Entity-Relation Extraction Based on Edge-Enhanced Graph Alignment Network and Word-Pair Relation Tagging supplies a third design, Gromov-Wasserstein optimal transport for edge alignment, which is non-convex and approximate. Its ablation shows the relational term matters: F1 falls from 55.29% to 51.07% without it. The relational constraints are where the value lies, and they are also what the relaxations handle loosely.
The method comes from structural graph algorithms. Courcelle's theorem, as used in Computing Crossing Numbers in Quadratic Time and On Graphs Coverable by k Shortest Paths, says that any property written in monadic second-order logic can be decided in linear time on bounded-treewidth graphs. That logic quantifies over sets of vertices, and the procedure is a finite-state pass over a tree decomposition. Applying the theorem naively to grounding fails in two ways, and we design around both. First, the visual scene graph is dense, with many crossing, directed relations. On Graphs Coverable byShortest Paths shows that directed and non-isometric path structures keep treewidth unbounded, so the width bound must come from the query side. Second, generic compilation of a formula into an automaton incurs a tower of exponentials. We therefore take only the lesson of the meta-theorem: uniqueness ("the only red ball"), negation ("the man not holding anything"), threshold counting and distinctness keep the dynamic-programming state finite. We then hand-build the states for that small fragment. Improving Vertex Cover as a Graph Parameter supports this choice: it obtains elementary rather than non-elementary dependence by restricting structure.
Kernelization theory constrains the design. Limits of Preprocessing shows that constraint satisfaction parameterized by treewidth admits no polynomial kernel, meaning no polynomial-size lossless compression, unless NP ⊆ coNP/poly. It proves this through cross-composition, a construction that glues many hard instances into one instance with a small parameter, as also used in Clique Cover and Graph Separation: New Incompressibility Results. For grounding we get a clean instance of the same phenomenon. With distinctness constraints, grounding a path-shaped query with uniform labels is exactly the k-Path problem. Placing $t$ scenes side by side as disjoint candidate groups is an OR-composition: the joint scene grounds the query if and only if some individual scene does. So injective grounding parameterized by query size has no polynomial kernel under the standard assumption, even though color coding solves it in FPT time. In plain terms, no pruning rule can be guaranteed to keep only poly($k$) candidate boxes without sometimes discarding the unique correct answer. This is the theoretical reason the pruning step in Learning Cross-Modal Context Graph for Visual Grounding and in Flickr30k Entities: Collecting Region-to-Phrase Correspondences for Richer Image-to-Sentence Models has to be audited. The latter paper reports exactly that pruning losses on small objects cannot be recovered downstream.
Research Program
The first component is a structural census. We will parse every query in Flickr30K Entities and RIS-CQ into a query graph using the parsers DUMOGA and the context-graph model already rely on. We will add coreference edges from Flickr30K's 244,035 annotated coreference chains, and add distinctness pairs between same-category phrases. We then compute exact treewidth, which is easy at these sizes. For contrast, we also compute the treewidth of the predicted visual scene graphs. Our hypothesis is that query width is at most 2 or 3 for nearly all queries, while scene-graph width grows with object count. If that holds, it supports the claim that the scene is the wrong place to look for tractability.
The second component is the exact grounder. We build a tree decomposition of each query graph and run max-product dynamic programming over its bags. Each bag stores a table over joint candidate assignments of its phrases, extended with small bit-states for the logical fragment: a "seen another satisfying box" flag for uniqueness, and a bounded counter for counting. Distinctness edges join the decomposition like any other edge. For training we run sum-product over the same decomposition, which gives exact marginals and so an exact conditional-random-field likelihood. The scorers are those of the baseline being compared: Wan et al.'s phrase and object graph features for Flickr30K, and DUMOGA's node and edge features for RIS-CQ. Holding the scorers fixed means the comparison isolates inference.
The third component is certified pruning. Before running the dynamic program, we remove a candidate $c$ for phrase $u$ only if an upper bound on any assignment using $c$ falls below the score of a feasible assignment already found greedily. Such pruning is lossless by construction and is decided per query. The kernel lower bound tells us it cannot always shrink $m$ to poly($k$), so we report how much it shrinks in practice next to the loss from top-K pruning.
The fourth component is the theory. We will write out the frontier: polynomial time for distinctness-free queries of bounded width; NP-hard but FPT in $k$, with no polynomial kernel, once distinctness enters; and polynomial again when distinctness pairs are confined to a bounded number of same-category groups, which we expect is the realistic regime. We will check whether the last case has a polynomial kernel parameterized jointly by $k$ and the number of distinctness pairs, and treat it as an open question until proved.
Baselines
The naive reference point grounds each phrase independently by the argmax of its unary score. It uses the same proposals and scorer and ignores all relations. It shows how much relational inference is worth at all.
The strongest existing methods are the published structured models, run in their own published configurations. On Flickr30K Entities that is the cross-modal context graph of Learning Cross-Modal Context Graph for Visual Grounding, which reports 76.74% grounding accuracy with ResNet-101 and 67.90% with ResNet-50. On RIS-CQ it is DUMOGA from Towards Complex-query Referring Image Segmentation: A Novel Benchmark, which reports 24.4 mIoU. These are the strongest competitors because they already contain a global structural matching step, so any gain we show must come from exactness and the added constraints, not from merely using structure. For a fair comparison we reuse their backbones, proposals and feature extractors. We swap only the matching or inference module and retrain with the same epoch budget and the same hyperparameter search size, and we reproduce their numbers in our pipeline before claiming any delta. Beating them means a statistically significant gain over our reproduced number across three seeds, concentrated on queries of width at least 2 and on queries with coreference or distinctness.
A second inference-level baseline swaps the exact dynamic program for Gromov-Wasserstein matching in the style of Joint Multimodal Entity-Relation Extraction Based on Edge-Enhanced Graph Alignment Network and Word-Pair Relation Tagging, and also for loopy max-product belief propagation, on identical scores. The JMERE benchmark itself has a reported EEGA F1 of 55.29%. We will treat it only as a secondary transfer check because its graphs are word-pair grids, not grounding queries.
Two ablations isolate the key ingredient. The tree-projection ablation drops all cycle-closing edges and runs exact inference on a spanning tree of the parse; its difference from the full grounder is the grounding laminarity gap. The no-distinctness ablation keeps cycles but drops the distinctness pairs. An integer-programming solver run on the full objective serves as a correctness oracle and as a runtime competitor.
Why not just…?
Why not just run max-product on the dependency tree? This is the most serious threat. It is exactly our tree-projection ablation, so the experiments settle it directly. If the grounding laminarity gap is near zero on both benchmarks, then exact tree inference is all one needs. The contribution then shrinks to the claim that exactness beats the relaxations used by DUMOGA and the context-graph model, and we would report that plainly. Our expectation that the gap is positive rests on Flickr30K's dense coreference and on RIS-CQ's 13-word average queries, where repeated reference to the same object is common. That is a hypothesis, not a finding.
Why not just use a stronger end-to-end model with cross-attention? LAVT's drop to 10.84 mIoU on RIS-CQ, against DUMOGA's 24.4, and the attribute-binding failures documented in Uncovering Limitations in Text-to-Image Generation: A Contrastive Approach with Structured Semantic Alignment show that flat attention struggles with multi-relational queries. More to the point, our grounder sits on top of any scorer. A stronger backbone improves the unary and pairwise scores we consume, so the two are complementary rather than competing. We test this by also running the grounder on the ResNet-50 variant to see whether gains persist across scorer quality.
Why not just hand the objective to an integer-programming solver? A solver also returns exact answers, and we use one as the oracle. The difference is predictability: the dynamic program has a runtime bound fixed by measured width, and it yields exact marginals for training, which a branch-and-bound solver does not provide cheaply. If the solver turns out fast and trainable through a surrogate, the practical case for the dynamic program weakens. The scientific claims about width and the laminarity gap would stand either way.
Why not just keep the top-K boxes per phrase? The k-Path reduction shows that no pruning rule can be both lossless and worst-case small once distinctness is enforced, and Flickr30K Entities documents unrecoverable pruning losses on small objects. We measure, at matched candidate budgets, how often top-K pruning discards the box that exact inference would select, and compare it with certified pruning.
Proposed Experiments
The first decisive check is the census. If more than a small fraction of queries exceed width 3, the runtime story fails at $m\approx100$ and we fall back to the integer-programming route. The second is the accuracy comparison against reproduced context-graph and DUMOGA numbers with matching held to the same scorer. We stratify results by query width, coreference presence and distinctness presence. The claim predicts gains concentrated in the non-tree strata and none on tree queries.
The third check is the grounding laminarity gap, reported per benchmark and per stratum. The fourth is an inference-quality audit on identical scores. Using the oracle, it records the fraction of queries on which Gromov-Wasserstein matching or loopy belief propagation returns a suboptimal assignment, and how often suboptimality coincides with a grounding error. If relaxations are almost always optimal, exactness cannot be the source of any gain, and we will say so.
The fifth is the pruning audit: candidate reduction and answer-loss rate for certified versus top-K pruning, with small-object phrases reported separately. The last is a targeted test of the logical fragment on RIS-CQ queries containing "only," negation or counting words, identified by keyword and verified by hand on a sample. It asks whether the uniqueness and counting states change answers relative to the plain relational objective. Throughout we report wall-clock inference time beside accuracy, since a slower exact method must earn its cost.
References
- Packing multiway cuts in capacitated graphs
- Learning Cross-Modal Context Graph for Visual Grounding
- Towards Complex-query Referring Image Segmentation: A Novel Benchmark
- Joint Multimodal Entity-Relation Extraction Based on Edge-Enhanced Graph Alignment Network and Word-Pair Relation Tagging
- Computing crossing numbers in quadratic time
- On Graphs Coverable by k Shortest Paths
- On Graphs Coverable byShortest Paths
- Improving Vertex Cover as a Graph Parameter
- Limits of Preprocessing
- Clique Cover and Graph Separation: New Incompressibility Results
- Flickr30k Entities: Collecting Region-to-Phrase Correspondences for Richer Image-to-Sentence Models
- Uncovering Limitations in Text-to-Image Generation: A Contrastive Approach with Structured Semantic Alignment