Efficient Long-Term Memory Compression for LLMs with Submodular Optimization

Large language models (LLMs) increasingly rely on external memory to support long-term interactions, but continuously growing memory introduces substantial storage, token, and computation overhead. Existing memory-management approaches often rely on heuristic retrieval or repeated LLM-based summarization and rewriting, which either provide limited control over redundancy under a fixed budget or incur additional model inference cost. We study long-term memory compression under two practically distinct access regimes. In the full-access setting, the complete candidate memory is available when compression is performed, as in periodically consolidated memory stores and query-time context construction. In the more restrictive streaming setting, memory chunks arrive continuously and must be processed in one pass without access to future interactions or future queries, as in long-running and resource-constrained agents. We propose SOMC, a submodular optimization framework that formulates memory selection as monotone submodular maximization under a single knapsack constraint. SOMC operates directly on existing memory chunks and therefore avoids repeatedly invoking an auxiliary generative LLM for memory summarization or rewriting. For full-access compression, we develop Static-SMK, a granularity-adaptive algorithm with provable approximation guarantees and linear oracle complexity. For continual memory maintenance, we develop Streaming-SMK, which maintains a bounded, query-independent memory state in one pass and subsequently applies Static-SMK for query-aware context construction. Its approximation guarantee improves as individual memory chunks become smaller relative to the available budget, while its oracle complexity is linear in the stream length for fixed accuracy. Experiments on widely used widely used long-term memory benchmarks show that SOMC consistently preserves or improves downstream task performance under substantial memory compression, while reducing the number of processed tokens and end-to-end computational cost compared with model-based compression methods and conventional memory-management baselines. Results demonstrate that principled submodular optimization provides an efficient and model-agnostic alternative for scalable LLM memory management.