acceptodds
Under review as a conference paper at ICLR 2027

MemPrice: Online Memory Allocation via Adaptive Pricing for Long-Horizon Agents

Abstract

Long-horizon LLM agents face a fundamental allocation problem as interaction histories grow: which information to retain, how much context to devote to it, and at what granularity. Existing memory mechanisms largely focus on relevance, retrieval, or compression, leaving this allocation trade-off implicit. We introduce MemPrice, which treats active context as a shared resource and dynamically allocates it across memories and representation levels. MemPrice turns accumulated memory pressure into an adaptive price on context, encouraging detail only when its estimated retention value justifies the additional footprint. This pressure persists across memory refreshes, allowing the contents of memory to evolve while preserving long-run control over context usage. We show that irreversible compression can force linear worst-case regret against hindsight following its own memory trajectory, and introduce a same-state benchmark to evaluate allocation on MemPrice's realized memory states. MemPrice enforces the hard context budget at every round and regulates long-run occupancy through adaptive pricing, without prior knowledge of the interaction horizon. Under priced-frontier regularity, its average allocation-regret bound against this benchmark vanishes when accumulated estimation error is sublinear. We evaluate the framework under matched memory budgets on LongMemEval, LoCoMo, AppWorld, and WebShop across three foundation models, spanning both query-blind memory construction and goal-directed agent context management.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Agent Memory, Resource Allocation

Reviews

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

This paper focus on the problem of memory allocation in long horizon agents. The paper frames it as an optimization problem over utility (from an LLM oracle), and price augmented budget and provide an algorithm. The paper provided a theoretical bound on the regrets versus a hindsight method. The paper tested 3 capable LLMs on long context benchmarks and found that their method exceeded the baselines on all setting.

Critical strengths
  1. The paper is timely, well motivated:

    • The introduction and motivation explanation is easily understandable.
    • Proofs seems to be correct with respect to their assumptions.
    • Explicit memory allocation for long running agents in lieu of pure compaction is well motivated and I expect this topic to grow quickly. I think this is well placed in the literature with some papers already exploring similar avenues, and works to bridge context compression method to context management methods.
  2. The overall method is reasonable and the result looks very promising.

    • The methods, while convoluted, are well thought of and elegant.
    • Under some assumptions, the method's error scaled sub-linearly to a hindsight benchmark.
    • The results are the best overall among the baselines
Critical weaknesses
  1. The paper written methodology are dense and hard to understand

    • Several technical terms specific to the methods are never defined explicitly, relies on the reader's familariatity on operation's research topics, or defined too late (e.g. Priced-frontier regularity is mentioned in Introduction and Abstract, which then cannot be fully understood without looking at section 4 and Appendix C)
    • The intuition behind the method choices are unclear or buried in the appendix.
    • Limitations discussion are very limited.
    • There are some inconsistensies in the tables and writing (e.g. GLM LongMemEval FIFO is 34.0 in Table 1 versus 30.4 in Table 3)
  2. The methods is a bit unconvincing, and the analysis lacks systems discussion.

    • Simulated results in the tables are very concerning.
    • The priced-frontier regularity is very load bearing for the proofs of the theorems, while the empirical result show promise in many domains, it still might fail on others (Browsing comes to mind where good information is sparse. We can also derive some elementary repeating workflow that violate this assumption) and the queue cant react fast enough. There are no analysis on the applicability of this assumption to the benchmarks tested.
    • The bound provided by Theorem 1 relates to the regrets of cumulative decisions, rather than downstream performance. While this is pedantic, I think its important to state the bound is for the optimality of further allocation and still leave room for error in earlier compression.
    • There are no discussion on cumulative/running memory trajectories, we might imagine that the extra performance vs the baselines can be explained by keeping more token early.
    • There are no explanation on the oracle at all. I think this is warranted as the oracle is the main backbone of the method, but very expensive (generating scores and all possible summaries in a turn), and the extra savings of reduce active context will be offset by the cost of running the oracles
