acceptodds
Withdrawn from ICLR 2027

Decision-Sufficient State Representations: Measuring and Reducing Write-Time Regret

Withdrawn from ICLR 2027, so left out of the paper lists and the map.

Abstract

Long tasks produce more history than an LLM agent can hold in its context, and more than it uses reliably even when the history fits. A growing line of work therefore has agents carry a short written state instead: at every step a writer rewrites the state, and a reader acts from the state alone. Steps stay cheap, but anything the writer drops is lost before later decisions reveal that they need it. We quantify this loss and ask whether training can reduce it. Comparing the written state with the best state of the same size written in hindsight, we split the reader's loss into a budget loss, which any state of that size must incur, and a write-time regret, which comes from the writer's choices. In TextWorld cooking games where we control how long a fact must be carried before it is needed, a 128-token state holding the facts wins nearly every game, while prompted language-model writers win at most 17%. Almost all of the loss is write-time regret, and it grows with the delay. Creating a real delay takes care: steps inserted between a fact and its use delay it only if they do not show the fact again. We then train the writer from the reader's own loss. DSSR (decision-sufficient state representations) scores candidate states by how well the reader acts after the writer carries them forward, and teaches the writer to prefer the better ones. This forward-rolled score predicts game outcomes (ρ = 0.48; 0.26 under the delayed protocol), whereas scoring a candidate as a fixed context, as hindsight methods usually do, does not (ρ ≤ 0.07). On a pre-registered test split opened once, training adds +7.0 [+1.9, +12.2] points of success when facts are needed soon, bringing a plain summary writer to the level of belief- and slot-based memory prompts. The gain shrinks as the delay grows: on held-out games it is only at the shortest delay, and our pre-registered tests for a gain under long delay fail. A hand-written rule that names what to keep, using task knowledge the writer is not given, does better at every delay. We trace this limit to credit assignment: keeping a fact now pays off only if every later rewrite keeps it too, which a per-step score cannot see. Anonymous codebase: https://anonymous.4open.science/r/AgentDSSR

Primary area:
foundation or frontier models, including LLMs
Keywords:
LLM agents, agent memory, memory compression, long-horizon decision making, credit assignment

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

The paper examines the viability of using a small discrete memory of tokens which is rewritten after steps to store relevant information. The paper diagnoses that the failure to succeed here is primarily a problem of knowing which facts to write rather than having enough space to write. Training a writer model to function better against the reader's loss yields a modest +7% improvement in keeping the critical facts over short horizons (but not long horizons). These modest gains are traced to credit assignment issues.

Critical strengths

The paper does careful experimentation to address and diagnose how a system (re)writing a discrete memory approach for a reader model fails and how to train it to perform better.

Critical weaknesses

There's a different approach to gaining learning signal which is likely significantly advantageous here. In particular, AggreVaTe https://arxiv.org/abs/1406.5979 diagnoses the problem and provides an approach to solve via rollout with a reference policy which seems valid here. There are followups like LOLS which can bring performance even higher.

Separately, the few% performance gain here seems near to the noise level in evaluations since observed noise is of a similar scale (table 2 says 3.3 / 15.6 / 12.2).

Another less serious issue is that portions of the language have formalized definitions of the literature but are used in an informal way here. The authors may want to examine:

L. Li, T. J. Walsh, and M. L. Littman. Towards a unified theory of state abstraction for MDPs. ISAIM 2006.

J. Subramanian, A. Sinha, R. Seraj, and A. Mahajan. Approximate information state for approximate planning and reinforcement learning in partially observed systems. JMLR 23(12):1–83, 2022

Write-time regret related: L. Peshkin, N. Meuleau, and L. P. Kaelbling. Learning policies with external memory. In Proceedings of the 16th International Conference on Machine Learning (ICML), pages 307–314, 1999 N. Meuleau, L. Peshkin, K.-E. Kim, and L. P. Kaelbling. Learning finite-state controllers for partially observable environments. In Proceedings of the 15th Conference on Uncertainty in Artificial Intelligence (UAI), pages 427–436, 1999.

Questions for authors

No questions.

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

The paper studies constant-context LLM agents, in which a writer recursively rewrites a fixed-size text state and a frozen reader acts from it. It splits the reader’s decision loss into budget loss and write-time regret, and shows in TextWorld cooking games that regret dominates and grows with the delay between observing a fact and needing it. The proposed DSSR trains the writer with distillation and DPO, scoring each candidate state by the reader’s likelihood of expert actions after rolling the writer forward from it.

Critical strengths

Provide a useful diagnostic: the budget-vs-writer decomposition, the controlled-lag protocol. Also provide a rigorous, honest evaluation with failure analysis.

Critical weaknesses

The method’s design cannot solve the identified problem. The writer is a recurrent model with a discrete text state. As the paper section 5.6 points out, scoring each write under a fixed greedy continuation of the current writer amounts to one-step credit assignment: once text is dropped, the signal is exactly zero. So the absence of gains under delay is expected by design. Multi-step remedies (e.g., multi-turn RL on the writer) are dismissed rather than tested.

The performance gain over non-trained methods (BELIEF) seems marginal. The method is also complex relative to its gains: reader behavior cloning with DAgger, best-of-n distillation, three DPO rounds, a reachability filter, and selection among several lines. All results come from one environment with scripted exploration, 4B models, and a single behavior-cloned reader.

Questions for authors

See the weaknesses.

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

This paper studies bounded textual memory for LLM agents and proposes DSSR, which trains a writer using a frozen reader’s future action likelihoods after recursively rewriting candidate states. The paper combines this training procedure with controlled experiments on memory delay.

Critical strengths

Evaluating a candidate state through subsequent rewrites is well motivated. The recursive score correlates with actual continuation returns, providing useful support for the design. Training also improves short-delay test success over the same SUMMARY writer, from 3.3% to 10.4%, with a reported gain of 7.0 percentage points and a 95% interval of [1.9, 12.2]. The paper clearly reports its unsuccessful long-delay results and substantial seed variability.

Critical weaknesses

1. The algorithmic contribution is relatively narrow. Recursive memory updates and task-driven memory training already appear in related work. DSSR’s main distinction is its candidate-level recursive scoring objective, combined with established distillation and preference optimization. The paper should explain more precisely what this objective adds beyond existing memory-learning approaches.

2. The positive empirical signal does not yet establish a clear advantage for the proposed method. The short-delay improvement over SUMMARY is meaningful, but the resulting performance is comparable to untrained BELIEF and SLOTS prompts and below GUIDE. GUIDE uses additional task knowledge, which qualifies this comparison, but the overall practical advantage remains unclear. At longer delays, the improvement over SUMMARY is not statistically distinguishable from zero, and the preregistered improvement tests fail.

3. The evidence for the specific scoring design remains incomplete. The correlation experiment supports recursive scoring as an evaluation signal, but does not directly establish its contribution to training gains. The reported advantage over OUTCOME uses the selected A4 configuration, which also changes write-point filtering, candidate count, and temperature. Please clarify whether OUTCOME shares these settings. I do not expect exhaustive ablations, but a matched comparison, or an existing result that resolves this ambiguity, would substantially strengthen the case.

Questions for authors

DSSR shows a positive improvement over SUMMARY at short delay, but its performance is comparable to the simpler BELIEF and SLOTS prompts, and no reliable improvement is observed at longer delays. Given these results, what is the main empirical case for the proposed training procedure? In particular, which results best demonstrate its added value over these simpler alternatives, and in what setting would the authors expect it to be useful?

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

Related papers

Discussion (0)

Sign in to comment.