acceptodds
Desk rejected at ICLR 2027

RandomLex: Exact Randomized Ratios for the Uniform k-Resource Problem and Dependency Caching

Desk rejected at ICLR 2027, so left out of the paper lists and the map.

Abstract

Prefix/KV caches must retain prerequisite states together with each reusable computation. Consequently, physical capacity can greatly exceed the number of independent caching choices. We determine the exact randomized complexity of the uniform -resource problem, which isolates this distinction. RandomLex samples one coordinate order and follows the lexicographically maximal work-function minimizer. Against oblivious adversaries on an -point uniform metric, it is -competitive, matching the known lower bound. The proof represents normalized work functions as distance cones over -convex minimizer families: free updates slice the family, paid updates perform one-unit rank truncations, and a Shapley-weighted potential yields the matching harmonic charge. A nonexpansive legality retraction and a finite-chain invariant extend the result to uniform-cost, no-bypass dependency caching. For posets of width at most , the exact ratio is for and one for chains. Dependency width determines the effective dimension of online choice.

Primary area:
learning theory
Keywords:
Online algorithms, randomized competitive analysis, k-resource problem, dependency caching, prefix/KV caching, M-convexity

Related papers

Discussion (0)

Sign in to comment.