SOLA: Optimizing SLO Attainment for Large Language Model Serving with State-Aware Scheduling

SOLA: Optimizing SLO Attainment for Large Language Model Serving with State-Aware Scheduling

Speakers: Ke Hong, PGD Student; Xiuhong Li; Lufang Chen; Guohao Dai; Xuefei Ning; Yu Wang

Conference: MLSys 2025

YouTube: https://www.youtube.com/watch?v=None

Overview

The rapid proliferation of large language models (LLMs) has introduced unprecedented challenges and opportunities in model serving. This talk, presented by Ke Hong from Tsinghua University and co-authored with researchers from Shanghai Jiaotong University, Peking University, and Infinity AI, introduces SOLA, a novel state-aware scheduling framework designed to significantly improve Service Level Objective (SLO) attainment for LLM inference. SOLA addresses the unique characteristics of LLM serving, specifically the distinct prefill and decode phases, each with its own critical latency metrics: Time To First Token (TTFT) and Time Per Output Token (TPOT).

The core motivation behind SOLA stems from observed inefficiencies in current LLM serving systems, which often exhibit biased latency distributions and high variance across requests. These issues lead to either TTFT or TPOT being underserved, or some requests needlessly consuming excess computational budget while others fail their SLOs. By exploiting a "two-fold tradeoff" — balancing TTFT and TPOT, and managing priorities among individual requests — SOLA proposes an iteration-level feedback mechanism that dynamically adjusts scheduling strategies based on real-time system and request states. This approach aims not only to enhance user experience by ensuring more consistent and predictable latency but also to drive down operational costs by enabling higher request throughput on existing infrastructure.

The significance of SOLA lies in its comprehensive approach to managing the intricate dynamics of LLM inference. Unlike prior work that often focuses on isolated aspects like prefill/decode interference or basic request prioritization, SOLA offers a coordinative co-optimization strategy. By formulating scheduling as a constrained optimization problem and employing a sophisticated feedback loop, SOLA achieves fine-grained control over latency distribution. The experimental results demonstrate substantial improvements in SLO attainment across various models and datasets, positioning SOLA as a critical advancement for efficient and cost-effective deployment of LLMs, particularly in non-disaggregated, resource-constrained environments.

Background

▶ Watch: Introduction and importance of SLO in model serving (0:00)

Model serving has been a well-established field long before the advent of large language models, with a primary focus on reducing operational costs while meeting client demands. A fundamental concept in this domain is the Service Level Objective (SLO), which quantifies the real-time performance requirements of a service. A typical SLO is defined as a tuple specifying both a latency constraint (e.g., 200 milliseconds) and a required attainment percentage (e.g., 99%). This means that 99% of user requests must be served within 200 milliseconds. Achieving high SLO attainment is crucial because the number of requests a system can serve per second directly correlates with its operational efficiency; higher throughput under SLO translates to fewer machines required and thus reduced infrastructure costs.

The landscape of model serving fundamentally shifted with the popularization of large language models. LLMs introduce distinct computational characteristics that complicate traditional serving paradigms. Specifically, LLM inference is typically divided into two sequential, yet computationally different, phases:

1. Prefill Phase: This phase processes the user's input prompt, computing the initial set of hidden states and often producing the first token. It is typically a compute-intensive operation, especially for long prompts, involving a large matrix multiplication or attention computation over many input tokens.
2. Decode Phase: Following the prefill phase, this phase generates subsequent tokens one by one, iteratively extending the output sequence. Each decode step involves processing a single new token along with the previously generated tokens (often utilizing a key-value (KV) cache to store past hidden states, reducing redundant computation). This phase is typically memory-bound and latency-sensitive, as users expect a continuous stream of output.

These two phases necessitate two distinct latency metrics that are critical for user experience and are now often part of LLM-specific SLOs:

• Time To First Token (TTFT): Measures the latency from the request submission to the reception of the very first output token. A high TTFT can lead to user frustration, as it implies a long initial wait.
• Time Per Output Token (TPOT): Represents the average latency for generating each subsequent token after the first one. A high TPOT results in a slow, choppy generation experience.

An LLM serving SLO, therefore, typically constrains both TTFT and TPOT. The challenge lies in the fact that optimizing for one metric can negatively impact the other due to shared resources and computational dependencies. For instance, aggressively prioritizing prefill requests to reduce TTFT might starve decode requests, increasing TPOT. Conversely, prioritizing decode requests might lead to longer queues for new prompts, increasing TTFT.

