💻 computer science

CoSPlan: Corrective Sequential Planning via Scene Graph Incremental Updates

This paper introduces CoSPlan, a benchmark for evaluating Vision Language Models' visual sequential planning capabilities through tasks requiring step completion and error correction, and proposes Scene Graph Incremental (SGI), a training-free method that improves performance by enabling iterative reasoning through textual scene graph updates.

Original authors: Shresth Grover, Priyank Pathak, Akash Kumar, Yogesh S Rawat

Published 2026-06-30

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Shresth Grover, Priyank Pathak, Akash Kumar, Yogesh S Rawat

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

The Big Idea: The "Broken GPS" Problem

Imagine you are giving a robot a set of instructions to navigate a maze or rearrange furniture. You say, "Start at the door, walk to the kitchen, then put the vase on the table."

Current AI models (called Vision-Language Models or VLMs) are great at reading these instructions and talking about them. But when you ask them to actually visualize the steps and fix a mistake, they often fail.

The paper introduces a new test called CoSPlan (Corrective Sequence Planning). Think of it as a "spot the error" game for AI.

The Setup:

The Scene: You show the AI a starting picture (e.g., a messy room) and a goal picture (e.g., a clean room).
The Story: You tell the AI a story of what has already happened. "First, we picked up the cup. Then, we dropped it on the floor."
The Trap: The story contains a mistake. Maybe the AI was told to walk through a wall, or put a heavy box on a wobbly shelf.
The Test: The AI must do two things:
- Detect the Error: Realize, "Wait, you can't walk through a wall!"
- Fix the Plan: Figure out the correct next steps to still reach the goal, despite the earlier mistake.

Why This is Hard for AI

The authors found that even very smart AI models (like GPT-4o) struggle with this. They are like a student who can recite the rules of chess perfectly but freezes when asked to play a game where the opponent made a weird move.

The "Text vs. Vision" Gap: These models are great at planning in their heads using words (text). But when they have to "see" the steps in their mind's eye (vision), they get lost.
The "Shortcut" Problem: Many models try to cheat. Instead of figuring out the steps, they just look at the final goal picture and say, "Oh, I need to get there," without actually checking if their previous steps made sense. The CoSPlan test is designed to catch this cheating by adding a "distractor" option that looks like the goal but ignores the mistake.

The Four Games They Played

To test this, the researchers created four different types of puzzles:

Maze-E: A robot trying to walk through a maze. The error might be walking into a wall.
Blocks-World-E: Stacking blocks like Jenga. The error might be trying to put a block in mid-air.
Shuffle-E: A jigsaw puzzle where pieces are swapped. The error is swapping the wrong pieces.
Robo-VQA-E: Real-world photos of objects (like bowls and fruit). The error might be putting fruit inside a bowl that is already full.

The Solution: "Scene Graph Incremental Updates" (SGI)

Since the AI struggles to imagine the whole future at once, the authors proposed a new method called SGI.

The Analogy: The "Mental Whiteboard"
Imagine you are trying to solve a complex puzzle, but instead of trying to hold the whole picture in your head, you use a whiteboard.

Step 1: You draw the starting scene on the whiteboard (a "Scene Graph").
Step 2: You take the first action (e.g., "Move the cup"). You physically erase the old spot on the whiteboard and draw the cup in the new spot.
Step 3: You do this for every single step, one by one.
Step 4: If you realize you made a mistake (e.g., "Oops, I moved the cup into the wall"), you stop, erase the wall collision, and draw the correct move.

Why it works:
Instead of asking the AI to "imagine the whole future" in one giant leap (which causes it to hallucinate or cheat), SGI forces it to update its "mental whiteboard" step-by-step. It turns a hard visual problem into a series of smaller, manageable text-based updates.

The Results

The Problem: Without help, most AI models performed no better than random guessing on these error-correction tasks. They couldn't "see" the mistake or fix the plan.
The Fix: When the researchers used the SGI method (the step-by-step whiteboard approach), the AI's performance jumped significantly (about 4.4% on average, which is huge in this field).
The Takeaway: AI is getting better at "thinking" in words, but it still needs help to "think" in pictures. By breaking visual planning down into small, incremental updates, we can make these models much more reliable at fixing their own mistakes.

Summary

The paper says: "AI is good at reading instructions but bad at visualizing the consequences of a mistake. We built a test (CoSPlan) to prove this, and we found a way (SGI) to help the AI fix its plans by updating its mental picture one tiny step at a time."

Technical Summary: CoSPlan: Corrective Sequence Planning via Scene Graph Incremental Updates

1. Problem Definition

Vision Language Models (VLMs) have demonstrated significant capabilities in textual reasoning and planning, particularly when utilizing techniques like Chain-of-Thought (CoT). However, their ability to perform sequential planning within the visual domain remains underexplored. Existing benchmarks often focus on static visual puzzles or assume ideal, error-free instructions, failing to capture the complexities of real-world decision-making where agents must navigate physical constraints and recover from execution errors.

The paper identifies a critical gap: VLMs struggle to sustain coherent multi-step visual reasoning, especially when required to detect and correct erroneous steps within a sequence. Current models tend to compress reasoning from an initial state to a final goal into a single step, implicitly simulating long action sequences without explicit intermediate representations. This leads to failures in "Step Completion" (planning remaining actions) and "Error Detection" (identifying where a sequence went wrong), often resulting in performance near random guessing when errors are introduced.

To address this, the authors introduce CoSPlan (Corrective Sequence Planning), a multimodal benchmark designed to evaluate VLMs on their ability to navigate a sequence of visual actions from an initial scene ( $I_0$ ) to a target scene ( $I_g$ ), given an initial context that contains at least one intentional, non-optimal, or erroneous action ( $A_E$ ).

