Efficient Lifelong Model Evaluation in an Era of Rapid Progress
Authors: Ameya Prabhu
Vishaal Udandarao
Philip Torr
Matthias Bethge
Adel Bibi
Samuel Albanie
Venue: NeurIPS 2024 poster (2024)
Keywords: benchmarking
efficient model evaluation
Primary area: evaluation
TL;DR: This work addresses the challenge of spiraling evaluation cost through an efficient evaluation framework called Sort & Search (S&S).

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.

Efficient Lifelong Model Evaluation in an Era of Rapid Progress
Ameya Prabhu Vishaal Udandarao" 112
Philip H.S. Torr
Matthias Bethge"!
Adel Bibi
Samuel Albanic
Tübingen Al Center, University of Tübingen University of Cambridge University of Oxford
https://githuu:
http::/ww....oooooooo/////oottaa sears
benchmarks
Abstract
Standardized benchmarks drive progress in machine learning. However, with re- peated testing, the risk of overfitting grows as algorithms over-exploit benchmark idiosyncrasies. In our work, we seek to mitigate this challenge by compiling ever- expanding large-scale benchmarks called Lifelong Benchmarks. These benchmarks introduce a major challenge: the high cost of evaluating a growing number of models across very large sample sets. To address this challenge, introduce an efficient framework for model evaluation, Sort & Search (S&S), which reuses previously evaluated models by leveraging dynamic programming algorithms selectively rank and sub-select test samples. To test our approach at scale, we create Lifelong-CIIANe CIFARIO and Lifelong ImageNet, containing 1.69M and 1.98M test samples for classification. Extensive empirical evaluations across ~31,000 models demonstrate that S&S achieves highly highly-efficient approximate accuracy mea- surement, reducing compute cost from 180 GPU days to 5 GPU hours (~-1000x reduction) single A100 GPU, with low approximation error and memory cost <100MB. Our work also highlights issues with current accuracy prediction metrics, suggesting need to move towards sample-level evaluation metrics. We hope to guide future research by showing our method's bottleneck lies primarily generalizing Sort beyond a single rank order and not in improving Search.
Samples
New Model
Sample Pool
X
subset
size It'
{x, X Sor X.)
m=1
eval on subset
Efficient Model Evaluation
Predictions?
Models
New Sample
Existing Models
0
:
Predictions
select subset
Initial Accuracy Predictions
Efficient Insertion
eval on subset
Figure 1: Efficient Lifelong Model Evaluation. Assume initial pool of n samples and m models evaluated on these samples (left). Our goal is to efficiently evaluate a new model (insert,v) at sub-linear cost (right top) and efficiently insert a new sample into the lifelong benchmark (insertp) by determining sample difficulty at sub-linear cost (right bottom). See Section for more details.
"cqual contribution, i equal supervising
38th Conference on Neural Information Processing Systems (NeurIPS 2024).

