PaperlayerView exact revision on arXiv

Source-linked AI summary

The Price of Anarchy in Disaggregated Inference

Athos Georgiou

arXiv:2606.17081v1cs.ARcs.AIcs.DCcs.GTcs.PF

TL;DR

Disaggregated inference couples resource allocation, caching, and routing decisions across competing GPU pools, but its game-theoretic inefficiency is not well characterized. The paper models these interactions as coupled games, measures routing inefficiency, and deploys adaptive saturation-aware control, finding improved operating points and the largest reduction on the 70B 1P/5D configuration.

  • Problem

    Disaggregated inference couples competing prefill, decode, request-routing, and KV-cache decisions under millisecond latency and shared GPU constraints.

  • Method

    The paper models serving as three coupled games, measures routing inefficiency on Dynamo across models and topologies, and deploys an online saturation-aware routing controller.

  • Results

    Adaptive routing improves operating points, with the largest d PoA reduction on the 70B 1P/5D topology and consistent reductions across the evaluated 70B and 340B 1P/2D topologies.

  • Takeaways & Limitations

    Routing parameters matter primarily after saturation, supporting a shift from cache-affinity exploitation to load-balanced congestion avoidance in the evaluated Dynamo settings.

  • Takeaways & Limitations

    Experiments use one homogeneous workload, leaving cache placement partly degenerate and never exercising KV-cache tier spillover.

Abstract

from arXiv · show

Disaggregated inference architectures physically separate prefill and decode phases onto distinct GPU pools, creating competing "agents" that share a fixed hardware budget. We provide, to our knowledge, the first formal game-theoretic analysis of this architecture, using NVIDIA Dynamo as a concrete case study. We model disaggregated serving as three coupled games: a two-player resource game between prefill and decode pools, a selfish caching game over the hierarchical KV cache, and a congestion game with positive externalities for request routing. We empirically validate the latter two; the P/D resource game is treated analytically (Section 9.2). We characterize how GPU saturation induces regime transitions that shift the game's payoff structure: below saturation, selfish behavior has bounded Price of Anarchy (PoA); at saturation, superlinear latency and cache externalities drive our empirical estimator PoA-hat (defined in Section 6.4) upward. Based on this analysis, we design an adaptive controller that detects saturation transitions in real time and adjusts routing parameters accordingly, shifting from cache-affinity exploitation to load-balanced congestion avoidance. We instantiate our framework on a 3-node NVIDIA B200 cluster running Dynamo with two models, Nemotron-4-340B (TP=8, full-node workers with cross-InfiniBand KV transfers) and Llama-3.1-70B (TP=4), and find the same three-regime PoA-hat structure with the same first post-knee grid point (C=128) on both models. Adaptive routing shifts each model to a better operating point. Our strongest result is on the 70B 1P/5D topology, where PoA-hat drops 3.1x (66.4 to 21.5) in the saturated phase at a 13% throughput cost. On the 70B 1P/2D, PoA-hat drops 2.2x and TTFT P99 drops 7.6x (see Section 8.5).

1 Introduction

The paper frames disaggregated inference in Dynamo as three coupled games governing P/D resource allocation, KV-cache placement, and request routing. It introduces a game-theoretic lens for analyzing equilibrium efficiency and shows that GPU saturation changes routing inefficiency across operating regimes.

  • System framing: Dynamo’s Planner, KVBM, and Smart Router arbitrate competing claims over GPU capacity, memory tiers, and worker placement.The architecture separates prefill and decode while coordinating cache placement and cache-aware routing.
  • Analytical lens: PoA measures the efficiency gap between sequential greedy routing and globally optimal assignment, without requiring requests themselves to be rational.The router’s individual-cost minimization mirrors best-response dynamics in the corresponding congestion game.
  • Three-game model: The paper recasts disaggregated inference as three coupled games: P/D resource allocation, KV cache placement, and request routing.The games are coupled because saturation propagates externalities across their cost functions.
  • Saturation transition: GPU saturation induces a regime transition: routing inefficiency is stable below saturation but grows rapidly above the knee as the prefill pool overloads.The paper treats P/D resource allocation analytically, while empirically validating KV-cache placement and request routing across three topologies.
  • Empirical validation: The study measures routing inefficiency on a 3-node B200 Dynamo cluster using Nemotron-4-340B at TP=8 and Llama-3.1-70B at TP=4.It presents these as the first empirical routing-inefficiency measurements under a game-theoretic lens for disaggregated inference.

