🤖 machine learning

Why Are GUI Agents Correct but Late? Decode on the Decision-Time Critical Path, Tested with Pre-Compiled Policy Trees

This paper introduces Adaptive Anticipatory Policy Trees (AAPT), a framework that eliminates decision-time latency in GUI agents by pre-computing policy trees during idle periods to enable immediate action execution upon event detection, thereby significantly improving success rates on transient events without modifying the underlying model.

Original authors: Zihan Dong, Rui Qian, Qishi Zhan, Dongshen Peng, Kaixin Li, Yu Li

Published 2026-07-31

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Zihan Dong, Rui Qian, Qishi Zhan, Dongshen Peng, Kaixin Li, Yu Li

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 are playing a fast-paced video game where a secret door only stays open for half a second. If you see the door, think about which key to use, walk over, and press the button, you'll likely miss it. By the time your brain finishes the math, the door is gone. This is the daily struggle for "GUI agents"—smart computer programs designed to click buttons, type text, and navigate screens just like humans do. These agents usually work in a simple loop: take a picture of the screen, ask a giant artificial intelligence brain what to do, and then move. But in the real world, screens don't wait. Pop-up windows, login timers, and fleeting notifications appear and vanish in the blink of an eye. The big question scientists have been asking is: Why do these smart agents fail? Is it because they are too slow to understand the picture, or because they are too slow to act on that understanding before the window slams shut?

This paper, titled "Why Are GUI Agents Correct but Late?", investigates a frustrating glitch where agents figure out the right answer but arrive just a fraction of a second too late. The researchers discovered that the problem isn't that the agent is confused; it's that the agent is trying to do its heavy thinking while the clock is ticking. They propose a clever fix called Adaptive Anticipatory Policy Trees (AAPT). Think of it like a chef who, instead of waiting for the customer to order a burger before starting to chop the onions, prepares a set of pre-chopped ingredients for every possible burger the customer might order while the restaurant is quiet. When the customer finally says, "I want a cheeseburger," the chef doesn't start chopping; they just grab the pre-made cheeseburger patty and serve it instantly.

The researchers tested this idea on a special benchmark where a prompt appears for exactly 600 milliseconds (0.6 seconds). In a standard setup, the agent has to take a screenshot, send it to the AI, wait for the AI to write a response, and then click. This whole process takes about 567 milliseconds, leaving almost no room for error. If the AI is even a tiny bit slow, the window closes, and the agent fails. The AAPT method changes the game. While the screen is quiet, the AI pre-calculates a "tree" of possibilities. It prepares a plan for "If the prompt asks for F12, press F12," and another for "If it asks for Enter, press Enter." These plans are locked and loaded. When the prompt actually appears, a tiny, super-fast "observer" just looks at the screen, matches it to the pre-made plan, and fires the action immediately. No new thinking is required at the last second.

The results were striking. In the "contested" window where the standard agent failed 50% of the time, the AAPT agent succeeded 79% of the time. Crucially, the paper shows that simply "thinking ahead" isn't enough. The researchers tested other methods where agents tried to guess early but still had to do the heavy thinking after the event appeared. Those methods failed just as badly as the slow ones. The secret sauce was moving the heavy thinking off the critical path—doing the hard work while the clock wasn't running. The study also found that this trick only works if the agent can list all possible answers in advance. If the task requires guessing a secret number that hasn't been revealed yet, or navigating a complex maze with unknown turns, the pre-made plans fall apart, and the agent must go back to the slow, standard way of thinking.

The paper suggests that for fast, fleeting moments on a computer screen, the best strategy isn't a faster brain, but a smarter workflow: prepare your options while you have time, so you can act instantly when the moment arrives. However, the authors are careful to note that this isn't a magic bullet for every computer task. It works beautifully for predictable, short-lived events but doesn't replace the need for a reactive, thinking agent when the future is truly unknown. The success of this method depends on the agent being able to "compile" its plans quickly and route the right one without hesitation, a balance that the researchers measured and confirmed across several different AI models.

Technical Summary: Why Are GUI Agents Correct but Late?

Problem Statement

Computer-use agents frequently fail on transient GUI events (e.g., boot prompts, auto-dismissing dialogs, short-lived authentication requests) not because they misunderstand the task, but because they act too late. The standard reactive loop—capture screenshot, call multimodal model, execute action—requires a full "perceive-reason-act" round trip. The paper identifies that the autoregressive decoding latency of large multimodal models on the decision-time critical path often exceeds the lifespan of these transient windows. Consequently, the agent computes the correct action only after the relevant window has already closed.

The central hypothesis tested is whether this failure is due to a lack of anticipation or simply the placement of heavy computation on the critical path. The authors argue that even if an agent anticipates correctly, if the generation of the action occurs after the event onset, it will miss the deadline.

Methodology: Adaptive Anticipatory Policy Trees (AAPT)

To isolate the cause of these failures, the authors propose Adaptive Anticipatory Policy Trees (AAPT). This is not a new agent architecture in the traditional sense but a controlled manipulation of the execution pipeline to move generation off the critical path.

Core Mechanism

AAPT operates in two distinct phases:

