# Optimal-order randomized *k*-server on arbitrary metrics > Randomized k-server costs at most a squared-logarithm factor on every space, matching the known lower bound. Canonical: https://closedform.nishachay.tech/e/openai-math-2026-110/ Last updated: 2026-10-11 **Randomized k-server costs at most a squared-logarithm factor on every space, matching the known lower bound.** **Trust:** Formal proof listed · **Papers:** 2 · **First paper:** September 24, 2026 · **Field:** Theoretical computer science · **Entry:** 110 *Explained by AI.* Drafted by one AI model and checked sentence by sentence against the paper by a different one. Spot a mistake? Report an error. In the k-server problem, k movable servers answer calls in a space, paying the distance moved. This paper proves that a coin-flipping rule can stay within a fixed number times (log(k+1))² of the best cost in hindsight. It holds on every space, even infinite ones. A 2023 result showed that some spaces force a factor of this order. A companion paper makes the rule computable on finite spaces, but its fixed extra cost may be enormous. ## At a glance - **First step:** 2023 (Bubeck, Coester and Rabani, the squared-logarithmic lower bound) - **Significance:** Major. If it holds, it settles the order of the randomized k-server ratio on every space. The number of points drops out. - **Trust:** Formal proof listed - **Field:** Theoretical computer science (2 papers) ## The explanation Picture three spots, A, B and C, each one mile from the other two. You run two repair vans, parked at A and B. Calls arrive one at a time. A van must drive to each called spot, and you pay for every mile. Say the calls run C, A, B, C, A, B, and so on, twelve calls in all. One simple rule sends the van whose spot was called longest ago. On this list it drives every single time, 12 miles in total. Someone who knew the whole list in advance would drive only 6. This is the k-server problem, here with k = 2 servers (movable units, like the vans). An online rule (one that must act before seeing later calls) is judged by its competitive ratio. That is the worst factor by which its cost exceeds the best cost in hindsight. A fixed extra amount is allowed. Mark Manasse, Lyle McGeoch and Daniel Sleator introduced the problem. They showed that no fixed rule beats a ratio of k on a space with more than k points. The example hints why. Calls can always target the one empty spot. Coin flips help. A rule that flips coins can hide its next move. The list of calls must then be fixed in advance, without seeing the coins. This setting is called an oblivious adversary. When all distances are equal, the problem is called paging. There, McGeoch and Sleator reached the best possible ratio, 1 + 1/2 + … + 1/k. For k = 100 that sum is about 5.19, against 100 for rules without coins. It grows like the natural logarithm of k (ln 100 is about 4.6). Many expected a logarithmic ratio on every space. That guess was the randomized k-server conjecture. In 2023, Sébastien Bubeck, Christian Coester and Yuval Rabani disproved it. They built spaces with k + 1 points that force a ratio of order (log k)², the logarithm squared. So the squared logarithm is the best order one can hope for on every space. Upper bounds lagged behind. In 2015, Bansal, Buchbinder, Mądry and Naor gave the first bound in powers of logarithms for finite spaces. Its bound also grows with n, the number of points. In 2018, Bubeck, Cohen, Lee, Lee and Mądry reached (log k)² on special tree-shaped spaces. Carrying that to a general space costs an extra factor of log n. James Lee proposed trees that change as calls arrive, but his general claim was withdrawn after a gap. The first paper proves a ratio of C times (log(k+1))² on every space, for one fixed number C[1]. The same C works for every space and every k of at least 2. The space needs at least k + 1 points. It may be infinite, and its distances may be unbounded[2]. For each space and starting position, one rule handles every finite list of calls. A fixed extra amount, B, is allowed, depending on the space and the start but not on the list[3]. If the servers start at different points, B is zero. The single difficulty was the size of the space. A fixed tree picture of a space distorts its distances by a factor that grows with n. The paper lets its grouping of points change as calls come in[4]. It steers those changes by where a hidden best solution is likely to be. It then charges each change against real movement, so the changes stay affordable. One logarithm comes from the changing groups and one from sharing servers down the tree[5]. Return to the vans and scale up. The theorem does not say how large C is. So it does not promise beating a ratio of 100 at k = 100. Its force is in how slowly the bound grows. At k = 100, (ln 101)² is about 21.3. At k = 1,000, (ln 1,001)² is about 47.7. The number of servers grew tenfold, and that factor grew about 2.2-fold. The number of points, even infinitely many, no longer enters it. The first paper does not claim its rule can be computed quickly[2]. The second paper claims to fill part of that gap, for finite spaces with rational distances. It builds one algorithm whose setup time is polynomial (bounded by a fixed power) in the input's length in bits[6]. The time for call number t may also grow with the number of binary digits of t. The price sits in the extra amount B. It is finite but may be enormous. The algorithm may serve a huge number of early calls with one fixed server before its full rule takes over[7]. Coester and Cosson had faster methods, but their ratio on general spaces keeps a log n factor. How sure is this? A computer proof checker called Lean has checked formal versions of both main statements, according to the Lean scope note. They are the squared-logarithmic bound on every space and the computable algorithm on finite rational spaces. The note does not claim the extra amount B is polynomially bounded. No specialist review of either paper has been published. **What it doesn't show.** This does not give the size of the constant C or a useful bound on the extra startup cost. ## Where it came from This result comes from an unreleased OpenAI model, published in the openai/math release on 6 October 2026. ## Hype check Major if the proofs hold. Lean has checked formal versions of both main statements. The constant C has no stated size. The startup cost may be enormous. No specialist review is published. ## Words used - **k-server problem:** Moving k servers around a space to answer calls at points, paying the distance moved. - **Competitive ratio:** The worst factor by which an online rule's cost exceeds the best cost in hindsight, up to a fixed extra amount. - **Online rule:** A rule that must act on each call before seeing the later ones. - **Oblivious adversary:** A model where the list of calls is fixed in advance, without seeing the rule's coin flips. - **Paging:** The k-server problem when all distances between points are equal, as in a computer cache. - **Natural logarithm:** The power to which the number e, about 2.718, must be raised to give a number; ln 100 is about 4.6. - **Polynomial time:** Running time bounded by a fixed power of the input's length. - **Metric space:** A set of points with a distance between every pair that obeys the usual triangle rule. ## The original papers (2) - [Squared-logarithmic randomized k-server on arbitrary metrics](https://github.com/openai/math/blob/main/preprints/Squared-logarithmic-randomized-k-server-on-arbitrary-metrics-September-24-2026/Squared-logarithmic-randomized-k-server-on-arbitrary-metrics-September-24-2026.pdf) - September 24, 2026 - [Uniform computation of the squared-logarithmic k-server bound](https://github.com/openai/math/blob/main/preprints/Uniform-computation-of-the-squared-logarithmic-k-server-bound-September-24-2026/Uniform-computation-of-the-squared-logarithmic-k-server-bound-September-24-2026.pdf) - September 24, 2026 - [Lean notes](https://github.com/openai/math/blob/main/lean/docs/110.md) ## Quoted lines from the paper (7) [1] From [Squared-logarithmic randomized k-server on arbitrary metrics](https://github.com/openai/math/blob/main/preprints/Squared-logarithmic-randomized-k-server-on-arbitrary-metrics-September-24-2026/Squared-logarithmic-randomized-k-server-on-arbitrary-metrics-September-24-2026.pdf): > There is an absolute constant \(C<\infty\) such that, for every integer \(k\ge2\), every metric space \((X,d)\) with at least \(k+1\) points, and every \(s\in X^k\), there exist a randomized online policy \(A\) and a finite \(B\ge0\) satisfying \begin{equation} \E\,\cost_{A,s}(\sigma) \le C\bigl(\log(k+1)\bigr)^2\OPT_{X,d,k,s}(\sigma)+B \end{equation} for every finite request sequence \(\sigma\). [2] From [Squared-logarithmic randomized k-server on arbitrary metrics](https://github.com/openai/math/blob/main/preprints/Squared-logarithmic-randomized-k-server-on-arbitrary-metrics-September-24-2026/Squared-logarithmic-randomized-k-server-on-arbitrary-metrics-September-24-2026.pdf): > There is no finiteness, boundedness, or discreteness assumption on \(X\), and no computational-efficiency claim for the policy. [3] From [Squared-logarithmic randomized k-server on arbitrary metrics](https://github.com/openai/math/blob/main/preprints/Squared-logarithmic-randomized-k-server-on-arbitrary-metrics-September-24-2026/Squared-logarithmic-randomized-k-server-on-arbitrary-metrics-September-24-2026.pdf): > The same policy serves all finite sequences and horizons. If the initial positions are distinct, one may take \(B=0\). [4] From [Squared-logarithmic randomized k-server on arbitrary metrics](https://github.com/openai/math/blob/main/preprints/Squared-logarithmic-randomized-k-server-on-arbitrary-metrics-September-24-2026/Squared-logarithmic-randomized-k-server-on-arbitrary-metrics-September-24-2026.pdf): > Heavy-ball protection and accounting for changing partitions are methodological antecedents of our construction. Here the partition schedule is driven by the posterior measure of a hidden comparator; it produces a fixed tree of label strings. [5] From [Squared-logarithmic randomized k-server on arbitrary metrics](https://github.com/openai/math/blob/main/preprints/Squared-logarithmic-randomized-k-server-on-arbitrary-metrics-September-24-2026/Squared-logarithmic-randomized-k-server-on-arbitrary-metrics-September-24-2026.pdf): > One logarithm comes from the partition estimate and one from the allocation estimate; rounding and realization preserve their product. [6] From [Uniform computation of the squared-logarithmic k-server bound](https://github.com/openai/math/blob/main/preprints/Uniform-computation-of-the-squared-logarithmic-k-server-bound-September-24-2026/Uniform-computation-of-the-squared-logarithmic-k-server-bound-September-24-2026.pdf): > A single uniform randomized online algorithm preprocesses these data in at most \(p(L)\) bit operations and serves request \(r_t\), for every reachable history and internal state, in at most \[ p\!\left(L+\left\lceil\log_2(t+1)\right\rceil\right) \] additional bit operations. [7] From [Uniform computation of the squared-logarithmic k-server bound](https://github.com/openai/math/blob/main/preprints/Uniform-computation-of-the-squared-logarithmic-k-server-bound-September-24-2026/Uniform-computation-of-the-squared-logarithmic-k-server-bound-September-24-2026.pdf): > Our algorithm serves requests immediately, but may serve an enormous initial number of them using one fixed label before the constructed policy takes over. ## Other sources - [M. S. Manasse, L. A. McGeoch and D. D. Sleator, “Competitive Algorithms for Server Problems”, Journal of Algorithms 11(2) (1990), 208–230](https://doi.org/10.1016/0196-6774(90)90003-W) - [L. A. McGeoch and D. D. Sleator, “A Strongly Competitive Randomized Paging Algorithm”, Algorithmica 6 (1991), 816–825](https://doi.org/10.1007/BF01759073) - [S. Bubeck, C. Coester and Y. Rabani, “The Randomized k-Server Conjecture Is False!”, STOC 2023, 581–594](https://doi.org/10.1145/3564246.3585132) - [N. Bansal, N. Buchbinder, A. Mądry and J. Naor, “A Polylogarithmic-Competitive Algorithm for the k-Server Problem”, Journal of the ACM 62(5) (2015)](https://doi.org/10.1145/2783434) - [S. Bubeck, M. B. Cohen, J. R. Lee, Y. T. Lee and A. Mądry, “k-Server via Multiscale Entropic Regularization”, STOC 2018, 3–16](https://doi.org/10.1145/3188745.3188798) - [J. R. Lee, “Fusible HSTs and the Randomized k-Server Conjecture”, FOCS 2018, and erratum](https://homes.cs.washington.edu/~jrl/papers/kserver-erratum.html) - [C. Coester and R. Cosson, “Randomized k-Server in Polynomial Time”, ICALP 2026, LIPIcs 374, 65:1–65:20](https://doi.org/10.4230/LIPIcs.ICALP.2026.65) - [openai/math release notes (2026): model provenance and review status](https://github.com/openai/math/blob/main/README.md): “manuscripts and supporting proof artifacts produced by an internal OpenAI model” ## Related - [Integer multiplication below n log n](https://closedform.nishachay.tech/e/openai-math-2026-109/) - Theoretical computer science - [One-sample matroid prophet inequalities against an almighty adversary](https://closedform.nishachay.tech/e/openai-math-2026-111/) - Theoretical computer science - [A cubic permanent–determinant lower bound](https://closedform.nishachay.tech/e/openai-math-2026-108/) - Theoretical computer science - [Beyond the square-root exponent for depth-three circuits](https://closedform.nishachay.tech/e/openai-math-2026-112/) - Theoretical computer science - [Matrix multiplication with exponent at most 9/4](https://closedform.nishachay.tech/e/openai-math-2026-107/) - Theoretical computer science - [Theoretical computer science](https://closedform.nishachay.tech/science/mathematics/theoretical-computer-science/) - Field · 40 results - [Open since the 2020s](https://closedform.nishachay.tech/open-since/2020s/) - Era · 9 results - [Lean-checked results](https://closedform.nishachay.tech/trust/lean-checked/) - Trust · 242 results - [Report an error](https://github.com/nishachay/closed-form/issues/new?template=report-error.yml&labels=entry-error&title=%5Bentry%20110%5D%20)