PVLDB Reference Format:
. . PVLDB, 14(1): XXX-XXX, 2027.
doi:XX.XX/XXX.XX

¹

1 Introduction↩︎

Large language model (LLM) agents are deployed in increasingly complex, long-running tasks: personal assistants maintaining months of conversation history [1], game-playing agents accumulating strategies over thousands of episodes [2], and research agents that iteratively refine their knowledge through tool use [3]. A common architectural pattern has emerged across these systems: the agent maintains a retrieval buffer of past experience that is queried at each step to inform its current response. This buffer serves as the agent’s long-term memory, supplementing the fixed context window of the underlying language model.

The retrieval buffer operates as follows. At each interaction step, the agent generates a new experience item: in conversational deployments this is typically a user utterance or a stated preference, while in fully agentic deployments it is more often an environment observation, a tool-invocation result, or a completed subtask trace. The agent also receives a query (the current user question, task specification, or sub-goal). It retrieves the top-\(k\) most relevant items from its buffer via embedding similarity search, injects them into the LLM prompt as additional context, and generates a response. When the buffer reaches its capacity limit \(K\), the agent must decide whether to admit the new item and, if so, which existing item to evict. This architecture closely parallels buffer pool management in database systems: a fixed-capacity buffer holds a working subset of items selected from a much larger (potentially unbounded) pool of candidates, and the system must continually decide which items to admit and which to evict as the workload evolves. The admission decision corresponds to whether to bring a page into the buffer pool; the eviction decision to which page to flush. This analogy suggests that decades of research on cache replacement and buffer management policies (LRU [4], LFU [5], ARC [6], and their variants) should directly apply.

Current practice and a surprising finding. Production agent memory systems predominantly inherit these classical heuristics: MemGPT [1] and LangChain [7] default to FIFO/sliding-window eviction [8], while many recent agent frameworks adopt LRU or recency-based scoring. To stress-test this reliance, we conduct comprehensive experiments with 8 cache replacement policies across 4 capacity settings on two datasets from MemoryBench-Full [9]: LoCoMo (10 conversational sessions) and DialSim (3 TV-show dialogue datasets). Our results reveal a counter-intuitive phenomenon: classic cache heuristics consistently underperform even the naive FIFO baseline on semantic workloads. Specifically:

• LRU (Least Recently Used) performs no better than FIFO across the tested cache sizes, falling clearly below it at \(K \in \{20, 50\}\) and only matching it at \(K=10\). Recency of retrieval is not predictive of future utility in conversational agents.

• LFU (Least Frequently Used) and ARC (Adaptive Replacement Cache) rank consistently among the worst, with LFU below FIFO at every \(K\). Frequency accumulation is actively misleading when topics are diverse and non-repeating.

• These failures are systematic: they persist across two datasets with vastly different signal densities (LoCoMo: \(\sim\)​30% hit rate; DialSim: \(\sim\)​4% hit rate), strengthening as \(K\) approaches the working set size, and replicate across multiple random seeds.

What’s really different about semantic memory? The failures above share a common cause. Classic cache theory rests on three implicit assumptions: (i) hits are binary (a page is either in cache or not), (ii) items are addressed by exact ID, and (iii) item utility is determined by access pattern alone (recency, frequency, or some combination). None of these holds for LLM agent memory. Retrieval quality is continuous: a query may be partially answered by a semantically related item. Items are matched by embedding similarity, so a cached item can serve queries from nearby topics even if it has never been accessed exactly. And item value drifts as conversation topics evolve, so any policy that conflates “previously useful” with “currently useful” will systematically misallocate the cache. Existing policies therefore inherit assumptions that the workload no longer satisfies.

Problem formalization. This motivates a new problem formulation that explicitly captures the three departures above. We define the online semantic cache replacement problem with switching costs, with three defining features:

1. Soft hits: Cache utility is continuous (measured by retrieval quality \(\in [0,1]\)), not binary. A “miss” here means poor retrieval quality, not the complete absence of an item.

2. Semantic matching: Items are retrieved by embedding similarity rather than exact ID match. A cached item can partially serve queries from related (but not identical) topics.

3. Non-stationary utility: Item value changes over time as conversation topics evolve. An item highly relevant at turn 50 may become irrelevant by turn 200.

Within this formulation, we express the total cost as the sum of cumulative miss cost (retrieval quality loss) and switching cost (penalties for cache modifications), enabling competitive analysis against an offline optimal policy.

Our approach: SOLAR. The new formulation calls for two coupled decisions: when to modify the cache, and what to put in. SOLAR is built around these two questions, with each component motivated by a specific failure mode of classic policies.

1. When to modify (cost-aware admission control). Always admitting (as classic policies do) wastes the switching budget on noise items and amplifies non-stationarity: useful items get displaced before their value can be observed. We instead gate admission by accumulated regret: a new item enters the cache only when the cumulative cost of not having it exceeds an adaptive threshold \(\tau\). The threshold tracks workload difficulty via exponential moving average. This drives the admission rate down to roughly 17%, keeping the cache populated by genuinely valuable items and turning the switching budget into a scarce resource that is spent only when the cache is demonstrably inadequate.

2. What to put in (Bayesian online eviction). When admission fires and the cache is full, we must pick an eviction target despite uncertainty about each item’s true utility. Heuristics like LRU/LFU collapse this uncertainty into a single proxy statistic (recency or frequency) and ignore the exploration–exploitation tradeoff entirely. We instead maintain a Beta posterior over each item’s utility, updated from implicit retrieval feedback, and evict by Thompson sampling: naturally exploiting items believed to be low-utility while preserving under-observed items long enough to learn whether they are valuable.

The two components interact synergistically. Admission control ensures the cache contains predominantly high-value items, which provides cleaner feedback signals for the Thompson Sampling posteriors. In turn, better eviction decisions preserve the highest-quality items, amplifying the value of selective admission. We empirically verify this super-additive interaction: the combined effect (+0.014 F1 over FIFO at K=50) exceeds the sum of individual effects (+0.003 from eviction alone + +0.007 from admission alone = +0.010).

