Near-Miss Verification for Referring Segmentation That Knows When to Say "Nothing"

When a model is asked to segment "the kid in the blue shirt" in a photo that only contains a kid in a purple shirt, current systems usually segment the purple-shirted kid anyway. This proposal treats "is the described object here at all?" as a conjunction of small checks. Is there a kid? Is that kid's shirt blue? Does the stated spatial relation hold? The target exists only if some candidate region passes every check. The model abstains when the best candidate is a near-miss, meaning it fails exactly one check. We score candidates without assuming the checks fail independently, and we calibrate the abstain decision on held-out empty queries. The result is a controlled rate of "ghost masks," masks drawn for objects that are not there.

Why this matters: in benchmarks that include absent targets, the absent-or-present decision sits at the root of the prediction and carries the rest of it. A wrong "present" yields a ghost mask. A wrong "absent" throws away a correct mask. Neither can be repaired by a better mask head. The field's own analyses say the dominant remaining failure is the deceptive near-miss expression. Existing models answer it with one learned "no target" score that cannot tell "nothing resembles this" apart from "something matches four of five words." We also use two ideas from classical search theory. The first is the ordering rule for conjunctive checks, which runs the checks most likely to fail first. The second is the warning that independence assumptions break when failures are correlated. Together they make verification cheap enough to run with expensive verifiers such as large vision-language models, and optionally with image-external text like captions.

Core Claim

Consider generalized referring expression segmentation (GRES), the task of segmenting all regions an expression refers to, possibly zero or several. Our claim is that no-target errors are concentrated on near-miss queries. They are reduced more by explicit per-constraint, per-candidate verification with a correlation-aware aggregator than by stronger monolithic existence heads. At a fixed ghost-mask rate on absent-target queries, this verification should keep more correct detections on present-target queries than the best existing no-target mechanisms. The gain should come mostly from the near-miss stratum.

Formally, let $c$ range over candidate regions and $k$ over the $K$ constraints parsed from the expression. Let $p_k(c)$ be a verifier's probability that candidate $c$ satisfies constraint $k$. The textbook "independent AND" score is

$$S_{\text{ind}} = \max_c \prod_{k=1}^{K} p_k(c).$$

We replace it with $S = \max_c A_\theta(p_1(c),\dots,p_K(c))$, where $A_\theta$ is a small learned aggregator trained on near-miss negatives. The aggregator can represent correlated verifier errors. For example, attribute checks tend to fail together on small or occluded regions. A product assumes such failures are unrelated and so treats weak-but-uniform evidence and one decisive failure alike.

The abstain threshold $\tau$ is the $\lceil (n+1)(1-\alpha)\rceil$-th smallest score among $n$ held-out absent-target queries. Under exchangeability, this gives a finite-sample guarantee that at most a fraction $\alpha$ of absent-target queries receive a ghost mask. The calibration step is standard split-conformal thresholding and is not itself the contribution. The contribution is a score for which that guarantee costs less recall.

Where Prior Work Stands

Three lines of GRES work motivate the gap and supply our base models.

GRES and its extension GREx introduced gRefCOCO and the ReLA model. ReLA adds region-level attention and an explicit no-target branch. Both papers name deceptive expressions as the main open failure.

CoHD decodes at several semantic levels and adds an object-counting head that predicts zero for absent targets. InstAlign aligns phrases to object instances and uses a global no-target token.

All three still collapse existence into a single learned signal, a flag, a count, or a token. None exposes which constraint failed on which candidate. Our method sits on top of their instance proposals rather than replacing their mask decoders.

Rex-Thinker grounds objects by step-by-step reasoning over candidates. It is the closest in spirit to explicit verification. It does not calibrate abstention or account for the cost of each reasoning call. We borrow its style of candidate-by-candidate checking as one verifier option.

A constraining result comes from He et al.. They show that large vision-language models "see" digitally removed objects because they rely on co-occurrence statistics. So a verifier built on such a model cannot be trusted raw, and calibration on real absent-target queries is necessary rather than cosmetic.