2. Methodology

2.1 The CoSPlan Benchmark

CoSPlan evaluates models on two distinct tasks:

Error Detection: Identifying the specific erroneous step within the provided initial context (or determining if no error exists).
Step Completion: Selecting the correct sequence of remaining actions to reach the goal state, effectively correcting the trajectory established by the error.

The benchmark comprises four distinct tasks, each featuring intentional sub-optimal errors (except for one specific case noted below):

Maze-E: Navigation tasks where the agent must move from a start cell to a goal cell while avoiding obstacles. Errors include moving out of bounds, hitting obstacles, or making illegal diagonal moves.
Blocks-World-E: Block rearrangement tasks where the goal is to transform an initial stack configuration to a target one. Errors involve physically impossible moves (e.g., moving non-top blocks, floating blocks) or inefficient stacking.
Shuffle-E: Image reconstruction tasks where shuffled image patches must be swapped to restore the original image. Note: Due to the cascading nature of errors in this task, only a single error is introduced, but it is noted that this creates a unique challenge for uniformity.
Robo-VQA-E: Real-world object re-organization tasks using curated image-text pairs. Errors include suboptimal placements, arbitrary interactions with non-existent objects, or invalid actions (e.g., opening an already open door).

Design Safeguards: To prevent models from "cheating" by simply selecting an option that visually matches the final goal state ( $I_g$ ) without reasoning through the constraints, CoSPlan includes distractor options. These distractors reach the final state but fail to correct the specific error in the initial context, forcing the model to understand the scene's history and constraints.

2.2 Proposed Solution: Scene Graph Incremental Updates (SGI)

Recognizing that standard CoT and static Scene Graph (SG) approaches struggle with long-horizon visual reasoning, the authors propose SGI, a training-free method.

Core Concept: Instead of reasoning directly on images or compressing the entire sequence into a single step, SGI transforms images into textual Scene Graphs. It then performs iterative, step-by-step reasoning in the text space.
Algorithm:
1. Vanilla Scene Graphs: The VLM generates an initial Scene Graph ( $S_0$ ) from $I_0$ and a goal Scene Graph ( $S_g$ ) from $I_g$ .
2. Incremental Update: Starting from $S_0$ , the model is prompted to "simulate" each action in the initial context (including the error) to update the graph incrementally, producing an intermediate state graph ( $S_c$ ).
3. Option Simulation: For each multiple-choice option (representing a potential future sequence), the model simulates the actions starting from $S_c$ , generating a hypothetical final graph ( $S_m$ ) for that option.
4. Similarity Comparison: The model compares each hypothetical graph ( $S_m$ ) against the goal graph ( $S_g$ ) to determine which option best aligns with the goal constraints, effectively selecting the path that corrects the error.

This approach decomposes the reasoning burden, allowing the model to explicitly track evolving states rather than relying on implicit visualization.

3. Key Contributions

CoSPlan Benchmark: The first multimodal benchmark to evaluate VLMs on sequential planning in the vision-language domain under error-prone conditions. It uniquely combines temporal action sequences with the requirement for error detection and correction across four diverse task types.
Empirical Analysis of VLM Weaknesses: The paper provides a rigorous evaluation of state-of-the-art VLMs (including GPT-4o, GPT-5.1, Intern-VLM, Qwen, and others). It reveals that even advanced models perform near random chance on these tasks, highlighting a significant inability to visualize intermediate steps and handle in-context errors.
SGI Method: A novel, training-free technique that leverages Scene Graphs for incremental updates. SGI significantly improves performance over vanilla Scene Graphs and Chain-of-Thought baselines by explicitly modeling intermediate states.

4. Results

Baseline Performance: Vanilla VLMs and those using standard CoT or static SGs perform poorly, often near or below random guessing (e.g., ~20% accuracy on 5-option MCQs). This indicates a fundamental struggle with visual sequence planning when errors are present.
SGI Performance: The SGI method yields a consistent improvement across all tasks.
- Step Completion: SGI achieves an average improvement of ~4.4% over standard Scene Graph methods, with gains reaching up to 10.3% for specific models like Intern-VLM 2.
- Error Detection: SGI improves error detection accuracy by an average of 4.1% to 9.2% depending on the model.
- Generalization: SGI demonstrates robustness on external datasets, showing improvements on VQA (Visual Question Answering) tasks and the PlanBench (text-based planning) benchmark, suggesting the method's utility extends beyond the specific CoSPlan tasks.
Error Sensitivity: The study shows that VLMs excel in error-free settings but degrade significantly when a single error is introduced. Furthermore, performance drops as the number of MCQ options increases, suggesting a reliance on option bias rather than genuine reasoning.

5. Significance and Claims

The paper claims that CoSPlan exposes a critical limitation in current VLMs: while they may possess strong zero-shot generalization in text or static image understanding, they lack the coherent multi-step visual reasoning required for real-world decision-making where errors occur.

The significance of the work lies in:

Realism: By introducing errors, CoSPlan mimics realistic deployment scenarios (e.g., robotics, autonomous navigation) where agents must recover from suboptimal actions, a capability currently missing in most benchmarks.
Methodological Shift: The success of SGI suggests that transforming visual reasoning into iterative textual reasoning (via Scene Graphs) is a viable path to overcoming the "long-horizon" reasoning gap in VLMs, without requiring extensive retraining.
Diagnostic Value: The benchmark serves as a rigorous test to distinguish between models that merely "hallucinate" a final state and those that genuinely understand the causal relationships and constraints of a visual sequence.

The authors conclude that while SGI substantially boosts performance, the near-random performance of many models even with SGI highlights that simulating visual steps remains an inherently difficult challenge for current architectures, necessitating further research into robust visual reasoning mechanisms.