acceptodds
Under review as a conference paper at ICLR 2027

Efficient Long-Term Memory Compression for LLMs with Submodular Optimization

Abstract

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.

Primary area:
foundation or frontier models, including LLMs
Keywords:
LLM, Memory Compression, Submodular Optimization, Streaming Algorithms

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_4PT9OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper introduces SOMC, which formulates long-term LLM memory compression as submodular optimization under a token budget. It selects existing memory chunks based on coverage, diversity, and query relevance, avoiding repeated LLM-based summarization. The authors develop algorithms for both full-history access and one-pass streaming, with approximation guarantees that depend on chunk granularity. Experiments on LoCoMo and LongMemEval show that SOMC reduces memory size and management costs while maintaining competitive answer quality.

Critical strengths
  1. Selecting original memory chunks avoids repeated LLM-based summarization. The approach is practical and achieves competitive results on two benchmarks.
  2. The paper covers both full-history and streaming access, with approximation guarantees that explicitly account for chunk size.
Critical weaknesses
  1. The theoretical guarantees apply to the submodular objective, not directly to answer quality. Coverage and diversity may not adequately capture the value of evidence that requires reasoning across multiple chunks.
  2. The streaming algorithm maintains multiple candidate sets, so the output budget does not reflect its actual working memory. Peak memory usage, including candidate sets, embeddings, and caches, is not reported.
  3. The static and streaming variants use different coverage objectives, so their performance gap cannot be attributed solely to the restrictions of streaming access.
Questions for authors
  1. In Table 6, replacing STATIC-SMK with density-based greedy under the same objective and budget drops the LoCoMo score from 74.6 to 41.5. Why is the gap so large? Could the authors report objective values, actual token usage, and evidence recall to help explain it?
  2. How much data does STREAMING-SMK actually retain during execution? Does it still offer an advantage when all candidate sets and auxiliary state count toward the memory budget?
  3. Could the static and streaming algorithms be compared using the same coverage objective? This would help separate the cost of not seeing future information from the effect of changing the objective.
Reviewer_fQbGOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes SOMC, which formulates memory selection as a monotone submodular maximization problem subject to a single knapsack constraint. The method directly selects original memory segments, avoiding repeated calls to an auxiliary generative LLM for memory summarization or rewriting. The authors propose STATIC-SMK for full access and STREAMING-SMK for single-pass streaming access; after a query arrives, query-relevant context is selected from the retained memory.

Critical strengths
  1. The problem formulation and theoretical design account for practical information-access constraints. The paper clearly distinguishes two settings: an offline setting in which the complete history can be revisited, and a streaming setting in which discarded memories cannot be recovered. The objective function in the streaming stage also does not use future queries or future reference sets, so it largely avoids introducing offline information. Appendix A clearly explains why the objective is submodular, while Appendices B and C provide the corresponding approximation guarantees and oracle-complexity analyses. In addition, exploiting the small segment-to-budget ratio to strengthen the guarantee is consistent with the needs of practical system design.

  2. Non-generative memory selection demonstrates an appealing quality-cost trade-off. As shown in Table 1, static SOMC produces answer quality fairly close to that of several strong memory systems across different settings. For example, on LoCoMo, its Qwen LLM-Judge score is 74.6, compared with 73.5 for NEMORI; on LongMemEval, the corresponding scores are 61.2 and 60.6. These gaps are modest. The results in Table 2 are also notable: unlike LightMem and NEMORI, SOMC does not require additional calls to a generative model, and its reported compression latency is substantially lower. Overall, these results suggest that long-term memory management need not rely on complex generative compression; directly retaining the original evidence may also be a practical approach.

Critical weaknesses
  1. The source of the improvement over PACMS is not fully isolated. Section 5.2 attributes the advantage to stronger approximation guarantees, but Table 1 compares complete systems with potentially different objectives, chunking, and relevance scoring. These results do not establish that STATIC-SMK itself explains the downstream gains. A stronger worst-case guarantee alone is insufficient evidence for this attribution.

  2. The streaming efficiency claims need clearer resource accounting. Algorithm 2 maintains multiple candidate sets and OneStream state, whereas Table 2 reports final prompt tokens rather than total storage. Static SOMC is also slower than PACMS on both datasets, so the efficiency advantage depends on the comparison.