Theoretical guarantees. We prove that our combined policy achieves:

• Competitive ratio \(\leq 3\) (a universal constant, independent of \(K\), \(T\), and the switching cost \(\lambda\)) against the offline optimal in the worst case, in the standard sense of competitive analysis, and converging to 1 under piecewise-stationary workloads. FIFO, by contrast, has unbounded competitive ratio: we construct a cycling workload where FIFO achieves exactly 0% hit rate while OPT achieves near-perfect performance.

• Eviction regret \(O(\sqrt{KT \log T})\) where \(K\) is cache size and \(T\) is the time horizon, matching the information-theoretic lower bound \(\Omega(\sqrt{KT})\) up to logarithmic factors.

Experimental validation. Beyond the two real-world benchmarks, we design three controlled synthetic experiments, each isolating one structural question that real datasets confound:

• Why do classic policies fail? A cycling workload (working set size \(> K\)) instantiates the worst case behind our \(\Omega(K)\) competitive-ratio theorem: FIFO drops to exactly 0% hit rate, providing a clean empirical witness that the failure is structural rather than an artifact of any particular dataset.

• When does our policy stop winning? A working-set sweep traces the boundary between the regime where selective admission matters and the regime where raw coverage suffices, locating the phase transition as a function of \(K\) and the effective working-set size.

• Why is capacity a constraint at all in the LLM era, where storage is cheap? A retrieval-noise experiment with 5000-item pools demonstrates an inverted-U relationship between pool size and retrieval quality: enlarging the pool past \(\sim\)​1000 items degrades retrieval quality because near-duplicates confuse the embedder. Capacity in semantic memory is therefore bounded by retrieval precision, not by disk space.

Contributions. Our main contributions are:

1. We formalize LLM agent experience memory as an online semantic cache replacement problem, establishing a bridge between the well-studied theory of online algorithms and the emerging challenge of LLM memory management (§2).

2. We reveal the systematic failure of classic cache heuristics on semantic workloads and analyze its root cause: the absence of temporal locality and frequency concentration (§6).

3. We propose a learning-augmented admission-eviction framework with provable competitive ratio and regret bounds, requiring no external predictors or model training (§4, §5).

4. We conduct comprehensive experiments on 2 real benchmarks, 3 synthetic workloads, 8 methods, and 4 capacity settings, providing actionable insights including the phase transition characterization and retrieval noise justification (§6).

2 Problem Formulation↩︎

We formalize LLM agent memory management as an online cache replacement problem in a semantic embedding space. Our formulation captures the key properties that distinguish this setting from traditional paging while remaining amenable to competitive analysis and regret bounds.

2.1 System Model↩︎

Consider an LLM agent that interacts with a user (or environment) over \(T\) discrete time steps. The system maintains:

• A cache (retrieval buffer) \(S_t \subseteq \mathcal{U}\) of experience items, with \(|S_t| \leq K\) where \(K\) is the capacity limit.

• An embedding function \(\phi: \mathcal{U} \to \mathbb{R}^d\) mapping items to a \(d\)-dimensional vector space.

• A similarity function \(\text{sim}(a, b) = \frac{\phi(a) \cdot \phi(b)}{\|\phi(a)\| \|\phi(b)\|}\) (cosine similarity).

At each time step \(t = 1, 2, \ldots, T\), the following sequence of events occurs:

1. Query arrival. A query \(q_t\) arrives, representing the user’s current question or the agent’s current information need.

2. Retrieval. The system retrieves the top-\(k\) items from \(S_t\) ranked by \(\text{sim}(q_t, \cdot)\). Let \(R_t = \text{top-}k(S_t, q_t)\) denote the retrieved set.

3. Response generation. The agent uses \(R_t\) as context to generate a response, incurring miss cost \(\ell_t(S_t)\).

4. Experience generation. A new experience item \(e_t\) is produced from the interaction (the user’s feedback, the agent’s observation, or a summary of the exchange).

5. Cache decision. The policy \(\pi\) makes two decisions:

   • Admission: whether to insert \(e_t\) into \(S_t\).

   • Eviction: if \(|S_t| = K\) and \(e_t\) is admitted, which item \(i^* \in S_t\) to remove.

2.2 Miss Cost Function↩︎

The miss cost \(\ell_t(S_t) \in [0,1]\) quantifies the quality degradation from using cache state \(S_t\) to answer query \(q_t\). In our experiments, we define: \[\ell_t(S_t) = 1 - \text{F1}(q_t, S_t)\] where \(\text{F1}(q_t, S_t)\) is the token-level F1 score of the agent’s response when augmented with items retrieved from \(S_t\), compared against a ground-truth reference answer.

This definition captures several important properties:

• Continuity: Unlike traditional caching where a hit is binary, \(\ell_t\) is continuous. Even a partial match (some relevant items in cache, some missing) yields intermediate cost.

• Composition: The cost depends on the set of retrieved items, not individual items. Two individually weak items may jointly provide good coverage.

• Query-dependence: The same cache state yields different costs for different queries, reflecting the semantic nature of matching.

2.3 Total Cost Objective↩︎

The total cost of a policy \(\pi\) over \(T\) time steps combines miss cost and switching cost: \[\label{eq:cost} \text{COST}(\pi, T) = \underbrace{\sum_{t=1}^T \ell_t(S_t^\pi)}_{\text{cumulative miss cost}} + \underbrace{\lambda \cdot N^\pi}_{\text{switching cost}}\tag{1}\] where:

• \(N^\pi = |\{t : S_{t+1}^\pi \neq S_t^\pi\}|\) counts the number of cache modifications (replacements) under policy \(\pi\).

• \(\lambda \geq 0\) is the per-replacement penalty, capturing the overhead of modifying the cache state.

