acceptodds
Under review as a conference paper at ICLR 2027

SAGE: From Reactive to Programmatic Web Agents via State Machine Memory

13 views

Abstract

Many web agents operate through a reactive execution loop: they observe the current interface, reason about the next action, execute it, and repeat. This design incurs latency and cost that grow with the number of actions, while requiring agents to repeatedly rediscover how the same web application works. We present SAGE, a novel architecture that replaces step-by-step reasoning with programmatic execution using reusable knowledge of the application. A Crawling Agent explores the application offline and constructs an updatable state-machine memory that represents its GUI states, the operations available in each state, and the transitions between states. Unlike trajectory memory, this representation stores how the application works rather than solutions to individual tasks. At runtime, an Execution Agent uses this memory to synthesize a complete executable program in a single planning step, which is then executed deterministically without further planning calls. When the interface changes or the memory is incomplete, a reactive fallback repairs the failed action and updates the memory for future tasks. On 655 tasks across four WebArena domains, SAGE achieves a 91.2% success rate, outperforming the strongest reactive baseline, Claude Code, by 8.5 percentage points while reducing average task latency by 3.2x and cost by 8x.

Primary area:
foundation or frontier models, including LLMs
Keywords:
LLM, Agent, LLM-based Agent, Web Agent, Web Navigation

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_nNDZOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes SAGE, a web-agent architecture that replaces step-by-step reasoning with programmatic execution using reusable knowledge of the application. SAGE crawls a web application to build a reusable state-machine graph describing interface states, operations, and transitions. It then generates a Python program for each task, compiles abstract operations into browser actions, and executes it with minimal further reasoning. Evaluated on WebArena, it reports >90% accuracy with lower latency and cost, showing the effectiveness of the proposed approach.

Critical strengths
  • The proposed approach provides an interesting method of storing application-level memory and generating one-time program for task execution, which provides insights on effective and efficient web agents.
  • The paper reports impressively high results on WebArena with relatively low costs.
Critical weaknesses
  • The experiments are constrained to WebArena, and it is unclear how the proposed method can generalize to other web agent benchmarks, especially the live web ones interacting with the real Internet (for example, Online-Mind2Web).
  • It is unclear what types of the tasks the proposed method can cover. It seems that it needs to fully understand the environment for building the state memory, but for real-world applications, this might not always be fesible. React-styled online exploration might still be necessary for many of these tasks.
Questions for authors
  • For target websites where one cannot effectively crawl all the pages and build the state memory, how will the proposed approach perform?
  • It seems that there is a lack of comparisons to approaches that specifically use enhanced agent memory methods.
  • According to 356, evaluation is carried out in a single execution attempt without online repair; then will there be execution errors and how to deal with runtime errors like this?
1 comment
AuthorsOpenReview ↗

Response to Reviewer nNDZ

We thank the reviewer for the feedback and questions. The main changes in the paper (marked in blue) are:

  1. A comparison with Agent Workflow Memory (AWM), a memory-based baseline (Section 5, Appendix D.3).
  2. Preliminary results with an updated crawler that explores the application more thoroughly offline (Appendix D.5).

Target use case. SAGE targets agents that use the same applications repeatedly, such as an organization's internal tools or a user's frequently visited sites. In this setting, the one-time cost of building the SMG is amortized over many tasks (Table 2). In settings with one-off tasks across many different websites, a reactive agent that explores each site on the fly is a better fit.

Task coverage. We agree that some tasks are more suited for reactive exploration, and SAGE uses it as a fallback: when execution fails, the Patcher diagnoses and repairs the plan step by step (Section 4.3). In our evaluation, the main class of tasks that one-shot planning handles poorly is search tasks, where search terms must be chosen before the results are observed (∼22 failures, Appendix D.2). Tasks over structured interfaces, such as forms, reports, and multi-page navigation, are where planning over the SMG helps most (Section 5.2, Appendix D.1).

Q1: For target websites where one cannot effectively crawl all the pages and build the state memory, how will the proposed approach perform?

