Evaluation metrics

Deep dive

How it works

In: true labels or relevances, model scores or predictions, a test set · Out: metric values and a confidence interval for the difference between two models · State: none · Cost: O(n) threshold metrics, O(n log n) AUC and AP, O(B·n) bootstrap

AUC by ranks. Sort all scores, assign ranks 1..n with ties getting the average rank. AUC = (Σ ranks of positives − n₊(n₊+1)/2) / (n₊·n₋). One sort, exact tie handling.

Paired bootstrap. Resample test indices with replacement B times (B = 1000-10000). For each resample compute metric(A) − metric(B) on the same indices. The 2.5 and 97.5 percentiles give a 95 % interval for the difference. If it excludes 0, the gap is unlikely to be test-set noise.

McNemar for two classifiers: count b = A right and B wrong, c = A wrong and B right. χ² = (|b − c| − 1)²/(b + c) with 1 degree of freedom.

Code

fn ranks_avg(scores: &[f64]) -> Vec<f64> {                // 1-based ranks; ties get their mean rank
    let mut idx: Vec<usize> = (0..scores.len()).collect();
    idx.sort_by(|&a, &b| scores[a].partial_cmp(&scores[b]).unwrap());
    let mut r = vec![0.0; scores.len()];
    let mut i = 0;
    while i < idx.len() {
        let mut j = i;
        while j + 1 < idx.len() && scores[idx[j + 1]] == scores[idx[i]] { j += 1; }
        let avg = (i + j) as f64 / 2.0 + 1.0;
        for k in i..=j { r[idx[k]] = avg; }
        i = j + 1;
    }
    r
}

pub fn roc_auc(y: &[bool], s: &[f64]) -> f64 {
    let r = ranks_avg(s);
    let np = y.iter().filter(|&&v| v).count() as f64;
    let nn = y.len() as f64 - np;
    let sum_pos: f64 = r.iter().zip(y).filter(|(_, &v)| v).map(|(x, _)| x).sum();
    (sum_pos - np * (np + 1.0) / 2.0) / (np * nn)
}

/// Average precision: sum over positives of precision at their rank (ties broken by order).
pub fn average_precision(y: &[bool], s: &[f64]) -> f64 {
    let mut idx: Vec<usize> = (0..s.len()).collect();
    idx.sort_by(|&a, &b| s[b].partial_cmp(&s[a]).unwrap());
    let total = y.iter().filter(|&&v| v).count() as f64;
    let (mut tp, mut ap) = (0.0, 0.0);
    for (k, &i) in idx.iter().enumerate() {
        if y[i] { tp += 1.0; ap += tp / (k + 1) as f64; }
    }
    ap / total
}

pub fn prf1(y: &[bool], s: &[f64], thr: f64) -> (f64, f64, f64) {
    let (mut tp, mut fp, mut fneg) = (0.0f64, 0.0f64, 0.0f64);
    for (&t, &v) in y.iter().zip(s) {
        match (v >= thr, t) { (true, true) => tp += 1.0, (true, false) => fp += 1.0, (false, true) => fneg += 1.0, _ => {} }
    }
    let (p, r) = (tp / (tp + fp).max(1.0), tp / (tp + fneg).max(1.0));
    (p, r, if p + r > 0.0 { 2.0 * p * r / (p + r) } else { 0.0 })
}

pub fn log_loss(y: &[bool], p: &[f64]) -> f64 {
    let eps = 1e-15;                                         // clip: one p = 0 on a positive is infinite loss
    y.iter().zip(p).map(|(&t, &q)| { let q = q.clamp(eps, 1.0 - eps); -(if t { q.ln() } else { (1.0 - q).ln() }) })
        .sum::<f64>() / y.len() as f64
}

