Self-Evolving Multi-Agent Systems via Decentralized Memory (DecentMem)

| Item | Details | |------|---------| | Paper title | Self-Evolving Multi-Agent Systems via Decentralized Memory | | Authors | Guangya Hao, Yunbo Long, Zhuokai Zhao | | arXiv ID | 2605.22721 | | Published | May 21, 2026 | | Category | cs.MA (Multi-Agent Systems) | | Key finding | DecentMem, a decentralized dual-pool memory framework, enables self-evolving MAS: each agent maintains an exploitation pool and an exploration pool, dynamically reweighted by LLM-as-judge feedback. Theoretically O(log T) cumulative regret; empirically up to +23.8% accuracy and up to 49% fewer tokens. |

1. The Three Curses of Centralized Memory

Multi-agent systems (MAS) share a default assumption: memory must be shared. Nearly all existing MAS frameworks—AutoGen, DyLAN, AgentNet—use a central memory repository that all agents write to and retrieve from.

But this design carries three curses:

1. Communication overhead. When 10 agents read and write the same memory store, coordination costs grow quadratically. Each agent must verify whether experiences are duplicated and relevant—not free operations. 2. Privacy collapse. Centralized memory lets any agent see every other agent's full experience history. Sometimes that helps collective learning; other times one agent's failed strategy gets blindly copied, homogenizing the system. 3. Diversity collapse. The most fatal: with shared memory, agent policies converge. Six agents become six copies of one agent—destroying the very diversity (perspectives, methods, failure modes) that gives MAS its value.

2. Dual Pools: The Marriage of Exploitation and Exploration

DecentMem's solution is elegantly simple: each agent maintains two memory pools.

• Exploitation Pool: trajectories this agent has successfully executed—verified strategies, correct reasoning paths, action sequences that led to good outcomes. An archive of "what I know works."
• Exploration Pool: candidate strategies created by an LLM generator based on the agent's current knowledge blind spots. Unverified, but covering context space the agent hasn't explored—a preview of "what I don't know but maybe should try."

An LLM-as-judge dynamically reweights the two pools. When exploitation-pool trajectories perform well in recent rounds, the judge raises their retrieval weight. When they start failing (indicating a shift in environment or task distribution), the judge shifts weight to the exploration pool, prioritizing new strategies.

This is an exploration-exploitation tradeoff running in real time—not manually tuned at the algorithm level, but automatically at the memory-retrieval level.

3. Theoretical Guarantee: O(log T) Regret

The authors prove DecentMem guarantees global reachability of the solution space (any agent set can reach any solution via the exploration pool) and achieves O(log T) cumulative regret.

What does O(log T) mean? In online learning, T is the number of time steps, and regret measures the gap between the loss of your chosen strategies and the best strategy in hindsight. O(log T) growth means your policies approach the optimum over time—each doubling of time adds only a constant amount of regret.

Crucially, O(log T) matches the theoretical lower bound for stochastic bandits: DecentMem's memory-management efficiency has touched the information-theoretic limit—you cannot do better than O(log T) mathematically.

4. +23.8% Accuracy and −49% Tokens

DecentMem was validated on three dimensions:

• Multi-framework: consistent gains across AutoGen, DyLAN, AgentNet.
• Multi-model: consistent across five backbones—Qwen3 4B/8B/14B, Gemma4 E2B/E4B.
• Multi-task: consistent across five benchmark domains—math, code, QA, embodied tasks.

Results:

• Up to +23.8% average accuracy over the strongest centralized-memory baseline
• Up to +52.5% over memoryless baselines
• Up to 49% reduction in token consumption

Token savings matter because in MAS, every agent burns tokens retrieving from memory. Centralized memory means every agent rummages through the same huge fridge—reading in and discarding lots of irrelevant information. Decentralized memory means each agent searches only its own small fridge.

5. Honest Limitations

• Judge cost not fully accounted. The 49% token saving is at retrieval; the LLM-as-judge's own inference cost isn't fully included in the comparison, and its share of the overall token budget is not clearly reported.
• Pool capacity unaddressed. Do exploitation pools grow indefinitely with long runs? Does retrieval efficiency degrade? Is a forgetting mechanism needed? Long-term memory management isn't covered.
• Interaction quality not evaluated. Whether inter-agent "conversational diversity" is genuinely higher under DecentMem than centralized memory is implied but not directly measured.
• Framework fit unknown. All three MAS frameworks required substantial modification to adopt DecentMem; the paper doesn't compare which framework benefits most, or whether some framework traits are naturally more compatible.

Closing Thought

Centralized memory is seductive—"put all knowledge together and be smart." But agents differ in role, context, and the experience they need. DecentMem is a reminder that sometimes separating things is smarter than pooling them—like a library: piling all books into one heap isn't the best retrieval system. Separate by topic, maintain per-shelf indexes, and you find what you want faster.