Fast Heterogeneous Serving: Scalable Mixed-Scale LLM Allocation for SLO-Constrained Inference Jiaming Cheng and Duong Tung Nguyen
arXiv:2604.07472v1 [cs.LG] 8 Apr 2026
Arizona State University, Tempe, AZ, 85281, USA {jiaming,duongnt}@asu.edu
Abstract. Deploying large language model (LLM) inference at scale requires jointly selecting base models, provisioning heterogeneous GPUs, configuring parallelism, and distributing workloads under tight latency, accuracy, and budget constraints. Exact mixed-integer linear programming (MILP) approaches guarantee optimality but scale poorly. We propose two constraint-aware heuristics: a Greedy Heuristic (GH) for singlepass allocation, and an Adaptive Greedy Heuristic (AGH) that enhances GH via multi-start construction, relocate-based local search, and GPU consolidation. Three constraint-aware mechanisms—TP-aware feasibility selection, cost-per-effective-coverage ranking, and TP upgrade—ensure feasibility under tightly coupled memory, delay, error, and budget constraints. On workloads calibrated with the Azure LLM Inference Trace (2025), both heuristics produce feasible solutions in under one second, with AGH closely approaching optimal cost while achieving over 260× speedup on large-scale instances. Under out-of-sample stress tests with up to 1.5× parameter inflation, AGH maintains controlled SLO violations and stable cost, whereas the exact solver’s placement degrades sharply. Keywords: LLM inference, GPU provisioning, workload allocation, parallelism configuration, adaptive greedy heuristic
1
Introduction
Large language models (LLMs) have become central to modern AI services, powering applications from conversational assistants and code generation to multimodal content creation [1]. Serving diverse query types at scale requires LLM service providers (SPs) to jointly orchestrate multiple interrelated decisions— selecting base models, provisioning heterogeneous GPUs, configuring parallelism strategies, and routing workloads—all under tight service-level objectives (SLOs) on latency, accuracy, and budget. A growing body of work has advanced LLM inference efficiency along individual axes. Serving engines such as vLLM [2] and DistServe [3] optimize memory management and disaggregate prefill from decoding. DynamoLLM [4] reconfigures parallelism and GPU frequency for energy efficiency; Helix [5] formulates heterogeneous placement as a max-flow MILP; Jiang et al. [6] co-optimize GPU composition, deployment, and workload assignment via MILP scheduling. Kim
2
J. Cheng et al.
Fig. 1. System model: users submit queries classified by type, routed to heterogeneous GPU tiers hosting foundation models under TP/PP configurations.
et al. [12] study cost-efficient serving with heterogeneous VMs and KV cache offloading, SeaLLM [9] enables multi-LLM resource sharing, and SkyLB [11] proposes locality-aware cross-region load balancing. These works demonstrate the importance of heterogeneity-aware management but share a common limitation: they either rely on exact solvers whose runtime grows exponentially, or employ system-level heuristics that do not jointly optimize parallelism configuration with workload allocation under coupled SLO constraints. Despite this progress, the joint optimization of model selection, GPU provisioning, TP configuration, and workload distribution under coupled resource and SLO constraints remains underexplored from an algorithmic perspective. Existing systems either fix parallelism a priori and optimize routing alone [4], decompose into independent subproblems [9,12], or embed TP/PP in a monolithic MILP without scalable alternatives [5, 6]. The tight coupling—GPU memory limits feasible TP degrees, TP affects both prefill and decode latency, delay and error bounds jointly constrain allocatable workload—means that naive greedy strategies frequently produce infeasible solutions. Our algorithms integrate parallelism selection into the allocation loop via three constraint-aware mechanisms that jointly enforce memory, delay, error, and budget feasibility at every step. This paper shifts focus from exact MILP formulations to fast, constraintaware heuristic algorithms. Rather than relying on commercial solvers whose runtime can reach minutes to hours, we develop lightweight algorithms that produce feasible, near-optimal solutions in under one second—enabling real-time re-optimization as demand or GPU availability changes. Beyond computational efficiency, the algorithms exhibit robust operational performance: under outof-sample stress tests with up to 1.5× delay and error inflation, the heuristics maintain stable cost and controlled SLO violations, whereas the exact solver’s placement degrades sharply. Table 1 summarizes how our approach differs from prior work across five design dimensions. Compared to MILP-based systems [5,6] that achieve optimality but become intractable at scale, our heuristics provide over 260× speedup while maintaining near-optimal cost. Unlike system-level heuristics [4, 12] that optimize a single axis, our algorithms jointly determine parallelism, provisioning, and routing in a single allocation loop. Critically, the constraint-aware mechanisms (M1–M3) are not merely cost optimizations—they are feasibility prerequisites: our experiment shows that removing M1 or M3 renders solutions infeasible, a failure case absent from prior greedy approaches. Moreover, the sub-second runtime
Title Suppressed Due to Excessive Length
3
Table 1. Comparison with related approaches across key design dimensions. System
TP/PP Coupled Scalable Stress Constr.+ route SLOs solver robust aware
DynamoLLM [4] Helix [5] Jiang et al. [6] Kim et al. [12] SeaLLM [9]
– ✓ ✓ – –
✓ – ✓ ✓ –
✓ – – ✓ ✓
– – – – –
– – – – –
GH / AGH (ours)
✓
✓
✓
✓
✓
of AGH enables rolling re-optimization every 5 minutes, saving up to 48% over a static MILP under high demand volatility. Finally, our two-stage evaluation reveals that cost-minimal exact solutions are fragile under operational uncertainty, while the heuristics’ built-in conservatism provides inherent robustness—an advantage not demonstrated by prior work. Contributions. (C1) We formulate the joint model selection, GPU provisioning, joint TP/PP parallelism configuration, and workload allocation problem as a MILP with a two-phase delay model capturing TTFT and generation latency under TP/PP configuration. The formulation integrates memory, delay, and accuracy constraints. (C2) We propose a Greedy Heuristic (GH) using three constraint-aware mechanisms—(M1) constraint-aware configuration selection, (M2) cost-per-effective-coverage ranking, and (M3) parallelism upgrade for active GPUs—and an Adaptive Greedy Heuristic (AGH) that enhances GH via multi-start construction, relocate-based local search, and consolidation. (C3) Using workloads from the Azure LLM Inference Trace [13], we show that AGH matches or closely approaches optimal cost while achieving over 260× speedup on large-scale instances where the exact solver exceeds time limits, and maintains stable cost and controlled SLO violations under 1.5× out-of-sample stress where the exact solver degrades sharply.
2
System Model and Problem Formulation
2.1
System Model
We consider a service provider (SP) that rents heterogeneous GPU instances from a cloud platform to serve LLM inference workloads over a planning horizon ∆T . Users submit inference requests that are classified into I distinct query types i ∈ I (e.g., summarization, code generation, translation), each characterized by an arrival rate λi (queries/hour), an average input length of hi tokens, and an expected output length of fi tokens. The aggregate token count per query is ri = hi + fi . 1) Foundation Models: The SP maintains a catalog of J pre-trained foundation models j ∈ J , spanning a range of capacities from lightweight (e.g., 1B parameters) to large-scale (e.g., 70B). Each model j has a weight size of Bj (GB) and a per-token key–value (KV) cache memory footprint of βj (bytes/token). Larger models generally yield higher output quality but impose greater memory and computational demands.
4
J. Cheng et al.
2) GPU Resource Tiers: Inference jobs execute on resource tiers k ∈ K, where each tier pairs a specific GPU hardware type with a numerical precision level (e.g., H100–FP16, A6000–INT8). Tier k is characterized by its GPU memory capacity CkGPU (GB), compute throughput PkGPU (TFLOPs), and per-GPU hourly rental cost pck ($/hr). Higher-precision modes yield better inference accuracy but incur larger per-token latency and rental expense; quantized modes (INT8, INT4) trade accuracy for reduced cost. 3) Parallelism Configuration: For each deployed model–tier pair (j, k), the SP selects both a tensor parallelism (TP) degree and a pipeline parallelism (PP) depth. TP partitions the model’s weight matrices across co-located GPUs within a single pipeline stage, reducing per-device memory requirements and accelerating the compute-bound prefill phase at the cost of inter-GPU communication overhead during autoregressive decoding. PP distributes the model’s layers across sequential pipeline stages, enabling larger models to fit across multiple GPU groups at the cost of pipeline bubble overhead. Formally, the SP selects a TP degree n ∈ Nk from a hardware-dependent feasible set (e.g., {1, 2, 4, 8}) and a PP depth m ∈ M from a system-wide feasible n,m set (e.g., {1, 2, 4}). Binary variable wj,k ∈ {0, 1} indicates whether model j on tier k uses the joint configuration (TP = n, PP = m), and deployment flag qj,k ∈ {0, 1} records whether model j is active on tier k. The total number of tier-k GPUs allocated to model j is: X n,m yj,k = n · m · wj,k . (1) (n,m)∈Nk ×Mk
These yj,k GPUs are organized as TPj,k = n tensor-parallel devices within each of PPj,k = m pipeline stages, yielding the identity TPj,k × PPj,k = yj,k . This decomposition enters the model in two ways: TP governs per-stage memory and computation in the delay model (2), while PP determines inter-stage communication overhead and introduces pipeline bubble inefficiency captured by the factor η ≤ 1 in the compute constraint (5g). 4) Processing Delay: We decompose the processing delay into TTFT (prefill) TTFT and generation (decode) phases. The TTFT for query type i on (j, k) is Di,j,k = comp comp di,j,k hi /TPj,k , where di,j,k is the per-token computational cost. The generation Gen delay includes inter-stage communication under pipeline parallelism: Di,j,k = comp comm comm (di,j,k /TPj,k + PPj,k · di,j,k ) · fi , where di,j,k is the per-token communication delay and PPj,k = yj,k /TPj,k is the number of pipeline stages. The aggregate processing delay is: comp X di,j,k · ri + PPj,k · dcomm · f , ∀i (2) Diproc = xki,j i i,j,k TPj,k j,k
where ri = hi + fi . Substituting TPj,k = n and PPj,k = m via the joint selector n,m wj,k yields the MILP-compatible form: comp X X proc n,m di,j,k · ri k comm + m · di,j,k · fi , ∀i (3) Di = xi,j · wj,k n j,k (n,m)
Title Suppressed Due to Excessive Length
5
n,m The product xki,j · wj,k is bilinear (continuous × binary). We linearize via Mcn,m k,n,m = xki,j · wj,k Cormick envelopes: for each product we introduce auxiliary vi,j n,m with xki,j ∈ [0, 1] and wj,k ∈ {0, 1}, satisfying: k,n,m vi,j ≤ xki,j ,
k,n,m n,m vi,j ≤ wj,k ,
k,n,m n,m vi,j ≥ xki,j + wj,k − 1,
k,n,m vi,j ≥ 0. (4)
n,m Since TP and PP are selected jointly by the binary wj,k , no trilinear terms arise—a single McCormick layer suffices. We define the per-configuration delay k comm shorthand Di,j (n, m) = dcomp i,j,k ri /n + m · di,j,k · fi , a constant for given (n, m), so P k,n,m k Di,j (n, m). Increasing TP reduces computation that Diproc = j,k,(n,m) vi,j in both phases, while increasing PP adds inter-stage communication overhead that scales with fi .
2.2
Optimization Problem
The SP jointly determines: (1) resource provisioning yj,k ∈ Z+ and deployn,m ment flag qj,k ∈ {0, 1}; (2) parallelism configuration via wj,k ∈ {0, 1} with P n,m k w = q ; (3) workload routing fractions x ∈ [0, 1] with placement j,k i,j n,m j,k k indicator zi,j ∈ {0, 1}; and (4) unserved demand ui ∈ [0, ζi ]. The deterministic placement problem PDM minimizes total operational cost: X X X k PDM : min ∆T pck yj,k + ∆T ps Bj zi,j + ∆T ps θi ri λi xki,j x,y,z,u,w
j,k
|
i,j,k
{z
}
|
(i) GPU rental
X
+
i
|
X
|
{z
(iii) data storage
}
ϕi ui
(5a)
i
{z
}
| {z }
(iv) delay penalty
s.t.
i,j,k
}
(ii) model storage
X
ρi Diproc +
{z
(v) unmet penalty
xki,j + ui = 1, ∀i
(5b)
j,k
∆T
X
pck yj,k + ∆T
X
k ps Bj zi,j + θi (hi + fi )λi xki,j ≤ δ
j,k
i,j,k
X
n,m wj,k = qj,k , ∀j, k
(5c) (5d)
(n,m)∈Nk ×M
yj,k =
X
n,m n · m · wj,k , ∀j, k
(5e)
(n,m)∈Nk ×M
X Bj
n,m wj,k +
X βj
n,m wj,k ·
X
res ri Ti,j,k xki,j ≤ CkGPU qj,k , ∀j, k nm nm n,m n,m i X r λ i i k αi,j xki,j ≤ η Tconv PkGPU yj,k , ∀j, k 3 10 i X k Bj zi,j + θi ri λi xki,j ≤ C s
(5h)
j,k Diproc ≤ ∆i ,
(5i)
∀i
(5f) (5g)
6
J. Cheng et al.
X
ēki,j xki,j ≤ ϵi , ∀i
(5j)
j,k k 0 ≤ xki,j ≤ zi,j ≤ qj,k , ∀i, j, k
(5k)
Objective. The five terms capture: (i) GPU rental at rate pck ; (ii) model weight storage at rate ps ; (iii) token data storage (θi : per-token size); (iv) delay penalty weighted by ρi ; and (v) unmet demand penalty weighted by ϕi . Constraints. Constraint (5b) enforces supply–demand balance, recording any residual as unmet demand ui . Constraints (5d)–(5e) select (TP, PP) Pexactly onen,m configuration per active model–tier pair, with yj,k = nm · w n,m j,k . Constraint (5f) ensures the per-GPU model weight shard Bj /(nm) plus KV cache res βj /(nm) (scaled by token count and residency time Ti,j,k ) fits within GPU memGPU ory Ck ; PP further reduces per-GPU memory by distributing layers across m pipeline stages. Constraint (5g) bounds aggregate throughput against available k FLOPs, where αi,j is per-token compute cost (GFLOP/token), 103 aligns token units with TFLOPs, Tconv converts seconds to hours, and η ≤ 1 captures PP bubble overhead. Constraint (5h) caps total storage at C s ; (5i)–(5j) enforce delay (Diproc ≤ ∆i ) and error (≤ ϵi ) SLOs; and (5k) restricts routing to deployed configurations. Problem PDM has O(IJK) continuous and O(IJK +JK|N ||M|) binary variables, motivating scalable heuristics.
3
Solution Approach
The MILP formulation PDM can be solved exactly for moderate instances but its runtime grows exponentially as the problem scales. Moreover, the SP may need to re-solve the allocation problem frequently as demand shifts, requiring solutions in seconds rather than minutes. A fast heuristic that produces feasible, near-optimal solutions is therefore operationally essential. A key challenge specific to this problem is that the constraints are tightly coupled : GPU memory limits which TP degrees are feasible, TP choice directly affects processing delay, delay and error bounds jointly limit the allocatable workload fraction, and the budget caps the total number of activated GPUs. A standard greedy strategy that ranks candidates by cost alone ignores these dependencies and frequently yields infeasible solutions. This motivates the three constraint-aware mechanisms described below, which are shared by both the GH and AGH algorithms. 3.1
Three Constraint-Aware Mechanisms
M1 - Constraint-Aware Configuration Selection For each candidate placement (i, j, k), the algorithm determines the minimum-cost feasible (TP, PP) configuration that simultaneously satisfies GPU memory capacity and the delay threshold: Bj GPU k ∗ ∗ ≤ Ck , Di,j (n, m) ≤ ∆i . (6) (n , m )(i, j, k) := argmin nm : nm (n,m)∈Nk ×M If no feasible (n, m) exists, the candidate (i, j, k) is discarded entirely. This prevents placements where the model does not fit in GPU memory or the resulting delay violates the SLO.
Title Suppressed Due to Excessive Length
7
M2 - Cost-Per-Effective-Coverage Ranking: Candidates are ranked not by raw cost but by cost per unit of effective demand served. The marginal cost of placing query i on configuration (j, k) includes activation, storage, and delay penalty: k cki,j = ∆T pck (n̂m̂−yj,k )+ +ps (Bj +θi ri λi ) + ρi Di,j (n̂, m̂), ∀i, j, k, (7) where (n̂, m̂) is the required (TP, PP) configuration and (n̂m̂−yj,k )+ is the extra GPU cost (zero for already-active configurations). The effective coverage is the maximum allocatable fraction, limited by both the error and delay budgets: ϵi − Eiused ∆i − Diused k , , ∀i, j, k (8) x̄i,j = min r̃i , k (n̂, m̂) ēki,j Di,j where r̃i is the remaining unserved demand and Eiused , Diused track cumulative error and delay from prior placements. Candidates are sorted by (τ, µ) where ck
τ = 1[x̄ki,j < r̃i ] prioritizes full-coverage candidates and µ = x̄i,j is the unit cost. k i,j
M3 - Parallelism Upgrade for Active GPUs: When query i is routed to an already-active configuration (j, k) with current GPU allocation yj,k , but the current delay exceeds ∆i , the algorithm seeks a higher-parallelism configuration: k (n̂, m̂) = argmin nm > yj,k : Di,j (n, m) ≤ ∆i , budget allows . (9) (n,m)
Rather than activating a new (j, k) pair from scratch, this adds only (n̂m̂ − yj,k ) extra GPUs to the existing configuration, reusing the already-loaded model weights. 3.2
Greedy Heuristic (GH)
GH performs a single-pass allocation in two phases (Algorithm 1), invoking M1– M3 throughout to ensure feasibility at every step. Phase 1: Coverage pre-allocation (lines 2–5) operates as a greedy setcover, ensuring every query type has at least one feasible configuration. The feasible coverage set and activation cost for each pair (j, k) are: Fj,k = i ∈ I unc : (n∗, m∗ )(i, j, k) exists via M1, ēki,j ≤ ϵi , (10) Cost(j, k) = ∆T pck max n∗ (i, j, k)·m∗ (i, j, k). i∈Fj,k
(11)
The algorithm greedily selects (j ∗, k ∗ ) = argmaxj,k |Fj,k |/Cost(j, k) and repeats until all types are covered or the budget cap βδ (β = 0.8) is reached. Phase 2: Sequential allocation (lines 6–20) processes queries in descending λi order. For each query i and candidate (j, k): (1) determine (n̂, m̂) via M1 (6) or M3 (9), discarding infeasible candidates; (2) compute effective coverage x̄ki,j via (8); (3) rank by (τ, µ) where τ = 1[x̄ki,j < r̃i ] prioritizes full-coverage and µ = cki,j /x̄ki,j is unit cost via (7); and (4) verify constraints (5f)–(5h) and budget δ before committing xki,j = min(ui , x̄ki,j ).
8
J. Cheng et al.
Algorithm 1 Greedy Heuristic (GH) ¯ ē, ∆i , ϵi , δ) Require: Data (I, J , K, N k , M, d, Ensure: Allocation (x, y, z, u) 1: Initialize xki,j ← 0, yj,k ← 0, ui ← 1, I unc ← I, ∀i, j, k 2: // Phase 1: Coverage pre-allocation 3: while I unc ̸= ∅ and budget < β · δ do 4: Compute Fj,k via (10) and Cost(j, k) via (11), ∀j, k 5: Activate (j ∗, k∗ ) = argmaxj,k |Fj,k |/Cost(j, k); update I unc , budget, y 6: end while 7: // Phase 2: Sequential allocation 8: for each query i sorted by λi descending do 9: for each candidate (j, k) do 10: Step 1: Determine (n̂, m̂) via M1 (6) or M3 (9) 11: Step 2: Compute x̄ki,j via (8); discard if ≤ 0 12: Step 3: Compute cki,j via (7); record (τ, µ) 13: end for 14: Sort candidates by (τ, µ) ascending 15: for each (j, k) in sorted order while ui > 0 do 16: Step 4: Verify (5f)–(5h) and budget δ 17: if all constraints satisfied then 18: xki,j ← min(ui , x̄ki,j ); ui ← ui − xki,j 19: Update Eiused , Diused , y, budget 20: end if 21: end for 22: end for 23: return (x, y, z, u)
3.3
Adaptive Greedy Heuristic (AGH)
While GH is efficient, its single-pass structure has three limitations: (i) the solution quality depends on the order in which query types are processed; (ii) once a workload fraction is assigned, it cannot be revised even if a better candidate appears later; and (iii) GPUs activated early may remain underutilized. AGH (Algorithm 2) addresses these via three enhancements: – Multi-start construction (lines 2–5): generates 8 deterministic orderings (ascending/descending for each of λi , ϕi , storage footprint, and error tightness) plus R random permutations, retaining the best GH solution. – Relocate (lines 6–9): up to L = 3 passes of local search, moving active assignments (i, j, k) to alternative (j ′ , k ′ ) when feasible and cost-improving. – Consolidate (lines 10–12): redistributes queries from lightly loaded GPUs to other active configurations and deactivates freed instances, reducing GPU rental cost. 3.4 Complexity Analysis Remark 1. GH runs in O(I 2 JK + IJK log(JK)), dominated by the Phase 1 set-cover (I iterations, each O(IJK)) and Phase 2 sorting (O(JK log(JK))
Title Suppressed Due to Excessive Length
9
Algorithm 2 Adaptive Greedy Heuristic (AGH) Require: Data, R random starts, max local search iterations L Ensure: Best allocation (x∗ , y∗ , z∗ , u∗ ) 1: best_obj ← ∞ 2: Generate orderings Σ = {σ1 , . . . , σ8 } ∪ {R(n) random} [R adaptive, see Remark.1] 3: for each ordering σ ∈ Σ do 4: (x, y, z, u) ← GH-Construct(σ) [M1, M2, M3] 5: // Local Search: relocate 6: for iter = 1, . . . , L do 7: for each (i, j, k) with xki,j > 0 do 8: Try move to (j ′, k′ ); accept if feasible & cost-improving 9: end for 10: end for 11: // Local Search: consolidate 12: for each active (j, k) in ascending order of load do 13: Redistribute queries; deactivate (j, k) if feasible & improving 14: end Pfor 15: if ℓ Cℓ < best_obj then 16: (x∗, y∗, z∗, u∗ ) ← (x, y, z, u); update best_obj 17: end if 18: end for 19: return (x∗ , y∗ , z∗ , u∗ )
per query). AGH executes (8 + R) starts—8 deterministic orderings (ascending/descending λi , ϕi , storage, ϵi ) plus R random—each with GH construction, L relocate passes in O(L · I 2 J 2 K 2 ), and consolidation absorbed by relocate, yielding O (8 + R) · [I 2 JK + IJK log(JK) + L · I 2 J 2 K 2 ] . The random start count R adapts to problem scale N = IJK: R = 3 for N > 5000, R = 5 for N > 2000, R = 10 for N > 500, R = 20 otherwise; construction terminates early after five consecutive non-improving orderings; L = 3.
4
Numerical Results
4.1
Simulation Setup
We consider I = 6 query types (Summarization, Code, Translation, Math Solving, Image, Video), J = 6 Llama-3.x models (1B–70B, Bj = 2–140 GB, KV cache βj = 31–305 µB/token) [14], and K = 10 GPU tiers spanning A6000 (24 GB), RTX 4090 (24 GB), A100-40 GB, and H100-80 GB with FP16/INT8/ INT4 precision.1 TP degrees N = {1, 2, 4, 8}; PP depths M = {1, 2, 4}; the n,m joint selector wj,k yields bilinear (not trilinear) delay terms, requiring only a single McCormick layer. Arrival rates λi (queries/h) range from 1,000–3,000 (Video Gen.) to 18,000–25,000 (Summarization) [17]; delay SLOs ∆i = 1.5– 25 s [4]; error thresholds ϵi = 2–8%. GPU rental pck = $0.35–$2.50/h [10]; budget 1
GPU memory 24–80 GB, bandwidth 768–3350 GB/s, compute 40.7–1484 TFLOPS; from NVIDIA datasheets.
10
J. Cheng et al.
δ = $100; horizon ∆T = 24 h; storage capacity C s = 1000 GB; Phase-1 budget fraction β = 0.8. Storage price ps ∼ U[0.0005, 0.001] $/GB/h (cloud object-storage pricing). Delay penalty ρi ($/ms/query) is task-dependent: ρi ∈ [0.0001, 0.0003] for text tasks (Summarization, Translation), [0.0005, 0.0008] for Math Solving, and [0.0005, 0.001] for Image/Video Generation. Unmet-demand penalty ϕi ($/dropped query): $1,000–$1,500 for text tasks, $2,000–$3,000 for mediageneration tasks. Token storage footprint θi (KB/token) [2]: 10–14 (text), 40–60 (image), 80–120 (video). GPU utilization efficiency η = 0.9 [18]; time conversion Tconv = 3600 s/h converts GPU compute (TFLOPS) to per-hour capacity in (5g); all cost terms involving λi are multiplied by ∆T . k Per-token compute cost αi,j is derived from model FLOPs scaled by tier res precision; residency time Ti,j,k = ri βj /BWk ; communication delay dcomm foli,j,k lows from NVLink bandwidth (600–900 GB/s) and activation size. Computation delays follow the memory-bandwidth-bound decode model [15]: dcomp i,j,k = τi Bj σk /BWk , where τi is task-specific overhead, σk is the quantization scale (FP16: 1, INT8: 0.5, INT4: 0.25) [16], and BWk is GPU memory bandwidth. Quantized modes inflate error by ×1.15 (INT8) and ×1.35 (INT4) [16]; KV cache from model architecture [2]. All experiments are conducted based on Python 3.13, Gurobi 11 [8]. Source code is available at https://github.com/ JJmingcc/FastLLM. 4.2
Performance Evaluation
We employ a two-stage evaluation with S = 500 scenarios (delays/errors perturbed ±25%, arrivals ±20%). Stage 1 (Decision): Each algorithm computes (y∗ , z∗ , w∗ ) from nominal parameters. Stage 2 (Operation): Placement is fixed; for each scenario ℓ with realized (d˜ℓ , ẽℓ , λ̃ℓ ) we solve: Pa : min C4 (x; d˜ℓ ) + C5 (u) x,u P k s.t. j,k xi,j + ui = 1, ∀i P k k GPU ∗ yj,k , ∀j, k i α̂i,j ri λ̃i,ℓ xi,j ≤ ηTconv Pk P k ∗ ∗ ˜ k j,k Di,j (n , m ; dℓ ) xi,j ≤ ∆i , ∀i P k k j,k ẽi,j,ℓ xi,j ≤ ϵi , ∀i k,∗ 0 ≤ xki,j ≤ zi,j ,
∀i, j, k
(12a) (12b) (12c) (12d) (12e) (12f)
k k where α̂i,j = αi,j /103 absorbs the unit-scaling factor from (5g). Since placements P are fixed, Pa is a pure LP. We report expected total cost C a = C1 +C2 + S1 ℓ [C3 + P 1 C4 +C5 ] and SLO violation rate Pviol = SI ℓ,i 1(ui,ℓ > 0.01). Model comparison: Figs. 2(a)–2(b) compare all three methods under 1.2× and 1.5× delay/error inflation. Under nominal conditions, the exact MILP solver (DM) achieves the lowest cost. However, under stress, both GH and AGH achieve lower actual cost and SLO violation rates—a result explained by Fig. 2(c): the heuristics allocate moderately higher GPU rental (the dominant C1 term), provisioning headroom that absorbs demand fluctuations, whereas DM’s cost-minimal
Title Suppressed Due to Excessive Length
11
Table 2. Stage-2 evaluation under varied budget and penalty settings. Algo.
Pay.
Cost (C a )
Viol. (%)
GH S2: Tight AGH δ = $75, ϕv = 1× Gap
63.1 53.8 −14.7%
314.4 136.6 −57%
1.5 0.6 −60%
GH S3: Critical AGH δ = $72, ϕv = 1× Gap
63.1 35.5 −43.7%
1162.0 343.0 −70%
14.2 3.7 −74%
GH S4: Hi. pen. AGH δ = $75, ϕv = 5× Gap
63.1 53.8 −14.7%
964.0 140.0 −86%
1.5 0.6 −60%
GH S5: Hi. pen. + critical AGH δ = $72, ϕv = 5× Gap
63.1 35.5 −43.7%
1811.0 344.0 −81%
14.2 3.7 −74%
Scenario
ϕv scales ϕ4 (Image Gen.) & ϕ5 (Video Gen.). S1 (baseline, δ = $100): GH=AGH=$145.8.
placement incurs large unmet demand penalties (C5 ) when parameters deviate. This conservatism arises naturally from the constraint-aware mechanisms, which select TP degrees with feasibility margins and favor configurations that cover more query types per GPU. Under tight and critical budgets (Table 2), AGH’s advantage over GH becomes pronounced: at δ = $72 (S3), AGH reduces actual cost by 70% and SLO violations by 74% relative to GH. The multi-start construction explores diverse allocations, while consolidation eliminates fragmented GPU usage—effects that compound under budget pressure. Key insight 1: The constraint-aware mechanisms implicitly provision headroom, yielding placements that are nominally suboptimal but more robust under perturbation—periodic heuristic re-optimization thus outperforms a single exact solve. Moreover, AGH’s advantage over GH compounds under budget pressure, achieving up to 81% cost reduction at critical budgets (S5). Sensitivity analysis: Figs. 2(d)–2(f) vary parameters pairwise. Tightening ∆i forces higher TP degrees while stricter ϵi restricts feasible pairs—both increase cost, with delay the stronger driver (Fig. 2(d)). Rising pck shifts AGH toward fewer, higher-capacity tiers (Fig. 2(e)); relaxing ∆i enables lower TP degrees, reducing GPU count and cost (Fig. 2(f)). Ablation: Table 3 disables each mechanism individually. Removing M1 or M3 renders solutions infeasible (memory violation and delay violation, respectively); removing M2 preserves feasibility but inflates cost by >50%. Key insight 2: M1 and M3 are feasibility prerequisites—not mere optimizations— distinguishing constraint-aware allocation from standard GRASP heuristics [7] where ranking affects quality but not feasibility. Run time: Table 5 shows MILP runtime grows exponentially, exceeding the 600 s limit at (15, 15, 10), while GH remains sub-second and AGH stays under 10 s—over 260× speedup at (20, 20, 20). This makes both algorithms practical as
12
J. Cheng et al.
(a) Actual cost
(b) SLO violation (%)
(c) Cost breakdown
(d) Varying ∆ and ϵ
(e) Varying δ and pck
(f) Varying pck and ∆
Fig. 2. (a)–(c): Model comparison under delay/error stress. (d)–(f): AGH sensitivity analysis over SLO thresholds ∆i , ϵi , budget δ, and rental cost pc . Table 3. Ablation of constraint-aware mechanisms. Configuration
Feasible?
Cost ($)
AGH (all mechanisms) Yes 89.88 w/o M1 (TP selection) No (memory/delay violation) — w/o M2 (cost ranking) Yes 134.52 (>50%) w/o M3 (TP upgrade) No (delay violation) —
a planning layer re-invoked periodically or on-demand alongside serving engines such as vLLM [2]. 4.3
Rolling-Horizon Adaptation
The sub-second runtime of GH and AGH enables a practical advantage unavailable to the MILP solver: rolling re-optimization. We divide the 24-hour rental period (∆T = 24 h) into 288 × 5-minute windows and let demand evolve as a geo(t+1) (t) metric random walk, λi = λi exp(N (0, σ)), where σ is the per-step (5-min) volatility. Five levels σ ∈ {0.01, 0.02, 0.03, 0.04, 0.05} are tested, producing cumulative demand standard deviations of roughly 17%, 34%, 51%, 68%, and 85% over the full horizon. Static methods (DM-24h, GH-24h, AGH-24h) solve once at t = 0 and keep the same configuration for the entire 24 hours; the rolling method (AGH-5min) re-solves every 5 min and adopts the new configuration only if it improves upon the incumbent (keep-best strategy). Table 4 reports mean±std over 30 independent trials with 288 windows each. Three observations emerge. First, GH is immune to re-optimization: its deterministic ordering by λi preserves the same relative ranking after demand drifts, so re-solving reproduces the static solution in every trial (cost rises only +6% across all σ). Second, AGH benefits substantially once volatility is high:
Title Suppressed Due to Excessive Length
13
Table 4. Rolling-horizon re-optimization: mean±std cost ($) over the 24-hour rental period (30 trials, 288 windows each). Bold marks the lowest mean cost at each σ.
σ = 0.01 σ = 0.02 σ = 0.03 σ = 0.04
σ = 0.05
381±2 447±75 507±178 793±529 468±3 471±6 475±12 472±5 414±2 418±8 430±30 525±214 414±2 420±12 432±24 434±23
909±509 498±44 564±173 474±56
AGH-5 min vs AGH-24 h 0.0% +0.9% +0.4% −17.3% AGH-5 min vs DM-24 h +8.6% −5.6% −14.7% −45.2%
−16.0% −47.9%
DM-24h GH-(Any)† AGH-24h AGH-5min
†
GH-5min and GH-24h produce identical costs; GH’s deterministic ordering is invariant to demand drift, making re-optimization frequency irrelevant. Table 5. Runtime scaling with network size (seconds). Method (4, 4, 5) (6, 6, 10) (10, 10, 10) (15, 15, 10) (20, 20, 20) DM GH AGH
0.39 4.2 < 0.01 < 0.01 0.0149 0.113
13.04 0.3 0.57
601.12 0.5 1.09
> 600 0.9 2.3
at σ ≥ 0.04, AGH-5min saves 16–17% over static AGH-24h while reducing cost variance by 4–8× ($23–$56 vs. $173–$214 std), because its stochastic multi-start construction discovers genuinely different solutions when demand shifts. Third, the static MILP degrades sharply: DM-24h is optimal at σ = 0.01 ($381) but exceeds $793–$909 at σ ≥ 0.04, while AGH-5min saves up to 48%. Key insight 3: The sub-second runtime of AGH creates a compounding operational advantage: by re-solving every 5 minutes with updated observations, the SP accumulates frequent low-cost adjustments that a deterministic heuristic (GH) structurally cannot exploit and a MILP solver cannot support at the same granularity.
5
Conclusion
We proposed GH and AGH for joint model selection, GPU provisioning, parallelism configuration, and workload allocation under coupled delay, error, memory, compute, and budget constraints. The three constraint-aware mechanisms are feasibility prerequisites—not mere optimizations—as the ablation confirms. AGH closely approaches optimal cost while achieving >260× speedup, and maintains stable performance under 1.5× out-of-sample stress where the exact solver degrades sharply. Sub-second runtimes enable rolling-horizon re-optimization: re-solving every 5 minutes with updated observations compounds frequent adjustments into robust performance without explicit uncertainty modeling. Future work will incorporate stochastic optimization, queuing and continuous batching dynamics, and real cluster validation.
14
J. Cheng et al.
References 1. A. Chien, L. Fan, and H. Yeung, “Reducing the carbon impact of generative AI inference (today and in 2035),” arXiv preprint arXiv:2304.03271, 2023. 2. W. Kwon, Z. Li, S. Zhuang, Y. Sheng, L. Zheng, C.H. Yu, J. Gonzalez, H. Zhang, and I. Stoica, “Efficient memory management for large language model serving with PagedAttention,” in Proc. SOSP, 2023. 3. Y. Zhong, S. Liu, J. Chen, J. Hu, Y. Zhu, X. Liu, X. Jin, and H. Zhang, “DistServe: Disaggregating prefill and decoding for goodput-optimized large language model serving,” in Proc. OSDI, 2024. 4. J. Stojkovic, C. Zhang, İ. Goiri, J. Torrellas, and E. Choukse, “DynamoLLM: Designing LLM inference clusters for performance and energy efficiency,” in Proc. HPCA, IEEE, 2025. 5. Y. Mei, Y. Zhuang, X. Miao, J. Yang, Z. Jia, and R. Vinayak, “Helix: Serving large language models over heterogeneous GPUs and network via max-flow,” in Proc. ASPLOS, 2025. 6. Y. Jiang, F. Fu, X. Yao, G. He, X. Miao, A. Klimovic, B. Cui, B. Yuan, and E. Yoneki, “Demystifying cost-efficiency in LLM serving over heterogeneous GPUs,” in Proc. ICML, 2025. 7. T. A. Feo and M. G. C. Resende, “Greedy randomized adaptive search procedures,” J. Global Optim., vol. 6, pp. 109–133, 1995. 8. Gurobi Optimization, LLC, “Gurobi optimizer reference manual,” 2024. [Online]. Available: https://www.gurobi.com 9. Y. Zhao, J. Chen, P. Sun, L. Li, X. Liu, and X. Jin, “SeaLLM: Resource sharing for multi-LLM services,” in Proc. NSDI, 2025. 10. G. Wilkins, S. Keshav, and R. Mortier, “Offline energy-optimal LLM serving,” arXiv preprint arXiv:2407.04014, 2024. 11. T. Xia, Z. Mao, J. Kerney, E.J. Jackson, Z. Li, J. Xing, S. Shenker, and I. Stoica, “SkyLB: Locality-aware cross-region load balancing for LLM serving,” in Proc. SIGCOMM, 2025. 12. K. Kim, et al., “Cost-efficient LLM serving with heterogeneous VMs and KV cache offloading,” in Proc. EuroSys, 2025. 13. Microsoft Research, “Azure LLM inference trace,” 2025. [Online]. Available: https: //github.com/Azure/AzurePublicDataset 14. A. Dubey, A. Jauhri, A. Pandey, et al., “The Llama 3 herd of models,” arXiv preprint arXiv:2407.21783, 2024. 15. R. Pope, S. Douglas, A. Chowdhery, J. Devlin, J. Bradbury, J. Heek, K. Xiao, S. Agrawal, and J. Dean, “Efficiently scaling transformer inference,” in Proc. MLSys, vol. 5, 2023. 16. E. Frantar, S. Ashkboos, T. Hoefler, and D. Alistarh, “GPTQ: Accurate posttraining quantization for generative pre-trained transformers,” in Proc. ICLR, 2023. 17. P. Patel, et al., “Splitwise: Efficient generative LLM inference using phase splitting,” in Proc. ISCA, 2024. 18. D. Narayanan, et al., “Efficient large-scale language model training on GPU clusters using Megatron-LM,” in Proc. SC, 2021.