Observations from existing LLM serving systems reveal two critical issues:

1. Biased Latency Distribution: Often, either TTFT or TPOT exhibits significantly higher SLO attainment than the other. This imbalance is frequently a consequence of existing scheduling policies that implicitly or explicitly prioritize one phase over the other.
2. Large Variance in Latency: Different requests within the system are treated inconsistently. Many requests might fail to meet their SLOs, while others have ample "budget" to spare, indicating inefficient resource allocation.

These observations highlight a fundamental "two-fold tradeoff" that existing systems fail to exploit optimally:

• Tradeoff between TTFT and TPOT: Balancing the latency requirements of the prefill and decode phases.
• Tradeoff among different requests: Ensuring equitable and efficient resource allocation across all active requests.

Prior work in LLM serving has typically addressed these issues in a fragmented manner, focusing on managing latency interference between prefill and decode phases (e.g., using techniques like continuous batching, chunking, or speculative decoding) or implementing priority management for different request types (e.g., shortest-job-first). SOLA differentiates itself by aiming for a coordinative co-optimization, moving beyond qualitative controls to enable fine-grained, quantitative management of the latency distribution across both phases and all requests, thereby directly targeting improved SLO attainment.

Key Findings

▶ Watch: Motivation: Exploiting biased and varied latency distributions (4:00)

The central discovery of this work is that significant improvements in SLO attainment for large language model serving can be achieved by adopting a state-aware scheduling methodology that actively exploits the inherent two-fold tradeoffs within LLM inference. SOLA's key findings and contributions include:

1. Formulation of Iteration-Level Scheduling: SOLA formally defines the LLM serving scheduling process at the iteration level, recognizing that execution decisions (what to run, and how much) are made iteratively. This granular perspective allows for dynamic adjustments in response to real-time system conditions.
2. Introduction of State-Awareness: The system's ability to monitor and utilize both request-level states (e.g., real-time latency, input/output lengths) and system-level states (e.g., 99th percentile TTFT, memory usage) is a cornerstone of SOLA. This real-time feedback loop is crucial for informed, adaptive scheduling decisions.
3. Co-Optimization of TTFT and TPOT: SOLA successfully addresses the often-conflicting objectives of minimizing TTFT and TPOT. By formulating scheduling as a constrained optimization problem, it can dynamically prioritize one metric (e.g., optimize TTFT) while ensuring the other's SLO (e.g., TPOT) is met, or vice-versa. This adaptive strategy directly tackles the problem of biased latency distributions observed in prior systems.
4. Reduction of Latency Variance: Through its fine-grained control over execution order and workload size, SOLA effectively reduces the variance in latency experienced by different requests. This ensures that computational budgets are utilized more efficiently, preventing some requests from failing SLOs while others have redundant capacity.
5. Significant Improvement in SLO Attainment: The experimental results demonstrate that SOLA achieves substantial improvements in SLO attainment across a variety of LLM models and datasets compared to state-of-the-art baselines like vLLM and FastServe. This translates directly to a higher number of requests per second (RPS) that the system can serve while still adhering to stringent latency requirements.
6. Lower Operational Costs: By enabling higher throughput under specified SLOs, SOLA allows service providers to serve more requests with fewer machines. This direct correlation between SLO attainment and system capacity leads to a tangible reduction in infrastructure costs, making LLM deployment more economically viable.
7. Dynamic Tradeoff Exploitation: The visualization of TTFT and TPOT on a latency plane confirms that SOLA's adaptive scheduling effectively reduces the bias and variance in latency distribution, validating the hypothesis that these two-fold tradeoffs can be exploited for optimal performance.

In essence, SOLA's key finding is that by consciously and dynamically managing the interplay between prefill and decode phases, and by intelligently prioritizing requests based on their real-time state and SLO adherence, LLM serving systems can achieve a superior balance of performance, user experience, and cost efficiency.

Technical Deep Dive

▶ Watch: SOLA: Iteration-level state-aware scheduling method overview (6:00)

SOLA's technical innovation centers on its state-aware scheduling framework, built around an iteration-level feedback mechanism and a constrained optimization problem. This design allows for dynamic adjustment of scheduling strategies based on real-time system and request states, enabling fine-grained control over latency distribution.

