MemComposer: Learning to Assemble Memories for LLM Agents via Reinforcement Learning

1 Introduction

• Similarity alone does not guarantee memory usefulness: a less similar memory can provide crucial information that a more similar memory misses.Prior agent-memory work has focused primarily on representations while continuing to rely on similarity-based retrieval.Source: §1 · p. 1, Figure 1 · p. 1
• Memory count and ordering both affect outcomes: the best count differs across domains, and no single ordering is best on average.Reordering the same memory set changes per-task outcomes, while increasing the count does not consistently improve performance.Source: §1 · p. 2, Figure 2 · p. 2
• 16.9% and 4.9% fewer memory tokens across all domains for Qwen3-4B-Instruct and Ministral-3-8B-Instruct, respectively, while outperforming each executor’s strongest baseline.On RETAIL, the reductions are 26.9% and 35.2%, respectively.Source: §1 · p. 2
• The learned policy transfers to unseen domains, executors, and memory banks, and improves performance with memories generated by stronger models without further training.The authors interpret this as evidence that the composer learns to assess memory usefulness for downstream tasks.Source: §1 · p. 2
• MemComposer jointly selects and orders a variable-size subset of retrieved experiences for a frozen LLM agent.It examines the current query and retrieved candidates and is trained with ExPO using complete agent interactions.Source: §1 · p. 2

2.1 Memory for LLM Agents

• Agent memories store experiences, skills, or knowledge for reuse, but are typically recalled by embedding similarity; MemComposer instead decides which memories to include, how many, and in what order.The framework builds a fixed memory bank from reviewed, curated trajectories and assembles contexts as a whole.Source: §2.1 · pp. 2–3, Figure 3 · p. 3

2.2 Learning Context Selection from Downstream Feedback

• Prior context-selection and passage-reranking methods use signals such as gold-output likelihood, relevance labels, or single-answer quality, whereas this setting scores agent trajectories after multi-turn tool use and simulated-user interaction.ExPO estimates the sparse, stochastic reward over repeated executor trials.Source: §2.2 · p. 3

3.1 Problem Formulation

• For a query, the composer selects an ordered subset of distinct retrieved candidates, including the option to select none, and the executor returns a binary task-success reward.The objective is to maximize expected executor success for the selected memory sequence.Source: §3.1 · p. 3

3.2 Self-Generated Memory Bank

• The memory bank contains curated trajectories paired with outcomes and hindsight reviews, collected using a frozen executor and shared across methods for the same domain and backbone.Reviews are validated with deterministic consistency checks before memories are added to the bank.Source: §3.2 · p. 4

3.3 MEMCOMPOSER

• Given candidates from a fixed similarity-based retriever, MemComposer reads the query and candidates jointly and dynamically determines both sequence length and order.Both decisions are learned from task outcomes.Source: §3.3 · p. 4

3.4 Experience Policy Optimization

• ExPO evaluates each assembled sequence through complete downstream interactions and combines empirical success with penalties for memory size and invalid output format.It estimates success across repeated trials to address stochastic execution; the sequence is executed in its presented order, so the reward also trains ordering without a separate ordering objective.Source: §3.4 · p. 4
• ExPO uses GRPO’s clipped surrogate objective with group-centered rewards, discards groups with identical task-outcome rewards, and updates only the composer.The executor, retriever, and memory bank remain fixed; advantages are not normalized by group standard deviation to avoid amplifying noise in groups with nearly identical outcomes.Source: §3.4 · pp. 4–5

4.1 Datasets and Evaluation Metrics

• The evaluation uses RETAIL, AIRLINE, and TELECOM customer-service tasks with a simulated user, reporting pass1 as average success and pass4 as the fraction solved in all four trials.Each task is run four times, and domain averages use equal weighting.Source: §4.1 · p. 5

4.2 Baselines

• Baselines include no memory, similarity- and complexity-based heuristics, untrained model selection, a pretrained reranker, and the RL-based methods MemRL and Memento.For each backbone, methods share the frozen executor, user simulator, and memory bank, and select from the same top-10 candidates.Source: §4.2 · p. 5

