acceptodds
Under review as a conference paper at ICLR 2027

Remember What Cannot Be Recovered: Memory Allocation from Theory to Frontier Agents

Abstract

Language-model agents sustain extended interactions through context compaction, persistent memory, and retrieval, choosing what to remember and what to recover later under uncertainty about future needs and recovery resources. An agent may omit a dependency from memory if alternative paths preserve the answers it needs, but that dependency becomes necessary when unavailable components block those alternatives. For ordered random workflows, we quantify the average number of edges and bits needed to preserve every answer. In the small-average-error regime we analyze, we construct an asymptotically optimal memory by arranging retained connections so that surviving routes branch and reconnect, providing alternative paths between many source-target pairs using the same stored edges. We then test whether frontier language models can choose what to remember. On random and real citation graphs, models asked to write the memory fall far short: DeepSeek V4-Pro, GLM 5.2, and Muse Glimmer 30B do no better than randomly chosen edges, and on citation graphs most of their errors are avoidable isolation errors, in which every stored neighbor of an endpoint fails, an event that an even allocation of the budget makes much less likely. Telling models how our theory spreads the budget reduces these errors for a model that follows the advice, but its memories still do no better than random ones: avoiding isolation is necessary, yet good memories also depend on which routes are kept, and the models do not work this out from the graph. Our results show that what an agent should remember depends on how its information can be recovered rather than on how important it looks, and that current models do not yet make this choice on their own.

Primary area:
causal reasoning
Keywords:
Causal Inference, Agents

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_rHwvOpenReview ↗
Rating
1
Confidence
2
Informativeness
2
Presentation
1
Soundness
3
Read review
Paper summary

The authors consider the problem of answering directed reachability queries given node removals, from a compressed representation: e.g., given a graph GG, how much of it do we need to store so that given u,v∈Gu, v \in G and F⊆GF \subseteq G, we can answer (u,v)(u, v) reachability queries in G∖FG\setminus F? They also consider variants of this problem in graphs with edge-failure probabilities, causal graphs, and "AND networks." They also provide error probability results under a random graph model. The authors provide an analogy between these graph reachability queries and the memories stored by an agent that must reason over external information that may become unavailable at a later time. In experiments, the authors test whether LLMs can select good edge sets to answer robust reachability queries and find they perform no better than random edge sets, and significantly worse than a greedy baseline.

Critical strengths

There are some interesting theoretical questions studied about how much of a graph needs to be stored to answer robust reachability queries under node removal. A clear presentation of these results on random graphs and causal graphs could make for an interesting algorithms paper.

Critical weaknesses
  1. The paper is difficult to read as the writing quality and clarity are low. The motivation and takeaways for the results are also not clear. This is severe enough that it is hard to evaluate the paper and needs to be improved dramatically before publication.
  2. The connection between DAG reachability results and agent memory is very tenuous. Calling these graphs "memories" or "workflows" is a confusing layer of interpretation over the core graph results. It would be much clearer if presented as an algorithms paper at a different venue, without the agent memory dressing. This particular setting of memory in agents (workflows with external information sources that may become unavailable) seems rather niche, and it's not clear how much of the theory is useful for thinking about agent memory systems in practice.
Questions for authors
  1. Is there a figure that compares the LLMs, the LLMs with advice, and the baselines? Table 2 seems to be missing greedy.
  2. Is Greedy "the best memory we can compute" (line 320)? Is there no better algorithm? Is it really an upper bound on Dμ∗D_\mu^*? Couldn't some clever combination of edges answer more training request with lower budget?

Comments

  • The k-core of a graph is a different existing concept, so renaming would be helpful for disambiguation
  • We don't learn much from the experiments: it's not surprising that LLMs do a bad job of choosing a good edge set.
  • The paragraph break formatting is very strange. on page 1, there seem to be a number of paragraph breaks but no spacing between them. Later in the paper, some (but not all) paragraphs have space between them. Is there some \vspace compression being used?
  • some examples of clarity issues:
    • "one route may suffice, every prerequisite may be required, or contributions may add up" is extremely vague; what is a "route"? what does it mean for "contributions" to "add up"?
    • Example 4 is very confusing for a non-genetics audience. What is a latent gene program and what does it mean to weaken a program?
    • in general, these examples don't do a good job of introducing the key idea (OR, AND, ...), which is buried under extraneous details like "the public index, a company mirror, or a vendored copy" necessary. A clearer approach would be to explicitly define each workflow type, and then provide minimal examples that show how those occur in practice (without distracting extra details)
    • what does "OR memory is transitive reduction" mean?
    • "AND workflows need only the transitive reduction" is also unclear.
    • Theorem 3.1 uses undefined notation ≡k\equiv_k and undefined jargon "compatible graph"
    • "To leading order in the weight scale" does not parse
  • Prop 3.5 is just the corollary of theorem 3.1 stated below ("Hence ∣E(Corek(G))∣|E(\text{Core}_k(G))| is the exact...")
  • In Figure 4B, where is the dashed line? It's not visible.
