Verifier-Aware Eviction for Bounded Factual Memory

Language models that check their own facts while writing need somewhere to keep the evidence they retrieve. One recent system, Explicit Working Memory, keeps a small fixed number of retrieved passages and fact-checker corrections in the model's attention cache, meaning the stored internal states the model attends to while generating. When a new passage arrives it discards the oldest one, a first-in-first-out (FIFO) rule. Its authors report that this rule lets stale information linger and confuse the model while early background facts get pushed out simply for being early, and they name importance-based replacement as the obvious next step (Improving Factuality with Explicit Working Memory). This proposal takes that step and makes one specific bet. The most informative signal for what to evict is the fact-checker's own verdicts, not attention. A passage that a correction has contradicted keeps attracting attention precisely because it conflicts with the correction, so any attention-based importance score will protect exactly the stale content that causes trouble.

Concretely, we keep a small approximate Bayesian belief for each memory slot: the probability that this slot will support a correct claim later in the generation. The belief is updated cheaply from three kinds of evidence: how much attention the slot receives, whether claims it supported were verified or refuted, and whether the entity it describes is still under discussion. The slot with the lowest belief is evicted. Borrowing a lesson from traffic scheduling, a time bound keeps any slot from occupying memory forever without being reconfirmed. The question is whether this beats FIFO and, more importantly, beats simple attention-based eviction on claim-level factuality when memory is tight. We also locate the capacity at which the choice of eviction policy starts to matter.

Core Claim

Hallucination work usually evaluates with effectively unlimited context. That is the language-model version of the infinite capacity assumption in operations research. Such planning models hold in off-peak conditions and break at rush hour (Arthur Mahéo et al.), and assuming unlimited storage at transfer hubs degrades planning accuracy (Wouter van Heeswijk et al.). We expect the same shape here. Above some memory size the eviction rule is irrelevant. Below it, factuality depends on which slots survive.

Our claim is that in this "peak demand" regime, eviction that conditions on verifier outcomes cuts factual errors relative to both FIFO and attention-mass eviction. We expect the gain to come mostly from generations in which at least one correction occurred, because that is where attention-based rules keep contradicted evidence around.

The traffic literature supplies the design analogy. FIFO intersection control ignores the physical state of arriving vehicles (Arnaud de La Fortelle). Letting vehicles reorder cuts travel time (Yue Zhang), but unbounded reordering causes starvation unless each vehicle is guaranteed service within a window (Au et al.). The memory analogue of FIFO's blindness is ignoring whether a slot has been contradicted. The analogue of starvation runs the other way: a slot that never leaves.

Method

Each memory slot $i$ has a latent binary variable $z_i$, equal to 1 if the slot will ground a correct claim before generation ends. Each entity $j$ mentioned in memory has a latent $e_j$, equal to 1 if the entity is still active in the text. We approximate the posterior with independent Bernoulli factors $q(z_i)=\pi_i$ and $q(e_j)=\rho_j$, chosen to maximize the standard evidence lower bound:

$$\mathcal{L}(q)=\mathbb{E}_{q}\left[\log p(a,v,m\mid z,e)\right]-\mathrm{KL}\left(q(z,e)\,\|\,p(z\mid e)\,p(e)\right)$$

In this bound, $a$ is each slot's attention share at recent decoding steps, $v$ is the fact-checker's verdict (supported, refuted, or none) on claims attributed to the slot, and $m$ records mentions of each entity in newly generated text. The prior $p(z_i\mid e_j)$ ties a slot's usefulness to whether its entity is still active, and it decays with the slot's age. That coupling is why we use a variational approximation rather than a closed-form filter: exact inference over which subset to keep, with entities shared across slots, is combinatorial. This matches the NP-completeness of optimal cache eviction shown in A Probabilistic Interpretation of KV Cache Eviction. Coordinate updates on $\pi$ and $\rho$ are a few scalar operations per slot at each pause-and-check step. No model call is needed, unlike the utility estimate in A-MAC, which takes over 97% of its runtime (Adaptive Memory Admission Control For LLM Agents).

