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 VLM digital agents; directly relevant to agent harness design

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 agentic framework that introduces a unified causal state and a verifier-gated workflow to address brittleness in long-horizon computer-use tasks. By ensuring only verifier-backed decisions can commit or revoke task progress, it transforms noisy VLM interaction histories into compact, auditable state representations. Applied to open VLM backbones, it achieves new open-source SOTA on OSWorld-Verified (78.9% with MiniMax-M3) and generalizes to web and Minecraft environments.

Problem

Existing digital agents operate over raw, growing interaction histories that accumulate failed attempts, intermediate edits, and partial results. This makes task state ambiguous, impedes error detection, and causes unreliable DONE claims—particularly in long-horizon workflows where VLMs lose track of causal dependencies across many steps. No prior framework enforces that progress updates be grounded in verified evidence rather than agent self-reports.

Method

StructAgent decomposes agent context into a typed, three-part unified state:

\[s_t = \left(s_t^{req},\; s_t^{val},\; s_t^{ver}\right)\]

where \(s_t^{req}\) holds current subgoal requirements with statuses \(\sigma_{i,t} \in \{\texttt{PENDING}, \texttt{VERIFIED}, \texttt{INVALIDATED}\}\), \(s_t^{val}\) holds discovered values (file paths, URLs, entities), and \(s_t^{ver}\) holds verified evidences supporting past progress.

The structured workflow is:

\[s_t \xrightarrow{\text{Planner}} g_t \xrightarrow{\text{Actor}} \tau_t \xrightarrow{\text{Verifier}} d_t \xrightarrow{\text{Update}} s_{t+1}\]

State transitions are causality-oriented: neither the planner nor actor can commit progress—only a verifier-backed decision \(d_t\) can advance or invalidate requirements. The verifier uses structured and agentic probing (file checks, shell probes, accessibility trees, vision checks) rather than screenshot-only judgment. This design enables: (1) progress checkpointing and resumption from \(s_t\) without replaying history; (2) targeted failure recovery from \(s_t^{ver}\) rather than generic retries; and (3) tool-supported execution where state-conditioned memory surfaces reusable procedures.

Key Contributions

  • Unified state schema \((s_t^{req}, s_t^{val}, s_t^{ver})\): a compact, typed, auditable shared interface for planner, actor, and verifier modules
  • Verifier-gated state transitions: all progress commits require explicit verifier-backed decisions, blocking false DONE claims
  • Progress checkpointing and targeted failure recovery derived directly from the structured state rather than history replay
  • Cross-domain generalization: the same state abstraction is instantiated in desktop GUI (OSWorld), web (Mind2Web), and Minecraft (inventory-based verification) without architectural changes
  • Open-source SOTA on OSWorld-Verified: 78.9% with MiniMax-M3

Results

  • OSWorld-Verified (controlled self-run):
  • Qwen3.5-9B: 27.0% → 46.9% (+73.7% relative; vs. Agent S3 40.8%, OS-Symphony 43.3%, VLAA-GUI 40.2%)
  • Qwen3.5-27B: 31.6% → 62.2% (+96.8% relative; vs. Agent S3 60.2%, OS-Symphony 52.8%, VLAA-GUI 48.2%)
  • MiniMax-M3: 75.2% → 78.9% (new open-source SOTA; reported frameworks top at 76.3%)
  • Structured vs. visual-only verification (354 Qwen3.5-27B trajectories): recall 0.67 → 0.81, F1 0.70 → 0.76; correct in 63% of disagreements vs. 31% for visual-only
  • Mind2Web (web generalization):
  • Qwen3.5-9B: 47.3% overall (vs. best baseline 46.0%)
  • Qwen3.5-27B: 52.3% overall (vs. best baseline 51.7%)
  • Minecraft (cross-domain): 76% task-weighted average vs. 59% for Optimus-1; strongest gains on Iron (65% vs. 47%), Golden (86% vs. 9%), Redstone (57% vs. 25%) tiers

Limitations

  • Cross-application tasks remain hardest; smaller backbones (Qwen3.5-9B) still trail on Multi-Apps category, indicating state structure helps but complex cross-app reasoning is a separate bottleneck
  • Structured verification is less beneficial when success conditions are embedded in GUI layout (Calc, Writer, Impress), where visual evidence dominates and richer app-specific checks are still needed
  • On Minecraft Stone tasks, StructAgent underperforms Optimus-1; even when it succeeds, it can be less step-efficient due to verification overhead
  • Web environments with dynamic widgets, pop-ups, and transactional flows expose action-grounding bottlenecks that state tracking alone does not resolve
  • Results on Mind2Web use judge-based scoring (WebJudge-style) rather than executable scoring, making cross-benchmark comparison noisier

Relevance to Vision-Language Models

StructAgent directly addresses a failure mode of VLMs deployed as computer-use agents: their tendency to hallucinate task completion or lose critical intermediate context in long interaction histories. By wrapping VLM backbones (Qwen3.5, MiniMax-M3) in a verifier-gated state machine, the framework compensates for VLMs' limited ability to self-monitor progress over extended trajectories—an issue that purely scaling the VLM does not resolve. The structured verification layer that augments (rather than replaces) visual understanding is particularly relevant, as it reveals which task domains remain bottlenecked by screenshot-only VLM perception versus those amenable to multi-modal agentic probing. The framework's backbone-agnostic design and consistent gains across model scales offer a reusable scaffold for the broader VLM-as-agent research direction.