The search-theory side supplies method, not motivation.

  • Barnett proves the ordering rule for conjunctive checks. Evaluate checks in decreasing order of failure probability over expected cost, $q/E$, and stop at the first failure. For disjunctions (OR over candidates), the rule is the mirror image.
  • Barnett and Cohen show that switching costs between alternatives break simple sorting. In our setting, re-cropping and re-encoding a new candidate is such a cost. They give the corrected merit $p_i/(c_i+(1-p_i)d_i)$ with an $O(n\log n)$ schedule.
  • Barnett notes that the static-order optimality fails when outcomes are correlated. This is exactly the regime here, and it is where the uniform-tree and independence assumptions that Pearl and Gaschnig criticize for classical search reappear in perception. We therefore use these results as a baseline ordering and test adaptive ordering against them.

For hierarchical error propagation, Zhou et al. show that a scan-then-zoom cascade cannot recover from a bad first stage. Wang et al. show that letting fine evidence correct coarse decisions helps. Our design follows the second lesson: per-constraint evidence can overturn the coarse "exists" decision. We also measure the first lesson's failure in our own pipeline. If the true target is absent from the candidate set, no verifier can recover it.

The conformal hierarchical-classification method CRSVP gives coverage guarantees on label trees but has no empty answer. Ours is a much simpler calibration problem whose only set-valued output is "nothing."

On external metadata, MISTI and Whitehead show that structured side text resolves what pixels cannot. Behavior-LLaVA shows the value of external signals and also their platform bias. GRSer uses other images in a group as context for confirming absence. Metadata plays a secondary role in this proposal. It is one more verifier whose reliability is learned and whose failures the calibration must survive. It is not the core mechanism.

Research Program

Components. The system has four parts.

  1. A constraint parser. A language model splits each expression into a category, attribute constraints, and relation constraints. Parse errors are audited on a hand-labeled sample.
  2. A candidate generator. This is the instance-query set of a reproduced GRES base model, with a COCO-trained detector as an alternative. We measure candidate recall directly, because it bounds everything downstream.
  3. A verifier bank at three cost levels:
  4. a cheap level of crop-level CLIP-style attribute scores;
  5. a medium level of the base model's own phrase-to-instance alignment scores;
  6. an expensive level of a vision-language model asked yes/no about one constraint on one crop.
  7. The aggregator $A_\theta$. It is trained on gRefCOCO's training split plus synthetic near-miss negatives, made by swapping one attribute or relation word in a positive expression, and it is compared against product, min, and noisy-OR aggregation.

Hand-labeled strata. We label a stratified sample of gRefCOCO validation absent-target expressions by type: category absent, single-attribute near-miss, relation near-miss, and multi-constraint mismatch. This lets every result be reported per stratum.

Metadata verifier. The optional external-context verifier uses the human captions that accompany COCO images, which underlie gRefCOCO. A text entailment model checks whether any caption supports a constraint. We will first verify how often captions mention the queried attribute at all, since that sets the ceiling. Robustness is tested with captions swapped in from visually similar images. That corruption should raise false abstentions or ghost masks unless the aggregator learns to discount the verifier.

Scheduling. Each expensive verifier call costs measured wall-clock time. We compare four orderings:

  • exhaustive evaluation;
  • Barnett's static $q/E$ ordering, with $q$ estimated from training-set failure rates per constraint type;
  • the Barnett–Cohen merit with candidate-switch costs;
  • an adaptive order that updates remaining failure probabilities after each outcome using the learned correlations.

We report expensive calls per query against no-target accuracy.

Baselines

Do-nothing reference. The first reference is the base GRES model's native existence decision at its default threshold. We report ReLA as a guaranteed-reproducible anchor. GRES reports 63.60% gIoU on gRefCOCO val, and GREx reports 63.98. gIoU is a generalized IoU in which a correctly empty prediction on an absent-target query counts as a perfect score.

Strongest existing method. This is InstAlign, which Nguyen et al. report at 74.34% gIoU and 79.72% no-target accuracy (N-acc, the fraction of absent-target queries correctly left empty) on gRefCOCO. It is the strongest competitor because it already reasons at the instance level with a dedicated no-target token. Any gain from explicit verification has to show up beyond what instance alignment already captures. CoHD, reported as +4.8% gIoU over ReLA by its authors, is a second strong existence mechanism. We include it if reproducible.

