Can Vision-Language Models Solve the Shell Game?

AI summary

Overview

Research area: Computer vision / video-language understanding — specifically visual entity tracking in Vision-Language Models (VLMs), with a theoretical computer-science component (circuit complexity).

Technical level: Advanced. The paper combines empirical VLM benchmarking with an NC¹-completeness proof, transformer expressivity arguments (TC⁰ vs. NC¹), and chain-of-thought training.

Scope: A single paper that (1) audits an existing benchmark for shortcuts, (2) introduces a synthetic diagnostic benchmark (VET-Bench) for visual entity tracking, (3) proves the task is NC¹-complete, and (4) proposes a grounded chain-of-thought method (SGCoT) that lifts Molmo2 to over 90% accuracy.

What This Paper Is About

Tracking visually identical objects through a shuffling sequence — the shell game — is effortless for humans, but the authors show it is a fundamental blind spot for today's video VLMs. Existing benchmarks let models cheat by re-identifying objects from static appearance cues in a single frame, hiding the failure. The paper isolates genuine spatiotemporal tracking, explains theoretically why fixed-depth transformers cannot do it without intermediate computation, and then shows how to fix it with grounded chain-of-thought.

Key Contributions

1. Identification of a hidden benchmark flaw plus a new benchmark. The authors audit the Perception Test's cups-game subset and find that many clips contain appearance shortcuts (distinct cups, transparent cups, or final cut frames revealing the answer). They introduce VET-Bench, a synthetic testbed with visually identical objects, no frame-level cues, and controllable swap and object counts (50 cups-game and 50 cards-game videos, 3 objects, 5 swaps, ~12 seconds).

2. A comprehensive negative evaluation. Ten video-capable VLMs — Gemini-3, Gemini-2.5, Qwen-3.5, Qwen3-VL, GLM-4.6V-Flash, Ernie-4.5, Doubao-Seed-2.0, Kimi-K2.5, PerceptionLM, and Molmo2 — all perform at or near random-chance level (1/N) on VET-Bench, across model sizes and for both reasoning and non-reasoning configurations.

3. A theoretical characterization. The paper defines the decision problem TRACK_k and proves it is NC¹-complete for any fixed k ≥ 5, via a reduction from the word problem for the symmetric group S₅. Since constant-depth transformers lie in TC⁰, this establishes that intermediate computation (chain of thought) is necessary in principle.

4. Spatiotemporal Grounded Chain-of-Thought (SGCoT). By aligning Molmo2 to emit explicit object trajectories as intermediate states before answering, the authors achieve state-of-the-art accuracy exceeding 90% on VET-Bench — end-to-end, with no external tools.

Main Findings

• Frontier models fail at chance level. On VET-Bench, all evaluated VLMs perform near the random baseline. For a task with N objects, the random baseline is 1/N (0.33 for 3 objects). Table 1 shows scores on the filtered Perception Test subset vs. VET-Bench respectively: Random 0.33 / 0.33, Gemini-3-Pro 0.31 / 0.34, Gemini-3-Flash 0.40 / 0.30, Qwen3-VL-8B 0.34 / 0.30, GLM-4.6V-Flash 0.42 / 0.34, Doubao-Seed-2.0 0.40 / 0.30.

• The Perception Test score is inflated by shortcuts. Of the 3,525 videos in the Perception Test test split, the authors identify 189 cups-game clips. Filtering out visual shortcuts and requiring at least one swap leaves 107 video–question pairs; restricting to the strict 3-cup setting and excluding zero-swap cases leaves 65 videos. Gemini-3-Pro drops from 80% on the full dataset to 36.45% on the filtered subset, and further to 30.77% in the strict 3-cup setting — no better than random guessing (1/3).

• Failure starts after just one swap. With zero swaps (object permanence only), most models score near-perfectly, and Doubao-Seed-2.0-Mini can answer directly without CoT. Performance drops substantially after a single swap and converges to chance thereafter.

• Even two objects is too hard. At N = 2, where the task reduces to a parity problem, models still do not significantly beat the random baseline. Accuracy scales inversely with object count (1/N) at N = 2, 3, 4.

• Gemini-3 has a unique zero-swap hallucination mode. Gemini-3-Pro and Gemini-3-Flash often correctly identify the initial state but then hallucinate a long sequence of swaps that never occurred, producing wrong final answers. Rephrasing the question to ask about the start of the video restores near-perfect accuracy. The authors did not observe this prompt-sensitive pattern in other VLMs.

• Three recurring error patterns. (1) Direct Answer — models such as Molmo2, PerceptionLM, Doubao-Seed-1.8, and GLM-4.6V-Flash emit only a final answer, appearing to guess. (2) Coarse Description — models collapse the shuffling phase into high-level semantics (e.g., Qwen3-VL-8B-Instruct: "The cups are shuffled in a shell game-like motion, with the ball remaining under one of the cups throughout the video."). (3) Inaccurate Perception and Hallucination — reasoning models like Gemini-3-Pro and Gemini-3-Flash produce linguistically coherent swap sequences grounded in wrong visual perception, so errors cascade.

• Direct-answer training does not work. Training Qwen2.5-VL-3B-Instruct on 500 synthesized cups-game videos at 8 FPS with answer-only supervision leaves the loss stagnant at random-chance level even after 60 epochs.

• Annotated benchmarks are easier. Gemini-2.5-Pro reaches 56% on VideoReasonBench, where swap operations are marked with overlaid arrows acting as symbolic "swap tokens," yet stays near chance on VET-Bench, which has no such cues.

• SGCoT works and is cheap. Aligning Molmo2 takes one epoch over 300 text-only samples, completing in 3 minutes on a single A100 GPU, and improves accuracy from near-random to 91%. Overall the method exceeds 90% on VET-Bench.