Questions for authors
  1. Table 2 states "All values are simulated targets rather than observed experimental evidence", can you explain what this is? Which of the numbers of the result tables actually come from experiments?
  2. Is there an analysis on the effect/optimality of the five representation levels?
  3. I think the current strongest baseline of adaptive historical memory other than LRE is PACE[1]. I agree that a full experiment will be infeasible and this can count as concurrent work, instead can the authors give a short comparison of their methods (difference, advantage, disadvantage) here in more detail compared to the comparison in the related work section.
  4. Is there an analysis on how refresh window interact with the benchmarks and the comparison of fixed vs capacity-triggered refreshes?
  5. Do you think that your method will scale well beyond 0.6 compression? Is there experiments on sharper compression?

Comment: My overall score reflects the lack of readibility and supporting discussion of the paper rather than the method itself, which shows good result. I'd be willing to increase my score if the authors addresses the concerns. Simulated result declaration in Table 2 is very concerning and might be ground for a desk reject at the SAC/PC discretion, but I'm writing this review with the benefit of the doubt that its either an artifact or a misunderstanding.

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

The paper proposes MemPrice, an online memory-allocation framework for long-horizon LLM agents that combines multiple representation levels with adaptive context pricing. It provides conditional theoretical guarantees and presents evaluations on conversational memory and interactive agent benchmarks.

Critical strengths

The framework explicitly considers the trade-off between estimated retention utility and context occupancy, jointly selecting memory representations under a hard capacity constraint. It also distinguishes the per-round capacity limit from a long-run occupancy target.

Critical weaknesses

The caption of Table 2 explicitly states: “All values are simulated targets rather than observed experimental evidence.” Nevertheless, Section 5.2 treats these values as empirical results and uses them to support claims of consistent improvements across models and benchmarks. The paper does not explain this discrepancy, leaving the empirical claims supported by Table 2 unsubstantiated.

Questions for authors

Are the values in Table 2 simulated targets or measurements obtained from actual experimental runs? Please explain the caption and clarify the provenance of both the reported means and standard deviations, providing verifiable experimental results if these evaluations were conducted.

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

This paper studies how a long-horizon LLM agent should allocate a limited active-context budget across past interaction items, choosing for each item one of five representations (raw, summary, abstract, keywords, delete). MemPrice maintains a virtual queue of accumulated occupancy above a target ratio α\alpha, converts it into a global context price λt=c Qt/t\lambda_t = c\,Q_t/\sqrt{t}, and at each round solves a multiple-choice knapsack that maximizes LLM-estimated retention utility minus the priced footprint under the hard capacity B. The queue persists across periodic memory refreshes in which raw transcripts are archived and BM25 retrieval refills the context. On the theory side, the paper proves a linear regret lower bound against a hindsight policy that follows its own memory trajectory, and, against a same-state hindsight benchmark, a regret bound of cT+2ET+ΔTc\sqrt{T} + 2E_T + \Delta_T together with O(T)O(\sqrt{T}) occupancy violation. Experiments report results on LongMemEval-S and LoCoMo (query-blind) and on AppWorld and WebShop (goal-observable) with three backbones, plus ablations and a sensitivity study on α\alpha.

Critical strengths

(1) The framing of agent memory as an explicit online resource-allocation problem, where relevance alone does not decide whether an item is worth its footprint, is clear. (2) The theoretical discussion separates two sources of hindsight advantage, which is a useful way to state what an online memory allocator can be held accountable for, and the proofs of Proposition 1 and Theorem 1 are correct.

Critical weaknesses

The caption of Table 2 states that "All values are simulated targets rather than observed experimental evidence." As written, the entire goal-observable evaluation on AppWorld and WebShop, the claim that MemPrice "consistently outperforms all baselines across three backbones and both agent benchmarks", and the AppWorld/WebShop columns of Tables 3 and 4 are not experimental results.

Questions for authors

Please clarify the caption of Table 2. Were the AppWorld and WebShop results actually obtained by running AI agents? If so, please provide the run logs (the anonymous repository is referenced), per-seed results, and explain the caption.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.