Source-linked AI summary
Queuing for Inference: Dynamic Memory Footprints and Costly Preemption
Jiahui Ni, Vishrant Tripathi
TL;DR
Inference requests can grow their memory footprints during service, and finite memory can slow execution while making preemption costly. This paper models those effects and analyzes scheduling policies, including MLPT. It shows that Gittins-index scheduling can incur substantial preemption overhead and gives guidance for choosing MLPT’s quantum.
Problem
Inference memory footprints grow during service, and finite capacity can slow long requests while memory-dependent state restoration makes preemption costly.
Source: §1 · pp. 1–2Method
The paper models finite memory, service degradation, and nonzero preemption overhead, then analyzes MLPT scheduling and its quantum threshold.
Source: §2 · p. 4, §6 · p. 20Results
The classical Gittins-index policy can incur substantial preemption overhead in this model, while MLPT limits preemption and retains priority for jobs with small attained service.
Source: §6 · p. 20Takeaways & Limitations
Larger overhead costs or service-time variability favor a larger quantum, while less spare capacity makes additional overhead more costly.
Source: §4.3 · p. 17The model assumes only one job runs inference at a time; extending it to shared-memory multiple servers and batching remains future work.
Source: §6 · p. 20
Abstract
from arXiv · showhide
Modeling inference workloads for transformer-based neural networks poses unique challenges due to their dynamic memory footprints, head-of-line blocking caused by heavy-tailed request distributions, and memory-dependent preemption overhead arising from the need to load/unload cache state. In this paper, we introduce a new queuing model that captures the impacts of these features on system stability and scheduling design. We show that the Gittins-index policy, which minimizes mean response time in the standard M/G/1 setting, can incur substantial preemption overhead in our model. Motivated by this limitation, we propose the Multi-Level-Priority-Threshold (MLPT) policy, that limits preemption while preserving priority for short jobs. We characterize the mean response time under MLPT and provide empirical rules-of-thumb to solve the resulting threshold-optimization problem. Our key observation is that optimal scheduling is a balance between reducing the response times of shorter jobs and limiting the overhead incurred when preemption occurs. These results provide a theoretical framework for understanding scheduling in memory constrained queuing systems for inference tasks.
1 Introduction
Inference queues couple growing request memory footprints to service rates and preemption costs, unlike classical queueing models. The paper develops a queueing framework and scheduling analysis for these interactions.
1 Introduction
- Growing KV caches can exhaust finite GPU memory, slowing a request’s remaining service and disproportionately affecting long requests.The slowdown depends on intrinsic job size and memory growth during execution.Source: §1 · pp. 1–2
- Preemption can reduce head-of-line blocking, but restoring accumulated KV-cache state adds overhead that grows with attained service.The scheduling tradeoff is between response-time gains and capacity consumed by state movement or recomputation.Source: §1 · p. 2
- Unlike a finite-buffer constraint, memory pressure can change a job’s service rate and the work required to resume it, not merely limit stored work.Source: §1 · p. 2
1.1 Contributions
- The paper models growing memory, finite capacity, service degradation, and memory-dependent preemption costs, then studies stability and scheduling tradeoffs.Source: §1.1 · pp. 2–3
- The authors show that Gittins-index scheduling can incur substantial preemption overhead and propose MLPT to limit preemption while prioritizing jobs with small attained service.They derive MLPT mean response time and characterize its threshold-optimization problem.Source: §1.1 · p. 3
1.2 Related Work
- Prior serving systems address batching, memory management, and preemption, while existing analyses do not capture the full coupling of growing memory, service degradation, and memory-dependent preemption cost.The paper identifies the absence of an explicit steady-state mean-response-time characterization for preemptive scheduling with memory-dependent overhead.Source: §1.2 · pp. 3–4
2 System Model
The model extends a classical single-server queue to represent growing memory footprints, finite capacity, memory-related service slowdown, and costly preemption. Its assumptions connect these effects to inference while keeping the queueing analysis tractable.
2 System Model
- The M/Gg/1C β model represents a single-server queue with finite memory, attained-service-dependent memory growth, slower service beyond capacity, and switching costs proportional to occupied memory.The analysis assumes Poisson arrivals and job sizes unknown individually at arrival, although their distribution is known.Source: §2 · p. 4
2.1 Dynamic Memory Footprint
- A job’s memory requirement is a known nondecreasing function g(a) of attained service, representing the growing state retained during execution.For full-attention transformers, KV-cache size grows approximately linearly with generated sequence length.Source: §2.1 · pp. 4–5
2.2 Memory Constraint and Slowdowns
- Service runs at normalized rate 1 until memory capacity C is reached, then at rate β; under linear growth, the slowdown threshold is ℓ_C = C/α.The resulting service time differs from intrinsic job size because remaining work is processed at the reduced rate; β aggregates effects such as swapping or recomputation.Source: §2.2 · p. 5
2.3 Preemption and Switching Cost
- Preemption adds restoration work proportional to the job’s accumulated memory state, with γ denoting restoration cost per unit of state.Only the running job’s memory is retained; this separates a job’s own memory-dependent slowdown from its preemption overhead.Source: §2.3 · pp. 5–6
- The model’s parameters g(·), C, β, and γ represent memory growth, fast-memory capacity, service-rate degradation, and restoration overhead, respectively.Source: §2.3 · p. 6
3 The Stability Region of a Memory-Constrained Queue
For non-preemptive, size-unaware policies, the section characterizes how memory-induced slowdown affects stability. The stable arrival-rate region depends on job-size tails as well as mean size, and grows with more memory or a smaller slowdown penalty.
3 The Stability Region of a Memory-Constrained Queue
- The memory constraint adds load equal to the expected work served after a job’s memory requirement reaches capacity.This excess work proceeds at the reduced service rate β.Source: §3 · p. 7
- Increasing memory capacity delays slowdown, while increasing β reduces its penalty; both enlarge the stability region.Source: §3 · p. 7
- For the parameters considered, memory constraints substantially reduce the maximum stable arrival rate, and stability depends on job-size tails as well as mean size.Figure 2 compares exponential and log-normal job-size distributions with the same mean.Source: §3 · p. 7
- Log-normal job sizes incur larger memory-induced load and therefore a smaller stability region.Source: §3 · p. 7
- Any policy that preempts with positive probability has a smaller stability region than its non-preemptive counterpart because preemption adds overhead.At light or moderate loads, reduced head-of-line blocking can nevertheless lower mean response time.Source: §3 · p. 7
4 Scheduling Design
The section examines scheduling under costly preemption, characterizing MLPT stability and mean response time and explaining how age-based priority thresholds shape scheduling. It discusses selecting the MLPT quantum to balance delayed priority changes against preemption overhead, including an empirical moment-based rule of thumb and the effects of memory thresholds and additional priority levels.
4.1 Motivation from Age-Based Scheduling
- Under strictly decreasing hazard rates, Gittins can cause infinitely many preemptions and unbounded overhead, making jobs’ response times infinite and the system unstable when the tie state is reachable.Tied jobs’ indices decrease with attained service, so any positive service quantum breaks priority ordering; with positive preemption cost, infinitely many switches prevent further useful service.Source: §4.1 · pp. 8–9
4.2 Mean Response Time of the MLPT-(𝜃,𝑘) Policy
- MLPT uses k strict-priority levels with FCFS within each level, demoting unfinished jobs after θ service quanta so a job is preempted at most k−1 times when k is finite.Jobs enter the highest-priority level, and jobs in the last level run to completion.Source: §4.2 · p. 9
- The section gives a stability condition and derives MLPT mean response time by completion level, accounting for effective service, preemption overhead, and waiting from existing and arriving jobs.The mean response time can be optimized over a common quantum θ in a one-dimensional problem for fixed k, or over distinct level quanta in a multidimensional problem.Source: §4.2 · pp. 11, 13
- Optimizing θ lets MLPT’s stability region approach that of non-preemptive policies, and its optimized mean response time is no greater than FCFS for any base load ρ0.The argument uses θ=0 or θ=∞, which reduce MLPT to FCFS, as stable choices when positive preemption overhead would destabilize other policies.Source: §4.2 · p. 14
4.3 Finding the optimal 𝜃for MLPT-(𝜃,𝑘)
- For k=2, threshold selection generally requires numerical optimization; local minima can occur where A(x)/B(x) crosses the intrinsic-size hazard rate from below to above or at a jump at the memory threshold.With the illustrated small threshold ℓ_C=3E[L], the jump yields a candidate minimum; with ℓ_C=8E[L], a below-to-above crossing occurs below ℓ_C instead.Source: §4.3 · pp. 14–15, Figure 3 · p. 15
- For two priority levels, ℓ_C can be an effective quantum when it is neither very small nor too large, because earlier or later preemption can respectively add unnecessary preemptions or delay waiting small jobs.When ℓ_C is very small, setting θ = ℓ_C can make many jobs incur preemption overhead; increasing θ reduces that fraction but delays priority changes and can raise overhead per preempted job.Source: §4.3 · pp. 15–17
- Allowing k > 2 postpones entry into the terminal nonpreemptible level until age (k−1)θ, reducing long-job blocking but increasing overhead and effective load, especially for long jobs.The added flexibility requires careful quantum selection to avoid excessive preemption.Source: §4.3 · p. 16
- The rule’s square-root scale balances cumulative overhead, which decreases inversely with the quantum, against an approximately linear penalty for delaying priority changes.A larger preemption cost factor γ favors a larger quantum; the rule also reflects memory slowdown and scheduler granularity through E[S], E[S²], and ρ₀.Source: §4.3 · p. 17
- The proposed moment-based rule of thumb uses service-time moments and base load to choose the quantum, with larger overhead costs or variability favoring a larger quantum and less spare capacity making overhead costlier.Its additive E[S] term and multiplicative factor 2 are based mainly on numerical observations.Source: §4.3 · p. 17
- For the Section 5 simulation setup, a = 3 and b = 7 reasonably approximate the normalized memory-threshold range where θ = ℓ_C is effective for k = 2, though these constants may vary with workload and system parameters.Across varying system parameters and arrival rates, the proposed rule follows the trends in the optimal quantum θ*, supporting it as a reasonable placeholder.Source: §4.3 · p. 17
5 Numerical Simulations
The simulations compare MLPT settings across quantum sizes, priority levels, and memory thresholds, measuring mean response time against FCFS and other policies. The gains depend on memory capacity and the number of priority levels.
5 Numerical Simulations
- Simulations measure 100,000 jobs after 20,000 warm-up arrivals and average results across eight seeds using matched traces.Unless otherwise stated, job sizes are log-normal, with β=0.39 and γ=0.1.Source: §5 · p. 17
- 32.2% (MLPT-(θ*, ∞)) and 21.7% (MLPT-(θ*, 2)) lower mean response time than FCFS at ℓC=6E[L].The proposed rule-of-thumb quantum gives MLPT-(bθ, ∞) a 31.9% reduction, 0.3 percentage points below the optimized gain.Source: §5 · pp. 17–18, Figure 6 · p. 18
- 50.3% (MLPT-(θ*, ∞)) and 46.6% (MLPT-(θ*, 2)) lower mean response time than FCFS at ℓC=3E[L].At ℓC=8E[L], the reductions are 24.6% for MLPT-(θ*, ∞) and 14.9% for MLPT-(θ*, 2).Source: §5 · p. 18, Figure 7 · p. 18, Figure 8 · p. 19
- Increasing priority levels brings more performance gain with large memory, while under small memory a single preemption already improves substantially over FCFS.As k increases in the stable range of θ, MLPT-(θ,k) mean response time converges to that of MLPT-(θ,∞).Source: §5 · p. 19
- Under heavy load, MLPT-(θ,k) closely approximates the mean response time of its arrival-dependent-preemption counterpart.The comparison removes an analysis assumption by charging preemption overhead only when higher-priority jobs are present.Source: §5 · p. 19
6 Conclusion
The conclusion presents a memory-constrained inference queueing model and MLPT scheduling analysis, including an empirical rule for choosing the quantum. The model assumes one inference job runs at a time, and the authors identify relaxing that assumption as future work.
6 Conclusion
- The paper models dynamically growing memory footprints, finite capacity, memory-dependent service degradation, and nonzero preemption overhead.It characterizes stability implications and scheduling tradeoffs, and reports that Gittins-index scheduling can incur substantial preemption overhead.Source: §6 · p. 20
- The authors derive MLPT mean response time and propose an empirical rule of thumb for setting its quantum.Source: §6 · p. 20
- The analysis assumes only one job runs inference at a time; future work would model multiple jobs sharing memory and interactions among batching, scheduling, and memory contention.The authors also plan to study retaining preempted-job state in local memory and integrating MLPT-style scheduling into serving systems.Source: §6 · p. 20
where
The passage lists quantities used in the surrounding analysis, including Q(x), service components S1 and S2, and load terms.
where
- Q(x) is given as d1(x) + q(x) − (1 − γ)E[S2].Source: where · p. 22
- S1 is defined as min(S, q(x)), while S2 is defined for S > q(x) as S − (1 − γ)q(x).Source: where · p. 22
- The passage defines ρ1(x) as λE[S1] and ρ(x) as λE[S] + λγq(x)F̄L(x).Source: where · p. 22
B Optimal quantum 𝜃with varying system parameters
The optimal MLPT quantum varies with memory capacity, slowdown, preemption cost, and the number of priority levels. The observed trends reflect a balance between limiting preemption overhead and preserving priority separation.
B Optimal quantum θ with varying system parameters
- When ℓC is very small, both policies require a large optimal quantum; below 3.5E[L], the infinite-level policy selects a larger quantum than the two-level policy.As memory increases, the ordering reverses: extra priority levels let moderately sized jobs retain priority, allowing the infinite-level policy to use a smaller quantum.Source: B Optimal quantum 𝜃with varying… · p. 22, Figure 10 · p. 23
- For ℓC=3E[L], the two-level optimum remains at ℓC across the tested γ range and most of the tested β range.The infinite-level optimum decreases with β and increases with γ, with a plateau at ℓC over part of each sweep.Source: B Optimal quantum 𝜃with varying… · p. 22
- For ℓC=8E[L], both policies choose smaller quanta as β increases and larger quanta as γ increases, with the infinite-level optimum consistently below the two-level optimum.Increasing γ makes preemptions more expensive and favors a larger quantum.Source: B Optimal quantum 𝜃with varying… · p. 23
- The rule-of-thumb quantum closely follows the optimal quantum's trends as system parameters vary.The memory boundary can anchor the optimal quantum under limited memory; with more memory, priority separation and preemption overhead become more prominent.Source: B Optimal quantum 𝜃with varying… · p. 23