💬 NLP

StructAgent: Harness Long-horizon Digital Agents with Unified Causal Structure

StructAgent introduces a state-centered framework that harnesses unified causal structures to manage long-horizon digital agent tasks, significantly improving success rates and generalizability across diverse LLM/VLM backbones and environments by enabling verifiable, evidence-driven progress tracking and recovery.

Original authors: Wenyi Wu, Sibo Zhu, Kun Zhou, Aayush Salvi, Zixuan Song, Biwei Huang

Published 2026-07-14

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Wenyi Wu, Sibo Zhu, Kun Zhou, Aayush Salvi, Zixuan Song, Biwei Huang

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're trying to teach a super-smart robot to do a long, complicated chore, like "Find the photo in my latest email, save it, and set it as your desktop wallpaper." If you just tell the robot to "go do it" and let it chat with itself as it works, things get messy fast. The robot might forget what it just did, get confused by a failed attempt, or think it's finished when it's actually still stuck in the middle of the task. It's like trying to navigate a maze while wearing a blindfold and only remembering the last step you took.

This is the problem the paper StructAgent tries to solve. The authors argue that instead of letting the robot wander through a giant, messy pile of its own past actions (which they call "raw interaction history"), we need to give it a structured, organized notebook to keep track of exactly where it stands.

The Big Idea: A "Truth-Telling" Notebook

The paper proposes a new way to run digital agents called StructAgent. Think of it as giving the robot a special, three-part notebook that it must update before it can move on to the next step. This notebook isn't just a diary; it's a strict, verified record of reality.

What's Left to Do: A list of the current requirements (e.g., "I need to find the email attachment").
What We Know: Useful facts gathered so far (e.g., "The file path is /home/user/pics").
Proof of Work: Verified evidence that a step is actually done (e.g., "I checked the folder, and the image file is definitely there").

The magic isn't just in the notebook; it's in the rules for using it. In most robot systems, if the robot says "I'm done," it's done. In StructAgent, the robot can't just claim victory. It has to hand its work to a Verifier (a strict referee). The Verifier checks the evidence. Only if the Verifier says, "Yes, I see the file, and it matches the rules," does the notebook get updated. If the Verifier says, "Nope, that's not the right file," the notebook stays the same, and the robot has to try again or fix its mistake.

What They Argue Against

The paper explicitly argues against the idea that agents should just keep going based on their "feeling" or a long, unstructured list of everything they've ever done. They show that when tasks get long and complex, this "raw history" approach makes the robot lose its way. The robot gets buried under failed attempts and half-finished jobs, making it impossible to know if it's actually making progress or just spinning its wheels. StructAgent says: "Stop guessing. Stop relying on a messy memory. Use a verified, structured state instead."

The Results: Does It Actually Work?

The authors didn't just dream this up; they tested it on real computer tasks. They ran experiments on a benchmark called OSWorld-Verified, which tests how well agents can use real desktop applications (like email, spreadsheets, and photo editors).

Here is what they found, with the exact numbers from their study:

When they used a smaller AI model called Qwen3.5-9B, the success rate jumped from 27.0% (without StructAgent) to 46.9% (with StructAgent). That's a huge improvement!
With a slightly bigger model, Qwen3.5-27B, the success rate went from 31.6% to 62.2%.
When they used their strongest open-source model, MiniMax-M3, StructAgent helped it reach a 78.9% success rate. This is the highest score they found for any open-source method on this specific test.

They also tried this system in a completely different world: the video game Minecraft. Instead of checking desktop files, the "Verifier" checked the player's inventory. Even with this totally different environment, the system worked, showing that the idea of a "verified notebook" is flexible.

The "Gotchas" and Limits

The paper is careful to say this isn't a magic wand that solves everything.

It's not perfect yet: Even with StructAgent, some tasks still fail. When they looked at the failures, they found that about 33% were because the robot (the "Actor") messed up the action, 30% were because the planner got confused, and another 30% were because the verifier missed something.
It depends on the task: The system works best when there is clear, checkable proof (like a file existing on a computer). It struggles a bit more with tasks that rely heavily on visual details (like "make the text look pretty") where there isn't a simple file to check.
It's a framework, not a single model: The paper shows that this structure helps many different AI models. It's not that they built a new super-brain; they built a better way for any brain to organize its work.

The Bottom Line

The paper suggests that to make AI agents reliable for long, complicated jobs, we need to stop treating them like free-flowing chatbots and start treating them like careful project managers with a strict, verified checklist. By forcing the agent to prove its progress before moving forward, StructAgent makes these digital helpers much more reliable, transparent, and capable of handling the long, messy tasks of the real world. It's a step toward agents that don't just try to do things, but actually know they've done them.

Technical Summary: StructAgent

Problem Statement

Recent advances in Large Language Models (LLMs) and Vision-Language Models (VLMs) have enabled digital agents to perform computer-use tasks. However, real-world tasks are often long-horizon, involving complex workflows with evolving contexts. As agents execute these tasks, they accumulate a raw interaction history containing factual information, intermediate edits, failed attempts, and partially completed executions.

The core challenge identified is that existing agents typically operate over this raw, unstructured history. As the context grows, critical information becomes buried, and the current task state becomes ambiguous. This lack of structure makes it difficult for agents to:

Maintain a clear causal understanding of task progress.
Promptly detect abnormal states or intermediate errors.
Perform accurate planning and execution.
Recover from failures without replaying the entire history.

