Paper deep dive
M$^\star$: Every Task Deserves Its Own Memory Harness
Wenbo Pan, Shujie Liu, Xiangyang Zhou, Shiwei Zhang, Wanlu Shi, Mirror Xu, Xiaohua Jia
Intelligence
Status: succeeded | Model: google/gemini-3.1-flash-lite-preview | Prompt: intel-v1 | Confidence: 97%
Last extracted: 4/15/2026, 1:15:39 AM
Summary
M* is a framework that automatically discovers task-optimized memory harnesses for LLM agents by representing memory systems as executable Python programs. It uses a reflective code evolution method, combining population-based search and LLM-guided debugging to jointly optimize data schemas, storage logic, and agent workflow instructions, outperforming fixed-memory baselines across diverse benchmarks.
Entities (6)
Relation Signals (5)
M* → evaluatedon → LoCoMo
confidence 100% · We evaluate M* on four distinct benchmarks spanning conversation... LoCoMo
M* → evaluatedon → ALFWorld
confidence 100% · We evaluate M* on four distinct benchmarks... ALFWorld
M* → evaluatedon → HealthBench
confidence 100% · We evaluate M* on four distinct benchmarks... HealthBench
M* → evaluatedon → PRBench
confidence 100% · We evaluate M* on four distinct benchmarks... PRBench
GPT-5.4 Mini → usedas → Task Agent
confidence 100% · We use GPT-5.4 Mini as the task agent
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Large language model agents rely on specialized memory systems to accumulate and reuse knowledge during extended interactions. Recent architectures typically adopt a fixed memory design tailored to specific domains, such as semantic retrieval for conversations or skills reused for coding. However, a memory system optimized for one purpose frequently fails to transfer to others. To address this limitation, we introduce M$^\star$, a method that automatically discovers task-optimized memory harnesses through executable program evolution. Specifically, M$^\star$ models an agent memory system as a memory program written in Python. This program encapsulates the data Schema, the storage Logic, and the agent workflow Instructions. We optimize these components jointly using a reflective code evolution method; this approach employs a population-based search strategy and analyzes evaluation failures to iteratively refine the candidate programs. We evaluate M$^\star$ on four distinct benchmarks spanning conversation, embodied planning, and expert reasoning. Our results demonstrate that M$^\star$ improves performance over existing fixed-memory baselines robustly across all evaluated tasks. Furthermore, the evolved memory programs exhibit structurally distinct processing mechanisms for each domain. This finding indicates that specializing the memory mechanism for a given task explores a broad design space and provides a superior solution compared to general-purpose memory paradigms.
Tags
Links
- Source: https://arxiv.org/abs/2604.11811v1
- Canonical: https://arxiv.org/abs/2604.11811v1
Trouble viewing inline? Open PDF directly →
Full Text
86,499 characters extracted from source content.
Expand or collapse full text
M ⋆ : Every Task Deserves Its Own Memory Harness Wenbo Pan 1∗ Shujie Liu 2 Xiangyang Zhou 2 Shiwei Zhang 2 Wanlu Shi 2 Mirror Xu 2 Xiaohua Jia 1 1 City University of Hong Kong 2 Microsoft Task: Legal Queries Neighbor's fence is 3ft onto my property (15+ yrs). They claim rights from deed language. Texas. What are my legal options? Memory: Legislation DB STATESTATUTELIMIT Texas§16.02610 yr Florida§95.187 yr Calif.CCP §3255 yr Texas? §16.026, 10yr Agent Permissive use does not qualify under §16.026. File a quiet title action to resolve this. RAG +entity SQL index +entity-fact index +IDF weighting +9- f ield schema +triage scoring +token scoring − in-memory +SQLite +action cache +multi-signal scoring +source dedup +schema expansion +faceted domains +scenario scoring +escalation f ields +dual-mode LLM +entity key matching +completion criteria +state-tool tracking +state change tracking +synonym normalization +jurisdiction f ilter +atomic facts +intent detection +person tracking +semantic search +fuzzy matching +quantity tracking +quantity f ield +special requirement +IDF weighting +quote tracking +slot sanitization +procedural f ields +anchor enforcement +retrieval signals +faceted retrieval +activity schema f ix: score bug +multi-jurisdiction No Memory RAG Cheatsheet +TF-IDF ranking +SQLite retrieval +red_ f lags f ield +deterministic scoring − LLM +SQL scoring +LLM synthesis +co-occurrence scoring +relation extraction +source diversify +lexical index +location tracking +legal reasoning +fact indexing +environment f ield +precedent tracking +decision completeness +forum boosts +schema f ields +deadline tracking RAG RAG Cheatsheet +metadata hybrid +structured schema +token index − compression +excerpting +source location +source quality +speaker tracking − context window No Memory No Memory +hybrid retrieval +SQL retrieval +multi-factor scoring +authority detection No Memory +entity scoring +hybrid scoring Cheatsheet Cheatsheet General Memory Program Conversation (LoCoMo) Healthcare (HB) Embodied AI (ALFWorld) Legal (PRBench) Task: Conversations Jon I dance to destress Gina Dancing helps me relax How do they both destress? Memory: Entity Graph destress relax lost job lost job started started opened Jon Gina dancing banker DoorDash business studio Agent Both Jon and Gina like to destress by dancing, as mentioned in sessions 3 and 5. Task: Embodied Actions > Put a clean mug in cabinet Memory: Trajectory Lookup bat → pick up → bed plate → sink → clean → cabinet ▸mug → sink → clean → cabinet apple → microwave → heat → fridge bread → fridge → cool → counter Agent go to sink → clean mug → go to cabinet → put mug in cabinet ✓ Task: Medical QA LDL: 92HDL: 64 Age: 45FLipid panel Is her cholesterol in normal range? Memory: Checklist Templates LDL HDL Total chol. Triglyc. Agent Incomplete: total cholesterol and triglycerides missing. Cannot confirm normal range. Figure 1: Evolved memory harnesses across tasks. Starting from shared seeds (center), MSTAR evolves structurally distinct harnesses for each task. Each node is an evolved program. AbstractLarge language model agents rely on specialized memory systems to accumulate and reuse knowledge during extended interactions. Recent architectures typically adopt a fixed memory design tailored to specific domains, such as semantic retrieval for conversations or skills reused for coding. However, a memory system optimized for one purpose frequently fails to transfer to others. To address this limitation, we introduce MSTAR, a method that automatically discovers task-optimized memory harnesses through executable program evolution. Specifically, MSTAR models an agent memory system as a memory program written in Python. This program encapsulates the data Schema, the storage Logic, and the agent workflow Instructions. We optimize these components jointly using a reflective code evolution method; this approach employs a population-based search strategy and analyzes evaluation failures to iteratively refine the candidate programs. We evaluate MSTAR on four distinct benchmarks spanning conversation, embodied planning, and expert reasoning. Our results demonstrate that MSTAR improves performance over existing fixed-memory baselines robustly across all evaluated tasks. Furthermore, the evolved memory programs exhibit structurally distinct processing mechanisms for each domain. This finding indicates that specializing the memory mechanism for a given task explores a broad design space and provides a superior solution compared to general-purpose memory paradigms. ∗ Correspondence to: wenbo.pan@my.cityu.edu.hk Preprint. Under review. arXiv:2604.11811v1 [cs.PL] 10 Apr 2026 1 Introduction Agentic systems powered by large language models (LLMs) require memory mechanisms to accumu- late and reuse knowledge across extended interactions. Consequently, recent studies have extensively investigated memory systems designed specifically for LLM agents. A prevailing trend provides agents with different solutions to solve distinct problems, which we refer to as an agent memory harness. For example, a conversational agent relies on semantic matching or retrieval-augmented generation paradigms to perform iterative retrievals for recalling messages across sessions. Mean- while, a web browsing or coding agent uses skill systems to reuse workflows discovered from past tasks and updates these skills when necessary. Furthermore, specialized agents for expert domains frequently use dedicated memory systems, such as relational databases, combined with specific workflows. However, a memory harness designed for one purpose often fails to transfer effectively to other purposes. As a result, a critical question remains unresolved: how can we discover the most suitable memory harness for a given task? To address this question, we propose MSTAR, an evolutionary method that automatically discovers task-optimized memory harnesses for LLM agents. Specifically, MSTAR expresses any memory harness as a memory program, which is a Python protocol implementation. This program encompasses a Schema defining what to store and retrieve, Logic dictating how to read and write data, and Instructions providing workflow guidance for the agent to execute retrievals and queries. These components are jointly optimized through executable program evolution. Although previous work has attempted to evolve memory systems by optimizing content, combining modules, or evolving prompts, their design spaces typically focus on only a single aspect of memory. Therefore, they are not designed to find corresponding memory harnesses for arbitrary tasks. Because finding an optimal design within an open space of memory harnesses is challenging, we design a reflective code evolution method to efficiently and effectively iterate and improve the memory program. This method uses an LLM-based reflector to debug evaluation failures and propose targeted improvements. In addition, it employs a population-based search strategy to balance exploration and exploitation, applying evolutionary constraints to ensure program quality. We apply MSTAR to four distinctly different benchmarks (LoCoMo, ALFWorld, HealthBench, and PRBench), evaluating its performance against nine competitive baselines across three memory paradigms. Our results indicate that MSTAR achieves the best overall score and performs robustly on every task; in contrast, the baselines perform well only on specific tasks. Furthermore, we observe that the optimal memory programs across different tasks are structurally and procedurally distinct. By exploring a broad program optimization space, MSTAR evaluates diverse memory programs to identify the task-optimized memory harness. Ultimately, our study demonstrates a critical direction for self-evolving memory harnesses: specializing the optimal memory harness for different tasks can surpass the performance of general agents in specific domains. In summary, our main contributions are as follows: 1. We formulate the optimization of agent memory harnesses as an executable program search problem over a specific task. To this end, we introduce MSTAR, which expresses a memory harness as a memory program that can be systematically evaluated and evolved. 2. We design a reflective code evolution method to search for task-optimized memory programs. We evaluate this approach on four benchmarks against baselines from three memory paradigms, validating the effectiveness of MSTAR in optimizing agent memory harnesses. 3.We provide an analysis of the nature and dynamics of agent memory program evolution. This analysis illustrates that a large landscape of agent harnesses exists and that different tasks require structurally distinct code, thus corroborating the necessity of task-specific optimization. 2 Problem Setting We consider a taskT = (D e ,D test ), whereD e = e 1 ,...,e N is a collection of episodes rep- resenting past experiences, andD test = (q 1 ,y 1 ),..., (q M ,y M )is a set of held-out test queries with corresponding ground-truth answers. An agentAmust memorize information from these past episodes to successfully evaluate onD test . Specifically, the agent is equipped with a knowledge base K; it observes episodes inD e and extracts knowledge items k to populate this knowledge base. The 2 0 Seed Memory Program InstructionsPrompt constants for the task agent 1 INSTRUCTION_KNOWLEDGE_ITEM = "..." 2 INSTRUCTION_QUERY = "..." 3 INSTRUCTION_RESPONSE = "..." 4 SchemaDataclass definitions for storage and retrieval 5 class KnowledgeItem:# what to store 6 topic: str 7 content: str 8 9 class Query:# how to retrieve 10 question: str 11 category: str 12 LogicKnowledgeBase class with toolkit access 13 class KnowledgeBase: 14 15 def write(self, item: KnowledgeItem): 16 self.db.execute(...) 17 18 def read(self, q: Query) .> str: 19 return self.chroma.query(...) 20 1 Program Pool write()/read() Instructions Toolkit ✓×✓0.47 ✓×0.32 ✓×0.41 ×✓0.38 ✓×✓0.26 2 Evaluate Episodes Agent + Write Instr. write() read() Agent Val set + Read Instr. ✓× Rotating Set 0.47 Static Set 3 Reflect & Mutate Current Program Success cases Failed cases Lineage log Reflector Diagnose eval errors and generate patch − + + Diff patch Analysis Change log 4 Quality Checks Compile Valid syntax & imports Smoke Test write()/read() cycle Exec Limits Output ≤3000 chars, ≤60s pass pass fail LLM Auto-Fix Repair errors, up to k×3 Program FeedbacksChild program Add to pool 5Task-Optimized Memory Episodes Agent + Write Instr. write() read() Agent Test set + Read Instr. Improved performance on task Figure 2: System overview of MSTAR. Starting from a seed memory program (0), the system maintains a population pool (1) and iteratively improves programs through evaluation on task episodes (2), LLM-guided reflection and code mutation (3), and compile/runtime quality checks (4). The best-scoring program is evaluated on a held-out test set (5). knowledge base is thus defined as a collection of these items. At test time, given a queryq j , the agent queriesK, which in turn returns relevant contextc j . Building on this retrieved information, the agent then produces its answer or takes a defined action conditioned on both the query and the context: ˆy j =A q j ,K.read(q j ) .(1) Problem: Task-Optimized Memory Harness. While several prior works have proposed various memory modules for agent systems to organize information, these generalist memory structures cannot effectively transfer to different types of tasks [14]. For example, a conversational task may require storing information about character relationships and user preferences; in contrast, expert domains such as legal queries require structured memories of previous cases. However, existing approaches often rigidly employ flat vector databases or hard-code entity connections through structures like knowledge graphs and hierarchical memories. As demonstrated in Table 1, no single baseline method performs consistently well across different task domains. As a result, finding the best knowledge base architecture for a specific downstream task remains necessary and crucial. To this end, we formalize this objective as finding a task-optimized memory harness. Specifically, we abstract the reading and writing strategies, along with the structural organization of the knowledge base, into a memory programP. This programPdefines the input and output formats of the knowledge base, its underlying organization method such as a vector database or relational tables, and the agent’s policy for when and how to access memory. Consequently,Pdescribes an open design space that can express various memory pipeline implementaions. We defineJ (P )as the agent’s performance onD test when equipped with a knowledge base instantiated byP. The objective is to find the optimal memory programP ∗ that maximizes this performance metric within a fixed 3 evaluation budget: P ∗ = arg max P J (P ).(2) In the next section, we address how we can automatically discover the optimal memory harness for a given task; specifically, we propose a framework that uses executable code evolution to search this design space. 3 Method Figure 2 provides an overview of the system. We propose MSTAR, an executable code evolution method to automatically discover the optimal memory structure for a given task. Specifically, MSTAR consists of three main components: (1) expressing the memory search space using code (Section 3.1), (2) reflective code mutation (Section 3.2), and (3) an efficient search strategy (Section 3.3). 3.1 Expressing Memory Search Space with Code We represent a memory program using executable code; specifically, we use Python protocols. This code-based representation provides an open design space to describe the organization of the knowledge base. In contrast, recent works on evolutionary memory typically restrict the optimization of memory systems to a selection among predefined modules in a closed system [4,20] or to textual optimization at the prompt level [21,1]. To maximize the search space and discover effective strategies, our code-based program simultaneously defines and controls three key dimensions of the knowledge base: Schema, Logic, and Instruction. In addition, the program has access to a standardized Toolkit. • Schema. The schema specifies the data formats that the knowledge base accepts for writing and querying. For example, the input format can range from structured data with timestamps to natural language insights. We implement the schema using Python dataclasses. As a result, when the agent needs to write or query information, it instantiates these dataclass types and passes them into the memory program for parsing. •Logic. The logic dimension defines the backend operations of the knowledge base when processing and storing the schema-formatted inputs and queries. This component can include operations such as computing embeddings, managing SQL tables, or calling an LLM for secondary data processing. Specifically, the logic exposeswriteandreadfunctions, which are executed whenever the agent performs write or read actions. • Instruction. Instructions define how the agent interacts with the knowledge base. This includes how to extract information from observed episodes, how to formulate queries, and how to interpret the results returned by the knowledge base. We define these instructions through constant prompt strings. Consequently, these strings are inserted into the system prompt when the agent executes corresponding actions. • Toolkit. Within our search space, we allow the memory program to utilize various data structures and external tools. We provide a set of whitelisted components, including lists, heaps, relational databases, vector databases, and LLM endpoints. This toolkit enables the memory programs to implement complex storage and retrieval mechanisms. 3.2 Reflective Code Evolution Representing a memory program using executable code introduces an enormous search space. Inspired by recent evolutionary algorithm discovery methods, we design a reflective code evolution process that iteratively refines memory program through feedback for targeted improvement. Specifically, this process consists of three stages: sampling feedback from a validation loop, iterative refinement via a coding agent, and constraint checking with automated repair. Sampling feedback from the validation loop. We select a representative subset from all available episodes and validation samples. This selection includes a subset of episodes and a subset of validation queries. The validation queries are further partitioned into a static set, which remains constant across all iterations, and a rotating set, which changes in each iteration similar to mini-batches in training. Given the current program, the agent executes one knowledge base write operation for each sample 4 in the episode subset. During validation, the agent initiates a query to the knowledge base for each sample in both the rotating and static sets; the returned information is then used to generate a response or take an action. The aggregated score on the static validation set serves as the performance metric for the current memory program. Meanwhile, the generated trajectory is used as feedback to improve the program. We partition the validation data into static and dynamic sets because the rotating validation set provides targeted feedback without leaking information from the static set, preventing evaluation contamination. Simultaneously, using an identical static validation set ensures that the scores remain comparable across different memory programs. Coding agent iteration. We employ a coding agent to iteratively update the current memory program to improve performance and fix potential bugs. The information provided to this coding agent includes the execution trajectories from the read and write processes, underperforming samples from the rotating validation set, and the change logs from prior iterations along with their corresponding scores and so on. Based on this information, the coding agent analyzes whether the read and write operations function as expected, identifies the root causes of underperforming cases, and determines which past improvements were effective. Consequently, the coding agent generates a code patch to apply to the current program and produces a new change log to guide future iterations. The complete prompt template is provided in Appendix G. Constraint checks and automated repair. Before applying the updated memory program, the code evolution process executes a set of runtime checks to ensure its quality. These checks consist of multiple validation gates. If any gate fails, the memory program and its corresponding error messages are resubmitted to the coding agent for repair. The gates include a static check to verify that no modules outside a predefined whitelist are imported and that no compilation errors exist. A smoke test is also conducted to ensure the program does not raise runtime errors when provided with mock input data. Additionally, performance constraints are enforced; for instance, the read operation must return no more than 3000 characters, and each function must complete within a two-minute time limit. This step guarantees the efficiency of the overall iterative loop and prevents low-quality programs from consuming excessive computational resources. 3.3 Effective Searching Strategy Unlike function search, prompt optimization, or modular memory functions, the validation process in MSTAR can be highly expensive. For any code modification, the agent must regenerate all episode knowledge and evaluate the program on the validation set. To address this, we design two strategies that significantly reduce the validation overhead while maintaining the effectiveness of the evolution process. Population-based search. Instead of continuously updating a single program, which can cause the evolution algorithm to fall into local optima, we maintain a program pool. We initialize the search with a small set of simple seed programs (Appendix E). In each iteration, we select a high-scoring program for mutation with a higher probability by applying softmax temperature sampling based on the validation scores of all programs in the pool. Specifically, the probabilityP (x i )of selecting program x i is computed as: P (x i ) = exp(s(x i )/τ ) P j exp(s(x j )/τ ) ,(3) wheres(·)represents the validation score andτdenotes the temperature parameter. The mutated programs are subsequently added back to the pool. This design balances exploration and exploitation; top-performing programs have a greater chance of being selected for improvement, yet lower-scoring programs retain a non-zero probability of being explored. Representative subset selection. As mentioned previously, we use a validation subset for perfor- mance evaluation. To ensure that the static validation set accurately reflects the ultimate capability of the model, we avoid random sampling from the complete validation set. Instead, we usek-means clustering to cluster the validation set intongroups based on sample embeddings. We then randomly select one sample from each cluster to form the static validation set. This approach enables the static validation set to better cover various types of problems. Furthermore, for the episode subset selection, we apply a facility location formulation to compute an optimal subset ofMepisodes, allowing the agent to learn from highly relevant context. Under this formulation, every validation sample is matched with a similar episode by maximizing the sum of similarities between all validation samples 5 and their nearest episodes. Formally, given the set of validation samplesVand the overall episode set E, we select a subset S ⊆ E of size M to maximize: max S⊆E,|S|=M X v∈V max e∈S sim(v,e),(4) where sim(·,·) measures the embedding similarity. Overall, MSTAR provides an efficient code evolution method to search for optimal memory harnesses. In the following section, we provide an empirical analysis to validate our method. 4 Experimental Setup We evaluate MSTAR on four benchmarks with six domain configurations: LoCoMo for conversational question answering, ALFWorld for embodied task completion (seen and unseen environments), HealthBench for health data interpretation and emergency referral recognition, and PRBench for legal and financial professional reasoning. For each configuration, we run 20 evolution iterations independently. At the start of each iteration, we reset the knowledge base to its initial state; within the iteration, the same knowledge base remains persistent across all episode writes and validation queries. We split each benchmark into validation and held-out test partitions. The validation partition contains a static set and a rotating set, following Section 3.2. In addition, validation and test use disjoint episode groups to reduce leakage and to better measure generalization of the learned memory harness. We use GPT-5.4 Mini as the task agent and GPT-5.3-Codex as the coding agent in reflective code evolution. Additional hyperparameters are provided in Appendix D; computational cost analysis in Appendix C; and pseudocode in Appendix A. 4.1 Benchmarks • LoCoMo. LoCoMo is a multi-session conversational question answering benchmark in which the agent must recover relevant facts from long dialogue histories. The dataset contains extended dialogues with timestamped sessions, and the questions cover single-hop recall, temporal reasoning, causal reasoning, and cross-session multi-hop reasoning. We use the provided conversation sessions as episodes and report token-level F1 together with LLM-judge score. •ALFWorld. ALFWorld evaluates embodied task completion in simulated household environments through text interaction. The agent must complete goals such as finding, heating, cleaning, and placing objects. We use expert trajectories from the training split as episodes. We report success rate within a 50-step budget on both seen and unseen environment splits. •HealthBench. HealthBench [3] is a medical question answering benchmark with professional rubric-based evaluation. Each sample includes a multi-turn clinical dialogue, an ideal completion, and structured pass or fail criteria written by medical professionals. We evaluate two categories: health data interpretation and emergency referral recognition. Because HealthBench does not provide a training split, we construct episode pools from a held-out portion of the benchmark data and keep evaluation queries disjoint from episode construction. We report rubric score, computed as the fraction of criteria marked positive by an LLM judge. • PRBench. PRBench [2] evaluates professional reasoning in legal analysis and financial valuation. Each sample contains a task prompt, an expert reference, and an importance-weighted rubric. Similar to HealthBench, PRBench does not provide a training split, so we construct episodes from a held-out portion and evaluate on disjoint query sets. We use the same rubric-based scoring protocol as HealthBench. Dataset sizes and split configurations are provided in Appendix B; evaluation metric details are in Appendix H. 4.2 Baselines We compare MSTAR with competitive memory and continual-improvement methods from three categories, as summarized in Table 1. We also report a No Memory setting, where the agent answers directly without any external memory store. 6 Table 1: Main results across four benchmarks. LoCoMo (token F1 / LLM judge), ALFWorld (success rate), HealthBench (rubric score), and PRBench (rubric score). Baselines are grouped by memory paradigm: retrieval-based systems that memorize raw episodes, self-evolution systems that memorize distilled experiences, and prompt-optimizing systems that memorize traction from prior attempts. MSTAR achieves the best score on seven of eight configurations. Best per column in bold, second best in green. LoCoMoALFWorldHealthBenchPRBench MethodF1L-JUnseenSeenDataEmerg.LegalFinance No Memory0.0360.0300.7380.6400.2420.4290.4310.269 Retrieval-based Systems (Memorizing Episodes) Vector Search0.2560.4000.6430.7200.2640.4000.4660.308 G-Memory0.2240.3800.6900.5600.3090.4470.4990.318 Mem00.3730.5400.7380.6400.2160.4130.4500.321 Self-evolution Systems (Memorizing Experiences) Trajectory Retrieval0.2760.4200.7140.7800.2650.4420.4800.304 ReasoningBank0.1940.3800.7380.5800.3150.4700.5080.330 Dynamic Cheatsheet0.1240.1900.6190.4800.2860.4870.4740.327 Prompt-optimizing Systems (Memorizing Traction) GEPA0.1320.1900.8570.7200.3040.4660.5680.449 GEPA + Vector Search0.3000.3900.8100.8200.3270.4840.5540.411 MSTAR0.4590.6100.8810.7000.3900.4930.6600.586 •Retrieval-based systems. These methods store raw observations and retrieve relevant context by similarity. Vector Search stores each observation in a vector collection and retrieves top-k items by embedding cosine similarity, without task-specific parsing. G-Memory [19] augments vector retrieval with a hierarchical graph over related tasks implemented with SQLite. Mem0 [19] extracts atomic facts from observations and maintains them with LLM-driven add, update, and delete operations. • Self-evolution systems. These methods distill reusable knowledge from experience instead of storing raw episodes directly. Trajectory Retrieval [19] retrieves full episode trajectories by embedding similarity. ReasoningBank [9] extracts key insights from each episode and retrieves them with similar task descriptions. Dynamic Cheatsheet [19] maintains a single global summary that is iteratively rewritten after each new experience. •Prompt-optimizing systems. These methods improve agent behavior by evolving the system prompt. GEPA [1] optimizes prompts through reflective mutation with Pareto-based candidate selection. We evaluate two variants: GEPA and GEPA + Vector Search. The second variant adds a vector database to GEPA because the original GEPA setup does not include a persistent knowledge base, which can limit performance on memory-intensive tasks. 5 Results Table 1 summarizes the main results. We organize the analysis around three observations about the effectiveness and mechanism of evolutionary memory harness search. Evolutionary search progressively discovers better memory structures. Table 1 shows that MSTAR achieves the highest score on seven of eight benchmark configurations. Compared with the best baseline in each winning configuration, the relative improvement ranges go up to 31%, with the largest gains on LoCoMo and PRBench. We attribute this pattern to the ability of code evolution to discover task-optimized memory harnesses that are not reachable with fixed memory designs. In addition, no baseline is consistently strongest across all tasks. Although GEPA is the strongest baseline overall, it still tends to underperform on benchmarks that require richer structured memory operations. Figure 3 further illustrates how performance improves during evolution. Specifically, early iterations mainly fix structural issues inherited from seed programs, middle iterations deliver the largest gains by introducing task-relevant indexing and retrieval logic, and later iterations focus on 7 05101520 Iteration 0.4 0.5 0.6 0.7 Validation Score 1 2 3 Best so far Child score Compile fail Vanilla RAG ❶ Iter 050.50 → 0.60 Store observations as structured task records - lessons.append(...)dump all - facts.append(...) - return ALL stored textno retrieval + record = typed fields + "target_object": ..., + "state": ..., + "tool": ..., + "target": ..., + "tokens": tokenize(blob)bag-of-words + + sig = sha1(text).hexdigest()dedup + if sig in self.seen: return ❷ Iter 130.60 → 0.67 Increase weights for key fields; drop LLM call if q_obj == rec["primary_object"]: - score += 6 + score += 8object ID most critical elif q_obj in rec["tokens"]: - score += 2 + score += 4doubled if q_loc == rec["target_location"]: - score += 3 + score += 5location ↑ if q_state == rec["required_state"]: - score += 4 + score += 5 - return llm_synthesize(top)LLM call + return format_top4(ranked)no LLM ✔ ❸ Iter 160.67 → 0.70 Penalize mismatches; generate task checklist if q_primary == rec["primary_obj"]: score += 4.0 else: + score -= 1.8wrong-obj penalty if q_action != rec["action_type"]: + score -= 0.4action mismatch + lines.append("Exec checklist:")checklist + lines.append(f"- Only: q_ent[:4]") + lines.append("- Never substitute") + if q_state and q_primary: + lines.append(f"- q_state") Figure 3: Evolution trajectory. Validation score across iterations for all benchmarks. Most benchmarks follow a common phased pattern: early iterations correct structural errors in seed programs, middle iterations produce the largest gains by discovering task-relevant indexing strategies, and later iterations refine retrieval precision with diminishing returns. precision refinements with smaller returns. This phased behavior suggests that evolution first builds a viable program skeleton and then refines its internal memory logic. Table 2: Ablation study on LoCoMo. Each row removes one design choice from the full system; metric is token F1. Removing code evolution causes the largest drop (−0.203), confirming that structural adaptation is the pri- mary performance driver.∆: absolute change from the full system. VariantF1∆ MSTAR0.459— − Instruction0.353−0.106 − Code0.256−0.203 w/ Max sampling0.381−0.078 − Diversity0.318−0.141 Different tasks produce structurally distinct optimal memory harnesses. To understand how MSTAR adapts memory structure to different tasks, we visualize the pro- gram embedding landscape accumulated during evolution (Figure 4). For each task and iteration, we first sanitize the program by replacing strings and variable names with domain-agnostic placeholders so that the embedding empha- sizes structural differences. We then embed the sanitized programs with a code embedding model and project them with t-SNE. The resulting landscape indicates that different benchmarks occupy different regions that correspond to dis- tinct algorithmic structures, and the best program for each task (star marker) is structurally different from the others. For example, although our toolkit supports both relational and vector databases, the best ALFWorld program primarily uses simple list-based memory plus LLM summarization, whereas the best LoCoMo program uses a hybrid design with both vector and relational components. These case studies are consistent with Figure 1, and we provide full code for the best programs in the appendix. To further test whether evolved programs are task-specific or universally transferable, we evaluate each task’s best evolved program on other tasks (Figure 5). In every target benchmark, the native evolved program (highlighted) outperforms transferred programs from other benchmarks. Moreover, most transferred programs perform worse than the universal seed baseline. These results suggest that memory structure should be co-optimized with the target task, and that evolution discovers specialized adaptations that fixed designs cannot reliably provide. 8 (a) Population Search (LoCoMo) 0.41 (b) Linear Search (LoCoMo) 0.38 (c) All Programs DATASET LoCoMo HB-Data HB-Emergency PRB-Finance PRB-Legal LoCoMo-Linear ALFWorld-Seen ALFWorld-Unseen ARCHITECTURE Vector+LLM Vector-only SQL+Vector SQL-only LLM-centric Seed Best LLM-Centric Relies on the LLM to filter and rank raw text at read time Semantic Search Pure vector similarity search over multi-field knowledge items Hybrid Retrieval Combines SQL indexing with vector search and LLM re-ranking Relational Index Stores facts in multi-table SQL with indexed queries Structured RAG Organizes data in SQL tables and vector indices for structured retrieval Figure 4: Program embedding landscape. Each evolved program is embedded with a code embedding model and projected to 2D via t-SNE. (a, b) Population-based search (MSTAR) explores structurally diverse regions of the program space, while linear search concentrates in a narrow neighborhood; colored edges trace parent – child lineage. (c) All programs across five benchmarks, colored by dataset. Marker shapes denote the storage architecture discovered by evolution: circles for vector + LLM, triangles for vector-only, squares for SQL + vector, rotated squares for SQL-only, and crosses for LLM-centric designs. Distinct benchmarks converge on different architectural clusters, confirming that optimal memory design is task-dependent. 0 0.1 0.2 0.3 0.4 0.5 0.26 0.41 0.02 0.09 Universal mem. LoCoMo mem. ALFWorld mem. Legal mem. LoCoMo Token F1 0 0.2 0.4 0.6 0.8 1.0 0.72 0.62 0.88 0.58 Universal mem. LoCoMo mem. ALFWorld mem. Legal mem. ALFWorld Success Rate 0 0.2 0.4 0.6 0.8 0.47 0.06 0.58 0.66 Universal mem. LoCoMo mem. ALFWorld mem. Legal mem. PRBench Rubric Score Figure 5: Cross-task transfer of evolved memory harnesses. Each panel evaluates memory harnesses evolved on different source benchmarks against a single target benchmark. The dashed line marks the universal seed baseline. Programs evolved on their native task (highlighted) consistently outperform those transferred from other tasks, confirming that memory structure must be co-optimized with the target task. Joint evolution of structure and policy enables task-specific adaptation. Our method jointly optimizes multiple components of a task-optimized memory harness, including memory structure, retrieval logic, and interaction instructions. To quantify the contribution of each component, we conduct ablations on LoCoMo (Table 2). We find that removing code evolution causes the largest drop, which confirms that structural adaptation is the primary performance driver. Removing instruction optimization also leads to a substantial drop, suggesting that task-specific guidance for how the agent reads from and writes to the knowledge base is also important. Overall, these results indicate that jointly optimizing memory structure and memory-use policy is more effective than optimizing either side in isolation. 9 Table 4: Per-category performance breakdown. (a) ALFWorld Unseen success rate by task type. (b) LoCoMo token F1 by query type.n: number of test episodes or validation queries per category. Categories withn=1(movable, light) are omitted. MSTAR achieves the highest minimum across categories on ALFWorld (0.75) while maintaining competitive per-category scores on LoCoMo. Bold: best per column. (a) ALFWorld Unseen(b) LoCoMo SimpleCleanCoolHeat2-ObjSingleTemp.CausalOpen (n=8)(n=11)(n=7)(n=6)(n=8)Min(n=18)(n=18)(n=9)(n=55)Min No Memory0.880.820.570.830.620.570.020.000.110.040.00 Mem00.880.640.571.000.750.570.330.260.370.430.26 Trajectory Retrieval0.750.730.710.670.750.670.180.330.340.280.18 GEPA + Vector Search0.881.000.571.000.620.57 0.150.380.390.310.15 MSTAR0.880.911.000.830.750.750.330.190.350.510.19 6 Discussion The previous section established that MSTAR outperforms fixed baselines and that each design choice contributes to final performance. Building on this, we analyze the search process itself. Specifically, we ask three questions: how reflective code evolution explores the memory-program space, how stable the outcomes are across random seeds, and whether gains are distributed across categories or concentrated in a few subsets. How does evolution explore the program space? Figure 4 visualizes the program-embedding landscape accumulated during evolution. We observe that evolved programs form several clusters associated with different structural paradigms. After inspecting representative programs, we group these clusters into five broad families: LLM-centric, semantic search, hybrid retrieval, relational index, and RAG. Moreover, most cluster regions contain programs that were evolved for different benchmarks. This pattern suggests that reflective code evolution evaluates diverse program structures before convergence, even when all runs start from the same seed program. To clarify the role of diversity in this process, we compare our population-based search against a linear search variant in Figure 4(a,b). In linear search, optimization starts from one empty seed and repeatedly mutates only the current best program. In contrast, population-based search keeps multiple candidates active, which preserves alternative trajectories and delays premature convergence. Consistent with this interpretation, Table 2 shows that removing diversity (linear search) reduces the best test score from 0.459 to 0.318, while removing the diversity mechanism but retaining multi-seed starters yields 0.381. These results indicate that population-based search is a key factor for exploring heterogeneous memory-harness structures. Table 3: Stability across evolution seeds. Mean and std. over five independent runs with different random seeds (seeds 0–4); metric matches each benchmark’s primary column in Table 1 (LoCoMo: token F1; HealthBench Data: rubric score; PRBench Finance: rubric score). Best BL: strongest non- evolution baseline (method in parentheses). Win: number of seeds that outperform the best baseline. All benchmarks show coefficient of variation below 9%. BenchmarkMean±StdCVBest BaselineWin LoCoMo0.410 ±.037 8.90.373 (Mem0)4/5 HB Data0.391 ±.023 5.90.327 (GEPA+VS)5/5 PR Finance0.561 ±.032 5.70.449 (GEPA)5/5 Is the evolution consistent and sta- ble? A practical concern for evolu- tionary methods is sensitivity to ran- dom seeds, especially because our budget is limited to 20 iterations and some runs may not discover the strongest program within this horizon. To evaluate this effect, Table 3 re- ports test scores from five independent runs on three benchmarks. Across all benchmarks, the coefficient of varia- tion remains below 9%, which indi- cates stable outcomes with moderate variance. At the same time, 14 of 15 seeds outperform the strongest baseline, which suggests that the gains from evolution are robust rather than incidental. Appendix J provides full per-seed scores and validation trajectories. Does evolution improve performance uniformly? We next ask whether evolution improves performance uniformly across categories or mainly optimizes a few high-impact subsets. Table 4 disaggregates the results in Table 1 by category (full per-category tables are in Appendix I). Overall, MSTAR tends to improve broad category coverage, with the largest gains in weaker categories, 10 rather than relying on isolated gains in one dominant category. On ALFWorld, this behavior appears as robustness across task types rather than dominance in a single task type. Specifically, MSTAR attains the highest minimum category score (0.75) and the lowest cross-category standard deviation (σ=0.08), which suggests that the evolved action cache addresses failure modes that fixed designs leave exposed. However, this objective can still induce trade-offs: because evolution optimizes an aggregate metric, it tends to allocate capacity to categories with larger impact on the final score, which may leave lower-frequency categories relatively underserved. 7 Related Work 7.1 Memory for LLM Agents Prior work on agent memory focuses on constructing external memories from interaction histories and leveraging them to support downstream reasoning and decision making [22]. Typical pipelines periodically extract salient information into a memory store, retrieve relevant entries for a new query, and update the store via consolidation or pruning [10, 24, 16]. More recently, MemSkill [21] frames memory operations as learnable natural-language skills selected by an RL controller, and AWM [17] induces reusable workflows from successful trajectories to guide future retrieval. Because these approaches commit to a fixed representation at design time, they cannot express task-specific computational logic such as relational schemas or stateful aggregations. Several concurrent works explore self-evolving memory, but within closed design spaces: Evo- Memory [18] benchmarks test-time memory evolution, and MemEvolve [20] searches over combi- nations of four predefined modules (encode, store, retrieve, manage), limiting reachable designs to those already in the library. By contrast, we search over executable Python programs that implement arbitrary data structures and retrieval logic, subsuming the closed spaces of prior systems. 7.2 Self-Evolving Agents Recent work on self-evolving LLM agents studies how agents can improve from interaction experience without gradient-based parameter updates [6]. ExpeL [23] distills successful and failed trajectories into editable natural-language insights retrieved at test time, and FLEX [4] formalizes this as forward learning, constructing an experience library through continual reflection on environmental feedback. A complementary line automates agent design: ADAS [7] searches over agentic components via meta- optimization, Voyager [15] synthesizes reusable skill programs in open-ended environments, and Reflexion [13] feeds verbal self-critique back into the next trial. All of these evolve text-level artifacts that an LLM must re-interpret at runtime; MSTAR instead evolves deterministic code, removing interpretation variance and enabling structures that natural language cannot express. 7.3 LLM-Guided Program Search Using LLMs as mutation operators for program synthesis has produced solutions surpassing human- designed heuristics in combinatorial optimization [12], neural architecture search [5], and broader algorithmic discovery [8]. Closest to our work, GEPA [1] iteratively mutates every prompt within a compound AI system by reflecting on sampled trajectories in natural language, maintaining a Pareto front to diversify strategies across training instances. MSTAR applies the same reflective evolution paradigm to executable memory programs; because generated code can fail to compile or violate runtime constraints, we introduce a compile-fix loop and runtime violation recovery that are unnecessary in prompt evolution (Section 3.2). 8 Conclusion In this paper, we introduced MSTAR, a method for automatically discovering task-optimized memory harnesses for large language model agents. Because existing memory architectures are frequently optimized for a single paradigm, they are less effective when applied to dissimilar domains. To overcome this limitation, MSTAR formulates the memory design problem as an executable code search: it represents the memory functionality as a Python memory program encompassing a Schema, Logic, and Instructions. Using an LLM-based reflective code evolution process, our approach 11 iteractively evaluates, debugs, and improves these programs across generations. Experiments on four distinct benchmarks demonstrate that MSTAR consistently outperforms paradigm-specific baselines by adapting the storage, retrieval, and action workflows to the unique demands of each domain. As a result, our study establishes that discovering custom memory programs through an evolutionary search provides a significantly more robust solution than relying on a fixed, general-purpose memory design. Future work will explore more sample-efficient strategies for the code search space and extend the evolutionary framework to broader families of agent tasks. References [1] Lakshya A. Agrawal, Shangyin Tan, Dilara Soylu, Noah Ziems, Rishi Khare, Krista Opsahl-Ong, Arnav Singhvi, Herumb Shandilya, Michael J. Ryan, Meng Jiang, Christopher Potts, Koushik Sen, Alexandros G. Dimakis, Ion Stoica, Dan Klein, Matei Zaharia, and Omar Khattab. GEPA: Reflective prompt evolution can outperform reinforcement learning. In ICLR, 2026. Oral. arXiv:2507.19457. [2]Afra Feyza Akyurek, Advait Gosai, Chen Bo Calvin Zhang, Vipul Gupta, Jaehwan Jeong, Anisha Gunjal, Tahseen Rabbani, Maria Mazzone, David Randolph, Mohammad Mahmoudi Meymand, et al. PRBench: Large-scale expert rubrics for evaluating high-stakes professional reasoning. arXiv preprint arXiv:2511.11562, 2025. [3]Rahul K. Arora, Jason Wei, Rebecca Soskin Hicks, Preston Bowman, Joaquin Quiñonero- Candela, Foivos Tsimpourlas, Michael Sharman, Meghan Shah, Andrea Vallone, Alex Beutel, Johannes Heidecke, and Karan Singhal. HealthBench: Evaluating large language models towards improved human health. arXiv preprint arXiv:2505.08775, 2025. [4]Zhicheng Cai, Xinyuan Guo, Yu Pei, Jiangtao Feng, Jiangjie Chen, Ya-Qin Zhang, Wei-Ying Ma, Mingxuan Wang, and Hao Zhou. FLEX: Continuous agent evolution via forward learning from experience. arXiv preprint arXiv:2511.06449, 2025. [5]Angelica Chen, David Dohan, and David So. EvoPrompting: Language models for code-level neural architecture search. In NeurIPS, 2023. [6]Huan-ang Gao, Jiayi Geng, Wenyue Hua, Mengkang Hu, Xinzhe Juan, Hongzhang Liu, Shilong Liu, Jiahao Qiu, Xuan Qi, Yiran Wu, et al. A survey of self-evolving agents: What, when, how, and where to evolve on the path to artificial super intelligence. arXiv preprint arXiv:2507.21046, 2025. [7] Shengran Hu, Cong Lu, and Jeff Clune. ADAS: Automated design of agentic systems. In ICLR, 2025. [8] Alexander Novikov, Ngân V ̃ u, Marvin Eisenberger, Emilien Dupont, Po-Sen Huang, Adam Zsolt Wagner, Sergey Shirobokov, Borislav Kozlovskii, Francisco J. R. Ruiz, Abbas Mehrabian, M. Pawan Kumar, Abigail See, Swarat Chaudhuri, George Holland, Alex Davies, Sebastian Nowozin, Pushmeet Kohli, and Matej Balog. AlphaEvolve: A coding agent for scientific and algorithmic discovery. arXiv preprint arXiv:2506.13131, 2025. [9] Siru Ouyang, Jun Yan, I-Hung Hsu, Yanfei Chen, Ke Jiang, Zifeng Wang, Rujun Han, Long T. Le, Samira Daruki, Xiangru Tang, et al. ReasoningBank: Scaling agent self-evolving with reasoning memory. In ICLR, 2026. [10]Joon Sung Park, Joseph C O’Brien, Carrie J Cai, Meredith Ringel Morris, Percy Liang, and Michael S Bernstein. Generative agents: Interactive simulacra of human behavior. In UIST, 2023. [11]Pranav Rajpurkar, Jian Zhang, Konstantin Lopyrev, and Percy Liang. SQuAD: 100,000+ questions for machine comprehension of text. In EMNLP, 2016. [12]Bernardino Romera-Paredes, Mohammadamin Barekatain, Alexander Novikov, Matej Balog, M Pawan Kumar, Emilien Dupont, Francisco JR Ruiz, Jordan S Ellenberg, Pengming Wang, Omar Fawzi, et al. Mathematical discoveries from program search with large language models. Nature, 625:468–475, 2024. 12 [13]Noah Shinn, Federico Cassano, Ashwin Gopinath, Karthik Narasimhan, and Shunyu Yao. Reflexion: Language agents with verbal reinforcement learning. In NeurIPS, 2023. [14]Alina Shutova, Alexandra Olenina, Ivan Vinogradov, and Anton Sinitsin. Evaluating memory structure in LLM agents. arXiv preprint arXiv:2602.11243, 2026. [15]Guanzhi Wang, Yuqi Xie, Yunfan Jiang, Ajay Mandlekar, Chaowei Xiao, Yuke Zhu, Linxi Fan, and Anima Anandkumar. Voyager: An open-ended embodied agent with large language models. Transactions on Machine Learning Research, 2024. [16] Weizhi Wang, Li Dong, Hao Cheng, Xiaodong Liu, Xifeng Yan, Jianfeng Gao, and Furu Wei. Augmenting language models with long-term memory. In NeurIPS, 2023. [17] Zora Zhiruo Wang, Jiayuan Mao, Daniel Fried, and Graham Neubig. Agent workflow memory. In ICML, 2025. [18]Tianxin Wei, Noveen Sachdeva, Benjamin Coleman, Zhankui He, Yuanchen Bei, Xuying Ning, Mengting Ai, Yunzhe Li, Jingrui He, Ed H. Chi, Chi Wang, Shuo Chen, Fernando Pereira, Wang-Cheng Kang, and Derek Zhiyuan Cheng. Evo-Memory: Benchmarking LLM agent test-time learning with self-evolving memory. arXiv preprint arXiv:2511.20857, 2025. [19]Yiming Xiong, Shengran Hu, and Jeff Clune. Learning to continually learn via meta-learning agentic memory designs. arXiv preprint arXiv:2602.07755, 2026. [20]Guibin Zhang, Haotian Ren, Chong Zhan, Zhenhong Zhou, Junhao Wang, He Zhu, Wangchun- shu Zhou, and Shuicheng Yan. MemEvolve: Meta-evolution of agent memory systems. arXiv preprint arXiv:2512.18746, 2025. [21]Haozhen Zhang, Quanyu Long, Jianzhu Bao, Tao Feng, Weizhi Zhang, Haodong Yue, and Wenya Wang. MemSkill: Learning and evolving memory skills for self-evolving agents. arXiv preprint arXiv:2602.02474, 2026. [22]Zeyu Zhang, Xiaohe Zhang, Yuanpei Wang, Shengjie Yan, and Rui Sun. A survey on the memory mechanism of large language model based agents. ACM Transactions on Information Systems, 2025. [23]Andrew Zhao, Daniel Huang, Quentin Xu, Matthieu Lin, Yong-Jin Liu, and Gao Huang. ExpeL: LLM agents are experiential learners. In AAAI, 2024. [24]Wanjun Zhong, Lianghong Guo, Qiqi Gao, He Ye, and Yanlin Wang. MemoryBank: Enhancing large language models with long-term memory. In AAAI, 2024. A Algorithm B Dataset Details Table 5 summarizes the data splits for each benchmark configuration. For LoCoMo, we exclude category 5 (adversarial and unanswerable questions), which tests refusal capability rather than memory retrieval, retaining 1,540 QA pairs across four categories. For PRBench, hard items (finance_hardandlegal_hard) are excluded from evolution to avoid distortion of the fitness signal. C Computational Cost Table 6 reports the computational cost of running MSTAR evolution and baselines across all bench- marks. We break down API calls by role: the task agent (knowledge extraction, query generation, and answer generation), the reflector (code mutation via LLM reflection), the judge (per-criterion rubric scoring for HealthBench and PRBench), and the toolkit (LLM calls made by the evolved KB program’sread()/write()methods). All experiments usegpt-5.4-minias the task agent, 13 Algorithm 1 MSTAR: Evolutionary Memory Harness Search (a) Evolution Loop Require:Seed programsS 1 ,...,S K , bud- get B, temp. τ Require:Train dataD train , static valD val , ro- tate pool D r Ensure: Best program P ∗ 1: P ←∅ 2: for i = 1 to K do 3:(J i , _)← EVAL(S i ,D train ,D val ) 4: P ←P ∪(S i ,J i ) 5: end for 6: for t = 1 to B do 7: P par ← SOFTMAXSAMPLE(P,τ ) 8: ̃ D ← SAMPLE(D r , n r ) 9:(_,R)← EVAL(P par ,D train , ̃ D) 10: P mut ← MUTATE(P par ,R) 11: P ′ ← COMPILEFIX k (P mut ) 12:(J ′ , _)← EVAL(P ′ ,D train ,D val ) 13: P ←P ∪(P ′ ,J ′ ) Unconditional 14: end for 15: return arg max (P,J)∈P J (b) Split Evaluation Require: Program P , task agentA, metric μ Require: Train data D train , eval queries D eval Ensure: Score J , diagnostic casesR 1: // Phase 1: Knowledge ingestion 2: KB← P.init() 3: for d∈ D train do 4:item←A.extract(d, P.INSTR KI ) 5:KB.write(item, d) 6: end for 7: // Phase 2: Retrieval and scoring 8: F,S ←∅,∅ 9: for (q,y)∈ D eval do 10:query←A.formulate(q, P.INSTR Q ) 11: c← KB.read(query) 12:ˆy ←A.respond(q,c, P.INSTR R ) 13: s← μ(ˆy, y); add (q,y, ˆy,c) toF orS 14: end for 15: return 1 |D eval | P s, (F,S) Table 5: Dataset split sizes. LoCoMo trains on conversation sessions and evaluates on QA pairs; ALFWorld trains on expert trajectories and evaluates on interactive episodes; HealthBench and PRBench use homogeneous items throughout. BenchmarkSplitTrainValTest LoCoMo—272 sessions1,440 QA100 QA ALFWorldUnseen4,652 traj.145 ep.50 ep. Seen4,652 traj.150 ep.50 ep. HealthBenchData Tasks257120100 Emergency260122100 PRBenchLegal10010050 Finance12013050 judge, and toolkit model, andgpt-5.3-codexas the reflector model. Cost estimates use Azure OpenAI pricing: $0.75/$4.50 per 1M input/output tokens forgpt-5.4-mini, and $1.75/$14.00 per 1M input/output tokens forgpt-5.3-codex. Note thatgpt-5.3-codexis a reasoning model; its output token counts include internal reasoning tokens, which are billed at the same rate as visible output tokens. The total evolution cost ranges from $12–90 per benchmark over 20 iterations, depending primarily on the evaluation protocol. Rubric-graded benchmarks (HealthBench and PRBench) are substantially more expensive because each validation item requires multiple LLM judge calls for per-criterion scoring, making the judge the dominant cost component (60–80% of total calls). Token-F1 bench- marks (LoCoMo) and binary-success benchmarks (ALFWorld) avoid judge calls entirely, keeping evolution under $26. ALFWorld’s long wall-clock time (100h) is dominated by TextWorld environ- ment interaction, not API latency. Although the reflector makes only 24–48 calls per run, it uses the more expensivegpt-5.3-codexmodel ($14/1M output tokens vs. $4.50 forgpt-5.4-mini) and produces long code patches, so it accounts for 7–24% of total cost depending on the benchmark. Compared to baselines, the evolution overhead is a one-time cost: once the best program is found, inference uses the same number of calls as any baseline. The per-query inference cost of an evolved program equals that of the corresponding baseline configuration (No Memory or Vector Search) plus any toolkit calls the evolved program makes, typically 0–2 additional LLM calls per query. 14 Table 6: Computational cost of evolution runs and baselines. All runs use 20 iterations. Wall- clock time includes environment interaction overhead (e.g., TextWorld episodes for ALFWorld). All experiments use gpt-5.4-mini as the task agent and gpt-5.3-codex as the reflector. BenchmarkConfigIter. Task Refl. Judge TKit In Tok Out TokCost Time LoCoMoMSTAR20 580248—1354.9M4.2M $25.435.1h Vector Search02000—272294K71K$0.542m No Memory02000—272219K64K$0.451m ALFWorldMSTAR20 335525—4437.5M1.4M $13.92100h (Unseen)Vector Search0800—497711K50K$0.7614m No Memory0800—497708K50K$0.7611m ALFWorldMSTAR20 242028—4945.6M1.1M $11.94101h (Seen)Vector Search0800—497692K49K$0.7411m No Memory0500—22410M25K$0.310m HB-Emergency MSTAR20 427231 21370 221921M6.1M $47.204.3h Vector Search04501102423830K145K$1.286m No Memory05401102412761K137K$1.191m HB-DataTasksMSTAR20 420424 15006 157518M6.3M $44.642.1h Vector Search02401097433950K177K$1.517m No Memory03401105423836K171K$1.402m PR-LegalMSTAR20 306528 19984 124248M11M $90.1915h Vector Search0150958185818K130K$1.206m No Memory0150950185712K117K$1.061m PR-FinanceMSTAR20 179531 18602 249747M10M $84.812.6h Vector Search080845212740K153K$1.246m No Memory0130895207646K139K$1.1111m D Hyperparameters Table 7 lists the key hyperparameters used across all experiments. Table 7: Hyperparameters for MSTAR evolution. All benchmarks share the same configuration. ParameterValue Evolution iterations20 Population seed programs3 Selection strategySoftmax (T =0.15) Static validation subset25 items (k-means clustering) Rotating validation subset5 items per iteration Train-to-val ratio5 (train episodes = 5× val items) Embedding model (subset selection)BGE-M3 Reflector modelGPT-5.3-Codex (reasoning: medium) Task agent / toolkit modelGPT-5.4-mini Toolkit LLM call budget1 call per read/write invocation Compile-fix attempts (k)3 Evaluator thread pool64 workers LLM retry attempts3 (exponential backoff) E Seed Programs The program pool is initialized with three structurally diverse seeds designed to cover different points in the memory design space. All three share identical instruction constants but differ in storage strategy and retrieval logic. Table 8 summarizes their key design choices. Vector Search (Listing 1) implements vanilla RAG: raw text is split into 500-character paragraph- aligned chunks and stored in a ChromaDB collection;read()retrieves the top-5 most similar documents by embedding cosine similarity. No LLM call is used at retrieval time. 15 Table 8: Seed program comparison. Each seed covers a different region of the storage–retrieval design space. SeedStorageRetrievalLLM in read Vector SearchChromaDB chunksTop-k cosine similarityNo LLM SummarizerIn-memory listConcatenate + LLM summarizeYes (1 call) Experience LearnerSeparate lesson/fact listsReturn allNo LLM Summarizer (Listing 2) stores raw text in an in-memory list without any preprocessing. At retrieval time, all stored text is concatenated (up to 30,000 characters) and passed to the toolkit LLM alongside the query for query-focused summarization. This seed tests whether neural synthesis at read time can compensate for the lack of structured indexing. Experience Learner (Listing 3) extracts a general lesson and a specific fact from each observation, storing them in separate lists. At retrieval time, it returns all stored lessons and facts (truncated to 500 characters each), ignoring the query entirely. This seed explores whether dual-track extraction with full recall outperforms selective retrieval. Listing 1: Seed 1: Vector Search. class KnowledgeBase: """Vanilla␣RAG:␣store␣text␣chunks␣in␣ChromaDB,␣retrieve␣by␣semantic␣similarity.""" def __init__(self, toolkit): self.toolkit = toolkit self.collection = toolkit.chroma.get_or_create_collection("knowledge") self._doc_id = 0 def write(self, item: KnowledgeItem, raw_text: str) -> None: chunks = self._chunk(raw_text, max_chars=500) for chunk in chunks: self.collection.add(documents=[chunk], ids=[f"doc_self._doc_id"]) self._doc_id += 1 def read(self, query: Query) -> str: if self._doc_id == 0: return "No␣information␣stored." results = self.collection.query( query_texts=[query.query_text], n_results=min(5, self._doc_id)) docs = results["documents"][0] if results["documents"] else [] return " ".join(docs)[:3000] if docs else "No␣relevant␣information␣found." Listing 2: Seed 2: LLM Summarizer. class KnowledgeBase: """LLM-powered␣query-focused␣summarization␣over␣stored␣raw␣texts.""" def __init__(self, toolkit): self.toolkit = toolkit self.raw_texts: list[str] = [] def write(self, item: KnowledgeItem, raw_text: str) -> None: self.raw_texts.append(raw_text) def read(self, query: Query) -> str: if not self.raw_texts: return "No␣information␣stored." combined = " ".join(self.raw_texts)[:30000] messages = ["role": "user", "content": f"Given␣the␣following␣query,␣summarize␣ONLY␣the␣relevant␣information␣" f"from␣the␣provided␣texts.␣Be␣concise␣and␣factual. " f"Query:␣query.query_text : combined"] try: result = self.toolkit.llm_completion(messages) except Exception: result = combined return result[:3000] 16 Listing 3: Seed 3: Experience Learner. @dataclass class KnowledgeItem: lesson_learned: str = field( metadata="description": "A␣general␣lesson␣or␣pattern␣learned␣from␣the␣text") fact_to_remember: str = field( metadata="description": "A␣specific␣fact␣worth␣remembering␣from␣the␣text") class KnowledgeBase: """Experience-driven␣learner␣that␣stores␣lessons␣and␣facts,␣returns␣all␣on␣read.""" def __init__(self, toolkit): self.toolkit = toolkit self.lessons: list[str] = [] self.facts: list[str] = [] def write(self, item: KnowledgeItem, raw_text: str) -> None: self.lessons.append(item.lesson_learned) self.facts.append(item.fact_to_remember) def read(self, query: Query) -> str: if not self.lessons and not self.facts: return "No␣information␣stored." lessons_text = " ".join(self.lessons)[:500] facts_text = " ".join(self.facts)[:500] return f"Lessons: lessons_text : facts_text"[:3000] F Evolved Programs We present the best evolved programs for two representative benchmarks, selected to illustrate the structural diversity described in Section 5. Full source code for all seven benchmark configurations is available in the supplementary material. F.1 ALFWorld: Deterministic Action Cache The best ALFWorld program (Listing 4, Listing 5) constructs a deterministic action cache using SQLite. It stores structured fields extracted from expert demonstrations—target object, destination, required state change (clean/cool/heat/examine/toggle), action hints, and failure modes—and retrieves them via a weighted scoring function that combines token overlap with exact-match bonuses for object, location, and state. The program includes a_canonical_state()normalizer that maps diverse surface forms (“rinse”, “wash”→“clean”; “chill”, “cold”→“cool”) to canonical labels, and a fallback parser that extracts task metadata from raw text when the LLM’s structured extraction is sparse. A single LLM call at read time synthesizes the top-6 retrieved memories into concise step-by-step guidance. Key architectural properties: • 97 lines of logic in write() + read(), with zero vector retrieval (ChromaDB unused). • Canonical state normalization unifies synonymous state descriptions (6 canonical states). •Keyword-based scoring with exact-match bonuses (+6 for object, +5 for location, +5 for state) and recency tiebreaker. •Schema: 8 structured fields per memory item (task_summary, task_type, target_object, tar- get_location, required_state, action_hint, failure_mode, keywords). F.2 LoCoMo: Multi-Signal Episodic Index The best LoCoMo program builds a hybrid memory combining SQLite and ChromaDB (Listing 6, Listing 7). Each observation is parsed into 7 structured metadata fields (participants, organizations, activities, key facts, relation facts, named entities) and stored in both a relational table and a vector collection. At retrieval time, the program fuses semantic similarity scores from ChromaDB with lexical overlap scores from SQLite, applies person-focused boosting when the query targets a specific individual, limits per-source diversity (at most 2 chunks from any single dialogue), and separately ranks extracted facts by query relevance. The final output combines top-ranked candidate facts and relevant text excerpts. 17 Listing 4: ALFWorld evolved write() — canonical state extraction and fallback parsing. def _canonical_state(self, text): t = (text or "").lower() if any(k in t for k in ["rinse", "wash", "clean"]): return "clean" if any(k in t for k in ["cool", "chill", "cold", "refrigerat"]): return "cool" if any(k in t for k in ["heat", "warm", "hot"]): return "heat" if any(k in t for k in ["examine", "inspect", "look␣at"]): return "examine" if any(k in t for k in ["toggle", "turn␣on", "light"]): return "toggle" return "" def write(self, item, raw_text): required_state = self._canonical_state(item.required_state) or \ self._canonical_state(f"item.task_summary␣item.task_type␣raw_text") # Fallback: extract from raw task metadata when LLM fields are sparse target_object = self._clean(item.target_object) if not target_object: m = re.search(r"object_target: *([A-Za-z0-9_]+)", raw_text) if m: target_object = m.group(1) self.db.execute("INSERT␣INTO␣memories␣(...)␣VALUES␣(...)", (task_summary, task_type, target_object, target_location, required_state, action_hint, failure_mode, json.dumps(sorted(kw)), raw_text[:2000])) Listing 5: ALFWorld evolved read() — weighted scoring with exact-match bonuses. def read(self, query): rows = self.db.execute("SELECT␣...␣FROM␣memories").fetchall() q_tokens = self._tokenize(query.request) | self._tokenize(query.target_object) q_state = self._canonical_state(query.required_state) scored = [] for row in rows: mem_kw = set(json.loads(row.keywords_json or "[]")) score = len(q_tokens & mem_kw)① if q_obj == row.target_object: score += 6② if q_loc == row.target_location: score += 5③ if q_state == row.required_state: score += 5④ score += min(row.id, 1000) / 100000.0⑤ scored.append((score, row)) selected = sorted(scored, reverse=True)[:6] # One LLM call: synthesize top memories into step-by-step guidance synthesized = self.toolkit.llm_completion([...])⑥ return synthesized[:3000] ① Token overlap② Exact object match③ Exact location match④ State match⑤ Recency tiebreaker⑥ LLM synthesis Key architectural properties: • 290 lines of logic, the longest evolved program across all benchmarks. • Dual storage: SQLite for structured metadata + ChromaDB for semantic search. • 7 metadata fields per item including relation facts (subject-verb-object triples). •Source diversity cap: maximum 2 chunks per source document, preventing any single conversation from dominating retrieval. • Two-tier output: candidate facts (direct answer candidates) and relevant excerpts (contextual evidence). F.3 Cross-Benchmark Structural Comparison Table 9 summarizes the architectural differences across all four benchmark domains, illustrating how evolution discovers structurally distinct solutions for each task. G Prompt Templates This section documents the key LLM prompts used in MSTAR. We categorize prompts by their role in the system: task agent prompts (used during evaluation) and reflector prompts (used during evolution). 18 Listing 6: LoCoMo evolved schema — 7 structured metadata fields. @dataclass class KnowledgeItem: summary: str = field(metadata="description": "Short␣summary") participants: list[str] = field( metadata="description": "People␣explicitly␣discussed␣in␣the␣text") organizations: list[str] = field( metadata="description": "Organizations,␣groups,␣or␣institutions") activities: list[str] = field( metadata="description": "Activities,␣hobbies,␣events␣mentioned") key_facts: list[str] = field( metadata="description": "Atomic␣factual␣statements␣useful␣for␣QA") relation_facts: list[str] = field( metadata="description": "Subject-verb-object␣facts") named_entities: list[str] = field( metadata="description": "Exact␣named␣items:␣orgs,␣games,␣places") Listing 7: LoCoMo evolved read() excerpt — hybrid scoring and source diversity. def read(self, query): # Phase 1: Semantic retrieval from ChromaDB results = self.collection.query(query_texts=[query_text], n_results=24) for rank, doc_id in enumerate(ids): semantic_scores[doc_id] = 1.25 / (rank + 1) + 1.0 / (1 + dist) # Phase 2: Lexical scoring from SQLite for row in rows: lexical = self._overlap_score(query_tokens, doc_tokens) person_boost = 1.2 if focus_person matches participants else 0.0 scores[doc_id] += 2.1 * lexical + 1.0 * info_overlap + person_boost # Phase 3: Source diversity enforcement for doc_id, _ in ranked_pairs: source_id = row_by_id[doc_id]["source_id"] if source_counts[source_id] >= 2: continue① ranked_ids.append(doc_id) # Phase 4: Separate fact ranking for doc_id in ranked_ids: for fact in relation_facts + key_facts: fscore = overlap(query_tokens, fact_tokens) if focus_person in fact: fscore += 0.5② fact_candidates.append((fscore, fact)) # Output: candidate facts + relevant excerpts return "Candidate␣facts: ..." + " : ..."③ ① Max 2 chunks per source② Person-focused boost③ Two-tier output format G.1 Task Agent Prompts The task agent interacts with evolved memory programs through three fixed prompt templates. These templates are parameterized by the program’sINSTRUCTION_*constants, meaning evolution can steer the agent’s behavior by modifying these constants without changing the prompt structure. Knowledge item generation.Given raw text and aKnowledgeItemschema, the task agent extracts structured information: INSTRUCTION_KNOWLEDGE_ITEM Text: raw_text The KnowledgeItem must conform to this schema: schema Output ONLY a valid JSON object matching the schema fields. No explanation. Query generation. Given a question and aQueryschema, the task agent formulates a retrieval query: INSTRUCTION_QUERY Question: question 19 Table 9: Structural comparison of best evolved programs across benchmarks. Each program was evolved from the same three seeds with identical hyperparameters. BenchmarkLines SQLite ChromaDB LLM in read Schema fields Test LoCoMo290 ✓No70.408 ALFWorld (Unseen)97 ✓—Yes80.881 HB-Emergency220 ✓—Yes70.493 HB-Data195 ✓—Yes60.390 PR-Legal350 ✓Yes210.660 PR-Finance240 ✓—Yes100.586 The query must be a JSON object matching this schema: schema Respond with the JSON only. Answer generation. Given retrieved memory, the task agent generates an answer.The ALWAYS_ON_KNOWLEDGE constant, if non-empty, is prepended to the retrieved content: <retrieved_memory> ALWAYS_ON_KNOWLEDGE retrieved </retrieved_memory> INSTRUCTION_RESPONSE G.2 Reflector Prompt The reflector receives the current program, its evaluation score, underperforming cases, and optional context (reference programs, lineage history), and outputs a V4A patch to improve the program. The complete prompt template is shown below. Sections inbracesare populated dynamically at each iteration; optional sections (lineage log, write examples, success cases, reference programs) are included only when available. Interface specification. The following specification is provided to the reflector to define the KnowledgeBase API: You are designing a Knowledge Base Program that implements three classes: 1. **KnowledgeItem** (dataclass): Defines what information is captured as knowledge items when writing to the knowledge base. - Must be a @dataclass with typed fields - An external LLM will populate instances by generating JSON matching your field definitions - **Field types MUST be JSON-compatible**: use only str, int, float, bool, list[str], Optional[str] - Do NOT use datetime, tuple, bytes, or custom objects - Use ‘field(metadata="description": "...")‘ to describe fields 2. **Query** (dataclass): Defines what parameters are used when reading from the knowledge base. - Same constraints as KnowledgeItem 3. **KnowledgeBase** (class): The core knowledge base system. - ‘__init__(self, toolkit)‘: Receives a Toolkit with: - ‘toolkit.db‘: sqlite3.Connection (in-memory SQLite) - ‘toolkit.chroma‘: chromadb ephemeral client - ‘toolkit.llm_completion(messages, **kwargs) -> str‘: LLM for reasoning, summarization, and information extraction (1 call per write/read invocation) - ‘toolkit.logger.debug(message)‘: Debug logging - ‘write(self, item: KnowledgeItem, raw_text: str) -> None‘ - ‘read(self, query: Query) -> str‘ Allowed imports: json, re, math, hashlib, collections, dataclasses, typing, datetime, textwrap, sqlite3, chromadb 20 ## Runtime Constraints - ‘read()‘ output limit: at most 3000 characters. - ‘write()‘ / ‘read()‘ timeout: 60 seconds each. - ‘toolkit.llm_completion()‘ budget: at most 1 LLM call per ‘write()‘ or ‘read()‘ invocation. The budget resets before each call. ## Instruction Constants (required) Four module-level string constants: - INSTRUCTION_KNOWLEDGE_ITEM: What to extract and how to structure it. - INSTRUCTION_QUERY: How to formulate retrieval queries. - INSTRUCTION_RESPONSE: Answer format, length, and style. - ALWAYS_ON_KNOWLEDGE: Persistent context injected into every task agent prompt. Can be empty. Patch format specification. The reflector is instructed to output changes in V4A patch format: Before the patch, output a commit message summarizing your changes: *** Commit Message Title: <one-line summary of what you changed and why> - <root cause / diagnosis> - <what you changed> Then output your changes as a V4A patch. IMPORTANT: You MUST output the exact markers ‘*** Begin Patch‘ and ‘*** End Patch‘ on their own lines. Do NOT wrap them in code fences. Format: *** Begin Patch *** Update File: program.py @@ <optional context hint> context line (1-2 lines before change) -removed line +added line context line (1-2 lines after change) *** End Patch Rules: - Lines prefixed with ‘-‘ are removed, ‘+‘ are added, ‘ ‘ (space) are unchanged context. - Include 1-2 context lines before and after each change. - Multiple hunks are allowed within one ‘*** Update File‘ block. Main reflection prompt.The following is the complete prompt template sent to the reflector LLM at each mutation step: You are an expert Python programmer specializing in knowledge base system design. Your task: Given a Knowledge Base Program, its evaluation score, and underperforming cases, identify the root cause of each low score and improve the program. Improvements are two-fold: (A) **Prompt Optimization** -- tune the four instruction constants (especially ALWAYS_ON_KNOWLEDGE) to steer the task agent’s ␣behavior,␣and (B)␣**Memory␣Design**␣--␣improve␣the␣KnowledgeItem/Query␣schemas␣and ␣KnowledgeBase␣storage/retrieval␣logic. Both␣dimensions␣matter␣and␣should␣be␣considered␣together. <interface_spec> KB_INTERFACE_SPEC </interface_spec> <rules> 1.␣Output␣your␣diagnosis␣first,␣then␣your␣changes␣as␣a␣patch. 2.␣The␣code␣must␣define␣exactly␣three␣classes␣(KnowledgeItem,␣Query, ␣KnowledgeBase)␣and␣four␣module-level␣string␣constants ␣(INSTRUCTION_KNOWLEDGE_ITEM,␣INSTRUCTION_QUERY, ␣INSTRUCTION_RESPONSE,␣ALWAYS_ON_KNOWLEDGE). 3.␣KnowledgeBase.__init__␣must␣accept␣‘toolkit‘;␣write␣takes␣a ␣KnowledgeItem;␣read␣takes␣a␣Query␣and␣returns␣str. 4.␣‘read()‘␣must␣return␣at␣most␣3000␣characters. 5.␣Keep␣it␣simple.␣Make␣minimal␣changes␣that␣generalize␣beyond␣the ␣specific␣cases␣shown␣--␣no␣hardcoded␣word␣lists␣or ␣case-specific␣pattern␣rules. 6.␣**Prompt␣Optimization**:␣Update␣INSTRUCTION_*␣to␣steer␣the␣task ␣LLM’s output format. Update ALWAYS_ON_KNOWLEDGE with domain 21 strategies, heuristics, and behavioral rules the task agent should always follow -- this constant is injected into EVERY task agent action/decision prompt and is often the highest-leverage change. Study the <model_generation> transcripts in the underperforming cases to identify agent behavioral patterns (e.g., looping, inefficient exploration, wrong object selection) that ALWAYS_ON_KNOWLEDGE can fix. 7. **Memory Design**: Improve KnowledgeItem/Query field schemas and KnowledgeBase read()/write() logic to store and retrieve more useful information for the task agent. 8. Add clear comments explaining WHY each part of the code works the way it does -- this helps future iterations understand and preserve your design decisions. </rules> <patch_format> PATCH_FORMAT_SPEC </patch_format> <current_program iteration="iteration"> ‘python code ‘ </current_program> <evaluation_score>score</evaluation_score> lineage_section train_section memory_debug_logs success_section reference_section The following cases show poor performance on the validation set after memory has been written. Each case contains the full retrieval-and-answer conversation trajectory. <underperforming_cases> <case id="1"> <question>question</question> <rationale>expected_answer</rationale> <model_generation>model_output</model_generation> <score>case_score</score> <conversation> [user]: query_generation_prompt [assistant]: query_json [user]: <retrieved_memory>...</retrieved_memory> instruction [assistant]: answer </conversation> </case> ... </underperforming_cases> <task> 1. Diagnose why these cases scored low -- examine both the retrieval conversation AND the <model_generation> transcript for agent behavioral issues. 2. Propose improvements along two dimensions: (A) **Prompt Optimization**: How should INSTRUCTION_* and ALWAYS_ON_KNOWLEDGE change to steer the task agent better? (B) **Memory Design**: How should the schemas or storage/retrieval logic change to provide more useful information? 3. Output your changes as a patch. </task> Optional sections. The following sections are conditionally included when their data is available: • Lineage log: Evolution history of the current program’s lineage (ancestors, children, regres- sion markers), formatted as commit-style entries with delta scores. Regression markers (← REGRESSION) flag changes that hurt performance, instructing the reflector not to repeat them. •Write examples: Sample knowledge ingestion trajectories showing how the external LLM gener- ates knowledge items from raw document text and how write() is called. • Success cases: Cases where the current program performed well, instructing the reflector to preserve the behavior that makes these work. 22 •Reference programs: Higher- or lower-scoring programs from the population, with instructions to study which design patterns (e.g., use ofllm_completion, ChromaDB vs. SQLite, schema granularity) correlate with scores. •Memory debug logs: Outputs oftoolkit.logger.debug()calls withinwrite()andread(), providing visibility into program execution. Underperforming case selection. At each iteration, 2 failed cases are sampled from the rotating validation set using the Efraimidis–Spirakis weighted sampling algorithm with weightw i = 1−score i , biasing selection toward lower-scoring cases while maintaining diversity. G.3 Compile-Fix Prompt When a mutated program fails to compile or violates runtime constraints, a compile-fix prompt is sent to the reflector with the broken code and error details: You are an expert Python programmer. A Knowledge Base Program failed to compile or run. Fix the error and output your fix as a patch. KB_INTERFACE_SPEC ## Broken Code ‘python code ‘ ## Error **error_type**: error_details Fix the error and output your fix as a patch. Up to k compile-fix iterations are attempted before the mutation is discarded. H Evaluation Protocols Each benchmark uses a task-specific evaluation metric. All metrics return a score in[0, 1]; the fitness function J (P ) averages these scores across the evaluation set. Token F1 (LoCoMo). Following Rajpurkar et al.[11], we compute token-level F1 between the model output and the expected answer. Both strings are lowercased, articles (“a”, “an”, “the”) are removed, and all punctuation is stripped. Precision and recall are computed over the resulting token multisets: F 1 = 2·|out∩ exp| |out| +|exp| .(5) If both token sets are empty, the score is 1.0; if exactly one is empty, the score is 0.0. Binary success (ALFWorld). The agent interacts with the TextWorld environment for up to 50 steps. A score of 1.0 is assigned if the task is completed within the step budget; 0.0 otherwise. Rubric-based scoring (HealthBench, PRBench).Each evaluation item includes a structured rubric with multiple criteria, each assigned a point value (positive for desirable traits, negative for undesirable ones). An LLM judge independently grades each criterion by examining the conversation and the last assistant response, returning a JSON object with anexplanationand a booleancriteria_met field. For negative criteria (e.g., “Is overly verbose”), a good response should be graded asfalse (the undesirable trait is not present). The score is computed as: score = clip P i: met i p i P i: p i >0 p i , 0, 1 ! ,(6) wherep i is the point value for criterioniandmet i indicates whether the criterion was judged as met. Negative criteria that are met subtract from the numerator. This protocol follows the official HealthBench evaluation methodology [3]. The LLM judge uses the following prompt template for each criterion: 23 Table 10: Complete per-category results: ALFWorld Unseen (success rate by task type). 8 episodes with corrupt PDDL states excluded (n=42; see Appendix K). Bold: best per column. Simple MovableCleanLightCoolHeat2-Obj (n=8)(n=1)(n=11) (n=1) (n=7) (n=6) (n=8) No Memory0.881.000.820.000.570.830.62 Vector Search0.621.000.640.000.710.670.62 G-Memory1.001.000.551.000.290.830.75 Mem00.881.000.640.000.571.000.75 Trajectory Retrieval0.751.000.730.000.710.670.75 ReasoningBank1.001.000.551.000.570.830.75 Dynamic Cheatsheet1.001.000.361.000.001.000.75 GEPA0.881.001.000.000.861.000.62 GEPA + Vector Search0.881.001.000.000.571.000.62 MSTAR0.881.000.911.001.000.830.75 Table 11: Complete per-category results: ALFWorld Seen (success rate by task type). Bold: best per column. SimpleCleanLightCoolHeat2-ObjOverall (n=2) (n=12) (n=2) (n=8) (n=7) (n=15) No Memory1.000.331.000.500.430.870.60 Vector Search1.000.421.001.000.290.870.68 G-Memory1.000.331.000.120.290.870.52 Mem01.000.251.000.620.430.870.60 Trajectory Retrieval1.000.581.000.880.430.930.74 ReasoningBank1.000.331.000.250.430.800.54 Dynamic Cheatsheet1.000.171.000.380.000.730.44 GEPA1.000.501.000.880.430.800.68 GEPA + Vector Search1.000.921.001.000.290.800.78 MSTAR1.000.421.000.750.570.800.70 Note: The ALFWorld Seen split does not include the pick_and_place_with_movable_recep category. Bold marks the best per column; GEPA+VS achieves the highest overall (0.78), the only configuration where MSTAR does not lead. Your job is to look at a conversation and a rubric item, and score the last turn (the last assistant response) on how well it follows the rubric item. # Conversation <<conversation>> # Rubric item <<rubric_item>> # Instructions Return a json object with fields: "explanation" and "criteria_met". - "explanation": why the response does or does not meet the criteria. - "criteria_met": boolean. If a rubric item has multiple criteria, all must be met to return true. - Exception: if criteria says "such␣as" or "for␣example", the response need not include all listed examples. - For negative criteria (undesirable traits), return whether the criteria IS met (true = bad behavior present), not whether the response is good. I Extended Per-Category Results Table 4 in the main paper reports per-category results for ALFWorld Unseen and LoCoMo with selected baselines. Here we provide the complete per-category breakdown for all benchmarks and all baselines. 24 Table 12: Complete per-category results: LoCoMo (token F1 by question category). Cat 1: single- hop recall. Cat 2: temporal reasoning. Cat 3: causal reasoning. Cat 4: open-domain. Bold: best per column. Single-hopTemporalCausalOpen-domainOverall (n=18)(n=18)(n=9)(n=55) No Memory0.020.000.110.040.04 Vector Search0.190.290.380.250.26 G-Memory0.230.120.310.240.23 Mem00.330.260.370.430.33 Trajectory Retrieval0.180.330.340.280.26 ReasoningBank0.250.070.340.190.23 Dynamic Cheatsheet0.140.000.220.140.13 GEPA0.090.060.240.150.13 GEPA + Vector Search0.160.380.390.310.28 MSTAR0.330.190.350.510.41 HealthBench and PRBench each evaluate on single-category splits (emergency referrals, health data interpretation, legal reasoning, and financial reasoning). Their per-category scores equal the overall scores reported in Table 1; we omit separate per-category tables for these benchmarks. J Extended Stability Analysis Table 3 in the main paper reports summary statistics (mean, standard deviation, coefficient of variation) across five evolution seeds. Here we provide the full per-seed results. Table 13: Per-seed test scores across stability experiments. Seed 0 corresponds to the main experiment (Table 1); seeds 1–4 use different random evolution seeds with identical hyperparameters. Best BL: strongest non-evolution baseline. Test Score by Seed Benchmark01234Mean±StdCVBest BL LoCoMo0.408 0.463 0.364 0.394 0.423 0.410.0378.9%0.373 HB-Data0.390 0.382 0.357 0.411 0.413 0.391.0235.9%0.327 PR-Finance0.586 0.544 0.582 0.582 0.513 0.561.0325.7%0.449 On LoCoMo, 4 out of 5 seeds exceed the strongest baseline (Mem0, 0.373). The single exception (seed 2, 0.364) falls within 2.4% of the baseline, consistent with the higher variance inherent to LoCoMo’s multi-category evaluation. On HealthBench Data and PRBench Finance, all 5 seeds exceed the respective strongest baselines (GEPA+VS at 0.327; GEPA at 0.449) by substantial margins, demonstrating consistent improvement regardless of initialization. Table 14 reports the best validation score achieved during evolution for each seed, which determines the program selected for final test evaluation. Table 14: Best validation score during evolution by seed. These scores are computed on the static validation subset and determine which program is selected for test evaluation. Best Validation Score Benchmark01234Mean±Std LoCoMo0.333 0.273 0.289 0.312 0.333 0.308.027 HB-Data0.424 0.381 0.378 0.397 0.380 0.392.020 PR-Finance0.521 0.522 0.559 0.554 0.515 0.534.020 25 K ALFWorld Corrupt Episode Exclusion The ALFWorld benchmark generates interactive household environments from PDDL specifications. We found that 8 of the 50 test episodes in the unseen split contain corrupt PDDL states: the environment initializes with zero admissible commands, making the episode unsolvable regardless of the agent’s memory program. These 8 episodes span two task categories: 6 of 7 look_at_obj_in_light episodes and 2 of 10 pick_and_place_simple episodes. The seen split is unaffected. Because the corruption is environment-level and independent of the memory program under evalua- tion, we exclude these 8 episodes from all reported ALFWorld Unseen scores. The effective test set size isn=42. Table 15 shows the impact of this correction on overall scores. All method rankings are preserved; the correction slightly widens the gap between MSTAR and baselines because MSTAR genuinely solves a larger fraction of the valid episodes. Table 15: ALFWorld Unseen score correction. Original scores include 8 corrupt episodes scored as 1.0; corrected scores exclude them (n=42). MethodOriginal (n=50)Corrected (n=42)∆ MSTAR0.9000.881−0.019 GEPA0.8800.857−0.023 GEPA + Vector Search0.8400.810−0.030 No Memory0.7800.738−0.042 Mem00.7800.738−0.042 ReasoningBank0.7800.738−0.042 Trajectory Retrieval0.7600.714−0.046 G-Memory0.7400.690−0.050 Vector Search0.7000.643−0.057 Dynamic Cheatsheet0.6800.619−0.061 During evolution, the validation set (a separate 50-episode subset) contains 14 corrupt episodes (28%). Because all candidate programs encounter the same corrupt episodes, relative fitness comparisons remain valid and the selection pressure is unaffected. 26