Kendall Target

kendall-target

Efficiently Ranking Software Variants with Minimal Benchmarks — Matricon et al. (2025) (arXiv:2509.06716, 2025)

What this evaluates

Evaluates whether a reduced subset of benchmark tests preserves the relative performance ranking of software variants compared to a full test suite. It probes the fidelity of black-box performance comparisons when benchmark execution costs are minimized.

Datasets

• General Software Variant Benchmarks — total ?; splits: test (-1)

Metrics

• Kendall target (primary) — range: [-1, 1]
  • A threshold-based check on Kendall rank correlation. The algorithm computes rankings on the full test suite and on the candidate subset (using optimized linear regression weights), then verifies if the Kendall correlation between the two rankings meets a predefined target value.

Input / output format

Input: A performance matrix P (variants × tests) and a candidate test subset T′.

Output: A boolean indicating whether the subset T′ achieves the target Kendall rank correlation with the full suite, or the optimized weight vector W and resulting ranking.

Scoring recipe

def check_kendall_target(P_full, T_subset, variants, target_kendall):
    # 1. Compute full-suite ranking (e.g., sum of performances)
    full_scores = P_full.sum(axis=1)
    full_rank = rank(full_scores)
    # 2. Optimize weights W via linear regression on subset
    W = np.linalg.lstsq(P_full[:, T_subset], full_scores, rcond=None)[0]
    # 3. Compute subset ranking using optimized weights
    subset_scores = P_full[:, T_subset] @ W
    subset_rank = rank(subset_scores)
    # 4. Calculate Kendall correlation
    kendall_val = kendalltau(full_rank, subset_rank).correlation
    return kendall_val >= target_kendall

Common pitfalls

• Assuming the evaluation metric cares about absolute performance magnitudes; the protocol explicitly ignores magnitude differences and only tracks ordinal ranking preservation.
• Failing to re-optimize the weight vector W for each candidate subset, which is required to fairly compare rankings across different test sizes.
• Treating the problem as a standard regression task instead of a combinatorial search for ranking stability.

Evidence (verbatim from paper)

checks if the Kendall target is reached with T′ as a solution to the problem with the complete test set being T, if it is, then the procedure returns true otherwise, it returns false.

Citation

@misc{matricon2025efficiently,
  title={Efficiently Ranking Software Variants with Minimal Benchmarks},
  author={Matricon et al. (2025)},
  year={2025},
  note={arXiv:2509.06716}
}

• arXiv: 2509.06716