Multi-agent memory stops storing steps alone: task dependency graphs become the shared script, topping all six benchmark settings

A multi-agent team's memory no longer stores only what to do; it also stores the prerequisites between steps, so the coordination structure itself becomes a reusable object. Earlier multi-agent memory systems supported information sharing or procedural reuse, but the evolution of shared procedures often stayed disconnected from task dependencies and execution states, and procedural memory built for a single agent did not transfer directly to a team. Across six benchmark settings, three benchmarks under two hosts, SEPM reaches the highest task score among the compared methods; under AutoGen it improves over the no-added-memory baseline by 29.85, 25.86, and 13.00 percentage points.

The mechanism treats the task dependency graph as a common representation for both coordination and memory: nodes are executable steps and directed edges are prerequisites, and retrieved procedures are instantiated into task graphs bound to agent assignments and verified state. During execution a lightweight shared blackboard records structured evidence alongside task dependencies, which supports detecting goal, plan, and world-state divergence and realigning on the basis of evidence. After execution, verified actions and dependencies are distilled into reusable procedures while recurring failures become warnings with triggering conditions; the procedure pool evolves through creation, refinement, specialization, and retirement, guided by success and cost utility and constrained by evidence and safety requirements.

The implementation represents collaborative procedures as directed acyclic graphs of executable steps with explicit prerequisite relations, targeting workflow-oriented collaboration in which task dependencies and relevant execution states can be identified during interaction. Evaluation covers 134 ALFWorld tasks, 812 WebArena tasks, and all 300 OfficeBench tasks, with a supplementary comparison on 100 tasks each in the coding, research, and database environments of MultiAgentBench. The authors propose richer temporal and dependency representations as a natural extension that could broaden applicability to more iterative or less explicit forms of collaboration.

Performance varies substantially with the joint choice of execution and memory model, with score ranges of 35.82, 28.70, and 22.00 percentage points on ALFWorld, WebArena, and OfficeBench, and since execution and memory management change together the experiment measures their joint effect. Component contributions differ by benchmark: on OfficeBench, procedural reuse alone adds only 0.33 points over the blackboard, rising to 3.67 points once alignment is present. The authors also note that more open-ended settings may contain iterative or less explicit coordination structures that the current representation may not cover.