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

Source: arXiv:2606.17929 · Published 2026-06-16 · By Bojie Li

TL;DR

PreAct addresses the inefficiency of contemporary computer-using agents that repeatedly solve tasks from scratch, incurring full perception and reasoning overhead each time. By compiling a successful task execution trace into a small, parameterized state-machine program, PreAct enables later runs of the same task to bypass the language model inference step entirely, replaying the procedure up to 8.5–13× faster with zero per-step LLM calls. Crucially, PreAct verifies at runtime that each step's precondition matches the live screen and falls back to full agent reasoning when deviations occur, ensuring reliability unlike traditional blind record-and-replay approaches.

Beyond runtime checks, PreAct enforces a verify-before-store gating mechanism: new compiled programs are independently re-run from a clean environment and only stored if they both execute without errors and achieve a full task evaluation score. This double verification prevents accumulation of faulty programs that could degrade performance. Experiments across mobile (AndroidWorld), desktop (OSWorld), and web (WebArena) benchmarks confirm PreAct’s ability to progressively improve repeated-task efficiency, saving 1.75–2.6 tasks worth of full agent solves per benchmark. The system also matches strong record-and-replay baselines when no cached program fits, showing robustness and practical applicability. Notably, variations in prompt design, runtime guardrails, and program retrieval methods had minimal impact, highlighting that the core contribution lies in verified program compilation and reusable state-machine replay.

Key findings

• Repeated runs replay stored state-machine programs 8.5–13× faster in wall-clock time than full agent re-derivation with no per-step language model calls (Fig 1).
• Verify-before-store gate prevents programs that replay fully but fail task evaluation (cov=100%, score=0), stopping flawed code from degrading the corpus (§3.3, Fig 6).
• Across AndroidWorld, OSWorld, and WebArena, verified replay yields monotonic improvement worth 1.75–2.6 fewer agent solves per benchmark, consistently across platforms (§4.4).
• Using a fallback that explores afresh when no stored program fits maintains performance comparable to a strong record-and-replay baseline (Muscle-Mem) (§4.5).
• Selector method—language model vs. plain embedding retriever—does not significantly impact retrieval success or overall performance (§6.1).
• Run-time per-step verification (observing expected UI state before acting) significantly reduces replay failures compared to blind flat-script playback (§4.6).
• The program corpus self-extends and self-refines by replacing prior programs with verified updates, allowing improved task coverage over time (§3.2).
• Prompt wording, added guardrails, and retrieval ordering had negligible effects, isolating the contribution to the compile–verify–replay design itself.

Threat model

The adversary is the operating environment that may change state or UI unpredictably between runs; the agent must detect and adapt to these changes. The adversary cannot interfere with the agent's internal code, program store, or verification process. The agent assumes access to clean environment resets for replay verification, precluding irreversible side effects during verification.

Methodology — deep read

1. Threat model & assumptions: The adversary is a fixed software environment that may change unpredictably between runs (e.g., UI changes, dialogs). The agent cannot predict or control these changes. The agent assumes access to an environment that can be reset to a clean initial state for verify-before-store. The adversary cannot modify the agent's code or stored programs directly.

2. Data: Experiments are conducted on three public benchmarks representing different platforms and tasks: AndroidWorld (mobile app interaction, 15 tasks subset), OSWorld (desktop apps including Chrome and LibreOffice, 6 tasks subset), and WebArena (web admin panel, 12 extraction tasks subset). Each task has scripted environment resets and built-in evaluators.

3. Architecture: PreAct wraps a classical computer-using agent (CUA) with a compile-extend-replace loop. On first success, the agent's trace (list of observed states, actions, parameters) is compiled into a deterministic, parameterized state-machine program: a graph where each state holds a verification predicate (UI element pattern expected) and each transition performs an atomic action (click, type, navigate). A Program Selector chooses the most relevant stored program for the task. The Replayer executes the program step-by-step, verifying predicates against the live screen before each action. On predicate failure, control falls back to the full CUA which produces a new trace.

4. Training regime: Rather than traditional ML training, PreAct's "training" is interaction-driven corpus growth. Each successful new trace is compiled and passed through a verify-before-store gate by replaying it on a freshly reset environment and evaluating success. If both replay and evaluation succeed, the program either replaces an older version with the same deduplication signature or is appended. This process continuously refines the corpus.

5. Evaluation: Metrics include wall-clock execution speedup relative to full CUA solves, cumulative LLM calls (for cost), task success rates on repeated runs, and count of solves saved by replay corpus growth. Ablations disable verify-before-store or run-time verification to isolate components. Baselines include pure CUA, Muscle-Mem record-and-replay, and variants with embedding or LLM retrieval selectors.

6. Reproducibility: Code and sample programs are publicly released on GitHub. Benchmarks like AndroidWorld and WebArena are public or well-documented datasets. Exact training seeds or hyperparameters are not discussed, as this is an interactive system rather than traditional ML training.