2 Background

Background establishes that prefill and decode have distinct computational bottlenecks, motivating disaggregated serving that separates them across GPU pools and enables independent scaling. Dynamo implements this architecture through planning, KV-aware routing, hierarchical caching, and event coordination, which the paper analyzes using game-theoretic concepts.

  • Inference phases: Prefill processes the full prompt and is compute-bound, whereas decode generates one token at a time and is memory-bandwidth-bound.Prefill is limited by peak FLOPS; decode is limited by HBM read throughput.
  • Disaggregated serving: Disaggregated serving separates prefill and decode onto distinct GPU pools, resolving co-located resource conflict and enabling independent scaling.The prefill pool targets TTFT, while the decode pool targets ITL and throughput.
  • Disaggregated serving: 30× throughput improvement is reported for DeepSeek-R1 671B on a disaggregated GB200 NVL72 rack versus traditional co-located serving.This comparison is reported by NVIDIA.
  • Dynamo architecture: Dynamo coordinates disaggregated inference through a Planner, Smart Router, KV Block Manager, and Event Plane.The Planner adjusts prefill/decode worker ratios; the Smart Router uses KV-cache-aware costs; the KV Block Manager stages blocks across four storage tiers; and the Event Plane propagates cache and worker-state updates.
  • Dynamo architecture: The Smart Router’s kv_overlap_score_weight parameter controls the tradeoff between cache affinity and load balancing, with deterministic routing at τ = 0 and stochastic routing at τ > 0.It selects the lowest-cost worker deterministically or samples from a softmax distribution over costs stochastically.
  • Game-theoretic concepts: The Price of Anarchy compares worst-Nash social cost with the social optimum, with PoA = 1 indicating optimal selfish behavior and larger values indicating inefficiency.Congestion games depend on co-user counts on shared resources and guarantee pure Nash equilibria via an exact potential function.

3 Related Work

Prior work covers game-theoretic GPU allocation, disaggregated serving, Pareto analysis, and selfish caching separately, but not inference routing or their coupling. This work positions itself as the first framework connecting equilibrium analysis to production disaggregated inference mechanisms.

  • Game-theoretic resource allocation: Game-theoretic resource allocation is established for cluster scheduling, but has not been applied at the inference-routing level.DRF, Themis, and Shockwave provide fairness, auction, or market-based allocation mechanisms for GPU resources.
  • Disaggregated inference systems: Existing LLM-serving work separates prefill and decode or targets edge inference, but does not model P/D separation, KV placement, and routing as coupled games.DistServe, Splitwise, and TaiChi motivate phase splitting, while Xu et al. combine auctions with reinforcement learning for mobile edge serving.
  • Disaggregated inference systems: Dynamo provides the richest production game structure, with Planner, Smart Router, KVBM, and NIXL corresponding to resource-allocation, congestion, and caching games.Its components dynamically rebalance P/D resources, route with KV awareness, manage hierarchical caches, and transfer KV state across nodes.
  • Pareto analysis: Pareto analysis dominates serving evaluation, but prior methods have not connected Pareto frontiers to game-theoretic equilibria.AIConfigurator, Vidur, KV Pareto, and related systems use enumeration, simulation, or filtering to identify throughput-latency or memory-accuracy tradeoffs.
  • Selfish caching and congestion: Selfish caching theory establishes topology-dependent PoA and capacitated equilibrium results, but no prior work applies it to KV-cache management in LLM inference.Complete graphs can yield PoA = 1, while line topologies can yield PoA = O(√n); hierarchical GPU interconnects motivate applying these results to KV placement.
  • Positioning: This work is the first to formalize disaggregated inference as coupled games and connect equilibrium analysis to mechanisms in a production inference system.The framework covers resource allocation, caching, and routing, while prior systems make decisions over seconds to minutes rather than inference schedulers’ sub-millisecond cycles.

4 Formalization: Disaggregated Serving as Coupled Games

