MemQuilt: Context-Budget-Aware Submodular Memory Selection for LLM Agents

Long-term memory enables large language model agents to reuse past information, but its effectiveness depends on which memories enter their limited working context. Existing memory-selection methods estimate individual values from relevance, utility, or task-specific signals. However, pointwise ranking may select memories that repeatedly support the same requirements, while similarity-based diversification does not ensure task complementarity. Moreover, under a context budget, lengthy memories may displace complementary evidence, and selecting a fixed number of memories may add low-value context after the required evidence has been recovered. To address these limitations, we propose **MemQuilt**, a set-aware memory selection framework that integrates individual value, task-requirement coverage, and memory-context cost through set-conditioned marginal utility. Specifically, MemQuilt proceeds in three stages: (i) missing-requirement analysis identifies missing task requirements, (ii) requirement-conditioned memory assessment estimates a requirement-support vector for each candidate, and (iii) context-budget-aware submodular selection selects a memory set using an objective that combines individual value with concave requirement coverage. If no missing requirement is identified, MemQuilt returns an empty memory context. Otherwise, cost-aware greedy selection and threshold stopping determine when further context is no longer worthwhile. Extensive experiments on MS-TOD, Mem2Act, and LoCoMo demonstrate that MemQuilt consistently achieves empirical Pareto improvements in task performance and memory-context cost across different memory units and evidence structures. Notably, relative to Top-K, MemQuilt improves SlotAcc by **11.17** percentage points while reducing memory-context tokens by **38.8%** on MS-TOD.