🤖 AI

PreAct: Computer-Using Agents that Get Faster on Repeated Tasks

PreAct is a system that accelerates computer-using agents on repeated tasks by compiling successful executions into verifiable state-machine programs, enabling 8.5–13x faster replays with built-in safety checks to ensure correctness and prevent the accumulation of faulty scripts.

Original authors: Bojie Li

Published 2026-06-17

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Bojie 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 have a very smart, but very expensive, robot assistant. This robot can look at your computer screen, figure out what buttons to click, and type text to get things done—like booking a meeting or adding a contact.

The problem is, this robot is wasteful. Every time you ask it to do the same task twice, it forgets everything it just did. It has to look at the screen again, think through every step from scratch, and pay a huge "thinking fee" (using expensive AI computing power) every single time. It's like hiring a tour guide who, after showing you the museum once, makes you pay for a whole new tour guide to show you the exact same museum the next day, even though they both know the layout perfectly.

PreAct is a new system that teaches this robot to be fluent instead of forgetful. Here is how it works, using some everyday analogies:

1. The "Recipe Book" vs. The "Chef"

Normally, the robot acts like a chef who tastes every ingredient and re-invents the recipe for every single meal.
PreAct changes the game. The first time the robot successfully completes a task (like adding a contact), it doesn't just forget. Instead, it writes down a perfect, step-by-step recipe (a "state-machine program").

The First Time: The robot uses its expensive "thinking brain" to solve the task and writes the recipe. This takes time and money.
The Second Time: Instead of using its expensive brain, the robot simply reads the recipe and follows the instructions. It doesn't need to think; it just acts. This makes it 8.5 to 13 times faster and almost free to run.

2. The "Safety Check" (Not Blindly Following)

You might worry: "What if the screen looks different? What if a pop-up window appears?"
If the robot just blindly followed the recipe, it might click the wrong button and break things.
PreAct is smart about this. Before it takes every single step from the recipe, it glances at the screen to make sure it looks exactly as the recipe expects.

If it matches: It clicks the button instantly (no thinking required).
If it doesn't match: It stops immediately, says "Wait, something is wrong," and calls the expensive robot brain back in to figure out the new situation.
This is like a driver who follows a GPS route but keeps their eyes on the road. If a road is closed, they don't blindly drive into a wall; they stop and ask for new directions.

3. The "Quality Control Gate" (The Most Important Part)

Here is the tricky part: What if the robot writes a recipe that looks complete but actually fails?
Example: The recipe says "Type name, click Save." But maybe the robot forgot to actually type the name, so when it clicks Save, nothing happens. If the robot saves this bad recipe, it will fail every single time it tries to use it later.

PreAct has a strict Quality Control Gate.
Before it puts a new recipe into its library, it resets the computer and runs the recipe from scratch to see if it actually works.

If the recipe works: It gets added to the library.
If the recipe fails (even if it ran all the way to the end): It is thrown in the trash.

The paper found that without this gate, the robot's library fills up with "bad recipes," and it actually gets worse at doing tasks over time. With the gate, the robot gets better every time it repeats a task.

The Results

The researchers tested this on phones, desktop computers, and websites.

Speed: Repeating a task became 8.5 to 13 times faster.
Cost: The robot stopped paying the expensive "thinking fee" for repeated tasks.
Reliability: By checking the screen at every step and filtering out bad recipes, the system didn't just get faster; it got more accurate over time.

In short: PreAct turns a robot that re-invents the wheel every time into a robot that learns a skill, writes it down, and then executes that skill perfectly and instantly—until something changes, at which point it learns again. It's the difference between a student who memorizes a math problem once and a student who forgets it and has to re-learn it every day.

Technical Summary: PreAct – Computer-Using Agents that Get Faster on Repeated Tasks

1. Problem Statement

Computer-using agents (CUAs) operate software by observing screens and issuing clicks or keystrokes. While effective at solving tasks, they are inherently inefficient for repeated work. Current agents treat every task instance as a new problem: they re-read the screen, re-reason through every step, and incur the full cost of vision-and-language inference for every execution, even if the task is identical to one solved previously. This "re-derivation" prevents agents from acquiring the fluency humans develop through practice, where initial deliberate reasoning is internalized into automatic routines. Furthermore, existing efficiency improvements—such as skill libraries or record-and-replay systems—often fail to balance speed with reliability. Skill libraries typically still require a language model (LLM) to execute stored behaviors at runtime, while naive record-and-replay systems lack verification, leading to "blind" execution that fails when the environment changes or when the stored trace is flawed.

2. Methodology: PreAct Architecture

PreAct introduces a system that compiles successful agent runs into directly executable state-machine programs. The core innovation is a "verify-before-store" discipline applied at two timescales: runtime verification during replay and pre-storage verification before a program is saved.

2.1 The Artifact: State-Machine Programs

Instead of storing flat scripts or parameterized code snippets, PreAct compiles a successful task execution into a small state machine ( $P = (S, T, M, V)$ ):