2 comments

We thank the reviewer for the comments on presentation and scope.

Q1: “The paper is difficult to read … The motivation and takeaways for the results are also not clear.”

We thank the reviewer for pointing out the flaws in writing, and will revise it to make things clearer.

Q2: “The connection between DAG reachability results and agent memory is very tenuous.”

The connection is one specific memory function: keeping the dependencies that let an agent recover information when some resources become unavailable. The stored edges are the memory, and the reader answers from them after failures. Conceptually, these can be thought of as world knowledge and the agent wants to keep the necessary logical links, Learning the dependencies and writing free-form summaries, for instance, are outside our scope, and we will clarify the framing accordingly.

Q3: “We don’t learn much from the experiments: it’s not surprising that LLMs do a bad job of choosing a good edge set.”

It is worth pointing out that choosing a good edge set on small graphs is not apriori a task too difficult for modern LLMs, which reportedly have achieved superior reasoning capabilities. Moreover, experiments show why the models fail, proving further insights. On citation graphs, 80%–97% of model errors come from query endpoints whose stored neighbors all fail; one GLM memory spends 117 of its 128 edges on links from three papers. A prompt telling GLM to spread its budget raised the share of covered vertices from 0.350.35 to $0.80, yet its loss only fell to that of random edges, which reveals a second requirement: links between nearby vertices. In a new experiment, GLM 5.3 still lost 0.87610.8761 when shown the vertex order and given feedback, against 0.8130.813 for random edges.

Q4: “Is there a figure that compares the LLMs, the LLMs with advice, and the baselines? Table 2 seems to be missing greedy.”

We will add Greedy and Balanced to the guidance table, so that all conditions appear together.

Q5: “Is Greedy ‘the best memory we can compute’ … Is there no better algorithm?” “Is it really an upper bound on DμD_{\mu}?”

Greedy is our strongest tested algorithm rather than an established optimum, and we will drop that phrase to avoid confusion. Greedy's loss still bounds the optimum from above because Greedy's memory is one of the allowed memories: Dμ∗(B,G)≤Dμ(Hgreedy;G)D_{\mu}^*(B,G)\le D_{\mu}(H_{\mathrm{greedy}};G) by definition. The reported test loss estimates Greedy's loss over the full request distribution.

Q6: “The k-core of a graph is a different existing concept, so renaming would be helpful for disambiguation.”

We agree with this point and will use alternative names such as “fault-tolerant reachability core”.

Q7: “‘One route may suffice, every prerequisite may be required, or contributions may add up’ is extremely vague.” “Example 4 is very confusing for a non-genetics audience.”

In an OR workflow, one surviving directed path suffices. In an AND workflow, a target needs all of its ancestors. In a linear model, each path contributes the product of its coefficients, and the total effect is their sum. We will revise Example 4 to make it more direct: observed variables mix latent variables, and the data cannot separate direct from indirect effects.

Q8: “What does ‘OR memory is transitive reduction’ mean?” “‘AND workflows need only the transitive reduction’ is also unclear.”

Without failures, an OR answer is whether a directed path exists, and the transitive reduction is the smallest subgraph that preserves all such answers. An AND target can be produced exactly when none of its ancestors fails, and the transitive reduction is the smallest subgraph that preserves every vertex's ancestors, so it suffices for any number of failures. We will revise both statements.

Q9: “Theorem 3.1 uses undefined notation ≡k\equiv_k and undefined jargon ‘compatible graph’.” “‘To leading order in the weight scale’ does not parse.”

G≡kJG\equiv_k J means that the two graphs give the same answer to every request with at most kk failures. We will restate this in the theorem and replace “compatible graph” with “graph with the same answers.” “To leading order in the weight scale” means that all coefficients are multiplied by a small ss, and the result describes the s2s^2 term of the loss as s→0s\to0.

Q10: “Prop 3.5 is just the corollary of theorem 3.1 stated below.”

We agree and will label it as a corollary.