Consequently, reliable long-horizon execution is limited because agents struggle to distinguish valid progress from noise or self-reported but unverified completion claims.

Methodology: StructAgent

To address these challenges, the authors propose StructAgent, a state-centered framework that explicitly structures both the agent's state and workflow around a unified causal representation of task progress. The framework consists of two complementary components:

1. Unified Agent State

Instead of inferring progress from raw trajectories, StructAgent maintains a compact, typed, and auditable state $s_t$ that serves as a shared interface for all modules. The state is defined as:
$s_t = (s_t^{req}, s_t^{val}, s_t^{ver})$

$s_t^{req}$ (Requirements): Stores the requirements of the current subgoal, specifying what must be achieved and what the verifier should check.
$s_t^{val}$ (Useful Values): Stores persistent, useful values discovered during execution (e.g., file paths, URLs, selected entities).
$s_t^{ver}$ (Verified Evidences): Stores evidence collected by the verifier during the probing process, allowing for auditing and reuse.

Causality-Oriented Transitions: State transitions are strictly controlled. A requirement's status ( $\sigma_{i,t}$ ) can only change to VERIFIED or INVALIDATED based on a verifier-backed decision. This ensures that progress updates are grounded in verifiable evidence rather than the agent's self-report.

2. Structured Workflow

The framework operates on a fixed execution loop: Planner $\rightarrow$ Actor $\rightarrow$ Verifier $\rightarrow$ State Update.

Planner: Reads the current state to select the next subgoal ( $g_t$ ). It does not need to reconstruct progress from raw history.
Actor: Attempts to execute the subgoal in the environment, producing an action trace ( $\tau_t$ ).
Verifier: Checks if the attempted subgoal produced valid progress using structured and agentic probing (e.g., checking files, shell outputs, application states). It outputs a decision ( $d_t$ ) to verify, invalidate, or leave the state unchanged.
Memory: Provides state-conditioned support, suggesting subgoals or action patterns based on reusable experience.

Key Capabilities Enabled

Progress Checkpointing: The state history serves as a self-contained, human-readable snapshot, allowing agents to resume execution without replaying the full interaction history.
Targeted Failure Recovery: When progress stalls, the system diagnoses the issue using verified evidences (e.g., lack of evidence, conflicting requirements) and selects specific interventions (replanning, retrying, or human takeover) rather than generic retries.
Tool-Supported Execution: Recurring patterns are summarized into reusable procedures. The actor can invoke these tools, but outcomes are only committed to the state if verified.

Key Contributions

Unified State: Introduction of a compact, typed, and auditable state representation that provides planning, acting, and verification with a shared view of task progress.
Structured Workflow: Design of a planning-acting-verification loop where only verifier-backed decisions can commit, preserve, or invalidate progress.
Broad Empirical Validation: Demonstration that the framework improves diverse LLM and VLM backbones on long-horizon computer-use tasks and generalizes across domains (desktop, web, and Minecraft).

Experimental Results

OSWorld-Verified (Desktop)

The framework was evaluated on OSWorld-Verified, a benchmark for long-horizon computer use. StructAgent consistently improved performance across various backbones:

Qwen3.5-9B: Improved success rate from 27.0% (single model) to 46.9%.
Qwen3.5-27B: Improved success rate from 31.6% to 62.2%.
MiniMax-M3: Achieved a new open-source state-of-the-art of 78.9%, surpassing the single-model baseline of 75.2%.
Domain Performance: Gains were most pronounced in "Office" tasks (spreadsheets, documents) where durable intermediate states and file-based checks are available. Cross-application tasks remained challenging but saw improvements with stronger backbones.

Generalization

Web (Mind2Web): StructAgent generalized to web environments, achieving 47.3% (Qwen3.5-9B) and 52.3% (Qwen3.5-27B), outperforming reproduced baselines. Gains were strongest in information-seeking tasks where progress can be tracked via URLs and page states.
Minecraft: The framework was instantiated in Minecraft by replacing desktop evidence sources with inventory-based verification. It achieved a 76% task-weighted average success rate (vs. 59% for Optimus-1), demonstrating that the state-update discipline is domain-agnostic.

Analysis

Verification Quality: Structured verification improved recall from 0.67 to 0.81 compared to visual-only verification, primarily by recovering true completions that were invisible in final screenshots (e.g., file existence, command outputs).
Failure Modes: Analysis of failed trajectories revealed that errors are distributed across the Planner (30%), Verifier (30%), and Actor (33%), indicating that long-horizon reliability requires system-wide improvements rather than just scaling the actor.

Significance and Claims

The paper argues that the purpose of abstraction is to create a semantic level where one can be "absolutely precise" (citing Edsger W. Dijkstra). StructAgent achieves this by moving away from continuous generation over noisy histories toward an explicit causal structure.

The authors claim that:

Transparency and Control: By enforcing verifier-backed state transitions, the agent's progress becomes transparent, auditable, and controllable.
Robustness: The framework enables targeted failure recovery and evidence-driven task completion, reducing reliance on brittle self-reported "DONE" claims.
Generality: The state-centered paradigm is not tied to specific model scales or desktop environments; it effectively generalizes to web browsers and game environments (Minecraft) by adapting the evidence source while maintaining the same structural workflow.

The work positions itself as a systems-level solution to long-horizon reliability, suggesting that structuring the task progress itself is as critical as improving the underlying language models.