Preparation Phase (Off-Critical Path): During idle screen periods, the same frozen multimodal model (the "slow planner") pre-compiles a bounded conditional policy tree. This tree consists of:
- Observable Guards: Conditions based on visual changes (e.g., "Prompt requests F12").
- Pre-authorized Actions: Primitive actions (e.g., press('f12')) or short chunks.
- Branch-Specific Deadlines: Time limits for each branch.
- Confidence and Risk Metrics: Calibrated probabilities to determine branching.
  The tree is sized to cover the model's own decoding latency ( $T_{cover} \ge L_{p95} + M$ ), ensuring the preparation time is sufficient to arm the system before the event occurs.
Runtime Phase (Critical Path): When a screen change is detected (via a change gate), a lightweight observer (a low-token, fast-decoding call) analyzes the new frame.
- The observer matches the frame against the pre-compiled guards.
- It returns a single JSON object identifying the matching branch ID.
- If a match is found, eligible, and within the deadline, the pre-authorized action fires immediately without generating new text.
- If no match is found, the guard is ambiguous, or the deadline passes, the system falls back to replanning (re-entering the slow loop).

Experimental Design

The study utilizes a custom benchmark, key_prompt, designed with millisecond-scale control over event windows (250–2000 ms). The environment presents a transient prompt requesting one of three keys (e.g., F12, Enter, Esc) after a fixed delay. Success requires the correct keypress to reach the server before the window closes.

The authors employ a rigorous paired per-seed design with exact McNemar tests to compare AAPT against:

R0 (Reactive Baseline): Standard loop (screenshot $\to$ full model decode $\to$ action).
R1 (Open Loop): Pre-planned unconditional sequence without observation.
P1 (Predict-and-Replan): Predicts a trajectory, executes one step, then replans (keeping heavy decoding on the critical path).
O1 (Oracle Routing): Uses ground truth to select the branch, isolating the cost of the observer's routing decision.

Key Contributions

Causal Isolation of Latency: The paper provides evidence that removing generation from the decision-time critical path, rather than merely acting earlier, is the primary factor in recovering success on contested windows.
A Controlled Method (AAPT): A framework that isolates decode latency as a cause of missed windows without modifying the underlying model weights.
Three Capability Gates: The authors identify three necessary conditions for AAPT to succeed, validated through ablation and cross-model replication:
- Fast Observer Decoding: The routing call must be sub-second.
- Valid Tree Planning: The planner must generate a schema-valid, flat tree covering the outcome space.
- Accurate Branch Routing: The observer must correctly map the visual input to the pre-compiled branch.
Boundary Conditions: The study delineates where pre-computation helps (pre-enumerable outcomes) versus where it fails (late-bound parameters, multi-step sequencing, or positional grounding).

Results

Success Rate Improvement: In the contested window regime (600–650 ms), AAPT (T2) improved the success rate from 0.50 (R0) to 0.79, with a statistically significant p-value of $1.8 \times 10^{-3}$ . Crucially, AAPT produced zero incorrect actions in these trials, as late or unmatched decisions were suppressed rather than executed.
Baseline Failures: Open-loop (R1) and predict-and-replan (P1) baselines achieved zero success in the contested regime because they still required full model decoding on the critical path.
Replication: The effect was reproduced on an independent, untuned generalist model (Qwen3.6-35B-A3B) over 126 paired trials ( $p = 4.9 \times 10^{-13}$ ), confirming the result is not specific to a fine-tuned agent.
Ablation Findings:
- Routing is Causal: An oracle probe on a model with poor routing accuracy (UI-Venus) showed that perfect routing alone could turn a tie into a win, confirming routing accuracy is a causal bottleneck.
- Budget Sensitivity: Performance drops sharply if the tree budget (branch count) does not match the outcome set size, leading to "budget refusal" or incorrect actions.
- Preparation Time: The advantage only emerges when the preparation time exceeds the planner's own latency ( $L_{p95} + M$ ). Below this threshold, AAPT degrades to the reactive baseline or worse.
External Benchmark: On the DynaCU-Bench, AAPT matched the overall performance of a reactive baseline but showed a clear dissociation: AAPT won on tasks with pre-enumerable responses (dashboards), while reactive execution won on tasks requiring multi-step sequencing or late-revealed values.

Significance and Claims

The paper claims that missed transient GUI events are often a scheduling failure rather than a reasoning failure. The significance lies in reframing "anticipation" not as a model trait (the ability to predict the future) but as a pipeline property.

Latency-Compute Trade-off: AAPT trades off increased total token usage (due to pre-compilation) for reduced critical-path latency. It is economically viable only when the reactive latency distribution overlaps with the task deadline and sufficient "quiet time" exists for preparation.
Hybrid Control: The authors suggest that the optimal future agent is not purely anticipatory or reactive, but a hybrid controller that detects whether a transition is pre-enumerable. If so, it uses AAPT; if the task involves late-bound parameters or complex sequencing, it reverts to reactive execution.
Reproducibility: The study highlights that reproducing thresholded agent results requires strict preservation of "decision boundaries," including compiled-kernel identities and serving latency quantiles, as small shifts (e.g., 100 ms) can move a window from contested to ceiling/floor.

The paper concludes that while AAPT does not universally outperform reactive agents, it provides a robust mechanism to recover performance in specific, high-stakes, time-constrained GUI scenarios where the correct response can be enumerated in advance.