PaperlayerView exact revision on arXiv

Source-linked AI summary

The Price of Scale in Proactive Memory Recall

Yichuan Chen, Xin Wang

arXiv:2610.34507v2cs.CLcs.AIcs.IRstat.ML

TL;DR

Proactive assistants must decide whether any stored memory merits an unsolicited reminder, and the decision becomes harder as the store grows. The paper studies this as repeated testing, evaluates gates on benchmark replays, and shows that fixed thresholds can produce sharply rising false-alarm rates.

  • Problem

    Proactive recall requires deciding whether any stored memory is relevant without a query specifying what to retrieve, while each unwarranted reminder costs attention.

    Source: §1 · p. 1

  • Method

    The paper analyzes best-of-store gates as repeated tests, replays benchmark stores at controlled sizes, and evaluates a cue-swap conformal gate.

    Source: §1 · p. 2, §3 · p. 3, §4.1 · p. 5

  • Results

    Fixed thresholds lose false-alarm control as stores grow; cosine reaches 87% and tf-idf 99% false alarms at N=2048 after tuning each to 5% at N=8.

    Source: §1 · p. 2, §5.1 · p. 6

  • Takeaways & Limitations

    At a fixed false-alarm rate, increasing the number of comparisons constrains attainable hit rate, and cue-swap error control depends on exchangeability of reference cues.

    Source: §4 · p. 4, §4.1 · p. 5

    Replays use answer-aware model-written cues and pooled simulated-user histories, hold out questions rather than users, and the main analysis assumes independent scores.

    Source: §7 · p. 12

Abstract

from arXiv · show

A long-lived assistant that brings up memories without being asked must decide at every turn whether anything in its store is worth an interruption. We show that this decision is a multiple-testing problem whose difficulty grows with the store size N. On streaming replays of LongMemEval, a similarity threshold tuned to 5% false alarms at N=8 reaches 84-100% at N=2048 across embedding models and cue types, and LoCoMo and LLM judges show it too. We prove that a gate which thresholds the best of N independent irrelevant scores at false-alarm rate alpha operates at a per-item false-positive rate of about -ln(1-alpha)/N, which pins its hit rate to the far left of the single-comparison ROC curve and, under regular variation, makes it regularly varying in N. A finite-pool form of this bound predicts the hit rate of a label-tuned threshold on held-out questions to within 6.1 points. At matched false alarms the deployed score recalls 14-26 points more than raw cosine. A cue-swap conformal gate, which ranks the current cue among other cues on the same store, has a finite-sample false-alarm guarantee under exchangeability. With a background drawn from the user's unfiltered history it keeps false alarms at 3-6% on LongMemEval at the hit rate of a label-tuned threshold; on LoCoMo it overshoots or turns conservative depending on where its reference cues come from. In a chronological replay with the user's own earlier messages as references, it speaks on 6-8% of session-opening turns, against 57% for the deployed gate at N=2048, at about 50 ms per decision on one CPU thread. A cross-encoder reranker pays the same price of scale, and on a prospective-memory benchmark, similarity gates recall at most 9% of constraints at controlled false alarms. One human and two LLM annotators judge most false alarms unhelpful for a response. Code and data: https://github.com/RiverChenStillCompiling/price-of-scale

1 Introduction

Proactive memory requires an assistant to decide whether a stored memory warrants interrupting the user, unlike question answering, where the query specifies what to retrieve. The paper frames this as a multiple-testing problem and measures, analyzes, and addresses how growing stores affect false alarms and recall.

1 Introduction

  • An assistant must decide whether to volunteer a memory, because an unwarranted reminder consumes the user's attention.Unlike question answering, proactive recall has no query that specifies what to retrieve.Source: §1 · p. 1
  • The best-of-store gate faces more chances for an irrelevant memory to score highly as the store grows, making false alarms harder to control while retaining recall.The paper studies both the scale-dependent error and how much recall remains when false alarms are held fixed.Source: §1 · p. 1
  • Across growing-store replays, fixed thresholds lose false-alarm control within a few doublings, while the paper analyzes scaling laws and tests a cue-swap conformal gate.The contributions also compare multiple gates, a cross-encoder, LLM judges, and prospective-memory performance.Source: §1 · p. 2

2 Related work

Prior work studies selective intervention, retrieval decisions, score distributions, and error control, but does not formally characterize how proactive-memory gate errors scale with store size. This paper distinguishes proactive recall from retrieval decisions where a query asks whether outside knowledge is needed.

