Efficient Lifelong Model Evaluation in an Era of Rapid Progress

Authors: ameya  prabhu
vishaal  udandarao
philip h s torr
matthias  bethge
adel  bibi
samuel  albanie
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 20:09:19

Abstract: Standardized benchmarks drive progress in machine learning. However, with repeated testing, the risk of overfitting grows as algorithms over-exploit benchmark idiosyncrasies. In our work, we seek to mitigate this challenge by compiling \textit{ever-expanding} large-scale benchmarks called \textit{Lifelong Benchmarks}. As exemplars of our approach, we create \textit{Lifelong-CIFAR10} and \textit{Lifelong-ImageNet}, containing (for now) 1.69M and 1.98M test samples, respectively. While reducing overfitting, lifelong benchmarks introduce a key challenge: the high cost of evaluating a growing number of models across an ever-expanding sample set. To address this challenge, we also introduce an efficient evaluation framework: \textit{Sort \& Search (S\&S)}, which reuses previously evaluated models by leveraging dynamic programming algorithms to selectively rank and sub-select test samples, enabling cost-effective lifelong benchmarking. Extensive empirical evaluations across $\sim$31,000 models demonstrate that \textit{S\&S} achieves highly-efficient approximate accuracy measurement, reducing compute cost from 180 GPU days to 5 GPU hours ($\sim$1000x reduction) on a single A100 GPU, with low approximation error. As such, lifelong benchmarks offer a robust, practical solution to the ``benchmark exhaustion'' problem.

Main paper: 
 introduction: 
 The primary goal of standard evaluation benchmarks is to assess model performance on some task using data that is representative of the visual world [87] . For instance, the CIFAR10 [54] benchmark tested whether classifiers can distinguish between 10 categories, such as dogs and cats. Subsequent versions like CIFAR10.1 [59] , CIFAR10.2 [59] , CINIC10 [21] , and CIFAR10-W [83] introduced more challenging and diverse samples to evaluate the same objective of classifying 10 categories. As benchmarks become standardized and repeatedly used to evaluate competing methods, they gradually lose their capacity to represent broader tasks effectively. This is because models become increasingly specialized to perform well on these specific benchmarks. This phenomenon, known as overfitting, occurs both in individual models and within the research community as a whole [28, 90] . Fresh approaches must compete with a body of methods that have been highly tuned to such benchmarks, incentivising further overfitting if they are to compete [9, 10] .One approach to preventing models from overfitting to biases [87, 3] is to move beyond fixed test sets by creating an ever-expanding pool of test samples. This approach, known as Lifelong Model Evaluation, aims to restore the representativeness of benchmarks to reflect the diversity of the visual world by expanding the coverage of test sets. One can expand the pool by combining datasets or using well-studied techniques like dynamic sampling [81, 51, 52] , these expanding benchmarks can grow substantially in size as they accumulate samples. This raises the less-explored issue of increasing evaluation costs. As an example, it takes roughly 140 and 40 GPU days respectively to evaluate our current model set on our Lifelong-CIFAR10 and Lifelong-ImageNet datasets (containing 31,000 and 167 models respectively). These issues are only exacerbated in benchmarking foundation models [15] . For instance, evaluating a single large language model (LLM) on MMLU [40] (standard benchmark for evaluating LLMs) takes 24 hours on a consumer-grade GPU [45] . This inevitably will lead to a surge in evaluation costs when benchmarking lots of increasingly expensive models against an ever-growing collection of test samples [78, 22] . Hence, we primarily ask: Can we reduce this evaluation cost while minimising the prediction error?We design algorithms to enable efficient evaluation in lifelong benchmarks, inspired by computerized adaptive testing (CAT) [89] . CAT is a method used to create exams like the GRE and SAT from a continuously growing pool of questions. Unlike traditional tests where all questions must be answered, CAT sub-samples questions based on examinee responses. This approach efficiently gauges proficiency with far fewer questions, while maintaining assessment accuracy. Similarly, we aim to evaluate classification ability of new models without testing on all samples, instead selecting a subset of samples to evaluate models. We propose a method, Sort & Search (S&S), which reuses past model evaluations on a sample set through dynamic programming to enable efficient evaluation of new incoming models. S&S operates by first ranking test samples by their difficulty, done efficiently by leveraging data from previous tests. It then uses these updated rankings to evaluate new models, streamlining the benchmarking process. This strategy enables efficient lifelong benchmarking, reducing the cost dramatically from a collective of 180 GPU days to 5 GPU hours on a single A100 GPU. We achieve a 1000× reduction in inference costs compared to static evaluation on all samples, reducing over 99.9% of computation costs while accurately predicting sample-wise performance. Moreover, with a single algorithm, we address both key challenges: expanding dataset size and evaluating new models given a dataset.Taken together, our main contributions are:1. We curate two lifelong benchmarks: Lifelong-CIFAR10 and Lifelong-ImageNet, consisting of 1.69M and 1.98M samples respectively. 2. We propose Sort & Search, a novel framework for efficient model evaluation. 3 . We show that our simple framework is far more scalable and allows saving 1000x evaluation cost. 4. We provide a novel decomposition of errors in Sort & Search into largely independent subcomponents (aleatoric and epistemic errors). 5. We prove and empirically validate that our solution for the Search sub-component reaches the optimal solution and our framework is stable under repeated additions without any degradation. 
