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

Bingyu Shen; Boyang Li

cs.AISep 26, 2026

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

Authors: Bingyu Shen, Boyang Li

Organizations: Independent Researcher · Department of Computer Science and Technology Kean University, Union, NJ, USA

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. 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$ ), whereas scoring a candidate as a fixed context, as hindsight methods usually do, does not ( $ρ\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.

Figures & tables

	success, $B{=}128$				$\kappa$ , $B{=}128$				success, $B{=}256$
$F^{\prime}$	0	10	20	40	0	10	20	40	0	10	20	40
full	97.8	97.8	97.8	97.8	–	–	–	–	–	–	–	–
oracle-b	100	100	100	97.8	$-0.19$	$-0.17$	$-0.21$	$-0.15$	100	100	100	97.8
lastk	0	0	0	0	0.71	1.80	1.46	1.46	2.2	0	0	0
summary	2.2	2.2	0	2.2	0.85	1.26	1.47	1.10	20.0	6.7	2.2	2.2
slots	11.1	0	0	0	0.49	1.55	1.38	1.69	15.6	4.4	2.2	0

Table 1: Validation games under protocol

F^{\prime}

B=128

: online success (% of 45 games won) and mean write-time regret

\kappa

(nats) per lag; success at

B=256

for comparison. FULL has no budget; ORACLE-B is privileged (

\approx 47

tokens).

\kappa

is the mean of per-game means;

\beta

lies between

-0.14

and

0.23

in every

B{=}128

cell. Full grid with

\delta

\beta

\kappa

and intervals in Appendix F .

	success (%)				$\kappa$ (nats)
$F^{\prime}$	0	10	20	40	0	10	20	40
full (no budget)	95.6	96.7	96.7	94.4	–	–	–	–
oracle-b (privileged)	98.9	100	98.9	97.8	–	–	–	–
lastk	0	0	0	0	–	–	–	–
summary	3.3	2.2	1.1	0	0.79	1.05	1.35	1.66
belief	11.1	0	0	0	0.57	1.21	1.55	1.73

Table 2: Test split (90 games),

B=128

, reader

R_{1}

: success (%) and

\kappa

(nats, mean of per-game means) per lag

F^{\prime}

. Trained writers are the best validation round of each variant; DSSR is the selected A4 round-2 configuration, mean of three seeds (seeds at

F^{\prime}=0

: 3.3 / 15.6 / 12.2). Intervals,

R_{2}

rows and the budget frontier: Appendix H .

Appendix figures & tables16 assets

Supplementary material from the paper’s appendix.

Appendix

rooms	$F^{\prime}$	Phase-A steps	Phase-B steps	history tokens (mean)	history tokens (max)
6	0	15.7	12.0	2230	2821
6	40	55.7	12.0	6843	9087
9	0	25.0	18.9	4151	5514
9	40	64.8	18.7	9102	10908
12	0	33.5	21.1	4825	6721
12	40	73.3	20.8	9079	11591

Appendix

Table 3: Environment statistics per (rooms,

F^{\prime}

) on the 285 train and validation games: mean Phase-A length (steps), mean Phase-B length of the oracle, mean and maximum full-episode history length in tokens of the reader tokenizer.

gate	criterion	result	verdict
G1a	$\kappa$ grows with lag: $\kappa(F^{\prime}{=}40)-\kappa(F^{\prime}{=}0)>0$ , interval excluding 0, for the write-time formats	1/3 formats on the primary GPU (plateau after ten rewrites), 3/3 on the replicate; in the measured-lag form $\kappa(\ell\geq 5)-\kappa(\ell<5)=+1.08$ [0.24, 1.97]	fail / pass ( $\ell$ form)
G1b	the mean gap $\delta$ predicts online success across cells (Spearman)	$-0.84$ over 76 cells ( $-0.90$ replicate)	pass
G1c	$\rho(S_{12},\text{return})\geq 0.3$ and $\rho(S_{12})-\rho(S_{1})>0$ on Phase-A write points	window form: $0.07$ , fail; recursive form: $0.48$ [0.39, 0.56] under the original protocol, $0.26$ [0.13, 0.43] under $F^{\prime}$ (91/200 write points without return variance)	fail (window)
G2a	at $B{=}128$ , $F^{\prime}\in\{20,40\}$ : DSSR $\geq$ best prompted $+8$ ptsand $\geq$ outcome $+8$ pts(intervals $>0$ ); $F^{\prime}{=}0$ not below $-3$ pts	$+1.5$ [-0.4, +3.3] over summary ; $+1.5$ [+0.2, +3.0] over outcome ; $F^{\prime}{=}0$ : $+7.0$ [+1.9, +12.2]	fail
G2b	$\kappa$ at $F^{\prime}\in\{20,40\}$ reduced by $\geq 40\,\%$ (interval $<0$ ); smaller $\kappa$ -vs- $F^{\prime}$ slope	as first computed: $1.456\to 1.422$ ( $-2\,\%$ ), difference $-0.03$ $[-0.27,+0.20]$ ; slopes $0.022\to 0.012$ per step (seed 0), difference $-0.010$ $[-0.022,+0.003]$ . Corrected (A5): $1.50\to 1.47$ ( $-2\,\%$ ), $-0.03$ $[-0.27,+0.21]$ ; slopes $0.022\to 0.022$ per step (three seeds), difference $+0.000$ $[-0.009,+0.009]$	fail
G2c	$K{=}12$ beats $K{=}1$ at $F^{\prime}\in\{20,40\}$ (interval $>0$ ); the gap shrinks at $F^{\prime}{=}0$	$+1.5$ [-0.4, +3.3] at lag; $+3.7$ [-3.3, +10.4] at $F^{\prime}{=}0$	fail

Appendix

Table 4: Pre-registered gates and verdicts. G1 was evaluated on validation games before training; G2 once, on the test split, with the trained writer fixed. Intervals are paired game bootstraps. G2b gives both the statistics as first computed and their correction (Amendment A5).

format	quantity	$F^{\prime}{=}0$	$F^{\prime}{=}10$	$F^{\prime}{=}20$	$F^{\prime}{=}40$
full	success	97.8	97.8	97.8	97.8
oracle-b	success, $B{=}64/128/256$	100	100	100	97.8
oracle-b	$\kappa$ , $B{=}128$	$-0.19$ [-0.30, -0.08]	$-0.17$ [-0.29, -0.07]	$-0.21$ [-0.29, -0.13]	$-0.15$ [-0.22, -0.09]
lastk	success, $B{=}64/128$	0	0	0	0
	success, $B{=}256$	2.2	0	0	0
	$\kappa$ , $B{=}128$	0.71 [0.54, 0.92]	1.80 [1.39, 2.22]	1.46 [1.10, 1.83]	1.46 [1.03, 1.92]

Appendix

Table 5: Validation grid under protocol

F^{\prime}

(primary GPU): success (% of 45 games) at every budget, and mean

\kappa

with game-bootstrap intervals at

B=128

(200–270 audited decision points per cell).

\kappa

is the mean of per-game means;

\beta

is between

-0.14

and

0.23

in every cell.

	$B{=}64$				$B{=}256$
$F^{\prime}$	0	10	20	40	0	10	20	40
oracle-b	$-0.37$	$-0.22$	$-0.20$	$-0.31$	$-0.26$	$-0.15$	$-0.18$	$-0.25$
lastk	0.63	1.52	1.48	1.32	0.77	1.95	1.65	1.36
summary	0.93	1.42	1.29	1.56	0.42	1.31	1.50	1.50
slots	0.65	1.72	1.60	1.53	0.39	1.92	1.47	1.82
belief	0.70	1.24	1.11	1.45	0.50	1.15	1.05	0.95

Appendix

Table 6:

\kappa

(nats, mean of per-game means) at

B=64

and

B=256

under protocol

F^{\prime}

(validation, primary GPU).

$\ell$ bin	$n$	$\kappa$	$\beta$	$\mathrm{NLL}(h)$	$\kappa$ (thr. 0.3)	$\kappa$ (thr. 1.0)
1–4	107	0.61 [0.38, 0.84]	0.30 [-0.00, 0.59]	0.10	0.60	0.56
5–9	15	1.89 [0.33, 3.78]	$-1.61$ [-3.76, 0.32]	2.58	1.35	2.26
10–19	123	1.97 [1.41, 2.62]	0.01 [-0.27, 0.24]	0.37	1.89	2.21
20–39	146	1.87 [1.41, 2.36]	0.29 [-0.01, 0.57]	0.32	1.87	2.12
40+	141	2.30 [1.75, 2.92]	$-0.22$ [-0.67, 0.15]	0.68	2.18	2.50

Appendix

Table 7:

\kappa

\beta

and the full-history loss against the measured relevance lag

\ell

(validation,

B=128

write-time formats, 900 sampled decision points, 532 with a defined

\ell

at the 0.5-nat threshold; game-bootstrap intervals). The two other thresholds give the same picture. The chunk whose removal hurts most is the cookbook at 441 of the 532 points (83 %), a Phase-A room visit at 78 (15 %) and another Phase-B block at 13.

condition	mean $\kappa$
baseline, $F{=}0$	0.69
baseline, $F{=}40$ (walk before the reveal)	0.45
brief, $F{=}40$	0.92
post, 40 steps after the reveal	1.76
post and brief	1.13
contrast	estimate [lo, hi]

Appendix

Table 8: Protocol pilot ( summary ,

B=128

, 45 validation games, replicate GPU): mean

\kappa

under three placements of the same 40-step walk, and paired contrasts with intervals. “Brief” suppresses the re-printed room contents during the walk; “post” places the walk after the reveal.

writer	round	$F^{\prime}{=}0$	10	20	40	mean
DSSR ( $K{=}12$ )	0	13.3	0	2.2	0	3.9
	1	11.1	4.4	2.2	2.2	5.0
	2	4.4	8.9	4.4	0	4.4
	3	13.3	0	0	2.2	3.9
$K{=}4$	0	6.7	2.2	0	0	2.2
	1	4.4	2.2	0	0	1.7

Appendix

Table 9: Validation success (%) per writer, round and lag (

B=128

; round 0 = SFT, rounds 1–3 = DPO). Untrained summary : 2.2 / 2.2 / 0 / 2.2; guide : 11.1 / 11.1 / 2.2 / 6.7.

writer	round	$F^{\prime}{=}0$	10	20	40	mean
DSSR ( $K{=}12$ )	0	0.71	1.24	1.17	1.70	1.20
	1	0.52	1.60	1.59	1.87	1.40
	2	0.47	1.06	1.17	1.41	1.02
	3	0.79	1.11	1.02	1.14	1.01
$K{=}4$	0	0.94	1.49	1.51	1.36	1.33
	1	0.80	1.30	1.44	1.54	1.27

Appendix

Table 10: Validation

\kappa

(nats, mean of per-game means) per writer, round and lag (

B=128

). Untrained summary : 0.85 / 1.26 / 1.47 / 1.10 (mean 1.17).

candidates	group	$n$	cov. all	cov. best	cov. worst	all zero	differ	best $>$ worst	best $<$ worst
main, round 0	all	2818	0.24	0.23	0.24	0.51	0.09	0.28	0.29
	$F^{\prime}{=}0$	439	0.44	0.44	0.43	0.19	0.20	0.24	0.33
	$F^{\prime}{=}10$	632	0.30	0.30	0.31	0.41	0.10	0.29	0.33
	$F^{\prime}{=}20$	760	0.20	0.19	0.20	0.58	0.07	0.30	0.26
	$F^{\prime}{=}40$	987	0.13	0.13	0.13	0.67	0.05	0.31	0.18
	1–4 steps after reveal	331	0.42	0.42	0.41	0.27	0.25	0.28	0.27

Appendix

Table 11: Credit assignment on the training candidates (post-reveal write points). Coverage = fraction of the recipe’s verb–ingredient directives present in a state; “all zero” = no candidate holds a directive; “differ” = candidates differ in coverage; the last two columns are, among differing points, how often the best candidate by

S_{12}

has higher (lower) coverage than the worst.

	success				$\kappa$
seed	0	10	20	40	0	10	20	40
0 (selected)	26.7	11.1	4.4	2.2	0.61	1.13	1.19	1.46
1	8.9	11.1	2.2	2.2	0.51	1.26	0.91	1.26
2	22.2	8.9	8.9	4.4	0.31	1.34	1.14	1.55
mean $\pm$ sd	19.3 $\pm$ 7.6	10.4 $\pm$ 1.0	5.2 $\pm$ 2.8	3.0 $\pm$ 1.0	0.48	1.24	1.08	1.42
untrained	2.2	2.2	0	2.2	0.85	1.26	1.47	1.10

Appendix

Table 12: Seeds of the selected configuration (A4 round 2) on validation,

B=128

: success (%) and

\kappa

(mean of per-game means) at

F^{\prime}=0/10/20/40

reader	condition	$F^{\prime}{=}0$	10	20	40	$\kappa$ , $F^{\prime}\in\{20,40\}$
$R_{1}$	full	95.6 [91.1, 98.9]	96.7 [92.2, 100]	96.7 [92.2, 100]	94.4 [88.9, 98.9]	–
	oracle-b	98.9 [96.7, 100]	100	98.9 [96.7, 100]	97.8 [94.4, 100]	–
	lastk	0	0	0	0	–
	summary	3.3 [0.0, 7.8]	2.2 [0.0, 5.6]	1.1 [0.0, 3.3]	0	1.50 [1.23, 1.80]
	belief	11.1 [5.6, 17.8]	0	0	0	1.64 [1.36, 1.93]
	slots	10.0 [4.4, 16.7]	0	0	0	1.80 [1.50, 2.12]

Appendix

Table 13: Test split,

B=128

: success (%) with game-bootstrap intervals per lag, under

R_{1}

and

R_{2}

; the last column is the lag

\kappa

F^{\prime}\in\{20,40\}

(mean over games of a game’s mean of its

F^{\prime}{=}20

and

F^{\prime}{=}40

means, so it equals the average of the two cells of Table 2 ) with its interval.

	$B{=}64$				$B{=}128$				$B{=}256$
$F^{\prime}$	0	10	20	40	0	10	20	40	0	10	20	40
summary	0	0	0	0	7.8	0	0	1.1	7.8	1.1	2.2	1.1
belief	2.2	0	1.1	1.1	16.7	1.1	1.1	1.1	16.7	6.7	8.9	2.2
slots	0	0	0	0	12.2	0	0	0	20.0	2.2	0	0
guide	0	0	0	0	16.7	2.2	5.6	2.2	30.0	16.7	15.6	15.6
DSSR (A4 r2, seed 0)	2.2	0	0	0	14.4	4.4	4.4	1.1	18.9	14.4	2.2	5.6

Appendix

Table 14: Budget frontier on the test split (replicate GPU): success (%) at

F^{\prime}=0/10/20/40

for

B\in\{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.

condition	0	1–2	3–5	6–9	10–14	15–19	20–29	30–39	40–59	60+
summary , valid	0.02	1.03	1.24	1.36	1.28	1.73	1.54	1.14	0.94	0.54
DSSR seed 0, valid	0.05	0.39	0.66	0.27	1.07	1.59	1.25	0.59	1.29	1.13
DSSR seed 1, valid	0.01	0.21	0.98	0.71	0.82	1.21	1.31	0.91	1.20	0.38
DSSR seed 2, valid	0.07	0.21	0.61	0.25	0.95	1.37	1.13	0.94	1.49	1.03
guide , valid	0.02	0.82	0.59	0.85	0.73	1.15	0.71	0.90	1.07	0.66
summary , test	$-0.02$	0.68	0.99	1.17	1.15	1.04	1.29	1.10	1.39	0.68

Appendix

Table 15: Mean

\kappa

(nats) by the number of rewrites since the cookbook reveal (audited decision points, validation and test,

B=128

); the number of points per cell is in Table 16 .

condition	0	1–2	3–5	6–9	10–14	15–19	20–29	30–39	40–59	60+
summary , valid	39	67	45	20	152	29	183	44	229	67
DSSR seed 0, valid	26	58	50	43	152	54	182	47	245	65
DSSR seed 1, valid	29	66	53	37	139	56	196	54	246	75
DSSR seed 2, valid	27	57	51	45	153	56	182	64	230	83
guide , valid	33	59	44	32	125	46	187	59	260	50
summary , test	69	132	130	69	247	85	364	107	493	151

Appendix

Table 16: Number of audited decision points per rewrite bin for Table 15 .

split	writer	bin	games	difference [lo, hi]	relative
valid	DSSR (3 seeds)	1–2	39	$+0.83$ [+0.20, +1.65]	$-81$ %
		3–5	30	$+0.64$ [+0.10, +1.25]	$-52$ %
		6–9	11	$+0.60$ [-0.14, +1.63]	$-44$ %
		10–14	44	$+0.27$ [-0.21, +0.73]	$-21$ %
		15–19	15	$+0.22$ [-1.13, +1.65]	$-13$ %
		20–29	43	$+0.28$ [-0.14, +0.69]	$-18$ %

Appendix

Table 17: Game-paired reduction of

\kappa

against summary per rewrite bin: difference of per-game means (nats, positive = lower

\kappa

than summary ) with bootstrap interval, and the relative reduction. The three DSSR seeds are pooled. The 0-rewrite bin is omitted (baseline

\kappa\approx 0

$F^{\prime}$	0	2	3	5	7	9	10	15	20	30	40
DSSR, 3-seed mean (%)	19.3	11.9	9.6	9.6	8.9	6.7	10.4	6.7	5.2	2.2	3.0
summary (%)	2.2	2.2	0	0	0	0	2.2	0	0	0	2.2
gain (points)	$+17.0$	$+9.6$	$+9.6$	$+9.6$	$+8.9$	$+6.7$	$+8.1$	$+6.7$	$+5.2$	$+2.2$	$+0.7$
interval, lower	$+8.1$	$+3.7$	$+5.2$	$+4.4$	$+4.4$	$+2.2$	$-0.0$	$+2.2$	$+1.5$	$+0.0$	$-5.2$
interval, upper	$+26.7$	$+14.8$	$+14.8$	$+14.8$	$+14.8$	$+11.9$	$+16.3$	$+12.6$	$+9.6$	$+5.2$	$+5.2$

Appendix

Table 18: Success gain of the selected writer (three seeds pooled per game) over the untrained summary writer at every filler length of the exploratory grid (validation,

B=128

): percentage points with 95 % game-paired bootstrap intervals over the 45 games (10,000 resamples). Short and medium lag (

F^{\prime}\leq 9

): every interval excludes zero;

F^{\prime}=10

: interval touching zero; long lag (15–20): smaller but above zero; extra-long (30–40): not distinguishable from zero.

Explore similar work

May 22, 2026cs.LG

State commitment learning: training language models to distinguish computation from memory

Reasoning language models do not distinguish tokens used for computation from tokens that constitute persistent state: once generated, all hidden thoughts remain in context and influence future predictions. As a result, downstream reasoning may depend on failed attempts, dead ends, and private scratch work that should not be safely relied on later. We recast this phenomenon as a new training objective, state commitment learning: training models to explicitly distinguish information that should be committed as persistent state from temporary computation that can be discarded. We define a counterfactual criterion, persistent-state sufficiency, which makes it trainable and measurable whether an answer remains usable after hidden thoughts are erased. We then propose Counterfactual Erasure RL (CERL), which evaluates, under the same prefix, both a path that keeps hidden thoughts and a path that erases them, and gives reward only when the erasure path remains correct. We also introduce the Erasure Dependence Protocol and show across mathematics, long-chain logic, scientific QA, and multi-turn tool-use evaluation that CERL substantially reduces answer dependence on hidden thoughts without sacrificing accuracy, consistently outperforming correctness-only RL and long-answer SFT baselines.

Fei Ding, Yongkang Zhang, Runhao Liu +3

Alibaba Group · Tsinghua University

Transition Learning Language Modeling Persistent State Downstream Reasoning

Ask PDF

Sep 22, 2026cs.AI

How Strongly Should Task State Influence an LLM Agent?

Long-horizon assigned work requires an LLM agent to track the state of a task: which steps are done, blocked, cancelled, or open to repetition. Agent systems either keep this state as text in the prompt and rely on the model to read that text, or move the state into a module that enforces it, and each system is evaluated as a whole, so no one knows how much reliability comes from the state being shown, told, or enforced. We fix the task rules, the model, and paired episodes and vary how strongly task state reaches the agent: a raw transcript, an exact checklist, per-turn directives from a state machine compiled from the brief and advanced only by execution receipts, or an enforcement gate on that machine that refuses state-violating actions; every episode is scored by exact payload matching against dynamic ground truth. Across three models, two reasoning regimes, and two domains, four findings hold without per-turn reasoning: displaying accurate state is unreliable, an unverified ledger the agent writes itself beats an accurate checklist it is shown, directives help in proportion to the model's obedience, and enforcement needs no obedience but is bounded by the correctness of its state and by the matcher that maps requests to steps; per-turn reasoning at a 235B agent compresses these separations without repairing the text rungs. The same gate, compiled from

τ^2

-bench's airline policy, raises a 235B agent's pass

^1

from 0.39 to 0.54 and changes nothing for a 35B agent that rarely violates the policy; on PM-Bench, where acting turns on recognizing a cue rather than on state, showing the record is the best rung--matching or beating both gates and reversing the ledger-over-checklist finding--and enforcing the matcher's judgement drops a 35B agent below its raw transcript. Enforcement pays when failures are state-decidable and frequent, and hurts when the gate's judgement is wrong.

Chenyu Zhang, Wonbin Kweon, Jiawei Han

University of Waterloo · Sungkyunkwan University · University of Illinois Urbana-Champaign

Large Language Model Agents State-Tracking Artificial Intelligence Agents Ledger

Ask PDF

Aug 7, 2026cs.AI

MemWM: Memory-Augmented Text-Based World Model

World models are increasingly used to support planning in agents by predicting how environment states evolve in response to agent actions. Yet fluent next-state predictions can still omit task-critical facts, corrupt product attributes, or apply incorrect transition rules. To address such systematic prediction errors, we introduce MemWM, a memory-augmented text-based world model. MemWM uses world memory, a curated memory bank of transition rules, state caches, and hard-to-predict facts, to condition next-state imagination. We evaluate factual state preservation with Structured State Fidelity (SSF), which scores predicted states through benchmark-specific facts and fields. Compared with SFT, memory-augmented training improves SSF by up to 206.3%. In the full planning setting, we keep the policy model frozen and provide policy-side world skill: retrieved task-level skills and step-wise corrective guidance for action selection. Across ALFWorld, WebShop, and ScienceWorld, memory-augmented agents improve downstream success over an SFT-trained world-model agent, with up to a 65.4% relative gain. Sensitivity analyses further show that retrieved memory improves task success and efficiency under different memory and action-budget settings.

Yujun Wang, Tao Zhang, Jinhe Bi +9

LMU Munich · Munich Center for Machine Learning (MCML) · Huawei Heisenberg Research Center +4

World Models Next-State Prediction Omninwm World Skills

Ask PDF