Efficient Lifelong Model Evaluation in an Era of Rapid Progress

Summary

The paper presents the idea of Lifelong Benchmarks as a way to deal with the problem of model overfitting, both at the individual model level and at the community level. The authors present a framework, Sort & Search (S&S), as a way to deal with the ever increasing benchmarking cost: not only does each benchmark have a myriad of samples on which ML models are tested, but there is an ever increasing number of benchmarks on which to evaluate models, thus exponentially increasing the cost for evaluating model performance. S&S addresses the problems of adding N new samples and M new models to the benchmark, which require evaluating the existing models on the N new samples, and evaluating the M new models with all existing samples, respectively. S&S reduces the complexity of these problems by finding the smallest subsets N' and M' such that the evaluation for the remaining N-N' samples and M-M' models can be extrapolated from the evaluation of N' and M'.

Strengths

**Originality:** The idea of creating lifelong benchmarks that grow over time as new models and samples become available is interesting and addresses the relevant problem of overfitting. It's a bit unclear, however, where these new samples and models come from and how the datasets actually grow. If a researcher/engineer has to manually update the benchmark/dataset, is it actually that different from simply creating yet another dataset on which to test models? 
 **Quality:** The submission seems to be technically sound and the claims supported. The methods used are appropriate. The authors seem to have conducted quite an extensive evaluation on the proposed approach, however a re-structuring of the evaluation section could be helpful in highlighting all the key results. The authors seem to have struggled with including all evaluation results in the main manuscript, which resulted in a very condensed evaluation section with very little discussion and explanation of the results. 
 **Clarity:** Overall organisation could be improved, particularly in section 3. It is challenging to follow all the reasoning behind the several steps of the framework. It would be really helpful to have a figure highlighting the steps or depicting the framework. Figure 1, for example, helps a lot with understanding the matrices and the model evaluation. Something similar to that is missing for the framework as a whole. The methodology description of section 3.1 assumes the reader will consult the supplemental material to look at the listings and algorithms, but the main manuscript should be self-contained. Section 4.2 seems to be out of place, as it describes a design decision of the framework, and not something specific to the experiments. The baselines and experimental settings could be introduced more concisely at the start of the experimental evaluation section. It would also be nice to have a list/description of the research questions/attributes that are explored in the evaluation section (e.g. RQ1: what is the cost efficiency of S&S, or something like this) 
 **Significance:** Reducing model evaluation cost is a relevant problem that can have significant impact given not only the increasing size of ML models, but also the widespread training and testing of ML models.

Weaknesses

See above for strengths and weaknesses.

Questions

**a)** Is there an underlying assumption that if a new model M' does well on a "hard" sample s, then it will do well on all samples sorted as easier than s? **b)** How do you know/compute matrix Y, the optimal ranked accuracy prediction matrix? **c)** Did you come you with DP-Search or did you find it in the literature and applied it to your use-case? I couldn't understand if the algorithm was also a contribution. **d)** Could you explain what you mean by "Now, having optimized the ranking, we have a P∗ from the data matrix indicating the sample ordering based on difficulty." (Lines 170-171) **e)** Line 191: "We want to find the best n′ observations" -- best with respect to what? **f)** You present S&S as a framework. If I wanted to leverage different performance metrics to evaluate the models, how would I go about updating the framework to use the new metric? 
 **Comments:** - [line 131] What does EM stand for? 
 **[minor comment / observation]** - [line 110] Typo on operation 2 -- I believe it should be insert_M

Rating

5

Confidence

3

Soundness

3

Presentation

2

Contribution

3

Limitations

The authors could discuss more limitations of the proposed approach. For instance, for what types of tasks does it work? (e.g. only classification or also regression problems?)

Summary

To mitigate models from overfitting to the standardized benchmark itself, new samples can be added to the test set, resulting in a Lifelong Benchmark. However, when a new sample is added, all existing models must be evaluated on the added sample. When a new model is added, it must be evaluated on all existing samples. This results in very high evaluation costs. The authors propose a framework termed Sort & search leveraging dynamic programming. First, the samples are ranked w.r.t. their difficulty and sorted accordingly via alternating minimization. When a new model or sample is added, it is only evaluated against a sampled subset and extrapolated, saving computational cost.

Strengths

- The paper discusses about lifelong benchmarking, which is important in mitigating new methodologies and models overfitting to the benchmark itself. - Computation costs for new evaluations can be effectively reduced (with a trade-off of evaluation error).

Weaknesses

- For Figures 2,3,4, the plots display MAE values larger than $0.1$. In Section 4.6, the paper states that this aleatoric error is irreducible. I am not sure if an MAE of this magnitude is practically tolerable. - The method assumes that the obtained order of difficulty generalizes to new incoming models (Section 3.2), which might not be the case in the real world. Can any observations be provided on the robustness of the proposed method when this assumption is violated? - When consecutively adding new models or data serially, is the matrix $\textbf{P}$ and $\textbf{A}$ recomputed after each addition? If so, does the error accumulate for consecutive additions?

Questions

- For Figures 2,3,4, Could the MAE get lower if more computing is utilized? Could the plots be extended further towards $10^{0}$x compute saved (full evaluation)? (if the experiments are expensive, please do not run them and skip the plot extension part) - It is relatively difficult to grasp the overall outline of the framework only from the writing, could an outline figure be provided? (if not capable, it is OK)

Rating

5

Confidence

3

Soundness

3

Presentation

2

Contribution

3

Limitations

The authors include a limitations section in their manuscript.

Summary