The formalization decomposes disaggregated serving into three coupled games operating at different timescales: prefill-decode resource allocation, hierarchical KV-cache placement, and request routing. It characterizes their equilibria, externalities, classical-bound limitations, and routing trade-offs under saturation-sensitive latency.

  • 4 Formalization: Disaggregated Serving as Coupled Games: Three coupled games operate at distinct timescales: planner-level resource allocation, per-request routing, and continuous KV-cache placement.The games are analyzed independently before their coupling is characterized.
  • 4.1 Game 1: Prefill-Decode Resource Allocation: The prefill-decode game allocates a shared GPU budget between prefill and decode players under GP + GD ≤ G.Prefill and decode utilities are coupled asymmetrically because prefill controls KV transfer availability for decode.
  • 4.1 Game 1: Prefill-Decode Resource Allocation: Under strict convexity and diminishing returns, the resource game has a unique variational equilibrium that equalizes marginal SLO improvement across pools.The equilibrium follows from the shared-budget KKT conditions.
  • 4.1 Game 1: Prefill-Decode Resource Allocation: At saturation, the equilibrium diverges more from the social optimum because it omits prefill’s positive externality on decode, whereas the gap is small below saturation.The Planner’s ±1-worker adjustment every 30 s is modeled as an inertial best-response dynamic, but convergence is not directly validated.
  • 4.2 Game 2: KV Cache Placement: The hierarchical KV-cache placement game has pure Nash equilibria; on complete-graph topologies, selfish caching is socially optimal with PoA = 1.Under HBM capacity constraints, it becomes a capacitated selfish replication game with polynomial-time equilibrium computation for hierarchical topologies.
  • 4.2 Game 2: KV Cache Placement: For hierarchical topologies, the paper conjectures sublinear PoA growth with worker count, using Chun et al.’s O(√n) line-topology bound as the closest classical analog.This is presented as a conjecture rather than an established theorem.
  • 4.3 Game 3: Request Routing as a Congestion Game: Dynamo’s sequential greedy Smart Router is equivalent to best-response dynamics, producing a Nash equilibrium or approximate NE when τ > 0.The resulting PoA measures deviation from the globally optimal batch assignment.
  • 4.3 Game 3: Request Routing as a Congestion Game: When ω = 0, routing is a potential game with classical PoA bounds; when ω > 0, heterogeneous overlap costs generally destroy that structure and shift behavior between cache affinity and load balancing.The empirical index d PoA is ≈7.5 at C = 64 for 70B with 2 workers and ≈19 for 340B, while remaining stable below saturation and growing rapidly at saturation.

5 Saturation Dynamics and Regime Transitions

GPU saturation creates practically significant regime transitions: below saturation, latency and PoA remain stable, while near capacity superlinear latency, queueing, and resource coupling rapidly worsen inefficiency. The transition also makes caching and configuration choices sharply more consequential, motivating regime-specific adaptive control.

  • Routing congestion game: Below saturation, the routing game has approximately linear latency and bounded PoA that remains stable as load increases.The GPU has idle compute and memory bandwidth, while batching amortizes fixed overhead.
  • Saturation mechanisms: Above saturation, HBM eviction, batch-size degradation, and queuing cascades make latency superlinear and increasingly sensitive near capacity.The singular latency term has a pole at capacity, unlike standard polynomial latency functions.
  • Routing congestion game: At saturation, PoA grows rapidly because singular latency amplifies routing imbalances and insufficient P/D allocation becomes binding.A near-balanced Nash equilibrium can still incur disproportionately higher cost than a social optimum that leaves headroom below the singularity.
  • Caching game: At the first eviction, PoAKV jumps from 1 to a topology- and eviction-policy-dependent value, transforming caching into a coupled congestion game.Eviction from HBM creates recomputation demand on prefill compute, coupling memory and compute resources.
  • Pareto frontiers: At saturation, the performance frontier steepens and becomes parameter-sensitive: a landscape flat at C = 64 becomes rugged at C = 128.Configurations that are near-optimal below saturation can become far from the frontier above it, supporting dynamic selection among regime-specific Pareto frontiers.

6 Adaptive Controller Design

The adaptive controller detects saturation regimes from smoothed TTFT P99 and changes routing parameters accordingly, replacing cache-affinity exploitation with load balancing as PoA degrades. It runs in Python through Dynamo’s per-request configuration override without modifying the Rust core.

  • Implementation: The Python controller adjusts temperature and overlap weight per request through router_config_override, enabling zero-downtime switching between frontend configurations.It requires no Dynamo Rust-core modifications and exports gauges for PoA, saturation state, temperature, and routing cost.
  • Regime-Specific Routing: Below saturation, τ = 0 and ω = 1 exploit cache locality because bounded PoA makes KV-cache-hit TTFT reductions worthwhile.The controller shifts from cache affinity to load balancing as the PoA bound degrades near saturation.
  • Regime-Specific Routing: In Transition, τ = 0.7 and ω = 1.0 use a calibrated 70B 1P/5D setting transferred across topologies, while Saturated uses conjectural τ = 0.8 and ω = 0.1.The Saturated row prioritizes load balancing but never fired in reported Experiment 3 because the load spike did not persist long enough to cross θ2.