States ( $S$ ): Each state contains a verification predicate (e.g., an XPath pattern or accessibility tree check) that must match the live screen before the agent proceeds.
Transitions ( $T$ ): Actions (clicks, types, navigations) that move the agent from one state to another.
Parameters ( $M$ ): Concrete values typed during the trace (e.g., a specific name or phone number) are lifted to parameters, allowing the same program to generalize across different instances of the same task family.
Execution: During a "warm" run, the Replayer walks the graph. Before firing a transition, it checks the live screen against the state's predicate. If the check passes, the action executes immediately without an LLM call. If it fails (e.g., a dialog appeared unexpectedly), the system halts and falls back to the full CUA.

2.2 The Loop: Select, Replay, Fall Back, Verify

The system operates via a compile-extend-replace loop:

Select: A Program Selector queries the corpus for a program matching the current goal.
Replay: If found, the Replayer executes the state machine with per-step verification.
Fall Back: If a predicate fails or an action errors, control transfers to the full CUA, which solves the task from the current screen state and records a new trace.
Verify and Store: Upon success, the new trace is compiled into a candidate program $P'$ . Crucially, $P'$ is not immediately stored. It undergoes a Verify-before-Store Gate.

2.3 The Verify-before-Store Gate

This is the system's primary mechanism for ensuring monotonic improvement. Before a program enters the corpus:

The environment is reset to a clean initial state.
The candidate program $P'$ is re-run from scratch.
An independent evaluator checks if the task was actually solved.
The program is stored (or replaces an older version with the same dedup signature) only if the replay completes successfully and the evaluator confirms the task is solved.

This gate specifically catches "lossy" programs that replay to 100% coverage (all actions execute) but fail to achieve the goal (e.g., a contact form is filled and saved, but a stale field prevents the contact from being created).

2.4 Fallback Mechanism

When the gate rejects all candidate programs for a task (leaving the corpus empty for that task), PreAct employs a fallback: it triggers a fresh CUA exploration for the second run. This ensures that even if the system cannot find a verified program, it does not simply give up, maintaining performance parity with strong record-and-replay baselines like Muscle-Mem.

3. Key Contributions

Direct Execution of Verified State Machines: PreAct shifts the execution paradigm from LLM-driven reasoning to deterministic graph execution for repeated tasks, eliminating per-step LLM calls.
Two-Timescale Verification: The system applies the same "observe-first, then-act" discipline at runtime (per-step) and at storage time (pre-storage re-run). This prevents the accumulation of faulty programs that would otherwise degrade performance over time.
Self-Extending Corpus: Unlike append-only caches, PreAct's corpus is mutable. New programs can replace older ones if they pass the verification gate, allowing the system to refine its representation of tasks over time.
Empirical Validation of Efficiency: The paper establishes "repeated-task efficiency" as a first-class metric, measuring not just success rates but the reduction in wall-clock time and LLM token costs.

4. Experimental Results

The authors evaluated PreAct on three benchmarks: AndroidWorld (mobile), OSWorld (desktop), and WebArena (web).

Speed and Cost: Warm runs (replaying stored programs) are 8.5–13× faster in wall-clock time than cold runs (re-deriving from scratch) and incur zero per-step LLM costs. The one-time overhead of compiling and verifying a program is roughly equivalent to one additional solve (+162% on Android, +217% on OSWorld), but this is amortized over subsequent runs.
Monotonic Improvement: With the verify-gate enabled, repeated runs consistently improve or hold steady in success rate.
- AndroidWorld: Mean improvement of +1.33 tasks (out of 15) from cold to warm.
- OSWorld: Mean improvement of +0.2 tasks (out of 6).
- WebArena: While the gate causes a regression in raw warm success rate (due to high rejection of brittle web selectors), the gate's marginal value is positive. Without the gate, performance degrades significantly (e.g., -5.8 tasks on WebArena) as lossy programs accumulate. With the gate, degradation is reduced (-4.0 tasks).
The Necessity of the Gate: Ablation studies show that disabling the verify-gate leads to performance collapse across all platforms. The gate prevents the "runs but doesn't work" failure mode, where a program executes all steps but fails the task logic.
Fallback Efficacy: On WebArena, where the gate rejects many programs, adding a "cache-miss-to-CUA" fallback allows PreAct to match the performance of the strong baseline Muscle-Mem (statistically indistinguishable, $p \approx 0.84$ ), closing the gap created by aggressive verification.
Robustness: The results are robust to the choice of LLM for compilation (Claude vs. Gemini) and the choice of selector (LLM-based vs. embedding retriever). The core mechanism, not the specific model, drives the results.

5. Significance and Claims

The paper claims that PreAct demonstrates that computer-using agents can acquire continual-learning capabilities similar to humans: becoming faster and cheaper on repeated tasks without sacrificing reliability.

Fluency vs. Blindness: PreAct achieves fluency not by blind repetition but by "prediction with verification." The agent acts automatically when the screen matches expectations but immediately reverts to deliberation when it does not.
Design over Tuning: The authors emphasize that the performance gains are driven by the system architecture (store the program you run, verify before storing) rather than prompt engineering, runtime guardrails, or specific model choices.
A New Evaluation Dimension: The paper argues that benchmarking should move beyond simple success rates to include the cost of repeated execution. An agent that re-derives every task is less efficient than one that has learned to skip deliberation, even if both achieve the same success rate.

In summary, PreAct provides a framework where agents build a library of verified, directly executable programs, allowing them to solve familiar tasks with the speed of a macro and the reliability of a verified agent, effectively solving the "re-derivation tax" of current computer-using agents.