The switching cost \(\lambda\) serves two roles in our model. First, it captures the computational overhead of updating embeddings and re-indexing the retrieval structure upon each modification. Second, and more importantly, it provides a regularization that prevents pathologically unstable policies (those that replace items every step perform poorly due to insufficient observation time for newly admitted items).

Degenerate policies. The cost objective excludes two degenerate strategies:

• Never replace (\(N^\pi = 0\)): Zero switching cost but potentially maximal miss cost, since the initial cache may quickly become irrelevant.

• Always replace (\(N^\pi = T\)): Minimal miss cost (if the right items are chosen) but linear switching cost \(\lambda T\).

An optimal policy balances these extremes, replacing only when the expected miss cost reduction justifies the switching penalty.

2.4 Fundamental Differences from Traditional Caching↩︎

Our semantic cache model differs from classical online paging [10], [11] in several fundamental ways that necessitate new algorithmic approaches, summarized in Table 1:

The most critical difference is the source of the capacity constraint. In traditional systems, cache size is limited by physical memory. If infinite memory were available, one would simply cache everything. In our semantic setting, even with unlimited storage, retrieval quality degrades as the pool grows large, because the embedding space becomes crowded with semantically similar items from different topics that confuse the retriever. We empirically demonstrate this inverted-U effect in §6: hit rate peaks at a finite pool size and declines thereafter. Thus, the capacity constraint arises from information-theoretic retrieval noise, not physical storage limitations.

2.5 Performance Metrics↩︎

We evaluate cache policies through two complementary theoretical lenses and one empirical metric.

2.5.1 Competitive Ratio↩︎

The competitive ratio measures worst-case performance relative to an omniscient offline algorithm:

A competitive ratio of \(c\) guarantees that the online policy’s cost is at most \(c\) times the optimal, regardless of the input sequence. This is the standard measure in the online algorithms literature [11] and provides worst-case (adversarial) guarantees.

2.5.2 Eviction Regret↩︎

While competitive ratio captures worst-case robustness, regret captures the learning efficiency of the policy under stochastic conditions:

Sublinear regret (\(R_T = o(T)\)) implies that the per-step loss converges to optimal, i.e., the policy learns the correct eviction strategy over time. Linear regret (\(R_T = \Theta(T)\)) means the policy never improves, regardless of experience.

2.5.3 Empirical Metric: Downstream F1↩︎

In experiments, we report the downstream task metric directly: token-level F1 score of the agent’s responses on held-out evaluation queries. This measures end-to-end system quality rather than intermediate retrieval metrics, ensuring that our improvements translate to actual user-facing performance.

2.6 The Admission-Eviction Decomposition↩︎

A key insight of our formulation is that the cache management problem naturally decomposes into two sub-problems:

1. Admission control: Should the new item \(e_t\) enter the cache? This decision directly controls the switching cost term in Eq. 1 and determines the “selectivity” of the cache.

2. Eviction policy: Given that an item must be evicted (because admission is triggered in a full cache), which item should be removed? This decision affects future miss costs by determining which items remain available for retrieval.

Classic policies (FIFO, LRU, LFU, ARC) always admit (\(N^\pi = T - K\) for all runs after the initial fill), differing only in their eviction strategy. Our approach introduces explicit admission control as a first-class component, reducing switching cost and filtering the cache contents to maintain high retrieval precision.

3 Related Work↩︎

3.1 Classic Cache Replacement↩︎

Online cache replacement dates to Bélády’s optimal offline algorithm [4] and Sleator and Tarjan’s competitive analysis [10], proving LRU achieves competitive ratio \(K\). ARC [6] adaptively balances recency and frequency, representing the state-of-the-art heuristic. 2Q [12] uses a two-queue structure as an implicit admission filter; TinyLFU [5] gates admission by frequency. LRU-K [13] and LIRS [14] refine recency signals with inter-reference distances. All these policies assume temporal locality or frequency concentration in access patterns. Our experiments (§6) demonstrate these assumptions fail on semantic workloads.

3.2 Learning-Augmented Caching↩︎

Lykouris and Vassilvitskii [15] initiated caching with ML predictions, achieving competitive ratio interpolating between \(O(1)\) (perfect predictions) and \(O(\log K)\) (adversarial). Rohatgi [16] tightened these bounds. Chen et al. [17] proposed GUARD, robustifying learning-augmented caching to \(2H_{k-1}+2\) while preserving 1-consistency. Song et al. [18] and Liu et al. [19] applied ML to CDN caching via relaxed Bélády and imitation learning respectively.

Our work differs in three ways: (1) no external oracle (we learn from implicit feedback online), (2) continuous soft-hit setting (vs.binary), (3) joint admission-eviction design with admission providing its own CR guarantee.

3.3 Semantic Caching and RAG↩︎

Dar et al. [20] introduced semantic caching for database queries. GPTCache [21] caches LLM API responses by prompt similarity. RAG systems [22]–[24] augment LLM responses with retrieved documents from static corpora, and recent work has pushed RAG toward more advanced question answering settings [25] and comprehensive benchmarking [26]. Our setting differs: the retrieval pool is dynamic (evolves through agent interactions), creating the admission/eviction management challenge absent in static RAG.

3.4 Memory for LLM Agents↩︎

Agent memory systems include MemGPT [1] (hierarchical virtual memory), Voyager [2] (skill library), Generative Agents [3] (memory stream with importance scoring), MemoryBank [27], and Mem0 [28]. Beyond storage abstractions, another line of work targets long-horizon conversational memory through structured organization of past experience, e.g., GRAVITY [29] proposes architecture-agnostic structured anchoring across dialogue sessions. These systems use ad-hoc replacement policies (FIFO, recency-based). A recent survey [30] identifies memory management as an open challenge. Formally, DAM [31] frames memory as sequential decision-making but provides no algorithm or experiments. A-MAC [32] scores admission on 5 factors with an LLM call (2644ms/decision, F1=0.583 on LoCoMo admission); it has no eviction, no theory, and evaluates admission quality rather than downstream performance. MemAct [33] learns memory curation via RL on a 14B model, targeting in-context working memory (token-level), not retrieval buffers.