Example end-to-end: On the AndroidWorld 'add contact' task, the first execution involves the CUA agent alternately perceiving the screen and deciding actions until success. PreAct then compiles this full trace into a parametric state machine with seven states, each with a predicate verifying UI elements (e.g. 'Contacts app open', 'first name entered') and transitions performing taps or types with parameter binding. On subsequent runs, the Program Selector retrieves this program, which the Replayer executes by checking each UI condition, then performing the action without invoking any language model. If at any point the UI has changed, the fallback agent takes over, generates a new trace, which then can be compiled and verified before updating the corpus. This loop achieves large speedups in repeated executions while maintaining accuracy.

Technical innovations

• Compile full successful agent interaction traces into directly executable, parameterized state-machine programs with per-state verification predicates.
• Introduce a dual verification gating mechanism: per-step runtime checks against live UI before each action, plus an independent verify-before-store gate that replays compiled programs from a clean state and confirms task success.
• Implement a mutable program corpus that self-extends and self-refines by replacing prior programs with verified improvements rather than being append-only.
• Demonstrate that skipping the language model inference loop on repeated tasks yields 8.5–13× runtime speedups with zero per-step LLM calls, a step-change over prior LLM-bound replay or cached skill libraries.

Datasets

• AndroidWorld official-15 subset — 15 tasks across 8 mobile app domains — public benchmark
• OSWorld test_tiny subset — 6 tasks spanning desktop apps Chrome, LibreOffice Calc, Writer — curated test subset
• WebArena shopping_admin subset — 12 tasks extracting answers on Magento e-commerce admin web UI — public benchmark

Baselines vs proposed

• CUA baseline full solve: normalized LLM cost = 1.0 vs PreAct replay later runs: near 0 with one-time compile overhead (+162% to +217%)
• Muscle-Mem record-and-replay baseline: matched by PreAct fallback exploration when no program fits, showing comparable task success rates
• No verify-before-store gate: repeated runs accumulate faulty programs, decreasing task solve counts by 1.75–2.6 tasks per benchmark
• Embedding retriever selector: retrieval accuracy 100% vs LLM selector 75.6%, but final task performance nearly identical
• Run-time predicate verification disabled: higher replay failure rates and more fallback calls, losing speed advantage

Limitations

• Requires deterministic or resettable environments to safely replay and verify programs—irreversible side effect tasks (payments, messages) need alternate verification.
• The corpus stores task-specific state machines that do not transfer across task families or generalize broadly beyond repeated exact or similar tasks (§5.6).
• No evaluation under adversarial UI changes or deliberate environmental manipulation; robustness to malice untested.
• The fallback agent (CUA) efficiency limits overall throughput when fallback is frequent; PreAct depends on the baseline agent quality.
• No formal statistical tests reported; improvements shown via task counts and speedups but with unknown confidence intervals.
• Possible brittleness to UI selector changes or unexpected screen layouts despite per-step verification, especially in highly dynamic UIs.

Open questions / follow-ons

• Can PreAct’s verified replay approach be extended to environments with irreversible or side-effectful tasks, using side-effect-free verification methods?
• How well does the mutable program corpus scale with very large and diverse task sets, and how to manage corpus growth and pruning?
• Can learned generalization or meta-program synthesis enable transfers across related task families rather than purely parametric reuse?
• What are the limits of robustness under adversarial environment conditions or adaptive UI changes that attempt to defeat per-step verification?

Why it matters for bot defense

For bot-defense and CAPTCHA practitioners, PreAct provides a systemic approach to drastically reduce agent inference costs on repeated, rule-based tasks by compiling behavior into verified, executable code artifacts. This is relevant for designing long-lived automation that must repeatedly traverse similar UI flows robustly under changing conditions. The dual verification gates ensure that replayed behavior is reliable and self-correcting, which is critical to prevent stealthy automation bypasses that degrade over time.

PreAct’s method shows the value of embedding runtime semantic checks into any recorded automation steps before replay, rather than blindly replaying scripts or macro chains. This aligns with CAPTCHA design principles where human verification steps and dynamic UI states help prevent blind replay attacks. Bot-defense engineers can consider analogs of such verified replay and mutation to harden persistent automation—tracking stale program reuse and forcing re-verification to avoid silent failures that may go undetected. Additionally, the experimental methodology of measuring cumulative cost per repeated run is useful for evaluating efficiency gains from bot detection or challenge injection techniques that aim to increase attack cost incrementally over multiple attempts.

Cite

@article{arxiv2606_17929,
  title={ PreAct: Computer-Using Agents that Get Faster on Repeated Tasks },
  author={ Bojie Li },
  journal={arXiv preprint arXiv:2606.17929},
  year={ 2026 },
  url={https://arxiv.org/abs/2606.17929}
}

Read the full paper

• arXiv:2606.17929 (abstract)
• arXiv:2606.17929 (PDF)