7 Experimental Setup

The study evaluates Dynamo-based disaggregated inference on a three-node B200 cluster using Nemotron-4-340B and Llama-3.1-70B across multiple prefill/decode topologies. Four experiments measure equilibrium, saturation detection, adaptive routing, and parameter sensitivity under controlled workloads.

  • Cluster and software configuration: The testbed comprises 3× HGX B200 nodes with 8× B200 SXM GPUs each and InfiniBand links measured at ∼390 Gb/s between node pairs.Active GPU counts are 12 for 70B 1P/2D, 24 for 340B 1P/2D, and 24 for 70B 1P/5D.
  • Models and topologies: Experiments use Nemotron-4-340B-Instruct at FP8 with TP=8 and Llama-3.1-70B-Instruct-FP8 with TP=4 across 1P/2D and 1P/5D topologies.The 70B 1P/5D topology increases the routing action space to m = 5, while both models use 1P/2D with m = 2.
  • Workload and load generation: The workload uses 5 prompt templates with 128 input tokens, 256 maximum output tokens, temperature 0.0, and controlled concurrency with ramp and hold phases.Concurrency is maintained with a fixed number of in-flight requests using an asynchronous Python client and semaphore.
  • Measurement methodology: NATS event correlation matches SSE response identifiers to request assignments, achieving 100% per-request decode worker attribution for PoA measurement.The PoA estimate applies the Hungarian algorithm to a frozen-latency cost matrix.
  • Experimental program: Four experiments sweep concurrency and routing parameters to characterize equilibrium, detect saturation, compare adaptive with static routing, and test Pareto sensitivity.Experiment 4 compares C = 64 below saturation with C = 128 at saturation using a 4 × 4 grid over τ and ω.

8 Results

Section 8 finds extreme prefill-dominated saturation, a consistent three-regime d PoA pattern, and router-parameter invariance below saturation. At saturation, parameter sensitivity emerges, while measurement uncertainty and knee-resolution limits constrain interpretation.

  • Measurement limitations: ±0.10: cross-configuration spread across 16 Pareto configurations in Experiment 4a is comparable to the 1.6× spread used for 340B saturation sensitivity claims.Experiments 1, 2, 4a, and 4b are single-run measurements with unknown measurement uncertainty; reported means average per-iteration P99 values.
  • Asymmetric P/D saturation: 1,500×: TTFT P99 rises from 74 ms to 113 s while ITL P99 remains 21.7 ± 1.3 ms, confirming prefill as the dominant bottleneck.The 70B likewise shows flat ITL P99 at ∼10–14 ms with the same TTFT explosion.
  • Throughput ceiling: ∼18 rps: the 340B throughput ceiling is 16.5 rps at C = 128 and 18.0 rps at C = 512, versus ∼47 rps for the 70B.The 2.6× lower ceiling for the 4.9× larger model reflects partial FP8-quantization offsetting of increased compute cost.
  • Three PoA regimes: C = 128: d PoA transitions from stable to rapidly growing for both models, with 340B TTFT P99 increasing from 544 ms to 16.2 s and 70B from 354 ms to 10.0 s.The true knee is unresolved within the sampled interval, and deep-saturation d PoA primarily reflects prefill resource-allocation failure rather than routing inefficiency.
  • PoA invariance: 18.7 ± 0.10: 340B d PoA remains statistically indistinguishable across all 16 (τ, ω) configurations below saturation.The 70B corroborates this with d PoA = 7.47 ± 0.08 on 1P/2D and 14.93 ± 0.06 on 1P/5D.

9 Discussion

