CoSPlan: Corrective Sequential Planning via Scene Graph Incremental Updates

AI summary

Overview

Research area: Computer vision and vision-language model (VLM) evaluation, specifically multimodal sequential planning and error correction.

Technical level: Intermediate. Readers should be familiar with VLMs, multiple-choice benchmark evaluation, chain-of-thought prompting, and scene graphs.

Scope: The paper introduces the CoSPlan benchmark for error-prone sequential visual planning and proposes SGI (Scene Graph Incremental update), a training-free method that refines text-based scene graphs step by step.

What This Paper Is About

VLMs have become good at step-by-step planning when the problem is expressed in text, but visual decision-making is far less explored. The authors build a benchmark where a model sees an initial scene, a goal scene, and a partial list of already-executed actions that contains a deliberately wrong step; the model must identify that error and choose the remaining actions that actually reach the goal. They then propose a prompting method that turns images into text scene graphs and updates them one action at a time, so the model reasons over explicit intermediate states instead of guessing.

Key Contributions

1. CoSPlan benchmark: Described as the first multimodal benchmark with temporal sequences of actions spanning the vision and language domain, designed to evaluate VLM visual reasoning in error-prone scenarios. It contains four planning tasks and tests two abilities: Error Detection and Step Completion.
2. VLM evaluation and failure analysis: The authors evaluate GPT-5.1, GPT-4o, CoG-VLM, Intern-VLM 2, Intern-VLM 3, Janus-Pro-7B, Llama3-8B, Qwen2-VL-8B, Qwen3-VL-8B (plus Gemini-3-pro and Gemini-2.5-pro in reported tables), revealing weaknesses in error handling, vision-based sequence planning, and scene understanding.
3. SGI (Scene Graph Incremental update): A training-free technique that converts images into textual scene graphs and refines them after every action, enabling step-by-step reasoning through iterative scene-graph refinement.
4. Generalization evidence: SGI is also tested on VQA-style tasks from SpatialEval and on the text-only PlanBench benchmark (Blocksworld Task 8), where it outperforms the vanilla, CoT, and non-incremental SG variants reported.

Main Findings

• CoSPlan tasks and sizes: Maze-E (navigation / path planning, 5,000 samples, synthetic), Blocks-World-E (block re-arrangement, 5,000, synthetic), Shuffle-E (image re-construction, 1,000, ImageNet), Robo-VQA-E (real-world re-organization, 350, ROM). Average initial context lengths are 2.0, 2.0, 3.7 and 5.5 respectively; average remaining steps are 4.6, 3.8, 7.1 and 4.1.
• Near-random VLM performance: Lightweight open-source models perform near or below random chance. Step Completion random accuracy is 20% (1 of 5 options); Error Detection random accuracy is E[1/(initial context length + 1)]. Llama3-8B, CoG-VLM, Janus-pro-7B, Qwen2-VL-8B and Qwen3-VL-8B hover close to these floors on most tasks.
• Stronger models still fail on errors: GPT-4o and GPT-5.1 "make reasonably informed decisions" but fail to reliably use visual context to recover correct plans. Gemini-3-pro is the strongest reported model, reaching 67.3% (Robo-VQA-E), 61.6% (Shuffle-E), 70.4% (Maze-E) and 71.3% (Blocks-World-E) on Step Completion with SG.
• SG beats CoT, which beats vanilla: Scene Graphs outperform Chain-of-Thought, which in turn outperforms vanilla input in most cases, highlighting the need for structured representations.
• SGI improvement: SGI improves over vanilla SG by an average of roughly 4.4%. For Step Completion, improvements reach up to 10.3%, 4.8% and 10.0% for Intern-VLM 2, Intern-VLM 3 and GPT-4o; for Error Detection, average gains are 4.1%, 1.7% and 9.2% respectively. One reported case: Gemini-2.5-pro on Blocks-World-E improves from 67% (CoT) to 70% (SG) to 71.5% (SGI).
• Fewer cheating instances with SGI: Intern-VLM-2 (43% to 39%), Intern-VLM-3 (41% to 35%), Qwen-3 (35% to 30%), CoG-VLM (27% to 23%).
• Errors are the real difficulty: VLMs excel in error-free settings (GPT-4o near-perfect) but struggle on error-prone ones, suggesting some models simply pick the option that describes the target scene.
• In-context errors are harder: Models struggle more when the erroneous action involves plausible objects already in the scene than when it involves random out-of-context objects.
• Vision lags text: Describing the same tasks in text-only format significantly boosts reasoning accuracy, exposing an inability to iterate over visual steps.
• MCQ behavior: Accuracy drops as the number of MCQ options grows; accuracy stays nearly constant as more steps toward the goal are revealed in the options. Janus-pro-7B selects "option A" 94% of the time in one analysis, and Janus and Qwen 2 select option A 90%+ and 75%+ times elsewhere.
• Longer initial context helps: Model accuracy correlates positively with the number of already-performed steps in the initial context.
• Scene graph quality matters: With ground-truth "Oracle" scene graphs, performance improves but still stays below text-only reasoning, indicating that simulating visual steps is inherently difficult. SGI is also more robust than SG under noisy scene graphs for Qwen-3.
• Human baselines: Step Completion — Robo-VQA-E 42.1, Shuffle-E 53.7, Maze-E 95.7, Blocks-World-E 81.8. Error Detection — Robo-VQA-E 60.0, Maze-E 90.0, Blocks-World-E 80.0. Difficulty order by human scores: Robo-VQA-E > Shuffle-E > Blocks-World-E > Maze-E.
• Generalization: On PlanBench Blocksworld Task 8, Qwen2-VL-8B scores 13.8 (vanilla), 14.1 (CoT), 13.9 (SG) and 14.7 (SGI). On SpatialEval-style VQA, SGI outperforms CoT and SG for Intern-VLM on all three reported sub-tasks.
• Visual simulation failure: Proprietary models Grok, Claude and ChatGPT fail to generate correct intermediate states on Blocks-World-E (Grok misplaces the red block; Claude moves the purple block left instead of right; ChatGPT fails to generate correct steps).

