2026 Theses Doctoral

Scalable Dynamic Control for Large-Scale Service Systems

Zhang, Wenxin

Many modern service systems operate under persistent tension between efficiency and implementability. Capacity is scarce, demand is stochastic, and operational decisions interact over time through congestion, reuse, and state dependence. In large-scale settings, the fully optimal dynamic control is often too complex to compute, too data-hungry to estimate, or too centralized to implement. This thesis develops scalable dynamic controls for several such problems. The central insight is that, even when the full system state is intractable to optimize over, a well-chosen low-dimensional signal of congestion or resource scarcity can power a simple policy with strong performance guarantees.

The first part of the thesis establishes this methodological foundation in the context of dynamic pricing for reusable resources. Companies managing assets such as cloud servers face an exponentially large state space when usage durations are non-memoryless. Classical approaches either assume memoryless usage durations, which are unrealistic in many applications, or resort to static pricing, which ignores the system state. We propose stock-dependent policies that rely on a single, low-dimensional signal: the number of available units. We prove that optimizing within this class reduces to a tractable convex program, and we rigorously characterize its tight performance guarantees. Furthermore, we demonstrate that these gains can be fully realized by a simple two-price policy that sets a higher price when the stock is below some threshold and a lower price otherwise. This ``power of two prices'' captures the underlying theme of this thesis: a little dynamicity, built on the right signal, goes a remarkably long way.

During the course of this doctoral work, generative AI underwent explosive growth, creating critical new operational frontiers of unprecedented scale. The remaining two chapters bring our methodology of scalable dynamic control directly to this frontier.

Chapter 2 studies distributed load balancing for AI inference. Modern AI services rely on vast, expensive computational resources and processing power, all sustained by a global network of data centers. A key operational challenge is ensuring these systems remain responsive by efficiently routing requests. We introduce the Greatest Marginal Service Rate (GMSR) policy that routes each request to the data center where it will have the highest marginal impact on the current service rate. GMSR is designed to be fully distributed, with routers in different geographic regions making decisions independently using only local information. This design makes the system scalable and resilient while eliminating the need for complex coordination. We prove that, despite its distributed design, the GMSR policy converges to the globally optimal solution that a central coordinator would choose to minimize system-wide latency. Furthermore, the policy is robust: even when the system is overloaded, it maximizes throughput and minimizes latency for all completed requests. GMSR yields a practical routing rule that requires neither demand-rate knowledge nor centralized coordination. By relying only on local information, service providers can achieve near-optimal latency performance through decentralized decisions, making the policy well suited to large-scale cloud computing, LLM serving, and other distributed service environments where centralized control is costly or infeasible.

Chapter 3 studies prompt caching for multi-turn LLM inference, where the key metric is tail latency: the response time experienced by the slowest fraction of requests, which determines user-perceived quality. Prompt caching reuses previously computed data from a conversation's history and is widely used in production systems---OpenAI and Anthropic report up to 50--90% cost savings through prompt reuse. When cache capacity is limited, the system must decide which entries to evict. The widely used Least Recently Used (LRU) policy, however, can perform arbitrarily poorly on tail latency, as it is oblivious to the heterogeneity of conversation lengths. Yet this heterogeneity is precisely what drives tail latency: a short conversation incurs low latency regardless of caching, while a long conversation can experience a significant latency spike if its cache is prematurely evicted. We propose Tail-Optimized LRU (T-LRU), a simple modification of LRU that provably dominates LRU on every workload and reduces P95 tail latency by up to 27.4\% on real traces.

Together, these chapters demonstrate that scalable dynamic control---identifying a low-dimensional congestion signal and building a simple policy around it---is both broadly applicable and increasingly important as AI systems grow in scale and complexity.