The discussion bounds the findings through workload, validation, modeling, and controller limitations, while deriving implications for regime-aware serving and multi-tenant mechanism design. It recommends exposing PoA, evaluating transitions, and extending analysis beyond the controlled single-tenant setting.

  • Modeling limitations: Full dynamic-game analysis remains future work because inference state evolves continuously, while the controller pragmatically detects observable regime shifts and applies pre-computed settings.Output lengths, arrivals, batch composition, and memory pressure are uncertain, making the formalized games incomplete-information games.
  • Limitations: The experiments use one homogeneous workload, making the cache-placement game potentially degenerate and limiting generality beyond diverse traffic.The profile uses 5 prompt templates, 128 input tokens, 256 maximum output tokens, and deterministic generation.
  • Limitations: Game 1 is only analyzed theoretically: fixed P/D splits and synthetic utilization validate cache placement and routing, but not dynamic GPU reallocation.The empirical findings therefore validate Games 2 and 3, not Game 1.
  • Controller limitations: 11.6 rps versus 18.2 rps shows the adaptive controller’s 340B latency improvement carries a 36% throughput reduction.The shifted operating point prioritizes latency over throughput.
  • Design implications: Serving frameworks should export PoA alongside TTFT and ITL, and planners and routers should be evaluated during regime transitions rather than only at steady state.The discussion identifies rising PoA as an early warning and highlights convergence speed, overshoot, and oscillation as transition criteria.
  • Design implications: Multi-tenant disaggregated inference motivates mechanism design because tenants can strategically overprovision, warm caches, or time jobs to avoid contention.Potential extensions include strategy-proof auctions, incentive-compatible allocation, and fairness analysis beyond aggregate SLO optimization.

10 Conclusion

The paper models disaggregated inference as three coupled games and measures routing-game Price of Anarchy across two models and three topologies. Its conclusions emphasize saturation-regime adaptation, analytical game-theoretic guidance, and extensions to larger, dynamic, heterogeneous, and multi-tenant systems.

  • Conclusion: The study models NVIDIA Dynamo’s disaggregated inference architecture as three coupled games and measures request-routing Price of Anarchy on a 3-node B200 cluster.The evaluation spans two models and three topologies.
  • Conclusion: Below saturation, d PoA varies by less than ±0.10 on the 340B, ±0.08 on the 70B 1P/2D, and ±0.06 on the 70B 1P/5D.Parameters matter only at the first post-knee grid point, which occurs at C = 128 on a 70B parameterization.
  • Conclusion: The same apparent knee may reflect single-prefill-worker compute exhaustion, but the grid cannot determine whether the true knees are exactly co-located within (96, 128].Denser sweeps on other hardware are needed to test whether the coincidence is deeper than single-worker prefill saturation.
  • Conclusion: The adaptive controller detects the operating regime and switches routing parameters, with improvements scaling with routing-game size.The largest d PoA reduction occurs on the 70B 1P/5D configuration (m = 5).
  • Conclusion: Run-to-run variance shrinks by an order of magnitude in every case, while deep-saturation d PoA blow-up of ∼200–309 is consistent with compute exhaustion rather than routing suboptimality.Attributing this specifically to Game 1 resource allocation would require varying the P/D split.
  • Conclusion: Game theory contributes analytical vocabulary, suboptimality metrics, and regime analysis to guide operations without runtime equilibrium computation.Future work includes production-scale queuing baselines, controlled cache experiments, dynamic games, MoE congestion, multi-tenant mechanism design, and PoA-driven P/D adaptation.

A Game Theory Definitions

This section defines the game-theoretic concepts used throughout the paper, including normal-form games, Nash and congestion equilibria, Price of Anarchy, Pareto optimality, and Wardrop equilibrium. Together, these definitions formalize individual incentives, resource congestion, social inefficiency, tradeoffs, and continuous-flow routing.

  • Normal-form games and Nash equilibrium: A normal-form game specifies players, each player’s strategy set, and each player’s utility function over joint strategy profiles.A Nash equilibrium occurs when no player can improve utility through unilateral deviation.
  • Congestion games: A congestion game assigns players feasible resource subsets and resource costs determined by the number of users.Its player cost sums the costs of resources in the player’s selected subset.
  • Congestion games: Every congestion game is an exact potential game and therefore has at least one pure Nash equilibrium.The potential decreases whenever a unilateral cost-reducing deviation occurs.
  • Social efficiency: Price of Anarchy is the ratio of social cost at the worst Nash equilibrium to social cost at the social optimum.A value of 1 indicates socially optimal selfish behavior, while larger values indicate inefficiency from uncoordinated decisions.
  • Social efficiency: Pareto optimality excludes alternatives that improve every player’s utility while strictly improving at least one player’s utility.In LLM serving, the Pareto frontier typically captures tradeoffs among throughput, TTFT, ITL, and cost.
  • Routing equilibrium: Wardrop equilibrium assigns continuous routing flow so used paths have equal cost and no unused path has lower cost.It is the continuous-flow analog of Nash equilibrium when requests are numerous relative to GPUs.
Loading 2606.17081v1…