SAGE does not need to visit every page to build its state memory. The SMG models interface templates, not individual pages: on a shopping site, every product's detail page shares the same layout, so all of them map to one state. The graph size therefore grows with the number of distinct templates rather than the amount of content (Appendix A.1). Discovering the pages of a website is a well-researched problem that search engines solve at web scale, and SAGE could borrow their techniques.

When the crawl is less thorough, the SMG is less complete and performance drops. On GitLab, without warm-up, our original crawler (\29.5)yields55.029.5) yields 55.0% success, and our updated crawler, which explores the website more thoroughly offline (\\130), yields 84.4 (Table 2a, Appendix D.5). When coverage is incomplete, the Patcher repairs the plan at runtime and records the repair in the SMG, so coverage improves with use. When available, developers could also derive the graph from source code and documentation rather than relying solely on black-box crawling.

Q2: It seems that there is a lack of comparisons to approaches that specifically use enhanced agent memory methods.

We have added Agent Workflow Memory (AWM) as a memory-based baseline. AWM induces reusable workflows from its own successful trajectories and adds them to its prompt for later tasks. We run it in its online setting with the same model (Claude Opus 4.6) on the same 655 tasks: after each task, an LLM judge decides whether the trajectory succeeded, and AWM induces workflows from the successful ones. Because AWM builds its memory from the evaluation tasks themselves, it receives more warm-up than SAGE. By the end of each domain, its memory holds 11 to 24 workflows (Appendix D.3). Even so, AWM reaches 58.6% overall success, 32.6 points below SAGE (Table 1), and is 6.1× slower and 10× more expensive per task (Figure 4).

Q3: According to 356, evaluation is carried out in a single execution attempt without online repair; then will there be execution errors and how to deal with runtime errors like this?

With the Patcher disabled, an action that fails at runtime causes the task to fail. In our experiments, none of SAGE's failures were caused by broken selectors or SMG structural issues after the online refinement (Appendix D.2). We disable the Patcher during evaluation so that each result reflects a single pass of the synthesized program over a fixed SMG, with no repair or learning at test time. This is a conservative setting that measures the quality of the SMG and the plan.

Reviewer_ogmsOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

SAGE constructs reusable state-machine memory through offline website exploration, then uses this memory to generate and execute task programs. Experiments on 655 WebArena tasks evaluate task success, online execution cost, latency, memory refinement, and prefix caching.

Critical strengths

The approach is well motivated for persistent agents repeatedly using a small set of applications. Reusable operations and live-data access provide a practical alternative to repeated step-by-step exploration. The same-backbone comparisons show promising results: reported success increases from 82.7% to 91.2%, while query-time cost and latency decrease substantially. The paper also reports initial crawling costs, break-even estimates, and useful refinement and caching ablations.

Critical weaknesses

Lifecycle cost accounting is incomplete. The reported 8× saving concerns query-time execution, while the 39–101-task break-even estimates amortize initial crawling only. The template-based warm-up required for the main results is not separately costed. Maintenance, interface changes, and cache expiration could further affect the economics of long-term use.

Exploration’s marginal returns are not characterized. The paper compares crawler-generated and refined memory, with success increasing from 73.1% to 91.2%, but provides no controlled sweep over exploration budget, depth, coverage, or warm-up volume. Moreover, refinement introduces task-template-related experience. These two endpoints cannot establish an optimal exploration budget or a saturation point.

The comparisons do not isolate the benefit of the memory representation. SAGE receives offline exploration and template-aware warm-up, whereas the reactive baselines lack equivalent persistent application knowledge. An experience-matched baseline allowed to retain documentation, scripts, or skills would better distinguish SMG-specific benefits from the general advantage of pre-exploration.

Construction-cost reporting requires clarification. Table 2 reports GitLab crawling at $29.5 and 230 minutes, whereas Appendix C.1 reports approximately $5 and 1.5 hours, with different graph sizes. These configurations should be reconciled before drawing amortization conclusions.

