Escaping Self-Confirming Optima in Congestion-Aware Caching and Routing

When a network decides both where to store copies of content and how to route requests to those copies, the two decisions reinforce each other. Requests flow toward wherever an item is cached, and the item stays cached there because that is where the requests arrive. This lock-in can trap an iterative optimizer in a configuration that is stable but costly: a different arrangement of copies and paths could be much cheaper, yet no small local change reveals it. The best current algorithms for the realistic case, with dynamic routing and link costs that rise steeply under congestion, are local by construction. They provably reach a stationary point and nothing stronger.

We propose a small population of copies of the network's own distributed solver that push each other apart. The push is measured in the space of who serves whom: which node ends up supplying each item to each requester. It does not act on raw optimization variables. The push is gated so that it switches on only when a copy drifts toward the current best configuration, and it decays to zero, so every copy still converges to the same optimality condition the original algorithm guarantees. Before building anything, the proposal measures whether these traps exist and how costly they are on small networks where the true optimum can be computed. It also commits to reporting a negative answer if plain restarts with the same compute budget do as well.

The problem and where it is open

Jointly optimizing caching and routing is NP-complete (Dehghan et al.). It becomes tractable when routing is fixed. In that case the objective has diminishing returns (DR-submodularity, the continuous analogue of "each extra cached copy helps less"), and greedy or projected-gradient methods achieve a $(1-1/e)$ approximation (Ioannidis and Yeh, Dehghan et al.). Li et al. keep a version of this guarantee under bounded link capacities by using a primal-dual Frank-Wolfe method, although it needs momentum smoothing to damp oscillation when capacities are tight.

The guarantees disappear in the regime that matters most operationally. Zhang and Yeh show that once routing is dynamic and link costs are non-linear in load, the diminishing-returns structure breaks. They respond with three components: a modified KKT condition, a necessary optimality test built from marginal link and caching costs; a distributed gradient projection (GP) algorithm that provably reaches it; and distributed randomized rounding (DRR) to produce discrete placements. Their condition is stricter than ordinary first-order stationarity and removes some degenerate fixed points, but it remains local. Kamran et al. face the same limit for rate allocation, where their barrier method also stops at a stationary point.

These papers motivate the proposal. Its method draws on the premature-convergence literature. Da Costa and Modenesi add a repulsive velocity to particle swarm optimization (PSO, a population search in which particles are pulled toward the best point found so far). The repulsion is gated by a Gaussian similarity kernel between a particle's own best and the global best, so it acts only when the two are too close. Doulazmi et al. show that greedily cloning the current winner in population-based training collapses diversity over long horizons.

Two negative results constrain the design. First, DPSO's repulsion costs precision on smooth unimodal functions such as Sphere, so a mechanism that always fires would hurt benign network instances. Second, the repulsion strength must be tuned to the scale of the landscape. Both findings are reasons for a gated, decaying, scale-free metric.

Core claim

We claim three things. On congestion-aware joint caching and routing with dynamic routing, the distributed GP algorithm of Zhang and Yeh has multiple modified-KKT points with materially different costs, and these are reached from different initializations. A population of $K$ GP copies that repel each other in serving-map distance, with gating and annealing, finds lower-cost configurations than $K$ independent restarts at equal gradient-evaluation and message budgets. The gain comes from the choice of metric: the same repulsion applied to raw caching and routing variables should help much less.

The intuition behind the metric is as follows. Two solutions can differ greatly in raw variables yet serve every request from the same nodes. Examples are permuted splits across symmetric paths, or caching probabilities that differ only where no traffic flows. Two solutions can also differ slightly in raw variables yet assign service completely differently. Lock-in is a property of the serving assignment, so the repulsion should act on that assignment.

Let $x$ denote caching variables and $\phi$ routing fractions. Let $p_{x,\phi}(r,i,v)$ be the fraction of requester $r$'s demand for item $i$ that is served at node $v$. Define the serving-map distance between population members $a$ and $b$ as $d(a,b)=\sum_{r,i,v}\lambda_{ri}\,|p_a(r,i,v)-p_b(r,i,v)|$, where $\lambda_{ri}$ is the request rate. This weighting makes $d$ the volume of traffic whose server differs between the two solutions, normalized so that it lies between 0 and 2. Member $a$ updates as

$$ (x_a,\phi_a) \leftarrow \Pi\Big[(x_a,\phi_a) - \eta\,\nabla C(x_a,\phi_a) + \eta\, c_t\, e^{-d(a,\star)^2/\sigma^2}\,\nabla d(a,\star)\Big], $$

The terms are defined as follows. $\Pi$ is Zhang and Yeh's feasible projection with loop prevention. $C$ is total routing-plus-cache cost. $\star$ is the current lowest-cost member. $\sigma$ is a bandwidth expressed as a fraction of total traffic. The coefficient $c_t$ decays to zero.

Because $d$ is normalized by traffic volume, a single $\sigma$ should transfer across topologies; this addresses the scale sensitivity noted for DPSO. Because $c_t\to 0$, each member's late dynamics are exactly the original GP, so each member inherits its convergence to a modified-KKT point. The method chooses which basin to converge in, not what convergence means. We use subgradients of the absolute value, and $p$ is differentiable in $(x,\phi)$ through the path-flow expressions Zhang and Yeh already compute. In deployment, each node holds $K$ copies of its local variables, messages carry $K$ values, and only the best member is rounded with DRR and installed. The overhead is therefore a factor of $K$ in local computation and message size, and the system never reconfigures live caches during the search.

Research program

The work proceeds in three stages, each of which can kill the project.