2 Related work

  • Prior proactive-memory systems study selective intervention and prospective memory, but none formally characterizes gate errors as stores grow or provides a finite-sample false-alarm guarantee.Related work reports timing challenges in MemoProAgent [40], false-alarm rates above 50% for proactive baselines in PRISM [10], and prospective-memory trade-offs in TriggerBench [42] and PM-Bench [22].Source: §2 · p. 2
  • Adaptive retrieval asks whether a model needs outside knowledge, whereas proactive recall asks whether any stored item is relevant, making store size central.Calibration-based adaptive retrieval variants may depend on threshold tuning [43].Source: §2 · p. 2
  • Prior retrieval work models non-relevant score distributions and database-size effects, while this paper analyzes fixed-false-alarm hit rates using extreme-value theory.The cited lines of work include BLAST's database-size scaling and more frequent irrelevant dense-retriever results as the index grows [31].Source: §2 · pp. 2–3
  • The paper applies conformal p-values to control firing on stores with nothing relevant, unlike prior conformal retrieval methods that cover answers or bound generated-text risk.Its cue-swap reference-set choice and empirical study of reference-source effects distinguish the application from those prior methods.Source: §2 · p. 3

3 Proactive recall as repeated testing

The paper models proactive recall as a gate over the highest-scoring memory, then evaluates gates on controlled-size benchmark stores. Its replay design separates null trials from positive trials and compares fixed, adaptive, oracle, and cue-swap approaches.

3 Proactive recall as repeated testing

  • A gate speaks when the maximum score across stored memories exceeds a threshold, and a hit requires both speaking and selecting the relevant memory.A turn with no relevant memory is a false alarm if the gate speaks.Source: §3 · p. 3
  • Null trials draw N irrelevant items, while positive trials add one evidence turn to N−1 irrelevant items; labels define the trials, not the background sample.Thresholds are tuned on one hash-defined half of questions and evaluated on the other; confidence intervals bootstrap over questions or LoCoMo conversations.Source: §3 · p. 3
  • The comparison includes cosine and tf-idf thresholds tuned at N=8, deployed and frozen z-score gates, an extreme-value gate, label-retuned oracle gates, and cue-swap conformal.LLM judges also inspect the five memories with the highest cosine scores and either select one or stay silent.Source: §3 · p. 3

4 Theory: the price of scale

With a fixed store-level false-alarm rate, the best-of-N gate must operate at a per-memory false-positive rate that shrinks with store size, constraining recall through the far-left ROC tail. The paper also gives a cue-swap gate with a finite-sample false-alarm guarantee under exchangeability, subject to assumptions about its reference cues.

4 Theory: the price of scale

  • The gate’s per-item false-positive rate is about λ/N, placing its hit rate at the far-left end of the single-comparison ROC curve; under regular variation, hit rate decays regularly with N.The asymptotic form is Hit_N ∼ C(α, κ) λ^κ N^-κ ℓ(1/N).Source: §4 · p. 4
  • In the binormal model, the stated N*(β) formula bounds the largest store size that can sustain hit rate β, with capacity between the two bounds given for β and β/(1−α).For t_β>0, the upper bound grows on an exponential scale with t_β²/2.Source: §4 · p. 4
  • The bounds also apply to without-replacement stores sampled from a shared finite pool, and the averaged finite-pool form is used as the exact model in §5.3.The finite-pool expression replaces the independent-score factor with a hypergeometric factor.Source: §4 · pp. 4–5
  • For a global threshold, cue-specific false-alarm rates and pass rates can covary; positive covariance lowers the derived bound but does not establish that per-cue control recalls more.The paper reports positive covariance in its data at every N and leaves whether per-cue normalisation helps as an empirical question.Source: §4 · pp. 4–5

4.1 A cue-swap conformal gate

  • The cue-swap gate ranks the current cue’s best store score against scores from other cues, with a false-alarm bound when the scores are exchangeable under the null.The bound also covers a pathwise-coupled null vector; marginal stochastic dominance alone is insufficient, and the guarantee is marginal over cues and stores.Source: §4.1 · p. 5
  • Reference cues must come from the same source as the current cue for exchangeability, while the pathwise coupling for relevant references remains a data assumption.The paper checks the resulting false-alarm rates empirically.Source: §4.1 · p. 5
  • The described implementation scores current and earlier user messages against the store plus a history background, standardizes channels by median and MAD, and costs about 47 ms at N=2048 for K=199.It stays silent when there are fewer than 19 references at α=0.05.Source: §4.1 · p. 5