lifelong model evaluation: formulation and challenges: 
 We first formalise evaluation in lifelong model evaluation and describe the key challenges it raises.Formulation. Let D=((x 1 , y 1 ), . . . , (x n , y n )) denote an ordered collection of labeled examples, sampled from the underlying task distribution of interest P (X ×Y). Here, x i ∈X denotes the i th data sample and y i ∈Y denotes the corresponding label. Let M=(f 1 , . . . , f m ) denote an ordered collection of models where each model, f :X →Y, maps data samples to predicted labels. Lifelong benchmark, B=(D, M, insert D , insert M , metrics), augments D and M with three operations: Inserting ∆m models ( 2 insert M ). Suppose that ∆m new models have just been released. We wish to insert these new models into M and efficiently predict performance of these new models.1 insert D ((x ′ , y ′ )) inserts a new labeled example (x ′ , y ′ ) into D. 2 insert M (f ′ ) inserts a new model f ′ into M.A naive approach would entail evaluating the ∆m models on all |D| samples. Our first challenge is: Can we instead generate the prediction matrix by performing inference only on a small subset of n ′ ≪ |D| samples? We want to enable accurate prediction of the remaining entries in the prediction matrix.Inserting ∆n samples ( 1 insert D ). Our second challenge arises when we obtain new ∆n labeled data examples. We seek to insert these samples into D and efficiently predict performance of these new samples. A naive approach entails evaluating all |M| models on the ∆n new examples. As above, to substantially reduce cost, we select a small subset of m ′ ≪ |M| models with the objective of accurately predicting the remaining entries of the prediction matrix corresponding to the new ∆n samples.Approach. Our approach is characterized by two key ideas. First, we augment B with an instancelevel accuracy cache to amortise inference costs across evaluations. The cache is instantiated as a matrix A ∈ {0, 1} |M|×|D| where A(i, j) ≜ I[f i (x j ) = y j ]. Second, we propose strategies to efficiently generate the prediction matrix Y ∈ {0, 1} |M|×|D| , using a combination of sampling and inference leveraging the accuracy cache. Our methodology is illustrated in Fig. 1 .Connections to Existing Literature. The lifelong model evaluation setup, where M and D grow over time, has received limited attention [3] , the sub-challenge of efficiently evaluating models when new models are released has received more focus. Concretely, this maps to the problem of insert M ( 2 ) within our framework. We comprehensively draw connections across different research directions in Appendix H and briefly present the most similar works here. Model Spider [105] efficiently ranks models from a pre-trained model zoo. LOVM [110] , Flash-Eval [106] and Flash-HELM [67] similarly rank foundation models efficiently on unseen datasets. However, these approaches predict dataset-level metrics rather than instance-level metrics, and thereby cannot be used in our setup to grow the prediction cache efficiently (see Section 2.1). Concurrent to our work, Anchor Point Sampling [91] and IRT-Clustering [69] both propose efficient instance-level evaluations by creating smaller core-sets from test data. They introduce clustering-based approaches and item response theory [4] to obtain sample-wise accuracy predictions. However, their methods require memory and time complexity quadratic in the number of data samples, i.e., O(|D| 2 ) requiring well over 10TB of RAM for benchmarks having a million samples. The comparisons are infeasible to scale on datasets bigger than a few thousand samples. In contrast, our novel Sort & Search approach, requires memory and time complexity of O(|D| log |D|) with the number of samples, and can scale up to billion-sized test sets (see Section 4 for empirical results). In practice, our method only requiring only two 1D arrays of size of the number of samples, requiring extremely minimal storage overhead, being less than 3GB in absolute terms on billion scale datasets. Furthermore, we motivate why one should adopt sample-wise prediction instead of overall accuracy prediction below.Given model predictions y m+1 and ground-truth predictions a m+1 , current methods typically measures whether one can predict the average accuracy over the full test, measured by mean absolute difference of aggregate accuracies E agg (y m+1 , a m+1 ) = |(|ym+1|-|am+1|)| /n. We argue this is highly unreliable as minimizing the metric only requires predicting the count of 1s in the prediction array rather than correctly predicting on a sample level. For instance, consider a ground-truth prediction array of [0,0,0,1,1,1]. A method that predicts [1,1,1,0,0,0] as the estimated prediction array achieves optimal E agg of 0 despite not predicting even a single sample prediction correctly! More generally, it is always possible to obtain globally optimal E agg of 0 while having worst-case mean-absolute error E for any ground truth accuracy a m+1 . Formally, Theorem 2.1. Given any ground-truth vector a m+1 , it is possible to construct a prediction vector y m+1 such that E agg (y m+1 , a m+1 ) = 0 and E(a m+1 , y m+1 ) = 2.min(1-|am+1| /n, |am+1| /n)One might wonder whether these worst case bounds ever occur in practice. We empirically test a simple yet optimal array construction, given with oracle ground-truth dataset-level accuracy of k2 , which achieves E agg = 0, and consistently observe high mean-absolute error E of 0.4-0.5 on a sample level on our lifelong benchmarks (n=∼10 We first describe our Sort and Search method in the case when new models are added ( 2 insert M ), and subsequently show that the same procedure applies when we have new incoming samples ( 1 insert D ) simply by transposing the cache (A → A T ). A full schematic of our pipeline is depicted in Fig. 2 . 
ranking by sort: 
 Setup. We recall that our lifelong benchmark pool consists of evaluations of |M| models on |D| samples. For ease of reference, say |M|=m and |D|=n, and we have our cache A ∈ {0, 1} m×n (see Fig. 1 left ). We can decompose the cache A row-wise corresponding to each model f i , i ∈ {1, .., m}, obtaining the binary accuracy prediction across the n samples, denoted bya i = [p i1 , p i2 . . . , p in ].Here, p ij ∈{0, 1} represents whether the model f i classified the sample x j correctly.Goal. Given the cache A, we want to obtain a ranked order (from easy to hard) for its columns, which represent the samples. This sorted order (Sort) can later be used for efficient prediction on new incoming models (Search). We want to find the best global permutation matrix P ∈ {0, 1} n×n , a binary matrix, such that AP permutes the columns of A so that we can rank samples from easy (all 1s across models) to hard (all 0s across all models). We say this has a minimum distance from the optimal ranked accuracy prediction matrix Y ∈ {0, 1} m×n computed by the hamming distance between them, posed as solving the following problem:EQUATIONFigure 2 : Full Pipeline of Sort & Search. For efficiently evaluating new models, (Left) we first sort all data samples by difficulty (refer Section 3.1) and (Right) then perform a uniform sampling followed by DP-search and extrapolation for yielding new model predictions (refer Section 3.2). This entire framework can also be transposed to efficiently insert new samples (refer Section 3.3).By definition of a permutation matrix, the constraints P1 n = 1 n , 1 ⊤ n P = 1 n on binary P enforces by definition that P is a valid permutation matrix. The ranked accuracy prediction matrix Y is a binary matrix created by a row-wise application of a thresholding operator for every row in Y separately. The informal explanation of the optimization problem in Eq. ( 1) is to find an ordering of samples such that error introduced by thresholding is minimized.We next discuss how to solve this optimization. While the goal is finding the optimal permutation P * , we still need to jointly solve for P, Y here. We find a solution by alternating between optimizing P keeping Y constant and optimizing Y keeping P constant, with the goal of finding the best P * , with a coordinate descent algorithm. We now present algorithms for optimizing the two subproblems.We know P is binary from Eq. (1). Hence, finding the optimal P * is NP-Hard [101] . To simplify the sub-problem, we first present an algorithm to solve the case where we can order samples in a strictly decreasing order of difficulty, measured by how many models classified it correctly ( 1 ). However, samples cannot be arranged as strictly decreasing in practice. Subsequently, we present an alternative which computes soft confidences, enabling the strictly decreasing constraint to hold ( 2 ) . A third alternative we explore removes the introduced constraint of a strictly decreasing order ( 3 ).1 Sorting by Sum. We discuss how to order samples if they follow a strictly decreasing order of difficulty. We can order samples in decreasing order of difficulty by a simple algorithm detailed in Listing 1 (sort_by_sum)-intuitively, this algorithm greedily sorts samples from easy (more 1s) to hard (less 1s) by sorting the sum vector across rows per column (which can trivially be converted to the permutation matrix P * ).However, the assumption of strictly decreasing order of difficulty is unrealistic as the number of samples is usually far larger than the number of models. Hence, it is guaranteed that many samples will have the same level of difficulty by the pigeonhole principle [2] . We propose to address this by two methods: (a) Converting the cache (A) to store confidence predictions of ground truth class rather than accuracy (Algorithm 2 ), or (b) Iteratively optimizing rows which are tied in sum values (Algorithm 3 ). Note that we find 1 Sorting by Sum effective in all our tested scenarios, but provide these alternatives in the case where it is insufficient.2 Sorting by Confidence Sum. One method to have a strictly decreasing order is to relax the constraint on the samples ofa i = [p i1 , p i2 . . . , p in ] from p ij ∈ {0, 1} to p ij ∈ [0, 1],and use confidence of the ground truth class. This modification allows all examples to be unique. The procedure is then identical to Sorting by Sum, i.e. algorithm still greedily sorts samples from easy (more 1s) to hard (less 1s) by sorting the sum vector across rows per column.3 Recursive Sorting by Sum. Another alternative is relaxing the equal difficulty assumption in Algorithm 1 . A natural question is: How does one order samples which have equal number of models predicting them correctly, i.e., two columns of A with equal number of 1s?We propose an iterative solution: at each step, order samples of equal difficulty by alternatively optimizing P keeping Y constant by applying Algorithm 1 and optimizing Y keeping P constant by DP-Search algorithm (presented in the next Section). We provide the algorithm for two iterations for an illustration in Listing 1 (two_stage_sort_by_sum). Note that this strictly improves the solution at each recursion depth. Note that ties are broken by preferring the model which minimizes error the most.Optimizing Y given a P, is equivalent to finding a row-wise threshold k ≤ n minimizing the error with the matrix AP for a given P. Intuitively, if the threshold for the i th row is k, then the i th row is of the form[1 ⊤ k , 0 ⊤ n-k ]where 1 k is a vector of all ones of size k and 0 n-k is a zero vector of size n -k. In every row, all samples before the row-wise threshold k are predicted to be correctly classified (easy) and those after are incorrectly classified (hard) for the model corresponding to the row. To optimize Y given P, we propose a dynamic programming algorithm, DP-Search which operates on each row y i , detailed in Listing 1 (dp_search). Given a row in Y, DP-Search computes the difference between number of 1s and number of 0s for each index. By using a prefix sum structure, for an input of size n, the DP approach reduces time complexity from O(n 2 ) to O(n). The optimal threshold k is the index of the maximum value in this vector. The vectory i is simply [1 ⊤ k , 0 ⊤ n-k ]where 1 k is a vector of all ones of size k and 0 n-k is a zero vector of size n -k. DP-Search is guaranteed to return the globally optimal solution: Theorem 3.1. Optimality of Y given P. For any given a i ∈ {0, 1} 1×n and P, DP-Search returns an ordered prediction vector y i ∈ {0, 1} 1×n which is a global minimum of ∥a i Py i ∥ 1 .Applying DP-Search independently row-wise, the algorithm returns the optimal Y given P. Now, we shallWe have outlined the process of optimizing (i) P given Y and (ii) Y given P. Note that (i) alone suffices for Sorting Operation when using the 1 Sorting by Sum algorithm, while a combination of (i) and (ii) is primarily needed for 3 Recursive Sorting by Sum. After sorting, we obtain AP * , which reflects the sample ordering based on difficulty. In the following section, we will reuse (ii) to search for a Y given P to efficiently evaluate new models or add new samples.Goal. After solving Eq. ( 1), we obtain the optimal P * in the sorting phase. We assume that this sample difficulty order generalizes to new models, ∆m. Recall that AP * represents the columns of cache A, ordered by sample difficulty (those most often misclassified by models). Given ∆m new models, our goal is to predict accuracy across all n samples for each model, i.e., the accuracy matrix Y ∆m ∈ {0, 1} ∆m×n . This would be simple if we could evaluate all ∆m models on all n samples, but this approach is costly. The challenge is thus to predict performance on the remaining samples while evaluating only a small subset n ′ ≪ n. Hence, we will assume that we can create a smaller ground truth subset a ′ m+1 and study: How to find the best accuracy prediction vector y m+1 ? We use the ground truth vector a m+1 for evaluating the efficacy of our method.Recall that evaluation of every new model can be done independently of others, i.e. Y ∆m is separable per row. Hence, we describe the problem for the first new model y m+1 ∈ {0, 1} 1×n here.(i) How to get the optimal y m+1 ? Our goal here is to generate the sample-wise prediction vector y m+1 ∈ {0, 1} 1×n . We divide it into two subtasks: selection and optimization. The selection task is to select the best n ′ observations to sample. The optimization task is, given the n ′ observations a ′ m+1 ∈ {0, 1} 1×n ′ how to generate the prediction vector y m+1 ∈ {0, 1} 1×n .Subtask 1: How to Select Samples? We want to find the best n ′ observations forming a ′ . Note that any ranked solution we obtain using this vector needs to be interpolated from n ′ points to n pointswe use this intuition to sample n ′ points. Hence, a simple solution is to sample points such that any threshold found minimizes the difference between the actual threshold and a threshold predicted by our set of n ′ , i.e., sample n ′ points uniformly, providing the algorithm in Listing 1 (uniform_sampling). We also compare empirically with a pure random sampling approach in Section 4.Subtask 2: Optimizing y m+1 . Given the n ′ observations a ′ m+1 ∈ {0, 1} 1×n ′ , how to generate the prediction vector y m+1 ∈ {0, 1} 1×n ? We use the threshold given by DP-Search (Listing 1) and obtain the threshold, given in terms of fraction of samples in |a ′ m+1 |. We extrapolate this threshold from n ′ to n points, to obtain the threshold for the prediction vector y m+1 . y m+1 is simply [1 ⊤ k , 0 ⊤ n-k ] where 1 k is a vector of all ones of size k and 0 n-k is a zero vector of size n -k.So far, we have only discussed evaluation of ∆m new models ( 2 insert M ). How can we also efficiently extend the benchmark i.e. efficiently adding ∆n new samples ( 1 insert D )?To add new samples into our lifelong benchmark efficiently, we have to estimate their difficulty with respect to the other samples in the cache A. To efficiently determine difficulty by only evaluating m ′ ≪ m models, a ranking over models is required to enable optimally sub-sampling a subset of m ′ models. This problem is quite similar in structure to the previously discussed addition of new models, where we had to evaluate using a subset of n ′ ≪ n samples. How do we connect the two problems?We recast the same optimization objectives as described in Eq. ( 1), but replace A with A ⊤ and Y with Y ⊤ . In this case, Eq. ( 1) would have A ⊤ P, which would sort models, instead of samples, based on their aggregate sum over samples (i.e., accuracy) optimized using Algorithm 1 to obtain P * , ordering the models from classifying least samples correctly to most samples correctly. Here, Algorithm 1 is sufficient, without needing to solve the joint optimization ( 3 ) because accuracies (sum across rows) are unique as the number of samples is typically much larger than the number of models. In case of new incoming samples ∆n, we similarly would treat every sample independently and optimize the predicted array y ⊤ n+1 using Efficient Selection by Search (Section 3.2). 
experiments: 
 To validate Sort & Search empirically, we showcase experiments on two tasks: 1 efficient estimation of new sample difficulties (insert D ) and 2 efficient performance evaluation of new models (insert M ). We then comprehensively analyse various design choices within our S&S framework.Lifelong-Datasets. We combine 31 domains of different CIFAR10-like datasets comprising samples with various distribution shifts, synthetic samples generated by diffusion models, and samples queried from different search engines to form Lifelong-CIFAR10. We deduplicate our dataset and downsample images to 32×32. Our final dataset consists of 1.69M samples. Similarly, we source test samples from ImageNet and corresponding variants to form Lifelong-Imagenet, designed for increased sample diversity (43 unique domains) while operating on the same ImageNet classes. We include samples from different web-engines and generated using diffusion models. Our final Lifelong-ImageNet contains 1.98M samples (see full list of dataset breakdown in Appendix C).Model Space. For Lifelong-CIFAR10, we use 31, 250 CIFAR-10 pre-trained models from the NATS-Bench-Topology-search space [25] . For Lifelong-ImageNet, we use 167 ImageNet-1K and ImageNet-21K pre-trained models, sourced primarily from timm [98] and imagenet-testbed [84] .Lifelong-CIFAR10, we hold-out CIFAR-10W [83] samples for evaluation (∼500, 000 samples) and use the rest ∼1.2 million samples for sorting. We do not perform experiments for Lifelong-Imagenet since the number of models is quite small (167 in total), directly evaluating all models is relatively efficient, as opposed to the more challenging Lifelong-CIFAR10 where evaluation on 31, 250 models is expensive, practically necessitating reducing the number of models evaluated per new sample.Model Evaluation Split ( 2 insert M ). To study efficient evaluation of new models, we split the model set for the Lifelong-CIFAR10 benchmark into a randomly selected subset of 6, 000 models for ordering samples (i.e., Sort) and evaluate metrics on the remaining 25, 250 models (i.e., Search). For Lifelong-Imagenet, we use 50 random models for ordering samples and evaluate on 117 models. Metrics ( 3 metrics()). We measure errors between estimated predictions for each new model y m+1 and ground-truth predictions a m+1 using mean-absolute error (MAE): E(a m+1 , y m+1 ): Key Result 1: Extreme Cost-Efficiency. From Figs. 3(a) and 3(b), we note our approach converges to a very low mean-absolute error with 1 /1000 the number of evaluation samples, leading to extreme cost savings at inference time (from 180 GPU days to 5 GPU hours on one A100-80GB GPU) 4 .EQUATIONKey Result 2: Mean Absolute Error Decays Exponentially. Upon analysing the observed E vs. n ′ relationship, we note that exponentially decreasing curves fit perfectly in Figs. Key Result 3: Outperforming Baselines by Large Margins. We construct a competitive, scalable version of Vivek et al. [91] as a baseline, called CopyNearest&Expand: It first samples n ′ points out of n (similar to S&S without sorting), and then expands the n ′ -sized prediction array to n samples by copying the rest n-n ′ predictions from the nearest neighbor prediction array from the ranking set of models. We note that this baseline is equivalent to removing the Sort component, and only using random sampling. Comparing to the baseline, we see from Fig. 3 (c) that our Sort & Search is:1) More accurate: It achieved 1% lower MAE at a sampling budget of n ′ =8192 compared to the baseline, meaning that on average, our S&S correctly classifies ∼19k more samples.2) Faster convergence: S&S converges much faster than the baseline (at n ′ =1, 024 vs. n ′ =32, 768) thereby showcasing the high degree of sample efficiency in converging to the minimal error.3) Consistent: Fig. 4 (b) shows the better consistency of S&S, across wider range of models used for Sort-at n ′ =512, S&S with only 10 Sort-models still outperforms the baseline using 50 Sort-models.Storage Efficiency. Storage Efficiency. Our method (S&S) achieves high storage efficiency, requiring only two 1D arrays: one to store the sort-sum and another to construct the current search output. This results in minimal storage overhead, amounting to just 0.0166% of the input data or less than 100 MB in absolute terms. Consequently, Sort&Search not only outperforms alternative methods, such as CopyNearest&Expand, but is also far more memory-optimized. We next showcase results for the task ( 1 ) where for new samples, the goal is to sub-sample the number of models to evaluate, for accurately determining sample difficulty. We present results on Lifelong-CIFAR10, with two different methods for ranking models 5 , Sorting by Sum ( 1 ) and Sorting by Confidence Sum ( 2 ). We evaluate over 9 model budgets m ′ (number of models evaluated over): {8, 16, 32, 64, 128, 256, 512, 1024, 2048}. From Fig. 4 (a), we observe that both methods converge quickly-Sorting by Sum ( 1 ) reaches an MAE < 0.15 by only evaluating on m ′ =64 models out of 31, 250 (10 4 × computation savings). This demonstrates our method's ability to efficiently determine sample difficulty, enabling efficient insertion back into the lifelong-benchmark pool.Varying the Number of Sort-Models Used. In Fig. 4 (b), we analyse the effect of the number of models used for computing the initial ranking (i.e., m) on the final performance on Lifelong-ImageNet.Using more models improves MAE-using lesser models for ranking (m=10) converges to a higher MAE (2% difference at convergence when using m=50 (blue line) vs. m=10 (red line)). Note that the m used for ranking does not have any effect on the speed of convergence itself (all methods roughly converge at the same sampling budget (n ′ =2, 048)), but rather only on the MAE achieved.Different Sorting Methods. We compare the three different algorithms on Lifelong-Imagenet: 1 Sorting by Sum, 2 Sorting by Confidence Sum, and 3 Sorting by Recursive Sum. From Fig. 4 (c), we note an MAE degradation when using the continual relaxation of the accuracy prediction values as confidence values, signifying no benefits. However, using the multi-step recursive correction of rankings ( 3 ) provides significant boosts (0.5% boost in MAE at all n ′ >1, 024) due to its ability to locally correct ranking errors that the global sum method ( 1 ) is unable to account for.Different Sampling Methods. In Fig. 4 (d), we compare methods used for sub-selecting the datasamples to evaluate-we compare uniform vs. random sampling. Both methods converge very quickly and at similar budgets to their optimal values and start plateauing. However, uniform sampling provides large boosts over random sampling when the sampling budget is small (5% lower MAE at n ′ =8)-this can be attributed to its "diversity-seeking" behaviour which helps cover samples from all difficulty ranges, better representing the entire benchmark evaluation samples rather than an unrepresentative random set sampled via random sampling.Here, we showcase a decomposition of the errors of Sort & Search. Specifically, the total mean absolute error E(a m+1 , y m+1 ) can be decomposed into a component irreducible by further sampling, referred to as the Aleatoric Sampling Error (E aleatoric ), and a component which can be improved by querying larger fraction of samples n ′ , referred to as the Epistemic Sampling Error (E epistemic ).Aleatoric Sampling Error. Let y * m+1 = y ′ when n ′ = n, i.e., it is the best prediction obtainable across all subsampled thresholds, as we have access to the full a m+1 vector. However, some error remains between y * and a m+1 due to the ordering operation (i.e., Sort). This error, caused by errorsAleatoric ErrorLifelong-ImageNet Figure 5 : Error Decomposition Analysis on Lifelong-CIFAR10 (left) and Lifelong-ImageNet (right). We observe that epistemic error (solid line) drops to 0 within only 100 to 1000 samples across both datasets, indicating this error cannot be reduced further by better sampling methods. The total error E is almost entirely irreducible (Aleatoric), induced because new models do not perfectly align with the ranking order P * . This suggests generalizing beyond a single rank ordering, not better sampling strategies, should be the focus of subsequent research efforts.in the generalization of the permutation matrix P * cannot be reduced by increasing the sample budget n ′ . More formally, we define this error as:EQUATIONEpistemic Sampling Error. Contrarily, there is a gap between optimal ranking prediction y * m+1 and y m+1 with the current sample size n ′ . This gap, Epistemic Sampling Error, is formally defined as:EQUATIONResults. We analyse sampling effectiveness in Lifelong CIFAR-10 and Lifelong-ImageNet by studying the Epistemic Sampling Error (E epistemic ) and Aleatoric Sampling Error (E aleatoric ) in Figure 5 . First, we see that the epistemic error is very low and quickly converges to 0, i.e., we converge to the best achievable performance within sampling just 100 to 1000 samples on both datasets. The remaining error after that is irreducible. We attribute it primarily caused by generalization gaps in the global permutation matrix P * as better approximations like Recursive Sum ( 3 ) did not improve performance as shown in Fig. 4(c ). This introduces an interesting question: Do models follow a single global ranking order or are they better decomposed into different rank orders?How consistently do models follow one single global ranking order? We present a detailed analysis in Appendix E to verify this. We calculated the cross-correlation matrix for predictions from 167 models across the entire Lifelong-Imagenet benchmark (1.9M test samples). Surprisingly, all model pairs showed positive correlations to varying degrees, with no pairs being anti-correlated. Models with near-zero correlations had near-random performance, indicating uncorrelated predictions due to their randomness. Top-performing models exhibited slightly higher correlations. Overall, there was no clear evidence of model cliques. This analysis strongly suggests that model predictions are highly correlated, justifying our choice of using a single ranking function, but the ranking is simply noisy. 