The first step in SOLA's approach is the formalization of the iteration-level scheduling process. In the context of LLM serving, an "iteration" typically corresponds to a single forward pass of the model, which can process a prefill request, a decode request (generating one token for one or more sequences), or a mixed batch containing both. At each iteration, the scheduler must decide:

1. Which requests are executed: This involves selecting from the pool of waiting prefill and decode requests.
2. How many tokens/requests are processed: This determines the batch size and the computational load for the current iteration.

The execution of this chosen workload provides crucial feedback that informs the scheduling strategy for the subsequent iteration, forming a continuous control loop.

The design space for the scheduling strategy is abstracted into two orthogonal components:

1. Execution Order: This dictates the priority among all active requests. For example, should prefill requests be prioritized over decode requests, or vice versa? How are requests within the same phase ordered?
2. Workload Size: This determines the number of requests or tokens to be included in the current batch. This is critical for GPU utilization; too small a batch leads to underutilization, too large leads to increased latency.

To enable this fine-grained control, SOLA relies on comprehensive state monitoring. Two types of states are continuously tracked:

1. Request States: These are individual request-level metrics, including the real-time latency experienced by each request (its current TTFT or TPOT), its input prompt length, and its current output length.
2. System States: These are aggregate statistics reflecting the overall system health, such as the real-time 99th percentile TTFT and TPOT across all active requests, and the current memory usage on the serving hardware (e.g., GPU memory).

These monitored states serve two vital purposes: they are direct inputs to the scheduling optimization problem, and they are used for online cost model tuning. The cost model is a predictive component that estimates the latency for the next iteration based on the current system state and a hypothetical workload. This prediction is crucial for making proactive scheduling decisions rather than reactive ones.

At the heart of SOLA's adaptive scheduling is a constrained optimization problem. At each iteration, using the current states and the latency predictions from the cost model, the system formulates an optimization problem. The core idea is to dynamically choose an objective based on which SLO is currently "suffering" more:

• Optimize TTFT subject to TPOT SLO: If the TTFT attainment is low, the scheduler will prioritize actions that reduce TTFT, but only if they do not cause the TPOT SLO to be violated.
• Optimize TPOT subject to TTFT SLO: Conversely, if TPOT attainment is low, the scheduler will prioritize actions that reduce TPOT, while ensuring TTFT SLOs are maintained.

The solution to this constrained optimization problem determines the optimal execution order and workload size for the current iteration. The talk notes that the solution is a heuristic approach, balancing computational tractability with effectiveness.

Let's delve into the heuristic solutions for each optimization objective:

• Scenario 1: Optimizing TTFT Subject to TPOT SLO

In this case, the primary goal is to improve the time to receive the first token for new requests, without degrading the token generation rate for ongoing requests beyond their SLO.

1. Prioritization: Prefill requests are prioritized. This is intuitive, as prefill completion is a prerequisite for TTFT.
2. Ordering within Prefill: Among the waiting prefill requests, they are sorted by their predicted TTFT. This prediction considers factors like their input prompt length (longer prompts take more time) and their waiting time in the queue. Requests closer to violating their TTFT SLO would receive higher priority.
3. Workload Control (Batching): A critical constraint is to prevent decode requests from waiting too long or being batched too large, which would violate their TPOT SLO. SOLA "computes exactly how many tokens can be batched" for the current iteration. This involves complex calculations considering available GPU memory, current KV cache usage, the computational cost of different-sized prefill requests, and the number of decode requests that must be processed to maintain their TPOT. The goal is to fill the batch with as many high-priority prefill requests as possible, while leaving sufficient capacity and scheduling slots for decode requests to meet their TPOT targets.

• Scenario 2: Optimizing TPOT Subject to TTFT SLO

Here, the focus shifts to ensuring smooth, fast token generation for ongoing requests, while still preventing new requests from experiencing excessively long TTFTs.

1. Prioritization: Decode requests are prioritized. This ensures that token generation continues without significant stalls.
2. Ordering within Decode: Decode requests are sorted according to their predicted TPOT. Requests with higher predicted TPOT (e.g., those that have been waiting longer, or are part of a larger batch) are given higher priority.
3. Workload Control (Batching): The principle here is to limit the number of waiting prefill requests to ensure their TTFT SLO is satisfied. The system "computes how many prefill requests can be retained in waiting" without violating their TTFT. This means that while decode requests take precedence, a certain number of prefill requests must still be processed within a given timeframe to prevent their TTFT from exceeding the limit. This involves carefully managing the batch composition to include a mix of decode and prefill requests such that both sets of SLOs are balanced.