5 Experiments

Experiments replay LongMemEval and LoCoMo as growing memory stores, testing gates, judges, and rerankers across store sizes and cue types. They assess false alarms, recall, and how the cue-swap gate behaves in chronological deployment and prospective-memory tasks.

5.1 False alarms grow with the store

  • Tuned to 5% false alarms at N=8, cosine and tf-idf thresholds reach 87% and 99% false alarms at N=2048; recall-v1 reaches 66% and the extreme-value gate 21%.The pattern also holds with bge-large, implicit cues, and LoCoMo; untuned gates maintain high hit rates only because they speak almost always.Source: §5.1 · p. 6

5.2 Two channels, two growth rates

  • The lexical null maximum grows 2.4–2.8 times as much as the semantic maximum at the 95% quantile, while its growth pattern is more consistent across settings.At N=2048, the largest eligible lexical z-score exceeds the recall-v1 threshold in 57% of null trials, versus 26% for the semantic score.Source: §5.2 · pp. 6–7

5.3 Theory against data

  • Finite-pool predictions agree with replay within 1.0–1.5 points in-sample; held-out hit-rate predictions remain close, but small-store power laws overstate large-store recall.For bge-small, the cosine hit rate under controlled false alarms falls from 71% at N=8 to 8% at N=2048; finite pools cannot identify the asymptotic tail once per-item rates fall below pool resolution.Source: §5.3 · pp. 7–8

5.4 What the score buys

  • At matched false alarms, the deployed score recalls 14–26 points more than raw cosine, with intervals above zero at every store size.The lexical channel carries the advantage on implicit cues; on LoCoMo the full score beats raw cosine by 8–12 points, though ten conversations do not resolve the components.Source: §5.4 · p. 8

5.5 The cue-swap gate

  • With an unfiltered-history background, cue-swap false alarms stay at 2.6–5.9% on LongMemEval, but LoCoMo reference-cue choice can make the gate liberal or conservative.On LoCoMo, other-conversation references yield 8–10% false alarms, while same-conversation references yield 0.6–3.1% and lower hit rates; at N=2048 and K=199, hits are 8%, 22%, and 28% for α=0.01, 0.05, and 0.10.Source: §5.5 · pp. 8–9

5.6 Chronological replay

  • In chronological replay, the cue-swap gate speaks on 6–8% of session-opening turns from N=16 onward, versus 57% for recall-v1 at N=2048.It finds evidence after the last session in 20% of explicit-question cases and 2% of implicit-cue cases, close to label-tuned rates of 18% and 3%.Source: §5.6 · pp. 9–10

5.7 Several relevant memories; 5.8 A prospective-memory benchmark

  • With repeated or session-wide evidence, recall depends on which relevant turn is counted; on TriggerBench, controlled-false-alarm similarity gates recall only 5–9% of constraints.With the whole evidence session stored, the cue-swap gate retrieves the answer turn in 19% of positive stores at N=2048 and some session turn in 26%; TriggerBench also includes resolved negatives, where the label-tuned threshold fires on 14–17%.Source: §5.8 · p. 10, §5.7 · p. 10

5.9 LLM judges and a reranker; 5.10 What false alarms are

  • At N=2048, the 14B judge gets 28% hits at 4% false alarms, while the cross-encoder recalls 23% with explicit questions and 2% with implicit cues at 5% false alarms.By majority vote, only 5%, 5%, and 11% of recall-v1 false alarms are helpful at N=64, 512, and 2048; the human annotator alone rates 14–15% helpful.Source: §5.9 · p. 11, §5.10 · pp. 11–12

6 Design implications

The design implications favor calibrated, store-aware gates and warn that useful store size depends on score separation. They also identify reasoning-only reminders as beyond similarity gates.

6 Design implications

  • At matched false alarms with explicit questions, standardised combined channels recalled 14–26 points more than raw cosine with bge-small and 7–24 with bge-large.The eligibility rules of recall-v1 contributed nothing and can be dropped.Source: §6 · p. 12
  • A threshold tuned at N=8 reached 87–99% false alarms at N=2048, while the lexical maximum grew about twice as fast as the semantic one.Its upper tail grew faster still.Source: §6 · p. 12
  • The cue-swap gate needs no labels, takes about 50 ms per decision at N=2048, and spoke on 6–8% of chronological session openings versus 57% for recall-v1.Reference cues from other conversations made it overshoot on LoCoMo.Source: §6 · p. 12
  • Usable store size is limited by separation, and small-store slopes overstate large-store recall; in the binormal model, capacity grows exponentially in squared separation.Reasoning-only constraints such as TriggerBench are out of reach of similarity gates and need a judge that reads the conversation.Source: §6 · p. 12

