Skip to content

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

🕒 Published (v1): 2026-07-13 10:48 UTC · Source: Arxiv · link

Why this paper was selected

Causal structure for long-horizon digital agents; addresses context drift in real-world computer-use tasks

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

StructAgent is a state-centered framework for long-horizon computer-use agents that replaces raw interaction history with a compact, typed, causally-structured unified state and enforces progress only through verifier-backed state transitions. It achieves a new open-source state-of-the-art of 78.9% on OSWorld-Verified with MiniMax-M3 and generalizes to web and Minecraft environments.

Problem

Long-horizon digital agents accumulate noisy interaction histories mixing failed attempts, transient observations, and unsupported completion claims, making it increasingly difficult to maintain a coherent causal understanding of task progress. Existing agents operating over raw trajectories cannot reliably detect false progress commits, recover from failures, or verify intermediate task state, which caps reliable execution on multi-step computer-use workflows.

Method

StructAgent introduces two coupled components:

Unified Agent State \(s_t = (s_t^{\text{req}}, s_t^{\text{val}}, s_t^{\text{ver}})\) where \(s_t^{\text{req}}\) holds current requirements with statuses \(\sigma_{i,t} \in \{\texttt{PENDING}, \texttt{VERIFIED}, \texttt{INVALIDATED}\}\), \(s_t^{\text{val}}\) holds discovered values (file paths, URLs, entities), and \(s_t^{\text{ver}}\) holds verified evidences. Only verifier-backed decisions \(d_t\) can drive state transitions: $\(\sigma_{i,t+1} = \begin{cases} \texttt{VERIFIED} & \text{if } d_t \text{ verifies } r_i \\ \texttt{INVALIDATED} & \text{if } d_t \text{ invalidates } r_i \\ \sigma_{i,t} & \text{otherwise} \end{cases}\)$

Structured Workflow runs a fixed loop: \(s_t \xrightarrow{\text{Planner}} g_t \xrightarrow{\text{Actor}} \tau_t \xrightarrow{\text{Verifier}} d_t \xrightarrow{\text{Update}} s_{t+1}\). The verifier uses structured agentic probing (file checks, shell probes, accessibility queries, vision checks) rather than screenshot-only judgment. Planner/actor completion claims are proposals; only the verifier can commit progress. Built on this loop: progress checkpointing via state history, evidence-driven failure recovery (targeted re-planning based on \(s_t^{\text{ver}}\) diagnosis), and tool-supported execution that exposes reusable procedures without bypassing verification.

Key Contributions

  • A typed, auditable unified state schema shared across planner, actor, and verifier, retaining only minimum-sufficient causal information.
  • A causality-enforcing planning-acting-verification loop where the state advances only on verifier-backed decisions, preventing false progress commits.
  • Evidence-driven failure recovery that diagnoses failure mode (insufficient evidence, strategy conflict, environment block) and inserts targeted interventions as new subgoals.
  • Structured verification that combines latent evidence sources (files, shell outputs, URLs, application state) with visual verification, raising recall from 0.67 to 0.81 at the DONE gate.
  • Cross-domain generalization demonstrated on desktop GUI (OSWorld), web (Mind2Web), and Minecraft (inventory-based verification).

Results

  • OSWorld-Verified: StructAgent (MiniMax-M3) achieves 78.9%, new open-source SOTA; Qwen3.5-9B: 27.0% → 46.9%; Qwen3.5-27B: 31.6% → 62.2% (all vs. single-model baselines under matched runner settings).
  • In controlled comparisons against Agent S3, OS-Symphony, VLAA-GUI (all self-run with same backbone): StructAgent leads in Overall for both 9B and 27B groups; Office gains are largest (e.g., Qwen3.5-27B Office: 26.1% single-model → 71.7%).
  • Cross-application tasks remain hardest; Qwen3.5-9B still trails OS-Symphony on Multi-Apps (27.5% vs. 32.6%).
  • Mind2Web (web): Qwen3.5-9B: 47.3% overall (vs. 46.0% best reproduced baseline); Qwen3.5-27B: 52.3% (vs. 51.7%); gains concentrated in information-seeking tasks.
  • Minecraft: StructAgent 76% average vs. Optimus-1 59%; gains on Iron (65% vs. 47%), Golden (86% vs. 9%), Redstone (57% vs. 25%); Optimus-1 leads on Stone (92% vs. 70%).
  • Structured verifier is correct in 63% of disagreements with visual-only verifier; visual-only correct in 31% (6% unclear) across 100 reviewed intermediate cases.
  • Behavior Best-of-N (3–5 rollouts) provides additional gains as an optional test-time scaling procedure.

Limitations

  • Cross-application tasks remain a bottleneck for smaller backbones (9B) even with structured state, indicating complex dependency reasoning is not solved by state structure alone.
  • Verification quality is domain-dependent: Calc, Writer, Impress, and browser/email tasks embed success in GUI layout, where structured probes yield less advantage and visual verification remains necessary.
  • Dynamic web content (pop-ups, transactional widgets, site-specific flows) creates action-grounding bottlenecks not addressed by state tracking.
  • On Minecraft Stone tasks, StructAgent underperforms Optimus-1 and is sometimes less step-efficient even when successful, suggesting domain-specific actor efficiency is a separate bottleneck.
  • Structured evidence probes can become stale or use proxy matches, as surfaced in verifier disagreement analysis; a hybrid verifier with reliable fallback to visual checks is identified as future work.

Relevance to Agentic AI / LLM Agents

StructAgent directly addresses the core reliability problem in long-horizon LLM agent execution: uncontrolled context growth and unverified progress claims that cause cascading failures. By formalizing agent state as a typed causal object and making verification the sole gatekeeper for state transitions, it provides a principled alternative to the dominant pattern of prompting agents to self-report task completion from raw trajectory history. The structured workflow pattern — planner proposes, actor attempts, verifier commits — is a reusable design primitive applicable across GUI, web, and game environments, suggesting broad applicability to agentic scaffolding beyond any single benchmark. The evidence that smaller models (9B) gain proportionally more from structure than larger models is a practically important finding for researchers designing agents under compute constraints.