Randomized k-server: competitive ratios and uniform computation

Source and verification

This article explains family 110 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

🏷️ Online service and competitive ratios

In a metric space $(X,d)$, place $k$ labeled servers at an initial tuple $s\in X^k$. Repeated positions are allowed. A request $r_t\in X$ must be served by choosing one server and moving it to $r_t$, leaving the others fixed. An already present server can serve at zero cost.

An online policy sees the request prefix, while the offline optimum knows the entire finite request word $\sigma$. Let ${\mathrm{cost}}_{A,s}(\sigma )$ be the policy’s movement and ${\mathrm{OPT}}_s(\sigma )$ the least offline movement from the same initial positions. A randomized competitive guarantee has the form

$$\mathbb{E}{\mathrm{cost}}_{A,s}(\sigma )\le R_k{\mathrm{OPT}}_s(\sigma )+B.$$

The additive constant may depend on the metric and starting configuration but not on the request word or its length. Requests here are oblivious: the entire word is fixed independently of the policy’s random choices.

For the uniform metric, distinct points have distance one. Servers then represent cached pages, and an absent requested page costs one move. General metrics also charge which cached position is replaced and how far the server travels.

🏷️ A metric-independent existence claim

First manuscript statement

There is an absolute $C$ such that for every $k\ge 2$, every metric space with at least $k+1$ points, and every starting tuple, one randomized online policy satisfies

$$\begin{array}{c}\begin{array}{rl}& \mathbb{E}{\mathrm{cost}}_{A,s}(\sigma )\\ & \le R_k{\mathrm{OPT}}_s(\sigma )+B,\end{array}\\ R_k=C{\log }^2(k+1),\end{array}$$

for all finite request words and horizons. The constant $B$ is finite, and can be zero when the starting positions are distinct. No finiteness or boundedness assumption is imposed on the metric. (OpenAI, 2026)

The policy is not claimed to be efficiently computable on an arbitrary metric. The same policy must work for all horizons; choosing a new policy after learning the request length would be weaker.

The source combines its upper bound with the cited existence of metrics requiring squared-logarithmic competitive ratio. This is a worst-case statement across metrics, not a squared-logarithmic lower bound on every metric. Paging already illustrates why individual metrics can have better behavior.

🏷️ Posterior comparators without future information

The proof first considers a finite metric and a known probability law on requests. Select an offline optimum for each possible word, then condition its trajectory on the revealed prefix. The online construction uses the resulting posterior distributions, not the realized future optimum.

Changing partitions at multiple distance scales assigns each point a string of cell labels. Those strings identify leaves of a fixed tree. Posterior server counts below tree vertices become the input for fractional allocation: how much server mass should be placed in each subtree?

This is a distributional intermediate statement. The final policy cannot rely on being told an arbitrary adversary’s future law. Finite minimax and compactness transfer the family of distributional estimates to a single online policy, and then to arbitrary spaces. The source supplies the consistency and reset arguments needed for that passage.

🏷️ Accounting for exactly two logarithms

The tree allocation estimate contributes one factor $\log (k+1)$. Fractional amounts meet the serving requirement and are bounded by a constant multiple of posterior expected counts. Mass may remain parked at internal vertices while proportions among children change. For a nearly dominant child, the rule allocates to the other children first and assigns the remaining allowed parent amount to that child. This avoids paying another logarithm for incompatible independent caps.

The changing partition estimate contributes the other logarithm. It protects heavy balls around concentrated mass and organizes other requests through bounded chronological rosters. Local ball-mass ratios telescope across scales. Bounding each scale independently by a worst-case logarithm would overcharge the construction.

Two additional costs remain. First, a representative point, or anchor, of parked mass can move even if no mass crosses a tree edge. The source uses a separate potential to pay for this retained-anchor travel. Second, fractional mass must become exactly $k$ integral servers. Its dynamic rounding lemma permits correlated parent and child states and incurs only an absolute factor.

Thus the architecture is allocation times partition loss, with anchor motion and rounding charged within those budgets. A tree movement bound alone would not establish a bound for physical server movement in the original metric.

Independent episodes and reset blocks remove the finite-metric additive term for distinct starts. Compactness then gives one policy for all finite inputs in an arbitrary, possibly unbounded space. Repeated initial positions are handled by a matching simulation, allowing a finite additive term.

🏷️ The uniform computational companion

Second manuscript statement

For a finite rational metric on $n$ points, $2\le k<n$, and total encoded input length $L$, one uniform randomized algorithm has polynomial preprocessing and processes request $t$ in

$$\mathrm{poly}(L+\lceil {\log }_2(t+1)\rceil )$$

bit operations on every reachable history and internal state. It uses unbiased random bits and returns a legal server index at every request. Its expected movement has the same squared-logarithmic competitive form, with a finite instance-dependent additive term. (OpenAI, 2026b)

The additive term is not asserted to be polynomially bounded. Nor is request processing bounded by a polynomial in $L$ alone: the binary length of the request counter is permitted. These qualifications are central to the construction.

For a fixed finite horizon, causal configuration probabilities and transition flows satisfy rational linear constraints. The existence theorem ensures feasibility at a bounded competitive coefficient. Exact elimination produces a finite policy table, and dyadic rounding makes its choices implementable with unbiased bits.

🏷️ A bounded retained word for an unbounded input

A fixed-horizon table cannot directly handle an arbitrarily long word on which the optimum barely moves. A strongly lazy service moves only when the request is unoccupied. The companion filters requests by considering all such services from a fixed distinct starting tuple with a bounded number of positive moves.