---

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 CIFARIO 10 [54] benchmark tested whether classifiers can distinguish between 10 categories. such as dogs and cats. Subsequent versions like CIFARIO. [59], CIFARIO. 10.2 [59], CINICIO [21], and CIFARIO-N 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 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 approaches must compete with a body of methods that have been highly tuned to such benchmarks, incentivising further overfitting if they
whole [28, 90]. Fresh
compete [9, 10].
One approach to preventing models from overfitting to biases [87, 3] 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 example, takes roughly 140 and 40 GPU days respectively to evaluate our current model set on our Sefelong-CIFARIE and safelong-Imageeee datasets (containing 31,000 and 167 models respectively). These issues 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 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-gren grer-ggowing collection of test samples [78, 22]. Hence. we primarily ask: Can 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 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 subset of samples to evaluate models. We propose a method, Sort & Search (S&S), which reuses past model evaluations
sample set through dynamic programming 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 single A 100 GPU. We achieve x000x reduction in inference costs compared to static evaluation on all samples, reducing over 99.9 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-CIFARIO and Lifelong-ImageNett, consisting of 1. 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 sub- components (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.
2 Lifelong Model Evaluation: Formulation and Challenges
We first formalise evaluation in lifelong model evaluation and describe the key challenges it raises.

---

Formulation. Let D=((21.31) ui)...., (Iz, Br)) denote an ordered collection of labeled examples, sampled from the underlying task distribution of interest P(Xx Here, T'EX denotes the 7th data sample and y denotes the corresponding label. Let M- fm) denote an ordered collection of models where each model, f:X'+)' maps data samples to predicted labels. Lifelong benchmark, (D, insertp, insert,,, M. metrics), augments 'D and M with three operations: ansertp((a',00 , inserts new labeled example (z', .y) into D. (n")rtM((") inserts a new model f' into M.
metrics() returns a -imdeninsoo vector estimating each model's performance.
Key challenges. When new models are proposed, the set M expands over time. Similarly, the sample collection, DD expands as new evaluation datasets get proposed to test various aspects of the problem and resist overfitting. The key question becomes: How to efficiently update the benchmark? We can instantiate a "naive" implementation of the metrics() operation or insertp
by simply re-evaluating
However, such strategy exhibits ((D) runtime complexity for each call to metrics(), rendering lifelong model evaluation practically infeasible as 'D and M grow. The central question considered by this work is therefore the following: Given lifelong benchmark B, how can we efficiently compute metrica() each time we insert new labeled samples into D or new models into M
every model on every sample after each call to insert,
Inserting Am models insert,M) Suppose that Am new models have just been released. We wish to insert these new models into M and efficiently predict performance of these new models. A naive approach would entail evaluating the Am models on all [D] samples. Our first challenge is: Can we instead generate the prediction matrix by performing inference only on small subset of n' < [D] samples? We want to enable accurate prediction of the remaining entries in the prediction matrix.
Inserting An samples insertp). Our second challenge arises when we obtain new An 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 An new examples. As above, to substantially reduce cost, we select a small subset of mn' < [M] models with the objective of accurately predicting the remaining entries of the prediction matrix corresponding to the new An samples.
Approach. Our approach is characterized by two key ideas. First, we augment B with instance- level accuracy cache to amortise inference costs across evaluations. The cache is instantiated as a matrix A E {0, 1] [[IM (P) where A (i,j) A [[f((z;) = M/]- Second, we propose strategies to efficiently generate the prediction matrix Y E {o. 10.1) M| 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,
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. Concurrent to our work, Anchor Point Sampling [91] and IRT- 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., ( requiring well over 10TB of RAM for benchmarks having 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.
3

---

2.1 Why Adopt Sample-wise Prediction Metries instead of Overall Accuracy Prediction?
Given model predictions Ym+1 and ground-truth predictions am-11 current methods typically mea- sures whether one predict the average accuracy over the full test, measured by mean absolute difference of aggregate accuracies Engg (m++1, 4m+ = ([Y=+1l-lmm++ Dl/+ We argue this is highly unreliable minimizing the metric only requires predicting the count of 1s in the prediction array rather than correctly predicting on sample level. For instance, consider a ground-truth prediction array of [0,0,0,1,111] JJ. A method that predicts [1,1,1.0,0.0] as the estimated prediction array achieves optimal Fagg of O despite not predicting even a single sample prediction correctly! More generally, is always possible to obtain globally optimal Eugg of O while having worst-case ween-ubs error E for any ground truth accuracy am-1- Formally,
Theorem 2.1. Given any ground-truth vector am+1, it is possible to construct prediction vector ym++1 such that Bagg (Y m1, am+1) = 0 and 11 mm+1) 2.min(1 - (Bm 1mm411/n, [Bm41l/n)
One might wonder whether these worst case bounds ever occur in practice. We empirically test simple yet optimal array construction, given with oracle ground-truth dataset-level accuracy of k2, which achieves Eage = 0, and consistently observe high mean-absolute eπror E of 0.4-0.5 on sample level on our lifelong benchmarks (n=~100)) i.e., the model incorrectly predicts 40-50% of the samples in binary classification task, which is surprisingly high. In comparison, our S&S method, without any oracle access, gets 0.15-0.17 mean-absolute error with just n'=100 samples (at 10, 000x compute saving) on the same benchmarks. Overall. this demonstrates that thoughtful sample-level prediction mechanisms are necessary for efficient lifelong evaluation.
3 Sort & Search: Enabling Efficient Lifelong Model Evaluation
Inspired by CAT [89], we propose an efficient lifelong evaluation framework, Sort Search (S&S), comprising two components: (1) Ranking test samples from the entire dataset pool according to their difficulty", i.e., Sort and (2) Sampling subset from the pool to test on, i.e. Search. This framework effectively tackles the two key operations noted in Section 2 Oinsert and insert,.).
We first describe our Sort and Search method in the case when new models are added insert,y). and subsequently show that the same procedure applies when we have new incoming samples insertp)) simply by transposing the cache (A A²). A full schematic of our pipeline is depicted in Fig.
3.1 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 cache A {0, 1) 1mmxx (see
Fig. 1 left). We can decompose the cache row-wise corresponding to each model fú, i E {1. (1.... m
obtaining the binary accuracy prediction across the samples, denoted by a, [pr1 P:2 ..... Pinl- Here, Piy 5 (0, 1} represents whether the model fr classified the sample z, 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 E {0, 1)mxm, binary matrix, such that APP permutes the columns of so that we can rank samples from easy (all 1s across models) to hard (all Os across all models). We say this has a minimum distance from the optimal ranked accuracy prediction matrix Y (0, 1 f computed by the hamming distance between them, posed as solving the following problem:
P Y argmin p. x | YII,,
s.t. P E [0,1)"XM, PI, = In, 1 1
(1)
Y, 1, then Y, 1 Vj <
if Y, = 0. then Y. Vj 2j.
"Given |m = k. one can show the prediction array [1, o.T,, achieves optimal Engg "If a sample x; is more "difficult" than a sample 2; then at least equal number of models predict 2, correctly the number of models predicting correctly [6].

---

Sort (sec 3.1)
&
Search (sec 3.2)
Samples
New Model f +
pm
App
Prediction vector ym-1
1
0
Models
0
Sub-task 1: Sampling (sec 3.2.1)
p
Neg
Xg
uittern samplig
Azy
Sampled data points
Sule-rakk Expansion (see 3.2.1
A
Xg
...
Desearch extrppaation
p
Sampled data points
Prediction vector Ym-1
Ordering samples
easlest to hardest (see 3.1.2)
Full Pipeline of Sort & Search. For efficiently evaluating new models, (Left) first sort all data samples by difficulty (refer Section 3.1) I) and (Right) then perform 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).
Figure 2:
By definition of permutation matrix, the constraints P1, 1,, 1 = 1, 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 minimized.
We next discuss how to solve this optimization. While the goal is finding the optimal permutation P we still need jointly solve for P, Y here. We find solution by alternating between optimizing P keeping Y constant and optimizing Y keeping P constant, with the goal of finding the best P with coordinate descent algorithm. We present algorithms for optimizing the two subproblems.
3.1.1 Optimizing P Given Y
We know P is binary from Eq. (1). Hence, finding the optimal P is NP-Hard [101]. To simplify the sub- sub-problem, we first present an algorithm solve the case where we can order samples in strictly decreasing order of difficulty, measured by how many models classified it correctly 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 alternative explore removes the introduced constraint of strictly decreasing order
However,
). A third
Sorting by Sum. We discuss how order samples if they follow strictly decreasing order of difficulty. We can order samples in decreasing order of difficulty by a simple algorithm detailed in Listing (sort_bo b___ (as_sssmminntttiee 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 converted to the permutation matrix P*).
However, the assumption of strietly decreasing order of difficulty is unrealistic 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 (a) Converting the cache (A) to store confidence predictions of ground truth class
by two methods:
rather than accuracy (Algorithm ) or (b) Iteratively optimizing rows which are tied in sum values (Algorithm 3 Note that we find Sorting by Sum effective in all our tested scenarios, but provide these alternatives the case where it is insufficient.
Sorting by Confidence Sum. One method to have a strictly decreasing order is to relax the constraint on the samples of a, [Pt. ..... ..... Pin] from Pij E {0, to Psj E [0, 1), and use confidence of the ground truth class. This modification allows 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.
examples to be unique. The
Recursive Sorting by Sum. Another alternative is relaxing the equal difficulty assumption in Algorithm 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 is?
5

---

We propose an iterative solution: at each step, order samples of equal difficulty by alternatively optimizing P keeping Y constant by applying Algorithm and optimizing Y keeping P constant by DP-Search algorithm (presented in the next Section). We provide the algorithm for two iterations Stage_ssort_ael
for an illustration in Listing solution at each recursion depth. Note that ties are broken by preferring the model which minimizes error the most.
Note that this strictly improves the
3.1.2 Optimizing Y given a P
Optimizing Y given P. is equivalent to finding row-wise threshold & S. minimizing the error with the matrix AP for given P. Intuitively, if the threshold for the j"h row is k, then the j row is of the form [1g o,_ In every row, ni where 1; is vector of all ones of size k and On-k is zero vector of size samples before the row-wise threshold l 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, De-Schhch which operates on each row ys. detailed in Listing 1 (dp_search). Given row in Y. DP-Search computes the difference between number of is and number of Os for each index. By using a prefix sum structure. for an input of size n, the DP approach reduces time complexity from O(n") ) to On)). The optimal threshold is the index of the maximum value in this vector. The vector y, is simply [ O -T-p]] k. DP- DP-Search is
k.
where 1, is vector of all ones of size l and 0,, is zero vector of size guaranteed to return the globally optimal solution:
Theorem 3.1. Optimality of Y given P. For any given a, {0, 1 and P. DP- returns an ordered prediction vector y; E {0, 1 11 which is a global minimum of a yellı.
Applying DP-Search independently row-wise, the algorithm returns the optimal Y given P. Now, we shall
3.1.3 Process Summary
We have outlined the process of optimizing (i) Pgiven Y and (ii) Y given P. Note that (i) alone suffices for Sorting Operation when using the Sorting by Sum algorithm, while a combination of (i) and (ii) is primarily needed for 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.
3.2 Efficient Selection by Search
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, Am. Recall that AP" represents the columns of cache A, ordered by sample difficulty (those most often misclassified by models). Given Am new models, our goal is to predict accuracy across all samples for each model, i.e., the accuracy matrix YAm E {0, 1m This would be simple if we could evaluate all Am models on all n samples, but this approach is costly. The challenge is thus to predict performance 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 ym+1? ? We use the ground truth vector am+1 for evaluating the efficacy of our method.
the remaining samples
Recall that evaluation of every new model can be done independently of others, i.c. Yam is separable per row. Hence, we describe the problem for the first new model ym+1 E 10 here.
(i) How to get the optimal ym+1 ? Our goal here is to generate the sample-wise prediction vector Vm+1 E {0, 1] 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
am E 13 1xn' how to generate the prediction vector ym+1 E {0. 1)1m.
Subtask 1: How to Select Samples? We want to find the best r'' observations forming a'. Note that any ranked solution we obtain using this vector needs to be interpolated from n' points to points- we 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 threshold predicted by our set of n', i..,, sample n' points uniformly, providing the algorithm in Listing (uniform, aemiffrr_ssamplao -mmpsmmmmmln)... We also compare empirically with a pure random sampling approach in Section 4.

---

Subtask 2: Optimizing Mm+11 Given the n' observations a E {0, {0,1} how to generate the prediction vector Ym+1 E {0, 1xn2? We use the threshold given by DP-Search (Listing 1) and obtain the threshold, given in terms of fraction of samples in |a I- We extrapolate this threshold from n' to points, to obtain the threshold for the prediction vector Ym+1- Mm+1 is simply [1] O where 1 a vector of all ones of size and - a zero vector of size n k.
So far, we have only discussed evaluation of Am models insertm). How can also efficiently extend the benchmark i.e. efficiently adding An new samples Dinsertp)?
3.3 Efficient Insertion of New Samples (insertp)
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 TP, which would sort models, instead of samples, based on their aggregate sum over samples (i.e., accuracy) optimized using Algorithm to obtain Pt, ordering the models from classifying least samples correctly to most samples correctly. Here, Algorithm is sufficient, without needing to solve the joint optimization (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 An, we similarly would treat every sample independently and optimize the predicted array y using Efficient Selection by Search (Section 3.2).
because accuracies
4 Experiments
To validate Sort & Search empirically, we showcase experiments on two tasks: efficient estima- tion of new sample difficulties (insertp) and efficient performance evaluation of new models (i We then comprehensively analyse various design choices within our S&S framework.
4.1 Experimental Details
Lifelong-Datasees. 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 CIFARIO. We deduplicate our dataset and downsample images to 32x Our final dataset consists of 1.69M samples. Similarly, we source test samples from ImageNet and corresponding variants to form Lifelong--laggene 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--mageeNer contains 1. 1.98M samples (see full list of dataset breakdown in Appendix C).
Lifelong-CIFARIO
Model Space. For Lifelong- CIFARIO, we use 31, 250 CIFAR-10 10 pre-trained models from the Effelong-CIFAR10, TeTS--Bencc-TTpolggeee search space [25]. For difelong-ImageNer we use 167 ImageNet- K and ImageNet-21I pre-trained models, sourced primarily from timm [98] and imagenet- [84].
Sample Addition Split insertp). To study efficient estimation of new sample difficulties on Sifelong-CIFARII we hold-out CIFAR-1OW [83] samples for evaluation (~5000, 000 samples) and use the rest 1.2 million samples for sorting. We do not perform experiments for Lifelonn-hmaggner since the number of models is quite small (167 in total), directly evaluating all models is relatively efficient, as opposed the more challenging Lifelong-CIFARI where evaluation on 31, 250 models is expensive, practically necessitating reducing the number of models evaluated per new sample.
Model Evaluation Split insert,) To study efficient evaluation of new models, we split the model set for the Lifelong- Lifelong-CIFARIO CIFARIO benchmark into 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-Imagenn use 50 random models for ordering samples and evaluate on 1 117 models.
7

---

Compute 10'
Compute Saved
10%
Saved
0.21
0.13
Semtidearch (rees)
1.30
Meen Eeron
Mean Abs. Brror
Exponersialdeeco fit: 2=00.6 - 0,07 exp(d.
Esponentia filt E-
0.30
2.16
0.13 0.00 expe 0.00el)
0.30
0.15
0.77
0.14
0.3
0:36
10
10
10 10
10-
Sampling Budget 'n'
Sampling Budget o
Sampling Budget n
(a) Lifelong-CIFan CIFARIO
(b) Lifelong-ImageNee
(c) Baseline Comparison
Figure 3: Main Results. (a,b) We achieve 99% cost-savings for new model evaluation on Lifelong- showcasing the efficiency (MAE decays exponentially with n') of
ImageNet and Lifelong-CIral SSarhh. (c) S&S more efficient and accurate compared to the baseline on
Metries metrics()). We measure errors between estimated predictions for each new model ym+1 and ground-truth predictions am+1 using mean-absolute error (MAE): ((am+1:y+11))
E (:am+1:ymtll Vm+1) = |am+ -ym+s
4.2 Results: Sample-Level Model Performance Estimation (insert.y)
We evaluate the predictive power of S&S for evaluating new models when subjected varying sampling budgets n' i.e. we run our S&5 over 13 different sampling budgets: (8. 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768) on both Lifelong--mageeNe and (ffelong-CIFARIOO
Our main results in Sections 4.2 and 4.3 use Sorting by Sum (0) foor obtaining P and uniform sampling for the sample budget n'. Using this configuration, we now present our main results.
Key Result 1: Extreme Cost-Efficiency, From Figs. 3(a) and 3(b), we note our approach converges to very low -bbouua 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)*.
Key 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. 3(a) and 3(b). The exponential decay takes the form E=ae bz +c. The fitted curves have large exponential coefficients b of 0.04 and 0.02. This further shows the surprisingly high sample-efficiency obtained by S&S.
Key Result 3: Outperforming Baselines by Large Margins. We construct a competitive, scalable version of Vivek et al. [91] as baseline, called & It first samples nı' points out of n (similar to S&S without sorting), and then expands the n' nisiz prediction array to n samples by copying the rest n 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 sampling budget of =8181 compared to the baseline, meaning that on average, our S&S correctly classifies ~99 more samples.
2) Faster convergence: S&S converges much faster than the baseline (at n1=1,022 vs. n'=32, 768) thereby showcasing the high degree of sample efficiency in converging the minimal error.
3) Consistent:
Fig. 4(b) shows the better consistency of S&S, across wider range of models used for Sort-at at n' 512 S&S with only 10 mort- still outperforms the baseline using 50 Sort-models.
Storage Efficiency. Storage Efficiency. Our method (S&S) achieves high storage efficiency, requiring only two ID 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 Copy Exarettedxtt but is also far more memory-optimizze
"The "compute saved" axis in the plots is computed as =. Effective compute savings are: In Lifelong- CIFARIO, we do 25, 250x1, 1, 697, 682 evaluations in the full evaluation v/s 25, 250 048 in our evaluation. Similarly, for Lifelong ImageNet, perform 117x1. 986, 310 v/s 117x2, 048 evaluations.

---

Congutti
0.27
200
Xous Abs. BIEo
Condam
Mous Abs. BITOR
2.3
6.14
Sangling Budget
Sampling Budges
Sumpling Budgett
Sampling Budget
(a) Sample Difficulty
(h) #Ranking modely
(c) Reanking methods
(d) Sampling methods
Figure 4: (a) We achieve accurate sample difficulty estimates on (ifelong-CIFAREE (<0.15 MAE) at fraction of the total number of models to be evaluated, thereby enabling cost-efficient sample insertion. (b,c,d), We analyse three design choices for better understanding S&S, using tifelong-Imagenee
4.3 Results: Sample Difficulty Estimation (insertp)
We next showcase results for the task 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-CIFAN 10, with two different methods for ranking models", Sorting by Sum
and Sorting by Confidence Sum ). 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), observe that both methods converge quickly-Sorting by Sum reaches an MAE 0.15 by only evaluating on m'=64 models out of 31, 250 (10* x computation savings). This demonstrates our method's ability to efficiently determine sample difficulty, enabling efficient insertion back into the dffelong-benchnen pool.
4.4 Breaking down Sort & Search
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 (ie., m) on the final performance on ffelong-Imagehhe Using more models improves MAE- using lesser models for ranking (m=100 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' 22 048)), but rather only on the MAE achieved.
Different Sorting Methods. We compare the three different algorithms on
Sorting by Sum, Sorting by Confidence Sum, and 3 Sorting by Recursive Sum. From Fig. 4(c), 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 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
is unable to account for.
Different Sampling Methods. In Fig. 4(d), we compare methods used for sub-selecting the data- samples 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 small (5% lower MAE at n'=8))this can be attributed to its "diversity-secking" 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.
4.5 Decomposing the Errors of S&SS
Here, showcase decomposition of the errors of Sort & Search. Specifically, the total mean absolute error E Ea can be decomposed into a component irreducible by further sampling, referred to as the Alcatoric Sampling Error (Ealentoric), and component which can be improved by querying larger fraction of samples n', referred to the Epistemic Sampling Error (Fepistemic).
Aleatoric Sampling Error. Let y y' when ní = n, i.e., it is the best prediction obtainable have access the full am4 vector. However, some error
across all subsampled thresholds, remains between y" and am-+1 due to the ordering operation (i.e., Sort). This error, caused by errors
Recursive not applicable here all values unique, see Section 3.3.

---

0.4
Lefetong CHEARIO
Laliu Mey
0.4
Liflong-Immgeeee
0.3
Pyi mer Fooe
0.3
Mron Abc. Erorr
Mos Eroir
0.1
0.1
0.0
10
105
10
10-
Sampling Busdgett
Sampling Budgot
Figure 5: Error Decomposition Analysis Lifelong-CIFARII (left) and Lifelong-ImageNNet
(right). We observe that epistemic error (solid line) drops to O 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 (Alcatoric). 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:
Esleatoric (aalentoric(amm+ (am+11 1m++1) = min |am+1P -m 11 = |am+1 P - ym+tll-
(3)
Mm+1
Epistemic Sampling Error. Contrarily, there is gap between optimal ranking prediction ym+1 and Ym+1 with the current sample size n'. This gap, Epistemic Sampling Error, is formally defined as:
Expistemic (y 1m+1.80 1m+1+mm+)) Vm+1) = lly 1 Ym+1ll-
Results. We analyse sampling effectiveness in Lifelong CIFAR-IO and Effelong-ImageNe by studying the Epistemic Sampling Error (Eepiseemic) and Alcatoric Sampling Error (Esteatoric) in Figure 5. First, we see that the epistemic error is very low and quickly converges to 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 did not improve performance as shown in Fig. 4(c). This introduces an interesting question: Do models follow a single global ranking order are they better decomposed into different rank orders?
How consistently 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-Imagern pairs showed positive correlations to varying degrees, with 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 single ranking function, but the ranking is simply noisy.
benchmark (1.9M test samples). Surprisingly, all model
5 Conclusion
In this work, we address the efficient lifelong evaluation of models. To mitigate the rising evaluation costs on large-scale benchmarks, we proposed an efficient framework called Sort & Search, which leverages previous model predictions rank and selectively evaluate test samples. Our extensive experiments, involving over 31 ,,000 models, demonstrate that our method reduces evaluation costs by 1000x (over 99.9%) with minimal impact on estimated performance for Sort & Search to inspire the development of more robust and efficient evaluation methods. Our findings show that model predictions are highly correlated, supporting function, though the ranking is somewhat noisy. Our analysis of Sort & Search suggests that future research should focus generalizing beyond single rank ordering, rather than on better sampling strategies. Overall, we hope Sort & Search enables large reductions in model evaluation cost and provides promising avenues for future work in lifelong model evaluation.
sample-level. We aim
use of a single ranking
10

---

Acknowledgements
The authors would like to thank (in alphahetic order): Bruno Andreis, Çağatay Yıldız, Fabio Pizzati, Federico D' Agostino, Ori Press, Shashwat Goel, and Shyamgopal Karthik for helpful feedback. AP funded by Meta AI Grant No. DFRO5540. VU thanks the International Max Planck Research School for Intelligent Systems (IMPRS-IS) and the European Laboratory for Learning and Intelligent Systems (ELLIS) PhD program for support. VU was supported by a Google PhD Fellowship in Machine Intelligence. PT thanks the Royal Academy of Engineering for their support. AB acknowledges the funding from the KAUST Office of Sponsored Research (OSR-CRG2021-464)) and the support from Google Cloud through the Google Gemma 2 Academic Program GCP Credit Award. SA is supported by Newton Trust Grant. MB acknowledges financial support via the Open Philantropy Foundation funded by the Good Ventures Foundation. This work was supported by the German Research Foundation (DFG): SFB 1 1233, Robust Vision: Inference Principles and Neural Mechanisms, TP4, project number: 276693517 and the UKRI grant: Turing Al Fellowship EP/W002981/1. MB is member of the Machine Learning Cluster of Excellence, funded by the Deutsche Forschungseeminnshaatt (DFG, German Research Foundation) under Germany's 's Excellence Strategy EXC number 2064/1 Project number 390727645.
References
[1] Chirag Agarwal, Daniel D' D'souza, and Sara Hooker. Estimating example difficulty using variance of gradients. In Conference on Computer Vision and Puttern Recognition (CVPR). 2022.
[2] Miklós Ajtai. The complexity of the pigeonhole principle. Combinatorica, 14:417-433, 1994.
[3] Anonymous, Democratizing evaluation with infinity- bennit-bennemmars:: Sample-level heterogencous test- ing over arbitrary capabilities. In Submitted The Thirteenth International Conference on Learning Representations, 2024. URL https: / /ptn//veeeeeeeeeeeeeeeeeeee net/ httt///orodddddiiiieeee DJVLLD.. under review.
[4] Frank B Baker. The basics of item response theory. ERIC, 2001.
[5] Eslam Mohamed Bakr, Pengzhan Sun, Xiaogian Shen, Faizan Farooq Khan, Li Erran Li, and Mohamed Elhoseiny. Hrs-bench: Holistic, reliable and scalable benchmark for text-to-image models. In International Conference Computer Vision (ICCV), 2023.
[6] Robert Baldock, Hartmut Maennel, and Behnam Neyshabur. Deep learning through the lens of example difficulty. Conference on Neural Information Processing Systems (NeurlPS), 2021.
[7] Hritik Bansal and Aditya Grover. Leaving reality to imagination: Robust classification via generated datasets. International Conference on Learning Representations Workshop (ICLR- W), 2023.
[8] Andrei Barbu, David Mayo, Julian Alverio, William Luo, Christopher Wang. Dan Gutfreund, Josh Tenenbaum, and Boris Katz. Objectnet: A large-scale bias-controlled datasct for pushing the limits of object recognition models. Conference on Neural Information Processing Systems (NeurIPS), 2019.
[9] Emily M Bender, Timnit Gebru, Angelina McMillan- McMillan-Major, and Shmargaret Shmitchell. On the dangers of stochastic parrots: Can language models be too big? In Conference on Fairness, Accountability, and Transparency (FAccT), 2021.
[10] Lucas Beyer, Olivier Hénaff, Alexander Kolesnikov, Xiaohua Zhai, and Aäron van den Oord. Are we done with imagenet? In Conference on Neural Information Processing Systems (NeurIPS), 2021.
[11] Haoyang Bi, Haiping Ma, Zhenya Huang, Yu Yin, Qi Liu, Enhong Chen, Su, and Shijin Wang. Quality meets diversily: A model-agnostic framework for computerized adaptive testing. In International Conference on Data Mining (ICDM), 2020.
[12] Yonatan Bitton, Hritik Bansal, Jack Hessel, Rulin Shao, Wanrong Zhu, Anas Awadalla, Josh Gardner, Rohan Taori, and Ludwig Schimdt. Visit-bench: A benchmark for vision-language instruction following inspired by real-world use. Conference on Neural Information Processing Systems (NeurIPS), 2023.
[13] Nitzan Gitton-Guetta. Yonatan Bitton, Jack Hessel, Ludwig Schmidt, Yuval Elovici, Gabriel Stanovsky, and Roy Schwartz. Breaking common sense: Whoops! a vision-and-languaar henchmark of synthetic and compositional images. In Proceedings of the IEFF/CVF International Conference on Computer Vision, pages 2616-2627, 2023.
[14] Avrim Blum and Moritz Hardt. The ladder: A reliable lcaderboard for machine learning competitions. In International Conference Machine Learning (ICML), 2015.
[15] Rishi Bommasani, Drew A Hudson, Ehsan Adeli, Russ Altman, Simran Arora, Sydney von Arx, Michael S Bernstein, Jeannette Bohg, Antoine Bosselut, Emma Brunskill, et al. On the opportunities and risks of foundation models. arXiv preprint arXiv:2108. 072588 2021.

---

[16] Florian Bordes, Shashank Shekhar. Mark Ibrahim, Diane Bouchacourt, Pascal Vincent, and Ari S Morcos. Pug: Photoreatistic and semantically controllable synthetic data for representation learning. arXiv preprint arXiv:2308.00 000.:2370..37777,, 2023.
[17] Samuel R Bowman and George E Dahl. What will it take to fix benchmarking in natural language understanding? In North American Chapter of the Association for Computational Linguistics (NAACL). 2021.
[18] Sébastien Bubeck, Varun Chandrasekaran, Ronen Eldan, Johannes Gehrke, Eric Horvitz, Ece Kamar, Peter Lec, Yin Tat Lec, Yuanzhi Li, Scott Lundberg, et al. Sparks of artificial general intelligence: Early experiments with gpt-4. arXiv preprint arXiv:2.03.. 127112, 2023.
[19] Muxi Chen, Yu Li, and Qiang Xu. Hibug: On buman-interppetabl model debug. In Conference Neural Information Processing Systems (NeurIPS), 2023.
[20] Ciprian A Corneanu, Sergio Escalera, and Aleix M Martinez. Computing the testing error without a testing set. In Conference on Computer Vision and Pattern Recognition (CVPR), 2020.
[21] Lake N Darlow, Elliot J Crowley, Antreas Antoniou, and Amos J Storkey. Cinic-10 is not imagenet or 10.ar-10. arXiv preprint arXiv:
2018.
[22] Mostafa Dehghani, Anurag Amna, Lucas Beyer, Ashish Vaswani, and Yi Tay. The efficiency misnomer. arXiv preprint arXiv:21 2021.
[23] Jia Deng, Wei Dong, Richard Socher, Li-Jia Li, Kai Li, and Li Fei-Fei. Imagenet: large-scale hierarchical image datahase. In Conference on Computer Vision and Pottern Recognition (CVPR), 2009.
[24] Greg d'Eon, Jason d' Eon, James R Wright, and Kevin Leyton-Brown. Brown, The spotlight: A general method for discovering systematic errors in deep learning models. In Conference on Fairness, Accountabiliry, and Transparency (FAceT), 2022.
[25] Xuanyi Dong. Lu Liu, Katarzyna Musial, and Bogdan Gabrys. Nats- bench: Benchmarking nas algorithms for architecture topology and size. Transactions on Pattern Analysis and Machine Intelligence (TPAMI), 1021.
[26] Kawin Ethayarajh, Yejin Choi, and Swabha Swayamdipta. Understanding dataset difficulty with v-usable information. In International Conference on Machine Learning (ICML). 2022.
[27] Sabri Eyuboglu. Maya Varma. Khaled Saab, Bean-Benoit Delbrouck. Christopher Lee- Lee-Messer, Jared Dunnmon, James Zou, and Christopher Ré. Domino: Discovering systematic errors with mooal embeddings. International Conference Learning Representations (ICLR), 2022.
[28] Alex Fang. Simon Kornblith, and Ludwig Schmidt. Does progress on imagenet transfer to real-world datasets? In Conference on Newral Information Processing Systems (NeurIPS), 2023.
[29] Wanyong Feng. Aritra Ghosh, Stephen Sireci, and Andrew Lan. Balancing test accuracy and security in computerized adaptive testing. International Conference on Artificial Intelligence in Education (AIED), 2023.
[30] Samir Yitzhak Gadre, Gabriel Ilharco, Alex Fang. Jonathan Hayase, Georgios Smymis, Thao Nguyen, Ryan Marten, Mitchell Wortsman, Dhruba Ghosh, Jieyu Zhang, et al. Datacomp: In search of the next generation of multimodal datasets. In Conference Neural Information Processing Systems (NeurIPS). 2023.
[31] Deep Ganguli, Liane Lovitt, Jackson Kernion, Amanda Askell, Yuntao Bai, Saurav Kadavath, Ben Mann, Ethan Perez, Nicholas Schiefer, Kamal Ndousse, et al. Red teaming language models to reduce harms: Methods, scaling behaviors, and lessons learned. arXiv preprint 22X::22209.0785 2022.
[32] Trena Gao, Gabriel Ilharco, Scott I Lundherg, and Marco Tulio Ribeiro. Adaptive testing of computer vision models. In International Conference on Computer Vision (ICCV), 2023.
[33] Matt Gardner, Yoav Artzi, Victoria Basmova, Jonathan Berant, Ben Bogin, Sihao Chen, Pradcep Dasigi, Dheeru Dua, Yanai Elazar, Ananth Gottumukkala, et al. Evaluating models' local decision boundaries via contrast sets Conference on Empirical Methods in Natural Language Processing (EMNLP), 2020.
[34] Quentin Garrido, Randall Balcstriero, Luurent Najman, and Yann Lecun. Rankme: Assessing the downstream performance of pretrained self-super representations by their rank. In International Conference on Machine Learning (ICML), 2023.
[35] Robert Geirhos, Patricia Rubisch, Claudio Michaelis, Mathhis Bethge, Felix A Wichmann, and Wieland Brendel. imagenet-trainee cnns are biased towards texture; increasing shape bias improves accuracy and rohustness. In International Conference on Learning Representations (ICIR),, 2018.
[36] Robert Geirhos, Kristof Meding, and Felix A Wichmann. Beyond accuracy: quantifying trial-by-trial behaviour of cnns and humans by mcasuring error consistency. Conference on Neural Information Processing Systems (NeurIPS), 2020.
[37] Aritra Ghosh and Andrew Lan. Bobcat: Bilevel optimization based computerized adaptive testing. International Joint Conference on Artificial Intelligence (IJCAI), 2021.
12

---

[38] Dan Hendrycks and Thomas Dietterich. Benchmarking neural network robustness to common corruptions and perturbations. International Conference Learning Representations (ICLR), 2019.
[39] Dan Hendrycks, Steven Basart, Norman Mu, Saurav Kadavath, Frank Wang, Evan Dorundo, Rahul Desai, Tyler Zhu, Samyak Parajuli, Mike Guo, al. The many faces of robustness: A critical analysis of out-of-distributiio generalization. In International Conference on Computer Vision (ICCV), 2021.
[40] Dan Hendrycks, Collin Burns, Steven Basart, Andy Zou, Mantas Mazeika, Dawn Song, and Jacob Steinhardt. Measuring massive multitask language understanding. International Conference on Learning Representations (ICLR), 2021.
[41] Dan Hendryeks, Kevin Zhao, Steven Basart, Jacob Steinhardt, and Dawn Song. Natural adversarial examples. In Conference Computer Vision and Puttern Recognition (CVPR), 2021.
[42] Cheng- Yu Hsieh, Jieyu Zhang, Zixian Ma, Aniruddha Kembhavi, and Ranjay Krishna. Sugarcrepe: Fixing hackable benchmarks for vision-language compositionality. arXiv preprint arXiv:2306.14610. 2023.
[43] Zhenya Huang, Qi Liu, Chengxiang Zhai, Yu Yin, Enhong Chen, Weibo Gao, and Guoping Hu. Exploring multi-objective exercise recommendations in online education systems. In International Conference on Information and Knowledge Management (CIKM), 2019.
[44] Ben Hutchinson, Negar Rostamzadeh, Christina Greer, Katherine Heller,, and Vinodkumar Prabhakaran. Evaluation gaps in machine learning practice. Conference on Fairness, Accountability, and Trans- parency (FAccT), 2022.
[45] Régis Pierrard Ilyas Moutawwakil. LIm-perf leaderboard. http:://huugghhgfccc...//sss -eade---aadrbbbardd. 2023.
[46] Neel Jain, Khalid Saifullah, Yuxin Wen, John Kirchenhauer, Manli Shu, Aniruddha Saha, Micah Gold- blum, Jonas Geiping, and Tom Goldstein. Bring your own data! self-supervised evaluation for large language models. arXiv preprint arXiv:2306. 1,651, 2023.
[47] Disi Ji, Robert L Logan, Padhraic Smyth, and Mark Steyvers. Active bayesian assessment of black-box classifiers. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 7935-7944, 2021.
[48] Amita Kamath, Jack Hessel, and Kai-Wei Chang. Text encoders are performance bottlenecks in contrastive vision lainuala models. arXiv preprint arXiv:2305. 14897, 2023.
[49] Gal Kaplun, Nikhil Ghosh, Saurabh Garg, Boaz Barak, and Preetum Nakkiran. Deconstructing distribu- tions: pointwise framework of learning. International Conference on Learning Representations (ICLR), 2023.
[50] Faisal Khan, Bilge Mutlu, and Jerry Zhu, How do humans teach: On curriculum learning and teaching dimension. Advances in neural information processing syxtems, 24, 2011.
[51] Douwe Kiela, Max Bartolo, Yixin Nic, Divyansh Kaushik, Atticus Geiger, Zhengxuan Wu, Bertie Vidgen, Grusha Prasad, Amanpreet Singh, Pratik Ringshia, et al. Dynabench: Rethinking benchmarking in nip. North American Chapter of the Association for Computational Linguistics (NAACL), 2021.
[52] Jannik Kossen, Sebastian Farquhar, Yarin Gal, and Tom Rainforth. Active testing: Sample-efficient model evaluation. In International Conference on Machine Learning (ICML), 2021.
[53] Jannik Kossen, Sebastian Farquhar, Yarin Gal, and Thomas Rainforth. Active surrogate estimators: An active learning approach to label-efficient model evaluation. Conference on Neural Information Processing Systems (NeurlPS), 2022.
[54] Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
[55] Alina Kuznetsova, Hassan Rom, Neil Alldrin, Jasper Uijlings, Ivan Krasin, Jordi Pont-Tuset, Shahab Kamali, Stefan Popov, Matteo Malloci, Alexander Kolesnikov, et al. The open images dataset v4: Unified image classification, object detection, and visual relationship detection at scale. International Journal of Computer Vision (ICV), 128(7): 1956-1981, 2020.
[56] Tony Lee, Michihiro Yasunaga, Chenlin Meng, Yifan Mai, Joon Sung Park, Agrim Gupta, Yunzhi Zhang, Deepak Narayanan, Hannah Benita Teufel, Marco Bellagente, et al. Holistic evaluation of text-to-image models. Conference on Neural Information Processing Systems (NeurIPS), 2023.
[57] Percy Liang, Rishi Bommasani, Tony Lee, Dimitris Tsipras, Dilara Soylu, Michihiro Yasunaga, Yian Zhang, Decpak Narayanan, Yuhuai Wu, Ananya Kumar, et al. Holistic evaluation of language models. arXiv preprint wrXiv:22/1.091111 2022.
[58] Thomas Liao, Rohan Taori, Inioluwa Deborah Raji, and Ludwig Schmidt. Are we learning yet? a meta review of evaluation failures across machine learning. In Conference on Neural Information Processing Systems (NeurIPS), 2021.
13

---

[59] Shangyun Lu, Bradley Nott, Aaron Olson, Alberto Todeschini, Hossein Vahabi. Yair Carmon, and Ludwig Schmidt. Harder or different? closer look at distribution shift in datasct reproduction. In International Conference on Machine Learning Workshops (ICML-W) W), 2020.
[60] Inbal Magar and Roy Schwartz. Data contamination: From memorization to exploitation. arXiv preprint arXiv:2203.08242. 2022.
[61] Horia Mania, John Miller, Ludwig Schmidt, Moritz Hardt, and Benjamin Recht. Model similarity mitigates test set overuse. Conference on Neural Information Processing Syxtems (NeurIPS), 32, 2019.
[62] Dena F Mujtaha and Nihar R Mahapatra. Multi-objective optimization of item selection in computerized adaptive testing. In Proceedings of the Genetic and Evolutionary Computation Conference, pages 2021.
[63] Yixin Nie, Adina Williams, Emily Dinan, Mohit Bansal, Jason Weston, and Douwe Kiela. Adversarial nli: A new benchmark for natural language understanding. Annual Meeting of the Association for Computational Linguistics (ACL), 2020.
[64] Simon Ott, Adriano Barbosa-Silva Kathrin Blagee, Jan Brauner, and Matthias Samwald. Mapping global dynamics of benchmark creation and saturation in artificial intelligence. Nature Communications, 13(I):
6793, 2022.
[65]
Letitia Parcalabescu, Michele Cafagna, Lilitta Muradjan, Anette Frank, Iacer Calixto, and Albert Gatt. Valse: A task- ias-eendeeend benchmark for vision and language models centered linguistic phenomena. arXiv preprint arXiv:21 1tep22222....... 2.07566, 2021.
[66] Ethan Perez, Saffron Huang. Francis Song, Trevor Cai, Roman Ring, John Aslanides, Amelia Glaese, Nat McAleese, and Geoffrey Irving. Red teaming language models with language models. Conference on Empiricul Methods in Natural Language Processing (EMNLP). 2022.
[67] Yotam Perlitz, Elron Bandel, Ariel Gera, Ofir Arviv, Liat Ein-Dor, Eyal Shnarch, Noam Slonim, Michal Shmueli-Scheuer, and Leshem Choshen. Efficient benchmarking (af language models). arXiv preprint arXiv:2308. / 1696, 2023.
[68] Momchil Peychev, Mark Niklas Müller, Mare Fischer, and Martin Vechev. Automated classification of model errors on imagenet. Conference on Neural Information Processing Systems (NeurIPS), 2023.
[69] Felipe Maia Polo, Lucas Weber, Leshem Choshen, Yuekai Sun, Gongjun Xu, and Mikhail Yurochkin. tinybenchmark: evaluating 1lms with fewer examples. arXiv preprint arXiv:2402.
2024.
[70]
Christopher Potts. Zhengxuan Wu, Atticus Geiger, and Douwe Kiela. Dynasent: A dynamic benchmark for sentiment analysis. Dynasent: A dynamic benchmark for sentiment analysis, 2021.
[71] Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, et al. Learning transferable visual models from natural language supervision. In International conference machine learning, pages 8748 8763. PMLR, 2021.
[72] Inioluwa Deborah Raji. Emily M Bender, Amandalynne Paullada, Emily Denton, and Alex Hanna. Ai and the everything in the whole wide world benchmark. Conference on Neural Information Processing Systems (NeurlPS). 2021.
[73] Benjamin Recht, Rebecca Roelofs, Ludwig Schmidt, and Vaishaal Shankar. Do cifar- classifiers generalize to cifar-10? arXiv preprint
2018.
[74] Benjamin Recht, Rebecca Roelofs, Ludwig Schmidt, and Vaishaal Shankar. Do imagenet classifiers generalize to imagenet? In International Conference Machine Learning (ICML), 2019.
[75] Pedro Rodriguez, Joe Barrow, Alexander Miserlis Hoyle, John P Lalor, Rohin Jia, and Jordan Boyd- Graber. Evaluation examples are not equally informative: How should that change nlp leaderboards? In Annual Meeting of the Association for Computational Linguistics (ACL), 2021.
[76] Rebecca Roelofs, Vaishaal Shankar, Benjamin Recht, Sara Fridovich-Keit Moritz. Hardt, John Miller, and Ludwig Schmidt. A meta--nalyyse of overfitting in machine learning. Conference on Neural Information Processing Systems (NeurlPS), 2019.
[77] Mark Rofin. Vladislav Mikhailov, Mikhail Florinskiy, Andrey Kravchenko, Elena Tutubalina, Tatiana Shavrina, Daniel Karabekyan, and Ekaterina Artemova. Vote' n'rank: Revision of benchmarking with social choice theory. Annual Meeting of the Association for Computational Linguistics (EACL), 2022.
[78] Nikhil Sardana and Jonathan Frankle. Beyond chinchilla- opthmmll- Accounting for inference in language model scaling laws. arXiv preprint arXiv:2401.00444 2023.
[79] Zhelun Shi, Zhipin Wang, Hongxing Fan, Zhenfei Yin, Lu Sheng. Yu Qiao, and Jing Shao. Chef: comprehensive evaluation framework for standardized assessment multimodal large language models. arXiv preprint arXiv:2311.000 1,02692, 2023.
[80] Ali Shirali and Moritz Hardt. What makes imagenet look unlike laion. arXiv preprint 2577992306.15669
2023.
14

---

[81] Ali Shirali, Rediet Abebe, and Moritz Hardt. A theory of dynamic benchmarks. arXiv preprint arXiv:2210.03165, 2022.
[82] Aarohi Srivastava, Abhinav Rastogi, Abhishek Rao, Abu Awal Md Shoeb, Abubakar Abid, Adam Fisch, Adam R Brown, Adam Santoro, Aditya Cupta, Adrià Garriga-Alonso et al. Beyond the imitation game: Quantifying and extrapolating the capabilities of language models, arXiv preprint arXiv:2206. 246.05.. 2022.
[83] Xiaoxiao Sun, Xingjian Leng, Zijian Wang. Yang Yang, Huang, and Liang Zheng. Cifar- worehhous Broad and more realistic testbeds in model generalization analysis. arXiv preprint arXiv:2310.04414, 2023.
[84] Rohan Taori, Achal Dave, Vaishaal Shankar. Nicholas Carlini, Benjamin Recht, and Ludwig Schmidt. Measuring robustmess to natural distribution shifts in image classification. Conference on Neural Informa- tion Processing Systems (NeurlPS)) 2020.
[85] Tristan Thrush, Ryan Jiang, Max Bartolo, Amanpreet Singh, Adina Williams, Douwe Kicla, and Candace Ross. Winoground: Probing vision and language models for visio-linguistic compositionality. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pages 5238-
5248, 2022.
[86] Yonglong Tian, Lijie Fan, Kaifeng Chen, Dina Katabi, Dilip Krishnan, and Phillip Isola. Learning vision from models rivals learning vision from data. arXiv preprint urXiv:3312.7774. 2023.
[87] Antonio Torralba and Alexei A Efros. Unhiased look dataset bias. In Conference on Computer Vision and Pattern Recognition (CVPR), 2011.
[88] Vishaal Udandarao, Max F Burg, Samuel Albanie, and Matthias Bethge. Visual data-type understanding does not emerge from scaling vision-language models. arXiv preprint arXiv:2310.08377 2023.
[89] Wim J Van der Linden and Cees AW Glas. Computerized adaptive testing: Theory and practice. Springer, 2000.
[90] Kirill Vishniakov, Zhiqiang Shen, and Zhuang Liu. Convnet vs transformer. supervised vs clip: Beyond imagenet accuracy. 2023.
[91] Rajan Vivek, Kawin Ethayarajh, Diyi Yang. and Douwe Kiela. Anchor points: Benchmarking models with much fewer examples. arXiv preprint Skdi:23309008633 2023.
[92] Erie Wallace, Adina Williams, Robin Jia, and Douwe Kiela. Analyzing dynamic adversarial training data in the limit. In Annual Meeting of the Association for Computational Linguistic (ACL), pages 202-217, 2022.
[93] Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel R Bowman. Glue: A multi-tast task benchmark and analysis platform for natural language understanding. arXiv preprint arXiv:1804.07400 2018.
[94] Alex Wang, Yada Pruksachatkun, Nikita Nangia, Amanpreet Singh, Julian Michael, Felix Hill. Omer Levy, and Samuel Bowman. Superglue: A stickier benchmark for general-purpose language understanding systems. Conference on Neural Information Processing Systems (NeurIPS), 2019.
[95] Hangyu Wang. Ting Long, Liang Yin. Weinan Zhang. Wei Xia, Qichen Hong, Dingyin Xia, Ruiming Tang, and Yong Yu. Gmocat: A graph-enhanced multi objeetvb method for computerized adaptive testing. Conference on Knowledge Discovery and Data Mining (KDD), 2023.
[96] Haohan Wang. Songwei Ge. Zachary Lipton, and Eric P Xing. Learning robust global representations by penalizing local predictive power. Conference Neural Information Processing Systems (NeurIPS), 2019.
[97] Zan Wang, Hanmo You, Junjie Chea, Yingyi Zhang, Xuyuan Dong, and Wenbin Zhang, Prioritizing test inputs for deep neural networks via mutation analysis. In 202/ IEEF/ACM 43rd International Conference on Software Engineering (ICSE), pages 397-409. IEEE, 2021.
[98] Ross Wightman.
Pytorch image models.
https: htt.:uu....oo//wwtttttttott
pytorch- taarh-immee--ae models,
-mage-modele, 2019.
[99] Olivia Wiles, Isabela Albuquerque, and Sven Gowal. Discovering bugs in vision models using off-the-shell image generation and captioning. arXiv preprint xrXiv:2008 08831, 2022.
[100] Jingwei Yu, Mu Zhenyu, Jiayi Lei, Li' Ang Yin, Wei Xia, Yong Yu, and Ting Long. Sacat: Student- adaptive computerized adaptive testing. In The Fifth International Conference on Distributed Artificial Intelligence, 2023.
[101] Ganzhao Yuan and Bernard Ghanem. Binary optimization via mathematical programming with equilib- rium constraints. arXiv preprint 1Xi.::60..0440 2016
[102] Xiang Yue, Yuansheng Ni, Kai Zhang, Tianyu Zheng, Ruoqi Liu, Ge Zhang, Samuel Stevens, Dongfu Jiang, Weiming Ren, Yuxuan Sun, et al. Mmmu: A massive multi coltti-discipline multimodal understanding and reasoning benchmark for expert agi. arXiv preprint xrXiv:2311.16502 2023.
15

---

[103] Mert Yuksekgonul, Federico Bianchi, Pratyusha Kalluri, Dan Jurafsky, and James Zou. When and why vision-language models behave like hags-of-words. and what to do about it? In The Eleventh International Conference Learning Representations, 2022.
[104] Xiaohua Zhai, Joan Puigcerver, Alexander Kolesnikov, Pierre Ruyssen, Carlos Riquelme, Mario Lucic, Josip Djolonga, Andre Susano Pinto, Maxim Neumann, Alexey Dosovitskiy, et al. The visual task adaptation benchmark. 2019.
[105] Yi-Kai Zhang, Ting-Ji Huang, Mto-Xiang Ding, De-Chuan Zhan, and Han-Jia Yc. Model spider: Learning to rank pre-trained models efficiently. arXiv preprint arXiv:2306.03900 2023.
[106] Lin Zhao, Tianchen Zhao, Zinan Lin, Xuefei Ning, Guohao Dai. Huazhong Yang. and Yu Wang. Flasheval: Towards and accurate evaluation text-to-image diffusion generative models. arXiv preprint arXiv:2403. 16379, 2024.
[107] Lianmin Zheng, Wei-Lin Chiang. Ying Sheng, Siyuan Zhuang, Zhanghao Wu, Yonghao Zhuang, Zi Lin, Zhuohan Li. Dacheng Li. Eric. P Xing. Hao Zhang, Joseph E. Gonzalez, and lon Stoica. Judging Ilm-as-a-jugee with mt-bench and chatbot arena, 2023.
[108] Wangchunshu Zhou, Yan Zeng, Shizhe Diao, and Xinsong Zhang. Vlue: A multi-task multi-dimension benchmark for evaluating vision-language pre-training. In International Conference on Machine Learning (ICML). 2022.
[109] Yan Zhuang, Qi Liu, Zhenya Huang, Zhi Li, Shuanghong Shen, and Haiping Ma. Fully adaptive framework: Neural computerized adaptive testing for online education. In Conference on Artificial Intelligence (AAAI), 2022.
[110] Zohar, Shih Cheng Huang. Kuan-Chieh Wang, and Serena Yeung. Lovm: Language-only vision model selection, arXiv preprint arXiv:2306.08899 2023.
16

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We have highlighted the main efficient evaluation claim in the title, abstract, introduction and results section. We back up our main claim with our experiments in Sec- tion 4.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We have included a limitations section in Appendix L..
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: Yes, we provide our proofs in Appendices and
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided not)?
Answer: [Yes]
Justification: We transparently include all our experimental settings required to reproduce our findings in the main paper. We also include pseudo-code for the algorithms used in Sorr & Search in Listing 1. Further, we release our Sort & Search (anonymized) codebase for ensuring reproducibility, in the supplementary material.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described supplemental material?
Answer: [Yes]
Justification: Yes, we provide the code in the supplementary material.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Yes, we include all the experimental setup details in Section 4.1.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: We report error bars with standard error of the mean, for our main results in Section 4.2.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of exccution) needed to reproduce the experiments?
Question:
17