The paper presents a novel approach to addressing overfitting in standardized machine learning benchmarks by introducing Lifelong Benchmarks, which are designed to expand continuously, thereby providing a more dynamic evaluation environment. The authors propose the Sort & Search (S&S) framework for efficient model evaluation on these large-scale benchmarks. The S&S framework reuses previously evaluated models to selectively rank and sub-sample test samples, significantly reducing computational costs. Empirical evaluations on their Lifelong-CIFAR10 and Lifelong-ImageNet benchmarks show that S&S can reduce inference costs with low approximation error. This work contributes to the field by offering a solution for lifelong evaluation, enhancing both model evaluation efficiency and data sample insertion.

Strengths

The paper addresses an important area in the field, offering significant contributions through its novel approach. Specifically, the introduction of the framework called Sort & Search to efficiently evaluate models stands out as a key contribution. It is generally well-written, with well-defined theorems and definitions. The research provides comprehensive experimental evidence to support their claims.

Weaknesses

The paper would benefit from explicitly stating the assumptions about the data samples and models within the main text. I have included specific questions regarding the data samples in the questions section to help clarify these points.

Questions

Q1. Handling Multi-Use/Nested Cases of Benchmarks: The COCO dataset, among others, presents a scenario where each data point is associated with multiple labels, such as categories, super-categories, etc. In the context of lifelong benchmarks, how are these multi-use or nested cases managed? Specifically, would there be multiple versions of COCO to handle each use case separately or would there be just one Lifelong-COCO that handles all annotations? How would these different approaches impact model evaluation and data insertion steps? Q2. Differentiating Difficult Data Samples from Mismatched Data Samples: When evaluating data samples, how do you distinguish between ‘good difficult’ samples and ‘mismatched’ samples that might be irrelevant or noisy?

Rating

7

Confidence

3

Soundness

3

Presentation

4

Contribution

3

Limitations

Yes, the authors adequately addressed the limitations.

Summary

The paper aims to improve the efficiency for evaluating large-scale lifelong benchmarks with the rapidly growing number of machine learning models and samples. To address this issue, the authors propose the Sort & Search framework, which avoids the need to evaluate all samples upon adding new models (or evaluating all models upon inserting new samples). Instead, the proposed Sort & Search framework ranks the samples and selectively applies evaluation to a subset of test samples or models by leveraging previously benchmarked results. The experimental results demonstrate significant improvements in benchmark efficiency, achieving approximately 1000x computational reduction.

Strengths

+ The paper is well-written, with clear examples and theoretical proofs. + The paper targets a practical and pressing problem; the experimental results demonstrate significant compute reduction.

Weaknesses

- The evidence for supporting the effectiveness of the Sort algorithm is missing. Specifically, it would be beneficial to compare the proposed method with a sample-only approach to assess if the Mean Squared Error (MSE) will converge to a similar or a larger value. For example, can we skip sorting and directly perform random sampling to get the samples? If “random sampling-only” with a sufficiently large subset (e.g., n’ ~10^3, with moderate compute cost) yields a comparable MSE, the necessity of the sorting algorithm is questionable. - The reported improvement in MSE is minimal, with only a 0.01 reduction compared to the baseline in Figure 2(c) (e.g., from ~0.14 to 0.13). It is unclear whether such a small improvement justifies the proposed method. What is the reasonable target for MSE, and how challenging is it to achieve a 0.01 improvement? - The proposed framework saves computational resources at the expense of increased storage overhead, however, the storage overhead is not discussed in the paper. - The framework appears to be applicable only to classification models, limiting its scope. Can it be extended to other tasks such as object detection or segmentation? - Minor issue: In Appendix H, the text is overlapped and needs formatting correction.

Questions

1. What are the MSE results of applying uniform/random sampling directly to the sample pool without using the sort algorithm? 2. What is a reasonable target for MSE, and how difficult is it to improve MSE by 0.01? 3. What is the storage overhead introduced by the proposed framework? 4. Can the framework be extended to other tasks such as object detection or segmentation?

Rating

5

Confidence

2

Soundness

3

Presentation

3

Contribution

2

Limitations

Yes

Summary

The authors propose *lifelong benchmarks*, a solution to the high cost and saturation problems of the current evaluation paradigm. They try to predict which samples will be harder to classify to select a subset that can efficiently serve as a proxy for estimating model performance on the full set, and also use these correlates to determine the importance of new samples for evaluating the existing models. "Sort & Search" is their proposed method to bring a 1000x reduction in inference cost by finding these representative samples. Each time a new model is added, the "insert" function is called, intended to efficiently find samples to test this new model on to update the cache of sample-level correctness scores, which can be averaged to return a new score for all models in the benchmark. Using existing information of sample-level difficulty from the performance of initial models, the samples are sorted, using permutation matrix P of the samples that have been compared together across models and prediction matrix Y of which sample/model pairs are correctly/incorrectly scored. By iteratively optimizing Y with constant P and P with constant Y with their DP search algorithm, they can efficiently order the samples by difficulty. Assuming this ordering will generalize to future models, they can employ uniform or random sampling over the ordering of samples, and they can optimize the selection to pick a set of samples that minimizes the error between the full evaluation over all samples and the smaller set, wrt MAE. To efficiently insert samples, they just have to evaluate them on a set of models to estimate their difficulty.

Strengths

Strong mathematical formulation and convincing demonstration of the result.

Weaknesses

Simple classification tasks aren't the domain we're most concerned about evaluating models on efficiently. It is unclear how this would extend to harder domains such as LM evaluation.

Questions

None

Rating

7

Confidence

3

Soundness

4

Presentation

3

Contribution

3

Limitations

Limitations addressed my weaknesses.