Retain a request only if at least one candidate service would miss it. Candidate histories form a tree with at most $k$ branches at a miss and bounded depth. Each retained request removes a live node, and removed nodes do not return. The retained word therefore has bounded length even when the raw word is arbitrarily long.

A table trajectory that exhausts its move budget switches to a deterministic marking fallback. Blocks end at their $(k+1)$st distinct request, and each completed block forces the optimum to move. This pays for restarting between epochs. The block boundaries and filtered words depend only on the raw requests, so the finite table is tested on a fixed word even if the algorithm switches modes at a random time.

🏷️ Delayed activation and the additive constant

The finite-policy constructor has a finite but uncontrolled completion time $T$. At request $t$, the uniform algorithm simulates that constructor from scratch for only $\lfloor {\log }_2(t+1)\rfloor$ steps. Before completion it serves requests using a fixed server label. Once the constructor finishes, its output size is bounded by the same simulation budget and can be used by the suffix routine.

For illustration, a constructor taking $T$ steps may activate only around request $2^T$. On a finite metric of diameter $D$, serving that initial prefix by one server costs at most $D$ times its length. This can be enormous, but it is a finite instance-dependent quantity and is absorbed into $B$.

The algorithm still serves each request immediately and obeys the stated per-request bound. The distinction is between a uniform asymptotic competitive theorem with an unrestricted additive constant and a small startup cost. The manuscript establishes the former; it does not turn its nonconstructive input into a practical policy with polynomially bounded initialization loss.

🏷️ Key steps and proof outlines

A finite tree bounds the retained request word

The computational companion’s “Universal filter” proves a bound that is independent of the raw input length. Let $\delta$ be the smallest positive distance and $D$ the diameter of the finite metric. Fix a move cap $M$. A node of the filter tree records a labeled server configuration and the number of positive moves used to reach it. A missed request spends that node and creates at most $k$ children, one for each server that could move. At depth $M$, a missed request spends the node without replacement. (OpenAI, 2026b)

Induction on requests shows that the live nodes represent all strongly lazy trajectories with at most $M$ moves. A request covered by every live configuration may be discarded without changing any such trajectory. Every retained request spends at least one previously unspent node. Since the tree has at most

$$H=1+k+\cdots +k^M$$

nodes, at most $H$ requests are retained. A very long repetition of one already occupied point creates no new nodes. The bound depends on move complexity rather than elapsed time, which is exactly what a fixed-horizon policy table needs.

A shadow trajectory avoids conditioning on a random switch

Partition raw requests into blocks ending at the $(k+1)$st distinct requested point. Every completed block costs any service at least $\delta$. Group $R=\lceil kD/\delta \rceil$ completed blocks into an epoch, so each completed epoch forces offline cost at least $kD$.

During an epoch, follow the table until it makes $M+1$ positive moves, then use marking. Marking costs at most $(k+1)D$ per remaining block: every nonendpoint point moves at most once, and the final new point costs at most one additional move. Let $F=R(k+1)D$ reserve the entire possible fallback cost and take $M=\lceil F/\delta \rceil$.

Now run a shadow copy of the table on the entire deterministic retained word, sharing the actual algorithm’s random bits until switching. Write $V$ for the shadow cost. If switching occurs, its common prefix already costs $(M+1)\delta \ge F$. Thus, on every random tape,

$${\mathrm{cost}}_{\mathrm{virtual}}\le V+F{1}_{\mathrm{switch}}\le 2V.$$

The table’s expected bound applies to $V$ without conditioning on the switch event. Applying the bound only to the random prefix ending at the switch would require a stopping-time guarantee that the finite table theorem does not provide.

Charging resets and delayed computation

Virtual positions reset at epoch boundaries, while actual servers stay where they are. On a label’s first use in an epoch, actual and virtual positions synchronize. The triangle inequality bounds the excess by $D$ for that label; subsequent costs agree. Summing over labels costs at most $kD$ per epoch. A similar shortcut comparison relates the retained-word optimum to the whole-sequence optimum plus $kD$. Completed epochs pay these fixed charges through their forced offline cost; only the final incomplete epoch contributes an additive remainder.

The existence manuscript supplies the finite policy inequalities through fractional allocation, changing partitions, anchor travel and rounding. The first two estimates each contribute one logarithm; the latter two are charged within those estimates before minimax and compactness are applied. This order matters because compactness can transfer a family of valid finite inequalities, but cannot supply a missing movement charge. (OpenAI, 2026a)

Finally, delayed activation makes the finite-table search uniform. At request $t$, simulate only $O(\log (t+1))$ construction steps. Once construction has halted, its table fits within that simulation budget. Beforehand use the fallback fixed label. A finite completion time gives a finite startup cost, absorbed by the unrestricted additive constant. The resulting theorem bounds processing time per request even though the hidden startup horizon may be enormous.

See Also

• One-sample prophet inequalities permits an adversary to see the entire random seed, a stronger information pattern than oblivious requests.
• Mean-payoff games also requires accounting for restart costs before passing to long-run guarantees.

🏷️ Manuscripts and verification scope

• Squared-logarithmic randomized k-server on arbitrary metrics — pinned manuscript and companion source.
• Uniform computation of the squared-logarithmic k-server bound — pinned manuscript and companion source.

The family scope page describes selected formalization coverage. The two comparator entries distinguish arbitrary-metric policy existence from a uniform bit algorithm on finite rational metrics. The latter permits an unrestricted finite additive movement term and time polynomial in the binary request-counter length. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026a. Squared-logarithmic randomized k-server on arbitrary metrics.

🐻  OpenAI 2026b. Uniform computation of the squared-logarithmic k-server bound.