Q11: “The paragraph break formatting is very strange … Is there some \\backslash vspace compression being used?”

Yes. The main text reduces paragraph spacing due to page limit. We will make it more consistent.

Q12: “In Figure 4B, where is the dashed line? It’s not visible.”

In the middle panel (k=20k=20), the gray dash-dot Balanced curve almost coincides with the black Greedy curve, which hides it. We will add distinct markers and labels.

Thanks for the clarifications! I think these changes will improve the paper in a future revision.

For the current submission, the clarity and writing issues were too significant to be addressed in post-review revisions (the examples that I shared were a small selection). A fresh re-review would be needed to make sure the paper is in a better state, so I'm keeping my original score

Reviewer_xiQ4OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies how much dependency structure an agent will need to store in order to answer all queries under failures of unavailable components.

For ordered random workflows it provides an exact fault-tolerant core for all-pairs OR reachability and an asymptotic small-error budget law. The optimal construction arranges retained edges so that surviving routes branch and reconnect.

The paper experimented DeepSeek V4-Pro, GLM 5.2, and Muse Glimmer 30B to choose which edges to keep on random and citation graphs. These models are not outperforming randomly chosen edges, and most citation-graph errors are isolation errors. One can reduce the errors by telling a model how the theory spreads the budget, but its memories still do no better than random.

Critical strengths

The reporting is transparent. The appendices disclose failed preregistered rate checks, invalid model outputs, the absence of multiple-comparison correction, and unavailable raw records for some earlier studies. This makes the claims easy to calibrate.

The OR-reachability theory is exact and checked. Theorem 3.1 and Corollary 3.2 give a clean characterization of the minimum fault-tolerant memory. Exhaustive enumeration on 384 small graphs confirms Proposition 3.5. This part could stand as a contribution to fault-tolerant reachability on its own, and it does not depend on the agent experiments.

Critical weaknesses

1. The agent experiment measures unaided combinatorial search which implies little about agent memory.

In this paper: the writer receives entire dependency graph, request distribution and the budget, and returns a ranked list of edges in one call. The comparison is against a greedy algorithm that simulates failures on 2,000 training requests. The paper itself suggests that letting the agent simulate failures, as the greedy writer does, may close the gap (page 9) -- if this is the case then the headline finding reduces to the observation that a language model without tools cannot run greedy search over a large edge list.

The prompts also shuffle the list so the vertex order is hidden (page 32), yet the theory's own good construction depends on that order. Its nearest-successor memory reaches a loss of 0.45, against 0.82 for uniform random edges at the same budget ( see Table 8). The evidence in this paper cannot separate a failure to allocate memory from one to infer a withheld coordinate. The title refers to frontier agents,however, we don't have agent acts over time and no memory is written during a task. Also, the only memory format allowed is an edge list. The four motivating example workflows shown on page 2 (customer support, refunds, package setup, gene regulation) never appear in the experiments.

2. The paper combines two loosely connected studies.

The main text includes an asymptotic theory of random DAG sparsifi-cation together prompt-based edge selection. At the tested scale in the paper, the experiments confirm only the directional part of the theory. The paper states that, the tested graphs lie outside the regime of Theorem 3.6 (page 7 of main text), and the preregistered checks of equal normalized rates fail (Table 6 of main text). On citation graphs, the construction behind Theorem 3.6 falls well behind greedy (0.68 against 0.46). The causal-model result (Theorem 3.7) has no experimental support.

Most importantly (as i ask in the following question box), I cannot clearly tell whether the theory is necessarily integral to the conclusion, or can predict the empirical results the paper present.

Questions for authors
  • Does model-written memory still work at the level of uniformly random edges? A result at that level would support the stated conclusion. A result near greedy would show that the experiment measures unaided search.
  • Can you please explain why is an edge subgraph of a fully known graph the right model of agent memory? In the motivating workflows, the agent would store notes or summaries and would not see the full dependency graph in its prompt. Can the authors evaluate a memory format that agents actually use, at a matched token budget?
  • Clarification question: What role do Appendices J.2 to P play in the paper's argument? If these studies support the claims, the missing collection code and duplicate responses should be released. If they do not, the citation in Section 4.4 should be removed.
2 comments

We thank the reviewer for the questions.

Q1: “The agent experiment measures unaided combinatorial search which implies little about agent memory.”

