Efficient Lifelong Model Evaluation in an Era of Rapid Progress

We sincerely thank the reviewer for their thorough evaluation and positive, enouraging feedback. We seek to address the reviewer’s concerns and questions below:

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?

Our 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.

Lifelong 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.

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.

We 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!

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.

We 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.

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.

We agree and have shifted this to Section 3. Thank you for pointing this out!

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)

We will add details about an overview of our results at the start of the experimental evaluation section in the revised draft.

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?

Yes, 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.

Q b) How do you know/compute matrix Y, the optimal ranked accuracy prediction matrix?

This 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

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.

Dynamic 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.

On the broader point, our main contributions are as follows:

• Providing Sort&Search, a novel efficient model evaluation on an unexplored setting of lifelong benchmarks
  • Showing our simple framework is far more scalable and allows saving 1000x evaluation cost.
• Novel decomposition of errors in Sort&Search into largely independent sub-components (aleatoric and epistemic errors)
  • Proving theoretically and empirically that our solution for the search subcomponent reaches the optimal solution (in Figure 4).

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)

To 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."

Q e) Line 191: "We want to find the best n′ observations" -- best with respect to what?

We corrected this to “We want to find the $n′$ most informative observations from the $n$ samples” to clarify best and w.r.t what.

Comment1) [line 131] What does EM stand for?

EM stands for expectation maximization. Sorry for the confusion, we will correct this and write the full term.

Observation1) [line 110] Typo on operation 2 -- I believe it should be insert_M

Thank you for pointing this out, will correct this right away!

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?)

Thank 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.

We 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.

Q f) You present S&S as a framework. If I wanted to leverage different performance metrics to evaluate the models, how would I go about updating the framework to use the new metric?

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

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

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

We hope this clarifies the adaptability of our framework.

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

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

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

We sincerely thank the reviewer for their thorough evaluation and their detailed feedback. We seek to address the reviewer’s concerns and suggestions below:

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.

While MAE serves as a useful proxy metric for algorithm development, it is not a necessary requirement to provide practical applications. In particular, for many use-cases, it is the ranking of the models, rather than their absolute metrics, that are of primary importance for informing downstream decisions about which model to use.

To illustrate a practical application, we examine whether Sort&Search preserves the ranking of models at high sampling efficiency. Specifically, we conducted an experiment by changing the evaluation metric from MAE to Spearman correlation between the rankings of 25,250 models using Sort & Search and the rankings obtained after full sample evaluation on Lifelong-CIFAR10. The results, presented in the attached PDF, show a consistently high correlation of 0.5. We believe this demonstrates the framework's applicability for practical use-cases.

Furthermore, we provide interesting, concrete avenues for improving the sorting algorithm in point (2) in Appendix I – Limitations and Open Problems of our work.

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?

Thank 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.

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?

Thank 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:

Consider 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.

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$.

We shall formalize this and include these results alongside our point (1) in Appendix I – Limitations and Open Problems.

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)

We 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.

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)

We 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.

We 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.

Thank you for the detailed response. For the author response of W1 and W2,

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

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

However, recognizing the Authors' response and the current scope of discourse, I think that it is not necessary to address such aspects of the problem in a single research stride. I will raise my score.

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.

We thank the reviewer for this point. We have sought to answer the questions raised below for clarity.

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?

Thank 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:

• 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.
• 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.
• 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.

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?

We 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.

We 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.

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:

W1/Q1 What are the MSE results of applying uniform/random sampling directly to the sample pool without using the sort algorithm?

We 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.

We show in Figure 2(c) and 3(b) that our Sort & Search algorithm outperforms this baseline by significant margins, discussed in the next question.

W2/Q2 What is a reasonable target for MSE, and how difficult is it to improve MSE by 0.01?

Improving 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.

The 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.

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?

Thank 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.

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.

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?

Thank 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:

• 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.

W5 Minor issue: In Appendix H, the text is overlapped and needs formatting correction.

Thank you for bringing this to our notice, we missed this. We have corrected this!

We 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.

We thank the reviewer for their detailed feedback. We seek to address the reviewer’s concerns and suggestions below:

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.

Thank 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:

• 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 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.