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

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 $k$-resource problem, which isolates this distinction. RandomLex samples one coordinate order and follows the lexicographically maximal work-function minimizer. Against oblivious adversaries on an $n$-point uniform metric, it is $\mathrm{Harm}(\min k,n-1)$-competitive, matching the known lower bound. The proof represents normalized work functions as distance cones over $M$-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 $\ell$, the exact ratio is $\mathrm{Harm}(\min k,\ell -1)$ for $\ell \ge 2$ and one for chains. Dependency width determines the effective dimension of online choice.