Perfect Memory is not Enough for Reliable Lifelong Prediction

Lifelong and continual learning have long been organized around a single adversary: catastrophic forgetting. Retrieval systems, exact key-value caches, and persistent memory push that defense to its limit by storing historical interactions verbatim. Yet, even when retention error is eliminated by construction, a fundamental question remains: does perfect memory guarantee reliable prediction? We show that it does not, and we isolate the irreducible statistical bottleneck: the missing mass of unobserved tasks. In heterogeneous, heavy-tailed request streams, standard split conformal prediction offers only marginal coverage, dangerously masking catastrophic coverage collapse on rare, user-specific tasks. We formalize *taskwise honest prediction*, requiring each recurring task to satisfy a distribution-free coverage guarantee at level $1-\alpha$. Through an indistinguishable-worlds construction, we prove sharp minimax lower bounds on prediction set efficiency (Lebesgue measure and cardinality), showing that taskwise validity necessitates set inflation on unobserved tasks. To reduce this cost, we introduce *active query allocation*: proactively spending a hard query budget $B$ over a submodular polymatroid before test requests arrive. We develop a scalable stochastic top-$B$ dual Hedge algorithm circumventing exponential subset constraints. To bridge theory and practice, we introduce the finite-sample *taskwise coverage guard*, certifying validity around any nominal set predictor. Instantiating this guard around pooled conformal prediction (*Guarded CP*) separates certification from prediction, which eliminates tail undercoverage while preserving small empirical set sizes on frequent tasks. Furthermore, we establish *lifetime coverage* across extended deployment horizons, proving that a single greedy query policy is universally optimal across all horizons.