When a new unit arrives and memory is full, we evict the slot with the lowest $\pi_i$, with two exceptions. First, a slot whose entity is active ($\rho_j$ high) cannot be evicted, which protects entity definitions. Second, a slot that has been in memory longer than a bound $T$ without a supporting verdict is forcibly evicted, so no slot outlives the bound unconfirmed. Slots with intermediate beliefs are demoted to a text tier outside the attention cache rather than deleted, and can be re-admitted if their entity is mentioned again. This two-tier structure borrows the evidence-then-promotion split of SAGE-Mem (Before It Persists: Write-Time Defense for Multimodal Agent Memory). The difference is that we use a soft, probabilistic boundary, which targets its reported collapse in benign completion (0.655 to 0.418).

The likelihood parameters are fit offline. We use logged FIFO runs of the Explicit Working Memory pipeline, labelling each slot in hindsight by whether it later grounded a verified claim.

Relation to Prior Work

Explicit Working Memory (Improving Factuality with Explicit Working Memory) motivates the work and supplies the base system. We keep its memory, verification loop, and backtracking and replace only its FIFO rule.

Two papers on compressing the attention cache supply method and constrain the design. Both evaluate on generic long-context question answering and synthetic retrieval, never on claim-level factuality. A Probabilistic Interpretation of KV Cache Eviction treats attention as an expectation and keeps entries by importance sampling with a correction at decode time. Rethinking KV Cache Eviction via a Unified Information-Theoretic Objective scores subsets by an information-capacity objective under a linear-Gaussian surrogate and assumes future queries resemble past ones. Both are driven purely by attention statistics, and neither can tell that a passage has been contradicted. The second paper's stationary-query assumption fails precisely at topic shifts, which is where our entity-activity variable works.

Agent-memory systems are the closest competitors on admission and consolidation. A-MAC combines five heuristic signals linearly at write time and does not handle eviction. MemoryOS (Memory OS of AI Agent) moves short-term memory to mid-term memory by FIFO and admits that its capacities are tuned empirically. Graph reconstruction in MRAgent (Memory is Reconstructed, Not Retrieved: Graph Memory for LLM Agents) has no forgetting at all.

On the Bayesian side, Bayesian low-rank adaptation (Bayesian-LoRA: Probabilistic Low-Rank Adaptation of Large Language Models) places uncertainty over weights. We place it over memory contents instead, which requires no retraining. We accept the known weakness of independent Bernoulli factors, which underestimate variance. We address it only through the entity coupling, and we test whether that suffices.

Research Program

The work has three parts. The first is a capacity sweep. We run the unchanged Explicit Working Memory pipeline with memory sizes ranging from very small up to effectively unlimited, and we plot factuality against capacity for each eviction policy. This locates the point below which the policy matters.

The second is a diagnostic study of what occupies memory under each policy at each step. We measure the share of slots holding content that a correction has contradicted, and how often an entity definition is evicted while that entity is still being written about. These two numbers are the direct test of the staleness mechanism. If attention-mass eviction does not in fact over-retain contradicted slots, the core bet is wrong, and we will know before any end-to-end comparison.

The third is the full comparison and ablations described below. We then transfer the method to MemoryOS's FIFO boundary between short-term and mid-term memory as a secondary test.

Baselines

The naive reference is the unchanged system with FIFO replacement. The cited paper reports that adding its FIFO-managed working memory raises VeriScore by 2 to 6 points absolute over the base model across LongFact, Fava, AlpacaFact and Biography. The file gives only these deltas, so we will reproduce absolute FIFO scores ourselves at each memory size. The unlimited-memory setting, in which nothing is evicted, is a second reference. It tells us whether bounded memory with a good policy can match or even exceed keeping everything, which could happen because stale context distracts.

