acceptodds
Under review as a conference paper at ICLR 2027

Perfect Memory is not Enough for Reliable Lifelong Prediction

Abstract

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 . 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 over a submodular polymatroid before test requests arrive. We develop a scalable stochastic top- 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.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
Uncertainty Quantification, Conformal Prediction, Distribution-Free Inference, Taskwise Coverage, Prediction Sets, Lifelong Learning

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_2viDOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies the problem under the setting of lifelong and continual learning, and raises a conclusion that does perfect memory can not guarantee reliable prediction. The authors formalize taskwise honest prediction, and prove sharp minimax lower bounds to support their claim. In addition, authors propose a scalable stochastic top-B dual Hedge algorithm to optimize the policy. The proposed methods are compared with other two prediction rules on digit vision benchmark, and various ablation studies are complemented to show its optimal performance.

Critical strengths
  1. The authors provide a theoretical investigation into an important but underexplored question in lifelong or continual learning, i.e., whether perfect memory guarantee reliable prediction when the catastrophic forgetting is avoided totally. Existing studies primarily focus on mitigating the CF phenomenon and ignore the prediction performance without the storage limitation.

  2. The experiments are comprehensive and provide strong empirical evidence for the theoretical results, demonstrating the effectiveness of the proposed method.

Critical weaknesses
  1. The paper relies heavily on mathematical notation, but many of them are not clearly defined or explained when they are first introduced, making some parts of the paper difficult to follow and understand.

  2. The theoretical results are derived under the ideal assumptions of perfect memory, which eliminates catastrophic forgetting but may be difficult to achieve in real-world scenarios. Since the number of tasks increases, retaining all historical samples can introduce substantial storage overhead and raise privacy concerns. Therefore, the practical applicability of the theoretical findings is unclear.

  3. Each individual sample is regarded as a task in the experiments, which is against the conventional continual learning setting. In CL setting, a group of samples which follow the same data distribution would be regarded as a task. Since the paper focuses on lifelong learning and continual learning, the conventional CL experimental setting should also be considered or added to demonstrate the effectiveness of the proposed method.

Questions for authors
  1. Why is there a relationship between perfect memory and the reliable prediction of unobserved tasks? In class-incremental learning, even though the knowledge or samples of previous tasks are retained perfectly, the prediction of unobserved tasks is impossible to be achieved. For example, the class labels of task 1 samples are ranged from 1 to 20, and class labels of task 2 samples are ranged from 21 to 40. How can a model trained solely on task 1 generate correct predictions for task 2 samples?

  2. Can the experimental findings be generalized to more complex problems, such as NLP or vison-based benchmark beyond the digit recognition? Can similar results be obtained in models more complex than MLPs? If not evaluated, could you comment on potential challenges in these new experiment settings?

Reviewer_n6w1OpenReview ↗
Rating
2
Confidence
1
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies lifelong prediction in a setting with perfect memory, where tasks recur in a stationary stream, each task has a fixed response, and all observed responses are stored exactly. The authors argue that unseen tasks remain a source of uncertainty and that high average coverage can hide poor coverage on rare tasks. They therefore study taskwise coverage, which requires a coverage guarantee for each task. Under this model, they derive lower bounds on prediction-set size and provide procedures that achieve these bounds. Experiments on synthetic request streams and the scikit-learn digits dataset illustrate the theoretical results and the trade-off between coverage and prediction-set size.

Critical strengths
  1. The paper makes a useful point. Remembering past information does not guarantee reliable predictions on unseen tasks. Good average coverage can also hide poor coverage on rare tasks.
  2. The paper provides a detailed theoretical analysis under its assumptions. It gives lower bounds and methods that achieve them. It also studies how to use a limited query budget and maintain coverage over time.
Critical weaknesses
  1. The experiments are limited, and some comparisons are framed favorably. The only experiment with a learned model uses an MLP on scikit-learn digits (1,797 images of 8×8 pixels), where each "task" is a single image. There is no experiment on any memory-augmented, retrieval, or LLM-based system. The proposed method produces noticeably larger prediction sets than the pooled baseline and covers well above the 90% target, so the cost of the stronger guarantee should be stated more directly.

  2. The setup makes some simplifying assumptions. Each task has a fixed answer, task frequencies are known, and the request distribution does not change over time. It is unclear how well this setup represents the real-world applications discussed in the Introduction. In practice, answers may be uncertain and the environment may change. The authors should explain these limitations more clearly and be more careful when connecting the results to practical lifelong learning.

  3. The presentation needs improvement. The main text is quite dense, and some details require frequent checks of the appendix. It would help to explain the notation earlier. For example, the Introduction presents the expression α(1+pH)\alpha(1+pH) without explaining pp, HH, or the conditions under which this expression applies.

Questions for authors
  1. Could you give a concrete example of how the method would be useful in practice?
Reviewer_XzS4OpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
2
Read review
Paper summary

The paper consider an ideal case where the memory is perfect to find another issue of Continual Learning beside the catastrophic forgetting.

Critical strengths

The finding of another attribute beside the catastrophic forgetting is worth investigating in the future.

Critical weaknesses
  1. My main concern is that the remaining problem is generalization to unseen tasks, not memory. Under the paper’s definition of perfect memory, every observed task is solved by construction, so the only failure left is prediction on tasks never encountered. Domain generalization (DG), meta-learning and lifelong-learning theory already study this problem, and the headline claim holds almost by definition.
  2. The notations are inconsistent and hard to follow. Several symbols carry multiple meanings. For example, GG denotes the number of groups in Prop. 8, a rank function Cor. 7, and audit event in proof of Theorem 5, and a subset of tasks in Prop. 12. This issues appear a lot of time thorough the paper.
  3. The discussion of prior work is brief and does not match the paper’s continual-learning framing. Several adjacent lines of work are absent: Mondrian/class-conditional conformal prediction, online and group-conditional conformal methods, and domain-generalization and meta-learning theory. Without explicit comparisons to this work, it is unclear which results are new.
  4. Most experiments only confirm the theory rather than test practical value. The evaluations on the real challenging data with wide range of ablation studies are suggested to verify the paper's proposed method.
  5. The paper is framed around reliable prediction and generalization in lifelong learning. However, its model assigns each task a fixed answer with no structure linking tasks, so no learning or generalization occurs. The main results quantify the cost of returning uninformative sets on unseen tasks and how to allocate label queries. These are information-acquisition results, as the conclusion itself acknowledges. This disconnect explains why the experiments cannot show such a benefit.
  6. The paper’s presentation is dense and offers limited intuition about its main ideas and their significance. Important contributions and experimental details receive insufficient attention in the main text, leaving readers heavily dependent on the appendix. A clearer narrative, more balanced coverage, and simpler, more measured language would make the paper easier to follow and evaluate.
Questions for authors

Please see the weaknesses above.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.