Our positioning. We are the first to combine: (1) formal problem formulation (cache replacement with switching costs), (2) provable guarantees (constant CR \(\leq 3\), regret \(O(\sqrt{KT\log T})\)), (3) no LLM calls or training, (4) end-to-end task evaluation. Table 2 summarizes.

4 The SOLAR Framework↩︎

We now present SOLAR (Semantic Online Learning-Augmented Replacement), a unified framework for semantic cache management. Rather than combining off-the-shelf components, SOLAR is derived from first principles: we analyze the switching-cost objective (Eq. 1 ) to identify the optimal conditions for cache modification, then instantiate each condition with a mechanism tailored to the specific challenges of semantic workloads.

4.1 From Objective to Design↩︎

The cost objective decomposes into two terms: cumulative miss cost (retrieval quality loss) and switching cost (modification penalty). An optimal policy must answer two coupled questions at each step:

1. When to modify: Should the cache be changed now, or should we wait? Modifying too frequently wastes switching budget; waiting too long accumulates miss cost.

2. How to modify: Given that modification is warranted, which item should be replaced? Choosing poorly wastes the switching budget on a change that does not improve future retrieval.

These are not independent decisions. The answer to “when” determines the context in which “how” operates: if modification is triggered only when the cache is demonstrably inadequate, the newly admitted item is likely to fill a genuine gap. Conversely, good “how” decisions (evicting the right item) maintain cache quality over time, reducing the frequency at which “when” is triggered. This coupling motivates a joint framework rather than separate components.

4.2 Regret-Gated Modification Timing↩︎

We derive the modification timing rule directly from the cost objective. Consider a policy that has not modified the cache for \(\Delta t\) steps, during which it has accumulated miss cost \(c = \sum_{s=t-\Delta t}^{t} \delta_s\) where \(\delta_s = 1 - \text{retrieval\_quality}(q_s, S_s)\). A modification at time \(t\) incurs switching cost \(\lambda\) but resets the accumulation. The modification is cost-effective when: \[c \geq \lambda \cdot f(\text{expected future improvement})\]

Under mild assumptions (bounded per-step cost, diminishing returns of waiting), the optimal trigger condition simplifies to a threshold: \[\text{Modify when } c \geq \tau, \quad \tau^* = \sqrt{2\lambda / L}\] where \(L\) is the average loss rate. This is the classical result from inventory theory (economic order quantity), adapted to our online setting.

Since \(L\) is unknown and non-stationary, we estimate \(\tau\) adaptively: \[\tau_{t+1} = (1-\alpha)\tau_t + \alpha \cdot \delta_t\]

Key property. The modification rate self-regulates: when the cache is adequate (low \(\delta_t\)), accumulation is slow and modifications are rare (\(\sim\)​17% of steps in practice). When the cache becomes stale (high \(\delta_t\)), accumulation accelerates and modifications happen more frequently. The total number of modifications is bounded by \(N \leq T/\tau\) (Theorem 2), directly controlling the switching cost term in our objective.

4.3 Posterior-Guided Content Selection↩︎

When modification is triggered, we must decide which cached item to replace. The challenge is that item utility is:

• Latent: we cannot directly observe how useful an item will be for future queries.

• Non-stationary: an item’s utility changes as conversation topics evolve.

• Partially observable: we only observe whether an item was retrieved (implicit feedback), not its counterfactual contribution.

These properties define an exploration-exploitation problem under uncertainty. We maintain a Bayesian belief over each item’s utility and make decisions by sampling from the posterior, naturally balancing exploitation (evicting items believed to be low-utility) with exploration (maintaining uncertainty about under-observed items).

Specifically, each cached item \(i\) maintains a posterior: \[\mu_i \sim \text{Beta}(\alpha_i, \beta_i)\] updated through two feedback channels:

• Positive evidence (item retrieved in top-\(k\)): \(\alpha_i \leftarrow \alpha_i + 1\).

• Temporal decay (item not retrieved for \(\Delta\) steps): \(\beta_i \leftarrow \beta_i + 0.05\).

The temporal decay implements implicit forgetting: items that are never retrieved see their posterior drift toward low utility, enabling the framework to adapt as topics change. Without this mechanism, items that were useful early in the conversation would accumulate permanent positive evidence, becoming impossible to evict even after becoming irrelevant.

The novelty bonus prevents premature eviction of recently admitted items before sufficient observation. It decays with item age, so long-term fate is determined by observed utility alone.

4.4 Design Coherence and Emergent Synergy↩︎

The two mechanisms in SOLAR are not independent modules assembled post-hoc; they are co-derived from the same cost objective and interact through a self-reinforcing feedback loop.

Principled derivation. The modification timing rule (\(c \geq \tau\)) is not a heuristic filter but the optimal stopping condition under switching costs, analogous to the economic order quantity in inventory theory. The threshold \(\tau\) adapts online and provably converges to \(\tau^* = \sqrt{2\lambda/L}\). Similarly, the posterior-guided selection is not off-the-shelf Thompson Sampling: it incorporates temporal decay (for non-stationarity) and a novelty bonus (for insufficient observation), both absent in textbook formulations and specifically motivated by the implicit, delayed feedback structure of semantic retrieval.

Mutual reinforcement. The super-additive synergy observed empirically (+0.014 vs.+0.003 + +0.007 = +0.010, a 40% bonus) arises from architectural coupling. Regret-gated timing acts as a data quality filter: by admitting items only when the cache is demonstrably inadequate, newly admitted items fill genuine coverage gaps. This produces a cache with clear utility differentiation, providing higher signal-to-noise ratio in posterior updates, which improves selection quality, which maintains cache quality, which raises \(\tau\), which makes timing even more selective. This self-reinforcing loop is an emergent property of the joint design that would not exist if either mechanism operated independently.

