Real-Time Procedural Learning From Experience for AI Agents

AI summary

Overview

Research area: AI agents / LLM-based agent memory and post-training learning, applied to web browsing and computer-use environments.

Technical level: Intermediate. The paper assumes familiarity with LLM agents, retrieval-augmented generation, and web benchmarks, but its core idea is explained in plain terms.

Scope: The paper proposes and evaluates PRAXIS, a state-indexed procedural memory that lets an existing web agent learn "how to do things" from its own past episodes at inference time, tested on the REAL web browsing benchmark across five vision-language model backbones.

What This Paper Is About

Most LLM-based agents can learn facts after deployment but have no practical mechanism to learn procedures — the state-dependent sequences of steps that accomplish real goals, such as checking out on an e-commerce site or troubleshooting a failed login. Writing these procedures down in advance (as standard operating procedures) is brittle because many procedures are undocumented, the space of possible states and edge cases is combinatorial, and web interfaces change quickly. PRAXIS instead learns procedures a posteriori, by storing the consequences of past actions and retrieving them when the agent encounters a similar environmental and internal state.

Key Contributions

1. State-dependent procedural memory. The paper introduces PRAXIS (Procedural Recall for Agents with eXperiences Indexed by State), a lightweight post-training learning mechanism that indexes memory entries by both the environment state and the agent's internal state (including the overall directive it is pursuing), and retrieves past action outcomes by jointly matching both to the current state. The design is explicitly inspired by state-dependent memory in psychology (Tulving and Thomson, 1973; Bower, 1981).

2. A concrete retrieval algorithm. Each memory entry stores the pre-action environment state, the agent's internal state, the action taken, and the post-action environment state. Retrieval (Algorithm 1) computes an environment similarity score using intersection-over-union over environment states multiplied by a length-overlap term, then re-ranks the top-k candidates by embedding similarity of internal states, and finally keeps only candidates above a similarity threshold τ.

3. An integration into a deployed agent. PRAXIS was added to the action selection node of Altrina, a frontier computer-use agent (previously known as Tessa), which orchestrates foundation models with a "node-based" architecture and can perceive the environment visually and as compressed text.

4. A multi-backbone evaluation on REAL. The method was benchmarked on the REAL benchmark — deterministic clones of 11 commonly used sites with 112 everyday tasks, using programmatic state checks for action tasks and rubric-guided natural language evaluation for information retrieval tasks — across Llama 4, Qwen3-VL, Gemini 2.5 Flash, GPT-5, and Claude Sonnet 4.5 backbones.

Main Findings

• Accuracy improved (average 40.3% to 44.1%). Across models, mean accuracy on REAL over five repetitions rose from 40.3% without procedural memory to 44.1% with it.
• Best-of-5 accuracy improved (average 53.7% to 55.7%). Per-model: Llama 4 47.3 to 52.7, Qwen3-VL 44.6 to 47.3, Gemini 2.5 Flash 59.8 to 61.6, GPT-5 56.2 to 57.1, and Claude Sonnet 4.5 60.7 to 59.8 (the one backbone that did not improve).
• Reliability improved (74.5% to 79.0%). Reliability is defined as the mean success rate over five repetitions of a task, averaged over all REAL tasks with at least one successful run in the five repetitions. The authors attribute this to memory traces biasing model decisions toward previously successful trajectories under similar states, suppressing stochastic variance.
• Efficiency improved (25.2 to 20.2 steps). Steps-to-completion, averaged over tasks with at least one successful run across five repetitions, fell from 25.2 to 20.2 across models. Per-model: Llama 4 19.8 to 16.2, Qwen3-VL 27.7 to 20.8, Gemini 2.5 Flash 28.9 to 22.3, GPT-5 24.2 to 20.7, Claude Sonnet 4.5 25.2 to 21.0.
• Retrieval breadth helps, up to a plateau. Ablating the retrieval breadth k (Algorithm 1) on the Gemini 2.5 Flash backbone only, the authors found performance generally increased in steps as breadth grew, with slight decreases within each step, converging to a plateau — suggesting some local context crowding but increasingly helpful generalizable context at larger scale.
• Preliminary generalization to unseen tasks. The abstract reports preliminary generalization to unseen tasks in similar environments; no numeric value for this generalization is reported. Statistical significance tests are also not reported.
• Context on the benchmark baseline. Prior benchmarking reported that frontier models with naïve scaffolding achieve at most ~41% success on REAL, which the authors cite as room for post-training procedural learning.

