Technical Summary: Agent JIT Compilation for Latency-Optimizing Web Agent Planning and Scheduling

Problem Statement

Computer-use agents (CUAs) automate web-based tasks specified in natural language (e.g., "order the cheapest item from Taco Bell") by generating sequences of tool calls such as click, type, and scroll. Current implementations typically follow a sequential fetch-screenshot-execute loop, where each iteration requires a Large Language Model (LLM) call. This architecture suffers from two primary limitations:

1. High Latency and Cost: The necessity of an LLM call at every step creates significant execution delays and high inference costs.
2. Accuracy and Error Rates: Naive application of frontier LLMs leads to frequent errors, often stemming from incorrect tool use sequences (e.g., clicking the wrong element or typing into the wrong field) and a lack of optimization in execution scheduling.

Existing attempts to improve performance, such as aggressive DOM filtering or reinforcement learning of smaller models, still rely on static tool sets and sequential execution, failing to explore the full space of execution schedules (including parallelism and request hedging) or to eliminate non-deterministic LLM calls between tool invocations.

Methodology: Agent JIT Compilation

The authors propose Agent Just-In-Time (JIT) Compilation, a system that translates high-level natural language instructions into optimized, executable code at plan synthesis time. Unlike standard agents that execute a loop of "observe-think-act," this system compiles a task into a static code graph that orchestrates tool calls and inference, selecting the translation with the lowest estimated cost. The architecture consists of three core components:

1. Invariant-Enforcing Tool Protocol

To ensure the correctness of generated code plans, the system introduces a protocol where every tool specifies preconditions and postconditions (state invariants).

• Structure: Tools define expected states before execution (pre), guaranteed states after execution (post), and optional runtime predicates (pre_check, post_check) for debugging.
• Verification: This enables compositional verification at compilation time. A tool call is only valid if the current state satisfies its precondition. This static checking eliminates a large class of errors caused by incorrect action sequences (e.g., attempting to order an item before navigating to the detail page).
• Benefit: The protocol shifts the latency-accuracy Pareto frontier, significantly increasing the rate of valid plan generation.

2. Cost-Optimizing Planner (JIT-Planner)

The planner generates multiple candidate code plans in parallel, validates them against the tool protocol, and selects the minimum-cost candidate.

• Parallel Generation: Multiple workers sample code plans from an LLM simultaneously.
• CFG-Based Validation: Each plan is converted into a Control Flow Graph (CFG). The system traverses the graph to verify state flow (ensuring post of step $i$ satisfies pre of step $i+1$) and estimate cost.
• Cost Model: Costs are accumulated based on tool calls and AI evaluation (ai_eval) calls. A nesting penalty ($\gamma$) is applied to discourage nested loops involving expensive LLM calls.
• Outcome: The planner selects the valid plan with the lowest estimated cost, often replacing unnecessary LLM calls with pure code logic (e.g., calculating the minimum price in code rather than asking the LLM).

3. Cost-Aware Scheduler (JIT-Scheduler)

The scheduler determines the optimal execution strategy for a given plan based on learned latency distributions. It evaluates three strategies:

• Serial: Sequential execution.
• Parallel: Task parallelism across $n$ workers.
• Hedge: Speculative parallel execution where $n$ redundant workers run the same task, and the first valid result is returned.
• Mechanism: Using Monte Carlo cost estimation, the scheduler samples from learned latency distributions of specific DOM elements (collected offline). It predicts which elements a plan will interact with and estimates the expected latency for each strategy, selecting the one with the minimum mean latency.

Offline Caching

The system relies on an offline process to populate two caches:

1. Planner Cache: Maps high-level actions to reusable, protocol-compliant tool code (synthesized from execution traces).
2. Scheduler Cache: Maps page schema elements to latency distributions (fitted from historical execution traces).

Key Contributions

1. Invariant-Enforcing Tool Protocol: Extends standard tool interfaces to include state invariants, enabling static verification of tool sequences and reducing generation errors.
2. Cost-Optimizing Planning: Introduces a planner that generates parallel candidates, validates them via CFG traversal, and selects the lowest-cost execution path, effectively eliminating redundant LLM calls.
3. Cost-Aware Scheduling: Implements a scheduler that dynamically selects between serial, parallel, and hedging strategies based on Monte Carlo simulations of learned latency distributions.
4. End-to-End System: Integrates these components into a JIT compiler that translates natural language tasks into optimized executable code, moving beyond the standard agent loop.

Results

The system was evaluated across 37 tasks on five web applications (Dashdish, GitLab, Gomail, Omnizon, Reddit) using various frontier LLMs.

• JIT-Planner Performance:

  • Achieved a 10.4× speedup over the standard Browser-Use baseline.
  • Improved accuracy by +28% over Browser-Use.
  • Demonstrated that cost estimation effectively ranks plans: the difference between the best-cost and worst-cost candidates was a 5.3× variance in latency.
  • The invariant protocol reduced the failure rate of plan generation from 80% to 43% and shifted the dominant failure mode from tool ordering violations to other types.

• JIT-Scheduler Performance:

  • Achieved a 2.4× speedup and +9% accuracy improvement over OpenAI's CUA.
  • Outperformed fixed scheduling strategies (Serial, Parallel, Hedge) by adaptively selecting the optimal strategy per task. For instance, it correctly identified that tasks with high-variance UI elements (e.g., finding a specific button) benefit from hedging, while simple lookups benefit from serial execution.

• Complexity Analysis:

  • Speedups were consistent across task cardinality (low, medium, high) and length, indicating the benefits stem primarily from eliminating per-step LLM inference rather than task-specific heuristics.
  • Applications with complex navigation patterns (e.g., Reddit) saw the highest speedups (up to 18.9×), while those with simpler flows saw lower but still significant gains.

Significance and Claims

The paper claims that Agent JIT Compilation presents a promising direction for improving the efficiency and reliability of computer-use agents. By treating agent planning as a compilation problem, the system:

1. Decouples Planning from Execution: It allows for the optimization of the entire execution graph before runtime, rather than making greedy, step-by-step decisions.
2. Reduces Non-Determinism: By enforcing state invariants and compiling tasks into code, it reduces the reliance on non-deterministic LLM calls during execution, leading to higher accuracy.
3. Optimizes Resource Usage: Through cost-aware scheduling, it adapts to the specific latency characteristics of web interactions, balancing the trade-off between latency and accuracy more effectively than static strategies.

The authors note that the approach is best suited for applications an agent will handle repeatedly, as it requires an offline setup cost (tool synthesis and trace collection) to build the necessary caches. They acknowledge limitations regarding UI changes (which can break cached tools) and highly stochastic environments (e.g., CAPTCHAs), but assert that the invariant protocol provides a mechanism for runtime detection and fallback.