PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Bingyu Shen, Boyang Li

arXiv:2609.32805v2cs.AIcs.CLcs.LG

TL;DR

Long-running agents need bounded written states, but rewriting can discard facts before their relevance is known, and task success alone does not distinguish capacity limits from writer choices. The paper decomposes these losses and trains writers to prefer states that support the reader after recursive rewriting. Training improves success when facts are needed soon, while gains shrink with delay.

  • Problem

    Fixed-size written states irreversibly discard history, while task success alone cannot distinguish losses caused by limited state capacity from losses caused by the writer’s choices.

    Source: §1 · pp. 1–2

  • Method

    DSSR scores candidate states by how well a frozen reader acts after the writer recursively carries each state forward, then trains the writer to prefer better-scoring candidates.

    Source: §4 · p. 4

  • Results

    +7.0 [+1.9, +12.2] points of success over the untrained writer when facts are needed soon; the gain shrinks with delay and is significant only at the shortest delay.

    Source: §1 · p. 2

  • Takeaways & Limitations

    Most measured loss comes from writer regret rather than the state budget, and recursively scoring candidates predicts outcomes where fixed-context scoring does not.

    Source: §1 · pp. 2–3

    The gain shrinks with delay because a per-step score cannot credit keeping a fact when its payoff depends on every later rewrite preserving it.

    Source: §5.6 · p. 9, §6 · p. 9

Abstract