Methodology in Plain English

The researchers built their own synthetic videos using three.js so they could control everything: the color, material, texture, lighting, camera angle, the number of objects, and the number of swaps. Critically, every object looks identical, so the only way to know which one is which after shuffling is to follow its motion continuously through the frames.

To make the task fair and unambiguous, they enforce a continuity constraint: the maximum displacement of any object between consecutive frames must satisfy 2d < Δ, where Δ is the minimum spatial separation between any two objects. This is a temporal Nyquist-style condition that prevents objects from "aliasing" into each other when they cross. In VET-Bench each swap lasts 2 seconds, so 1 FPS is the minimum sampling rate needed to resolve a swap — and they set 5 swaps per episode for a total duration as short as 12 seconds.

They then tested a large range of commercial and open-source video VLMs under each model's maximum supported frame rate, using multiple-choice grading and Top-1 accuracy.

For the theory, they formulated a decision problem called TRACK_k: given a video of k indistinguishable objects on a constant-size grid, decide whether the global permutation from the first frame to the last is the identity. They proved this is NC¹-complete for k ≥ 5 by reducing from the word problem for the symmetric group S₅, using physical trajectory "gadgets" that realize adjacent transpositions. Since prior work shows constant-depth transformers can be simulated in TC⁰, and TC⁰ ⊊ NC¹ is widely conjectured, fixed-depth transformers cannot solve this generally without intermediate computation.

For the fix, they exploited Molmo2's built-in video object tracking. Molmo2 can already emit trajectories in a structured format (<tracks coords="timestamp object_idx x y;...">Object</tracks>, with timestamps every 0.5 seconds and x, y normalized to 0–1000), but by default it answers tracking questions directly rather than tracking. The authors fine-tuned it on synthesized text-only trajectory data — no video input needed — masking the loss on the trajectory tokens and supervising only the final answer, so the model learns to derive its answer from the trajectory rather than from a guess.

Why This Matters

Impact on research. The paper shows that aggregate scores on real-world video benchmarks can mask fundamental perceptual failures. It also connects VLM benchmarking to established complexity-theoretic results about state tracking, giving a principled reason — not just an empirical observation — for why chain of thought is needed for entity tracking. It argues that visual entity tracking belongs in the same complexity class as tracking chess moves or entities in a narrative, and speculates that humans overcome the limitation through foveal eye movements, a form of "physical CoT."

Real-world applications:

• Embodied AI and robotics — agents that must maintain object identity through occlusion, manipulation, and motion.
• Game-playing agents — card games and board games where hidden state must be tracked from observed moves.
• Video surveillance and sports analysis — following specific individuals or objects through crowded, changing scenes.
• Autonomous driving and traffic reasoning — maintaining identity of vehicles and pedestrians across frames.

Industry relevance. The result is directly actionable for teams building video-capable assistants: adding grounded, timestamped trajectory output as an intermediate reasoning step — rather than a final-answer-only prompt — appears to be what separates chance-level performance from over 90% accuracy, and the alignment step costs only minutes of single-GPU training.

Future Directions

• Generalize beyond location-determined answers. VET-Bench is a simplified setting where the answer is fully determined by the terminal coordinate in the generated SGCoT. Real scenarios may require resolving general referring expressions such as "Which cup contains the ball at the end of the video, from the person's point of view?", which needs additional visual perception in the final frames.
• Handle harder physical conditions. The current analysis assumes localization and continuity conditions. Real tracking involves objects moving in close proximity, overlapping, motion blur, and occlusion — which may require stronger physical priors or world models.
• Reduce residual SGCoT errors. Molmo2-SGCoT still occasionally misidentifies visually identical objects, producing abrupt "jumps" in the output trajectory and wrong terminal locations.
• Understand why fine-grained grounding helps. The paper attributes SGCoT's success to aligning when an event occurs (discrete timestamps) with where each entity is (fine-grained coordinates), while coarse descriptive CoTs suffer temporal misalignment. Testing this explanation more broadly across video tasks is an open question.

Target Audience

Researchers and engineers working on video-language models, multimodal reasoning, and chain-of-thought methods; benchmark designers interested in shortcut-resistant evaluation; and theoretically inclined readers interested in the connection between transformer expressivity (TC⁰ vs. NC¹) and the necessity of intermediate computation. Practitioners building embodied AI, game-playing, or video analytics systems that depend on reliable object tracking would also benefit from the concrete recipe in Section 5.

Authors’ abstract

Visual entity tracking is an innate cognitive ability in humans, yet it remains a critical bottleneck for Vision-Language Models (VLMs). This deficit is often obscured in existing video benchmarks by visual shortcuts. We introduce VET-Bench, a synthetic diagnostic testbed featuring visually identical objects that necessitate tracking exclusively through spatiotemporal continuity. Our experiments reveal that current state-of-the-art VLMs perform at or near chance level on VET-Bench, exposing a fundamental limitation: an over-reliance on static frame-level features and a failure to maintain entity representations over time. We provide a theoretical analysis drawing connections to the state-tracking problem, proving that fixed-depth transformer-based VLMs are fundamentally limited in tracking indistinguishable objects without intermediate supervision due to expressivity constraints. To address this, we propose Spatiotemporal Grounded Chain-of-Thought (SGCoT): generating object trajectories as explicit intermediate states. Leveraging Molmo2's object tracking ability, we elicit SGCoT reasoning by fine-tuning on synthesized text-only data for alignment. Our method achieves state-of-the-art accuracy exceeding 90% on VET-Bench, demonstrating that VLMs can reliably solve the video shell-game task end-to-end without external tools. Our code and data are available at https://vetbench.github.io .