Contrast with prior admission-eviction combinations. 2Q [12] gates admission by requiring a second access (a fixed rule unrelated to cost), then uses LRU for eviction. TinyLFU [5] gates by frequency comparison (a heuristic), then uses segmented LRU. In both cases, admission and eviction are designed independently with no feedback between them. SOLAR’s distinguishing feature is that the two decisions share information: the same retrieval feedback that updates posteriors also drives the cost accumulator, and the threshold adaptation responds to the quality of the cache that eviction maintains.

4.5 Computational Complexity↩︎

Let \(d\) denote the embedding dimension, \(K\) the cache capacity, \(k\) the retrieval depth, and \(T\) the total steps.

• Per-step (no modification): Accumulation and threshold check: \(O(1)\). Posterior updates for the \(k\) retrieved items: \(O(k)\). Aging updates (every \(\Delta\) steps): amortized \(O(K/\Delta)\) per step.

• Per-step (with modification): Sampling \(K\) Beta distributions: \(O(K)\). Computing \(\arg\min\) over scores: \(O(K)\). Total: \(O(K)\).

• Amortized per-step: Modifications occur at rate \(\sim L/\tau \approx 17\%\), so average cost is \(O(k + K/\Delta + 0.17K) = O(K)\).

• Retrieval cost (shared by all methods, not SOLAR-specific): Top-\(k\) similarity search over \(K\) items of dimension \(d\): \(O(Kd)\) via brute-force cosine, or \(O(d \log K)\) with approximate nearest neighbor indexing.

• Space: \(2K\) floats for \((\alpha_i, \beta_i)\) pairs, plus \(K\) floats for admission timestamps. Total auxiliary: \(O(K)\), negligible vs.the \(O(Kd)\) storage for item embeddings.

• Wall-clock latency: All SOLAR operations are arithmetic on cached scalars. Measured overhead: \(< 1\)ms per step on commodity hardware (\(K=100\), \(d=384\)). This is 3 orders of magnitude below the LLM inference latency (\(\sim\)​1300ms), making SOLAR’s overhead imperceptible.

5 Theoretical Analysis↩︎

We establish formal separations between SOLAR and baselines through competitive ratio bounds (worst-case) and regret bounds (stochastic). We present the main results with proof sketches sufficient to verify each claim; complete formal proofs are deferred to the extended supplement [34].

5.1 FIFO Has Unbounded Competitive Ratio↩︎

We verify this empirically (§6): on synthetic cycling workloads with \(m/K \geq 1.5\), FIFO achieves exactly 0% hit rate.

5.2 SOLAR Bounds Competitive Ratio↩︎

Our competitive-ratio analysis relies on a regularity condition that isolates exactly what an offline policy can gain by holding a stale-but-fixed cache during an interval in which SOLAR refuses to modify.

This condition holds whenever the cache-content divergence between SOLAR and OPT is small relative to the retrieval depth (\(|E_j| \le k\tau / (2\,|E_j^{\text{len}}|)\), where \(|E_j^{\text{len}}|\) is the epoch length); it formalizes the intuition that a single fixed cache cannot fully compensate for an interval that SOLAR has already certified as inadequate. We make it explicit rather than hide it inside the proof.

Interpretation. The bound is a universal constant \(3\), independent of \(K\), \(T\), and even the switching cost \(\lambda\), a dramatic improvement over FIFO’s \(\Omega(K)\) ratio. The threshold \(\tau = 2\lambda\) minimizes the worst-case ratio 2 ; it differs from the cost-optimal \(\tau^\star = \sqrt{2\lambda/L}\) of §4, which minimizes SOLAR’s own average cost rather than the competitive ratio. The EMA threshold in Algorithm 1 tracks \(\tau^\star\) for average-case efficiency, while the bound above certifies that no fixed-\(\tau\) input can exceed \(3\times\) optimal.

Stationary convergence. Under piecewise-stationary workloads with \(P\) phase changes, the adaptive threshold \(\tau_t\) converges to \(\tau^\star = \sqrt{2\lambda/L}\) (where \(L\) is the stationary loss rate) within \(O(1/\alpha)\) steps per phase. Once converged, SOLAR’s per-step excess cost over OPT vanishes at rate \(O(P/T)\), yielding \(\text{CR} \to 1\) as \(T \to \infty\) for fixed \(P\).

5.3 FIFO Linear Regret↩︎

5.4 Thompson Sampling Eviction↩︎

Theorems 5 and 6 together show that TS is near-optimal (gap: \(\sqrt{\log T}\) factor only).

5.5 Combined Guarantees of SOLAR↩︎

SOLAR inherits both guarantees, with the analyses complementing each other (Table 3):

• Bounded CR from modification timing. Theorem 3 bounds total cost relative to OPT by the universal constant \(3\), independent of \(K\), \(T\), and \(\lambda\). This contrasts with FIFO’s \(\Omega(K)\) ratio and holds regardless of eviction strategy.

• Sublinear regret from posterior-guided selection. Theorem 5 bounds eviction quality loss at \(O(\sqrt{KT\log T})\), which is \(o(T)\) (vanishing per-step loss). This is conditional on the modification schedule determined by the timing mechanism.

• Uniqueness. No other method achieves both: FIFO has \(\Omega(K)\) CR and \(\Omega(T)\) regret; pure posterior-guided eviction without admission control (SOLAR-E) has sublinear regret but \(\Omega(K)\) CR due to a replacement at every step; classic heuristics have \(\Omega(T)\) regret on semantic workloads.

^\(\dagger\)On classical paging (binary hits); on semantic workloads LRU \(<\) FIFO empirically.

6 Experiments↩︎

We evaluate our approach through comprehensive experiments on two real-world benchmarks and controlled synthetic workloads. Our evaluation addresses four research questions:

• RQ1: Do classic cache heuristics fail on semantic retrieval workloads?

