Large Language Models (LLMs) vary in their abilities on a range of tasks. Initiatives such as the Open LLM Leaderboard aim to quantify these differences with several large benchmarks (sets of test items to which an LLM can respond either correctly or incorrectly). However, high correlations within and between benchmark scores suggest that (1) there exists a small set of common underlying abilities that these benchmarks measure, and (2) items tap into redundant information and the benchmarks may thus be considerably compressed. We use data from n > 5000 LLMs to identify the most informative items of six benchmarks, ARC, GSM8K, HellaSwag, MMLU, TruthfulQA and WinoGrande (with d = 28,632 items in total). From them we distill a sparse benchmark, metabench, that has less than 3% of the original size of all six benchmarks combined. This new sparse benchmark goes beyond point scores by yielding estimators of the underlying benchmark-specific abilities. We show that these estimators (1) can be used to reconstruct each original individual benchmark score with, on average, 1.24% root mean square error (RMSE), (2) reconstruct the original total score with 0.58% RMSE, and (3) have a single underlying common factor whose Spearman correlation with the total score is r = 0.94.

We consider the distributed complexity of the stable marriage problem. In this problem, the communication graph is undirected and bipartite, and each node ranks its neighbors. Given a matching of the nodes, a pair of nodes is called blocking if they prefer each other to their assigned match. A matching is called stable if it does not induce any blocking pair. In the distributed model, nodes exchange messages in each round over the communication links, until they find a stable matching. We show that if messages may contain at most B bits each, then any distributed algorithm that solves the stable marriage problem requires Omega(sqrt(n/(B log n))) communication rounds in the worst case, even for graphs of diameter Theta (log n), where n is the number of nodes in the graph. Furthermore, the lower bound holds even if we allow the output to contain O(sqrt(n)) blocking pairs. We also consider epsilon-stability, where a pair is called epsilon-blocking if they can improve the quality of their match by more than an epsilon fraction, for some 0

In the stable marriage problem, the communication graph is undirected and bipartite, and each node ranks its neighbors. Given a matching of the nodes, a pair of nodes is called blocking if they prefer each other to their assigned match. A matching is called stable if it does not induce any blocking pair. In the distributed model, nodes exchange messages in each round over the communication links, until they find a stable matching. We show that if messages may contain at most B bits each, then any distributed algorithm that solves the stable marriage problem requires Ω(√n/Blog n) communication rounds in the worst case, even for graphs of diameter Θ(log n), where n is the number of nodes in the graph. The lower bound holds even if the output may contain O(√n) blocking pairs. We also consider ε-stability, where a pair is called ε-blocking if they can improve the quality of their match by more than an ε fraction, for some 0 ≤ ε ≤ 1. Our lower bound extends to ε-stability where ε is arbitrarily close to 1/2. We also present a simple distributed algorithm for ε-stability whose time complexity is O(n/ε).