---

Answer: [Yes]
Justification: We mention the total number of GPU hours required for our entire model eval- uation using the standard full-evaluation using our Sorl & Search method, highlighting the cost savings from our method, in the main paper.
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https:/ /ttp://nneuupppppeeeee wwwpeurrp..ccppullllieeee wwtppblic//aaeeeeeeeeeeeeeeeeeee Cettci//iiiie csGuidelines:
Answer: [Yes]
Justification: Yes, to the best of our knowledge and abilities.
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: Our paper can be considered as foundational research and not tied to particular applications. let alone deployments. We do not immediately see any negative societal impact. A positive societal impact might be faster and cheaper evaluation available for developing benchmarks.
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: We only work with existing datsets and models, and do not release any new datasets models.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: We have cited the original datasets and code for correct credit assignment in Table
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: The code is documented and released under GPL3 license.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects 15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
18

---

Partl I
Appendix
Table of Contents
A Domain-Agmosticn of Lifelong Benchmarks
2
Towards Truly Lifelong Benchmarks: A Conceptual Framework
3
C Lifelong-ImageNet and Lifelong-CIFAR10: Details
4
D Pythonic Pseudo-code for Sort & Search algorithms
5
E Analysis: How Consistently Do Models Follow Global Ranking?
6
F Analysis: Changing metric from MAE a Rank Correlation
8
G Does Error Accumulate with Consecutive Additions of New Models/Data?
9
H Extended Related Work
10
Proof Theorem 3.1
Proof for Theorem 4.1
13
K 167 Models used for Ifflleng-ImageNer experiments
14
Limitations and Open Problems
15