Methodology in Plain English

The researchers took an existing web agent and gave its action-selection step an extra source of information: a memory of past experiences.

Every time the agent does something, the system records a package: what the environment looked like before the action, what goal the agent was pursuing and its internal state at the time, what action it took, and how the environment changed afterward.

When the agent later faces a new state, it does not search memory by goal alone. It first compares the current environment description against stored environment descriptions using a visual/textual overlap measure (intersection-over-union) scaled by how similar the two descriptions are in length. It takes the top k matches by that environment score, then re-ranks those candidates by how similar the stored internal states are to the current internal state, using embeddings and a similarity threshold. The survivors are inserted into the action node's context as concrete state-action-result exemplars.

The evaluation used the REAL benchmark, which provides deterministic clones of real websites so results are reproducible, and runs each configuration five times so that reliability and best-of-5 accuracy can be separated from single-run average accuracy. Five different vision-language model backbones were swapped in for the agentic compute nodes to test whether the gains were model-specific. The authors also swept the retrieval breadth k to see how much memory context helps; this ablation was limited to the Gemini 2.5 Flash backbone because of resource limitations.

Why This Matters

Impact on research. The paper argues that post-training learning of procedures is underexplored relative to factual memory work (Mem0, Letta, MemoryBank, A-MEM) and to self-reflection methods (Reflexion, Self-Refine, CLIN) that do not encode environmental state. It also distinguishes itself from workflow-memory approaches (Agent Workflow Memory, Synapse, ExpeL) by indexing memories with explicit state and action descriptors rather than high-level trajectories, and by grounding recall primarily in the live environment state rather than the goal. The result is a reusable local state-to-action prior that improved accuracy, best-of-5 accuracy, reliability, and step count on the same benchmark.

Real-world applications:

• Web automation where interfaces change often — seasonal pop-ups, redesigns, and newly generated layouts push agents into out-of-distribution states where pre-written procedures fail.
• Personalized agents that learn a specific user's or organization's way of doing tasks without that knowledge being trained into a shared model.
• Enterprise workflows where conventions are learned by observation rather than documented, so no SOP exists to hand the agent.
• Computer-use agents more broadly, since the authors state the approach is conceptually agnostic to the environment.

Industry relevance. The discussion frames personalized learning as critical to economic adoption: rather than replacing humans, agents are envisioned working alongside them, and each user should be able to decide whether to share private knowledge with the world. That makes methods that customize agents in real capabilities — not just superficially — central to deployment. The authors also note that as AI-based design tools generate and update web platforms, economic value shifts toward novel, previously unseen interfaces, making a priori SOPs brittle.

Future Directions

1. Beyond web environments. State-dependent memory is described as conceptually agnostic to the environment and naturally extensible to general agentic computer use.
2. Richer state encoding. The current proof-of-concept uses basic visual and DOM feature overlap with simple similarity metrics; a richer encoder could improve retrieval quality and invariance to superficial changes.
3. Adaptive retrieval mechanisms. Instead of fixed state-similarity heuristics, retrieval could account for real-time factors such as uncertainty and compute budget, and be iterative in highly uncertain scenarios.
4. From action agents to alignment agents. PRAXIS could use user preference, rather than only objective task success or failure, as the training signal where no objective standard exists — observing user inputs and feedback over time and converging on a procedural memory that encodes how that user prefers a task to be done.

Target Audience

Researchers and engineers working on LLM-based agents, agent memory, and web or computer-use automation; practitioners who need agents to adapt to changing interfaces or to learn organization-specific procedures after deployment; and readers interested in state-indexed retrieval as an alternative to factual memory stores, self-reflection buffers, and workflow-level memory abstractions.

Authors’ abstract

Learning how to do things from trial and error in real time is a hallmark of biological intelligence, yet most LLM-based agents lack mechanisms to acquire procedural knowledge after deployment. We propose Procedural Recall for Agents with eXperiences Indexed by State (PRAXIS), a lightweight post-training learning mechanism that stores the consequences of actions and retrieves them by jointly matching environmental and internal states of past episodes to the current state. PRAXIS augments agentic action selection with retrieved state-action-result exemplars that are generated in real time. When evaluated on the REAL web browsing benchmark, PRAXIS improves task completion accuracy, reliability, and cost efficiency across different foundation model backbones, and shows preliminary generalization to unseen tasks in similar environments. These results demonstrate that PRAXIS enables the practical adoption of AI agents in fast-evolving stateful environments by helping them learn new procedures effectively.