💻 computer science

SceneGraphVLM: Dynamic Scene Graph Generation from Video with Vision-Language Models

SceneGraphVLM is a compact, two-stage trained vision-language model that generates high-precision scene graphs from images and videos with approximately one-second latency by utilizing a token-efficient TOON serialization format and hallucination-aware reinforcement learning.

Original authors: Vladislav Makarov, Mark Gizetdinov, Dmitry Yudin

Published 2026-05-14

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Vladislav Makarov, Mark Gizetdinov, Dmitry Yudin

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are looking at a busy street scene. A traditional computer vision system might try to list every single thing it sees: "car, car, car, tree, tree, person, person..." and then try to guess how they are connected. Often, this results in a messy, overwhelming list full of mistakes, like saying a cloud is "touching" a car just because they are close in the picture.

SceneGraphVLM is a new method designed to clean up this mess. Think of it as a smart, efficient narrator that looks at an image or a video and instantly writes a short, structured story about what is happening, focusing only on what is actually there.

Here is how it works, broken down into simple concepts:

1. The Problem: The "Over-enthusiastic" Storyteller

Previous AI models that tried to do this were like an over-enthusiastic tour guide. They would tell you everything, including things that weren't there (hallucinations) or repeating the same facts over and over. They were also slow and produced very long, messy text that was hard for other computers to read.

2. The Solution: A "Telegraph" Style (TOON Format)

The authors realized that the way the AI writes its story matters. Instead of using a bulky format like JSON (which is like writing a letter with lots of extra words like "The object is...", "The relation is..."), they invented a TOON format.

The Analogy: Imagine sending a message via telegraph where you pay by the word. You wouldn't write "The cat is sitting on the mat." You would write "Cat, sit, mat."
The Result: SceneGraphVLM uses this "telegraph" style. It strips away all the extra fluff, making the output much shorter, faster to generate, and easier for computers to understand. It saves about 15–20% of the "space" needed to describe the same scene.

3. The Training: Learning by Doing (and Being Corrected)

The model is trained in two distinct stages, like a student learning a new skill:

Stage 1: Supervised Fine-Tuning (SFT) – The "Copycat" Phase:
The AI is shown thousands of pictures and their perfect descriptions. It learns to mimic this style. It learns the rules: "If I see a dog, I must write 'dog' and its location."
Stage 2: Reinforcement Learning (RL) – The "Strict Coach" Phase:
This is the secret sauce. In the first stage, the AI might still make up things that aren't there (hallucinations) just to be safe. In this second stage, a "coach" (a reward system) watches the AI.
- The Rule: If the AI invents a relationship that doesn't exist (e.g., saying a person is "holding" a cloud), the coach gives it a penalty.
- The Goal: The AI learns that it's better to be precise and say only what it sees, rather than guessing everything. It balances being thorough with being accurate.

4. The Video Superpower: "Memory" Without Tracking

When watching a video, things change from frame to frame. Traditional video AI needs a complex "tracker" to follow a person from one second to the next, like a security guard following a suspect.

SceneGraphVLM does this differently. It treats the video like a conversation.

The Analogy: Imagine you are describing a movie scene to a friend. You don't start from scratch every second. You say, "Okay, the guy is still there, but now he's walking left."
How it works: The AI looks at the current frame and briefly remembers the "story" it just told about the previous frame. It uses that memory to stay consistent without needing a heavy-duty tracking system. This keeps the video description smooth and fast.

5. The Results: Fast and Accurate

The paper tested this on three major datasets (PSG, PVSG, and Action Genome).

Speed: It can generate a full description of a scene in about one second. That's fast enough for near-real-time applications.
Quality: It is much better at not making things up compared to older methods. While other models might generate a messy web of 20 connections (many of which are wrong), SceneGraphVLM generates a tight, clean web of 5–6 connections that are actually true.
Efficiency: It works well even on smaller, cheaper computer chips (using a small model called Qwen3.5-0.8B), proving you don't need a massive supercomputer to get good results if you use the right "telegraph" format and training method.

Summary

SceneGraphVLM is a lightweight, fast AI that turns images and videos into clean, structured stories. It uses a shorthand language to save time, learns from a "strict coach" to stop making things up, and remembers the previous moment to keep video descriptions consistent—all without needing heavy, complex tracking systems.

Technical Summary: SceneGraphVLM

Problem Statement

Scene Graph Generation (SGG) aims to represent visual scenes as compact, structured graphs where nodes denote objects and edges encode relations. While essential for downstream tasks like robotics and video analysis, generating accurate, structurally valid, and compact scene graphs remains challenging. Traditional multi-stage pipelines suffer from error propagation and brittleness. Recent Vision-Language Model (VLM) approaches offer end-to-end generation but often produce long, token-inefficient outputs containing irrelevant objects and hallucinated relations. Furthermore, existing VLM-based methods frequently prioritize recall, leading to overly complete graphs that dilute useful information and reduce reliability for decision-making. Extending these challenges to video, maintaining temporal consistency without complex tracking or post-processing remains an open problem.