conclusion: 
 In this work, we address the efficient lifelong evaluation of models.  
initial accuracy predictions: 
 Efficient Model Evaluation 
 
 Appendix: Our framework is domain-agnostic. All our framework requires is an A matrix constructed using any binary metric, with rows representing samples and columns representing evaluated models. We discuss several applications of our framework across a range of metrics:• Language Models: Our framework can be directly applied to multiple-choice question evaluations popular for benchmarking language model evaluations. The metric here is exact match or near-exact match, a binary metric that perfectly aligns with our framework requirements. • Dense Prediction Tasks or Multi-label Classification: For pixel-wise prediction tasks or multi-label classification, our framework can be adapted by flattening the predictions of each sample. In this approach, each sample contributes an array of binary values to the A matrix instead of a single value. Extending the search algorithm is straightforward: if a point is sampled, all associated values are sampled and annotated. • Tasks with Real-valued Predictions: For tasks such as regression or BLEU score evaluations, our framework can be used after applying a thresholding operation, which converts predictions into binary values (above or below the threshold). While this adaptation allows the framework to function, it restricts the output predictions to the binary threshold level.Followup work [3] does extend lifelong benchmarks to evaluating language models and multimodal language models and tackles the unique challenges faced in those cases.In this section, we detail the creation of our two lifelong benchmarks.Considerations. We aim to establish lifelong benchmarking as a standard evaluation protocol in computer vision. To demonstrate this, we considered two popular datasets as our basis: CIFAR10 [54] and ImageNet [23] . We chose them due to (1) their widespread adoption in prior art, (2) the diverse set of models trained on them, and (3) the presence of numerous dataset with the same set of labels, encompassing distribution shifts [8] , temporal variations [80] , and adversarial samples [41] .Note that while our current lifelong benchmarks are based on two datasets, our framework can generally be applied to any broader range of datasets. We describe the precise construction of our datasets below. See Table 1 for key statistics and a detailed breakdown.Lifelong-CIFAR10. We combine 31 domains of different CIFAR10-like datasets comprising samples applied with various synthetic distribution shifts, synthetic samples generated by diffusion models, and samples queried from different search engines using different colors and domains. We deduplicate our dataset to ensure uniqueness and downsample all images to the standard CIFAR10 resolution of 32 × 32. Our final dataset consists of 1.69 million samples.Lifelong-ImageNet. We source our test samples from ImageNet and its corresponding variants. Similar to Lifelong-CIFAR10, our benchmark is designed for increased sample diversity (43 unique domains) while operating on the same ImageNet class set. We include samples sourced from different web-engines and generated using diffusion models. Our final Lifelong-ImageNet contains 1.98 million samples.Table 1 : Overview of our Lifelong Benchmarks. We list the constituent source datasets (deduplicated) and their statistics for constructing our lifelong benchmarks here. Our benchmarks encompass a wide-range of natural and synthetic domains, sources and distribution shifts, making for a comprehensive lifelong testbed. In all our main results using Sort & Search, we use a single ranking order for all new models. A natural question arises: Are all models consistent in their agreement of what is considered a difficult sample, and what is easy? Perhaps, there could be a clique of models that all agree that certain samples are hard, whereas other models that do not-is this the case or is one ranking order truly sufficient?To justify this choice of considering a single ranking order, we run a simple experiment. We compute the cross-correlation matrix between each of the 167 models with each other on the predictions across the entire Lifelong-Imagenet benchmark (1,986,310 test samples) where models are sorted in descending order of accuracy i.e. the highest accuracy model is plotted in the first row/column and the least accurate model is plotted last. Note that the 167 models are extremely distinct in architecture, backbone, training datasets, data augmentation, normalization, and loss functions (see full list in Appendix K). The cross-correlation matrix plot is depicted in Fig. 7(b) .Reading the plot. The colorbar is important here, it ranges from 0 to 1-we implicitly only look at positively correlated models. We verified that all the correlation values were positive by plotting the distribution of correlation values in Fig. 7 (a)-hence, there are no models that are totally anti-correlated with each other. Now, in the correlation matrix, if there exist certain "model cliques"-certain sets of models that are highly correlated with each other and anti-correlated with all others-we would observe disconnected components, systematically isolated squares.Result. From the correlation plot, we do not find any clear evidence of model cliques. The only anomalous entries we could find are low performing models, whose predictions are uncorrelated with all other models as they are random. We observe slightly higher correlations between the top performing models, but note that this is confounded by their high accuracy-if models are highly accurate, their correlations are likely to be higher by chance alone (since there are more ones in the prediction arrays and hence higher chance of intersecting predictions). However, no distinct cliques were found.Therefore, this analysis further gives us a strong indication that model predictions are highly correlated, hence justifying our choice of using a single ranking function.Brief Discussion. While our analysis suggests that model predictions are highly correlated, we point out that this analysis is done for a varied set of models purely for the task of image classification. We do acknowledge that other tasks like retrieval or captioning might yield different correlation structures, such that there might be different model cliques emerging. Such a structure would then potentially impact our Sort algorithm. Hence, while our current results suggest that the sorted order of difficulty generalizes to new incoming models holds fairly robustly, our method might still be sensitive to task deviations, labeling errors etc. We leave a further exploration of this for future work. In all our main results using Sort & Search, we use the mean-absolute-error (MAE) to evaluate the effectiveness of our framework.While MAE serves as a useful proxy metric for algorithm development, it is not a necessary requirement to provide practical applications. In particular, for many use-cases, it is the ranking of the models, rather than their absolute metrics, that are of primary importance for informing downstream decisions about which model to use. To illustrate a practical application, we examine whether Sort & Search preserves the ranking of models at high sampling efficiency. Specifically, we conducted an experiment by changing the evaluation metric from MAE to Spearman correlation between the rankings of 25, 250 models using Sort & Search and the rankings obtained after full sample evaluation on Lifelong-CIFAR10. The results, presented in Fig. 8 , show a consistently high correlation of 0.5. We believe this demonstrates the framework's applicability for practical use-cases.G Does Error Accumulate with Consecutive Additions of New Models/Data?In this section, we argue that the errors should not accumulate with consecutive addition of new models or data. The core intuition lies in the fact that sequential updates to P * t when made with the predicted vector y t+1 will necessarily preserve the same permutation, i.e. P * t+1 = P * t as y t+1 strictly follows P * t itself, adding an error of 0. Detailed Explanation. Considering the case where a new model is presented in which A ∈ {0, 1} |M×|D| where |M| is the number of models and |D| the number of data samples. We solve Equation 1 by alternating the solution between solving for y given the permutation P and P given the prediction y. For ease, and without loss of generality, consider the problem when solving Equation 1 repetitively for a sequence of new samples. A natural question is: Do we need to re-optimize for P t and update A with the new ranked prediction vectors y t for every timestep? ). The core intuition underlying this result is that at the new step t + 1 the vector y * t+1 has a structure of ones followed by zeros ordered according to the optimal permutation P * t+1 that orders samples from "easiest" to "hardest" following the structure in AP * t . Hence, adding it to the sum preserves the ordering of elements (if ties are broken in the manner of the old ordering).Empirical Backing. We conducted experiments by adding new models serially and using the Sort & Search predictions as ground truth for further model additions on Lifelong-ImageNet dataset. The results are presented in the Appendix G. We observe the errors do not accumulate with consecutive additions, exactly the same model order is preserved -confirming our insight empirically.In this section, we expand on the brief literature review from Section 2 for a more expansive coverage of related topics.Comprehensive Benchmarks. Benchmarking has become ubiquitous in the machine learning world in the last few years [72] . It has gained further traction in the recent past with the release of foundation models like GPT-4 [18] and CLIP [71] . A popular direction taken by efforts like GLUE [93] , BigBench [82] , HELM [57] etc., is to have a benchmark of benchmarks, reporting the average accuracy over the constituent datasets. This approach now spans across several domains including fact-based question-answering [40] , language understanding [94] , zero-shot classification of vision-language models [30] , large-scale vision model evaluation [104] , multi-modal model evaluation [102, 108] , and text-to-image generation [5, 56] . Despite these benchmarks having vast coverage of testing concepts, the obvious downsides are two-fold: (1) they are static in nature and hence can always be susceptible to test-set contamination [60] , and (2) their large sizes renders them very expensive to run full model evaluations on.Adversarial Dynamic Benchmarks. One necessary aspect essential for lifelong benchmarks is collecting harder samples, which has been pursued by two strands of works. Adversarial methods to augment benchmarks [92, 63, 51, 70, 81] aim to automatically curate samples that all tested models reliably fail on. These methods usually involve an iterative optimisation procedure to find such adversarial samples. The second strand of work in curating adversarial samples are efforts revolving around red-teaming [31, 66] that aim to explicitly elicit certain sets of behaviours from foundation models; primarily these approaches look at the problem of adversarial benchmarking from a safety perspective. Further, a host of benchmarks that aim to stress-test models are making their way on the horizon-their primary goal is to create test sets for manually discovered failure modes [103, 65, 85, 88, 42, 48, 13, 16] . However, while they are sample efficient, they are criticized as unfair. To mitigate this, a strand of automatic error discovery [19, 27, 99, 68] or their humanin-the-loop variants [97, 24, 32] have been developed. This is complementary to our work, as we primarily explore model testing.Active Testing. Efforts such as [47, 52, 53, 106] aim to identify "high-quality", representative test instances from a large amount of unlabeled data, which can reveal more model failures with less labeling effort. The key assumption underlying these works is that they assume access to a host of unlabeled data at a relatively cheap cost. However, they assume that the cost of label acquisition is a bottleneck. However, these assumptions can break down when doing multiple forward passes on a single batch of data with a large-scale foundation model is necessitated. Albeit similar in spirit to the task of actively acquiring a subset of samples for testing models, an important distinction of our method is that we want to minimise the number of forward-passes through a model-we believe that the cost of running a model on several test samples is substantial, and hence needs to be reduced for efficient evaluation in terms of time, resources and capital.Ideas for Replacing Benchmarks. Recently, there have been a surge of methods introducing creative ways of benchmarking models [58, 76, 49, 33, 75, 77, 61, 44, 17, 86, 64, 34, 76, 75] including hosted competitions [14] , self-supervised evaluation [46] and newer metrics [36] . Further, recently ELO style methods have been gaining a lot of attention [12, 107] due to their scalability of deployment to millions of users in a peer-to-peer manner. The ELO algorithm is used to compute ranks for different models based on human-in-the-loop preferences. However, despite its utility ELO is heavily dependent on the choice of user inputs and can be a very biased estimator of model rankings [79] . Another interesting idea proposed by [20] is to assume access to the pre-training data of models and compute topological maps to give predictions of test error; this however requires running expensive forward passes over the training data or modifying the training protocol, which might be not be scalable to pre-trained models.Computerized Adaptive Testing. Computerized Adaptive Testing (CAT) is a framework that allows for efficient testing of human examinees. The idea is to lower the burden of students taking tests by only asking them a subset of questions from the entire pool. There have been few main directions of solutions: model-agnostic strategies for selection [11] , bi-level optimization [37, 109, 29] , multiobjective optimization [62, 43, 95] , retrieval-augmented adaptive search [100] . One key challenge in CAT is the lack of a stable ground-truth. Since the goal in CAT is to estimate the proficiency of an examinee, and the examinee's true ground-truth proficiency is not provided, how would one evaluate the true proficiency of an examinee? Thereby, existing CAT methods cannot explicitly optimise for predicting ability directly i.e. they cannot do exact ability estimation. Hence, CAT methods are not usually guaranteed to converge to the true examinee abilities under certain conditions. The biggest distinction of our work from CAT is the access to the ground-truth targets for the tasks we consider. In both Lifelong-ImageNet and Lifelong-CIFAR10, we have access to the ground-truth and hence can compute grounded metrics that can be optimised towards, unlike in CAT, where every method has to inherently be label-free.Curriculum Learning. This refers to the problem of finding a curriculum of input samples such that the optimisation objective of an algorithm becomes easier. The most intuitive explanation from curriculum learning comes from how humans learn [50] . In the context of machine learning, the idea behind curriculum learning is to find the "difficulty" of samples, where difficulty is usually defined in terms of the ease of classifying that sample correctly. Some recent works in this direction utilise estimating variance of gradients [1] and other information theoretic properties [26] to estimate sample difficulty. These approaches are complementary to our Sum component in S&S since these can be easily integrated into our framework directly.Theorem. Optimality of Y given P. For any given a i ∈ {0, 1} 1×n and P, DP-Search returns an ordered prediction vector y i ∈ {0, 1} 1×n which is a global minimum of ∥a i Py i ∥ 1 , where being an ordered prediction vector implies that if y j = 1 then y j ′ = 1∀j ′ ≤ j. Moreover, if y j = 0, then y j ′ = 0 ∀j ′ ≥ j.Proof. First, we reduce the problem from Eq. (1) to the following: y ′ * = argmin y ′ ∥a ′ P * -y ′ ∥ if y ′ j = 1, then y ′ j ′ = 1 ∀j ′ ≤ j, and if y ′ j = 0, then y ′ j ′ = 0 ∀j ′ ≥ j.(5)Note that y ′ essentially constructs a vector, y ′ i , of all ones up to some index i with the rest being zero . Let b = a ′ P * be the sorted vector according to the permutation matrix. Thus, the objective function has the following error:EQUATIONObserve that the first term is the number of zeros to the left of index i (inclusive) in b, while the second term is the number of 1s in b to the right of index i.Proposition I.1. If y ′ i is a minimizer to Theorem 4.2, then, the following holds: Proof. Let j < i and that y ′ i and y ′ j are feasible solutions for Theorem 4.2. However, let that y ′ i be such that the inequality in Proposition I.1 while it is not the case for y ′ j . Then, we compare the differences in the objective functions e(y ′ i ) and e(y ′ j ). We have that: The inequality condition in proposition I.1 implies that for the choice of index i, the number of zeros in a to the right of index i is more than the number of 1s to the right of index i. Since any solution y ′ i either satisfies property in Proposition I.1 or not. Moreover, since Proposition I.1 demonstrated that the set of indices that satisfy this property are better, in objective value, than all those that do not satisfy it, then this condition achieves optimality.Although showcasing very promising results in enhancing the efficiency of evaluating models on our large-scale Lifelong Benchmarks, our investigation with S&S leads to some interesting open problems:(1) Ranking Imprecision: Our error decomposition analysis provides convincing evidence (Section 4.5) that the ordering of samples P * while evaluating new models bottlenecks prediction performance. Generalizing from imposing a single sample ordering P * to sample ordering structures, such as different clusters of models each with their or rejection frameworks for models if it does not align with the ordering could dramatically improve the framework.(2) Identifying Difficult Samples: Finding and labeling challenging examples is an essential task for lifelong benchmarks, which is not the focus of our work. Studying hard or adversarial sample selection approaches with lifelong benchmarking is a promising direction. We provide an extensive survey of related approaches in this direction in Appendix H.(3) Scaling up to Foundation Models: Our work mainly tackles lifelong model evaluation under an image classification setting for trained classification models. Despite it being clear that our method should scale to foundation models, since it only relies on the existence of an A matrix, it would be interesting to test it on more benchmarks from the LLM and VLM domain.Given |am+1| = k, one can show the prediction array [1 ⊤ k , 0 ⊤ n-k ] achieves optimal Eagg = 0If a sample xi is more "difficult" than a sample xj then at least equal number of models predict xj correctly as the number of models predicting xi correctly[6].The "compute saved" axis in the plots is computed as n n ′ . Effective compute savings are: In Lifelong-CIFAR10, we do 25, 250×1, 697, 682 evaluations in the full evaluation v/s 25, 250×2, 048 in our evaluation. Similarly, for Lifelong-ImageNet, we perform 117×1, 986, 310 v/s 117×2, 048 evaluations.Recursive sum ( 3 ) is not applicable here as all sum values are unique, see Section 3.3. 


