Organizations: Salesforce AI Research · University of California, Los Angeles · University of Illinois at Urbana-Champaign · University of Illinois Chicago
Long-term memory enables language-model agents to personalize future interactions, but a finite memory bank cannot preserve every extracted fact. Existing memory gating policies are typically shared across users and therefore fail to account for user-specific patterns of future reuse. In this paper, we study memory gating at the fact level. We first propose a retrieval-based labeling strategy that labels each fact by whether it is later retrieved and incorporated into responses. We then formulate online memory gating as contextual apple tasting with delayed one-sided feedback, and propose Warm-Start UCB, which combines offline learning from existing data with online adaptation to the current user. Our theoretical analysis establishes a high-probability regret upper bound of O~(Tε∧dT) when the delay window is at most O(T), where T is the total number of rounds, ε is the initialization error, d is the dimension of the feature map, and O~(⋅) hides constant and poly-logarithmic factors. The results of our experiment demonstrate that our method outperforms all baselines under different memory budgets and history lengths, establishing it as a promising personalized memory gating policy.
Figures & tables
Dataset
Self AUC
LOUO AUC
Gap
PerMemBench-S
0.756 ± 0.047
0.622 ± 0.049
0.134
PerMemBench-L
0.724 ± 0.029
0.665 ± 0.024
0.059
Table 1: Self (within-user CV) vs. LOUO (fixed global model) TF-IDF + logistic regression AUC for the fact-gating label, averaged over 20 users.
Metric
Micro Average
Macro Average
Budget
60
120
250
500
60
120
250
500
Oracle
69.34
92.99
100.00
100.00
77.28
95.22
100.00
100.00
Universal
17.44
35.94
56.93
80.60
19.34
39.29
60.76
84.91
Greedy
23.01
32.95
44.49
47.34
24.86
34.16
45.08
47.56
Greedy (Ours)
23.94
35.99
53.70
68.13
26.11
38.29
55.00
67.87
Context
23.39
32.28
42.96
45.28
25.33
33.20
42.95
45.21
Table 2: Results on the PerMemBench-S benchmark. We use bold for the highest score and underline for the second highest. For LLM-based methods, “(Ours)” indicates the corresponding method with our fine-grained prompt. The results show that Warm-Start UCB outperforms the Universal baseline and LLM-based methods uniformly across all budget sizes.
Metric
Micro Average
Macro Average
Budget Size
120
250
500
800
1000
120
250
500
800
1000
Oracle
54.30
78.61
97.51
100.00
100.00
58.68
82.62
98.33
100.00
100.00
Universal
20.17
35.28
50.77
65.73
73.77
22.03
37.13
52.55
67.50
75.71
Greedy
19.65
29.19
40.59
47.42
49.19
20.38
30.02
40.53
46.50
47.68
Greedy (Ours)
18.64
29.87
45.55
58.12
62.87
19.54
31.32
46.59
58.56
63.10
Context
17.01
25.43
36.30
41.56
43.49
17.70
25.93
36.50
40.61
42.52
Table 3: Results on the PerMemBench-L benchmark. We use bold for the highest score and underline for the second highest. For LLM-based methods, “(Ours)” indicates the corresponding method with our fine-grained prompt. The results show that Warm-Start UCB significantly outperforms the Universal baseline and LLM-based methods uniformly across all budget sizes.
Figure 1: Learning dynamics on PerMemBench-L: F1 gain over the Universal baseline in each session-position decile under memory budgets B∈{120,500,1000} . Shaded regions denote the 95% CI over all users. The gating quality improves in later deciles for online methods Cold-Start UCB and Warm-Start UCB .
Figure 2: Effect of the pre-training pool size on PerMemBench-L: best micro- and macro-averaged RHRs under B∈{120,500,1000} . The results show that the performance continues to improve as the pretraining pool size grows.
Appendix figures & tables6 assets
Supplementary material from the paper’s appendix.
Appendix
User
n
Confirmed
Unconfirmed
r
p
0045d22a
12
0.600 [0.42, 0.78]
0.167 [0.03, 0.33]
1.00
1.95×10−3
0097794e
29
0.510 [0.36, 0.66]
0.155 [0.07, 0.26]
0.75
1.04×10−3
009850d8
18
0.372 [0.20, 0.55]
0.144 [0.02, 0.31]
1.00
4.98×10−3
00aefb8e
32
0.456 [0.32, 0.60]
0.091 [0.03, 0.18]
0.90
1.11×10−4
00e85c7f
22
0.482 [0.35, 0.62]
0.077 [0.01, 0.15]
0.95
4.07×10−4
Pooled
113
0.477 [0.40, 0.55]
0.121 [0.08, 0.17]
0.88
6.95×10−13
Appendix
Table 4: Per-user fact-incorporation scores (mean, with 95% bootstrap CI) for confirmed vs. unconfirmed target facts, and the paired Wilcoxon test comparing them within each user. Reported as a robustness check on the pooled result, not as independent significance tests.
Metric
Mean
Median
Min
Max
Std
Sessions per uuid
54.25
57
36
70
9.93
Total entries per uuid
856.5
894
474
1295
203.58
Entries with valid hits per uuid
124.5
122
45
241
56.93
Hit rate (hit entries / total entries)
0.142
0.140
0.064
0.236
0.047
Avg delay-to-first-hit (sessions)
13.47
13.02
6.95
23.2
3.76
Appendix
Table 5: Per-user statistics of PerMemBench-S, computed over the 20 users. Delay-to-first-hit is measured in sessions from extraction to the first valid retrieval hit.
Metric
Mean
Median
Min
Max
Std
Sessions per uuid
150.35
153
94
193
30.84
Total entries per uuid
2449.65
2435
1378
3341
550.39
Entries with valid hits per uuid
493.9
518
225
780
170.45
Hit rate (hit entries / total entries)
0.199
0.203
0.113
0.256
0.043
Avg delay-to-first-hit (sessions)
30.44
28.64
19.38
41.08
5.86
Appendix
Table 6: Per-user statistics of PerMemBench-L, computed over the 20 users. Delay-to-first-hit is measured in sessions from extraction to the first valid retrieval hit.
Figure 3: Learning dynamics ( 3(a) , 3(b) ) and effect of the pre-training pool size ( 3(c) , 3(d) ) on PerMemBench-L for the remaining memory budgets B∈{250,800} . Shaded regions denote the 95% CI over all users.
Figure 4: Learning dynamics on PerMemBench-S: F1 gain over the Universal baseline in each session-position decile under memory budgets B∈{60,120,250,500} . Shaded regions denote the 95% CI over all users.
Figure 5: Effect of the pre-training pool size on PerMemBench-S: best micro- and macro-averaged RHRs under B∈{60,120,250,500} .