Large language model agents accumulate experience in memory, and how that memory evolves during interaction is as important as what it stores. Recent methods update memory online, yet both the operators that transform memory and the rules that select them remain fixed by design. We propose EvoDisco, which formulates agent memory evolution as evolutionary strategy discovery: the agent must discover which operator to apply, when to apply it, and how to instantiate it, rather than rewriting memory under a static operator schedule. A learnable policy conditions on the current memory state and recent task history, then selects and instantiates one of four semantic operators---Abstract, Refine, Bridge, and Reframe---which respectively compress related memories, decompose overloaded entries, connect weakly linked experiences, and reorganize retrieved reasoning chains. The policy is updated with a bi-level fitness. An inner signal scores each transformation using a retrieval-quality improvement regularized by memory complexity. An outer signal scores strategic efficacy over a window of past decisions, combining historical operator-utility regret, utility-prediction error, and selection diversity. Under a one-pass online plus frozen-transfer protocol on ALFWorld, WebShop, and LifelongAgentBench (OS and DB), EvoDisco improves over strong memory baselines including MemP and MemRL. The largest gains are on ALFWorld (+8.8 online / +12.9 frozen-transfer points over MemP; +16.4 / +17.9 over MemRL). Ablations attribute these gains to both fitness levels and the operator library.
Figures & tables
Figure 1: Overview of EvoDisco. A frozen language model interacts with a one-pass task stream, retrieves a subgraph, and writes new memories after each episode. A strategy policy reads the memory-graph state and selects one of four operators— Abstract , Refine , Bridge , and Reframe —which the operator executor applies to the graph. Immediate utility scores each edit by the change in retrieval quality regularized by graph complexity. Every N events, strategic efficacy combines operator-utility regret, utility-prediction error, and selection diversity, and updates the policy. Evolution runs only before the cutoff; afterward the agent continues to write memories. Held-out evaluation freezes the accumulated memory.
ALFWorld
WebShop
OS
DB
Method
Online
Transfer
Online
Transfer
Online
Transfer
Online
Transfer
No Memory
56.7
52.9
32.2
32.5
67.7
72.7
88.1
84.9
RAG
60.8
70.0
29.8
33.0
70.9
72.0
80.9
72.7
Self-RAG
56.0
62.9
31.8
32.5
69.7
74.7
85.3
84.2
Mem0
58.0
57.9
29.6
28.0
67.7
71.3
85.9
86.3
MemP
68.9
75.7
31.4
34.0
71.7
76.0
83.1
73.4
Table 1: Online and frozen-memory transfer success rates (%). Online SR is measured over the full training stream. Transfer SR is measured on the held-out split with all memory writes and evolution disabled. Bold denotes the highest value in each column.
Variant
Online
Transfer
Δ Transfer
EvoDisco (Full)
77.7
88.6
—
w/o Outer Fitness
75.3
80.7
−7.9
w/o Inner Fitness
76.0
79.3
−9.3
w/o Cognitive Operators
76.3
82.1
−6.5
Fixed Abstract
76.0
85.7
−2.9
Fixed Refine
75.2
81.4
−7.2
Table 2: ALFWorld ablations. Online and Transfer denote success rates (%). Δ Transfer is the difference from Full in percentage points. Bold denotes the highest success rate in each column.
Policy Training
WebShop
OS
DB
ALFWorld
31.0
75.3
82.7
Target Benchmark (Full)
35.0
77.3
87.1
Δ Transfer
−4.0
−2.0
−4.4
Table 3: Cross-benchmark transfer of the operator-selection policy. Values are frozen-memory transfer success rates (%). The ALFWorld-trained policy is held fixed while each target graph is constructed from scratch. Δ Transfer is relative to the target-trained Full model, in percentage points.
Appendix figures & tables10 assets
Supplementary material from the paper’s appendix.
Appendix
Level
Signal
Learning role
Frequency
Inner
Ui
Feedback and supervision
Each attempt
Outer
Ei
Strategy-policy update
Every N attempts
Appendix
Table 4: Two timescales of evolution feedback. Graph modification is performed by operator execution.
Symbol / Name
Value
Description
α
1.0
Immediate-utility weight on the online performance proxy ΔF=ΔQ
β
0.3
Immediate-utility weight on structural-complexity change ΔC
γ
1.0
Strategic-efficacy weight on Regret
δ
1.0
Strategic-efficacy weight on PredErr
η
0.3
Strategic-efficacy weight on operator diversity
K
20
Strategic-efficacy window size
Appendix
Table 5: Hyperparameters used in the reported EvoDisco experiments.
Benchmark
Online n
Transfer n
Max steps
ALFWorld
3553
140
50
WebShop
500
200
15
LifelongAgentBench-OS
350
150
15
LifelongAgentBench-DB
361
139
15
Appendix
Table 6: Split sizes and per-episode step budgets.
Variant
Online
Xfer
Δ Xfer
EvoDisco (Full)
74.0
77.3
—
w/o Outer Fitness
71.1
75.3
−2.0
w/o Inner Fitness
69.1
74.0
−3.3
w/o Cognitive Operators
71.7
74.0
−3.3
Fixed Abstract
72.0
74.0
−3.3
Fixed Refine
72.9
75.3
−2.0
Appendix
Table 7: OS ablations (%). Deltas are relative to Full (Table 1 ). Best in each column is bold.
Method
ALFWorld
WebShop
OS
DB
No Memory
58.6
31.0
71.4
86.1
RAG
69.1
28.0
75.7
80.6
Self-RAG
63.4
31.0
71.4
84.7
Mem0
62.7
26.0
70.0
81.9
MemP
74.7
30.0
77.1
80.6
MemRL
67.4
29.0
71.4
83.3
Appendix
Table 8: Success rates (%) over the final 20% of the online stream. Memory evolution is disabled during this interval, while ordinary memory writes remain enabled. Bold denotes the highest value in each column, including ties.
Figure 2: Cumulative online success rate over the training stream. Each point is the success rate on all episodes observed so far. The shaded interval is the final 20% , during which memory evolution is disabled and ordinary memory writes continue. EvoDisco separates from every baseline on ALFWorld and finishes highest on all four benchmarks. On WebShop and DB the curves overlap for much of the stream, and the final margins are small.
Benchmark
Abstract
Refine
Bridge
Reframe
Total
Updates
ALFWorld
7
117
69
164
357
80
OS
3
9
9
11
32
7
Appendix
Table 9: Applied operator counts. Attempts that do not commit an edit are excluded. Updates are policy-gradient steps, one every N=5 attempts.
Figure 3: Applied operators. (a) ALFWorld, five equal bins of the evolution window (first 2842 episodes). (b) Totals on ALFWorld ( 357 commits) and OS ( 32 commits). Abstract is confined to the early ALFWorld bins. Reframe is the most frequent commit on both benchmarks.
Figure 4: ALFWorld strategic-efficacy terms once the window contains K=20 attempts (events 20–400), including Abstract attempts that do not commit. (a) PredErr and Regret on the utility scale (Eqs. equation 10 and equation 9 ). (b) Operator entropy Div in nats (Eq. equation 11 ). The gray line is log4 , the maximum over four operators. A one-operator window has entropy 0 .
Figure 5: Two applied edits from the Table 1 runs, read left to right: the graph fragment before the edit, the operator that was applied, the structure written into the graph, and a later retrieval. (a) ALFWorld. Abstract ( k=1 ) links a meta-strategy to a 13-note neighborhood and prunes nothing. Five of the six linked notes remain in the frozen graph and are shown. At stream position 1579, a new statue-to-coffeetable episode retrieves only that strategy and succeeds in 9 steps. The same game reaches the 50-step limit under No Memory, RAG, Self-RAG, Mem0, and MemP. (b) OS. Refine (categorical, m=4 ) splits one log-backup procedure into four children and keeps the parent. At stream position 170, the instruction to copy .log files from /var/log into /backup retrieves the copy child, that parent, and one other copy note, and succeeds in 3 steps. The same five systems fail that instruction.