Neuro-Symbolic Video Search

Minkyu Choi, Harsh Goel, Mohammad Omama, Yunhao Yang, Sahil Shah, Sandeep Chinchali

Abstract

Neuro-Symbolic Video Search with Temporal Logic (NSVS-TL) addresses the critical limitations of deep learning foundation models in long-term temporal reasoning. By decoupling neural perception from symbolic verification, the framework allows for the precise identification of complex events in long-form video data. Experimental results demonstrate a 9–15% accuracy improvement over state-of-the-art LLM-based benchmarks, with performance remaining stable even as video length increases to 40 minutes.

The Challenge of Temporal Reasoning

The explosion of video data—from autonomous vehicle logs to massive social media uploads—has outpaced our ability to search it effectively. While state-of-the-art foundation models like VideoLLaMA excel at short-clip understanding, they frequently fail at long-term temporal reasoning. This failure stems from the "intertwining" of perception and reasoning within a single black-box neural network. As video length increases, the model's internal memory (latent vector) becomes saturated, losing the precision required to track complex sequences of events over time.

The NSVS-TL Framework

The authors propose a neuro-symbolic pipeline that separates the "seeing" (perception) from the "thinking" (reasoning). This modular approach ensures that each component handles the task it is best suited for.

  1. Neural Perception: The system utilizes off-the-shelf models such as YOLOv8 or Grounding DINO to detect "atomic propositions"—simple labels like "car," "pedestrian," or "ship"—in every frame.
  2. Calibration: Raw confidence scores are mapped to probabilities using a generalized logistic function, ensuring the reasoning engine understands the uncertainty of the detections.
  3. Symbolic Verification & Frame Validation: The system filters frames based on the user's query logic. For instance, if a query specifies "no other passengers visible," frames containing detected bystanders are discarded.
  4. Dynamic Automaton Construction: The video is modeled as a Probabilistic Automaton (PA), a mathematical state machine where states represent object combinations and transitions represent the flow of time.
  5. Formal Verification: Instead of heuristic guessing, the system uses the STORM probabilistic model checker to evaluate the automaton against a Temporal Logic (TL) formula (e.g., Event A happens UNTIL Event B occurs).
The NSVS-TL pipeline: from neural perception to formal verification.

Experimental Setup and Datasets

To evaluate the system, the researchers introduced the Temporal Logic Video (TLV) datasets, as existing benchmarks lack complex, long-horizon labels:

  • Synthetic TLV: Created by stitching together static images from COCO and ImageNet to form artificial videos with known ground-truth sequences.
  • Real TLV: Derived from autonomous driving datasets (Waymo and NuScenes) and annotated with complex Temporal Logic specifications (e.g., "Find a scene where a bus is visible until a truck appears").

Performance Analysis

NSVS-TL demonstrates significant advantages over pure deep learning approaches. While Large Language Models (LLMs) like GPT-4 are capable reasoners, their performance "drops off a cliff" as video length increases, typically after 500–1000 seconds. In contrast, NSVS-TL remains stable for videos up to 40 minutes long.

Performance comparison of NSVS-TL against baselines across varying video lengths and proposition complexities.

Key results include:

  • Accuracy Boost: An improvement of 9–15% in F1 scores for complex event identification compared to LLM-based benchmarks.
  • Robustness to Complexity: The system significantly outperforms baselines in multi-event scenarios (e.g., "Event A and B until Event C").
  • Interpretability: Unlike opaque neural networks, NSVS-TL provides a mathematically provable trace explaining why a specific video segment satisfies a query.

Conclusion and Future Directions

By decoupling perception from reasoning, NSVS-TL avoids the forgetting problems inherent in pure deep learning models. However, the system currently relies on per-frame detections, which can struggle with "multi-frame semantics" or actions defined by movement (e.g., "falling"). Future work will focus on integrating dedicated action-recognition models to capture these complex dynamics, further expanding the capabilities of neuro-symbolic video understanding.

Summary updated

BibTeX
@inproceedings{choi2024neuro,
  author = {Minkyu Choi and Harsh Goel and Mohammad Omama and Yunhao Yang and Sahil Shah and Sandeep Chinchali},
  title = {{Neuro-Symbolic Video Search}},
  booktitle = {European Conference on Computer Vision},
  year = {2024},
  doi = {10.1007/978-3-031-73229-4\_13},
}
Figure