How does capability-driven self-evolution improve agent memory programs?

Why overall scores hide useful revisions

Self-evolving memory treats an agent's memory as an executable program: the program is evaluated on training tasks, and a language model rewrites its implementation based on task feedback. The paper argues that the dominant holistic approach derives revision directions from feedback mixed across all memory capabilities and judges progress mainly by overall task performance.

That compressed scalar guidance creates two problems the authors name directly. Optimization directions become ambiguous, because mixed feedback combines failures from tasks that require different capabilities and may suggest several conflicting revisions to the same memory component. And capability gains become hidden, because a revision's improvement on one capability can be offset by regressions in others, leaving the overall score flat.

The paper's motivating analysis of M* and EvolveMem evolution traces on BEAM supports both claims. Many revisions improve at least one capability despite a lower overall score, and among revisions that improve one capability, score decreases in another capability are common. Under holistic evolution, the authors argue, exploration stays confined to a limited region of capability space while some capability directions remain underexplored.

Five capabilities that make progress observable

Capability-driven evolution needs a vocabulary that separates recurring memory requirements and makes progress on each one observable. The paper derives five representative capabilities from a broad review of agent memory benchmarks and memory systems: factual retrieval, temporal tracking, preference extraction, multi-session synthesis, and adversarial.

These labels are not free-form. The authors map benchmark question types onto them, so that LoCoMo single-hop and open-domain questions count as factual retrieval, multi-hop as multi-session synthesis, temporal reasoning as temporal tracking, and adversarial questions as adversarial. A single task can require several capabilities at once; resolving conflicting statements about whether a user implemented a project feature, for example, needs factual retrieval to recover both claims plus adversarial handling to recognize the inconsistency.

Annotation is done offline and deliberately excludes the question alone. Question-only annotation with GPT-5.5 on 700 BEAM-1M questions matched the benchmark-type mapping for only 337 questions, or 48.14%. Giving the annotator the question, reference answer, and evidence, GPT-5.5 assigns one primary capability and up to two distinct secondary capabilities. Capability labels are used only to aggregate capability-level feedback and select the next capability to evolve; they are never passed to the memory program, and only training and validation sets are annotated.

Three stages from cold start to integration

PrisMem runs evolution in three stages. Stage I, cold start, evolves from a deliberately simple seed program that appends extracted units in input order and returns their concatenation truncated to the context budget, without query-dependent ranking. The execution environment fixes that output budget at 16,000 characters across evolution runs.

Stage II, capability refinement, selects which capability to work on next using dependency-aware capability selection, which prioritizes targets with potential cross-capability benefits, and refines capability specialists through history-guided diagnosis. A candidate revision is kept only if it improves the selected capability on training data and then passes full-suite evaluation.

Stage III, integration, compares evaluated programs on paired differential cases. For each capability where a specialist beats the current unified program on training data, the algorithm picks the case with the largest gap and records both programs' behavior on it. Trace-guided integration then uses those behavioral differences to consolidate complementary gains into one unified memory program, accepting an integrated program only if it improves overall performance while no capability falls more than a threshold below the unified baseline.

What the 10.54-point gap measures

The headline result is a comparison against the strongest baselines, not against the seed program: PrisMem outperforms them by 10.54 percentage points on BEAM-1M and 7.83 percentage points on LongMemEval-M. Both benchmarks involve million-token histories, which is the setting the paper claims as its demonstration of effectiveness.

The two numbers belong to different benchmarks and should not be averaged or treated as one effect size. They are also aggregate margins over the strongest baseline on each benchmark, not per-capability improvements, and the paper reports capability-level results separately by grouping the test set with native benchmark types.

The capability vocabulary itself is an initial instantiation rather than a fixed standard: the authors describe the five capabilities as derived from a broad review of benchmarks and systems, and note that individual questions may involve additional capabilities beyond their primary and secondary labels.

Reducing the cost of repeated evaluation

Self-evolution repeatedly revises and evaluates memory programs, which incurs substantial inference cost. The paper reduces this in two ways. Compact diagnostic contexts strip redundant content from diagnostic cases while marking omissions and retaining snippets relevant to the question and answer; on PrisMem's real traces from BEAM and LongMemEval, average case-context size falls from 16,776 to 9,428 tokens, a 43.8% reduction.

Revision-aware execution reuse exploits the fact that a local revision leaves most of the pipeline unchanged. Because the memory program is decomposed into Extraction, Indexing, Planning, Retrieval, and Answer components, a candidate can be compared with its parent and re-execution can begin at the earliest affected stage. A retrieval-only change can reuse extracted units and the built memory, while a changed extraction instruction requires new units and all downstream computation.

Generated revisions are also validated before task-model calls are spent. Checks run from inexpensive source inspection to bounded synthetic execution: source and module completeness, schema and signature compatibility, functional smoke tests against a local stub backend, and synthetic complexity checks indexing roughly 2,000 synthetic units across 100 batches with 4096-dimensional embeddings.

Where these gains should not be extended

The reported margins come from BEAM-1M and LongMemEval-M, and the paper's framing ties them to million-token histories. Nothing in the evidence establishes the same margins on shorter histories, on other benchmarks, or on memory systems outside this executable-program interface.

The capability labels are also study-specific. They were derived to separate recurring memory requirements and make progress observable, and the authors present them as an initial step toward capability-driven evolution rather than a settled taxonomy. Because labels are used only for aggregating feedback and selecting the next capability, and are never passed to the memory program, the evolved program at test time receives the same history and question as the baselines.

The annotation procedure carries its own boundary: question-only labeling matched the benchmark-type mapping for only 48.14% of 700 BEAM-1M questions, which is why the annotator is given the reference answer and evidence. That makes annotation depend on labeled training and validation data, and the paper states no annotation is needed for the test set.

The priority is capability-level selection

The decision this paper pushes toward is not whether to evolve memory at all, but at what granularity to steer and judge it. Holistic evolution optimizes one overall score and can plateau while individual capability directions stay underexplored; capability-driven evolution keeps a per-capability record, selects the next target by potential cross-capability benefit, and only then integrates specialists under a constraint that no capability regress beyond a threshold.

For readers weighing this approach, the operative comparison is between a single aggregate score and a capability vector. The paper's evidence for that comparison is the BEAM trace analysis showing revisions that improve at least one capability while lowering the overall score, plus the 10.54 and 7.83 percentage-point margins on BEAM-1M and LongMemEval-M. The practical threshold it introduces is the integration acceptance rule: an integrated program must beat the unified baseline overall while keeping every capability within the allowed relative drop.

Sources used in this answer