Questions for authors
  1. Could the authors compare STATIC-SMK with the PACMS solver using identical objectives, chunks, and token budgets, reporting both objective values and downstream answer quality?

  2. Theorem 2 bounds the storage of density instances rather than just the returned memory. What is the peak storage across candidate sets, OneStream state, embeddings, and caches? Please compare streaming updates against repeated static compression under matched total storage budgets.

  3. Sections 3.1 and 4.1 describe memory-bank construction followed by query-aware selection. Was the static memory bank fixed before evaluation queries were revealed? Please specify the storage budgets and whether query-time selection accessed only the retained bank.

  4. Section 5.1 reports five repetitions, but Table 1 gives no uncertainty estimates. Could the authors report paired confidence intervals, especially for the 0.3-point GPT-5/LoCoMo advantage over NEMORI?

Reference: Ghulyani, M., Singh, A., Bharadwaj, K., Nath, A., & Goswami, S. (2026). PACMS: Submodular context selection as a pluggable engine for LLM agents. arXiv preprint arXiv:2606.20047.

Reviewer_LBVAOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
2
Soundness
2
Read review
Paper summary

The paper formulates long-term LLM memory selection as monotone submodular maximization under a token-budget constraint. It proposes Static-SMK for full-access selection and Streaming-SMK for causal maintenance, followed by query-aware context selection. The methods are evaluated on LoCoMo10 and LongMemEvalS.

Critical strengths
  1. Selecting original memory chunks avoids auxiliary generative rewriting and its associated LLM-call costs.
  2. The static and streaming formulations address distinct access constraints, with explicit approximation guarantees for the surrogate objectives.
Critical weaknesses
  1. Unresolved consistency of the LongMemEvalS results. If Table 1 and Tables 4–5 use the same examples and runs, with overall Judge accuracy computed as an example-weighted mean, one common set of category proportions must reproduce all seven shared rows. An independent minimax reconstruction yields a minimum maximum discrepancy of 0.352 percentage points, exceeding the 0.1-point tolerance from rounding category and overall scores to one decimal. Different samples, runs, or aggregation rules could explain this, but none is specified. This prevents a reliable audit of the reported results. Moreover, five repetitions are stated without confidence intervals or per-run results, despite several leading margins being below one percentage point. (Tables 1, 4–5; Section 5.1.)

  2. The claimed explanation for the optimizer's gains is not established. Section 5.2 attributes the advantage over PACMS to stronger approximation guarantees. Yet, under the reported fine-grained query setting, exact marginal-density greedy run until no feasible positive-gain item remains admits a surrogate guarantee of approximately 0.608, versus the approximately 0.570 bound established for Static-SMK using the same granularity cap. These lower bounds do not predict instance-level utility or QA performance. Consequently, the large greedy ablation drops—for example, 74.6 to 41.5—do not establish that stronger guarantees explain the gains. Achieved objective values, budget utilization, stopping rules, and same-candidate-set comparisons are needed to support this interpretation. This is an evidentiary gap, not proof of an implementation error. (Section 5.2; Appendix F.2.)

  3. The defining memory and streaming benefits are insufficiently evaluated. Table 2 measures final prompt length rather than actual memory-bank size or peak working storage. The disclosed multi-instance storage bound is not accompanied by measured memory usage. The advantage of incremental maintenance is also not demonstrated through prefix queries, per-arrival latency, or cumulative cost against periodic recomputation. Furthermore, static and streaming construction use different coverage objectives, so their performance difference does not isolate the cost of causality. (Sections 4.2, 5.3; Appendices C–D.)

Questions for authors
  1. Can one set of per-example judgments, category counts, and an aggregation script reproduce Tables 1, 4, and 5? If not, which evaluation protocols differ?
  2. On identical candidate sets and objectives, what utilities and token counts do Static-SMK and greedy achieve, and what is the exact greedy stopping rule?
  3. What are the actual retained-bank size, peak working memory, and cumulative update/query costs under a common online workload?

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.