Fair comparison protocol. Our verification layer runs on top of the same backbone and the same instance candidates. Every baseline's existence threshold is re-tuned on the same calibration split under the same target ghost-mask rate $\alpha$, so no method wins by sitting at a different operating point. Beating InstAlign means one of two things. The first is higher present-target accuracy at the same calibrated $\alpha$ on absent-target queries. The second is an N-acc above 79.72% with no loss in present-target accuracy and a gIoU gain, with the improvement concentrated in the near-miss strata.

Reasoning baseline. We run a Rex-Thinker-style verifier alone, with the model's own yes/no answer as the decision and the same candidates. There is no reported result found on Lacuna for chain-of-thought grounding models on gRefCOCO no-target accuracy.

Key ablation. This baseline isolates the proposal's ingredient: our full pipeline with $A_\theta$ replaced by the independent product $S_{\text{ind}}$ and by min. If the learned correlation-aware aggregator does not beat these at matched $\alpha$, the claim about correlated failures fails.

Why not just…?

Why not just tune the existing no-target threshold? This is the most serious threat. InstAlign's no-target token may already separate near-misses well, and our calibration step is itself only a threshold. The experiment settles it by re-calibrating every baseline's own score to the same $\alpha$. If their tuned curves match ours on the near-miss strata, explicit verification adds nothing, and we will report that. The existing evidence only shows that single binary flags underperform instance-level mechanisms, as the gap between InstAlign and earlier models and the CoHD analysis indicate. It does not show that instance-level tokens are the ceiling.

Why not just prompt a large vision-language model to reason about presence? The removed-object study by He et al. indicates that such models assert expected objects from context. Uncalibrated yes/no answers should therefore produce ghost masks on exactly the co-occurrence-plausible near-misses. The model is also expensive per call. Our design uses it as one verifier, so the question becomes empirical. We compare it alone against the same model inside calibrated aggregation with cost-ordered calls. If the raw model matches us at equal cost and equal $\alpha$, the proposal reduces to "calibrate the reasoning model," which would still be a useful but smaller finding.

Why not just append captions to the input text? Following MISTI, wrapping side text in marker tokens is a cheap way to give the segmenter context. We run this as a baseline. The risk is that the segmenter learns to trust captions blindly. The swapped-caption test measures that directly, comparing appended-caption and verifier-caption variants under identical corruption. If appending is equally robust and equally accurate, the metadata verifier is unnecessary. The core verification claim does not depend on it.

Proposed Experiments

Oracle-gate check. The first decisive check comes before any method building. We replace each base model's existence decision with the ground-truth existence label and measure the gIoU gain. This quantifies how much of the remaining error propagates from the root decision rather than from mask quality. If the oracle gain on InstAlign is small, the program is not worth pursuing and we stop.

Near-miss concentration. The second check measures, per stratum, what fraction of residual ghost masks are single-constraint near-misses. The claim predicts they dominate.

Main result. The third experiment is the main comparison. It plots present-target accuracy against the calibrated ghost-mask rate for all baselines and our method, on gRefCOCO val and test and on Ref-ZOM. CoHD reports +6.3% accuracy on Ref-ZOM, which we cite only as context for that dataset. Empirical ghost-mask rates are checked against the nominal $\alpha$, including on Ref-ZOM with a threshold calibrated on gRefCOCO. That transfer test is expected to break the exchangeability guarantee, and the goal is to see by how much.

Aggregator and candidates. The fourth experiment is the aggregator ablation described above, plus a candidate-recall analysis. It counts false abstentions caused by the true target never entering the candidate set. This is the scan-then-zoom failure that Zhou et al. identify, now in the reverse direction.

Scheduling. The fifth experiment compares the four orderings of expensive verifier calls. We expect static $q/E$ ordering to cut calls substantially relative to exhaustive checking. We expect adaptive ordering to help further only when learned verifier correlations are strong. That would be a direct empirical test of where Barnett's static-optimality result stops applying.

Transfer to image groups. As an optional transfer, we run the verifier bank on the Group Referring Dataset. There, GRSer reports 75.32% mIoU on G-RefCg. We test whether per-image conjunctive verification confirms certified negatives as well as cross-image prototypes do.