The monitoring of states is conducted at the iteration level, meaning after each token is generated, system and request states are collected. The overhead of this monitoring is stated to be "negligible" because these states are inherently part of the scheduling process and are already accessed for decision-making in any advanced scheduler. SOLA merely formalizes their collection and utilization within a feedback loop.

This intricate dance between state awareness, predictive modeling, and dynamic constrained optimization allows SOLA to achieve a level of fine-grained control over LLM serving that significantly outperforms static or less adaptive scheduling strategies.

Experimental Setup & Results

▶ Watch: Heuristic approach for execution order and workload size (8:30)

The primary objective of SOLA's experimental evaluation was to demonstrate its ability to improve SLO attainment for large language model serving, which in turn leads to a higher request rate per second (RPS) and ultimately lower operational costs. The experiments focused on assessing SOLA's performance across various LLM models and datasets, although specific model names, sizes, or dataset details were not explicitly enumerated in the presentation, the claim is general applicability.

Baselines for Comparison:

To validate SOLA's effectiveness, its performance was benchmarked against several established and high-performance LLM serving schedulers:

1. vLLM (Split-Fused Strategy): One of the strategies from the popular vLLM serving engine. This strategy typically prioritizes decode requests while attempting to chunk prefill requests and batch them together when token budgets allow. This aims to maximize GPU utilization for the decode phase.
2. vLLM (Default Strategy): The default scheduling strategy employed by vLLM, which often prioritizes prefill requests to reduce TTFT, potentially at the expense of TPOT for ongoing generations.
3. FastServe (Shortest Job First - SJF Strategy): A scheduling strategy inspired by the Shortest Job First (SJF) principle, where requests with shorter estimated execution times are prioritized. In LLM serving, this often translates to prioritizing shorter prompts or those with fewer remaining tokens to generate.

Evaluation Metrics:

The experiments measured two key aspects of performance:

• SLO Attainment: The percentage of requests that successfully meet both their TTFT and TPOT latency constraints. This was evaluated for both 90% and 99% attainment levels, representing different levels of service quality.
• Highest Request Rate: The maximum number of requests per second (RPS) that the system could sustain while still meeting a specified SLO attainment target (e.g., 99% of requests within X ms TTFT and Y ms TPOT). This metric directly quantifies the system's efficiency and capacity.

Headline Results:

The main result highlighted by the speaker was a significant improvement in SLO attainment across the tested models and datasets when using SOLA. While specific numerical improvements (e.g., "X% higher attainment") were not detailed in the presentation, the emphasis was on the consistent and substantial gains over the baselines. This higher attainment directly translates to the ability of the system to serve a higher request rate per second under the same SLO constraints, implying lower infrastructure costs.

Visualization of Tradeoffs:

A crucial aspect of the experimental validation involved visualizing the latency distribution on a TTFT and TPOT plane. This visualization aimed to confirm whether SOLA's approach effectively addressed the two-fold tradeoffs identified as motivations for the work:

• Less Biased Distribution: The results showed that SOLA successfully made the latency distribution less biased, meaning that neither TTFT nor TPOT was significantly underserved compared to the other. This indicates a more balanced and coordinated optimization.
• Reduced Variance: The variance of the distribution was significantly reduced. This implies that different requests were treated more consistently, with fewer requests failing SLOs due to excessive latency and fewer requests having redundant budget. This demonstrates SOLA's ability to efficiently allocate resources.

In summary, the experimental results provided strong evidence that SOLA's state-aware, iteration-level scheduling, driven by constrained optimization, effectively addresses the challenges of LLM serving. By dynamically balancing TTFT and TPOT and managing priorities across requests, SOLA consistently achieved superior SLO attainment and higher throughput compared to prominent existing solutions.

Practical Implications

▶ Watch: Experimental results and SLO attainment improvement (10:00)

SOLA presents several significant practical implications for various stakeholders involved in deploying and managing large language models:

For Practitioners and Model Builders:

• Improved User Experience (UX): By consistently meeting both TTFT and TPOT SLOs, SOLA ensures a smoother and more responsive interaction for end-users. This is critical for applications where real-time feedback and continuous generation are paramount, such as chatbots, code assistants, and creative writing tools.
• Predictable Performance: The reduction in latency variance means that model builders can expect more predictable performance from their deployed models, simplifying performance tuning and capacity planning.
• Focus on Model Development: With an optimized serving infrastructure, model builders can focus more on improving model quality and capabilities rather than constantly battling serving bottlenecks.

