Skip to content

Real-Time Procedural Learning From Experience for AI Agents

🕒 Published (v1): 2025-11-27 03:51 UTC · Source: Arxiv · Venue: ICLR 2026 · link

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

PRAXIS (Procedural Recall for Agents with eXperiences Indexed by State) is a lightweight post-training memory mechanism that enables LLM-based web agents to learn procedures from experience in real time. It retrieves past state-action-result exemplars by jointly matching current environmental and internal agent states to stored episodes. Evaluated on the REAL benchmark, PRAXIS improves accuracy, reliability, and step efficiency across five VLM backbones.

Problem

LLM-based agents lack mechanisms to acquire procedural knowledge (state-dependent action sequences) after deployment. Existing memory systems (Mem0, Letta/MemGPT) focus on factual memory, while experience-based approaches like Reflexion and Agent Workflow Memory encode high-level trajectories without grounding retrieval in live environmental state. A priori SOPs are brittle in fast-changing environments like the web, where interfaces evolve and edge cases are combinatorially intractable to enumerate.

Method

PRAXIS augments an agent's action selection node with a procedural memory store. Each memory entry records: (1) pre-action environment state (M_i^env-pre), (2) agent internal state/directive (M_i^int), (3) action taken (a_i), and (4) post-action environment state (M_i^env-post). At retrieval, candidate memories are scored by IoU between DOM/visual environment state representations multiplied by a length-overlap normalization; top-k candidates are then reranked by embedding similarity of internal states (f(M_i^int), f(Q^int)), and filtered by a similarity threshold Ï„. Retrieved exemplars are injected into the action selection node's context. Memory is accumulated from human demonstrations or live agent trajectories with no fine-tuning required.

Key Contributions

  • State-indexed procedural memory that jointly matches environmental and internal agent state for retrieval, grounded in psychology's state-dependent memory theory
  • A concrete retrieval algorithm (Alg. 1) combining IoU-based environmental matching with embedding-based internal-state reranking and a configurable search breadth k
  • Integration into the Altrina web agent with compatibility across diverse VLM backbones (Llama 4, Qwen3-VL, Gemini 2.5 Flash, GPT-5, Claude Sonnet 4.5)
  • Demonstrated improvements in accuracy, best-of-5 accuracy, reliability, and step efficiency on the REAL benchmark without any model retraining

Results

  • Mean accuracy: 40.3% → 44.1% (average across 5 VLM backbones on REAL), 5 repetitions per task
  • Best-of-5 accuracy: 53.7% → 55.7% on average; per-model gains e.g. Llama 4: 47.3% → 52.7%, Gemini 2.5 Flash: 59.8% → 61.6%
  • Reliability (mean success rate over 5 runs, tasks with ≥1 success): 74.5% → 79.0% average; Claude Sonnet 4.5: 84.4% → 89.0%
  • Steps to completion: 25.2 → 20.2 average across models; Claude Sonnet 4.5: 25.2 → 21.0, Llama 4: 19.8 → 16.2
  • Retrieval breadth ablation: performance scales with k (Gemini 2.5 Flash backbone), plateauing at larger k with minor local crowding dips

Limitations

  • Evaluated only in web browsing environments; generalization to other computer-use domains not yet demonstrated
  • Environmental state encoding uses basic DOM/visual feature overlap and simple similarity metrics; susceptible to superficial interface changes
  • Retrieval breadth k is a fixed hyperparameter; no adaptive mechanism based on uncertainty or compute budget
  • Ablation of k was only run on Gemini 2.5 Flash due to resource constraints
  • No comparison against fine-tuning baselines or online RL approaches; gains over base are moderate (≈4 pp average accuracy)

Relevance to Agentic AI / LLM Agents

PRAXIS directly addresses a critical gap in the agent memory literature: most non-parametric memory work targets factual recall, while PRAXIS targets procedural recall indexed by live environmental state—exactly the form of knowledge needed for robust web and computer-use agents. The state-dependent retrieval design (jointly matching env + internal state) is a principled departure from trajectory-level approaches like Agent Workflow Memory and Synapse, and is directly applicable to any stateful agentic loop. The demonstrated gains in reliability (variance suppression) and efficiency (20% step reduction) are especially relevant for production deployments where cost and consistency matter alongside raw accuracy.