Questions for authors

What are the complete warm-up costs, and how would including them change the break-even estimates?

Do existing exploration checkpoints reveal how performance varies with accumulated exploration expenditure?

1 comment
AuthorsOpenReview ↗

Response to Reviewer ogms

We thank the reviewer for the feedback! The main changes in the paper (marked in blue) are:

  1. A comparison with Agent Workflow Memory (AWM), a new baseline that retains experience across tasks (Section 5, Appendix D.3).
  2. An estimate of warm-up cost and its effect on break-even (Appendix D.6).
  3. Preliminary results with an updated crawler that builds the SMG without any warm up (Appendix D.5).

Q1: What are the complete warm-up costs, and how would including them change the break-even estimates?

We estimate warm-up costs at \2−19perapplication,whichislessthanthecostofcrawling.Includingwarmupraisesthebreak−evenpointfrom39–101to47–153tasks(AppendixD.6).WehavealsoextendedthecrawlerwithaphasethatrefinestheSMGbyexecutingworkflowsitcomposesitself,sonowarmuptasksareneeded(AppendixA.2).OnGitLab,thenewSMGreaches84.42-19 per application, which is less than the cost of crawling. Including warm up raises the break-even point from 39–101 to 47–153 tasks (Appendix D.6). We have also extended the crawler with a phase that refines the SMG by executing workflows it composes itself, so no warm up tasks are needed (Appendix A.2). On GitLab, the new SMG reaches 84.4% without any warm-up, close to the originally reported 88.9% with warm-up (Appendix D.5). The tradeoff is cost. The new SMG is larger (1,700 vs. 1,214 operations), so it costs more to build offline (about \\130) and more per task (\0.28vs.0.28 vs. \\0.10 without prefix caching), though still less per task than every baseline.

Q2: Do existing exploration checkpoints reveal how performance varies with accumulated exploration expenditure?

Unfortunately we did not keep checkpoints for the original crawler. For the new crawler, Appendix D.5 reports the size of the SMG and the cumulative tokens at each checkpoint (Table 5), and the changes made in the fifth phase (Table 6). The fifth phase adds few states and operations but repairs many existing ones, for example 122 selectors and 226 descriptions, and increases the total description length by 31%.

Experience-matched baseline. We have added Agent Workflow Memory (AWM) [Wang et al., 2024], a memory-based agent that retains reusable skills across tasks. After each task, AWM uses an LLM judge to check whether the trajectory succeeded, induces workflows (reusable action sequences such as searching for a product or filtering a report) from the successful trajectories, and adds them to its prompt for later tasks. We run it with the same model (Claude Opus 4.6) on the same 655 tasks. Because AWM learns from the evaluation tasks themselves, it receives more task-specific experience than SAGE's template warm-up. AWM reaches 58.6% overall success, 32.6 points below SAGE (Section 5, Appendix D.3).

Inconsistent crawling cost. The 1.5-hour number reported in the appendix came from an earlier crawler version and has been removed. Table 2 reports the crawler used in our evaluation.

Reviewer_khdzOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The authors focus on the problem that most web agents work step-by-step (an LLM call after each click), which is slow and expensive. The design SAGE that explores a webpage once offline and build a map for it to guide actions without continuously invoking the LLM (unless something goes wrong). The show that SAGE reaches 91% success rate for 655 webarena tasks compared to 82% for Claude code with lower latency and cost.

Critical strengths
  • The SAGE idea is clear and practical. The map helps prepare workflows. It is also a compact form for describing many sites with repeated structure (e.g., social news feeds)

  • The efficiency gains are big.

  • The authors clearly discuss the challenges of planning ahead, e.g., when the site involve search capabilities.