For Infrastructure Teams and Deployers:

• Higher Throughput, Lower Costs: The most direct benefit is the ability to serve a higher volume of requests per second (RPS) on existing hardware, or to achieve the same RPS with fewer machines. This directly translates to significant cost savings in GPU/TPU resources, power consumption, and data center footprint, which are substantial for LLM deployments.
• Efficient Resource Utilization: SOLA's dynamic batching and prioritization ensure that expensive GPU resources are utilized more efficiently, minimizing idle cycles and maximizing the effective work done per unit of time.
• SLO Guarantees: Infrastructure teams can confidently set and meet stringent SLOs, crucial for enterprise-grade applications and contractual obligations. The system's ability to adapt to real-time conditions means it can better weather fluctuating workloads.
• Simplified Operations: While the underlying mechanism is complex, the goal is to provide a more robust and self-optimizing system, potentially reducing the manual effort required for load balancing and performance tuning.

Tradeoffs and Limitations:

• Focus on Non-Disaggregated Systems: As acknowledged by the speaker, SOLA's current focus is on non-disaggregated serving systems, where the prefill and decode phases run on the same set of machines. While disaggregated systems (e.g., Deepseek's approach) are gaining popularity for very large-scale deployments, SOLA remains highly relevant for scenarios like:
• Local or Private Deployments: Where fewer machines are available or preferred for cost, security, or data locality reasons.
• Edge Deployments: Where resource constraints are tight, and maximizing efficiency on a single GPU or a small cluster is critical.
• Smaller-Scale Services: For organizations that don't operate at hyper-scale but still require robust LLM serving.
• Heuristic Approach: The solution to the constrained optimization problem is heuristic. While effective and computationally tractable, it might not always achieve the theoretically global optimum. However, for real-world, dynamic systems, a good heuristic that performs well in practice is often preferred over an intractable optimal solution.
• Monitoring Overhead: While claimed to be negligible, any iteration-level monitoring and state collection adds some overhead. For extremely low-latency, high-throughput scenarios, even minor overheads can accumulate. However, the benefits of informed scheduling likely outweigh this cost.
• Cost Model Accuracy: The performance of SOLA relies on the accuracy of its online cost model. In highly dynamic environments or with novel model architectures, the cost model might require continuous tuning and adaptation to maintain its predictive power.

In essence, SOLA offers a pragmatic and powerful solution for optimizing LLM serving in environments where resource efficiency and strict SLO adherence are paramount. Its state-aware, adaptive scheduling paradigm represents a significant step forward in making LLM deployments more robust, cost-effective, and user-friendly.

Key Takeaways

• Large Language Model (LLM) serving introduces unique challenges due to distinct prefill (prompt processing) and decode (token generation) phases, each with critical latency metrics: Time To First Token (TTFT) and Time Per Output Token (TPOT).
• Existing LLM serving systems often exhibit suboptimal performance characterized by biased latency distributions (one metric favored over another) and high variance across requests, indicating unexploited tradeoffs.
• SOLA proposes a novel state-aware scheduling framework that uses an iteration-level feedback mechanism to dynamically adjust scheduling strategies based on real-time request and system states.
• At its core, SOLA formulates scheduling as a constrained optimization problem, aiming to optimize either TTFT (subject to TPOT SLO) or TPOT (subject to TTFT SLO), thereby coordinating performance across both phases.
• Experimental results demonstrate that SOLA significantly improves SLO attainment, leading to higher requests per second (RPS) and consequently lower operational costs for LLM serving, while also reducing latency distribution bias and variance.
• SOLA is particularly relevant for non-disaggregated LLM serving environments, such as local or private deployments with limited machines, where maximizing efficiency and meeting strict SLOs on consolidated resources is crucial.

About the Speaker(s)

The primary presenter for this work was Ke Hong, a PGD student affiliated with Tsinghua University. The research behind SOLA represents a collaborative effort, involving contributions from multiple academic institutions and industry partners. These collaborators include researchers from Tsinghua University, Shanghai Jiaotong University, Peking University, and Infinity AI. This inter-institutional collaboration highlights a shared commitment to advancing the field of large language model serving efficiency and performance.