The strongest direct competitor is chunk-level attention-mass eviction: drop the slot with the least accumulated, recency-decayed attention. This is the H2O-style heavy-hitter idea lifted to whole memory units, and it is the rule a practitioner would try first. We also run least-recently-attended eviction. At the token level, we run the importance-sampling eviction with decode-time correction from A Probabilistic Interpretation of KV Cache Eviction and CapKV from Rethinking KV Cache Eviction via a Unified Information-Theoretic Objective, each at matched cache bytes. The file reports no factuality numbers for either; it lists only win scores and a Spearman correlation of up to 0.85 on LongBench. We also run an A-MAC-style linear score with its LLM utility call reused for eviction. A-MAC reports admission F1 0.583 on LoCoMo, but that is an admission metric and not directly comparable to our task.

All baselines use Llama-3.1 8B, the same retriever and fact-checker, the same pause schedule, and the same memory budget. Every learned or tuned method, including our likelihood fit and the decay rate for heavy-hitter eviction, gets the same logged-trace training split and the same hyperparameter search budget.

The key ablation removes verifier verdicts from the likelihood. This leaves an attention-and-recency posterior that should behave like decayed heavy-hitter eviction. A second ablation removes the entity coupling, and a third removes the time bound $T$. As an upper bound we compute a hindsight oracle that evicts the slot whose future use is least, the analogue of Belady's optimal cache policy.

Beating the baselines means a statistically reliable VeriScore gain over chunk-level heavy-hitter eviction at the two smallest memory sizes, concentrated in traces that contain a refutation, and closing a meaningful fraction of the gap to the oracle.

Why not just…?

Why not just make memory large enough that nothing is evicted? For short generations this may well be enough, and the capacity sweep will show where. Two things argue against it as a general answer. The Explicit Working Memory authors report that accumulated stale and conflicting context actively confuses the model. On agent memory, MRAgent reports that context stuffing with LangMem consumed 3.2M tokens on LongMemEval against 118k for structured memory, with lower accuracy. If unlimited memory matches our method on factuality, we will report that eviction policy only matters for cost, which is a narrower claim.

Why not just evict by accumulated attention? This is the real threat, and the proposal is built around it. For relevance alone, attention may be as good as anything we can compute. Our argument depends on one empirical fact: contradicted slots keep drawing attention. The occupancy diagnostic measures that directly, and the ablation without verdicts isolates the verdict signal. If the ablation matches the full model, the Bayesian layer adds nothing beyond heavy-hitter eviction, and we will say so.

Why not just re-retrieve by similarity to the current draft at every pause, keeping no memory state? Stateless retrieval avoids eviction entirely. However, it can re-fetch the very passage a correction has just contradicted, since that passage is topically similar, and it throws away the corrections themselves. We include it as an additional baseline and report how often it re-admits previously contradicted passages.

Why not just ask the model which slot to drop? A-MAC shows that model-scored utility dominates latency at 2,644 ms per candidate and transfers poorly to new domains (F1 0.338 on professional dialogue). Models are also overconfident about their own knowledge (Liyan Tang et al., Ayush Agrawal et al.). We run it anyway as a baseline, reporting latency alongside factuality.

Proposed Experiments

The primary evaluation uses LongFact, Biography, Fava and AlpacaFact, scored with VeriScore as in the Explicit Working Memory paper. LongFact is also scored with F1@K using SAFE, which the benchmark paper found agreed with humans on 72% of about 16k facts (Long-form factuality in large language models). We report helpfulness as an AlpacaEval win rate against the base model, where Explicit Working Memory held about 50%. We also report added latency per pause.

The secondary evaluation replaces MemoryOS's FIFO transfer from short-term memory and measures F1 and BLEU-1 on LoCoMo and accuracy on GVD. For robustness we measure benign completion and write admission on LoCoMo-Adv against SAGE-Mem's 0.418 benign completion.

Three results decide the question. First, whether contradicted content occupies more slots under attention-based eviction than under our method. Second, whether our VeriScore advantage over heavy-hitter eviction appears below the capacity threshold and vanishes above it. Third, whether removing verifier verdicts erases that advantage. If all three hold, the verifier-aware eviction rule is the finding. If the third fails, the finding is that attention-based eviction suffices for bounded factual memory, and the next step is cheaper systems rather than richer inference.