Certified Corruption Budgets: Anytime-Valid Leaderboard Claims under Adaptive Rigging
Abstract
Public leaderboards for AI models are read continuously, and attackers can see every published standing. Vote rigging, selective disclosure of private variants, and benchmark contamination can each move a ranking. Existing guarantees assume genuine records or bound the corruption per step, which an attacker who corrupts in bursts evades. We introduce the certified corruption budget, a tolerance B̂t computed after t records and published with each pairwise claim. With probability at least 1−α, simultaneously at all times, the claim is correct or more than B̂t records were corrupted. It holds against attackers who watch every certificate, with no bound on their budget. Forged records and records altered once seen require different certificates: the certificate for forgeries fails, with probability approaching one, against an attacker who flips votes it has seen, while one that charges roughly twice as much per record remains valid, with constant bets even against attackers who see the future, and no smaller charge is valid at every level. The certified budget grows nearly as fast as any valid method allows: with a win fraction 1/2+δ, each new record adds close to 2δ to the number of forged records the claim can withstand (δ flipped). Publishing the best of V private variants costs only an amount growing like log V. In replays on 1.8 million Chatbot Arena votes, a few hundred rigged votes make standard confidence intervals certify false orderings, while ours stays valid. On real votes, our certificate shows that clearly separated models withstand about 2,000 forged votes.
Related
- Certified Adaptive Refresh: Anytime-Valid Monitoring for Federated Conformal RAG
- Certified by Abstention: Distribution-Free Guarantees for Chain-of-Thought Verifiers at Small Calibration Budgets
- A general recipe for data-adaptive anytime-valid envelopes for iterative algorithms
- Adaptive auditing of AI systems with anytime-valid guarantees
- The Price of Self-Calibration: Exact Evidence Budgets and Manufactured Blind Sets in Adaptive Monitoring
BibTeX
@misc{khosravi2026certified,
title = {{Certified Corruption Budgets: Anytime-Valid Leaderboard Claims under Adaptive Rigging}},
author = {Hamed Khosravi and Xiaoming Huo},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.10597},
eprint = {2610.10597},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.10597},
}
RIS
TY - UNPB
TI - Certified Corruption Budgets: Anytime-Valid Leaderboard Claims under Adaptive Rigging
AU - Hamed Khosravi
AU - Xiaoming Huo
PY - 2026
DA - 2026/10/06
PB - arXiv
DO - 10.48550/arxiv.2610.10597
UR - https://arxiv.org/abs/2610.10597
AB - Public leaderboards for AI models are read continuously, and attackers can see every published standing. Vote rigging, selective disclosure of private variants, and benchmark contamination can each move a ranking. Existing guarantees assume genuine records or bound the corruption per step, which an attacker who corrupts in bursts evades. We introduce the certified corruption budget, a tolerance B̂_t computed after t records and published with each pairwise claim. With probability at least 1−α, simultaneously at all times, the claim is correct or more than B̂_t records were corrupted. It holds against attackers who watch every certificate, with no bound on their budget. Forged records and records altered once seen require different certificates: the certificate for forgeries fails, with probability approaching one, against an attacker who flips votes it has seen, while one that charges roughly twice as much per record remains valid, with constant bets even against attackers who see the future, and no smaller charge is valid at every level. The certified budget grows nearly as fast as any valid method allows: with a win fraction 1/2+δ, each new record adds close to 2δ to the number of forged records the claim can withstand (δ flipped). Publishing the best of V private variants costs only an amount growing like log V. In replays on 1.8 million Chatbot Arena votes, a few hundred rigged votes make standard confidence intervals certify false orderings, while ours stays valid. On real votes, our certificate shows that clearly separated models withstand about 2,000 forged votes.
ER -