7 Limitations

The evaluation uses benchmark questions and model-written cues rather than real user messages, and its data, assumptions, annotations, and language coverage limit how broadly to interpret results.

7 Limitations

  • Replays use benchmark questions and model-written implicit cues instead of real user messages; cue writers saw answers, and string filtering cannot rule out semantic hints.LongMemEval histories share session text across simulated users, held-out tests hold out questions rather than users, and pooled histories create unusual collisions.Source: §7 · p. 12
  • The main replays use random stores with one relevant item and assume independent scores; the theory covers best-score gates, not judges deciding jointly over candidates.The cue-swap guarantee is marginal and depends on exchangeability; the chronological variant is asymmetric and its firing rates are per-turn interruption rates, not false-alarm rates.Source: §7 · p. 12
  • Annotations come from one non-native English-speaking human reading machine translations and two LLMs, and usefulness labels do not establish whether users welcome interruptions.All experiments are in English; false alarms were sampled under version 1 of the protocol.Source: §7 · p. 12
  • Claude and GPT assisted with code, analyses, drafting, editing, proof review, and annotation; the authors checked the proofs and reported numbers and take responsibility.Source: §7 · p. 12

A Proofs

The appendix proofs relate best-of-store thresholds to per-item rates and hit bounds, including finite-pool and exchangeability results. It also specifies the scoring and gate procedures used in the experiments.

A Proofs

  • With false-alarm level α, the best-of-N threshold sets per-item rate p_N between α/N and −ln(1−α)/N, constraining hits through the relevant-score tail.Under regular variation, the hit rate scales as N^-κ.Source: A Proofs · p. 16
  • The capacity corollary bounds which store sizes can meet a target hit rate using the decreasing per-item threshold rate and the relevant-score distribution.Source: A Proofs · p. 16
  • For sampling without replacement from a finite irrelevant-item pool, the proof bounds hit rates using the relevant-score pass rate and the probability all other items fall below threshold.The average bound includes a covariance term between cue-specific false-alarm rates and pass rates.Source: A Proofs · p. 16
  • The cue-swap p-value controls false alarms marginally under exchangeability; its proof bounds how many cues can meet the nominal level by their rank.Source: A Proofs · p. 16

B Gates and scores

  • The lexical channel uses tf-idf cosine on word tokens, while recall-v1 standardises lexical and semantic scores per cue against a background sample and applies eligibility rules and a size-dependent threshold.Its defaults include channel-specific spread floors and a threshold of max(2, sqrt(2 ln N)) + 0.5.Source: B Gates and scores · p. 17
  • The extreme-value gate fits exponential tails above each channel’s 90th percentile and speaks when the smallest memory-and-channel p-value is at most α/(2N).A generalised Pareto fit was too conservative at moderate N and appears only in released results.Source: B Gates and scores · p. 17
  • The cue-swap gate compares the current cue’s best z-score with those from up to 199 reference questions scored using the same background and eligibility rules.Source: B Gates and scores · p. 17
  • LLM judges see the cue and five memories with the highest cosine, then choose one note to bring up or NONE.Decoding is greedy.Source: B Gates and scores · p. 17

C Background drawn from the null pool

The background protocol affects gate behavior differently: cue-swap changes little on LongMemEval, while the extreme-value gate becomes more conservative as the background tail is contaminated. The section also reports reference-pool sizes and decision latency.

C Background drawn from the null pool

  • On LongMemEval, switching to unfiltered-history backgrounds changes cue-swap false alarms by at most 1.1 points and hits by 1.4 on M, and by at most 2.2 points on S.The extreme-value gate’s false alarms and hits fall with contamination, sharply on S.Source: C Background drawn from the null pool · p. 17
  • LongMemEval-S is reported only through N=128 because just ten questions have null pools of at least 256 turns; on M, backgrounds usually contain 300 items.LoCoMo backgrounds average 296 items at N=128 and 272 at N=256.Source: C Background drawn from the null pool · p. 17