• RQ2: Does SOLAR consistently outperform baselines, and what is the source of its improvement?

• RQ3: How do admission and eviction contribute individually, and do they interact synergistically?

• RQ4: Under what conditions does smart cache policy stop providing value (phase transition)?

6.1 Experimental Setup↩︎

6.1.1 Benchmarks↩︎

We evaluate on two datasets from MemoryBench-Full [9], a benchmark for memory and continual learning in LLM systems that provides multi-turn dialogues with simulated implicit user feedback (like/dislike signals). The two datasets represent different points in the difficulty spectrum:

LoCoMo [37]. 10 multi-session personal conversations, totaling approximately 2000 interaction steps. Each session is split into a warmup phase (\(\sim\)​160 queries, during which the agent accumulates experience but is not scored) and a test phase (\(\sim\)​39 QA pairs, scored). The test queries span factual recall, temporal reasoning, and preference tracking. With an embedder-unlimited baseline achieving \(\sim\)​35% F1, this represents a moderate-difficulty task with meaningful signal density.

DialSim [38]. 3 TV-show dialogue datasets (Friends, The Big Bang Theory, The Office) evaluating long-term memory over extended conversations (\(\sim\)​19K messages per corpus, \(\sim\)​60 test queries per show). The embedder-unlimited baseline achieves only \(\sim\)​11% F1, indicating extremely sparse signal: even with perfect memory, most queries cannot be answered from experience alone. This makes DialSim a challenging stress test for memory policies.

Both datasets are used in on-policy mode: the agent processes dialogues sequentially, accumulates experience through its own policy, and is evaluated on held-out test queries. Implicit feedback (like/dislike) from the MemoryBench user simulator provides the hit/miss signal used by SOLAR’s posterior updates.

6.1.2 Methods Compared↩︎

We compare 8 cache management policies spanning three categories:

Baseline (no intelligence):

• Embedder (unlimited): No capacity constraint. All items are stored and retrieved from the full pool. Serves as an upper bound reference.

• FIFO: First-in, first-out. Always admits; evicts the oldest item. The simplest possible policy, and the de facto standard in deployed LLM agent systems (e.g., LangChain’s ConversationBufferWindow).

Classic heuristics (exploit access patterns):

• LRU: Least Recently Used. Evicts the item that was least recently retrieved in a top-\(k\) result. Assumes temporal locality.

• LFU: Least Frequently Used. Evicts the item with the fewest cumulative retrievals. Assumes frequency concentration.

• ARC [6]: Adaptive Replacement Cache. Dynamically balances recency and frequency using ghost lists that track recently evicted items. Represents the state-of-the-art in adaptive heuristic caching.

Learning-augmented (our category):

• SOLAR-E (eviction only): Always admits; posterior-guided eviction via Thompson Sampling [39] (SOLAR’s content selection mechanism in isolation, without regret-gated timing).

• SOLAR-A (admission only): Regret-gated admission; heuristic multi-score eviction (SOLAR’s timing mechanism with a simpler content selector).

• SOLAR: Full framework: regret-gated timing + posterior-guided selection (ours).

6.1.3 Configuration↩︎

Cache sizes: \(K \in \{10, 20, 50, 100\}\), representing tight to loose capacity regimes. Seeds: all results are 3-seed averages with standard errors available. LLM: GPT-4o-mini for response generation. Embedder: all-MiniLM-L6-v2 (384-dimensional sentence embeddings). Retrieval: Top-3 by cosine similarity. Metric: Token-level F1 between agent response and ground-truth reference.

6.2 Main Results: LoCoMo↩︎

Table 4 presents the main result: average F1 across all evaluation queries for each method and cache size combination.

6.2.1 Finding 1: Classic Heuristics Systematically Fail (RQ1)↩︎

The most striking result is the ordering among baselines: at \(K \in \{20, 50\}\) all three classic heuristics (LRU, LFU, ARC) fall below the naive FIFO, and LFU trails FIFO at every \(K\). At the tightest setting \(K=10\), LRU and ARC only match FIFO (within one standard error), never clearly beating it. This is the opposite of what decades of caching research would predict. We analyze the root cause:

• LRU failure: LRU evicts items not recently retrieved. But in conversational agents, an item idle for the last 10 queries may simply be awaiting the right topic to resurface; evicting these “dormant but valuable” items removes long-tail knowledge that FIFO (evicting by arrival order, independent of retrieval history) accidentally preserves.

• LFU failure: LFU preserves high cumulative-count items, which in diverse conversations favors items from the earliest topics (they have had the most time to accumulate hits), even after those topics become irrelevant. The cache becomes a museum of obsolete-but-popular items.

• ARC failure: ARC adaptively combines recency and frequency. When both signals are misleading, its adaptation oscillates between two equally poor strategies.

6.2.2 Finding 2: Learning-Augmented Methods Win at Tight Cache (RQ2)↩︎

SOLAR achieves +22.7% relative improvement over FIFO at K=10 and +4.7% at K=50. Table 5 provides a detailed comparison including temporal dynamics.

The “2nd-half F1 gap” shows that SOLAR’s advantage grows over time: the second half of the evaluation period shows larger improvements than the first half, indicating that the policy continues to learn and improve cache quality throughout the interaction. The “slope ratio” quantifies this: SOLAR’s F1 improves \(1.4\)–\(3.1\times\) faster than FIFO per step.

On effect size. The absolute improvement at K=50 (+0.014) may appear modest, but we contextualize it three ways. First, the gain is largest at the tightest capacity (+0.053 at K=10, +22.7% relative; +75% on DialSim), precisely the regime where production agents with limited context budgets operate. Second, the retrieval ceiling (Embedder = 0.354) bounds any cache policy; SOLAR captures 25% of the gap between FIFO (0.297) and this ceiling. Third, the result is consistent across all 8 configurations: SOLAR ranks first in every \(K\leq50\) setting, the only exceptions being at K=100 where the phase transition favors coverage.