4.3 Main Results

• 16.9% fewer memory tokens with Qwen3-4B-Instruct and 4.9% fewer with Ministral-3-8B-Instruct than each executor’s strongest baseline, while achieving the highest average pass1 and pass4 with both backbones.It is best or tied-best in 10 of 12 domain-level comparisons.Source: §4.3 · p. 5, Table 1 · p. 6

5.1 How Does Training Change Experience Selection?

• Training changes selection by drawing from deeper ranks, weakening preference for historically successful experiences, and improving the order of selected experiences.Together, these findings indicate that useful context assembly involves both which memories to include and how to present them.Source: §5.1 · pp. 6–7
• Training raises average selection size from 2.52 to 3.73 experiences and mean similarity rank from 3.21 to 4.35, indicating broader selection from the candidate pool.Figure 4 shows lower-ranked candidates account for a larger share of selections after training.Source: §5.1 · p. 6, Figure 4 · p. 6
• Training lowers the share of successful experiences among selections from 45.5% to 35.6%, narrowing or reversing their advantage across rank bands.At ranks 4–6, the pretraining selection rates are 32% for successful experiences versus 10% for failed or fakepass; after training the gap narrows to 6 points.Source: §5.1 · pp. 6–7, Figure 5 · p. 7
• A failed memory that demonstrates the needed exchange operation raises success from 0/4 to 4/4 trials compared with no memory.The training objective rewards the assembled context’s effect on the current task, not the memories’ past outcomes.Source: §5.1 · p. 7
• The composer’s ordering beats four fixed rules by 3.8 to 8.5 points and 6.1 on average in pass1 when the selected memories are held fixed.Because the memory set is identical, the gain comes solely from order.Source: §5.1 · p. 7, Table 2 · p. 7

5.2 Generalization

• The retail-trained composer outperforms the vanilla selector and both heuristics in AIRLINE and TELECOM, performing comparably to in-domain training.On AIRLINE, pass1 is 53.8 versus 52.5 and pass4 is equal; on TELECOM, it trades 1.2 points of pass1 for 2.5 points of pass4.Source: §5.2 · p. 7, Table 3 · p. 7
• With a Ministral-3-8B-Instruct executor and its own memory bank, the Qwen3-trained composer achieves 70.6 pass1 and 50.0 pass4, beating both heuristics and the untrained composer.Compared with the Ministral-trained composer, transfer has lower pass1 (70.6 versus 75.0) but higher pass4 (50.0 versus 47.5).Source: §5.2 · pp. 7–8, Table 4 · p. 8
• MEMCOMPOSER matches or outperforms similarity top-5 in 9 of 10 domain–bank pairs, improving average pass4 on every unseen bank by 9.1 points on average and 7.5 points with GPT-5.4’s bank.On retail, similarity top-5 with GPT-5.4’s bank performs close to its level with the executor’s own bank.Source: §5.2 · p. 8, Figure 6 · p. 8

6 Conclusion

• MEMCOMPOSER jointly selects and orders a variable-size subset of retrieved experiences for a frozen LLM agent.ExPO learns from downstream task outcomes while keeping the executor, retriever, and memory bank fixed.Source: §6 · p. 8
• Across three τ²-bench domains and two executors, MEMCOMPOSER achieves the highest average pass1 and pass4 among evaluated methods with fewer memory tokens than each executor’s strongest baseline.Further analyses report improved selection and ordering, plus transfer across domains, executors, and memory sources without retraining.Source: §6 · p. 8
• The results highlight the value of learning memory assembly from downstream feedback.Source: §6 · p. 8

Limitations

• Only 4B- and 8B-parameter executors are evaluated, leaving open whether a frontier-scale executor would benefit similarly from a separate composer.The paper also does not characterize how memory-context preferences differ across executors.Source: Limitations · p. 9
• Ordering credit is entangled with selection under sequence-level rewards, and the learned order is not guaranteed optimal because no oracle over all permutations is tested.The authors compare against four heuristic orderings of the same memories.Source: Limitations · p. 9
• Evaluation covers procedural memories—past trajectories with reviews—but not semantic facts and rules or episodic user histories.The interaction between selected items and their order may differ for those other memory types.Source: Limitations · p. 9

