Top-$k$ Retrieval Leaves Memory Value Undetermined

Arman Behnam

cs.AINov 2, 2026

Top- $k$ Retrieval Leaves Memory Value Undetermined

Authors: Arman Behnam

Organizations: Department of Computer Science, Illinois Institute of Technology, Chicago, IL, USA

Abstract

A memory-augmented agent must decide which memories to keep, merge and retrieve, and its only evidence of their value is its retrieval log: the memories it retrieved in each episode and whether it succeeded. Existing methods assign every memory a value from this log, even when the log cannot separate one memory's contribution from another's. We treat the log as an experiment that nobody designed and ask which memory values it determines. Two counts answer this before any outcome is observed: how often each memory was retrieved, and how often each pair was retrieved together. From these counts, we prove that top- $k$ retrieval leaves every memory value undetermined, however many episodes are logged, and that a question with its own memories, asked once, determines at most one of their values. On fourteen standard memory benchmarks, no memory value is determined in any of 55 configurations. Both causes are choices about retrieval. We introduce LEDGER, which estimates each determined Shapley value in closed form with a confidence interval and reports every other value as undetermined. It merges memories with identical histories without losing a determined value, and it retrieves so that the next log determines more. On pooled HotpotQA, LEDGER raises the fraction of memories determined from 0.001 to 0.797, at a cost of 2.6 accuracy points on HotpotQA and with a gain of 2.7 on LoCoMo.

Figures & tables

Panel of Figure 1 — Figure 1: A history that looks sufficient and determines nothing. Rows are episodes, labelled by the memories they retrieve; the column $|S_{t}|$ gives each retrieval size. Left: each pair of four memories retrieved once. Right: the same episodes plus retrievals of sizes $1$ and $3$ .

Panel of Table 1 — Table 1: Retrieval conventions and their invisible changes. Each icon is a small log: rows are episodes, columns are memories, and a filled cell marks a retrieval.

Panel of Figure 2 — Figure 2: LEDGER reads the kernel of the log from its counts and acts on each memory accordingly: it estimates the values the log determines, merges memories the log cannot separate, abstains on the rest. In the log shown, memories $2$ and $3$ are always retrieved together.

Benchmark	$k$	Store	$T$	$n$	Blocks	Determined
HotpotQA	3, 5, 10	per question	300	2,971	300	0
HotpotQA (1,200 q.)	3, 5, 10	per question	1,200	11,912	1,200	0
MuSiQue	3, 5, 10	per question	300	5,999	300	0
WikiHop	3, 5, 10	per question	300	4,560	300	0
TriviaQA	3, 5, 10	per question	300	27,456	300	0
LongMemEval	3, 5, 10	per question	300	6,845	300	0

Table 2: No memory benchmark determines a single memory value.

Panel of Figure 3 — Figure 3: What LEDGER’s retrieval determines, what it costs, and where the cost arises.

Appendix figures & tables14 assets

Supplementary material from the paper’s appendix.

Appendix

Step	Time	Memory
Gram matrix $\mathbf{M}$	$O(T\bar{k}^{2}+n^{2})$	$O(n^{2})$
Kernel basis $\mathbf{U}$ and $\mathbf{V}^{-1}$	$O(n^{3})$	$O(n^{2})$
Test for all memories	$O(n\cdot\dim\ker\mathbf{X}_{1})$	$O(n^{2})$
Estimates and intervals	$O(n^{3})$ , once	$O(n^{2})$
Merging (Algorithm 2 )	$O(T\bar{k}+n)$ expected	$O(T\bar{k}+n)$
Retrieval, one episode	$O(n+M\log M)$	$O(n)$

Appendix

Table 3: Cost of each step at

d=1

, where

p_{1}=n+1

Result	Design	Artifact
Audit, $55$ configurations (Table 2 )	fourteen benchmarks, one pass, their own retrieval	audit_stageB.csv
Fraction determined, four rules (Figure 3 a)	pooled HotpotQA, $300$ questions $\times$ $24$ passes, $n=2{,}971$ , $T=7{,}200$ , seeds $0$ – $4$	e1_
		identifiability.csv
