NAVER: A Neuro-Symbolic Compositional Automaton for Visual Grounding with Explicit Logic Reasoning

Zhixi Cai, Fucai Ke, Simindokht Jahangard, Maria Garcia de la Banda, Reza Haffari, Peter J. Stuckey, Hamid Rezatofighi

TL;DR

This paper introduces NAVER, a novel neuro-symbolic system for visual grounding that combines explicit probabilistic logic reasoning with a self-correcting finite-state automaton. NAVER significantly improves the robustness and interpretability of visual grounding by breaking down complex queries into logical steps and allowing for dynamic error correction, achieving state-of-the-art performance on challenging benchmarks.

What Problem Does This Paper Address?

Visual grounding, the task of linking textual descriptions to specific objects or regions in an image, is crucial for many AI applications. While recent advances in Large Language Models (LLMs) and Vision-Language Models (VLMs) have improved visual comprehension and reasoning, current methods often struggle with complex queries that require intricate logical reasoning, akin to human cognition. Existing compositional approaches, which break down tasks into smaller steps, still face limitations: they heavily rely on the implicit commonsense knowledge of LLMs, use ambiguous natural language for logic representation, and lack mechanisms to correct errors that propagate through the inference pipeline. This paper aims to bridge this gap by introducing a system that explicitly integrates probabilistic logic reasoning and a self-correcting mechanism for more robust and interpretable visual grounding.

Methods

NAVER is built upon a deterministic finite-state automaton (DFA) with five states: Perception, Logic Generation, Logic Reasoning, Answering, and Return Target. This DFA structure allows for dynamic transitions between states, enabling a self-correcting mechanism.

  • Perception: This state uses a VLM to generate a descriptive caption of the image. An LLM then identifies relevant entity categories from the caption and query. A foundation grounding model detects these entities and their bounding boxes, assigning probabilities.
  • Logic Generation: Here, an LLM translates the textual query and the identified entities into ProbLog logic expressions. This involves converting entities into ProbLog facts and generating rules that capture relations and attributes. VLMs are used to recognize attribute probabilities and directional relations, which are then incorporated into the ProbLog code.
  • Logic Reasoning: The generated ProbLog code is executed by a logic programming interpreter to perform probabilistic inference. This step identifies potential target candidates based on explicit probabilistic logic, ranking them by confidence.
  • Answering: A VLM acts as an "answerer" to validate the top-ranked candidate. The image is annotated with the candidate, and the VLM is prompted to confirm if it meets the query's criteria, providing a "Yes" or "No" answer.
  • Return Target: This is the final state, reached when the answerer confirms the target.

The self-correction mechanism is a key innovation. If an error is detected at any stage (e.g., logic generation failure, incorrect answer), the DFA can dynamically transition back to a previous state (e.g., Perception or Logic Generation) to refine the process. This is crucial for improving robustness and interpretability.

Datasets

NAVER is evaluated on standard visual grounding benchmarks:

  • RefCOCO
  • RefCOCO+
  • RefCOCOg
  • Ref-Adv

Key Insights and Ideas

  • Explicit Logic for Robustness: By explicitly representing reasoning steps in ProbLog, NAVER moves beyond the implicit reasoning of end-to-end models, making its decisions more interpretable and verifiable.
  • Finite-State Automaton for Dynamic Control: The DFA structure allows for flexible, non-linear transitions between processing stages, which is essential for implementing the self-correction mechanism and adapting to complex query requirements.
  • Self-Correction is Crucial: The ability to dynamically revisit previous states and correct errors significantly improves performance and reduces the impact of mistakes in early stages, a common issue in complex reasoning pipelines.
  • Compositionality with Explicit Logic: NAVER demonstrates that combining compositional approaches with explicit probabilistic logic reasoning can overcome the limitations of relying solely on LLMs for commonsense knowledge and natural language logic.

Key Results

NAVER achieves state-of-the-art (SoTA) performance on referring expression detection and segmentation tasks across multiple datasets (RefCOCO, RefCOCO+, RefCOCOg, Ref-Adv).

  • In referring expression detection, NAVER consistently outperforms both end-to-end and compositional baselines, even when using the same foundation models. For example, on the RefCOCO test A dataset, NAVER achieves an accuracy of 96.2% with its best configuration, surpassing other methods.
  • For segmentation, NAVER also demonstrates superior performance on RefCOCOg and RefCLEF datasets.
  • The self-correction mechanism is highly effective: approximately 10% of samples require self-correction, with 68% of errors resolved within a single retry and 96% within six retries.
  • NAVER is also more efficient than some compositional baselines, with a lower average runtime and token usage per sample, while achieving higher performance.

Limitations and Future Work

  • LLM Dependence for Code Generation: The logic code generation is still dependent on the capabilities of LLMs. Future work could focus on enhancing LLMs for more robust code generation.
  • Prompt Engineering: While the paper provides detailed prompts, fine-tuning these prompts could potentially further improve performance.
  • Generalization: While NAVER shows strong performance, further exploration into its generalization capabilities across a wider range of visual reasoning tasks and more complex, unseen scenarios would be beneficial.

The authors suggest that enhancing LLMs for code generation is a key direction for future research.

Summary updated

Abstract

Visual Grounding (VG) tasks, such as referring expression detection and segmentation tasks are important for linking visual entities to context, especially in complex reasoning tasks that require detailed query interpretation. This paper explores VG beyond basic perception, highlighting challenges for methods that require reasoning like human cognition. Recent advances in large language methods (LLMs) and Vision-Language methods (VLMs) have improved abilities for visual comprehension, contextual understanding, and reasoning. These methods are mainly split into end-to-end and compositional methods, with the latter offering more flexibility. Compositional approaches that integrate LLMs and foundation models show promising performance but still struggle with complex reasoning with language-based logical representations. To address these limitations, we propose NAVER, a compositional visual grounding method that integrates explicit probabilistic logic reasoning within a finite-state automaton, equipped with a self-correcting mechanism. This design improves robustness and interpretability in inference through explicit logic reasoning. Our results show that NAVER achieves SoTA performance comparing to recent end-to-end and compositional baselines. The code is available at https://github.com/ControlNet/NAVER .
BibTeX
@inproceedings{cai2025naver,
  author = {Zhixi Cai and Fucai Ke and Simindokht Jahangard and Maria Garcia de la Banda and Reza Haffari and Peter J. Stuckey and Hamid Rezatofighi},
  title = {{NAVER: A Neuro-Symbolic Compositional Automaton for Visual Grounding with Explicit Logic Reasoning}},
  booktitle = {IEEE/CVF International Conference on Computer Vision},
  year = {2025},
}
Figure