pub fn ndcg_at_k(rel_in_ranked_order: &[f64], k: usize) -> f64 {
    let dcg = |r: &[f64]| r.iter().take(k).enumerate().map(|(i, &g)| (2f64.powf(g) - 1.0) / (i as f64 + 2.0).log2()).sum::<f64>();
    let mut ideal = rel_in_ranked_order.to_vec();
    ideal.sort_by(|a, b| b.partial_cmp(a).unwrap());
    let id = dcg(&ideal);
    if id == 0.0 { 0.0 } else { dcg(rel_in_ranked_order) / id }
}

/// Unbiased pass@k from n samples with c correct (Chen et al. 2021), as a stable product.
pub fn pass_at_k(n: u64, c: u64, k: u64) -> f64 {
    if n - c < k { return 1.0; }
    1.0 - ((n - c + 1)..=n).map(|i| 1.0 - k as f64 / i as f64).product::<f64>()
}

/// Paired bootstrap 95 % interval of metric(A) − metric(B) on the same test examples.
pub fn paired_bootstrap(y: &[bool], sa: &[f64], sb: &[f64], metric: fn(&[bool], &[f64]) -> f64,
                        reps: usize, seed: u64) -> (f64, f64) {
    let mut st = seed | 1;
    let n = y.len();
    let mut diffs: Vec<f64> = (0..reps).map(|_| {
        let ix: Vec<usize> = (0..n).map(|_| { st ^= st << 13; st ^= st >> 7; st ^= st << 17; (st % n as u64) as usize }).collect();
        let yy: Vec<bool> = ix.iter().map(|&i| y[i]).collect();
        let a: Vec<f64> = ix.iter().map(|&i| sa[i]).collect();
        let b: Vec<f64> = ix.iter().map(|&i| sb[i]).collect();
        metric(&yy, &a) - metric(&yy, &b)
    }).collect();
    diffs.sort_by(|a, b| a.partial_cmp(b).unwrap());
    (diffs[reps * 25 / 1000], diffs[reps * 975 / 1000])
}

fn main() {
    let n = 2000;
    let mut s = 99u64;
    let mut u = || { s ^= s << 13; s ^= s >> 7; s ^= s << 17; (s >> 11) as f64 / (1u64 << 53) as f64 };
    let y: Vec<bool> = (0..n).map(|_| u() < 0.1).collect();       // 10 % positives
    let sa: Vec<f64> = y.iter().map(|&t| if t { 0.6 } else { 0.4 } + 0.3 * (u() - 0.5)).collect();
    let sb: Vec<f64> = y.iter().map(|&t| if t { 0.55 } else { 0.45 } + 0.3 * (u() - 0.5)).collect();
    println!("AUC A {:.3}  B {:.3}; AP A {:.3} B {:.3} (prevalence ≈ 0.1)",
             roc_auc(&y, &sa), roc_auc(&y, &sb), average_precision(&y, &sa), average_precision(&y, &sb));
    println!("P/R/F1 of A at 0.5: {:.3?}, log loss A {:.3}", prf1(&y, &sa, 0.5), log_loss(&y, &sa));
    println!("AUC(A) − AUC(B) 95% CI: {:.3?}", paired_bootstrap(&y, &sa, &sb, roc_auc, 1000, 5));
    assert!((roc_auc(&[true, false, true, false], &[0.5, 0.5, 0.9, 0.1]) - 0.875).abs() < 1e-12); // tie = ½
    println!("NDCG@3 {:.3}, pass@10 (n=100, c=5) {:.3}", ndcg_at_k(&[3.0, 2.0, 0.0, 1.0], 3), pass_at_k(100, 5, 10));
}

Complexity and constants

• AUC and AP: one O(n log n) sort; 10⁷ scores sort in order of a second.
• Bootstrap: B × metric cost. With B = 1000 and an O(n log n) metric on 10⁵ examples, order of seconds to tens of seconds. Pre-sorting does not survive resampling, so use multinomial counts per example if it is too slow.
• Standard errors scale as 1/√n: halving the interval needs 4x the test examples. A 0.5-point accuracy difference needs order of 10⁴ examples (more if the models disagree often) to resolve reliably.