Baseline-test residuals	same log as above	e1_ident_
		both_bases.csv
Accuracy, LEDGER against top- $k$	pooled HotpotQA, $1{,}600$ held-out questions, store of $15{,}900$ memories	e1_primary.csv

Appendix

Table 4: The run behind each result in Section 5 . Artifacts are named as in the released code.

Benchmark	Memory	Store	Sizes
HotpotQA ( Yang et al., 2018 )	paragraph	per question	3, 5, 10
MuSiQue ( Trivedi et al., 2022 )	paragraph	per question	3, 5, 10
WikiHop ( Welbl et al., 2018 )	supporting document	per question	3, 5, 10
TriviaQA ( Joshi et al., 2017 )	paragraph of the Wikipedia contex	per question	3, 5, 10
LongMemEval ( Wu et al., 2025 )	turn	per question	3, 5, 10
MSC-Self-Instruct ( Xu et al., 2021 )	turn	per dialogue	3, 5, 10

Appendix

Table 5: The fourteen audited benchmarks. “All” retrieves every memory of the context; bold marks the size the benchmark specifies, where it specifies one.

Rule	Parameter	Determined	Mean $\|S_{t}\|$	Accuracy change	$p$
Top- $k$	—	$0.001$ ( $0.003$ )	$5.33$	—	—
LEDGER	$\rho=0.4$ , $M=20$	$0.797$ ( $0.797$ )	$5.25$	$-2.6$ $[-4.2,-0.9]$	$0.004$
$\varepsilon$ -greedy	$\varepsilon=0.1$	$0.001$ ( $0.003$ )	$5.33$	$-3.0$ $[-5.3,-1.0]$	$0.012$
$\varepsilon$ -greedy	$\varepsilon=0.3$	$0.989$ ( $0.989$ )	$5.33$	$-13.3$ $[-17.3,-9.7]$	$<0.001$
Perturbation	$\beta=0.05$	$0.983$ ( $0.983$ )	$5.33$	$-14.0$ $[-19.3,-8.7]$	$<0.001$
Perturbation	$\beta=0.10$	$1.000$ ( $1.000$ )	$5.33$	$-37.0$ $[-43.0,-30.7]$	$<0.001$

Appendix

Table 6: Retrieval rules on pooled HotpotQA. Fractions determined are with the baseline column fitted and, in parentheses, without it; accuracy changes are against deterministic top-

k

, in points, with

95\%

intervals in brackets. LEDGER’s accuracy is measured on

1{,}600

questions; the random rules’ on

300

, with Holm-corrected

p

-values.

Corpus	Questions	Top- $k$	LEDGER	Change	$95\%$ interval
LoCoMo	$1{,}542$	$0.191$	$0.217$	$+2.7$	$[+1.0,+4.4]$
LongMemEval	$479$	$0.263$	$0.271$	$+0.8$	$[-1.9,+3.8]$

Appendix

Table 7: Accuracy of deterministic top-

k

and LEDGER on LoCoMo and LongMemEval, with the change in points and its

95\%

interval.

Questions	Share	Gold lost per question	Accuracy change	$95\%$ interval
Top- $k$ found all gold	$0.42$	$0.242$	$-6.9$ $[-9.6,-4.3]$	$0.242$
Top- $k$ missed some gold	$0.58$	$0.009$	$+0.7$ $[-1.4,+2.7]$	$0.009$

Appendix

Table 8: LEDGER against top-

k

on pooled HotpotQA, split by whether top-

k

retrieved every gold memory of the question.

Reader	Gold	Own store	Pooled store	Cost of pooling
gemini-2.5-flash-lite	$0.607$	$0.417$	$0.260$	$15.7$ $[11.0,20.7]$
gemini-3.6-flash	$0.783$	$0.497$	$0.287$	$21.0$ $[15.7,26.3]$
gemini-3.7-flash	$0.757$	$0.477$	$0.280$	$19.7$ $[14.7,25.0]$