Methodology

The authors propose SceneGraphVLM, a compact end-to-end method for image and video scene graph generation using small visual-language models. The methodology is built on three core pillars:

1. Token-Efficient Serialization (TOON Format)

To address the high decoding costs and length of standard JSON representations, the authors serialize scene graphs into a TOON format. This schema stores objects as rows under a shared header and relations in compact blocks, removing repeated keys and nested boilerplate. This reduces annotation length by approximately 1.17× to 1.24× across datasets (PSG, PVSG, Action Genome) while preserving all object, bounding box, and relation information, thereby accelerating generation and reducing latency.

2. Two-Stage Training Pipeline

The model undergoes a two-stage optimization process:

Supervised Fine-Tuning (SFT): The base VLM (specifically Qwen3.5-0.8B) is trained to map visual inputs to the target TOON schema. This stage teaches the model to follow the required format, use dataset-specific vocabularies, and produce parseable structured outputs.
Reinforcement Learning (RL) with GRPO: To optimize graph-level quality beyond token-level supervision, the authors employ Group Relative Policy Optimization (GRPO). Crucially, they introduce hallucination-aware rewards that balance relation coverage with precision. The total reward function ( $R_{total}$ $R_{t o t a l}$ ) combines:
- Base Graph Rewards: Format validity, object classification, and object localization (via Hungarian matching and IoU).
- Relation-Balance Rewards: Precision and F1-based terms to prevent the model from over-generating relations to maximize recall.
- Hallucination Penalties: Explicit penalties for unmatched (unsupported) objects and relations, discouraging the generation of ungrounded entities.

3. Video Inference with Temporal Context

For video sequences, SceneGraphVLM processes frames sequentially. It can condition the generation of the current frame's graph on the graph generated for the previous frame. This provides lightweight short-term temporal context without requiring separate tracking modules. The authors evaluate two protocols:

GT-prompt: Using ground-truth previous graphs (oracle setting).
Generated-prompt: Using the model's own previous predictions (realistic deployment setting), which tests robustness against error propagation.

Key Contributions

SceneGraphVLM Architecture: A compact end-to-end method utilizing small VLMs (e.g., Qwen3.5-0.8B) and the token-efficient TOON representation, achieving strong quality-speed trade-offs.
Hallucination-Aware Training: The introduction of GRPO-based training with graph-oriented rewards that explicitly penalize unsupported objects and relations, balancing recall with precision to produce grounded, compact graphs.
Efficient Video SGG: A lightweight approach for video scene graph generation that leverages previous-frame graphs for temporal context without complex post-processing, achieving near-real-time inference.

Experimental Results

The method was evaluated on PSG (Panoptic Scene Graph), PVSG (Panoptic Video Scene Graph), and Action Genome.

Performance vs. Baselines: On PSG, SceneGraphVLM achieves an SGG score of 0.442 (Strict) and 0.460 (Soft), outperforming zero-shot commercial VLMs (e.g., Gemini-3-flash at 0.318) and larger open-source models. It significantly improves precision-oriented metrics compared to recall-heavy baselines like R1-SGG.
Video Performance: On PVSG, the model demonstrates robustness in the Generated-prompt setting. The RL stage improves the Strict SGG score by 19% (from 0.306 to 0.365) over the SFT-only checkpoint, outperforming all commercial and open-source baselines.
Efficiency: Leveraging the TOON format and vLLM-accelerated decoding, SceneGraphVLM generates complete scene graphs in approximately 0.64 seconds for images and 1.07 seconds for videos on a single A100 GPU.
Action Genome: The model achieves a Precision@50 of 38.74 and F1@50 of 30.75, substantially outperforming the OED baseline (P@50=8.02, F1@50=13.37) in precision, demonstrating its ability to avoid hallucinated relations.

Significance and Claims

The paper claims that SceneGraphVLM establishes a new quality-speed trade-off for generative scene graph generation. By combining a token-efficient representation with precision-aware reinforcement learning, the method enables small VLMs to produce reliable, compact, and visually grounded scene graphs suitable for near-real-time applications. The authors emphasize that their approach addresses the common failure mode of VLM-based SGG—over-generation and hallucination—by explicitly penalizing unsupported content during training. The ability to maintain temporal consistency in videos using only the previous generated graph, without external tracking, is highlighted as a significant step toward practical deployment in robotics and video analysis.

The authors note limitations, including reliance on closed-vocabulary datasets, potential error accumulation in video sequences, and the need for specific GPU resources for real-time inference, but assert that the method provides a practical foundation for VLM-based SGG in downstream tasks.