TL;DR
NAVER (Neuro-symbolic compositional Automaton for Visual grounding with Explicit logic Reasoning) is a new framework that tackles complex visual grounding by combining the flexibility of Large Language Models (LLMs) with the precision of formal probabilistic logic. By organizing the reasoning process into a self-correcting finite-state automaton, NAVER achieves state-of-the-art performance and significantly higher robustness than previous compositional methods.
What Problem Does This Paper Address?
Visual Grounding (VG) is the task of locating specific objects in an image based on a text description. While current models are great at finding a "dog," they often stumble on complex, multi-step queries like "a person on the left wearing a blue shirt in front of a car."
The authors identify three main gaps in existing approaches:
- Implicit Reasoning: End-to-end "black box" models struggle with geometric and relational logic that humans find intuitive.
- Ambiguous Planning: Current compositional models use LLMs to generate natural language plans, which are often too vague for precise execution.
- Error Propagation: Most pipelines are "one-way streets." If the object detector makes a mistake in the first step, the entire process fails without any chance for the system to realize its error and try again.
Methods
NAVER introduces a neuro-symbolic architecture governed by a Deterministic Finite-State Automaton (DFA). As shown in the pipeline overview, the system moves through five distinct states:
- Perception ($S_P$): A Vision-Language Model (VLM) captions the scene, and an LLM identifies relevant entity categories (e.g., "person," "car"). A grounding model then localizes these candidates.
- Logic Generation ($S_L$): Instead of natural language, an LLM generates ProbLog code—a probabilistic logic programming language. This code represents the query as a set of formal rules and facts.
- Logic Reasoning ($S_R$): A logic interpreter executes the ProbLog code to find the best candidate based on spatial relations and attributes (like "blue shirt").
- Answering ($S_A$): A final verification step where a VLM looks at the top candidate and answers a simple "Yes/No" to confirm it matches the original query.
- Return Target ($S_F$): The final state reached only after successful verification.
The "secret sauce" is the self-correction mechanism (the red arrows in the DFA). If the verification in the Answering state fails, the system doesn't just give up; it can transition back to Perception or Logic Generation to refine its search or reasoning.
Datasets
The authors evaluated NAVER on several standard and challenging benchmarks:
- RefCOCO, RefCOCO+, and RefCOCOg: The standard "gold standard" datasets for referring expression detection and segmentation.
- Ref-Adv: An adversarial dataset specifically designed to test robustness against complex reasoning and attribute-heavy queries.
- RefCLEF: A dataset used to further validate segmentation performance.
Key Insights and Ideas
- Logic as a Robust Bridge: Moving from natural language plans to formal ProbLog code eliminates ambiguity. ProbLog also allows the system to handle uncertainty (e.g., "I'm 80% sure this is a blue shirt") mathematically rather than heuristically.
- LLMs are Better Verifiers than Solvers: A key insight is that while LLMs might struggle to find the exact coordinates of a complex target, they are excellent at confirming if a proposed target meets the criteria. NAVER leverages this by using the LLM as the final "gatekeeper" in the Answering state.
- The Power of the "Retry": Most AI pipelines are brittle. By framing the task as a DFA, NAVER can recover from intermediate failures. The authors found that approximately 10% of samples required self-correction, and a single retry resolved 68% of those errors.
Key Results
NAVER sets a new bar for visual grounding:
- State-of-the-Art Accuracy: On RefCOCO, NAVER achieved 96.2% accuracy, outperforming both end-to-end models like Florence2 and compositional baselines like HYDRA.
- Reliability: NAVER reduced the runtime failure rate to just 0.3%, compared to 10.3% for HYDRA and a staggering 70.2% for ViperGPT.
- Complexity Robustness: Unlike many models that see performance tank as queries get longer and more complex, NAVER’s performance remains remarkably stable.
Limitations and Future Work
The primary limitation acknowledged is that the system's reasoning is still bounded by the LLM's ability to generate correct logic code. If the LLM fails to translate a very niche linguistic structure into ProbLog, the reasoning engine will fail. The authors suggest that fine-tuning LLMs specifically for logic code generation in visual contexts is a promising future direction. Additionally, while the DFA is deterministic, the underlying neural models are probabilistic, leaving room for further optimization in how feedback is passed between states.
Summary updated