---

A Domain-Agnosticity of Lifelong Benchmarks
Our framework domain-agnostic. All our framework requires 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 range of metrics:
Language Models: Our framework can be directly applied multiple-choice question evaluations popular for benchmarking language model evaluations. The metric here is exact match or near-exact match, binary metric that perfectly aligns with our framework requirements.
Dense Prediction Tasks 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 A matrix instead of a single value. Extending the search algorithm is straightforward: if point is sampled, all associated values sampled and annotated.
array of binary values the
Tasks with Real-valued Predictions: For tasks such as regression or BLEU score evalua- tions, 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 function, it restricts the output predictions to the binary threshold level.
Followup work [3] does extend lifelong benchmarks evaluating language models and multimodal language models and tackles the unique challenges faced in those cases.

---

B Towards Truly Lifelong Benchmarks: Conceptual Framework
In the main paper, introduced the concept of lifelong model evaluation through the idea of ever-expanding large-scale benchmarks, termed Lifelong Benchmarks. Although and Lifelong- CIFARIO are large-scale, they are truly lifelong they do expand over time. These benchmarks primarily test the efficacy of our Sort & Search method due to their large size.
To achieve true lifelong benchmarks, we need continuous acquisition of samples and models, allowing for continual growth (as detailed in Section 2). In Fig. 6, we illustrate how lifelong benchmarking differs from the standard benchmarking approaches currently used in machine learning research.
Traditional Approach: Static Benchmarks
Proposed Approach: Lifelong Benchmarks
evaluate
Midell
'uumpl runking
2 0.49
Modell
Model
Dogs
Dogs
18: Cats- Dogs Toom
Model
model evaluction
0.82
Model
Scare
Model Soare 0.86
Medel Scoee
Lifelong Cats- Cats-Dogs
0.94
0.71
Supdate pool
Model
2 0.57
0.75
0.95
0.58
0.89
0.83
New incoming samples
Moje
M1 "stale-of-the-ate art" generalization" M2 best "distributiona generalization
türre
time
Figure 6: Static vs Lifelong Benchmarking. (Top) Static benchmarks incentivise machine learning practitioners to overfit models to specific datasets, weakening their ability to assess generalisation. (Bottom) We conceptualise Lifelong Benchmarks as an alternative paradigm--ever-exppaeg -ver-expanding pools of test samples that resist overfitting while retaining computational tractability.

