VIRO: Robust and Efficient Neuro-Symbolic Reasoning with Verification for Referring Expression Comprehension

AI summary

Overview

• Research area: Referring Expression Comprehension (REC) within vision-language AI, specifically neuro-symbolic / compositional reasoning with large language models (LLMs) and vision-language models (VLMs).
• Technical level: Advanced. The paper assumes familiarity with open-vocabulary detectors, CLIP-style contrastive models, symbolic program generation, and REC benchmarks.
• Scope in one sentence: The paper introduces and evaluates VIRO, a framework that attaches lightweight verification to each operator in an LLM-generated reasoning program so that a REC system can reject nonexistent targets, avoid cascading errors, and run efficiently in a 1-query–N-image setting.

What This Paper Is About

Existing neuro-symbolic REC systems translate a natural language query into a structured program of modular operators and execute it step by step, but they assume every intermediate step is correct. That assumption causes cascading errors: false detections from open-vocabulary detectors (OVDs) and invalid spatial relations propagate through the chain, producing confident false positives even when the described object is not in the image at all. The paper's goal is to make each reasoning operator both act and verify, so the pipeline can abstain and terminate early instead of being forced to output a box for a nonexistent target.

Key Contributions

1. The authors identify forced prediction as a fundamental failure mode of compositional vision-language reasoning, and introduce verification-integrated operators to address it.
2. They design operator-level programs in which each operator both acts and verifies, using uncertainty-based checks (a CLIP-based filter inside FIND) and logic-based checks (geometric and depth-relation tests) to suppress error cascades and enable explicit no-target detection.
3. In a zero-shot setting, VIRO reports strong robustness on the gRefCOCO no-target split and state-of-the-art performance among compositional baselines on standard REC benchmarks.
4. The framework decouples program synthesis from execution, so a single generated program is amortized over many images, giving favorable scaling in the 1-query–N-image regime.

Main Findings

• No-target robustness: VIRO reaches 61.1% balanced accuracy (50.2% TNR, 71.9% TPR) on the gRefCOCO no-target split paired with RefCOCO TestA, and 56.9% (52.9% TNR, 60.8% TPR) on TestB. Compositional baselines are far lower: ViperGPT 33.4, HYDRA 35.2, NAVER 33.8 balanced accuracy on TestA, with TNR of 0.2, 7.5, and 3.4 percent respectively.
• Forced prediction in baselines: Proposal-based methods (ReCLIP 23.5, SS-CLIP 33.3, GroundVLP 30.7 balanced accuracy on TestA) show 0.0% TNR because they must select one region from a pre-generated pool.
• Competitive with supervised methods without no-target supervision: Fully supervised models score 69.5 (Qwen2.5-VL-72B-AWQ), 62.0 (GREC-MDETR-R101), and 70.4 (GREC-UNINEXT-R50) balanced accuracy on TestA, so VIRO narrows the gap without any REC fine-tuning or no-target annotations.
• Reliability: VIRO's program failure rate is 0.07% on RefCOCO, 0.00% on RefCOCO+, and 0.30% on RefCOCOg, giving nearly identical inclusive and exclusive accuracies (71.9/71.9, 63.3/63.3, 66.6/66.3). HYDRA fails at 28.46%, 35.96%, and 32.37%, and NAVER at 6.01%, 7.39%, and 9.74%.
• Efficiency: Execution-stage runtime on RefCOCO testA is 0.71 s per query for VIRO versus 30.57 s for HYDRA, 7.08 s for NAVER, and 1.49 s for ViperGPT, measured on an NVIDIA RTX A6000 GPU. End-to-end latency is 12.92 s for VIRO, dominated by program generation.
• Scalability: Because program generation happens once per query (T_total = T_pre-execution + N × T_execution) rather than once per image, VIRO scales smoothly with the number of images, while HYDRA and NAVER require regeneration for every image.
• Egocentric video: On the RefEgo test set (all frames), VIRO obtains 22.8 mSTIoU and 51.9 Acc@0.5+n, exceeding the fully supervised MDETR+BH (36.9 mSTIoU, 51.1 Acc@0.5+n) on the latter metric, and on target-present frames reaches 36.2 TPR versus 27.6 for ViperGPT, 27.1 for OFA, and 22.8 for MDETR.
• Ablation of verification components: Starting from a detector-only baseline (40.0 balanced accuracy, 22.8 TNR, 57.1 TPR), adding operators raises balanced accuracy to 56.8, adding logical verification to 57.0, adding uncertainty verification with a fixed threshold to 58.8, and with an adaptive threshold to 61.1 — with TPR moving from 74.6 down to 71.9, reflecting a precision–recall trade-off.
• Threshold and backbone choices: The OVD detection threshold was set to 0.2 to favor recall at the proposal stage. The CLIP backbone ViT-H/14 gives 71.9 TPR at 0.71 s execution time, while the lighter ViT-L/14 gives 68.8 TPR at 0.55 s.
• Adaptive threshold calibration: Because CLIP is biased toward frequently seen labels, the authors calibrate per-label thresholds using ImageNet as auxiliary data, collecting 5 images per class (5,000 images total) and cropping class objects with GroundingDINO.