Stage one: a census of traps. On small instances, we compute the exact optimum and measure how often, and by how much, GP misses it. The instances are 3×3 and 4×4 grids, Abilene, and small Erdős–Rényi graphs with catalogs of tens of items. Congestion costs of the convex M/M/1 type become piecewise linear, and binary caching becomes a mixed-integer program. This follows the precedent of Dehghan et al., who verified solutions within 1% of brute force at small scale, though under fixed routing. We run GP from 200 random initializations per instance and record the cost distribution relative to the optimum. We then cluster the final serving maps under $d$ to count distinct basins. If more than roughly 90% of runs land within 1% of optimal across topologies and capacity levels, the landscape is benign. In that case the project reports this finding, which is itself unknown, and stops.

Stage two: the method and its ablations. Here we test whether the method beats equal-budget restarts and which ingredient is responsible.

Stage three: scale. We test whether the effect survives at scale, under tight capacities and with real demand.

Baselines

The naive reference point is decoupled operation: LRU caching with shortest-path routing, plus LFU and popular-content-first as variants. Ioannidis and Yeh report that joint projected gradient ascent reduced routing costs by 10× to 1000× relative to LRU under fixed routing. We include this reference only to calibrate the scale of improvement and do not expect it to be competitive.

The strongest existing method is the distributed GP with modified KKT condition and DRR rounding from Zhang and Yeh, along with its fixed-routing companion GCFW, which carries a (1/2, 1) approximation. That paper reports total costs "up to 30% lower than the second-best algorithm" on its elastic cache simulator. Lacuna has no reported result for its gap to the global optimum, which is exactly what stage one measures. We run it with its published update rules. Its step size is tuned on held-out instances with the same tuning budget, in tuning trials, that our method receives for $\sigma$ and the $c_t$ schedule.

Under bounded link capacities we also run the primal-dual method of Li et al., which that paper reports "typically converges within 1,000 iterations" and was often the only method to stay feasible under strict link constraints.

The decisive competitor is $K$-start GP: $K$ independent GP runs from random initializations, keeping the best. It uses identical total gradient evaluations, message volume, and rounding. Beating it means a lower median rounded total cost, by more than the run-to-run interquartile range, on at least the tight-capacity instances. On small instances it also means a higher fraction of trials reaching within 1% of the optimum.

Two ablations isolate the key ingredient. The first applies the same gated repulsion using Euclidean distance on $(x,\phi)$, mirroring DPSO directly. The second keeps serving-map repulsion but removes the gate, so the repulsion is always on, which tests the unimodal-penalty concern. Every method is evaluated after DRR rounding, so the comparison reflects deployable placements.

Why not just…?

Why not just restart GP from many random points? This is the most serious threat, and the argument that restarts are operationally prohibitive does not apply, because restarts can run on virtual copies exactly as our population does. The $K$-start baseline therefore receives the same deployment model and budget. Our hypothesis is that random initializations in high-dimensional caching space mostly fall into the same few large basins defined by the dominant popularity modes. Repulsion from the incumbent's serving map spends the budget on genuinely different assignments. Stage one's basin clustering tests this directly. If random starts already cover the low-cost basins, then $K$-start will match us, and we will report that diversity of starting points is sufficient.

Why not just add noise to the gradient or use annealing? Undirected perturbation is the Lévy-flight and chaotic-map family used for metaheuristics such as Xuan Chen et al.. It is cheap and needs no population. Its weakness in this setting is that noise on caching variables where no traffic flows changes nothing, so most of the noise budget is wasted on directions that the serving map ignores. We include perturbed GP, with an annealed isotropic noise scale tuned under the same budget, as an additional baseline. If it matches the serving-map population, the directed metric is not needed.

Why not just use entropy-regularized reinforcement learning, or greedy submodular maximization? Soft actor-critic adds action-level randomness, and Zheng et al. apply it with graph neural networks to satellite networks. However, their reported results use a cache of two items, so there is no evidence on whether the approach scales to realistic catalogs. Doulazmi et al. show that entropy-regularized populations still collapse over long horizons. Greedy submodular methods lose their guarantee once routing is dynamic over congestion costs (Zhang and Yeh), and Kamran et al. report non-convex methods beating greedy by up to 5.43× in utility under tight capacities. We therefore run greedy as a secondary baseline, not the main one. We do not train a reinforcement learning agent: the question here concerns static basins of a known cost model, where a learned policy adds sample cost without addressing that question.

Proposed experiments

We build topologies from the backbones used by Ioannidis and Yeh and Li et al.: Abilene, GEANT, Deutsche Telekom, grids, hypercubes, Erdős–Rényi graphs, and small-world graphs. Demand follows Zipf popularity, and at scale it is driven by the Kuaishou trace of over 8 million requests for 2 million items across 488 edge servers, also from Li et al.. Link costs follow Zhang and Yeh's congestion-dependent model, with capacity looseness $\kappa$ swept from loose to tight.

The metrics are rounded total cost, gap to the exact optimum on small instances, gap to the best configuration found by any method on large instances, the fraction of trials within 1% of the optimum, the number of distinct basins reached, iterations and messages to convergence, and per-iteration overhead. We compare the overhead against the 15–25% reported for DPSO.

Three checks decide the outcome. First, stage one must show a non-trivial trap gap, or the project ends with that finding. Second, at equal budget the serving-map population must beat both $K$-start GP and perturbed GP in the tight-$\kappa$ regime, where Li et al. already observe that local dynamics become fragile. Third, in the loose-$\kappa$ regime, where the landscape should be closer to unimodal, the gated method must be no worse than plain GP, while the ungated ablation is expected to lose precision as DPSO does on Sphere. If the Euclidean-distance ablation matches the serving-map version, the contribution reduces to applying DPSO to this problem, and we will say so.