---

C Lifelong-ImageNet and Eefelong-CIFARIA Details
In this section, we detail the creation of our lifelong benchmarks.
Considerations. We aim to establish lifelong benchmarking as a standard evaluation protocol in computer vision. To demonstrate this, considered two popular datasets as our basis: CIFARIO [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 variants 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 for key statistics and a detailed breakdown.
Lifelong-CIIse CIFARIO. We combine 31 domains of different CIFARIO 10-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 ensure uniqueness and downsample all images the standard CIFARIO resolution of 32 X 32, Our final dataset consists of 1 1.69 million samples.
Lifelong- ImageNet. We source test samples from ImageNet and its corresponding variants. Similar to Lifelong-CIFAR1O 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 Imageeeet contains 1.98 million samples.
Table 1: Overview of our Lifelong Benchmarks. We list the constituent source datasets (dedupli- cated) and their statisties for constructing our lifelong benchmarks here. Our benchmarks encompass a wide-range of natural and synthetic domains, sources and distribution shifts, making for a compre- hensive lifelong testbed.
Dataset
#'esst Samples
#Domalns
#1 Unnique Sonrees
Synthetie/Naturaa
Corrupted/Clean
License
Mflonn-CCPPRRN
1,097,822
Both
Both
CIFAR1O. [73]
Natural
CIRAR [54]
Natural
Unkknww
CIPAR10.2 [59)
12,000
Natural
Clean
Unkknown
CINICIO (21)
210,000
Natural
Clean
MIT License
CIFARJO-W [83]
513,682
Both
Cleun
MIT License
CIFAR 10-C:
950,000
Natural
Committed
Apache-2.0 2.0 License
Jjfelnn-tmageeNt
Roth
ImageNet-A [41)
7,500
Natral
Clean
MIT License
ObjectNet [S]
18.514
Natral
Clean
Custom License
OpenlmagesNet
23.101
Natural
Clean
MIT License
ImageNet- V2 [74]
30,000
Natural
Clean
MIT License
ImageNet-RR [39]
Natural
License
ImageNet (23)
50,000
Natural
Clean
Castom Non- Commercial
Greyscale-mmage ImageNet [8/]
50,000
Natural
Clean
MIT License
SiylizellmngeNee [35]
50,000
Synthetic
Corrupted
MIT Livense
ImageNet- Sketch [95]
Snatchet-Sketch
50,889
Satural
Clean
MIT License
SDNet
Synthetic
License
LatonNist [80]
677.597
Natural
Clean
Unknown
ImagoNet-C(1M [388
900000
Natural
Comppte
Apuche-2 2.0 Licnnse

---

D Pythonic Pseudo-code for Sort & Search algorithms
Here. we provide pythonic-pseude code for the constituent algorithms of Sort & Search, which described in detail in Section 3.
def eort_by bart_by_aun(A)) sun((A):
run_ranking (.xum(axis=0)
order up hanp:ppparggaottccuuaaaaaaaa
order
swo__ttge__orte bar.go_oortbbyyaumc.. idx):
#Step Sun
der uniforn, sarform_sanpInnn(uurry nun_p)::
order sort_by_sum(A))
idx -> uniforuly sanpled pointe
#Step 1: Search
idx np. np.arange(O, len (qu(r))));
thresh $p_search(A[;, order))
len(query) (nmeery)//un.ppp [1:]
return idx
aIterate over bina bine_ordered bin_
def dp_ sppachrhhhqqurr
unig_bina sp.uniqua ooddered)
query (k can be assigned :n n, n', B, m!)
k (from of PA)
for u_bin in unig. bins: nonzero (bins_ renzorroeins.odddred---o orderodd-u (0] bin_thresh
query [query--0]
cunsum up. (q.cumeun(querr)
np argnax(cuuuuun))
ap.nonzero all (([binsss ordered
return idz/len (query)
+ :dx.nin()], [bins_ordered <=
length,
+
idx.nex()]], axia-0)) [1]
size
A[thresh] [:, order [idx]]
#Step Sun
order sort_by, (ut(
Replace current ordering within new in
bin
order [idx] order [idx [nex_ordr]]
Listing (Left) Algorithm for Optimizing P given Y (Right) Algorithm for Optimizing Y given P

---

E Analysis: How Consistently Do Models Follow Global Ranking?
In all our main results using Sort & Search, we use a single ranking order for all new models. 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 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 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 Lmfeleng-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, ranges from O to I-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. hence, there are no models that are totally anti cnti-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
we would observe disconnected components, systematically isolated squares.
Result. From the correlation plot, 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 they are random. We observe slightly higher correlations between the top performing models, but note that this is confounded by their high accuracy- 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 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 done for 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.

---

Histogram of Usique Spearmnn Kank Correlation Values
902
402
202
(a) Spearman Correlations are all positive
Spearman Rank Correlation Matrix Heatmap
Highest accuracy models slighlly correlated to each other than others
0.5
Very accuracy uncorrelated to all other models
0.7
0.6
0.5
0.4 0.1-03
(b) Spearman Correlation Matrix
Figure Correlation Analysis between Model Predictions on Lifelong-ImageNNer (a) We note that all correlations between model predictions are positive, signifying the similarities between all models despite their diverse sizes, architectures, and inductive biases. (b) We show the cross-correlation matrix between all model predictions the and y axes showcase models, sorted by their accuracies. The floating point numbers on the x and y axes are the model accuracies the highest accuracy models (70% accuracy) appear at the top and left, while the lowest accuracy models appear at the bottom and right (10% 30%).

---

Analysis: Changing the metric from MAE to a Rank Correlation
In all our main results using Sort & Search, the mean-absolute-crror (MAE) evaluate the effectiveness of our framework.
While MAE serves as useful proxy metric for algorithm development, it is not necessary requirement to provide practical applications. In particular, for many use-cases, is the ranking of the models, rather than their absolute metrics, that are of primary importance for informing downstream decisions about which model use.
Are Model Rankings Correlated?
(GT v/s Fred Model Rankings)
0.50
Spoarman Corrolation
0.45
0.40
0.35
0.30
10
10a
10*
Sampling budget n'
Figure 8: We change the metric for evaluating the efficacy of Sort & Search from MAE to Spearman correlation observe consistently high correlations of 0.5 greater.
To illustrate 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 Spearman correlation between the rankings of 25, 250 models using CIFARIOO. The
Sort & Search and the rankings obtained after full sample evaluation on results, presented in Fig. 8, show consistently high correlation of 0.5. We believe this demonstrates 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 accumulate with consecutive addition of new models or data. The core intuition lies in the fact that sequential updates to P when made with the predicted vector Yr+1 will necessarily preserve the same permutation, i.e. P2+1 P; as Yr+1 strictly follows P itself, adding an error of
Detailed Explanation. Considering the case where new model is presented in which A E {0, 1] where [M] is the number of models and [D] the number of data samples. We solve Equation by alternating the solution between solving for y given the permutation P and P given the prediction For ease, and without loss of generality, consider the problem when solving Equation I repetitively for a sequence of new samples. A natural question is: Do need re-optimize for Pa and update A with the new ranked prediction vectors Yt for every timestep?
Our algorithm Sort & Search, while might not be achieving global optimality in both P and y. however, we have guarantee that if P and y; are the solutions of Sort Search at step t, then P; = P7+1 at every step and we do not require recomputing P2 optimizing [A,yy;] | after every addition where [A,] Yil is the concatenation of A, with the new sample Y++1. This is since The core intuition underlying this result is that at the new step + 1 the vector yi+1 has structure of ones followed by zeros ordered according to the optimal permutation Pi+1 that orders samples from "easiest" to "hardest" following the structure in AP;, Hence, adding it to the sum preserves the ordering of elements (if ties are broken in the manner of the old ordering).
Sort & Search only requires access to the sum over columns of [A, (see Algorithm
Effect of Serially Adding New models
10"x
10'x
10xx
10'x
10'x
10'x
MAES to Ground-Truth
0.18
One Shot (Fixed Pt)
Serial Add-and-Repeat
0.17
0.16
0.15
0.14
0.13
10a
10
Sampling Budget n'
Empirical Backing. We conducted experiments by adding new models serially and using the Sort & Search predictions as ground truth for further model additions on
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.

---

H Extended Related Work
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
[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 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- -herr 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, strand of automatic error discovery [19, 27, 99, 68] their human- in-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 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 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 single batch of data with a large-scale foundation model is necessitated. Albeit similar in spirit to the task of actively acquiring subset of samples for testing models, important distinction of our method is that we want to minimise the number of forward-passee through a model wwe 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 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 human- in -hethe-ooop 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 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]. multi- objective optimization [62, 43, 95], retrieval- augmenntd adaptive search [100]. One key challenge in Since the goal in CAT is to estimate the proficiency of an
CAT is the lack of stable ground-trute examinee, and the examinee's 's true ground-truth proficiency is not provided, how would one evaluate the true proficiency of an examince? Thereby, existing CAT methods cannot explicitly optimise for
10

---

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-trum targets for the tasks we consider. In both Lifelong-Imane compute grounded metrics that can be optimised towards, unlike in CAT, where every method has to inherently be label-free.
and Lifelong-CIFAne CIFARIO, we have access to the ground and hence can
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]. 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 this direction utilise estimating variance of gradients [1] and other information theoretic properties [26] to estimate sample difficulty, These approaches are complementary our Sum component in S&S since these can be easily integrated into our framework directly.

---

I Proof of Theorem 3.1
Theorem. Optimality of given For any given a, {0, 1] and DP-Search returns an ordered prediction vector y; E {0, 1 which is global minimum of |la,P - -yall. where being an ordered prediction vector implies that if y, 1 then Yj 14ÿ j. Moreover, if y, 0. then Y,' Vj j.
Proof. First, we reduce the problem from Eq. (1) to the following:
y" argminy ||a P - y'lll if y', = then y' Vj' S and if y', O, then y' =0 Vj 2 j.
(5)
Note that y' essentially constructs vector, y/: of all ones up some index 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:
e
by-
(6)
k=i+1
Observe that the first term is the number of zeros to the left of index (inclusive) in b, while the second term is the number of Is in b to the right of index i.
Proposition L.1 y's is minimizer to Theorem 4.2, then, the following holds:
Σ k=++1
by S (n - 1) -
by
k=i+1
Proof. Let < and that y', and y', are feasible solutions for Theorem 4.2. However, let that y'; be such that the inequality in Proposition I.1 while it not the case for y'; j. Then, we compare the differences in the objective functions e(y';) :) and e(y') ()) We have that:
(1 1 Σb,}
e(y'))-((y'))
+ Σ b
bk
+
b
k=1
k=j+1
k=
1m+++1
2
Σ b (i (i-1) j).
k=
However, we know from the assumptions that Dit1 b S n and that 2 E by 2 j.
Subtracting the two inequalities we have 2 Ek=j+1 by 2 - which implies that y'(s) 2 c(y'))
which implies that y'; is a better solution to any other y'; not satisfying the inequality in Proposition I.1.
The inequality condition in proposition I.1 implies that for the choice of index i, the number of zeros in the right of index is more than the number of to the right of index Since any solution y'; either satisfies property in Proposition I.I or not. Moreover, since Proposition I.1 demonstrated that the of indices that satisfy this property are better, in objective value. than all those that do not satisfy it, then this condition achieves optimality.
12

---

J Proof for Theorem 4.1
Theorem. Given any ground-truth vector am+11 it is possible construct prediction vector Ym+1
such that Enge (vm+1 8m++1 = 0 and [aam+1 Mm+1) = 2min - |am+ 1/,,, (am+ l/n)
Proof. Given +, construct the prediction vector Ym+1, such that Euge Mm am++1 1) 0 and E(am+11, +1) = 2.min(1 - |8m+11/n, [8m+=l/n)
Construction: We first design construction for the prediction vector ym+1- Let consider three cases: (i) |1 0.5, (ii) |m++1| 0.5 and (iii) |am+1l = 0.5.
Case (amm+l < 0.5): We construct the prediction vector by first flipping all the indexes with value 1 in a
resulting MAE of /m...l/n.. Since, are constrained to maintain the same | l we can flip any |mm+1 other indexes with values to 1. This is possible in this case as there are more Os than 1s in am+1- This results in MAE of |m (mme1/// /n. Taken together, they achieve the total MAE of 2/mm In.
Case 2 (amm1ll > 0.5): We construct the prediction vector by first flipping all the indexes with value 0 in am+1 1, resulting in MAE of 1 |am+://n. Since, are constrained maintain the same |am+1/ 1. we can flip any other index
|am+ with values to O. This is possible in this case as there are more Is than Os in am++1 1. This results in an MAE of 1 /am-1l/n. Taken together, they achieve the total MAE of F 2. [mm+1//n).
Case 3 a1am+1l 0.5): We construct the prediction vector by flipping all the indexes with value 0 in Am-1 1 to and flipping all the indexes with value am+1 to This achieves the total MAE of E = = 2/amm1////a.aa..... :l/m = 2. 1//))/a).
This concludes the construction of the prediction vector ym+1-
13

---

K 167 Models used for Lifelong-ImageNet experiments
We use the following models (as named in the timm [98] and imagenet-testber [84] repositories):
B1T-M-8101xh 11._800012--1VVV220222
57. inceptionve
113. http__iithdddduueeeeeeeeeee
B47-N-850x1-ILSVRCRA
114. resnet50_ fog.
3. N4T-M-850x3-ILSWRO00
59. sueeagran-roneext00__.22
115. resmet50_withhffrot..
PizPKAStiet
iustagran-remextt001_
116.
5. Fizßeesett50
61. maasnet0_5
117. remmatt..utthh.rryaaaa.....
FirRasXet500utlMi
62. maasnati_0
118. hatpratto__itt.jppe.oooereepee
63. mobilenet_v2
resnst50_ srenaat5__withmootiten www.:ittt_otiinbbur.r.
64. mobilenet_v2_1pff
121. httpso_wiithh.iieeteeeeee..
120. resnet50 resnets0_witth.piieeeee
FizResNet50_v2
65. 1ob11emet_v2_.ptt6
nasnstalargo
122. wtt.::ihhhhoooohuurreeero
11. alexnst_lpf2
67. nasnetamobile
123. resnat50
slexmet_lpf3
68. polynet
ressezit01__2xx16__eee
13. slexnst_lpff
69. resnet101
125. resmext101_32xde
14. bainception
remmeti01_cutmix
resmext101_32xdd,
15. baincaptiion-imngaattal
71. reamet101_1p12
127. cesnexti01__2xxd_neee
16.
72. rasmat:00__pp3
128. resnext101_
17. densemat121
73. resnet101_1pf5
resnext101_22xdd.02
densenet121_1pt2
74. resnat152
130. tecnext101__Sxxd___eo
19. densenat121_1pt3
75. resnet18
resnaxt101_64r
densemet121_1pf6
reaaattB-rotaacioo-nncrogg.
132. resmext50_32x44
21. densenati61
77. remmet18-rotatioo-raaneee 30
resmext50_32x4d_ees
remmetiB-rroaatioorrraaaooa
134. resmext5033xxdd_com
23. densenet201
79. reraactiB-rroaaciooovvaett11....
135. se_reanet101
dpn107
se_resuet152
25. dpn131
81. rea.att1B-rotattaooeeerrttt....
137. se_reanet50
dpn68
18_1p2
138. se se_resnexti01__222
27. dpm68b
83. resnst18_1pf3
139. sr_rescext50_322k6
dpn92
resnatt1_1ppf
29. dpm98
85. 1a_anet1__sai1
140. senet154
slufflenet.v2_x0.6
30. afficiantnat-bo
resnet18_rven
31. officientnst.bb.
87, resnet34
142. shufflenet_v2_xx1_
32. efficientnet-bl
resnet34_1pf2
squeazenat:1_0
33. wtwpatttttt----ddrooooooo auteaug
89. resmet34_1pf3
144. squeezeneti_1
34. affticienttet----arraagg
90. 1ep5
145. vgg11
35. ofFicientnat-B2
91. resnet50
146. vggl1_bn
36. (iicciantntt----aappoo--aaaaa
92, resnat50, reamat50_adv-craftt adv-crain-free
147. vgg13
37. efFicllantatt-b--auraaa
93. resnet50_ _aggiix
vgg13_bn
officiantmat-b33
94. reanat50_ aasto_ass____0 aws_o_alallabaloooo ine
149. vgg16
39. officiantnat- affiiclantnat-b--aayrreee bb-ddrprop--ttonn
95. resnat50_cutmis cutmix
150. vgg16_bn
b3-autoaug
96. reanat50_cutoon cutout
151. vag16_be_1pf2
41. officientnst.be
97. reanat50_docpaugeeeee deopaugnent
152, regl6_bn_lpft
officiantnat-Be secciinttet-----dvppeee ad-advprop-autte autoaug
98. recnat50_decpantt www.ddaggnnttauuggeoooooo
1g_16_bn_1p15
43. afficlentnettD4-arraaa
99. reanet50, Saatlttt_featuree fwwture_tteuuue _ettnix
154. vgg16_1pf2
44. efficientnet-b5
reanet50_12__00 1_____1___________
vgg16_1pf3
45. (FFicientnettD--aavrrpo-.. 101.
reamet50_1100
www.:liff_______eee__ robust
156. vgg16_Ipf5
reanet50_ 1ttp__iinn_______________
157. veg19
47. affiiclanttat-b--raadd
103. resnat50_1pf2
158. vgg19_bn
reanat50,
159. side__resnet101_2
49. officiantmat. -e--anttttt--bb-taaaagg
105. resnat50_ 1pf5
xception
50. officiantnet- awwpo
reanat50 _miiptppppxppppppp
161. resowt50
Sexxwtt0__traineee Sosiined_oo_SSS_eeml [t____n________ htt.ttttoofffeetteeeeeeo finetuned_ on__I
51. siicciantnat.b--auaaaa
107. resnetã0_ca
162. 19ane150, waggentt_ubbxappee....oo 116
wwt.b6bbttt4__orree origgial.. images
52. a
reanet50_ewa
2ww.2_.hehh__eiiieeeeeee insaees
53. efiicientaett---addpr------ppp 109. reanet50, reanet50_trainedd _I_
reanet50 ingenett wwggemtt_ubuuepl...cc
www.bettc_oorr. prriiooriiinnaa images
54. Ibresnet152
reanet50, reanet50_trainedd on_ and aod_]
165. reamet50, _ iagenett wttp:ettssseeeppl___..oo www.hhhhhh___._...
wor.oe44__riiiiil__. inagea
55. 1nceptionreanetv2
III. resmet50_vite wetp__itthbbbbbeee fettt_briaee wrw.brretataaaaaooo
166. resmestn wrthctnn_uithh... www.hhhhggtta....o.o.o.
56. inceptionv3
resnet50, sithetto_wiihh..bo weattthcoorrttteeec
recaet50, recaet0__nageeee inagenes, Saaagcet__1Opprreeet 100percent Sttprrrerrbbatchhe.. www.chhoooorriooa........ inages
14

---

L Limitations and Open Problems
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 single sample ordering P to sample ordering structures, such as different clusters of models each with their own orderings 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 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 foundation models, since it only relies the existence of an A matrix, it would be interesting to test on more benchmarks from the LLM and VLM domain.
15


Reviews:
[{"review_id": "vNrCJd9gvH", "reviewer": "Reviewer_oB2P", "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.\n\n\"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.\n\nUsing 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.\n\nAssuming 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.\n\nTo efficiently insert samples, they just have to evaluate them on a set of models to estimate their difficulty.", "questions": "None", "limitations": "Limitations addressed my weaknesses.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their detailed feedback. We seek to address the reviewer’s concerns and suggestions below:\n\n> W1 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.\n\nThank you for raising this important point. Our framework is domain-agnostic. What we require is an A matrix constructed using any binary metric, with rows representing samples and columns representing evaluated models. We summarize how our framework can be applied to various domains below:\n\n- **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. \n- **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. \n- **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. \n    - 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.\nWe hope this clarifies the adaptability of our framework to various tasks and domains, including language modeling.\n\n---\n\nWe hope we addressed the major concerns of the reviewer, and are happy to answer any further questions/concerns. Looking forward to a fruitful reviewer-author discussion phase.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "99Kg9SPQO3", "reviewer": "Reviewer_bEaJ", "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.", "questions": "1. What are the MSE results of applying uniform/random sampling directly to the sample pool without using the sort algorithm?\n2. What is a reasonable target for MSE, and how difficult is it to improve MSE by 0.01?\n3. What is the storage overhead introduced by the proposed framework?\n4. Can the framework be extended to other tasks such as object detection or segmentation?", "limitations": "Yes", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "+ The paper is well-written, with clear examples and theoretical proofs.\n+ 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.\n- 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?\n- The proposed framework saves computational resources at the expense of increased storage overhead, however, the storage overhead is not discussed in the paper.\n- 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?\n- Minor issue: In Appendix H, the text is overlapped and needs formatting correction.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for their thorough evaluation and positive feedback. We’re pleased that the reviewer recognised our work’s originality, noting it \"targets a practical and pressing problem\", \"experimental results demonstrate significant compute reduction\" and \"with clear examples and theoretical proofs.\" We seek to address the reviewer’s concerns and questions below:\n\n> W1/Q1 What are the MSE results of applying uniform/random sampling directly to the sample pool without using the sort algorithm?\n\nWe agree with the reviewer that evidence for supporting the effectiveness compared to random is important. We *provide this in our paper*. It is labeled as “CopyNearest&Expand” – we randomly sample n’ points and search using kNN (which replaces the search aspect). We shall revise the naming of this evaluation in the revision to make its role as an important baseline clearer.\n\nWe show in Figure 2(c) and 3(b) that our Sort & Search algorithm outperforms this baseline by significant margins, discussed in the next question.\n\n---\n\n> W2/Q2 What is a reasonable target for MSE, and how difficult is it to improve MSE by 0.01?\n\nImproving the performance by 0.01 MAE requires altering the results on 17,000 samples, which is a large margin. This difficulty is even greater at low MAE levels, as shown in the overall figure PDF.\n\nThe Sort and Search method achieved an MAE of 0.14 with 80 samples, while reaching an MAE of 0.13 required 1,000 samples—requiring more than ten times the number of samples for reducing MAE by 0.01.\n\n---\n\n> W3/Q3 The proposed framework saves computational resources at the expense of increased storage overhead, however, the storage overhead is not discussed in the paper. What is the storage overhead introduced by the proposed framework?\n\nThank you for this excellent question! Sort & Search only requires storing only two 1D arrays, one which maintains the sort-sum and one array used for constructing the current search output. The storage overhead is hence minimal, being 0.0166% of input data or <100MB in absolute terms. This is indeed a key strength of Sort & Search compared to recent methods including CopyNearest&Expand, and we should emphasize it in our work.\n\n**Details:** Sorting compresses the entire A matrix into a single vector, which can be updated online with a simple sum operation. Searching involves receiving a new vector, selecting n' points, and applying the DP-Search algorithm. These involve storing 3 1D arrays, with additional 1-2 1D arrays required temporarily for evaluation procedures.\n\n---\n\n> W4/Q4 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?/Can the framework be extended to other tasks such as object detection or segmentation?\n\nThank you for raising this important point. Our framework is domain-agnostic. What we require is an A matrix constructed using any binary metric, with rows representing samples and columns representing evaluated models.\n\nWe summarize how our framework can be applied to various domains below:\n\n- **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. \n- **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. \n- **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. \n    - 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.\n\nWe hope this clarifies the adaptability of our framework to various tasks and domains.\n\n---\n\n> W5 Minor issue: In Appendix H, the text is overlapped and needs formatting correction.\n\nThank you for bringing this to our notice, we missed this. We have corrected this!\n\n---\n\nWe hope we have addressed the major concerns of the reviewer, and are happy to answer any further questions/concerns. We look forward to a fruitful reviewer-author discussion phase.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "GSCPSmM9vF", "reviewer": "Reviewer_T9R1", "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.", "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?\n\nQ2. 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": "Yes, the authors adequately addressed the limitations.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "> W1 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.\n\nWe thank the reviewer for this point. We have sought to answer the questions raised below for clarity. \n\n> 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?\n\nThank you for raising this important point. Our framework is domain-agnostic. What we require is an A matrix constructed using any binary metric, with rows representing samples and columns representing evaluated models.\n\nWe summarize how our framework can be applied to various domains below:\n\n- **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.\n- **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.\n- **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.\n    - 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.\n\nWe hope this clarifies the adaptability of our framework to various tasks and domains.\n\n---\n\n> 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?\n\nWe currently assume that labels are correct, and are unable to identify label noise. One can extend this to noisy samples by trading off sample efficiency, a.la., error-correcting codes. Alternatively, we can apply a cleaning/verification process on the input labels provided by using frameworks like CleanLab and exclude outlier samples for better ranking estimation. \n\n---\n\nWe hope we have addressed the major concerns of the reviewer, and are happy to answer any further questions/concerns. We look forward to a fruitful reviewer-author discussion phase.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "K8tupMVVLN", "reviewer": "Reviewer_tnhy", "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.", "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)\n- 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": "The authors include a limitations section in their manuscript.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- The paper discusses about lifelong benchmarking, which is important in mitigating new methodologies and models overfitting to the benchmark itself.\n- 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.\n- 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?\n- 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?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for their thorough evaluation and their detailed feedback. We seek to address the reviewer’s concerns and suggestions below:\n\n> W1, 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.\n\nWhile 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. \n\nTo 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 the attached PDF, show a consistently high correlation of 0.5. We believe this demonstrates the framework's applicability for practical use-cases. \n\nFurthermore, we provide interesting, concrete avenues for improving the sorting algorithm in point (2) in Appendix I – Limitations and Open Problems of our work.\n \n---\n\n> W2 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?\n\nThank you for raising this point. In Appendix D, \"How Consistently Do Models Follow Global Ranking?\", we show that the underlying hypothesis of sorted order of difficulty generalizing to new incoming models holds fairly robustly. We will discuss the sensitivity of our sorting algorithms to other factors such as noisy samples and labeling errors, which are important robustness considerations additionally in our revised draft.\n\n---\n\n> W3 When consecutively adding new models or data serially, is the matrix P and A recomputed after each addition? If so, does the error accumulate for consecutive additions?\n\nThank you for the great question! We conducted experiments by adding new models serially and using the sort & search predictions as ground truth for further additions. The results are presented in the attached PDF. We observe the *errors do not accumulate with consecutive additions*, exactly the same model order is preserved. We provide an intuitive sketch for why this is the case:\n\nConsider a sum vector $s_t$, which when sorted gives us an order vector $P_t$ at time t. We can prove that sequential updates to the sum array when made with the predicted vector $y_{t+1}$ will necessarily preserve the same $P_t$, i.e. $P_t$ = $P_{t+1}$ for all t.  \n\n*Proof Sketch:* The core intuition behind the proof is that vector $y_{t+1}$ is [1111...000] in the order $P_t$, i.e. preserving the order as $P_t$. Incrementing the sum array with a order preserving $y_{t+1}$ preserves the order (if ties are broken in the manner of the old ordering). Why? If an element ${s_i}$ > ${s_j}$ at time t then necessarily ${s_i}$ > ${s_j}$ at t+1 for all elements i,j because y is sorted, i.e. if j >i in y then  ${y_i} >= y_j$.  \n\nWe shall formalize this and include these results alongside our point (1) in Appendix I – Limitations and Open Problems. \n\n---\n\n> Q1 For Figures 2,3,4, Could the MAE get lower if more computing is utilized? Could the plots be extended further towards x compute saved (full evaluation)? (if the experiments are expensive, please do not run them and skip the plot extension part)\n\nWe have extended Figures 2 and 3 in the common PDF to show the results of a full evaluation. Our observations indicate that the MAE error in these figures cannot be reduced further, demonstrating that *additional sampling does not decrease the MAE*.\n\n---\n\n> Q2 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)\n\nWe have provided an outline figure in the common PDF. Thank you for pointing this out, we believe this helps clarify the Sort and Search framework.\n\n---\n\nWe hope we have addressed the major concerns of the reviewer, and are happy to answer any further questions/concerns. We look forward to a fruitful reviewer-author discussion phase.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "SDcwO5dMnH", "reviewer": "Reviewer_jvk8", "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'.", "questions": "**a)** \nIs 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?\n\n**b)** \nHow do you know/compute matrix Y, the optimal ranked accuracy prediction matrix?\n\n**c)** \nDid 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.\n\n**d)** \nCould 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)\n\n**e)** \nLine 191: \"We want to find the best n′ observations\" -- best with respect to what?\n\n**f)**\nYou 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?\n\n&NewLine;  \n**Comments:**\n\n- [line 131] What does EM stand for?\n\n&NewLine;  \n**[minor comment / observation]**\n\n- [line 110] Typo on operation 2 -- I believe it should be insert_M", "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?)", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "**Originality:** \n\nThe 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?\n\n&NewLine;  \n**Quality:** \n\nThe 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.\n\n&NewLine;  \n**Clarity:** \n\nOverall 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.\n\nThe 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.\n\nSection 4.2 seems to be out of place, as it describes a design decision of the framework, and not something specific to the experiments.\n\nThe 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)\n\n&NewLine;  \n**Significance:**\n\nReducing 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for their thorough evaluation and positive, enouraging feedback. We seek to address the reviewer’s concerns and questions below:\n\n> S1 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?\n\nOur inspiration comes from the ChatBot Arena initiative by LMSys, where users test models with inputs from their use cases and provide feedback, which helps grow the benchmark.\n\nLifelong benchmarks differ from the current paradigm of creating new datasets as they aggregate data from older “solved” benchmarks to compare a wide range of models in a fair manner, rather than discarding old datasets, as new datasets are challenging only for the latest  models.\n\n---\n\n> S3, point 1: 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.\n\nWe agree and have added a figure in the common response PDF for reference. We will add this in the revised draft, and believe this will significantly improve the clarity of the sort and search method (section 3). Thank you for highlighting this!\n\n---\n\n> S3, point 2: 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.\n\nWe plan to include the framework figure to improve clarity of Section 3, and space permitting we will also include the algorithm in the main paper.\n\n---\n\n> S3, point 3: 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.\n\nWe agree and have shifted this to Section 3. Thank you for pointing this out!\n\n---\n\n> S3, point 4: 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)\n\nWe will add details about an overview of our results at the start of the experimental evaluation section in the revised draft. \n\n---\n\n> Q 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?\n\nYes, this is the assumption underlying our algorithm. We test the generalizability of permutation matrix $\\mathbf{P}^*$ empirically towards new, incoming models in detail in Appendix D: How Consistently Do Models Follow Global Ranking?, where we find that model predictions are correlated, i.e. if a model does well on a “hard” sample s, it does perform well on most samples sorted as easier than s. \n\n---\n\n> Q b) How do you know/compute matrix Y, the optimal ranked accuracy prediction matrix?\n\nThis is explained in detail in l.187 (i) How to get the optimal  ranked accuracy prediction matrix. To summarize: We use DP-search to compute the matrix Y \n\n---\n\n> Q c) Did you come up 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.\n\nDynamic programming is a classical set of algorithms (like greedy algorithms). Our contribution is in formulating the solution to the search  as a dynamic programming problem and proving that it is the optimal solution for searching. \n\nOn the broader point, our main contributions are as follows:\n\n- Providing Sort&Search, a novel efficient model evaluation on an unexplored setting of lifelong benchmarks\n    - Showing our simple framework is far more scalable and allows saving 1000x evaluation cost.\n- Novel decomposition of errors in Sort&Search into largely independent sub-components (aleatoric and epistemic errors)\n    - Proving theoretically and empirically that our solution for the search subcomponent reaches the optimal solution (in Figure 4).\n\n---\n\n> Q 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) \n\nTo clarify, Section 3.1.2 ended with the theorem. The last statement is a summary of  Section 3.1, which we should clarify by adding a “Summary:” to the start and correcting this to \"Now, Ranking by Sort provides a $\\mathbf{P}^*$ from the input data matrix, this permutation matrix orders the samples from easy to hard.\"\n\n---\n\n> Q e) Line 191: \"We want to find the best n′ observations\" -- best with respect to what?\n\nWe corrected this to “We want to find the $n′$ most informative observations from the $n$ samples” to clarify best and w.r.t what.\n\n---\n\n> Comment1) [line 131] What does EM stand for?\n\nEM stands for expectation maximization. Sorry for the confusion, we will correct this and write the full term.\n\n---\n\n> Observation1) [line 110] Typo on operation 2 -- I believe it should be insert_M\n\nThank you for pointing this out, will correct this right away!\n\n---\n\n> Limitations 1) 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?)\n\nThank you for the question. We discuss extensibility of our setup in comment below-- it is not particularly a limitation of our framework, however present limitations in detail in Appendix I: Limitations & Open Problems.\n\nWe hope we have addressed the major concerns of the reviewer, and are happy to answer any further concerns. We look forward to a fruitful reviewer-author discussion phase.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for finding our work to be ***important in the era of large models*** (Reviewers jvk8, T9R1, bEaJ, tnhy), to have ***strong mathematical formulations and theoretical results*** (Reviewers oB2P, bEaJ, T9R1), and to be ***tackling an important pressing problem with sound empirical results*** (Reviewers jvk8, T9R1, bEaJ). We provide detailed responses to each individual reviewer independently, and summarize the most important common points and additional experiments and visualizations provided in the rebuttal here:

- We have added a **detailed visualization of the Sort & Search method** in the uploaded PDF. We hope that this figure improves the clarity of our paper, and we will ensure to add this into section 3 of the revised version.
- We emphasise that **our framework is domain- and task-agnostic**. We summarize below how our Sort & Search framework can be extended to tasks beyond classification. 
  - **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 to various tasks and domains, including language modeling.
- We extend our results from fig 2 to n’={64,000, 128,000, 256,000, 512,000} and add these plots in the common PDF. We observe that the **absolute error (MAE) does not further reduce as we increase the sampling budget**, corroborating the point in sec 4.6 that **additional sampling does not decrease the MAE**.
- We conduct an additional experiment to **serially add new models using the Sort & Search** predictions as ground truth for further additions. We observe that the **errors do not accumulate with consecutive serial applications of our Sort & Search framework**. We provide a simple intuitive proof for why this is the case. This further **showcases the robustness of our method in being applicable without introducing cascading errors**.

Meta-review: 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.
Decision: Accept (poster)