Methodology in Plain English

VIRO runs in two separate stages. In the pre-execution stage, an LLM (Qwen2.5-72B-Instruct-AWQ) converts the natural language query into a short symbolic program built from a fixed set of primitive operators, and a validator checks the program's syntax and argument structure, feeding diagnostics back to the LLM for self-revision if needed. The operator vocabulary covers identification (FIND, PROPERTY), absolute spatial reasoning (LOCATE, SIZE, ORDER, ABSOLUTE_DEPTH), relative spatial reasoning (FIND_DIRECTION, FIND_NEAR, FIND_INSIDE, RELATIVE_DEPTH), and a terminating RESULT operator.

In the execution stage, the program is run line by line with built-in models — GroundingDINO or GLIP for detection, CLIP for attribute and uncertainty checks, and DepthAnything for depth. The distinctive step is that every operator verifies its own output. The FIND operator crops each detector proposal and compares CLIP similarity against the target label versus each of K predefined negative anchor categories, averaged into a verification score; proposals below a label-specific adaptive threshold are discarded. Spatial operators instead perform geometric tests, for example checking whether an object box actually lies in the requested direction of a reference object, or whether boxes intersect at all for containment. If any operator's verification fails, it returns the empty set, the pipeline halts immediately, and the system declares no target — this is the abstention mechanism that baselines lack. Because generation is decoupled from execution, the same program is reused across all images for a given query.

Why This Matters

The work shifts REC from an always-answer task to one that can say "not present," which matters for any deployed system where most images will not contain the described object. It also shows that lightweight, operator-level checks can substitute for expensive large multimodal models in the inner reasoning loop.

Real-world applications mentioned or implied by the paper:

• Robotic visual search, where a robot looks for an object across many views of a building and most views contain nothing matching the query.
• Human-robot interaction and instruction following, where ambiguous or ungroundable commands should be rejected before action rather than acted on.
• Vision-language navigation, which relies on grounding descriptions to regions.
• Egocentric video understanding, as demonstrated on RefEgo built on Ego4D, where target visibility varies frame to frame.
• Text-to-image retrieval, where the query region must be localized or reported as absent.

Industry relevance: the low failure rate (at most 0.3%) and 0.71 s execution-stage runtime make the pipeline closer to production-viable than iterative planner–reasoner loops, and the decoupled design directly targets the cost structure of serving one query over large image collections.

Future Directions

• Extending the operator set and validation grammar to new task types; the authors show modular extension to GQA in the appendix, suggesting the approach generalizes beyond REC.
• Interactive and dialogue-based settings in embodied AI, where robots interpret complex instructions and reject ambiguous commands before acting.
• Broader video and temporal reasoning, since RefEgo results show zero-shot grounding is competitive but the fully supervised model still leads on mSTIoU.
• Open questions the paper leaves for readers: how well per-label thresholds calibrated on ImageNet transfer to new domains, how sensitive results are to the negative anchor bank and the OVD threshold, and whether the verification overhead remains small as operators grow more complex.

Target Audience

Researchers and engineers working on vision-language grounding, neuro-symbolic and compositional reasoning, and multimodal agents, particularly those concerned with reliability, abstention, and inference cost rather than raw accuracy alone. It is also relevant to practitioners building robotic search or egocentric video systems who need a model that can report the absence of a target instead of hallucinating one.

Authors’ abstract

Referring Expression Comprehension (REC) aims to localize the image region corresponding to a natural language query. Recent neuro-symbolic REC approaches leverage large language models (LLMs) and vision-language models (VLMs) to perform compositional reasoning, decomposing queries into structured programs and executing them step-by-step. While such approaches achieve interpretable reasoning and strong zero-shot generalization, they assume that intermediate reasoning steps are accurate. However, this assumption causes cascading errors: false detections and invalid relations propagate through the reasoning chain, yielding high-confidence false positives even when no target is present in the image. To address this limitation, we introduce Verification-Integrated Reasoning Operators (VIRO), a neuro-symbolic framework that embeds lightweight operator-level verifiers within reasoning steps. Each operator executes and validates its output, such as object existence or spatial relationships, allowing the system to robustly handle no-target cases through verification-aware abstention. Our framework achieves state-of-the-art performance, reaching 61.1% balanced accuracy across target-present and no-target settings, and demonstrates generalization to real-world egocentric data. VIRO also shows high reliability with a program failure rate of at most 0.3%, efficient per-query runtime, and scalability through decoupled program generation and execution.