from arXiv · show

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. 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 ($\rho = 0.48$), whereas scoring a candidate as a fixed context, as hindsight methods usually do, does not ($\rho \leq 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 and is significant only at the shortest 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.

1 INTRODUCTION

Long-running agents can carry a bounded written state, but each rewrite irreversibly discards history before later needs are known. The paper finds that writer choices, rather than state capacity, account for most loss, and trains writers using the reader’s future decisions.

1 INTRODUCTION

  • Long-task agents use fixed-size states to keep each step’s cost constant, but a dropped fact can reach a later decision only if every rewrite preserves it.Unlike read-time compression, write-time compression occurs before the decision need is known.Source: §1 · p. 1, Figure 1 · p. 2
  • The paper separates decision loss into budget loss, which any same-size state incurs, and write-time regret from the writer’s prospective choices.The distinction identifies which part of the loss a better writer could address.Source: §1 · p. 2
  • A 128-token state holding the true facts wins nearly every game, while prompted language-model writers win at most 17%; almost all loss is write-time regret, which grows with delay.The evaluation uses TextWorld cooking games with controlled fact-to-need delays.Source: §1 · p. 2
  • DSSR trains writers to prefer candidate states that score well when the reader acts after the writer has carried them forward.This recursive score predicts game outcomes (ρ = 0.48), unlike the fixed-context form (ρ = 0.07).Source: §1 · p. 2
  • +7.0 [+1.9, +12.2] points of success: training improves the writer when facts are needed soon, reaching the level of belief- and slot-based prompts.The gain shrinks as delay grows and is significant on held-out games only at the shortest delay.Source: §1 · p. 2

2 RELATED WORK

Prior work studies memory designs for long interactions and compression of contexts at read time. This paper instead measures losses in recursively written states and trains the writer from the reader’s loss.

2 RELATED WORK

  • Memory systems propose compact states, retrievable memories, or constant-memory agents; this paper measures losses in fixed designs and trains the writer alone from a frozen reader’s loss.Prompted baselines mirror free-text summaries, belief lists, fixed slots, and hand-written retention guidelines.Source: §2 · p. 3
  • Read-time compression methods compress context when a query is known, while this paper’s write-time regret measures how far a prospective writer falls short of hindsight compression.The paper also adds a decomposition into budget and writer terms and a lag manipulation verified to create lag.Source: §2 · p. 3
  • DSSR relabels writes using the reader’s future loss and trains writer preferences; readers are behavior-cloned with DAgger iterations.The cited training connections include hindsight relabeling and direct preference optimization.Source: §2 · p. 3

3 CONSTANT-CONTEXT AGENTS AND WRITE-TIME REGRET

A constant-context agent recursively updates a bounded state and acts from that state with the current observation, discarding raw history after each write. The paper defines decision-loss and lag quantities to separate state-budget limits from prospective writer loss.

3 CONSTANT-CONTEXT AGENTS AND WRITE-TIME REGRET

  • The writer updates a state of at most B tokens from the goal, previous state, last action, and new observation; a frozen reader acts from the goal, state, and current observation.The reader is trained once on states from untrained writers and never changes.Source: §3 · p. 3
  • Budget loss is what a B-token state must lose even with hindsight; write-time regret is the additional loss from choosing prospectively what to keep.The decision-loss decomposition compares reader decisions under full history, a same-size hindsight state, and the writer’s state.Source: §3 · pp. 3–4
  • The read-time oracle compresses the full history in one shot using eight samples and the lowest reader NLL, serving as a hindsight reference rather than a bound.A recursively written state can outperform this reference at an individual decision.Source: §3 · p. 3
  • Relevance lag measures the distance from the most consequential past chunk to the decision, and is undefined when removing no chunk increases NLL by at least 0.5 nats.The lag is measured on actual history, regardless of the intended protocol.Source: §3 · p. 4
  • The controlled protocol inserts a seeded random walk of 0, 10, 20, or 40 steps after the recipe reveal; the original pre-reveal walk did not create lag.The revised protocol was adopted before writer training and before the test split was opened.Source: §3 · p. 4

4 DSSR: TRAINING THE WRITER FROM THE READER’S LOSS

DSSR turns the writer’s problem into comparisons among candidate states, scoring them by the frozen reader’s future decisions after recursive rewriting. Training then favors candidates with better scores.

4 DSSR: TRAINING THE WRITER FROM THE READER’S LOSS

  • DSSR compares sibling candidate states by the frozen reader’s ability to make future decisions from them, using the reader’s loss as the training signal.This decomposes writer training into single-turn write problems rather than episode-level reinforcement learning with sparse delayed reward.Source: §4 · p. 4
  • The recursive score rolls the writer forward through logged steps so the reader sees only the resulting state, matching online use; the window form instead exposes raw intervening steps.The two forms disagree for a lossy writer, and DSSR uses the recursive form.Source: §4 · p. 4
  • Training uses round-zero best-candidate distillation, then direct preference optimization on best-versus-worst pairs whose score gap is at least 0.3 nats.The writer is a LoRA adapter, and the prompt remains the unchanged summary prompt.Source: §4 · p. 4
  • The A4 variant samples post-reveal write points only when the input state still contains a recipe directive, making retention or dropping a genuine candidate choice.It writes 12 candidates so both choices appear; this variant produced the selected writer.Source: §4 · pp. 4–5
  • Table 1 reports validation online success and mean write-time regret by lag for B = 128, with B = 256 success for comparison.The caption identifies FULL as unbudgeted and ORACLE-B as privileged; β lies between −0.14 and 0.23 in every B=128 cell.Source: Table 1 · p. 5

5 EXPERIMENTS

In TextWorld cooking games, a small state can preserve the needed facts, but language-model writers often choose poorly, and regret grows with delay. DSSR improves success when facts are needed soon, while its gains shrink as rewrites accumulate.

5.1 SETUP

  • The experiment uses TextWorld cooking games with 240 train, 45 validation, and 90 test games; selection is completed before the test split is opened once.The reader is frozen, and the study tests three state budgets and four lag settings.Source: §5.1 · p. 5

5.2 THE BOTTLENECK IS WRITE-TIME REGRET, AND IT GROWS WITH LAG

  • Recursive scoring is reported to predict return, whereas the window score does not; the figure compares both scores across K values and protocols.Figure 2 summarizes within-write-point correlations for K ∈{1, 4, 12}.Source: Figure 2 · p. 6
  • 98–100% of games are won with ORACLE-B across budgets, while B = 128 LLM-written states win 0–11%; write-time regret rises with fact delay.At B = 128, κ rises from 0.5–0.9 nats at zero lag to 1.1–1.8 at longer lags; the full-history loss stays ≤0.7.Source: §5.2 · p. 6

5.3 TRAINING AND SELECTION

  • A4 is selected after two rounds; the selected writer wins 26.7 / 11.1 / 4.4 / 2.2% at F ′ = 0/10/20/40, versus 2.2 / 2.2 / 0 / 2.2% untrained.Measured sufficiency beats outcome reward under lag by +1.5 [+0.2, +3.0] points; NO-HINT retains the zero-lag gain with a lower command-phrase fraction.Source: §5.3 · p. 7, §5.5 · p. 8

5.4 MAIN COMPARISON ON THE TEST SPLIT:

  • On the 90-game R1 test, DSSR at zero lag beats prompted SUMMARY by +7.0 [+1.9, +12.2] points; untrained BELIEF and SLOTS formats reach the same 6.7–11.1% band.At F ′ ∈{20, 40}, DSSR is +1.5 [-0.4, +3.3] points over SUMMARY, +1.5 [+0.2, +3.0] over OUTCOME, and +0.9 [-0.9, +2.8] over GUIDE; every pre-registered gate on lag gain fails.Source: §5.4 · p. 7, Table 2 · p. 7
  • 10.4% of test games are won by trained DSSR at zero lag versus 3.3% by SUMMARY; all trained variants fall in a 6.7–11.1% band.Under R2, zero-lag ordering is GUIDE 11.1% > DSSR 5.6% > SUMMARY 2.2%.Source: §5.4 · p. 7, Table 2 · p. 7

5.5 ABLATIONS

  • The ablations find no significant pairwise differences among trained writers on 90 games; at B = 64 no LLM writer wins more than 2.2%.Round 0 supplies most of the zero-lag gain, and the zero-lag test seed spread is 3.3–15.6%.Source: §5.5 · p. 8

5.6 WHY THE GAIN SHRINKS WITH DELAY: CREDIT ASSIGNMENT ACROSS REWRITES

  • At 67% of post-reveal write points at F ′ = 40, no candidate contains a recipe directive, so best-of-n cannot select what earlier rewrites dropped.Candidates inherit the previous state; when they differ in coverage, S12 prefers the more complete candidate only at chance level, while later rewrites can still drop the recipe.Source: §5.6 · pp. 8–9, Figure 4 · p. 9

6 LIMITATIONS

The study is a controlled diagnostic of retention, not prospective memory selection, and its results have limits in model scale, long-delay coverage, and reproducibility across GPUs.

6 LIMITATIONS

  • Phase A is scripted, and protocol F′ tells the writer the recipe matters, testing retention of known-relevant facts rather than prospective selection.The study uses only 4B-parameter models, and long delays on Phase-A facts are rare.Source: §6 · p. 9
  • Validation selection picked the weakest test seed, while replicates on a second GPU differ by up to 14 points.Each table therefore uses one GPU.Source: §6 · p. 9
  • DSSR helps only at short and medium delay; GUIDE, which uses task knowledge, remains the strongest budgeted state.The second reader misses its pre-registered bar by one game, and κ is relative to a best-of-eight hindsight compression and a behaviour-cloned reader.Source: §6 · p. 9

7 CONCLUSION AND FUTURE WORK

With fixed context, the dominant loss is the writer’s choices, and the recursive score trains against reader loss. Its benefit fades when later rewrites must preserve facts beyond the writer’s forgetting horizon.

7 CONCLUSION AND FUTURE WORK

  • With a fixed budget, agents lose mainly through write-time regret, which grows with the number of rewrites a fact must survive.The loss is attributed mainly to the writer’s choices rather than the budget.Source: §7 · p. 9
  • A candidate’s value depends on what the reader can do after the writer carries it forward; the recursive score predicts return where a fixed-state approximation does not.DSSR trains the writer using this reader-based score.Source: §7 · p. 9
  • The gain shrinks with delay because a per-step objective cannot credit facts whose payoff lies beyond the writer’s forgetting horizon.The authors propose retention-enforcing roll-forwards, joint training, or a short-to-long-delay curriculum; readers that can request facts back are an alternative.Source: §7 · pp. 9–10

A ENVIRONMENT AND PROTOCOL

The protocol separates scripted fact discovery from later reader decisions and manipulates the time facts must be retained. The appendices specify the reader, writer, state formats, and evaluation setup.

A ENVIRONMENT AND PROTOCOL

  • TextWorld games vary room count and filler delay; train, validation, and test use disjoint seed ranges, and validation and test contain unseen foods and preparations.The environment exposes cleaned feedback, inventory, admissible commands, and privileged fields, which are withheld from the writer and reader.Source: A ENVIRONMENT AND PROTOCOL · p. 13
  • Phase A explores rooms, reveals the recipe at the cookbook, then inserts seeded random-walk filler; Phase B runs until win, loss, unwinnability, or 50 actions.Every ingredient and required tool or appliance is checked to have appeared in a Phase-A observation before the recipe reveal; the writer updates in both phases.Source: A ENVIRONMENT AND PROTOCOL · p. 13

B MODELS, SERVING AND READERS

  • The reader selects among labelled admissible commands from its context and current observation; training behavior-clones the optimal action across history and memory-state variants.Its action loss is the negative log probability of the optimal command, and the LASTK context uses recent raw steps that fit the budget plus the last action.Source: B MODELS, SERVING AND READERS · p. 14
  • R1 reaches 97.8% online success after iteration 2 and meets acceptance, while Phi-4-mini reaches 77.8% and misses the bar by one game.Phi-4-mini plateaus on 12-room games; iteration 2 is used for the transfer test and its shortfall is reported.Source: B MODELS, SERVING AND READERS · p. 14

C STATE FORMATS AND PROMPTS

  • Writer prompts combine the goal, previous state, last action, and new observation, enforce the token budget, and differ by retention instruction.SUMMARY asks for an updated account; GUIDE prioritizes locations and room connections, BELIEF uses confidence-tagged claims, and SLOTS requires three labelled slots.Source: C STATE FORMATS AND PROMPTS · pp. 14–15
  • ORACLE-B renders privileged game facts into a budgeted state, while the read-time oracle selects the lowest-loss hindsight summary from eight samples.ORACLE-B is excluded from writer training and never shown to the writer.Source: C STATE FORMATS AND PROMPTS · p. 15

D METRICS, STATISTICS AND PROVENANCE

The appendix defines relevance lag, paired uncertainty intervals, and checks for privileged-information leakage and run provenance.

D METRICS, STATISTICS AND PROVENANCE

  • Relevance lag is the distance to the history chunk whose removal most increases reader NLL, and is undefined if no removal costs at least 0.5 nats.The measure uses leave-one-chunk-out rescoring on sampled decision points; ties go to the earliest chunk.Source: D METRICS, STATISTICS AND PROVENANCE · p. 16
  • Confidence intervals use paired percentile bootstraps over games, with identical resampled games across conditions and equal weight per game.Intervals are the 2.5–97.5% range from 10,000 resamples; continuation analyses use write points with game-clustered resampling.Source: D METRICS, STATISTICS AND PROVENANCE · p. 16
  • Prompt checks search for privileged strings while allowing facts already observed by that step; run records preserve configurations, seeds, and model hashes.The test split was opened once, and no test episode or audit was rerun afterward.Source: D METRICS, STATISTICS AND PROVENANCE · p. 16

E PRE-REGISTERED GATES AND AMENDMENTS

The study used pre-specified gates and recorded protocol and scoring amendments before the corresponding evaluation stages. A post-test correction re-aggregated stored results and corrected one seed selection without rerunning episodes or changing verdicts.

E PRE-REGISTERED GATES AND AMENDMENTS

  • Amendments A1–A4 were recorded before writer training, second-reader training, or test opening; A5 followed test evaluation.A1 replaced the fixed-state score with the recursive score and changed the lag variable; A2 moved the filler walk after the reveal; A3 lifted a GPU residency rule; A4 added a reachability-restricted arm.Source: E PRE-REGISTERED GATES AND AMENDMENTS · p. 16
  • Table 4 lists pre-registered gates and verdicts, with G1 evaluated on validation games and G2 once on the fixed test split.Its G2b row reports both initial statistics and their correction; intervals are paired game bootstraps.Source: Table 4 · p. 17
  • A5 changed aggregation and corrected one seed selection in the report script, but reran no episode, audit, or decision and changed no gate verdict.The corrected G2b DSSR slope pooled three seeds rather than using seed 0 alone.Source: E PRE-REGISTERED GATES AND AMENDMENTS · pp. 16–17

F DIAGNOSTIC: FULL TABLES

The diagnostic separates budget loss from write-time regret and finds write-time regret dominates budgeted LLM states under the reported protocol. The controlled lag protocol is intended to test retention after a relevant fact is revealed.

F DIAGNOSTIC: FULL TABLES

  • κ dominates in every budgeted LLM cell under protocol F′, while the original pre-reveal filler protocol produced no consistent κ trend.For F = 40 minus F = 0 at B = 128, the contrasts were −0.20, −0.34, and +0.24 nats for SUMMARY, BELIEF, and SLOTS, respectively.Source: F DIAGNOSTIC: FULL TABLES · p. 17
  • The largest leave-one-chunk-out loss increase was attributed to the cookbook block at 87% of decision points.Figure 6 shows κ against post-reveal filler length under protocol F′.Source: F DIAGNOSTIC: FULL TABLES · p. 17
  • Table 5 reports validation success across budgets and κ with intervals at B = 128; β ranges from −0.14 to 0.23 in every cell.The caption specifies 200–270 audited decision points per cell.Source: Table 5 · p. 18
  • On 500 sampled steps where the reader’s argmax differed from a*, its action shortened the oracle plan in 8.8% of cases, so ties add noise rather than bias to δ and κ.The metrics compare decisions under the same a*.Source: F DIAGNOSTIC: FULL TABLES · p. 18

G TRAINING THE WRITER: DATA, HYPER-PARAMETERS AND ROUND-BY-ROUND RESULTS

Training compares candidate memory states using the frozen reader’s future decision loss, then trains the writer to prefer better candidates. The reported validation effects vary by round and lag, while the test materials specify comparisons across delays, readers, budgets, and rewrite counts.

G TRAINING THE WRITER: DATA, HYPER-PARAMETERS AND ROUND-BY-ROUND RESULTS

  • The main training line collected episodes across budgets and filler lengths, sampled write points from both phases, and scored candidate states with recursive scores for K ∈ {1, 4, 12}.The A4 arm retained 2,529 of 3,984 write points and generated 12 candidates; OUTCOME scored episode continuations from 1,000 write points per round.Source: G TRAINING THE WRITER: DATA,… · pp. 18–19
  • Figure 6 reports κ rising within the first ten post-reveal rewrites and staying high for writer formats, while ORACLE-B remains below zero.Table 7 is described as reporting κ, β, and full-history loss by relevance-lag bin; it also attributes the largest chunk-removal effect to the cookbook in 441 of 532 points (83%).Source: Figure 6 · p. 19, Table 7 · p. 20
  • Round 0 used supervised fine-tuning on the best candidate, and rounds 1–3 used DPO on best-versus-worst pairs with score gaps of at least 0.3 nats.The training recipe included a 0.5-weighted likelihood term on the chosen state; variants used the same recipe.Source: G TRAINING THE WRITER: DATA,… · p. 19
  • Validation κ contrasts were mixed across rounds and lags: main-line round 2 reduced κ by 45% at F′=0, while its lag contrast was 0%.The reported intervals were game-paired; A4’s pooled three-seed lag contrast at round 2 was −3% [−19, +20].Source: G TRAINING THE WRITER: DATA,… · p. 20
  • A4 round 2 was selected with 11.1% validation success at B = 128 averaged over F′, ahead of K=1 round 1 at 7.2% and main-line DSSR round 1 at 5.0%.The selected configuration was retrained from the same initialization and pairs with two additional seeds.Source: G TRAINING THE WRITER: DATA,… · p. 20, Table 12 · p. 22

H TEST SPLIT: INTERVALS, TRANSFER READER, BUDGET FRONTIER, REWRITE

  • Table 14 reports test-split replicate-GPU budget-frontier success (%) at F′ = 0/10/20/40 for B = 64, 128, 256: FULL 95.6/95.6/96.7/94.4; ORACLE-B 98.9/98.9/98.9/97.8 at every budget.Figure 9 compares test-split κ against F′ for writers trained with K = 1, 4, and 12; the K = 12 A4 line is the three-seed mean.Source: Table 14 · p. 24, Figure 9 · p. 25
  • Figure 10 compares κ against F′ on the test split for untrained formats, three DSSR seeds and their mean, and variant writers.Figures 11 and 12 plot mean κ by rewrites since reveal on validation and test games, respectively.Source: Figure 10 · p. 25, Figure 11 · p. 26, Figure 12 · p. 26

I EXPLORATORY LAG GRID ON VALIDATION

The validation lag-grid exploration indicates that the selected writer’s success advantage over SUMMARY diminishes at longer delays, with uncertainty varying by lag. Qualitative examples show cases where the trained state preserves task-relevant recipe and location information that the summary state omits.

I EXPLORATORY LAG GRID ON VALIDATION

  • At B = 256, the three seeds’ gain over SUMMARY held at every tested filler length, while GUIDE remained above them.The reported seed gains over SUMMARY were 31.9 / 17.0 / 19.3 / 14.1 / 12.6 points at F′ = 0/5/10/20/40; GUIDE’s were 40.0 / 31.1 / 31.1 / 31.1 / 22.2.Source: I EXPLORATORY LAG GRID ON VALIDATION · p. 28
  • Raw success curves were affected by whether episodes began in the kitchen, but conditioning on start room turned the reported curves into monotone decays with lag.The passage attributes remaining bumps to single-seed noise.Source: I EXPLORATORY LAG GRID ON VALIDATION · p. 28
  • Across the exploratory validation grid, the selected writer’s success gain over SUMMARY was significant at short and medium lags, smaller at long lags, and indistinguishable from zero at extra-long lags.This was a post-hoc validation exploration; the test split was not reopened.Source: I EXPLORATORY LAG GRID ON VALIDATION · pp. 27–28

J QUALITATIVE EXAMPLES

  • A separate SUMMARY example lost the recipe after 40 filler steps, and the reader’s later wrong cooking action made the game unwinnable.The fatal action was cooking carrot with the stove instead of taking red bell pepper from the fridge.Source: J QUALITATIVE EXAMPLES · p. 28
  • In one test-game comparison 69 steps after reveal, the trained state retained ingredient and room-graph information and led the reader to a*; the SUMMARY state produced a wrong option.The stated NLL values were 0.00 for the trained state and 2.27 for SUMMARY.Source: J QUALITATIVE EXAMPLES · pp. 28–29

Related papers

Loading 2609.32805v2…