Technical Summary: BlendServe

Problem Statement

Offline batch inference has emerged as a cost-effective solution for latency-insensitive Large Language Model (LLM) tasks, such as model evaluation and data curation. Unlike online inference, which prioritizes low latency, offline inference aims to maximize throughput (tokens per second) within a relaxed time window.

Existing throughput optimization techniques, such as chunked prefill (Sarathi-Serve) and operator-level overlapping (NanoFlow, Orion), focus on balancing compute and memory resources within a single batch. However, these approaches face diminishing returns as application diversity increases. Modern LLM workloads exhibit vastly different resource demands:

• Compute-intensive: Tasks with long input sequences but short outputs (e.g., document summarization, benchmarks like MMLU) saturate GPU compute units while leaving memory bandwidth underutilized.
• Memory-intensive: Tasks with long output sequences (e.g., video generation, reasoning) saturate memory bandwidth during the autoregressive decode phase while leaving compute units underutilized.

When a batch consists predominantly of one request type, hardware resources remain imbalanced, limiting throughput. Furthermore, simply reordering requests to maximize resource overlap often conflicts with prefix sharing, a technique that groups requests with common prefixes to avoid redundant computation. A request order that maximizes prefix sharing (typically Depth-First Search on a prefix tree) may result in batches dominated by a single resource type, while an order that maximizes resource overlap may destroy prefix locality.

Methodology: BlendServe

BlendServe is a serving system designed to harmonize resource-aware batching and prefix sharing to maximize offline inference throughput. Its core design involves three main components:

1. Performance Modeling and Compute Density

BlendServe introduces a metric called compute density ($\rho$), defined as the ratio of compute-bound operator time to memory-bound operator time for a request.

• Request Level: $\rho(r) = \frac{\text{Comp}(r)}{\text{Mem}(r)}$. High $\rho$ indicates compute-intensive workloads; low $\rho$ indicates memory-intensive workloads.
• Batch Level: The system models the total execution time $T$ as a function of compute time ($T_{comp}$), memory time ($T_{mem}$), and the prefix sharing ratio ($s$). The goal is to minimize $T$ by maximizing the overlap of compute and memory operations while minimizing redundant computation.
• Output Estimation: Since output lengths are unknown in autoregressive generation, BlendServe employs a sampling strategy during a warm-up phase. It infers output length distributions based on prompt semantics and task types, using sampled requests to estimate the density of unsampled requests within the same prefix subtree.

2. Resource-Aware Prefix Tree

To manage the trade-off between prefix sharing and resource overlap, BlendServe constructs a resource-aware prefix tree:

• Structure: Based on the Trie structure used in systems like SGLang, where nodes represent shared prompt segments.
• Enhancement: Each node is annotated with the compute density of all requests in its subtree.
• Sorting and Splitting: The system sorts nodes at each layer based on their compute density, placing compute-intensive nodes on the left and memory-intensive nodes on the right. To handle outliers that disrupt this global ordering, a conditional node splitting technique is used. If a node's density deviates significantly from its neighbors, it is split and repositioned. This incurs a controlled cost of recomputing a small prefix segment to achieve better resource balancing.

3. Dual Scanning Algorithm

To generate the final request schedule, BlendServe employs a dual scanning algorithm:

• Mechanism: The algorithm scans the leaves of the sorted prefix tree simultaneously from the left (compute-intensive) and right (memory-intensive) ends.
• Batch Formation: It dynamically calculates the required memory partition ($M_L$ and $M_R$) to achieve a target global compute density ($\rho_{target}$) that matches the root of the tree. Requests are selected from both ends to fill these partitions, ensuring that each batch contains a balanced mix of compute- and memory-intensive requests.
• Outcome: This approach preserves the hierarchical structure of the prefix tree (maintaining high prefix sharing) while interleaving requests to maximize hardware resource overlap.

4. Distributed Deployment

BlendServe supports Data Parallelism (DP) and Tensor Parallelism (TP).

• In DP, the centralized prefix tree is decomposed into subtrees assigned to different ranks, ensuring balanced workloads.
• In TP, the system integrates with existing pipeline strategies to overlap communication overhead with computation, maintaining compatibility with large-scale deployments.

Key Contributions

1. Analysis of Workload Diversity: A detailed characterization of how diverse LLM applications (chat, coding, video generation) create conflicting resource demands (compute vs. memory) that limit existing batching strategies.
2. Resource-Aware Prefix Tree: A novel data structure that encodes resource demands (compute density) while preserving prefix structures, enabling the system to reason about both prefix sharing and resource overlap simultaneously.
3. Dual Scanning Algorithm: A heuristic scheduling algorithm that constructs batches by scanning a sorted prefix tree from both ends, effectively blending request types to maximize resource overlap without sacrificing prefix sharing.
4. Prototype and Evaluation: A full implementation built on top of NanoFlow and SGLang, evaluated across multiple models (Llama-3-8B/70B, Qwen-2.5, DeepSeek) and diverse synthetic workloads.

Experimental Results

The authors evaluated BlendServe against industry-standard baselines (vLLM, SGLang) and state-of-the-art throughput-oriented systems (NanoFlow).

• Throughput Speedup:
  • Compared to vLLM and SGLang, BlendServe achieves up to 1.44× throughput speedup.
  • Compared to NanoFlow (the current state-of-the-art for throughput), BlendServe delivers an average 20.84% higher throughput.
• Optimality Gap: BlendServe achieves an average of 86.55% of the theoretical optimal throughput (up to 90% in specific configurations), demonstrating that it effectively approaches the limit of what is achievable with perfect resource overlapping and prefix sharing.
• Resource Utilization: Visualizations of compute and memory usage show that BlendServe maintains stable, balanced resource utilization across inference steps, whereas baselines like NanoFlow-DFS exhibit significant fluctuations and periods of resource underutilization.
• Prefix Sharing: Despite reordering requests for resource balance, BlendServe maintains 97% of the maximal prefix sharing ratio achievable by a standard DFS traversal.
• Scalability: The system demonstrates near-linear scaling with Data Parallelism (DP) and remains effective across different model sizes (7B to 72B) and hardware configurations.

Significance and Claims

The paper claims that BlendServe is the first serving system specifically optimized for offline batch inference that successfully harmonizes two traditionally conflicting objectives: resource overlapping and prefix sharing.

The authors argue that as LLM applications diversify, the assumption of uniform resource demands within a batch is no longer valid. By leveraging the relaxed latency constraints of offline inference to reorder requests, BlendServe unlocks significant throughput gains that previous intra-batch optimizations could not achieve. The system demonstrates that it is possible to approach optimal throughput (90%) without sacrificing the efficiency gains of prefix caching, providing a robust solution for cost-effective, high-throughput LLM inference.