The benchmark studies potentials over work functions for the k-server problem.
A work function assigns a value to each configuration of k servers. Intuitively, that value is the minimum cost needed to serve the request sequence seen so far and end in that configuration.
The evaluators operate on normalized work functions induced by precomputed metric instances. Candidate potentials are judged on how they change across transitions in those instances.
A potential is a function Phi(w) from a work function w to a scalar.
In this repository, potentials usually appear in one of two forms:
- a direct
Potentialclass used by the non-legacy evaluator - a combination of
PotentialFamily,Potential, andSearchEvaluatorused by the legacy evaluator
The benchmark includes a strong bias toward canonical potentials, where the candidate searches over a structured family described by:
nindex_matrixcoefs
Those objects encode a minimization over metric space points and antipodes. The relevant hint text lives under tasks/hints/canonical-potential/.
Metric instances are precomputed state graphs stored as pickles under metrics/.
Each instance packages:
- a
WFContext - the explored nodes and edges
- Bellman-style information used during scoring
The released benchmark mostly uses small but mathematically meaningful circle and circle-taxi instances. Smaller instances are often genuine subproblems of harder ones, which is why they are useful for proxy search rather than just random approximations.
The main benchmark objective is minimizing violations_k.
At a high level, the potential is checked across many edges of the instance graph. A violation means the potential change does not certify the desired inequality on that transition.
Important score fields include:
violations_kviolations_k_scorecombined_scoreprocessed_normalized_edges_score
The ideal result is zero violations on every evaluated metric, which corresponds to a perfect multiplicative score of 1.0.
Many candidate programs do not expose a fully fixed potential directly. Instead, they search for good hyperparameters within a time and CPU budget.
That leads to a two-stage picture:
- search logic proposes
potential_kwargs - the evaluator instantiates the final potential and scores it on the full metrics
This separation is central to the benchmark design. The search procedure is allowed to use proxy evaluations, but the final scoring is always done by the benchmark evaluator.