Source-linked AI summary
Learning Personalized Memory Gating from Delayed One-Sided Feedback
Kaixuan Ji, Zixiang Chen, Wenting Zhao, Cheng Qian, Heng Wang, Weizhi Zhang, Jielin Qiu, Liangwei Yang, Quanquan Gu, Silvio Savarese, Shelby Heinecke, Huan Wang
TL;DR
Finite memory banks require agents to choose which facts to retain, while shared gating rules overlook differences in users’ future reuse patterns. The paper labels facts through retrieval and proposes Warm-Start UCB for offline learning and online user adaptation; experiments report that it outperforms all baselines, while the method assumes stable user parameters.
Problem
Finite memory banks cannot preserve every extracted fact, and shared gating policies do not account for user-specific patterns of future reuse.
Source: §1 · p. 1Method
The paper labels facts using downstream retrieval and LLM-judge verification, then uses Warm-Start UCB to combine offline learning with online adaptation under one-sided delayed feedback.
Source: §1 · p. 2, §4.1.1 · p. 5Results
Experiments report that Warm-Start UCB consistently outperforms previous LLM-based methods and the naive admit-all baseline across memory budgets and interaction lengths.
Source: §1 · p. 2Takeaways & Limitations
The experiments support Warm-Start UCB as an effective personalized memory-gating policy on the constructed benchmark.
Source: §1 · p. 2The method assumes a stable parameter for each user; modeling evolving utility patterns remains future work.
Source: §6 · p. 10
Abstract
from arXiv · showhide
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 $\tilde{O}(T\epsilon \wedge d\sqrt{T})$ when the delay window is at most $O(\sqrt{T})$, where $T$ is the total number of rounds, $\epsilon$ is the initialization error, $d$ is the dimension of the feature map, and $\tilde{O}(\cdot)$ 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.
1 Introduction
Memory banks must choose which facts to retain, yet shared gating rules overlook user-specific patterns of future reuse. The paper derives utility labels from retrieval, frames gating as delayed one-sided feedback, and proposes Warm-Start UCB, which combines offline learning with online adaptation.
1 Introduction
- Existing gating policies use criteria shared across users, overlooking heterogeneity in how users reuse facts.Finite storage and context budgets make the choice of which extracted facts to preserve necessary.Source: §1 · p. 1
- The labeling pipeline derives fact-utility labels from downstream retrieval outcomes and refines them with LLM-judge verification, without heuristic or downstream reward signals.A fact is treated as useful when later retrieval indicates it was incorporated into a response.Source: §1 · pp. 1–2
- The paper frames personalized gating as apple tasting with one-sided delayed feedback and proposes Warm-Start UCB to learn from existing users, then adapt to the current user online.The feedback applies only to added facts and becomes meaningful after an unknown delay.Source: §1 · pp. 1–2
- Warm-Start UCB consistently outperforms previous LLM-based methods and the naive admit-all baseline across memory budgets and interaction lengths.The authors present it as an effective policy for personalized memory gating.Source: §1 · p. 2
2 Related Work
Prior memory systems commonly use universal storage policies, while prior apple-tasting and delayed-feedback work studies varied feedback and delay settings. This paper’s related-work framing situates fact-level personalized gating within those literatures.
Personalized Memory System
- Most existing memory systems use universal storage policies; unlike In et al. (2026), this work studies fact-level online adaptation from retrieval-derived feedback rather than session-level gating reliant on human or LLM heuristics.The related work describes In et al. (2026) as formalizing the limitation and introducing PerMem-Bench and session-level baselines.Source: §2 · p. 2
Learning with Apple Tasting Feedback
- Apple tasting is a canonical one-sided-feedback model, with contextual variants studied through partial monitoring, Bayesian logistic models, feedback-graph reductions, and log-loss.The cited literature also considers fairness-aware and strategically manipulated-context settings.Source: §2 · p. 2
Learning with Delayed Feedback
- Prior delayed-feedback work often assumes delay independent of feedback, while this paper adopts a running-zero-flipping-one model to represent retrieval feedback available only for added entries.Vernade et al. (2020) is cited for an eO(sqrt(T) + md) regret upper bound under its setting.Source: §2 · p. 3
3 Dataset Construction
The dataset construction section describes retrieval-based fact labeling and evaluation, then examines how utility patterns are shared across users and user-specific. Its analysis motivates a policy that learns from other users while adapting to the current user.
3.1 Benchmark Construction
- The benchmark starts from interaction histories, extracts candidate facts with a memory system, and processes PerMemBench-S alongside a synthesized longer-horizon PerMemBench-L dataset.The pipeline is described as agnostic to the underlying extractor, although the construction uses mem0.Source: §3.1 · p. 3
- A fact is labeled as required when it appears among the top-k retrieval hits for a later turn judged to require memory, with an LLM judge filtering hits for necessity or substantial answer-quality improvement.When retrieval has no strong match, an LLM also inspects whether top retrieved facts collectively help answer the prompt.Source: §3.1 · p. 3
- The fixed-budget evaluation measures retrieval-hit retention rate as the proportion of valid retrieval hits realized while the relevant facts remain in memory.A miss can result from dropping a required fact or evicting it by adding too many non-required facts; the section also evaluates storage decisions with F1.Source: §3.1 · p. 4
3.2 Meta Analysis
- Self AUC exceeds leave-one-user-out AUC, while leave-one-user-out AUCs of 0.622 and 0.665 are above the 0.5 random level, indicating shared and user-specific signal.The section uses TF-IDF with logistic regression and compares within-user cross-validation against a shared model trained on the other 19 users; Table 1 reports AUC averaged over 20 users.Source: §3.2 · p. 4, Table 1 · p. 4
4 Algorithm and Analysis
The paper models personalized memory gating as contextual apple tasting with delayed, one-sided feedback and develops Warm-Start UCB to combine information from other users with online adaptation. Its analysis and experiments support the method, while the model assumes a fixed cost for adding non-required facts and does not represent variation in how often useful facts are retrieved.
4.1.1 Interaction Protocol
- The learner observes a fact context and chooses whether to add it or skip it; skipped facts yield no later feedback.Added facts produce a delayed signal that changes from zero to one only when a useful fact’s delay elapses.Source: §4.1.1 · p. 5
4.1.2 Learning Objective
- The objective compares the learner’s actions with an oracle that adds a fact when its expected utility reaches the cost-derived threshold.The threshold is τ = c_store under the paper’s normalized reward setup.Source: §4.1.2 · p. 5
- The model does not capture varying retrieval frequency among useful facts or storage costs that change as memory capacity fills.The authors identify both as directions for extending the model.Source: §4.1.2 · p. 5
4.2 Training from Other Profiles
- The warm start uses data from other users to estimate a prior center, assumed to be close to the current user’s parameter with high probability.The paper motivates this assumption with shared and user-specific components in storage preferences and cross-user predictability.Source: §4.2 · p. 6
4.3 Online Adaptation
- Warm-Start UCB begins from the pretrained estimate but adapts online, addressing the linear regret that can result from relying on that estimate alone.Its decision rule compares an optimistic utility index with a fixed threshold and updates from available feedback.Source: §4.3 · pp. 6–7
- Warm-Start UCB outperforms the Universal baseline and LLM-based methods uniformly across all PerMemBench-S memory budgets.Table 2 reports these comparisons across budget sizes.Source: Table 2 · p. 7
- With a sufficiently accurate warm start, the regret scales as roughly Tε for shorter horizons and sublinearly with dimension for longer horizons.The stated bound is ˜O(Tε ∧ d√T), under the theorem’s assumptions and for sufficiently small ε.Source: §4.3 · p. 8
5 Experiments
The experiments compare memory-gating baselines and Warm-Start UCB across memory budgets and interaction lengths. Results favor Warm-Start UCB, while ablations examine the contributions of online adaptation and pre-training.
5.2 Experiment Results
- Warm-Start UCB beats Universal and LLM-based methods at every PerMemBench-S budget and averaging scheme; on PerMemBench-L it ranks first among non-oracle methods in eight of ten columns and second in the other two.At B=250 on PerMemBench-L, it is narrowly below Pre-trained Scorer.Source: Table 3 · p. 8, §5.2 · pp. 9–10
5.1 Baselines and Methods
- Model-free baselines are Oracle, which uses ground-truth labels, and Universal, which admits every extracted fact; LLM baselines judge fact utility with or without recent session context.The LLM comparisons use a standard prompt and a finer-grained prompt that accounts for remaining memory capacity.Source: §5.1 · p. 8
- The linear comparison includes Cold-Start UCB without other users’ data, a frozen scorer trained on other users, and Warm-Start UCB.These variants isolate online adaptation and cross-user pre-training, respectively.Source: §5.1 · p. 9
5.2 Experiment Results
- On PerMemBench-L, pre-training transfers useful information, but user-specific feedback remains important for maintaining performance over long interaction horizons.UCB without initialization is only marginally above Universal, while online adaptation still improves results at larger memory budgets.Source: §5.2 · p. 10
- LLM-based methods are comparable to Universal under small budgets but fall below it at larger budgets, and capacity-aware prompting only partly mitigates this gap.The gap increases with memory budget size.Source: §5.2 · p. 10
5.3 Ablation Studies
- Cold-Start UCB starts with little or negative improvement, while Warm-Start UCB combines pre-training’s initial uplift with increasing separation from the frozen policy as user feedback arrives.The online methods’ F1 gains over Universal improve in later session-position deciles.Source: Figure 1 · p. 9, §5.3 · p. 10
- PerMemBench-L RHR improves monotonically with the pre-training pool size across every displayed budget and averaging scheme, and continues improving through 15 profiles.The continued gains, especially at B=500 and B=1000, suggest the pre-trained scorer has not yet saturated.Source: §5.3 · p. 10
6 Conclusion and Future Work
The conclusion recaps a retrieval-based utility-labeling pipeline and a memory-gating algorithm, while identifying evolving user utility patterns as future work. The dataset-construction prompts judge whether memories are needed and whether retrieved facts help answer a user.
6 Conclusion and Future Work
- The conclusion describes a retrieval-based utility-labeling pipeline and dataset, then frames memory gating as apple tasting with one-sided delayed feedback.The algorithm’s regret guarantee is only partially legible in the supplied passage.Source: §6 · p. 10
- The conclusion reports that experiments on the constructed dataset consistently outperform all baselines, while assuming each user’s utility parameter is stable.Accounting for evolving utility patterns remains future work.Source: §6 · p. 10
A.1 Prompts in Dataset Construction
- The prompts test whether a memory lookup is needed, retrieve relevant facts, and assess whether those facts are necessary or improve answer quality.The checks allow related facts to be considered together and distinguish specific use from weak topical relation or irrelevance.Source: §A.1 · pp. 14–15
A.2 Meta Evaluation
The meta-evaluation tests whether confirmed facts are incorporated into later responses more than unconfirmed facts. The reported pooled and per-user findings support the labeling signal across the five evaluated users.
A.2 Meta Evaluation
- The evaluation samples retrieval probes and compares judge-confirmed facts with unconfirmed candidates using repeated response generations and a separate judge.Generated responses receive scores of 1, 0.5, or 0 for containing, weakly relating to, or being irrelevant to the candidate fact; paired scores are tested with a Wilcoxon signed-rank test.Source: §A.2 · p. 15
- W=220.5 and p≈7 × 10^-13; confirmed facts were more incorporated than unconfirmed facts across 113 matched pairs from five users, with effect size r=0.88.Per-user results agree with the pooled result: confirmed-fact mean scores range from 0.372 to 0.600 versus 0.077 to 0.167 for unconfirmed facts, with gaps of 0.23 to 0.43.Source: §A.2 · p. 15, Table 4 · p. 15
A.3 Statistics of the Constructed Benchmark
The benchmark statistics highlight sparse fact reuse and delayed feedback, while the LLM-based gating prompts vary whether decisions use only the current fact or also historical context and remaining capacity.
A.3 Statistics of the Constructed Benchmark
- Only 14.2% of facts are utilized on average in PerMemBench-S and 19.9% in PerMemBench-L, leaving most extracted facts unused in later queries.Even the highest user-level ratios are 23.6% and 25.6%, respectively.Source: §A.3 · p. 15
- Utilized facts receive their first valid hit an average of 13.47 sessions after extraction in PerMemBench-S and 30.44 sessions in PerMemBench-L.The passage says these delays are roughly a quarter and a fifth of average history length, respectively, and may exceed evaluated memory budgets in terms of subsequent facts.Source: §A.3 · p. 16, Table 5 · p. 16, Table 6 · p. 16
B.1 Prompts of LLM-Based Methods
- The greedy prompt decides from the current fact, whereas the context-aware prompt also supplies recent session summaries and current dialogue.The capacity-aware variants tailor the rubric to whether the memory bank has room, is filling, or is nearly full.Source: §B.1 · pp. 16–18
B.2 Hyper-parameters of Proposed Methods
The proposed linear gating methods use fact embeddings as features and select model parameters and thresholds through user-level training and validation.
B.2 Hyper-parameters of Proposed Methods
- Warm-Start UCB and the Pre-trained Scorer fit a linear parameter on 15 users and validate hyperparameters on another 4 of the 19 users.The methods use text-embedding-3-small features; Warm-Start UCB keeps Algorithm 1’s routine but tunes its confidence radii and gating threshold.Source: §B.2 · p. 18
- Cold-Start UCB sweeps confidence radii, gating thresholds, regularization values, and delay windows, selecting the combination with the highest micro RHR.The delay-window candidates are 8, 10, or 15 sessions for PerMemBench-S and 25, 35, or 45 for PerMemBench-L.Source: §B.2 · p. 18
- Warm-Start UCB tunes its threshold relative to the validated Pre-trained Scorer threshold and sweeps confidence radii, regularization values, and delay windows.The searched regularization and delay-window ranges differ between PerMemBench-L and PerMemBench-S.Source: §B.2 · p. 18
C Additional Experiment Results
The additional experiments show distinct learning dynamics across the two benchmarks: PerMemBench-L has clearer pool-size gains, while PerMemBench-S results are noisier and less monotonic. The short-history setting also limits reliable convergence.
C Additional Experiment Results
- On PerMemBench-L, Pre-trained Scorer gains early then fades, Warm-Start UCB separates later, and Cold-Start UCB stays near Universal across the remaining budgets.Figure 3 presents these learning dynamics for B=250 and 800.Source: C Additional Experiment Results · p. 18, Figure 3 · p. 19
- PerMemBench-L RHRs rise monotonically by roughly 3–4 points as the pre-training pool grows from one to fifteen users under both budgets.Figure 3 also presents the pool-size effect.Source: C Additional Experiment Results · p. 18, Figure 3 · p. 19
- On PerMemBench-S, pre-training gives gains from the first decile, and Warm-Start UCB and Pre-trained Scorer both beat Cold-Start UCB for most of the interaction.Figure 4 plots per-decile F1 gain over Universal across four budgets.Source: C Additional Experiment Results · p. 18, Figure 4 · p. 19
- PerMemBench-S confidence bands for Warm-Start UCB and Pre-trained Scorer largely overlap; a clear separation appears only at B=60.Cold-Start UCB fluctuates strongly and drops in the ninth decile before recovering under all four budgets.Source: C Additional Experiment Results · p. 18
- On PerMemBench-S, Figure 5 shows that RHR does not increase monotonically with pool size: it dips at five users for B=60 and 500, and stays nearly flat between two and ten users for B=120 and 250.Source: C Additional Experiment Results · pp. 18–19
- Shorter PerMemBench-S histories leave insufficient feedback for the online estimator to converge, while its offline pre-training pool is also smaller; the authors therefore treat PerMemBench-L as more reliable for learning dynamics.Figure 4 shows the short-history learning dynamics; Figure 5 shows pool-size effects.Source: C Additional Experiment Results · pp. 18–19, Figure 4 · p. 19
D Discussion of Assumption 4.5
The appendix justifies Assumption 4.5 by separating current-user deviation from population-center estimation error, then develops the optimism argument used in the proof. The population component reflects user heterogeneity and does not generally disappear with more pretraining data.
D Discussion of Assumption 4.5
- Assumption 4.5 is justified by bounding current-user deviation from the population center and the error in estimating that center, then setting ε=ε_pop+ε_est.The population parameter is the expectation of user parameters under ρ; its deviation component captures genuine user heterogeneity and need not vanish with n.Source: D Discussion of Assumption 4.5 · pp. 19–20
- With a sufficiently large pretraining sample and a nondegenerate feature covariance, ridge estimation can make the population-center estimation error ε_est sufficiently small with high probability.The discussion also allows an empirical covariance estimate spectrally equivalent to the scaled feature covariance.Source: D Discussion of Assumption 4.5 · pp. 19–20
E Missing Proof from Section 4
- The proof filtration places the current context and action in F_t, while the outcome and delay information become available in F_{t+1}.It defines the observed delayed label using the delay window.Source: E Missing Proof from Section 4 · p. 20
E.1 Proof of Optimism
- The optimism proof combines estimation and prior-mismatch bounds to obtain a simultaneous bound, then converts its conditional probability into an unconditional one.The final probability is at least 1−δ0−δ.Source: §E.1 · pp. 21–22
E.2 Main Theorem
The main-theorem proof uses optimism to ensure contexts whose oracle utility exceeds the threshold are added, and bounds regret by combining warm-start and learning-based contributions. Pending delayed feedback and regularization selection enter that analysis.
E.2 Main Theorem
- When oracle utility η(x_t) is at least τ, the optimistic score makes the algorithm add the context, so it does not incorrectly skip contexts the oracle would add.The proof therefore locates nonzero regret only outside this case.Source: §E.2 · p. 23
- At most m observations can be pending at a time, and each added context can contribute to the pending-set term for at most m subsequent rounds.This bounds the repeated contribution of delayed feedback in the regret analysis.Source: §E.2 · p. 24
- The regret proof combines warm-start and learning-based bounds and selects λ to balance them, yielding the claimed bound with probability at least 1−δ0−δ.The proof derives the two contributions separately before combining them.Source: §E.2 · pp. 24–25