6.3 Ablation: Admission vs.Eviction (RQ3)↩︎

To understand the individual and joint contributions of our two components, we perform an ablation at K=50 (Table 6).

Two key observations:

1. Admission contributes more than eviction. The admission-only variant (SOLAR-A, +0.007) provides more than double the improvement of eviction-only (SOLAR-E, +0.003). This suggests that in semantic caching, the decision of whether to modify the cache at all is more impactful than the decision of which item to evict. Selective admission maintains cache quality passively by preventing noise from entering.

2. Super-additive synergy. The combined improvement (+0.014) exceeds the sum of individual improvements (+0.010). The excess (+0.004, a 40% bonus) arises from the feedback loop: admission filtering produces a cleaner item pool, which provides better feedback for TS posteriors, which in turn produces better eviction decisions. This synergy is not merely additive composition; the components actively enhance each other.

6.4 Cross-Dataset Validation: DialSim↩︎

We validate generalizability on DialSim, which differs from LoCoMo in signal density, domain, and task type (Table 7).

The core LoCoMo findings replicate on DialSim: classic heuristics (LRU, LFU, ARC) fall below FIFO at \(K=50\), SOLAR or SOLAR-A is best at every \(K \leq 50\), FIFO overtakes at \(K = 100\), and SOLAR’s gains are largest at the smallest \(K\). Notably, the relative improvement of SOLAR over FIFO is even larger on DialSim (+75% at K=10 vs.+23% on LoCoMo), and the bar-chart view in Figure 3 makes the cross-\(K\) pattern visually explicit. This aligns with our intuition: when signals are sparser (DialSim hit rate \(\sim\)​4% vs.LoCoMo \(\sim\)​30%), selective admission provides greater value by maintaining a higher signal-to-noise ratio. Each cached item matters more when overall retrieval quality is low.

6.5 Controlled Evaluation: Synthetic Workloads↩︎

Synthetic experiments serve two purposes: (1) validating theoretical predictions in controlled settings free of confounders, and (2) exploring regimes inaccessible with real data (e.g., very large pools). All use 128-dimensional embeddings with top-3 cosine retrieval.

6.5.1 Experiment 1: Cycling Workload (Validates Theorem 4)↩︎

We construct cycling workloads where \(m\) topics appear in strict round-robin order, with cache size \(K = 10\). Each topic generates items within a compact embedding cluster, and queries target the current topic. This directly instantiates the adversarial construction in Theorem 4, with hit rates reported in Table 8 and visualized in Figure 5.

Analysis. FIFO demonstrates perfect thrashing: once \(m > K\) it collapses to exactly 0% hit rate, as every new item evicts precisely the item needed next in the cycle, the empirical manifestation of the \(\Omega(T)\) regret bound (Theorem 4). LRU is no better, and worse near the boundary (0.38 at \(m/K=1\) vs.FIFO’s 0.90): it evicts items not recently retrieved, which in a cyclic order are exactly those about to resurface, so recency acts as an anti-signal. SOLAR-A avoids this pathology through selective admission (store rate \(\sim\)​10%): by rejecting most items it retains a stable subset partially covering the workload, sustaining a 16% hit rate even at \(m/K = 5\) (50 topics competing for 10 slots).

6.5.2 Experiment 2: Working Set Sweep (Phase Transition, RQ4)↩︎

With a fixed workload (15 topics, 10 items per topic, 500 queries with uniform topic distribution), we sweep \(K\) from 5 to 200 to locate the transition point (Table 9, Figure 6).

Phase transition at \(K \approx 30\). The gap peaks at K=15 (+0.10 absolute) and crosses zero at \(K \approx 30\), precisely the effective working set size (\(15\) topics \(\times\) a few items each). Below it, SOLAR-A’s selective admission (\(\sim\)​10% store rate, capping the cache at \(\sim\)​40 items) wins; above it, FIFO holds enough of each topic to serve most queries through pure coverage. The same pattern appears on the real benchmarks (transition in \(K \in (50, 100)\) for both LoCoMo and DialSim), with the boundary scaling with each benchmark’s working set size.

6.5.3 Experiment 3: Retrieval Noise U-Curve↩︎

This experiment justifies our problem formulation by demonstrating that capacity constraints are meaningful even with unlimited storage. We create a large pool (50 topics \(\times\) 100 items = 5000 total) with moderate inter-topic separation (cosine distance 0.30 between topic centers) and intra-topic diversity (std 0.15 around centers). It has two parts: a policy-agnostic probe that establishes the underlying phenomenon, followed by a policy comparison that shows SOLAR exploits it.

(a) The phenomenon (policy-agnostic). We first isolate the intrinsic effect of pool size on retrieval, with no admission or eviction involved: we pre-fill a pool with exactly \(K\) items uniformly sampled from the 5000 and measure retrieval quality over 1000 queries (Table 10, Figure 7). Since the pool is frozen, this measures the retriever alone and is identical for every cache policy; no method is compared here.

Hit rate increases monotonically from K=50 to K=1000 (coverage effect: more items \(\to\) higher chance of having a relevant item in the pool), then drops by 55% from K=1000 to K=5000 (noise effect: too many similar-but-irrelevant items confuse the retriever). Precision@3 tells the same story: at K=5000, the top-3 results contain mostly irrelevant items from “neighboring” topics in embedding space. This establishes that the capacity constraint in LLM memory systems is informational, not physical: even with free, infinite storage, indiscriminate accumulation degrades downstream performance. Admission control is not about saving space; it is about maintaining the signal-to-noise ratio of the retrieval pool.