Decision: The authors propose an efficient evaluation framework, Sort & Search (S&S), to reduce the computational cost of evaluating a growing number of models on an ever-expanding sample set. The framework leverages dynamic programming to selectively rank and sub-select test samples, enabling efficient lifelong benchmarking.

Given the overall positive reviews, I recommend accepting the paper.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 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: questions: None
limitations: limitations: Limitations addressed my weaknesses.
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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: 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?
limitations: limitations: Yes
paper_summary: paper_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.
strength_weakness: strength_weakness: 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: 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?
limitations: limitations: Yes, the authors adequately addressed the limitations.
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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: 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)
limitations: limitations: The authors include a limitations section in their manuscript.
paper_summary: paper_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'.
strength_weakness: strength_weakness: See above for strengths and weaknesses.
questions: 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?

&NewLine;  
**Comments:**

- [line 131] What does EM stand for?

&NewLine;  
**[minor comment / observation]**

- [line 110] Typo on operation 2 -- I believe it should be insert_M
limitations: 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?)

Comments: title: Gentle Nudge
Reply
Additional Clarification for Q f)
comment: Thank you for your response.  I echo Reviewer oB2P's opinion and will maintain my current score for the same reasons.
Thank you for your response. Yes, I agree that it is easy to see how this technique could be applied to those consequential problems; that's why I gave a pretty high score to begin with. While I think the paper would have been much more impactful if the technique were demonstrated on these tasks, I think the current version as is already is a solid paper that should be accepted. I will keep my score.
Thank you for the clarifications.
We would really appreciate it if you could have a look at our replies and let us know if you had any further questions/comments. We  highly value your feedback.
> Q b) "To summarize: We use DP-search to compute the matrix Y": Does DP-search give you the global optimum? I mean, if you were to test all models on all samples (and thus knew matrix A unequivocally), would the global optimum be the same as the one computed with DP-search?