Critical weaknesses
  • Novelty is overstated: no discussion of Agent JIT compilation (ICML'26); memory based agents like AWM and PG-Agent are discussed but to compared quantitatively.

  • The SAGE map is tuned to the test tasks in a warm up phase. At minimum I would like to see the warm up task to be from te different task set than the one used in the evaluation. Note, without warm-up, SAGE seems to be inferior to the baseline.

  • There is manual correction apply to all methods and only corrected results are reported. The repair agent is off during evaluation.

Questions for authors
  • How does SAGE compare to the memory based agents and Agent compilation, assuming similar warmup conditions?

  • What is SAGE's success rate on templates not included in the warm-up?

  • What are initial webArena scores before correction for each method?

1 comment
AuthorsOpenReview ↗

Response to Reviewer khdz

We thank the reviewer for the feedback! The main changes in the paper (marked in blue) are:

  1. A comparison with Agent Workflow Memory (AWM), a new baseline that retains experience across tasks (Section 5, Appendix D.3).
  2. Results with an updated crawler that builds the SMG without any warmup (Appendix D.5).
  3. Clarification of novelty against Agent JIT in Related Work (Section 2).
  4. Success rates of all methods before and after manual review (Appendix D.4).

Q1: How does SAGE compare to the memory based agents and Agent compilation, assuming similar warmup conditions?

Memory-based agents. We have added Agent Workflow Memory (AWM) as a baseline. AWM induces workflows from its own successful trajectories and adds them to its prompt for later tasks. We run it online with the same model (Claude Opus 4.6) on the same 655 tasks, so it builds its memory from the evaluation tasks themselves. By the end of each domain, its memory holds 11 to 24 workflows (Appendix D.3). AWM reaches 58.6% overall, 32.6 points below SAGE, and is 6.1× slower and 10× more expensive per task (Table 1, Figure 4).

Agent Compilation. We have added Agent JIT [Winston et al., 2026] to Related Work (Section 2). Like SAGE, Agent JIT synthesizes a program up front instead of exploring step by step. The two differ in two meaningful ways:

  • Knowledge representation: Agent JIT stores a library of tools synthesized from execution traces, each annotated with pre- and postconditions. SAGE stores a state machine graph of the application's states, operations and transitions. Agent JIT's tool library covers only actions that past traces exercised; the SMG models the application itself, including operations no past task used.
  • Planning: Agent JIT uses generate-and-test. It samples many candidate plans in parallel, rejects those whose tool calls violate the pre- and postconditions, and picks the cheapest valid one; even so, 43% of sampled plans fail validation (Fig. 7 of Winston et al.). SAGE generates one sketch program in a single LLM call and then completes it deterministically. The linker uses the SMG's transitions to find any missing intermediate operations (via BFS) and to check that the plan forms a connected path. If a gap remains, the Planner repairs only that part of the sketch. In our experiments with Claude Opus 4.6, every generated plan was already feasible (Appendix B.2).

Agent JIT also focuses on latency, through cost-based plan selection and parallel scheduling, which is complementary to SAGE. Its WebArena evaluation covers 10 tasks, compared with 655 in ours.

Q2: What is SAGE's success rate on templates not included in the warm-up?

Without warm-up, the SMG from our original crawler reaches 73.1% (Table 2a), on par with Claude Code in every domain except GitLab (55.0% vs. 88.9%). We have since added a phase to the Crawling Agent that tests and repairs the SMG by executing workflows it composes itself, so it no longer needs benchmark tasks for warm-up (Appendix A.2). On GitLab, the new SMG reaches 84.4% success rate without any warm-up, close to the 88.9% with warm-up (Appendix D.5).

Q3: What are initial WebArena scores before correction for each method?

We have added Appendix D.4 which lists the original success rate for each method before correction, as well as examples of tasks that we manually corrected. Overall the ranking of the methods did not change after the correction and the average success rate went up by 8 to 10 percentage points for every method.

Patcher disabled during evaluation. We disable the Patcher during evaluation so that each result reflects a single pass of the synthesized program over a fixed SMG, with no repair or learning at test time. An action that fails at runtime therefore causes the task to fail. This is a conservative setting, as enabling the Patcher would only help failed tasks.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.