Decentralized Memory Boosts Multi-Agent Accuracy by 23.8%: The DecentMem Framework

Paper Overview

| Item | Detail | |------|--------| | Paper | 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-evolution in MAS: each agent maintains an exploitation pool and an exploration pool, dynamically reweighted via LLM-as-judge feedback. Theoretically achieves O(log T) cumulative regret; in practice, up to 23.8% accuracy gain and up to 49% token savings. |

1. The Triple Curse of Centralized Memory

Multi-agent systems (MAS) carry a default assumption: memory must be shared. Almost all existing MAS frameworks — AutoGen, DyLAN, AgentNet — use a centralized memory repository where all agents write experiences and retrieve from a common store. But this design suffers three curses:

• Communication overhead. When 10 agents read and write to the same memory store, coordination costs grow quadratically. Verifying "has this experience already been written?" and "is this relevant to my task?" is not free.
• Privacy collapse. Centralized memory lets every agent see every other agent's full history. A failed strategy from one agent can be blindly copied by another, homogenizing the whole system.
• Diversity collapse. The most fatal one: with shared memory, agents' policies converge. Six agents can start behaving like six copies of one agent — destroying the diversity that gives MAS its value.

2. Dual Pools: Marrying Exploitation and Exploration

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

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

An LLM-as-judge dynamically reweights the two pools. When exploitation trajectories perform well recently, the judge raises their retrieval weight. When they start failing (indicating a shift in environment or task distribution), weight shifts to the exploration pool. The exploration-exploitation tradeoff happens automatically at the memory-retrieval level rather than through manual algorithmic tuning.

3. Theoretical Guarantee: O(log T) Regret

The authors prove DecentMem guarantees global reachability of the solution space and achieves O(log T) cumulative regret. In online learning, regret measures the gap between your chosen policy's loss and the best policy in hindsight. O(log T) means the policy converges toward optimal — each doubling of time adds only a constant amount of regret. This matches the theoretical lower bound of stochastic bandits: mathematically, you cannot do better than O(log T).

4. Results: +23.8% Accuracy, −49% Tokens

DecentMem was validated across:

• Frameworks: AutoGen, DyLAN, AgentNet — consistently effective on all three mainstream MAS frameworks.
• Models: Qwen3 4B/8B/14B, Gemma4 E2B/E4B — consistent across five backbones of different scales.
• Tasks: math, code, QA, embodied tasks — consistent across five benchmark domains.

Results:

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

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

5. Honest Limitations

1. Judge costs not fully counted. LLM-as-judge adds inference cost; the 49% savings are at the retrieval level, and the judge's contribution to the overall token budget is not clearly reported. 2. No capacity bounds discussed. Does the exploitation pool grow unboundedly over long runs? Does retrieval efficiency degrade? Is a forgetting mechanism needed? Long-term memory management is not covered. 3. Interaction quality unmeasured. The paper implies diversity collapse is avoided but does not directly measure whether agent-to-agent conversational diversity is actually higher than under centralized memory. 4. Framework fit unclear. All three frameworks required substantial modification; the paper does not compare which framework benefits most from decentralized memory.

Takeaway

The temptation of centralized memory — "put all knowledge together, that's smartest" — ignores a basic fact: different agents play different roles, face different contexts, and need different experiences. DecentMem reminds us that sometimes separating things is smarter than pooling them. Like a library: piling all books into one heap is not the best retrieval strategy — organizing by topic, with each shelf maintaining its own index, lets you find what you want faster.