Yes, that is correct. DP-Search returns the optimal $\mathbf{Y}^\*$ for the optimization equation in lines 167-169 if we knew matrix $\mathbf{A}$ unequivocally. 

We use precisely this optimal $\mathbf{Y}^\*$ to compute the Aleatoric and Epistemic error discussed in lines 328-332, and results shown in Figure 4. Empirically, we observe that Epistemic error quickly reduces to nearly zero within just 1000 samples.
Thank you for the clarifications.

**Q b)** *"To summarize: We use DP-search to compute the matrix Y"*: Does DP-search give you the global optimum? I mean, if you were to test all models on all samples (and thus knew matrix A unequivocally), would the global optimum be the same as the one computed with DP-search?
Thank you for the detailed response. For the author response of W1 and W2,

W1: As the authors have said, MAE serves as a useful proxy metric for algorithm development. I believe that an efficient testing strategy such as the one proposed by the authors would be mainly utilized for quick probing tests during the development phase of an algorithm, for trial & error. For this purpose, approximating the amount of score improvement could be more meaningful than rankings.

W2: My subjective projection on this matter is that for contemporary foundation models such as LLMs, a new version of an LLM could be trained with different proprietary datasets that boost certain abilities of the model. For instance, if a lifelong dataset measures coding abilities, a novel programming language can be introduced, and certain new LLMs may be prepared for this new language, and vice versa.