A.1 Memory for LLM Agent

• Prior agent-memory work often improves what is stored or organized, while MemRL [Zhang et al., 2026c], Memento [Zhou et al., 2025], and Memory-R1 [Yan et al., 2026] score or operate on memories individually.MEMCOMPOSER instead chooses which memories to include, how many, and in what order, and optimizes the assembled context as a whole.Source: §A.1 · p. 12

A.2 Learning Context Selection from Downstream Feedback

• In-context learning and retrieval-augmented generation methods learn context selection from downstream feedback, including joint demonstration selection and passage reranking.Unlike those methods’ cheaper query-level signals, this setting scores full agent trajectories only after a frozen executor completes a multi-turn tool interaction with a simulated user.Source: §A.2 · pp. 12–13

B Statistical Significance

• Paired bootstrap intervals resample test tasks within domains 10,000 times, compute equal-weight macro-average gaps, and pool both executors without treating them as independent samples.No multiple-comparison correction is applied, so intervals barely excluding zero should be read with that caveat.Source: B Statistical Significance · p. 13, Table 5 · p. 13, Table 6 · p. 13
• MEMCOMPOSER is best or tied-best in 10 of 12 domain-level comparisons and uses 16.9% fewer memory tokens for Qwen3-4B-Instruct and 4.9% fewer for Ministral-3-8B-Instruct than their strongest baselines.Pooled gaps exclude zero on pass1 and on pass4 for every baseline except Complexity and Memento; within-executor strongest-baseline gaps include zero.Source: B Statistical Significance · pp. 13–14

C Memory Bank Construction

• Each agent’s memory bank uses only its own training-split rollouts; eight independent rollouts per task are reviewed, outcome-labeled, consistency-checked, and curated to at most two entries per task.The outcome reward is unchanged; successful rollouts with critical errors are labeled fake pass, while other successful rollouts are clean pass.Source: C Memory Bank Construction · p. 14
• A memory digest averages 1.0K–1.4K tokens for selectors, while the selected full trajectory and review are supplied to the executor; the shared candidate pool contains the ten highest-cosine-similarity entries.Entries are indexed by the user’s first message and embedded with Qwen3-Embedding-8B; training excludes candidates from the same training task.Source: C Memory Bank Construction · p. 14

D.1 Input and Output Format

• The composer receives task instructions, ten retrieved digests, the user’s opening request, and format instructions, then returns a dynamically sized ordered list of distinct candidate indices.An empty list specifies execution without memory.Source: §D.1 · p. 15

D.2 Reward Design Details

• Each valid memory sequence is evaluated over eight completed frozen-executor trials with the task, memories, and order fixed; the mean binary success label supplies the task-outcome reward.Infrastructure-error trials are resampled, and trials are shared when group sequences select the same memories in the same order.Source: §D.2 · p. 15
• Invalid outputs receive zero, while valid outputs missing a reasoning section incur a 0.05 format penalty; repeated indices are deduplicated and an empty list is valid.Source: §D.2 · p. 15
• Selection-size penalties apply only above a free allowance and favor smaller selections only among sequences with equal task outcomes and format penalties.For RETAIL and AIRLINE, Kmax is 0; for TELECOM, λlen is 0.02 and Kmax is 7, while the size penalty never reverses sequences with different task outcomes.Source: §D.2 · pp. 15–16

• Training pairs user-simulator openings with retrieved memory windows, excluding memories from the query’s task; usefulness labels are absent and reward comes from simulated agent runs.Training uses four openings per task and splits top-20 candidates into two windows of ten, except Ministral telecom and airline use the top 10; test tasks use one opening and top-10 candidates.Source: §D.3 · p. 16
• Each composer is trained for 30 policy updates, and the final checkpoint is evaluated.The hyperparameters are provided in Tables 8 and 9.Source: §D.3 · p. 16, Table 8 · p. 16
• Local training costs were 24.2, 16.3, and 81.7 GPU-hours for Qwen and 7.1, 16.2, and 24.9 for Ministral on RETAIL, AIRLINE, and TELECOM, respectively.These figures count local compute only; the user simulator is accessed through an API.Source: §D.3 · p. 16
• Rollout generation and simulation account for 69–91% of wall-clock time per training step, while model updating is inexpensive.TELECOM costs most in both settings because its conversations are longest; Ministral AIRLINE exceeds RETAIL because identical sequences within groups are rarer and fewer trials can be shared.Source: §D.3 · p. 16