D Cue-swap gate: number of reference cues and nominal level

  • With K=199 reference cues at N=2048, cue-swap scoring takes 15.3 ms and the gate 32.4 ms on one CPU thread.The timing emulates sparse lexical products with dense ones, overstating their cost.Source: D Cue-swap gate: number of reference… · p. 18

E Theory: out-of-sample prediction and simulation

A finite-pool bound predicts held-out hit rates for a label-tuned threshold, while power-law fits and simulations characterize how hit rates decline as stores grow. The simulations also test the accuracy of the theoretical bound across score models.

Out-of-sample prediction

  • Across questions, the calibration-half prediction is lower than the observation at every N below 2048, by at most 4.9 points with bge-small and 6.1 points with bge-large; intervals overlap throughout.Source: E Theory: out-of-sample prediction and… · p. 18
  • A power law fitted at N=32, 64, and 128 predicts declining hit rates at N=256–2048, broadly tracking the observed rates for both embedding models.For bge-small, predictions at N=256, 512, 1024, and 2048 are 0.28, 0.22, 0.18, and 0.14, versus observed 0.25, 0.18, 0.14, and 0.08; for bge-large, predictions are 0.29, 0.22, 0.17, and 0.13, versus 0.27, 0.21, 0.16, and 0.10.Source: E Theory: out-of-sample prediction and… · p. 18

Simulation

  • For exponential null and evidence scores, the exact hit rate agrees with Monte Carlo estimates within sampling error and approaches the Theorem 2 limit closely.The ratio to the limit is 1.0005 at N=8 and at most 1.0001 from N=64 onward.Source: E Theory: out-of-sample prediction and… · pp. 18–19
  • In the binormal model, the local exponent approaches its limit slowly, while the exact hit rate stays within 2% of Proposition 1’s upper bound in both tested cases.The local exponent rises from 0.40 to 0.64 for d=2, s=1, and from 0.09 to 0.24 for d=3.6, s=1.3; the latter limit is 0.59.Source: E Theory: out-of-sample prediction and… · p. 19

F Growth of the null maximum

The fitted growth pattern differs between lexical and semantic null maxima. Lexical maxima favor logarithmic fits across settings, while semantic maxima show less consistent fit preferences.

F Growth of the null maximum

  • The lexical mean maximum is fitted better by ln N in every setting, and the lexical 95% quantile also prefers ln N.For the semantic mean maximum, ln N fits better in three settings, including both implicit-cue settings, while neither fit is better in one; the semantic 95% quantile prefers ln N in two settings.Source: F Growth of the null maximum · p. 19
  • Table 8 reports mean and 95% quantile maxima at the smallest and largest stores, fit residual sums of squares across store sizes, and the lexical-to-semantic quantile-growth ratio.The endpoint sizes are N=8 and 2048 for LongMemEval-M, and N=8 and 256 for LoCoMo.Source: Table 8 · p. 20

H TriggerBench

TriggerBench evaluates whether similarity gates retrieve constraint memories as stores grow, using positive and null conditions alongside resolved or non-applicable controls. The section also describes the benchmark setup and reports an annotation check of sampled false alarms.

H TriggerBench

  • The constraint has the highest cosine in natural base stores for 71% of logical-adherence, 67% of safe-coding, 57% of attention-recovery, 37% of temporal-grounding, and 13% of state-tracking items.In the 40K stores, the corresponding shares are 61%, 29%, 57%, 1%, and 0%.Source: H TriggerBench · p. 20
  • TriggerBench compares positive hits, null firing, and firing on resolved or non-applicable controls across natural and grown stores.Items enter a store size only when the full store fits; at N=8, this leaves 173 scenarios, compared with 245 at other sizes. Positive-store variants include one evidence turn, all evidence turns, repeated evidence, and an evidence session.Source: H TriggerBench · p. 20, Table 10 · p. 21, Table 9 · p. 21

I Experimental details

  • Implicit cues were generated from each question and answer, then filtered for answer leakage and other disallowed content; embeddings used a 256-token limit and no query instruction.A manual sample check found most rewrites acceptable but repetitive, with a few too vague to evoke a memory.Source: I Experimental details · p. 21

J Annotation

  • Among sampled false alarms, majority-vote helpful shares were 3%, 5%, and 12% at N=64, 512, and 2048 after excluding the first 38 items.The sample followed a different protocol and describes the kind of memory that fires, not its frequency under the main protocol; annotation guidance and translation issues also affected some judgments.Source: J Annotation · p. 22
Loading 2610.34507v2…