However, recognizing the Authors' response and the current scope of discourse, I think that it is not necessary to address such aspects of the problem in a single research stride. I will raise my score.
> Q 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?

Thank you for raising this important point. All our framework requires is an A matrix constructed using any binary metric, with rows representing samples and columns representing evaluated models. In a sense, this is metric agnostic.

We discuss various applications of our framework which use a wide range of metrics:

- **Language Models:** Our framework can be directly applied to multiple-choice language model evaluations where the metric is exact match or near-exact match, a binary metric perfectly suitable to our framework.
- **Dense Prediction Tasks or Multi-label Classification:** For pixel-wise prediction tasks or multi-label classification, our framework can be extended by flattening the predictions of each sample. That is, every sample contributes an array of binary values to the A matrix instead of a single value. The extension to the search algorithm is simple, if it samples a point all associated values are sampled and annotated.
- **Tasks with Real-valued Predictions:** For tasks such as regression or BLEU score evaluations, our framework can operate after applying a thresholding operation. This converts predictions into binary values (above or below the threshold). While this allows the framework to remain valid, it limits the predictions obtained to the binary threshold.
    - A way to extend this would be having multiple thresholds that can enable quantized searching over output values, but this is beyond the current scope of the work. In contrast, the above applications are more straightforward applications of our framework.

We hope this clarifies the adaptability of our framework.