(b) Policy comparison: SOLAR vs.FIFO. The probe above shows that an overly large pool can hurt; we now ask whether an online policy can avoid it. We run the same workload in stream mode (items arrive over time, \(K\) is the live cache capacity) and compare SOLAR against FIFO (Table 11). Two observations. First, FIFO’s noise collapse is muted online (\(0.087\)–\(0.090\) across \(K \geq 500\), no sharp drop at \(K = 5000\)): its live cache holds the most recent \(K\) arrivals, temporally clustered rather than a uniform sample of all topics, so it accumulates far less cross-topic confusion than the frozen pre-fill. The probe in part (a) is thus a worst case that isolates the noise effect, while online dynamics are milder. Second, and more importantly, SOLAR uniformly dominates FIFO at every capacity and its hit rate is invariant to the nominal \(K\) (flat at \(0.094\)): selective admission caps the effective pool regardless of how large \(K\) is set, so SOLAR needs no capacity tuning, whereas FIFO is lower and more \(K\)-sensitive.

6.6 Learning Dynamics↩︎

To understand how SOLAR improves over time, we analyze the learning slope (F1 improvement per step) on LoCoMo (Table 12; the trajectory is plotted in Figure 4). SOLAR attains the highest slope at \(K \in \{20, 50\}\) and is statistically tied for the highest at \(K=10\), so its cache quality improves at least as fast as any baseline at every \(K\). The margin over FIFO is substantial: \(1.8\)–\(3.1\times\) FIFO’s slope across the three settings (e.g., \(1.26\) vs.\(0.40\) at K=50), so SOLAR’s advantage grows over time, a desirable property for long-running deployments. Classic heuristics fare worst at larger \(K\): at K=50, LFU and ARC have the smallest slopes in the table, barely improving with more data, the empirical signature of near-linear regret (Theorem 4).

6.7 Latency↩︎

SOLAR’s policy decisions are pure arithmetic (\(O(K)\) per modification: threshold check, posterior sampling, \(\arg\min\)), adding \(<\)​1 ms per step. End-to-end latency is therefore dominated by LLM inference (\(\sim\)​1200–1400 ms per GPT-4o-mini call) and is statistically indistinguishable across all policies. This contrasts with A-MAC [32], which issues an LLM call per admission (\(\sim\)​2644 ms overhead); SOLAR attains its F1 gains with no perceptible latency cost.

6.8 Summary of Experimental Findings↩︎

1) Classic heuristics fail (RQ1): LRU, LFU, and ARC systematically underperform FIFO on semantic workloads, validated across 2 benchmarks, 4 cache sizes, and 3 seeds. 2) SOLAR wins at tight cache (RQ2): 5–75% relative improvement over FIFO when \(K \leq 50\), with improvements growing over time (\(1.4\)–\(3.1\times\) learning slope). 3) Super-additive synergy (RQ3): Combined effect exceeds sum of parts by 40%, driven by the modification timing and content selection feedback loop. 4) Phase transition (RQ4): Clear boundary at the working set size. Below it, selectivity dominates; above it, coverage dominates. This provides actionable guidance for deployment. 5) Retrieval noise justifies capacity constraints: Inverted-U curve demonstrates that pool growth degrades performance, validating our problem formulation. 6) Zero latency overhead: SOLAR adds \(<\)​1ms policy computation per step, negligible vs.LLM inference time, and requires no additional LLM calls.

7 Discussion↩︎

7.1 Why Classic Heuristics Fail↩︎

The failure of LRU, LFU, and ARC reflects a fundamental mismatch between their assumptions and semantic workload properties. LRU assumes temporal locality, but topic progression is driven by evolving user intent, so recency of retrieval carries no predictive power. LFU assumes frequency concentration, but in diverse conversations frequency reflects age in cache rather than intrinsic value, degenerating into a “keep the oldest” policy. ARC combines both signals, yet when neither is informative, adapting between them provides no benefit. This pattern likely generalizes to any retrieval system over semantically diverse items without strong access locality.

7.2 The Coverage-Selectivity Tradeoff↩︎

Our experiments consistently identify a phase transition: below the working set size, selectivity dominates (5–23% relative gains on LoCoMo, up to 75% on the sparser DialSim); above it, coverage dominates (FIFO wins by never missing an opportunity to store). The transition point \(K^*\) scales with effective working set size: \(K^* \in (50, 100)\) on LoCoMo, \(\approx 30\) on synthetic. System designers should estimate their working set (e.g., via the FIFO saturation curve) and deploy selective policies only below \(K^*\).

7.3 Retrieval Noise as the True Bottleneck↩︎

The inverted-U curve reveals that capacity constraints in semantic retrieval are informational, not physical: beyond \(\sim\)​1000 items, embedding-space crowding degrades precision faster than coverage gains. Admission control is therefore not about saving storage but about maintaining signal-to-noise ratio; the 17% admission rate is a precision optimization, not just a space optimization.

8 Conclusion↩︎

We formalized LLM agent experience memory as an online semantic cache replacement problem, bridging classical online-algorithm theory and practical LLM memory management. We showed that classic cache heuristics systematically fail on semantic workloads, underperforming even FIFO across two datasets. Our framework, SOLAR, derives modification timing from regret accumulation and content selection from Bayesian online learning, requiring no external predictors, offline training, or LLM calls, and adding \(<\)​1 ms overhead per step. SOLAR delivers 5–75% relative improvement over FIFO at tight cache sizes with super-additive synergy between its two mechanisms, while controlled synthetic experiments confirm the theory (FIFO thrashing, the selectivity–coverage phase transition, and the retrieval-noise U-curve that motivates capacity management even under unlimited storage). These results establish semantic cache management as a principled challenge for the data management community, with connections to learned index structures and adaptive query processing.

References↩︎

---

1. This work is licensed under the Creative Commons BY-NC-ND 4.0 International License. Visit https://creativecommons.org/licenses/by-nc-nd/4.0/ to view a copy of this license. For any use beyond those covered by this license, obtain permission by emailing info@vldb.org. Copyright is held by the owner/author(s). Publication rights licensed to the VLDB Endowment.
   

   Proceedings of the VLDB Endowment, Vol. 14, No. 1ISSN 2150-8097.
   doi:XX.XX/XXX.XX
   ↩︎