Appendix

Table 9: Accuracy of three readers on LongMemEval when each question retrieves from its own store and from one pooled store, with the cost of pooling in points and its

95\%

interval;

300

questions per cell. The gold column gives the reader only the evidence sessions.

$d$	Designs	Settings	Settings reporting	Every memory	Reported values
$1$	full rank	$36$	$36$	$0.977$	$0.977$
$2$	full rank	$12$	$12$	$0.994$	$0.994$
$2$	rank-deficient	$24$	$6$	$0.572$	$0.995$

Appendix

Table 10: Lowest joint coverage over settings at

\delta=0.05

, with the target

0.95

. The last column restricts coverage to the values LEDGER reports; it is a post hoc analysis.

Interval	$d=1$	$d=2$
LEDGER, Eq. Eq. ( 5 )	$1.52$	$1.43$
Abbasi-Yadkori et al. (2011) , $\lambda=1$	$6.6$ ( $4.7$ – $9.4$ )	$35.9$ ( $11.0$ – $365.7$ )

Appendix

Table 11: Width of each interval relative to the pointwise Gaussian interval with the true

\sigma

: median over settings, with the range.

	Log		Identical histories		Similar histories
Rule	Units	Determined	Units	Determined	Units	Determined
LEDGER	$992$	$0.815$	$869$	$0.992$	$867$	$0.995$
Perturbation, $\beta=0.05$	$992$	$0.969$	$964$	$0.999$	$964$	$0.999$

Appendix

Table 12: Units and fraction determined before and after merging on pooled HotpotQA.

Claim	Decision rule	Where	Outcome
Standard benchmarks determine no memory value	falsified if a private-store protocol gives fewer than $0.9$ times as many blocks as contexts, or a fraction above $0.01$ at a fixed $k$	5.2	held: $0$ of $55$ configurations
The remedy recovers identifiability on three audited benchmarks	fractions above floors of $0.50$ , $0.22$ , $0.13$ ; falsified below $0.10$ or a quarter of the rank bound	F	failed: $0.46$ , $0.13$ , $0.08$ ; falsified on MemoryAgentBench
Reach is the binding ceiling	falsified if the window arm is flat or non-monotone, or the passes arm rises by $0.05$ or more	—	failed on two of three benchmarks
The crossover rule on synthetic logs	rises below $R=T$ , falls above, peak in $[0.5,2]$ , range at least $0.02$	—	held: peak at $R/T=0.75$ , range $0.14$
Instrumentation is approximately free	interval contains zero with half-width below $0.025$	5.3	withdrawn: $-2.6$ $[-4.2,-0.9]$
Displacement is the mechanism	gold retrieved per question on found-gold questions below $2.00$	5.3	held: $1.758$

Appendix

Table 13: Pre-registered claims, their decision rules and outcomes, in the order of the pre-registration documents. “Where” gives the section that reports the result; a dash marks a claim reported only in the released documents.

Defect	Earlier value	Corrected value
Pipeline
Baseline offset mishandled in eight estimator methods and four callers	coverage $0.102$ ; value recovery at chance	coverage $1.000$ ; recovery restored
Three bugs in the merging rule for undetermined totals (Case 1)	$60$ of $60$ accepted	$17$ and $25$ of $60$
A shadowed tolerance and a ridge-inverted kernel in one validation test, and a fixed-size test that divided by zero	tests passed without measuring	tests measure coverage
Paragraph splitter fell back silently	NarrativeQA as $11$ memories; InfiniteBench as $4$ episodes	$115$ and $14{,}282$ memories; $40$ episodes
Audit rows with $\mathrm{rank}\,\mathbf{X}=T$ read as evidence	$29$ of $55$ counted	reported as automatic

Appendix

Table 14: Defects found and the values they changed. Every value in the paper is the corrected one; each entry in docs/errata.md gives the full account.