Choosing a small subgraph that preserves future answers is indeed a combinatorial problem, and our experiment measures how well a model solves it without tools: the model sees the graph, the request distribution and the budget, and an ideal reader scores the memory it writes. Greedy shows what a feasible algorithm achieves with more computation. Therefore, our perspective is that selective agent memory itself is also a combinatorial task, especially when the memory is limited compared with the knowledge it is expected to encode. This is actually the main motivation of this work, and we will make it more explicit in future revisions.

Q2: “Does model-written memory still work at the level of uniformly random edges?”

Yes. Under the tested protocols, the models do not consistently beat random edges. On citation graphs, the three models lose 0.880.88–0.890.89, random edges 0.840.84, and Greedy 0.460.46. The gap remains with the provded extra guidance prompt.

Q3: “The evidence in this paper cannot separate a failure to allocate memory from one to infer a withheld coordinate.”

We agree for the original experiment. In a new experiment on GLM-5.3 we test this by showing the vertex order on the same 12 graphs. Showing it changed the loss by +0.0305+0.0305 without feedback (95% interval [−0.0144,0.0779][-0.0144,0.0779]) and by +0.0141+0.0141 with feedback ([−0.0144,0.0466][-0.0144,0.0466]), so the order did not help this model. We will describe Balanced as a reference that uses the order.

Q4: “Why is an edge subgraph of a fully known graph the right model of agent memory?” “Can the authors evaluate a memory format that agents actually use, at a matched token budget?”

An edge subgraph makes the stored information explicit, lets an ideal reader and a model read the same memory, and puts model-written and algorithmic memories in the same format. Natural-language notes at a matched token budget are a different format that we did not evaluate, and we will limit our conclusions to graph memory.

Q5: “The paper combines two loosely connected studies.” “I cannot clearly tell whether the theory is necessarily integral to the conclusion, or can predict the empirical results the paper presents.”

The theory defines what a memory must preserve and how small it can be, while the experiments measure how close model-written memories come. The theory does not predict a real model's performance (and is not established to do so), but it identifies the general failure patterns we measure. The event in our lower bound, an endpoint whose stored neighbors all fail, causes 80%–97% of model errors on citation graphs, against 51% for random edges. A prompt targeting it raised the share of GLM's covered vertices on random graphs from 0.350.35 to 0.800.80, but loss fell only from 0.800.80 to 0.710.71.

Q6: “The tested graphs lie outside the regime of Theorem 3.6 … the preregistered checks of equal normalized rates fail.”

We agree: the experiments do not verify the sharp constant, and we report the failed checks. Exhaustive search on 384 small graphs confirms the exact zero-loss boundary. Larger graphs show only the qualitative trend that loss falls more slowly as more vertices fail. The balanced approach follows the idea of the construction in the theory, but has no optimality guarantee. We will align the abstract and captions with these limits.

Q7: “The causal-model result (Theorem 3.7) has no experimental support.”

The reviewer is correct on this. No experiment tests it with agents since it is within an idealized setting. The appendix checks the local calculation numerically on three- and four-node graphs; at s=0.01s=0.01, the computed loss is 0.9920.992–1.00011.0001 times the predicted leading term.

Q8: “What role do Appendices J.2 to P play in the paper’s argument? If these studies support the claims, the missing collection code and duplicate responses should be released.”

They are supplementary, and the theorems, the budget law and the main model comparisons do not depend on them. The duplicate responses of the recovery-state study are retained, and we will release them in future versions.

I still cannot appreciate the connection between theory and experiment parts in this paper. Also, the concerns I raised are largely unresolved (e.g. Q4), meanwhile the authors admitted some weaknesses i find critical. (Q6). I will keep my score

Reviewer_tENoOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This paper investigates which information should be memorized versus what can be retrieved later in agent memory. Assuming a known dependency graph, the authors analyze the minimum number of connections that must be preserved to continue answering questions when some resources become unavailable.

Critical strengths
  1. Theorem 3.4 and 3.6 analyze the core size and the optimal budget when a small average error is allowed, and offer theoretical contributions.
  2. The experiment is comphrehensive.
Critical weaknesses
  1. The paper assumes that the dependency graph and the patterns of failure are known, and then provide accurate answers based on this graph. In practice, however, determining these dependencies and assessing whether information can be recovered are, is the significant challenges for agent memory. Consequently, it remains unclear to what extent these findings can actually assist agents in making decisions about what to retain in their memory.
  2. The paper assigns independent weights to indirect relationships, but the conclusion holds only for the model as defined by the authors and cannot be directly generalized to other contexts.
  3. Please clarify if numbers are based on different statistical scopes in Figure 10.
  4. Many conclusions depend on assumptions that author set, which are not commonly applied.
