- Rating
- 3
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
This paper studies the minimum additional evaluation cost required to improve estimates of model performance differences when a shared evaluation cache is already available. For multiple candidates compared against a common reference, Theorems 1–2 identify an exact precision threshold. With a fixed cache size, the optimal additional work is bounded above the threshold, grows as Θ(√M) at the threshold, and grows linearly below it. The authors also establish matching lower bounds for adaptive acquisition and determine the critical leading constant when both the cache size and the number of candidates grow. The paper further examines different accuracy requirements, derives an exact minimax risk characterization for balanced partial observations, and establishes high-precision work bounds for general comparison graphs. Numerical and frozen-score experiments illustrate these results.
Critical strengths
The main theoretical results are solid. For a fixed cache size, Theorem 1 establishes tight asymptotic orders for additional evaluation work in three precision regimes. Theorem 2 further determines the critical cost as (2+o(1))h√M when both h and M tend to infinity. Importantly, the lower bounds allow adaptive sampling, randomization, and stopping. Thus, the paper characterizes the optimal cost under its model, rather than merely analyzing a particular sampling method. This is my main reason for supporting acceptance.
The theoretical analysis has meaningful novelty. Although the minimax estimation result for a single bounded mean is classical, the paper shows how the remaining uncertainty in a finite cache determines the evaluation cost of an entire model library. The proof uses a common product prior to control the adaptive observation counts of all candidates, which is important for obtaining the lower bounds. The exact threshold also matters beyond constant-factor improvements, since replacing it with a first-order approximation can lead to the wrong cost regime.
Critical weaknesses
The strongest results still rely on a specific model. The tight three-regime characterization is established for equally sized complete caches, comparisons against a common reference, and marginal MSE. Although the paper also considers general comparison graphs, the asymptotically optimal work bound in Theorem 5 assumes d→0 and dh→0, and does not extend the full finite-cache transition to general comparison structures. Therefore, I regard this as a solid result for the proposed model, but its implications for more general evaluation allocation problems remain limited.
The broader significance of the critical regime is not sufficiently established. The square-root scaling occurs at the exact precision threshold, within a narrow transition region. Moreover, Theorem 3 shows that requiring every realized allocation to satisfy the error target can increase the critical cost to linear order. In Table 1, for M=10 and M=19, randomized and deterministic plans have the same evaluation work. The savings mainly come from sharing the reference rather than randomization. Larger controlled examples do demonstrate a separation, but it remains unclear how representative this regime is of practical model evaluation. This is my main reservation about the significance of the paper.
Questions for authors
The square-root scaling at the precision threshold is one of the most interesting results of the paper, but it depends on the precision target and the accuracy requirement. Could the authors clarify which natural model evaluation tasks would require precision close to d0(h), and why marginal MSE is the appropriate guarantee in those settings? In particular, since Table 1 does not show an additional work saving from randomization at the tested library sizes, how should we understand the practical significance of the critical regime?