Store, episodes and retrieval
$n$	number of memories in the store
$m_{i}$	memory $i$ , for $i\in[n]$
$T$	number of episodes
$q_{t}$ , $\mathcal{D}_{Q}$	query of episode $t$ ; the distribution it is drawn from
$S_{t}$	set of memories retrieved in episode $t$
$k_{t}=\|S_{t}\|$	retrieval size of episode $t$ ; written $k$ when every episode retrieves the same number

Appendix

Table 15: Symbols, in the order they appear.

Episode	one query, one retrieval, one answer and its outcome
Log	the retrieved sets and outcomes of all episodes, stored as $\mathbf{X}$ and $\mathbf{r}$
Determined, identifiable	the log determines $\varphi_{i}$ exactly when $\mathbf{c}^{(i)}$ lies in the row space of $\mathbf{X}_{d}$ ; the two words are used interchangeably
Undetermined	not determined; LEDGER reports no estimate for such a memory
Invisible change	a vector $\mathbf{h}\in\ker\mathbf{X}_{d}$ : $\bm{\theta}$ and $\bm{\theta}+s\mathbf{h}$ predict the same outcome in every episode
Convention	a habit of retrieval or evaluation that fixes the counts of the log, such as a fixed size or a private store
Top- $k$ log	a log in which every episode retrieves exactly $k$ memories

Appendix

Table 16: Terms, in the order they appear.

Memory Management for LLM Agents

See all 110 papers

When to Forget: A Memory Governance Primitive
Apr 13, 2026Baris SimsekAgent Memory Governance Agent Memory
Learning What to Remember: A Cognitively Grounded Multi-Factor Value Model for Agentic Memory
Jun 11, 2026Zhibao Chen, Qian ChengLLM Agent Memory Persistent Memory for Language Models
Huatai Securities, Nanjing, China
Memory Tax: Dissecting the Net Value of Agent Memory
Oct 25, 2026Xuan He, Sining Zhoubian, Ruozhen Yang +8LLM Agent Memory LLM Memory
University of Illinois Urbana Champaign · Tsinghua University · Renmin University of China +1

Apr 13, 2026J/K move · Enter open · S save

When to Forget: A Memory Governance Primitive

Baris Simsek

Agent Memory Governance Agent Memory Agent Memory Management

Open paper AskPDF arXiv

Agent memory systems accumulate experience but currently lack a principled operational metric for memory quality governance -- deciding which memories to trust, suppress, or deprecate as the agent's task distribution shifts. Write-time importance scores are static; dynamic management systems use LLM judgment or structural heuristics rather than outcome feedback. This paper proposes Memory Worth (MW): a two-counter per-memory signal that tracks how often a memory co-occurs with successful versus failed outcomes, providing a lightweight, theoretically grounded foundation for staleness detection, retrieval suppression, and deprecation decisions. We prove that MW converges almost surely to the conditional success probability p+(m) = Pr[y_t = +1 | m in M_t] -- the probability of task success given that memory m is retrieved -- under a stationary retrieval regime with a minimum exploration condition. Importantly, p+(m) is an associational quantity, not a causal one: it measures outcome co-occurrence rather than causal contribution. We argue this is still a useful operational signal for memory governance, and we validate it empirically in a controlled synthetic environment where ground-truth utility is known: after 10,000 episodes, the Spearman rank-correlation between Memory Worth and true utilities reaches rho = 0.89 +/- 0.02 across 20 independent seeds, compared to rho = 0.00 for systems that never update their assessments. A retrieval-realistic micro-experiment with real text and neural embedding retrieval (all-MiniLM-L6-v2) further shows stale memories crossing the low-value threshold (MW = 0.17) while specialist memories remain high-value (MW = 0.77) across 3,000 episodes. The estimator requires only two scalar counters per memory unit and can be added to architectures that already log retrievals and episode outcomes.

Abstract

Memory Management for LLM Agents

Explore similar work

When to Forget: A Memory Governance Primitive

Learning What to Remember: A Cognitively Grounded Multi-Factor Value Model for Agentic Memory

Memory Tax: Dissecting the Net Value of Agent Memory