Does state-indexed memory outperform high-level workflow memory for web agents?

PRAXIS distinguishes two kinds of agent knowledge — facts (atomic, context-independent at any moment) and procedures (state-dependent sequences over actions) — and argues procedures are at least as important as facts for real-world deployment yet remain underexplored compared to factual memory frameworks like Mem0 and Letta.

The standard alternative — a-priori procedural specification, where humans write SOPs included in the agent's context — fails for three structural reasons. Many procedures are not fully documented because humans learn by observation rather than reading SOPs. Enumerating all states and edge cases in a combinatorial space is intractable. And procedures become obsolete quickly as environments change. The brittleness intensifies as AI design tools generate novel interfaces that push agents into out-of-distribution states.

PRAXIS's response is a-posteriori learning of procedures from demonstrations or experience, indexed by environment state. The key differentiation from Agent Workflow Memory (see Can agents learn reusable sub-task routines from past experience?), Synapse, and ExpeL — which abstract workflows from successful trajectories at the high-level natural-language workflow tier — is that PRAXIS performs local state-based recall grounded primarily in the live environment state and secondarily to the goal. Memories are indexed with explicit state and action descriptors rather than high-level trajectory summaries, enabling precise recall of minute details that web environments require.

This is a direct architectural disagreement with Can frozen language models learn without updating their parameters? (CLIN: causal-rule memory transfers best) and AWM (workflow-routine memory compounds best). All three target the question "what shape should agent memory take?" and pick different answers — causal rules, abstracted workflows, or local state-action pairs — with PRAXIS arguing the first two abstract too far from the specifics web automation demands.

Empirically, integrating state-dependent memory into the Altrina web agent yields consistent improvements on the REAL benchmark across diverse VLM backbones: higher average accuracy, higher best-of-5, better reliability, fewer steps to completion. An ablation shows gains increase with retrieval breadth k. The structural claim is that reusable local state-to-action priors are what guide robust generalizable behavior — not abstracted workflows that transfer the gist but lose the click-by-click specifics web automation demands.

This note is tagged type: tension because the disagreement with AWM and CLIN is real and unresolved — see ops/tensions/agent memory granularity tension across AWM CLIN and PRAXIS for the cross-paper tension capture.

Source: Tool Computer Use