Efficiency

• Cost: accuracy, F1 and log loss are one O(n) pass. AUC and AP need one sort, O(n log n): 10⁷ scores in order of a second (this page). Memory is 8-12 bytes per example (score plus label). A bootstrap multiplies the cost by B (1000 typical). All of it is small next to running the model; the expensive resource is test examples, since standard error scales as 1/√n and halving it needs 4x the data.
• Levers:
  • Sort once, derive AUC, AP and the full curve from it — one sort instead of one per metric (this page) — ranking metrics.
  • Accumulate confusion counts or score histograms — O(1) memory, mergeable across devices (TorchMetrics) — evaluation during training.
  • Paired test (McNemar) on the same examples — resolves differences that independent intervals cannot (McNemar 1947; Dietterich 1998) — comparing two models.
  • SPRT early stopping — ends a match once the evidence is enough (fishtest) — engine and A/B comparisons.
• Naive → standard → state of the art:
  • Recompute each metric from raw predictions, point estimate only · k passes, no uncertainty
  • One sort, shared curves, bootstrap interval · O(B·n log n)
  • Streaming counts, paired test or SPRT · O(1) memory, fewer examples

Implementation notes

• Choose thresholds on validation data, never on test. Report the threshold with the precision/recall.
• Multi-class: report macro-F1 (each class equal) and micro-F1 (= accuracy for single-label) or per-class tables. One-vs-rest AUC per class, then average.
• Perplexity depends on the tokenizer: compare models with different vocabularies in bits per byte (total NLL in nats / (ln 2 · bytes)).
• pass@k: generate n ≥ k samples per problem (e.g. n = 200 for k ≤ 100 in the Codex paper) and use the unbiased estimator; c/n raised to a power is biased.
• Games and engines: measure strength by match results converted to Elo, with SPRT for sequential decisions on whether a change helps.
• Log the per-example predictions, not just aggregates. Paired tests and later slicing need them.

Pitfalls

• Test-set reuse: every comparison you make on it leaks information. Keep a final held-out set you rarely touch.
• Leakage: duplicates or near-duplicates across train and test (MinHash), future data in time series, the same user in both splits.
• AUC with ties broken by input order instead of averaged: inflates or deflates the score depending on sorting.
• Average precision computed with trapezoidal interpolation of the PR curve: optimistic. Use the step-wise sum.
• Reporting the best of many seeds without the spread.
• Comparing metrics at different prevalences: precision and AP change with the class ratio even for the same model.

Variants and alternatives

In production

scikit-learn metrics (roc_auc_score, average_precision_score, f1_score, log_loss, ndcg_score), torchmetrics, TREC trec_eval, the HumanEval harness (pass@k), lm-evaluation-harness (perplexity, bits per byte, accuracy); ROC analysis of diagnostic tests in medicine; fishtest for engine releases (SPRT on game pairs).

Implementations

Sources

• Hanley and McNeil, The Meaning and Use of the Area under a Receiver Operating Characteristic (ROC) Curve, Radiology 1982. paper
• Davis and Goadrich, The Relationship Between Precision-Recall and ROC Curves, ICML 2006. paper
• Järvelin and Kekäläinen, Cumulated Gain-Based Evaluation of IR Techniques, ACM TOIS 2002. paper
• Efron, Bootstrap Methods: Another Look at the Jackknife, Annals of Statistics 1979. paper
• McNemar, Note on the Sampling Error of the Difference Between Correlated Proportions or Percentages, Psychometrika 1947. paper
• Dietterich, Approximate Statistical Tests for Comparing Supervised Classification Learning Algorithms, Neural Computation 1998. paper
• Chen et al., Evaluating Large Language Models Trained on Code, 2021 (pass@k). paper · code
• Saito and Rehmsmeier, The Precision-Recall Plot Is More Informative than the ROC Plot When Evaluating Binary Classifiers on Imbalanced Datasets, PLoS ONE 2015. paper