Methodology in Plain English

The authors created four puzzle-style datasets, each containing a starting state, a goal state, and a short list of actions that have supposedly already been taken. One of those actions is deliberately wrong, either violating the environment's rules or being sub-optimal.

Each question is multiple choice. For Error Detection, the already-performed actions are the options, plus a "none of the above" choice. For Step Completion, the model picks one of five sets of remaining actions. To stop models from simply choosing whichever option looks most like the goal image, the authors add a distractor option that also reaches the goal but skips the required error correction.

They test three prompting modes: vanilla (raw images and text), Chain-of-Thought (identify constraints, walk through each action, verify), and Scene Graphs (query the VLM to describe the initial and goal scenes as nodes, edges and attributes).

Their proposed method, SGI, extends the scene graph idea. It first asks the model to build a scene graph for the initial image and one for the goal image. It then feeds each already-performed action to the model one by one and asks it to "simulate" that action, incrementally modifying nodes, attributes and edges. This produces an intermediate scene graph reflecting the model's current context. Each MCQ option is then simulated separately from that context, producing a candidate final scene graph. Finally, the model scores the similarity between each candidate graph and the goal graph (0-100), and the highest-scoring option is selected. Because scene graphs are model-specific internal representations, comparison is done via model-as-a-judge rather than a universal metric.

The authors note the cost: SGI requires one VLM call per step, but iterating over text-based scene graphs is far cheaper than synthesizing intermediate images.

Why This Matters

Impact on research: CoSPlan argues that a single deliberate error is enough to collapse VLM planning accuracy, and that current evaluation of "reasoning" models often hides this because error-free tasks are much easier. It also provides a concrete, training-free baseline (SGI) that other researchers can compare against, and it frames a distinction between text-domain and visual-domain reasoning that is testable.

Real-world applications (as framed by the paper and its task design):

• Robotics manipulation and object re-organization, where action sequences must obey physical constraints and a wrong step must be caught before execution continues.
• Autonomous navigation and path planning, where a single incorrect move (out of bounds, into an obstacle, or diagonal) invalidates the remaining plan.
• Embodied and assistive agents that receive partially executed instructions and must notice and repair human or system errors.
• Evaluation pipelines for multimodal agents, where benchmarks need safeguards so that a model cannot "cheat" by matching the final state without reasoning.

Industry relevance: Model developers evaluating the robustness of VLM planning can use the released dataset and benchmark directly. SGI is training-free, so it can be layered onto existing models without fine-tuning, which lowers the barrier for deployment. The paper also reports that Microsoft's AFMR grant program supported the work, indicating interest from commercial research labs.

Future Directions

• Multi-error settings: The current setup isolates exactly one erroneous step per sequence, which the authors call "somewhat artificial." Handling multiple cascading errors is noted as requiring exponential complexity and is limited by automation.
• Video-based planning: The current setup uses static image pairs; extending CoSPlan to video is listed as a natural next direction.
• Interactive settings: Having agents actually execute actions and observe updated states, rather than selecting from pre-written options, is proposed as a further extension.
• Scene graph perception quality: With ground-truth scene graphs, performance still trails text-only reasoning, raising the open question of how much of the failure is perception versus simulation.
• Automated problem generation: The authors note that generating multi-error problems is limited by automation, since tools such as GPT-4o are not equipped to handle even one error reliably.

Target Audience

Researchers and practitioners working on vision-language models, multimodal reasoning, and sequential planning benchmarks; roboticists and embodied-AI engineers who need agents to detect and recover from bad intermediate actions; and evaluation teams at model labs who want a benchmark that resists shortcut solutions. Readers with some background in VLM prompting and benchmark design will get the most from it, though the task framing and results are described in accessible terms.

Authors’ abstract

Vision Language Models (VLMs) have shown promising planning capabilities, yet their success remains confined to the text domain, leaving visual decision-making relatively underexplored. Addressing this gap, we introduce Corrective Sequence Planning (CoSPlan) benchmark, where VLMs must plan a sequence of visual actions from an initial scene to a target scene. CoSPlan evaluates models on their ability to imagine and execute a coherent set of visual steps required to reach the goal (Step Completion). To prevent any shortcuts that simply describe the final scene, we introduce an erroneous action in decision-making, which must be detected (Error Detection) and corrected to reach the goal, enabling a deeper understanding of the task. CoSPlan spans across 4 tasks: maze navigation, block re-arrangement, image reconstruction, and object re-organization. Despite using advanced reasoning strategies such as Chain-of-Thought and Scene Graphs, VLMs struggle on CoSPlan, while still showing promising performance in the text domain. Addressing this, we propose Scene Graph Incremental updates (SGI), a novel training-free method to transform images into `textual' scene graphs, enabling step-by-step reasoning through iterative scene graph refinement. SGI yields an average of ~4.4% improvement on CoSPlan w/ generalization on PlanBench and VQA. Link for solving puzzles on the project page.