Questions for authors
  1. How to obtain the dependency graph and the executable recovery path ?
  2. How are Theorem 3.7 and causal model related ?
  3. Does divide the budget evenly minimize isolation errors on all graphs, or only under specific assumptions ?
  4. Clarify the assumption for limited compressibility of linear effects ?
2 comments

We appreciate the reviewer for recognition of the theoretical contributions and experimental coverage. Below is our responses to the reviewer's questions.

Q1: The paper assumes that the dependency graph and the patterns of failure are known … determining these dependencies and assessing whether information can be recovered are … significant challenges for agent memory.

“How to obtain the dependency graph and the executable recovery path?”

Our analysis assums a supplied dependency graph to isolate a subsequent problem: which dependencies should survive compression under a storage budget? In the writer experiments, the model receives the graph, request distribution, and budget, and selects a memory without external search or optimization tools, and is scored by an ideal reader. This directly measures the quality of its selection under the specified prompt and inference settings. Learning the graph and verifying executable recovery paths are important upstream tasks, and conditioning on them lets us study the selection task separately.

Q2: “The paper assigns independent weights to indirect relationships, but the conclusion holds only for the model as defined by the authors and cannot be directly generalized to other contexts.”

“Many conclusions depend on assumptions that author set, which are not commonly applied.”

We agree that the precise rates depend on to the stated models. The idealizations make the problem exactly solvable, which identifies what determines the required memory: an edge must be stored exactly when at most kk failures can block all of its alternative paths. This result (Theorem 3.1 and Corollary 3.2) holds for every DAG, as do the zero-loss boundary and the isolation lower bound. Only the expected core size and the sharp budget use the random-graph model, and the mechanism they identify also appears on real citation graphs, where endpoint isolation accounts for 80%–97% of model-writer errors.

The independent weights on indirect relationships appear only in the causal extension. The independence assumption affects how errors below the core are weighted, but not the exactness of the memory. The exact causal memory is Corek(G)\mathrm{Core}_k(G) without the independence assumption; what depends on it is the exact proportionality to the OR loss and the budget constant. We will state these dependencies next to each result.

Q3: How are Theorem 3.7 and causal model related?

Theorem 3.7 connects the causal loss defined in Section 2 to the OR loss. The causal setting has latent Gaussian variables, an unknown invertible observation mixing, and soft interventions that change incoming coefficients and the target’s noise variance. Under this model, minimizing the leading causal approximation loss is equivalent to minimizing the OR loss. We will explain their connections more directly in the main text.

Q4: “Does divide the budget evenly minimize isolation errors on all graphs, or only under specific assumptions?”

We do not establish that equal allocation minimizes isolation errors on every graph. The isolation lower bound applies to every ordered host under the stated request distribution, but the construction attaining the sharp budget is proved for ordered random graphs in the theorem’s regime.

The paper reports evidence beyond a universal equal-allocation rule that the theory assumes. On citation graphs, Balanced has average normalized loss 0.680.68, compared with 0.460.46 for Greedy, and Greedy’s retained degrees are not uniform. Even on random graphs, keeping random successors at each vertex gives loss 0.750.75 at k=20,d=2k=20,d=2, while keeping nearby successors gives 0.450.45.

Q5: “Clarify the assumption for limited compressibility of linear effects?”

The result considers a fixed graph, independent mean-zero Gaussian edge coefficients with common variance s2s^2, squared error over the total-effect matrix, and the limit s→0s\to0. The retained topology is selected without observing the realized coefficients, although the retained weights may subsequently be optimized.

Under these assumptions, the leading normalized loss is the fraction of original edges omitted. Refitting retained coefficients cannot remove the first-order contribution of an omitted edge.

Q6: “Please clarify if numbers are based on different statistical scopes in Figure 10.”

Yes. The panels use different sets of cases because one DeepSeek call in the Hidden condition never returned a usable allocation. The reward panels use the 31 cases with all Hidden and Revealed scores for both models. Of these cases, 16 were designed to have low value of state information and 15 high value. The interval [0.42,1.98][0.42,1.98] covers all 32 cases. Note that it is the range of the 32-case mean as the missing score varies from 0 to 1. Even its upper end is below our prespecified 5-point threshold. The allocation panels use all 64 model–case pairs, because every Revealed response is available.

Thank you for your detailed responses. Your explanations helped me better understand the assumptions and theoretical results of the paper. However, I still have some concerns about their applicability to real-world agent memory settings, so I will maintain my original rating.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.