E Full Results

• Performance varies non-monotonically with k, and the best budget depends on both domain and executor.Figure 7 compares performance–memory-token trade-offs across two executor backbones and all domains; Table 10 reports similarity- and complexity-based selection across k values.Source: E Full Results · p. 16, Figure 7 · p. 17

F Baseline Implementation Details

• All methods draw from the same retrieved candidate pool, making memory selection rather than retrieval the stated source of method differences.Source: F Baseline Implementation Details · p. 17

F.1 Heuristic Baselines

• Similarity-based selection supplies the k most similar top-10 candidates in descending similarity order, with the best k reported in Table 1.The sweep uses k ∈{1, 2, 3, 5, 7}; additional k results are in Appendix E.Source: §F.1 · p. 17
• Complexity-based selection ranks candidates by rendered token length as a proxy for procedural detail and supplies the k longest first.For k < 10 it selects a different set than similarity-based selection; at k = 10 the methods use the same memories and differ only in order.Source: §F.1 · p. 17

F.2 Off-the-Shelf Reranker

• The off-the-shelf Qwen3-Reranker-8B scores each candidate digest against the user’s first message and supplies the five highest-scoring candidates in descending order.It uses the same candidate rendering as MEMCOMPOSER and is applied without further training.Source: §F.2 · p. 17

F.3 RL-Based Memory Methods

• MemRL combines a growing memory bank with similarity-based candidate proposal and a value phase that keeps memories with the highest estimated usefulness.For the fixed-bank comparison, memory write-back is disabled and only value-aware retrieval is reimplemented.Source: §F.3 · p. 17
• Memento predicts whether a stored case will help on a query and selects the five highest-probability cases from the shared top-10 pool.Its scorer reads case digests, like the composer, and is adapted from the authors’ released code.Source: §F.3 · pp. 17–18
• Memento’s fixed-bank training uses logged training-task episodes only, merging repeated query–case pairs and weighting each by its trial count.It yields 797–3,908 unique pairs per agent–domain cell from 1.2K–233K episode–case observations; some cells provide more supervision than the original online procedure, favoring Memento.Source: §F.3 · p. 18
• Memento uses a 512-token maximum sequence length because 256 tokens truncates 30–60% of digests, and splits training and validation by query.The query-level split ensures no query appears in both sets.Source: §F.3 · p. 18

G Evaluation Protocol

• 40 retail, 20 airline, and 40 telecom test tasks are evaluated using official domain splits, with memory banks built only from training tasks.Results are reported on test tasks.Source: G Evaluation Protocol · p. 18, Table 11 · p. 19
• Qwen3-4B-Instruct-2507 and Ministral-3-8B-Instruct run without parameter updates, and all methods use GLM-4.7 as the user simulator.Episodes end at task completion, user termination, or 50 steps; selected memories enter the system prompt in the selector's order.Source: G Evaluation Protocol · p. 18
• Selections are made once per test task and reused across its trials, while MEMCOMPOSER and the vanilla selector decode greedily.This holds selected candidates constant so trial differences reflect interaction rather than selection.Source: G Evaluation Protocol · p. 19
• Each test task runs for four official-seed trials; pass1 is average success rate, pass4 is the fraction of tasks solved in all four trials, and domain averages are unweighted.The official passk metric estimates the probability of success in all k independent trials.Source: G Evaluation Protocol · p. 19
• Memory-token counts use each agent's tokenizer, include the fixed 172-token header, and assign zero tokens when no memories are selected.Domain values average over test tasks; the three-domain average is weighted by test-trial counts.Source: G Evaluation Protocol · p. 19