AugServe: Adaptive Request Scheduling for Augmented Large Language Model Inference Serving

# Adaptive Request Scheduling for Augmented Large Language Model Inference Serving
Source: [https://arxiv.org/html/2512.04013](https://arxiv.org/html/2512.04013)
Zhen JinZhenqian ChenJiexiong XuWenhai LinYiquan ChenWenzhi Chen

###### Abstract

Augmented large language models \(LLMs\) that invoke external calls are increasingly prevalent in inference serving\. However, such augmentations pose significant challenges to inference efficiency under strict Service\-Level Objectives \(SLOs\)\. Existing inference systems are agnostic to the dynamic execution behaviors induced by external calls and rely on fixed batch\-level token budget, which leads to severe Head\-of\-Line \(HoL\) blocking and substantially reduced effective throughput\. We presentAugServe, an efficient augmented LLM inference serving framework that mitigates request queuing latency and improves effective throughput under external\-call\-augmented workloads\.AugServeintegrates state\-aware request scheduling with dynamic batch\-level token budgets to adapt to heterogeneous requests and their dynamically changing execution states\. Experimental results show thatAugServeachieves 6\.5×\\timesand 4\.7×\\timeshigher effective throughput than vLLM and INFERCEPT, respectively\.

Machine Learning, ICML

## 1Introduction

Augmented Large Language Models \(LLMs\) have rapidly emerged as a promising paradigm\(Abhyankaret al\.,[2024](https://arxiv.org/html/2512.04013#bib.bib22); Haoet al\.,[2023](https://arxiv.org/html/2512.04013#bib.bib7)\)for modern LLM inference serving\. Compared with traditional text\-only LLMs, which rely on fixed pretrained parameters and lack real\-time knowledge\(Schicket al\.,[2023](https://arxiv.org/html/2512.04013#bib.bib5); Gadeet al\.,[2025](https://arxiv.org/html/2512.04013#bib.bib18)\), augmented LLMs extend their capabilities by invoking external tools \(e\.g\., web APIs, databases, or specialized models\) during inference\(Chenet al\.,[2024b](https://arxiv.org/html/2512.04013#bib.bib3); Go and Park,[2025](https://arxiv.org/html/2512.04013#bib.bib8); Qinet al\.,[2024a](https://arxiv.org/html/2512.04013#bib.bib10); Luet al\.,[2024](https://arxiv.org/html/2512.04013#bib.bib4)\)\. This approach enables augmented LLMs to perform more complex tasks such as arithmetic computation\(Chenet al\.,[2024a](https://arxiv.org/html/2512.04013#bib.bib16); Yao and Yadav,[2025](https://arxiv.org/html/2512.04013#bib.bib15)\), real\-time information retrieval\(Suet al\.,[2024](https://arxiv.org/html/2512.04013#bib.bib17); Gadeet al\.,[2025](https://arxiv.org/html/2512.04013#bib.bib18)\), and web interactions\(Qiet al\.,[2025](https://arxiv.org/html/2512.04013#bib.bib13); Zhanget al\.,[2025](https://arxiv.org/html/2512.04013#bib.bib14)\)\.

![Refer to caption](https://arxiv.org/html/2512.04013v3/x1.png)Figure 1:Augmented LLM inference process\.Augmented LLM inference service systems are becoming the key infrastructure for AI\-centric cloud computing, with inference efficiency directly impacting user experience\.[Figure 1](https://arxiv.org/html/2512.04013#S1.F1)illustrates the workflow of the augmented LLM inference service\(Abhyankaret al\.,[2024](https://arxiv.org/html/2512.04013#bib.bib22); Gimet al\.,[2024](https://arxiv.org/html/2512.04013#bib.bib23)\):\(i\)During inference, the augmented LLM identifies the need for real\-time information and triggers the corresponding tool calls\.\(ii\)The inference process is paused while awaiting the response from the external augmentation module\.\(iii\)Upon the response being returned, the serving system appends it to the sequence generated and resumes normal generation\.

Ideally, inference systems must simultaneously deliver high throughput and low latency\. In this context,Service\-Level Objectives \(SLOs\)serve as strict latency boundaries \(e\.g\., requiring Time\-to\-First\-Token \(TTFT\) below a fixed threshold\)\(Gaoet al\.,[2025](https://arxiv.org/html/2512.04013#bib.bib20); Zhonget al\.,[2024](https://arxiv.org/html/2512.04013#bib.bib29); Wuet al\.,[2023](https://arxiv.org/html/2512.04013#bib.bib19); Patelet al\.,[2025](https://arxiv.org/html/2512.04013#bib.bib42)\)\. Accordingly, the system’s efficiency is best characterized byeffective throughput\(orgoodput\), defined as the volume of requests processed per unit time that successfully satisfy these SLO requirements\(Wanget al\.,[2025](https://arxiv.org/html/2512.04013#bib.bib38); Karthiket al\.,[2024](https://arxiv.org/html/2512.04013#bib.bib39); Zhanget al\.,[2023](https://arxiv.org/html/2512.04013#bib.bib40)\)\.

State\-of\-the\-art inference systems focus on improving inference performance\. vLLM\(Kwonet al\.,[2023](https://arxiv.org/html/2512.04013#bib.bib21)\)has emerged as the de facto standard for efficient LLM serving\. However, in augmented LLM inference, vLLM treats external calls as request termination and discards the request’s context \(i\.e\., Key\-Value \(KV\) cache\)\(Abhyankaret al\.,[2024](https://arxiv.org/html/2512.04013#bib.bib22)\)\. When the call returns, the system must recompute the KV cache, incurring substantial computation overhead and processing latency\. To address this issue, INFERCEPT\(Abhyankaret al\.,[2024](https://arxiv.org/html/2512.04013#bib.bib22)\)dynamically manages context based on call duration and context length, selecting among three KV\-cache handling policies: discarding it, preserving it in GPU memory, or swapping it to the host memory\. This design reduces resource waste and significantly improves the efficiency of augmented LLM inference\.

However, these systems still face two challenges in improving the goodput of augmented LLM inference:

C1: Inadequate scheduling leads to Head\-of\-Line \(HoL\) blocking and SLO violations\.In augmented LLM inference, existing systems \(e\.g\., vLLM and INFERCEPT\) typically adopt First\-Come\-First\-Served \(FCFS\) scheduling, batching requests without accounting for external calls\. When long requests trigger external calls and pause execution, their context \(KV cache\) may be preserved in GPU memory, swapped out to host memory, or discarded, all of which can block subsequent short requests\. This results in severe HoL blocking, causing queuing delays that exceed SLOs and sharply degrade goodput\. Some work attempts to mitigate these delays using approximate Shortest\-Job\-First \(SJF\) scheduling based on request length\(Jinet al\.,[2023](https://arxiv.org/html/2512.04013#bib.bib37); Fuet al\.,[2024](https://arxiv.org/html/2512.04013#bib.bib43); Wuet al\.,[2023](https://arxiv.org/html/2512.04013#bib.bib19)\)\. However, they still ignore the execution heterogeneity introduced by external calls and remain suboptimal for augmented LLM inference\.

C2: Fixed batch\-level token budget restricts throughput under external calls\.In augmented LLM inference, external calls introduce paused requests whose contexts may occupy GPU memory, complicating batch capacity selection\. A static batch\-level token budget cannot adapt to this dynamic memory availability\. A small budget limits per\-iteration concurrency and reduces throughput, while an overly large budget induces resource contention and frequent eviction of paused contexts, incurring recomputation overhead\. Moreover, existing approaches\(Zhenget al\.,[2025](https://arxiv.org/html/2512.04013#bib.bib49)\)adjust the budget based only on free GPU memory, ignoring reclaimable memory under different context\-handling policies, leading to suboptimal budget decisions\.

In this paper, we proposeAugServe, an augmented LLM inference serving framework that jointly rethinks request ordering and batch capacity\. Our key insight is that augmented LLM inference introduces significant execution heterogeneity, where requests with different external calls and context\-handling policies exhibit distinct resource demands across multiple stages\. Guided by this insight,AugServeadopts a unified, state\-aware design that optimizes request scheduling and batch\-level capacity adaptation to maximize goodput under dynamic augmented LLM workloads\.

Forstate\-aware scheduling \(C1\),AugServemodels request scheduling across the full inference lifecycle, explicitly capturing multi\-stage execution and cross\-round state evolution induced by external calls\. Scheduling priorities are constructed in a state\-aware manner that adapts to each request’s execution state, context\-handling outcome, and observed runtime feedback\. By prioritizing requests with higher execution efficiency given their current execution stages and resource footprint,AugServealleviates HoL blocking in augmented LLM inference, significantly reducing queuing delays and improving goodput\.

Fordynamic batch\-level token budget \(C2\),AugServeadapts batch capacity based on available GPU memory and reclaimable memory from paused requests under different context\-handling policies\. Besides,AugServeenforces bounded budget adjustments to ensure robustness\.

We implementedAugServewith vLLM and evaluated it against both vLLM and INFERCEPT across multiple LLMs and GPU platforms\. Experimental results show thatAugServeconsistently outperforms both baselines in latency and effective throughput\. In particular,AugServeachieves a geometric mean of 6\.5×\\timesand 4\.7×\\timeshigher effective throughput than vLLM and INFERCEPT, respectively, while reducing TTFT 95\.6% and 96\.0% on average\.

In summary, our contributions are as follows:

- •We presentAugServe, an augmented LLM inference serving framework that efficiently improves effective throughput \(§[5](https://arxiv.org/html/2512.04013#S5)\)\.
- •We propose an adaptively state\-aware request scheduling strategy that optimizes request ordering based on request characteristics, external\-call\-induced execution states, and runtime feedback\. \(§[5\.2](https://arxiv.org/html/2512.04013#S5.SS2), §[5\.3](https://arxiv.org/html/2512.04013#S5.SS3)\)
- •We develop a dynamic batch\-level token budget mechanism adapting to free and reclaimable memory\. \(§[5\.4](https://arxiv.org/html/2512.04013#S5.SS4)\)
- •We conduct extensive evaluations to validate the effectiveness ofAugServe\(§[6](https://arxiv.org/html/2512.04013#S6)\)\.

## 2Background

We review augmented LLMs and existing inference systems\.

### 2\.1Augmented Large Language Models

Augmented LLMs integrate external tools \(e\.g\., remote APIs, databases, external models\) during inference\(Chenet al\.,[2024b](https://arxiv.org/html/2512.04013#bib.bib3); Schicket al\.,[2023](https://arxiv.org/html/2512.04013#bib.bib5); Luet al\.,[2024](https://arxiv.org/html/2512.04013#bib.bib4); Go and Park,[2025](https://arxiv.org/html/2512.04013#bib.bib8)\), demonstrating superior performance in complex tasks such as arithmetic computation\(Haoet al\.,[2023](https://arxiv.org/html/2512.04013#bib.bib7); Chenet al\.,[2024a](https://arxiv.org/html/2512.04013#bib.bib16); Yao and Yadav,[2025](https://arxiv.org/html/2512.04013#bib.bib15)\)and real\-time information retrieval\(Suet al\.,[2024](https://arxiv.org/html/2512.04013#bib.bib17); Gadeet al\.,[2025](https://arxiv.org/html/2512.04013#bib.bib18)\)\. Furthermore, with the rise of tool\-using agents\(Patilet al\.,[2025](https://arxiv.org/html/2512.04013#bib.bib47); Wölfleinet al\.,[2025](https://arxiv.org/html/2512.04013#bib.bib48)\)and the standardized tool interactions via the Model Context Protocol \(MCP\)\(Anthropic,[2024](https://arxiv.org/html/2512.04013#bib.bib26)\), tool invocation has become a ubiquitous component of inference pipelines\(Feiet al\.,[2025](https://arxiv.org/html/2512.04013#bib.bib1); Mialonet al\.,[2023](https://arxiv.org/html/2512.04013#bib.bib9)\)\. Consequently, augmented LLM inference systems are emerging as the core infrastructure for next\-generation cloud platforms\.

### 2\.2Existing LLM Inference Systems

LLM inference has become a dominant workload in modern data centers, motivating the design of advanced systems to improve overall efficiency\. To handle varying request sequence lengths, Orca\(Yuet al\.,[2022](https://arxiv.org/html/2512.04013#bib.bib27)\)introduces iteration\-level scheduling, which has become the de facto standard in state\-of\-the\-art inference engines\. Meanwhile, to improve GPU memory utilization, vLLM\(Kwonet al\.,[2023](https://arxiv.org/html/2512.04013#bib.bib21)\)proposes PagedAttention to eliminate memory fragmentation\. Additionally, some research explores offloading KV cache to CPU or SSD\(Jeong and Ahn,[2025](https://arxiv.org/html/2512.04013#bib.bib30); Huet al\.,[2025b](https://arxiv.org/html/2512.04013#bib.bib32); Shenget al\.,[2023](https://arxiv.org/html/2512.04013#bib.bib33)\)to alleviate GPU memory bottlenecks\.

However, in augmented LLM inference, most prior works simply discard the context \(KV cache\) during external calls\. INFERCEPT\(Abhyankaret al\.,[2024](https://arxiv.org/html/2512.04013#bib.bib22)\)improves over these approaches by dynamically selecting amongPreserve,Discard, orSwapcontext\-handling policies based on the external call duration and context length:

- •Preserve: The KV cache remains in GPU memory, and decoding resumes once the response returns\.
- •Discard: The KV cache is discarded, and recomputation is required after the response returns\.
- •Swap: The KV cache is swapped to CPU memory and restored to GPU memory once the response returns\.

This adaptive design avoids inefficient reliance on a single policy, reducing memory waste and inference latency\.

## 3Motivation

Maximizing goodput under SLOs is challenging in augmented LLM inference, where requests are heterogeneous and involve multi\-round external calls\. This section analyzes the key limitations of existing approaches\.

### 3\.1Limitations of Existing Scheduling Strategies

Challenge 1: Existing inference scheduling strategies struggle in dynamic augmented LLM serving\.Current inference systems typically adopt FCFS scheduling and batch requests by arrival order, without considering external calls\. In augmented LLM inference, pausing requests for external calls \(whether context is preserved, swapped, or discarded\) blocks subsequent short queries\. This induces severe HoL blocking, increasing latency and degrading goodput\. To alleviate HoL blocking, prior work explores approximate SJF scheduling based on request length\(Jinet al\.,[2023](https://arxiv.org/html/2512.04013#bib.bib37); Fuet al\.,[2024](https://arxiv.org/html/2512.04013#bib.bib43); Wuet al\.,[2023](https://arxiv.org/html/2512.04013#bib.bib19)\)\. While these approaches outperform FCFS \([Figure 2](https://arxiv.org/html/2512.04013#S3.F2)\), they do not account for external calls and still fail to meet SLOs in augmented LLM inference, with TTFT often exceeding the SLO \(e\.g\., 1s\), high tail latency, and degraded goodput at high load\. Recent systems\(Shahoutet al\.,[2025b](https://arxiv.org/html/2512.04013#bib.bib46)\)propose memory\-based SJF heuristics that approximate job sizes using memory cost\. However, these approaches make one\-shot scheduling decisions at each execution round, treating requests as newly arriving jobs after external calls\. Consequently, they do not model dynamic and cross\-round execution stages in augmented LLM workloads \([Figure 5](https://arxiv.org/html/2512.04013#S4.F5)\), ignoring resumption costs from cumulative context and external call return lengths\.

Furthermore, we observe that both the cumulative context lengths at the time of external calls and the external call return lengths are highly variable \([Figure 4](https://arxiv.org/html/2512.04013#S3.F4)\)\. Such variability results in dynamic resumption costs after external calls under different context\-handling policies, which have distinct memory footprints and recomputation overheads\. Moreover, the varying external call return lengths significantly affect both TTFT and goodput \([Figure 4](https://arxiv.org/html/2512.04013#S3.F4)\)\. Together, these factors make existing scheduling policies suboptimal for augmented LLM inference\.

![Refer to caption](https://arxiv.org/html/2512.04013v3/x2.png)Figure 2:SJF outperforms FCFS in goodput \(effective throughput\) and TTFT, but remains suboptimal under high load\.Opportunity 1:Augmented LLM inference calls for scheduling mechanisms that explicitly account for heterogeneous execution states induced by external calls and dynamic resumption overhead\.

![Refer to caption](https://arxiv.org/html/2512.04013v3/x3.png)Figure 3:Context/External\_call\_return length
distribution in INFERCEPT and ToolBench datasets\.
![Refer to caption](https://arxiv.org/html/2512.04013v3/x4.png)Figure 4:TTFT and goodput with varying external call return lengths, including fixed lengths and a mix of 32\- and 256\- tokens\.

### 3\.2Fixed Batch\-Level Token Budget

Challenge 2: Fixed batch\-level token budget restricts throughput under external calls\.The batch\-level token budget determines the maximum number of tokens processed in a single forward iteration\. In augmented LLM inference, external calls introduce paused requests whose contexts may occupy GPU memory, fundamentally complicating budget selection\. While a small budget leads to low per\-iteration concurrency and reduced goodput, an overly large budget can trigger resource contention and unnecessary eviction of paused request contexts, incurring redundant recomputation overhead\. Recent systems\(Zhenget al\.,[2025](https://arxiv.org/html/2512.04013#bib.bib49)\)adjust the budget based on free GPU memory, but do not model reclaimable memory from paused requests underSwaporDiscardcontext\-handling policies, failing to capture the true memory availability under external\-call\-augmented workloads and constraining goodput\.

We evaluate statically configured batch\-level token budgets across different hardware, models, and workloads, and observe that both overly small and excessively large budgets degrade goodput \([Table 1](https://arxiv.org/html/2512.04013#S3.T1)\)\. Moreover, the optimal budget varies across hardware and workload conditions\.

Opportunity 2:Dynamically adapting the batch\-level token budget based on both free and reclaimable GPU memory from paused requests is crucial for maximizing goodput in augmented LLM inference\.

Table 1:Goodput \(req/s\) with different batch\-level token budgets, optimal token budget varies across hardware and workloads\.Max batch tokens1005001000150020002req/s, GPT\-J\-6B, RTX40900\.290\.410\.250\.110\.104req/s, OPT\-13B, H8000\.010\.160\.180\.220\.19

## 4Problem Formulation

To systematize request scheduling in augmented LLM inference, this section formalizes the request lifecycle and establishes the associated scheduling objectives\.

Request Lifecycle Modeling\.As shown in[Figure 5](https://arxiv.org/html/2512.04013#S4.F5), in augmented LLM inference, a request spans multiple execution stages \(e\.g\., prefill and decode\) interleaved with external call waiting stages\. The response length returned by external calls determines the input size and KV cache state for the subsequent execution phase\. Accordingly, we model each requestRiR\_\{i\}as a sequence ofnnservice segments, i\.e\.,Ri=\{Si,1,…,Si,n\}R\_\{i\}=\\\{S\_\{i,1\},\\dots,S\_\{i,n\}\\\}, each ending with an external call\. Formally, thekk\-th segmentSi,kS\_\{i,k\}is defined as:

Si,k=\{⟨Pi,1,Di,1,Wi,1⟩,k=1,⟨Ri,kr​e​s​\(pi\),Pi,kr​e​t,Di,k,Wi,k⟩,2≤k≤n\.S\_\{i,k\}=\\begin\{cases\}\\langle P\_\{i,1\},D\_\{i,1\},W\_\{i,1\}\\rangle,&k=1,\\\\ \\langle R\_\{i,k\}^\{\{res\}\}\(p\_\{i\}\),P\_\{i,k\}^\{\{ret\}\},D\_\{i,k\},W\_\{i,k\}\\rangle,&2\\leq k\\leq n\.\\end\{cases\}\(1\)
![Refer to caption](https://arxiv.org/html/2512.04013v3/x5.png)Figure 5:Augmented LLM inference request lifecycle modeling\.![Refer to caption](https://arxiv.org/html/2512.04013v3/x6.png)Figure 6:System architecture ofAugServewith state\-aware scheduling and dynamic batch\-level token budget\.The initial segmentSi,1S\_\{i,1\}comprises standard prompt prefill stagePi,1P\_\{i,1\}, decoding stageDi,1D\_\{i,1\}, and a tool\-wait stageWi,1W\_\{i,1\}\. Subsequent segments \(k≥2k\\geq 2\) introduce a context resumption stageRi,kr​e​sR\_\{i,k\}^\{\{res\}\}, wherer​e​s\{res\}denotes resuming a paused request under a context\-handling policypi∈Π=\{Preserve, Swap, Discard\}p\_\{i\}\\in\\Pi=\\\{\\texttt\{Preserve, Swap, Discard\}\\\}\. This is followed by an incremental prefill stagePi,kr​e​tP\_\{i,k\}^\{\{ret\}\}, wherer​e​t\{ret\}denotes incorporating tool return tokens into the KV cache\. This segmentation treats each segment as a composite unit with distinct, state\-dependent resource requirements, providing the necessary granularity for state\-aware scheduling\.

Scheduling Objective\.Our goal is to maximize goodput in augmented LLM inference, accounting for both request service rates and queuing delays\. Accordingly, we jointly consider how many requests can be served per iteration and how much waiting time can be reduced\. To quantify the per\-iteration benefit of scheduling a request, we define ascheduling valueVieV\_\{i\}^\{e\}capturing both its throughput contribution and waiting\-time reduction:

Vie=1\+β⋅wie,V\_\{i\}^\{e\}=1\+\\beta\\cdot w\_\{i\}^\{e\},\(2\)
where the constant term11represents the fundamental contribution of serving a request to system throughput progress,wiew\_\{i\}^\{e\}denotes the waiting time that would be eliminated if requestiiis scheduled at iterationee\. The hyperparameterβ\\betabalances throughput\-oriented scheduling and delay awareness\. A smallerβ\\betaprioritizes throughput by allowing the throughput term to dominateVieV\_\{i\}^\{e\}, whereas a largerβ\\betashifts the scheduling focus toward reduced waiting time\.

Given the candidate request setUeU^\{e\}, let𝐱e=\{xie∣i∈Ue\}\\mathbf\{x\}^\{e\}=\\\{x\_\{i\}^\{e\}\\mid i\\in U^\{e\}\\\}denote the batch selection decisions at iterationee, wherexie∈\{0,1\}x\_\{i\}^\{e\}\\in\\\{0,1\\\}indicates whether requestiiis selected for execution\. The scheduling objective is to maximize the aggregate scheduling value of the selected batch, subject to the available GPU memory budgetMeM^\{e\}:

Maximize∑i∈Uexie⋅Vie\\displaystyle\\sum\_\{i\\in U^\{e\}\}x\_\{i\}^\{e\}\\cdot\{V\_\{i\}^\{e\}\}\(3\)s\.t\.∑i∈Uexie⋅mi​\(t\)≤Me\.\\displaystyle\\sum\_\{i\\in U^\{e\}\}x\_\{i\}^\{e\}\\cdot m\_\{i\}\(t\)\\leq M^\{e\}\.

## 5Design

This section details the design ofAugServe, a unified inference framework for augmented LLM serving\.

### 5\.1Design Overview

As illustrated in[Figure 6](https://arxiv.org/html/2512.04013#S4.F6),AugServeconsists of three modules: \(1\)Prediction module\(§[5\.2](https://arxiv.org/html/2512.04013#S5.SS2)\) estimatesoutput\_lengthandexternal\_call\_durationto provide priors for scheduling\. \(2\)Scheduler module\(§[5\.3](https://arxiv.org/html/2512.04013#S5.SS3)\) employs a state\-aware scheduling policy that incorporates external call characteristics and runtime feedback to optimize request ordering\. \(3\)Token budget module\(§[5\.4](https://arxiv.org/html/2512.04013#S5.SS4)\) adjusts the batch\-level token budget based on free GPU memory and preemptable paused\-request contexts\. Together, these modules form a unified framework that reduces queuing latency and maximizes goodput for augmented LLM inference\.

The overall workflow proceeds as follows: An incoming request \(1\) is first processed by the prediction module to estimateoutput\_lengthandexternal\_call\_durationas scheduling priors \(2\)\. The scheduler utilizes these to determine the context\-handling policy and assign an initial priority \(3a\)\. Concurrently, the token budget module sets a batch\-level token budget based on available GPU memory and reclaimable memory from preemptable paused requests \(3b\)\. Then the scheduler ranks requests by priorityθi\\theta\_\{i\}and selects requests to form an execution batch under the token constraint \(4\)\. If an external tool is invoked, inference is paused until the call returns \(5\), after which runtime feedback is used to update the request’s scheduling priority \(67\)\. Requests are iteratively scheduled until completion\.

### 5\.2Lightweight Request Prediction

To support scheduling, we fine\-tune a lightweight BERT\-base model \(110M parameters\) to jointly estimateoutput\_lengthandexternal\_call\_duration, which provide coarse\-grained priors about each request’s future execution behavior\.Output\_lengthprediction is formulated as a classification task by discretizing sequences into fixed 50\-token buckets for robustness\(Huet al\.,[2025a](https://arxiv.org/html/2512.04013#bib.bib31); Jinet al\.,[2023](https://arxiv.org/html/2512.04013#bib.bib37)\)\. Using request inputs as features and realized output lengths as labels, the model achieves 85% bucket accuracy on ToolBench and 65% on the INFERCEPT dataset\.External\_call\_durationis predicted via regression using request input metadata as features and actual execution times as labels, with mean squared errors of approximately 5s on ToolBench and 0\.4s on INFERCEPT\. In addition, the predictor is invoked upon request arrival and tool call return, running off the critical execution path, and adds less than 0\.1% overhead to total execution time \(§[6\.2](https://arxiv.org/html/2512.04013#S6.SS2)\)\. Importantly, inaccuracies in early predictions are mitigated by continuously refined scheduling decisions \(§[5\.3](https://arxiv.org/html/2512.04013#S5.SS3)\)\. We empirically validate this robustness to prediction errors in §[6\.3](https://arxiv.org/html/2512.04013#S6.SS3)\.

### 5\.3Adaptive Scheduling with State Awareness

Value\-Density\-Based Scheduling Policy\.The scheduling task defined in[Equation 3](https://arxiv.org/html/2512.04013#S4.E3)is a variant of the NP\-hard 0\-1 knapsack problem, aiming to pack the maximum aggregate value into limited GPU memory\. To address this, we propose a greedy value\-density strategy that ranks requests by their scheduling efficiency, prioritizing those that yieldhigher scheduling value \([Equation 2](https://arxiv.org/html/2512.04013#S4.E2)\) per unit of resource consumption\. We defineCi,kC\_\{i,k\}as the resource consumption of thekk\-th service segment of requestii\. The scheduling priority \(value density\) is then computed as:

θi,k=ViCi,k=1\+β⋅wiCi,k\.\\theta\_\{i,k\}=\\frac\{V\_\{i\}\}\{C\_\{i,k\}\}=\\frac\{1\+\\beta\\cdot w\_\{i\}\}\{C\_\{i,k\}\}\.\(4\)
Here, scheduling valueViV\_\{i\}captures a request’s contribution to throughput progress and waiting\-time reduction, computed by tracking the elapsed waiting timewiw\_\{i\}since its last scheduling\. This density\-based ranking prioritizes requests with higher scheduling efficiency, enabling the scheduler to maximize aggregate throughput while minimizing queuing delays\. The remaining key challenge lies in accurately modeling the state\-dependent resource consumptionCi,kC\_\{i,k\}across heterogeneous execution phases, which we address next\.

State\-Aware Resource Consumption Modeling\.In augmented LLM serving, resource consumption depends not only on request length but also on external call behavior and context\-handling policies\. External calls induce variable pause durations and response sizes, while different context\-handling policies incur distinct memory and recomputation costs\. In addition, execution costs vary across service stages, including prefill, decoding, waiting, and resumption\. These factors make length\-based or instantaneous memory\-based cost models inadequate\. We therefore adopt a space\-time cost model that quantifies resource consumption as the integral of memory occupancy over the segment’s service duration\. Formally, the space\-time cost of service segmentSi,kS\_\{i,k\}under context\-handling policypip\_\{i\}is defined as:

Ci,k​\(pi\)=∫0τi,kmi​\(t,pi\)​𝑑t,C\_\{i,k\}\(p\_\{i\}\)=\\int\_\{0\}^\{\\tau\_\{i,k\}\}m\_\{i\}\(t,p\_\{i\}\)\\,dt,\(5\)
wheremi​\(t,pi\)m\_\{i\}\(t,p\_\{i\}\)denotes the instantaneous memory occupancy of requestiiunder policypip\_\{i\}, andτi,k\\tau\_\{i,k\}is the segment’s residency duration\. This formulation measures how long and how much GPU memory a request occupies over its service duration, providing a unified metric to evaluate resource overhead across heterogeneous execution stages\. To enable effective scheduling, we further constructCi,kC\_\{i,k\}in a state\-aware manner, conditioned on the execution state, context\-handling policy, and realized external call outcomes\. This construction proceeds in two regimes, including Pre\-Invocation estimation and Post\-Invocation refinement\.

\(1\) Pre\-Invocation Estimation:Upon request arrival,AugServeestimates the space\-time costCi,1C\_\{i,1\}to compute the initial scheduling priorityθi,1\\theta\_\{i,1\}before the external call returns\. Specifically, a lightweight prediction module \(§[5\.2](https://arxiv.org/html/2512.04013#S5.SS2)\) provides the predictedexternal\_ call\_durationτ^ic​a​l​l\\hat\{\\tau\}\_\{i\}^\{call\}andoutput\_lengthl^io​u​t\\hat\{l\}\_\{i\}^\{out\}111We use⋅^\\hat\{\\cdot\}to denote predicted values throughout the paper\.\. With these predictions,AugServeselects an initial context\-handling policyp^i,1\\hat\{p\}\_\{i,1\}that minimizes the expected memory wasteWasteipi\\text\{Waste\}\_\{i\}^\{p\_\{i\}\}caused by the external call:

p^i,1=arg⁡minp∈Π⁡Wasteip​\(l^io​u​t,τ^ic​a​l​l\)\.\\hat\{p\}\_\{i,1\}=\\arg\\min\_\{\{p\}\\in\\Pi\}\\text\{Waste\}\_\{i\}^\{p\}\(\\hat\{l\}\_\{i\}^\{out\},\\hat\{\\tau\}\_\{i\}^\{call\}\)\.\(6\)
Detailed formulations and symbol definitions are provided in Appendix[B](https://arxiv.org/html/2512.04013#A2)\. Next,AugServeconstructs the costCi,1\{C\}\_\{i,1\}using[Equation 5](https://arxiv.org/html/2512.04013#S5.E5), combining: \(i\) the execution cost during the prefillCi,1p​r​e​f​i​l​lC\_\{i,1\}^\{prefill\}and decoding stagesCi,1d​e​c​o​d​eC\_\{i,1\}^\{decode\}\(Pi,1P\_\{i,1\}andDi,1D\_\{i,1\}in[Figure 5](https://arxiv.org/html/2512.04013#S4.F5)\), and \(ii\) the memory residency costCi,1c​a​l​lC\_\{i,1\}^\{call\}during the external call under policyp^i,1\\hat\{p\}\_\{i,1\}\(Wi,1W\_\{i,1\}in[Figure 5](https://arxiv.org/html/2512.04013#S4.F5)\):

Ci,1​\(p^i,1\)=Ci,1p​r​e​f​i​l​l\+Ci,1d​e​c​o​d​e\+Ci,1c​a​l​l​\(p^i,1\)C\_\{i,1\}\(\\hat\{p\}\_\{i,1\}\)\\\!\\\!=C\_\{i,1\}^\{prefill\}\+C\_\{i,1\}^\{decode\}\+C\_\{i,1\}^\{call\}\(\\hat\{p\}\_\{i,1\}\)\(7\)Ci,1c​a​l​l​\(p^i,1\)=\{Ci,1p​r​e​s​e​r​v​ep^i,1=Preserve0p^i,1=DiscardCi,1s​w​a​p−o​u​tp^i,1=Swap\.C\_\{i,1\}^\{call\}\(\\hat\{p\}\_\{i,1\}\)\\\!=\\\!\\begin\{cases\}C\_\{i,1\}^\{preserve\}&\\\!\\\!\\\!\\hat\{p\}\_\{i,1\}\\\!=\\\!\\texttt\{Preserve\}\\\\ 0&\\\!\\\!\\\!\\hat\{p\}\_\{i,1\}\\\!=\\\!\\texttt\{Discard\}\\\\ C\_\{i,1\}^\{swap\-out\}&\\\!\\\!\\\!\\hat\{p\}\_\{i,1\}\\\!=\\\!\\texttt\{Swap\}\\end\{cases\}\.\(8\)
With this estimated space\-time efficiency, the scheduler initializes request priorityθi,1\\theta\_\{i,1\}with[Equation 4](https://arxiv.org/html/2512.04013#S5.E4)\.

\(2\) Post\-Invocation Refinement:When the external call returns, the request transitions from the tool\-wait state to the resumption state\.AugServeupdates the resource consumption based on actual runtime feedback\. Specifically, the realized return length and the context\-handling policypi,k−1p\_\{i,k\-1\}applied during the previous waiting phase are fed back to refine the cost of the next segment\. To capture these evolving resource demands,AugServefirst computes a feedback realization termCi,kf​bC\_\{i,k\}^\{fb\}that quantifies the actual overhead incurred during the transition, including the context resumption stage \(Ri,2r​e​s​\(pi\)R^\{res\}\_\{i,2\}\(p\_\{i\}\)in[Figure 5](https://arxiv.org/html/2512.04013#S4.F5)\) and the incremental prefill stage for return tokens \(Pi,2r​e​tP^\{ret\}\_\{i,2\}in[Figure 5](https://arxiv.org/html/2512.04013#S4.F5)\):

Ci,kf​b​\(pi,k−1\)=Ci,kr​e​t​u​r​n\+\{0pi,k−1=PreserveCi,1r​e​c​o​m​p​u​t​epi,k−1=DiscardCi,1s​w​a​p−i​npi,k−1=Swap⏟Resumption Cost\.C\_\{i,k\}^\{fb\}\(p\_\{i,k\-1\}\)\\\!=\\\!C\_\{i,k\}^\{return\}\+\\underbrace\{\\begin\{cases\}0&\\\!\\\!\\\!\{p\}\_\{i,k\-1\}\\\!=\\\!\\texttt\{Preserve\}\\\\ C\_\{i,1\}^\{recompute\}&\\\!\\\!\\\!\{p\}\_\{i,k\-1\}\\\!=\\\!\\texttt\{Discard\}\\\\ C\_\{i,1\}^\{swap\-in\}&\\\!\\\!\\\!\{p\}\_\{i,k\-1\}\\\!=\\\!\\texttt\{Swap\}\\end\{cases\}\}\_\{\\text\{Resumption Cost\}\}\\\!\\\!\.\(9\)
Here, Resumption Cost reflects the overhead of restoring the execution state underpi,k−1p\_\{i,k\-1\}\. For instance, ifpi,k−1p\_\{i,k\-1\}adopts theDiscardpolicy, this term captures the KV cache recomputation cost\. Return tokens costCi,kr​e​t​u​r​nC\_\{i,k\}^\{return\}reflects the memory required to process the call returned tokens\. By replacing predictive estimates with realized execution feedback,Ci,kf​bC\_\{i,k\}^\{fb\}resolves uncertainty from prior predictions\. Subsequently,AugServepredicts the remaining execution \(Di,2D\_\{i,2\}in[Figure 5](https://arxiv.org/html/2512.04013#S4.F5)\) and any subsequent external calls \(Wi,2W\_\{i,2\}in[Figure 5](https://arxiv.org/html/2512.04013#S4.F5)\) to construct the finalCi,kC\_\{i,k\}:

Ci,k​\(p^i,k\)=Ci,kf​b​\(pi,k−1\)\+Ci,kd​e​c​o​d​e\+Ci,kc​a​l​l​\(p^i,k\)\.C\_\{i,k\}\(\\hat\{p\}\_\{i,k\}\)\\\!=\\\!C\_\{i,k\}^\{fb\}\(p\_\{i,k\-1\}\)\\\!\+C\_\{i,k\}^\{decode\}\+C\_\{i,k\}^\{call\}\(\\hat\{p\}\_\{i,k\}\)\.\(10\)
This segment\-level refinement uses realized execution feedback to correct prior predictive estimates, aligning scheduling decisions with actual system states and effectively mitigating inefficiencies from earlier predictions\. For requests comprising multiple service segments, this refinement process repeats iteratively until the request completes\.

Scheduling Procedure\.At each scheduling decision, the scheduler proceeds as follows:

- •Cost Construction:For each request, construct its space\-time costCi,kC\_\{i,k\}and compute the priorityθi,k\\theta\_\{i,k\}\.
- •Ranking:All requests in the global poolUeU^\{e\}are ranked in descending order of their current value densityθi\\theta\_\{i\}\.
- •Greedy Packing:Requests are selected greedily from the ranked queue until the aggregate memory footprint∑xie⋅mi​\(t\)\\sum x\_\{i\}^\{e\}\\cdot m\_\{i\}\(t\)reaches the system memory limitMeM^\{e\}\.

This procedure dynamically schedules requests based on state\-aware space\-time costs and value\-density priorities, adapting to evolving request states and external calls\. The complete pseudocode is provided in Appendix[A](https://arxiv.org/html/2512.04013#A1), and a theoretical analysis is provided in Appendix[E](https://arxiv.org/html/2512.04013#A5)\.

### 5\.4Dynamic Batch\-Level Token Budget

In the scheduling procedure \(§[5\.3](https://arxiv.org/html/2512.04013#S5.SS3)\), the memory constraintMeM^\{e\}governs greedy packing through a batch\-level token budget that limits the number of tokens processed per iteration\. However, using a fixed token budget can underutilize GPU memory or trigger unnecessary discarding of paused request contexts in augmented LLM inference\. We dynamically adjust the token budget based on \(i\) currently available GPU memoryGf​r​e​e​\(t\)G\_\{\{free\}\}\(t\), and \(ii\) reclaimable memoryGkvp​r​e​e​m​p​t​\(t\)G\_\{\\text\{kv\}\}^\{\{preempt\}\}\(t\)from preemptable paused requests, i\.e\., those selectingSwaporDiscardpolicies by[Equation 6](https://arxiv.org/html/2512.04013#S5.E6)\. Formally, the token budgetℬt​o​k​e​n​\(t\)\\mathcal\{B\}\_\{\{token\}\}\(t\)is computed as:

ℬt​o​k​e​n​\(t\)=⌊Gf​r​e​e​\(t\)\+Gk​vp​r​e​e​m​p​t​\(t\)μ⌋,\\mathcal\{B\}\_\{\{token\}\}\(t\)=\\left\\lfloor\\frac\{G\_\{\{free\}\}\(t\)\+G\_\{\{kv\}\}^\{\{preempt\}\}\(t\)\}\{\\mu\}\\right\\rfloor,\(11\)
whereμ\\mudenotes the per\-token memory footprint\. To prevent instability from transient memory fluctuations,ℬt​o​k​e​n​\(t\)\\mathcal\{B\}\_\{\{token\}\}\(t\)is clipped to\[βl​o​w⋅Tmax,βh​i​g​h⋅Tmax\]\[\\beta\_\{\{low\}\}\\cdot T\_\{\\max\},\\beta\_\{\{high\}\}\\cdot T\_\{\\max\}\], whereTmaxT\_\{\\max\}is a reference offline budget andβl​o​w,βh​i​g​h\\beta\_\{\{low\}\},\\beta\_\{\{high\}\}are scaling factors\. This design balances throughput with controlled use of preemptable paused requests’ memory while maintaining scheduling stability under fluctuating GPU memory conditions\.

![Refer to caption](https://arxiv.org/html/2512.04013v3/x7.png)

![Refer to caption](https://arxiv.org/html/2512.04013v3/x8.png)

![Refer to caption](https://arxiv.org/html/2512.04013v3/x9.png)

![Refer to caption](https://arxiv.org/html/2512.04013v3/x10.png)

![Refer to caption](https://arxiv.org/html/2512.04013v3/x11.png)\(a\)INFERCEPT dataset\.
![Refer to caption](https://arxiv.org/html/2512.04013v3/x12.png)\(b\)ToolBench dataset\.

Figure 7:Comparison of goodput, TTFT, and normalized latency among vLLM, INFERCEPT, Speculative\-SJF scheduling, and AugServe with different models and GPUs on INFERCEPT and ToolBench datasets\. First row: Goodput \(higher is better\)\. Second row: TTFT \(lower is better\)\. Third row: Normalized latency \(lower is better\)\.

## 6Evaluation

We evaluate our approach and baselines across different hardware, models, and datasets\.

- •Baselines:We compareAugServeagainst vLLM and INFERCEPT with FCFS scheduling, and a Speculative Shortest\-Job\-First \(SSJF\) baseline representing length\-based scheduling using predicted output length\.
- •Setup and models:We run GPT\-J\-6B on an RTX 4090 GPU \(24GB\), OPT\-13B on an H800 GPU \(80GB\), Vicuna\-13B on two A100 GPUs \(40GB each\), and Llama\-3\-70B\-Instruct on four A100 GPUs\.
- •Datasets:We utilize the INFERCEPT dataset and the ToolBench dataset\(Qinet al\.,[2024b](https://arxiv.org/html/2512.04013#bib.bib34)\), which features thousands of API calls across various categories\.
- •Workloads:\(W1\)Poisson arrivals over 30 minutes;\(W2\)Gamma arrivals with varying coefficients of variation\.
- •Metrics and SLOs:We report Time\-to\-First\-Token \(TTFT\), normalized latency \(end\-to\-end latency divided by output length\), and goodput \(number of SLO\-satisfying requests per unit time\)\. Following prior work\(Gaoet al\.,[2025](https://arxiv.org/html/2512.04013#bib.bib20); Wuet al\.,[2023](https://arxiv.org/html/2512.04013#bib.bib19)\), SLOs are set asTTFT<1​s\\text\{TTFT\}\\\!\\\!<\\\!\\\!1\\text\{s\}and normalized latency<10×\\\!\\\!<\\\!\\\!10\\timessingle\-iteration time\. Performance improvements ofAugServeover baselines are reported as the geometric mean across all experimental settings\.

### 6\.1End\-to\-End Performance

\(1\) Goodput\.[Figure 7](https://arxiv.org/html/2512.04013#S5.F7)reports the goodput ofAugServeand the baselines across three model configurations and request rates under the W1 workload\.AugServeconsistently outperforms all baselines, achieving a geometric mean goodput of7\.5×7\.5\\timesthat of vLLM,5\.7×5\.7\\timesthat of INFERCEPT, and1\.9×1\.9\\timesthat of SSJF\. The performance advantage is particularly pronounced under high contention\. For example, on the H800 GPU with the ToolBench dataset, at a request rate of 5\.0 req/s, the goodput of vLLM and INFERCEPT drops to near zero, whereasAugServesustains a goodput of 2\.4 req/s\. This gap arises because FCFS scheduling in vLLM and INFERCEPT exacerbates HoL blocking under increasing load\. As a result, queuing delays frequently exceed SLOs, sharply reducing SLO attainment \(i\.e\., the fraction of requests meeting SLOs, Appendix[D\.8](https://arxiv.org/html/2512.04013#A4.SS8)\) and thereby degrading goodput\. SSJF partially alleviates HoL blocking by prioritizing requests based on predicted output lengths\. However, it ignores the execution\-stage heterogeneity and latency variability introduced by external calls, leading to suboptimal performance under heavy load\. In contrast,AugServecontinuously refines request priorities by incorporating external\-call behaviors and cross\-round execution states\. This state\-aware design effectively mitigates HoL blocking in augmented LLM inference, sustaining high SLO attainment under peak request rates \(Appendix[D\.8](https://arxiv.org/html/2512.04013#A4.SS8)\) and thereby achieving substantially higher goodput\.

\(2\) Latency Performance\.[Figure 7](https://arxiv.org/html/2512.04013#S5.F7)also compares the TTFT and normalized latency ofAugServewith the baselines\. These two metrics jointly influence goodput, capturing request\-level responsiveness and token\-level execution efficiency, respectively\.

TTFT reflects the queuing delay before the first token is generated\. Across all evaluated scenarios,AugServeconsistently achieves substantially lower TTFT, with geometric mean reductions of 95\.6%, 96\.0%, and 92\.5% compared to vLLM, INFERCEPT, and SSJF, respectively\. Under heavy load, existing systems suffer from severe HoL blocking caused by requests stalled at external calls, which prevents the scheduler from prioritizing runnable and resource\-efficient executions\. In contrast,AugServemaintains high responsiveness by scheduling requests based on their execution stage and state\-dependent resource efficiency\. Meanwhile, normalized latency captures average token\-level execution efficiency while mitigating bias from varying sequence lengths, enabling fair comparison across requests\. Overall,AugServereduces normalized latency by 77\.8%, 72\.8%, and 36\.5% relative to vLLM, INFERCEPT, and SSJF, respectively\. These gains in both responsiveness and token\-level efficiency contribute toAugServe’s superior goodput\. Additional analyses of tail latency \(P95\) are provided in Appendix[D\.7](https://arxiv.org/html/2512.04013#A4.SS7)\.

\(3\) Additional Results\.Appendix[D](https://arxiv.org/html/2512.04013#A4)presents additional experimental results that further validate the effectiveness and generality ofAugServe\. We first evaluateAugServeunder diverse models and workload settings, including mixed external\-call and non\-external\-call workloads \([D\.1](https://arxiv.org/html/2512.04013#A4.SS1)\) and Llama\-3\-70B\-Instruct \([D\.2](https://arxiv.org/html/2512.04013#A4.SS2)\)\. Then, we provide complementary analyses of sensitivity toβ\\beta\([D\.3](https://arxiv.org/html/2512.04013#A4.SS3)\), robustness to bursty arrivals \([D\.5](https://arxiv.org/html/2512.04013#A4.SS5)\), and comparison with memory\-based SJF scheduling \([D\.6](https://arxiv.org/html/2512.04013#A4.SS6)\)\. Finally, we analyze the GPU memory occupancy \([D\.9](https://arxiv.org/html/2512.04013#A4.SS9)\)\.

### 6\.2Ablation Study

![Refer to caption](https://arxiv.org/html/2512.04013v3/x13.png)Figure 8:Comparison of normalized latency, TTFT, and goodput under prediction error injection with OPT\-13B on an H800 GPU using the INFERCEPT dataset\. Prediction errors are injected at 10%, 20%, 30%, 40%, and 50%\. Left: Normalized latency \(lower is better\)\. Middle: TTFT \(lower is better\)\. Right: Goodput \(higher is better\)\.Table 2:Ablation study ofAugServe\.TTFT \(s\)Goodput \(req/s\)Base306\.260\.15\+B293\.510\.21\+S14\.530\.93Aug3\.881\.07![Refer to caption](https://arxiv.org/html/2512.04013v3/x14.png)Figure 9:Latency breakdown\.\(1\) Ablation\.We conduct an ablation study to evaluate the contributions ofAugServe’s two core components: dynamic batch\-level token budget and state\-aware scheduling\. Experiments use OPT\-13B on an H800 GPU with a 3\.0 req/s workload on the INFERCEPT dataset\.[Table 2](https://arxiv.org/html/2512.04013#S6.T2)summarizes their impact on TTFT and goodput, with Base denoting the INFERCEPT baseline\.

We first enable the dynamic batch\-level token budget alone \(\+B in[Table 2](https://arxiv.org/html/2512.04013#S6.T2)\) on INFERCEPT\. By adapting batch capacity to available GPU memory, including reclaimable memory from paused requests, this component improves resource utilization and increases goodput by 41\.5%\. Next, we replaced the original FCFS algorithm with AugServe’s state\-aware scheduling \(\+S in[Table 2](https://arxiv.org/html/2512.04013#S6.T2)\) while keeping a fixed batch budget\. This reduces average TTFT by 95\.2% and boosts goodput by4\.2×4\.2\\times\. Finally, combining both components in the fullAugServe\(Aug in[Table 2](https://arxiv.org/html/2512.04013#S6.T2)\) achieves the best overall performance, yielding lower TTFT and higher goodput than either component alone\. This confirms that dynamic batch\-level capacity adaptation and state\-aware scheduling are complementary and jointly essential for efficient augmented LLM inference\.

\(2\) Latency Breakdown\.Figure[9](https://arxiv.org/html/2512.04013#S6.F9)shows the breakdown of end\-to\-end request latency forAugServeand the baselines\. The results indicate thatAugServe’s performance gains are primarily attributed to a substantial reduction in queuing time\. Moreover, the prediction module inAugServeincurs negligible overhead, accounting for 0\.1% of end\-to\-end latency on average \(0\.18 s per request\)\.

### 6\.3Robustness to Prediction Errors

To assess the robustness ofAugServeto prediction inaccuracies, we inject noise into bothexternal\_call\_durationandoutput\_lengthpredictions\. Specifically, for each predictionm^\\hat\{m\}, we usem^​\(1\+ϵ\)\\hat\{m\}\(1\+\\epsilon\)as the noisy prediction, whereϵ\\epsilonis randomly chosen from\{−p,\+p\}\\\{\-p,\+p\\\}with equal probability\. We varyppfrom 10% to 50% and evaluate OPT\-13B on an H800 GPU using the INFERCEPT dataset\.

[Figure 8](https://arxiv.org/html/2512.04013#S6.F8)reports the impact of prediction errors on normalized latency, TTFT, and goodput\. Across all error levels, goodput and normalized latency remain largely stable, showing thatAugServeis insensitive to moderate\-to\-large prediction noise\. TTFT increases mildly as the prediction error grows, with an absolute increase of roughly 10–20 s even under high error rates of 40–50%\. Overall, the performance impact of mispredictions remains limited, demonstrating thatAugServeis robust to prediction inaccuracies\. This robustness arises fromAugServe’s feedback\-driven design, which continuously refines scheduling decisions using realized runtime information upon external call returns, rather than relying solely on static predictions\.

### 6\.4Scheduling Overhead

Table 3:Average per\-iteration scheduling overhead \(s\) under different request rates on the INFERCEPT dataset with OPT\-13B and an H800 GPU\.Req/sINFERCEPTAugServe3\.00\.0130\.0184\.00\.0150\.022SinceAugServeperforms iteration\-level scheduling, we further measure its per\-iteration scheduling overhead\. Table[3](https://arxiv.org/html/2512.04013#S6.T3)reports the average scheduling overhead on the INFERCEPT dataset with OPT\-13B on an H800 GPU\.AugServeincurs slightly higher overhead than INFERCEPT due to its richer state\-aware scheduling logic, but the overhead remains small\. Compared with the substantial queuing\-time reduction achieved byAugServe, this additional overhead is negligible\. Additional scalability results under different numbers of paused requests are provided in Appendix[D\.4](https://arxiv.org/html/2512.04013#A4.SS4)\.

## 7Conclusion

This paper presentsAugServe, a system for improving inference efficiency in augmented LLM services\.AugServecombines adaptively state\-aware request scheduling with a dynamic batch\-level token budget to reduce queuing delays and substantially improve effective throughput\.

## Acknowledgements

We would like to thank the anonymous reviewers for their tremendous feedback and comments, which have substantially improved the content and presentation of this paper\.

## Impact Statement

This paper presents work whose goal is to advance the field of machine learning systems\. There are many potential societal consequences of our work, none of which we feel must be specifically highlighted here\.

## References

- R\. Abhyankar, Z\. He, V\. Srivatsa, H\. Zhang, and Y\. Zhang \(2024\)INFERCEPT: efficient intercept support for augmented large language model inference\.InProceedings of the 41st International Conference on Machine Learning,ICML’24\.Cited by:[Appendix B](https://arxiv.org/html/2512.04013#A2.p1.5),[Appendix C](https://arxiv.org/html/2512.04013#A3.p1.1),[§1](https://arxiv.org/html/2512.04013#S1.p1.1),[§1](https://arxiv.org/html/2512.04013#S1.p2.1),[§1](https://arxiv.org/html/2512.04013#S1.p4.1),[§2\.2](https://arxiv.org/html/2512.04013#S2.SS2.p2.1)\.
- A\. Agrawal, N\. Kedia, A\. Panwar, J\. Mohan, N\. Kwatra, B\. Gulavani, A\. Tumanov, and R\. Ramjee \(2024\)Taming\{\\\{throughput\-latency\}\\\}tradeoff in\{\\\{llm\}\\\}inference with\{\\\{sarathi\-serve\}\\\}\.In18th USENIX Symposium on Operating Systems Design and Implementation \(OSDI 24\),pp\. 117–134\.Cited by:[Appendix C](https://arxiv.org/html/2512.04013#A3.p1.1)\.
- Anthropic \(2024\)Model context protocol \(mcp\)\.Note:[https://modelcontextprotocol\.io](https://modelcontextprotocol.io/)Cited by:[§2\.1](https://arxiv.org/html/2512.04013#S2.SS1.p1.1)\.
- N\. Chen, H\. Li, B\. Wang, and J\. Li \(2024a\)From good to great: improving math reasoning with tool\-augmented interleaf prompting\.InProceedings of the 2nd Workshop on Natural Language Reasoning and Structured Explanations \(@ACL 2024\),B\. Dalvi Mishra, G\. Durrett, P\. Jansen, B\. Lipkin, D\. Neves Ribeiro, L\. Wong, X\. Ye, and W\. Zhao \(Eds\.\),Bangkok, Thailand,pp\. 64–79\.External Links:[Link](https://aclanthology.org/2024.nlrse-1.7/)Cited by:[§1](https://arxiv.org/html/2512.04013#S1.p1.1),[§2\.1](https://arxiv.org/html/2512.04013#S2.SS1.p1.1)\.
- S\. Chen, Y\. Wang, Y\. Wu, Q\. Chen, Z\. Xu, W\. Luo, K\. Zhang, and L\. Zhang \(2024b\)Advancing tool\-augmented large language models: integrating insights from errors in inference trees\.Advances in Neural Information Processing Systems37,pp\. 106555–106581\.Cited by:[§1](https://arxiv.org/html/2512.04013#S1.p1.1),[§2\.1](https://arxiv.org/html/2512.04013#S2.SS1.p1.1)\.
- X\. Fei, X\. Zheng, and H\. Feng \(2025\)Mcp\-zero: proactive toolchain construction for llm agents from scratch\.arXiv e\-prints,pp\. arXiv–2506\.Cited by:[§2\.1](https://arxiv.org/html/2512.04013#S2.SS1.p1.1)\.
- Y\. Fu, S\. Zhu, R\. Su, A\. Qiao, I\. Stoica, and H\. Zhang \(2024\)Efficient llm scheduling by learning to rank\.Advances in Neural Information Processing Systems37,pp\. 59006–59029\.Cited by:[Appendix C](https://arxiv.org/html/2512.04013#A3.p2.1),[§1](https://arxiv.org/html/2512.04013#S1.p6.1),[§3\.1](https://arxiv.org/html/2512.04013#S3.SS1.p1.1)\.
- A\. Gade, J\. G\. Jetcheva, and H\. Trivedi \(2025\)It’s about time: incorporating temporality in retrieval augmented language models\.In2025 IEEE Conference on Artificial Intelligence \(CAI\),Vol\.,pp\. 75–82\.External Links:[Document](https://dx.doi.org/10.1109/CAI64502.2025.00019)Cited by:[§1](https://arxiv.org/html/2512.04013#S1.p1.1),[§2\.1](https://arxiv.org/html/2512.04013#S2.SS1.p1.1)\.
- S\. Gao, X\. Zhang, Y\. Shen, and L\. Chen \(2025\)Apt\-serve: adaptive request scheduling on hybrid cache for scalable llm inference serving\.Proceedings of the ACM on Management of Data3\(3\),pp\. 1–28\.Cited by:[§1](https://arxiv.org/html/2512.04013#S1.p3.1),[5th item](https://arxiv.org/html/2512.04013#S6.I1.i5.p1.2)\.
- I\. Gim, S\. Lee, and L\. Zhong \(2024\)Asynchronous llm function calling\.arXiv preprint arXiv:2412\.07017\.Cited by:[§1](https://arxiv.org/html/2512.04013#S1.p2.1)\.
- H\. Go and S\. Park \(2025\)A study on classification based concurrent api calls and optimal model combination for tool augmented llms for ai agent\.Scientific Reports15\(1\),pp\. 20579\.Cited by:[§1](https://arxiv.org/html/2512.04013#S1.p1.1),[§2\.1](https://arxiv.org/html/2512.04013#S2.SS1.p1.1)\.
- S\. Hao, T\. Liu, Z\. Wang, and Z\. Hu \(2023\)Toolkengpt: augmenting frozen language models with massive tools via tool embeddings\.Advances in neural information processing systems36,pp\. 45870–45894\.Cited by:[§1](https://arxiv.org/html/2512.04013#S1.p1.1),[§2\.1](https://arxiv.org/html/2512.04013#S2.SS1.p1.1)\.
- C\. Hu, H\. Huang, L\. Xu, X\. Chen, C\. Wang, J\. Xu, S\. Chen, H\. Feng, S\. Wang, Y\. Bao,et al\.\(2025a\)ShuffleInfer: disaggregate llm inference for mixed downstream workloads\.ACM Transactions on Architecture and Code Optimization\.Cited by:[Appendix C](https://arxiv.org/html/2512.04013#A3.p2.1),[§5\.2](https://arxiv.org/html/2512.04013#S5.SS2.p1.4)\.
- Y\. Hu, X\. Liu, G\. Yang, L\. Li, K\. Zeng, Z\. Zhao, S\. Chen, L\. Zhao, W\. Li, and K\. Li \(2025b\)TightLLM: maximizing throughput for llm inference via adaptive offloading policy\.IEEE Transactions on Computers\.Cited by:[§2\.2](https://arxiv.org/html/2512.04013#S2.SS2.p1.1)\.
- J\. Jeong and J\. Ahn \(2025\)Accelerating llm serving for multi\-turn dialogues with efficient resource management\.InProceedings of the 30th ACM International Conference on Architectural Support for Programming Languages and Operating Systems, Volume 2,pp\. 1–15\.Cited by:[Appendix C](https://arxiv.org/html/2512.04013#A3.p1.1),[§2\.2](https://arxiv.org/html/2512.04013#S2.SS2.p1.1)\.
- Y\. Jin, C\. Wu, D\. Brooks, and G\. Wei \(2023\)S3: increasing gpu utilization during generative inference for higher throughput\.NIPS ’23,Red Hook, NY, USA\.Cited by:[Appendix C](https://arxiv.org/html/2512.04013#A3.p2.1),[§1](https://arxiv.org/html/2512.04013#S1.p6.1),[§3\.1](https://arxiv.org/html/2512.04013#S3.SS1.p1.1),[§5\.2](https://arxiv.org/html/2512.04013#S5.SS2.p1.4)\.
- S\. Karthik, P\. Sioulas, A\. Pradhan, R\. Subramanya, I\. Mytilinis, and A\. Ailamaki \(2024\)Optimizing goodput through sharing for batch analytics with deadlines\.\.InEDBT,pp\. 332–344\.Cited by:[§1](https://arxiv.org/html/2512.04013#S1.p3.1)\.
- W\. Kwon, Z\. Li, S\. Zhuang, Y\. Sheng, L\. Zheng, C\. H\. Yu, J\. Gonzalez, H\. Zhang, and I\. Stoica \(2023\)Efficient memory management for large language model serving with pagedattention\.InProceedings of the 29th symposium on operating systems principles,pp\. 611–626\.Cited by:[Appendix C](https://arxiv.org/html/2512.04013#A3.p1.1),[§1](https://arxiv.org/html/2512.04013#S1.p4.1),[§2\.2](https://arxiv.org/html/2512.04013#S2.SS2.p1.1)\.
- Y\. Lu, H\. Yu, and D\. Khashabi \(2024\)GEAR: augmenting language models with generalizable and efficient tool resolution\.InProceedings of the 18th Conference of the European Chapter of the Association for Computational Linguistics \(Volume 1: Long Papers\),Y\. Graham and M\. Purver \(Eds\.\),St\. Julian’s, Malta,pp\. 112–138\.External Links:[Link](https://aclanthology.org/2024.eacl-long.7/),[Document](https://dx.doi.org/10.18653/v1/2024.eacl-long.7)Cited by:[§1](https://arxiv.org/html/2512.04013#S1.p1.1),[§2\.1](https://arxiv.org/html/2512.04013#S2.SS1.p1.1)\.
- G\. Mialon, R\. Dessì, M\. Lomeli, C\. Nalmpantis, R\. Pasunuru, R\. Raileanu, B\. Rozière, T\. Schick, J\. Dwivedi\-Yu, A\. Celikyilmaz,et al\.\(2023\)Augmented language models: a survey\.arXiv preprint arXiv:2302\.07842\.Cited by:[§2\.1](https://arxiv.org/html/2512.04013#S2.SS1.p1.1)\.
- P\. Patel, E\. Choukse, C\. Zhang, A\. Shah, Í\. Goiri, S\. Maleki, and R\. Bianchini \(2025\)Splitwise: efficient generative llm inference using phase splitting\.InProceedings of the 51st Annual International Symposium on Computer Architecture,ISCA ’24,pp\. 118–132\.External Links:ISBN 9798350326581,[Link](https://doi.org/10.1109/ISCA59077.2024.00019),[Document](https://dx.doi.org/10.1109/ISCA59077.2024.00019)Cited by:[§1](https://arxiv.org/html/2512.04013#S1.p3.1)\.
- S\. G\. Patil, H\. Mao, F\. Yan, C\. C\. Ji, V\. Suresh, I\. Stoica, and J\. E\. Gonzalez \(2025\)The berkeley function calling leaderboard \(BFCL\): from tool use to agentic evaluation of large language models\.InForty\-second International Conference on Machine Learning,External Links:[Link](https://openreview.net/forum?id=2GmDdhBdDk)Cited by:[§2\.1](https://arxiv.org/html/2512.04013#S2.SS1.p1.1)\.
- Z\. Qi, X\. Liu, I\. L\. Iong, H\. Lai, X\. Sun, J\. Sun, X\. Yang, Y\. Yang, S\. Yao, W\. Xu, J\. Tang, and Y\. Dong \(2025\)WebRL: training LLM web agents via self\-evolving online curriculum reinforcement learning\.InThe Thirteenth International Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=oVKEAFjEqv)Cited by:[§1](https://arxiv.org/html/2512.04013#S1.p1.1)\.
- Y\. Qin, S\. Hu, Y\. Lin, W\. Chen, N\. Ding, G\. Cui, Z\. Zeng, X\. Zhou, Y\. Huang, C\. Xiao,et al\.\(2024a\)Tool learning with foundation models\.ACM Computing Surveys57\(4\),pp\. 1–40\.Cited by:[§1](https://arxiv.org/html/2512.04013#S1.p1.1)\.
- Y\. Qin, S\. Liang, Y\. Ye, K\. Zhu, L\. Yan, Y\. Lu, Y\. Lin, X\. Cong, X\. Tang, B\. Qian, S\. Zhao, L\. Hong, R\. Tian, R\. Xie, J\. Zhou, M\. Gerstein, dahai li, Z\. Liu, and M\. Sun \(2024b\)ToolLLM: facilitating large language models to master 16000\+ real\-world APIs\.InThe Twelfth International Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=dHng2O0Jjr)Cited by:[3rd item](https://arxiv.org/html/2512.04013#S6.I1.i3.p1.1)\.
- T\. Schick, J\. Dwivedi\-Yu, R\. Dessì, R\. Raileanu, M\. Lomeli, E\. Hambro, L\. Zettlemoyer, N\. Cancedda, and T\. Scialom \(2023\)Toolformer: language models can teach themselves to use tools\.Advances in Neural Information Processing Systems36,pp\. 68539–68551\.Cited by:[§1](https://arxiv.org/html/2512.04013#S1.p1.1),[§2\.1](https://arxiv.org/html/2512.04013#S2.SS1.p1.1)\.
- R\. Shahout, eran malach, C\. Liu, W\. Jiang, M\. Yu, and M\. Mitzenmacher \(2025a\)DON’t STOP ME NOW: EMBEDDING BASED SCHEDULING FOR LLMS\.InThe Thirteenth International Conference on Learning Representations,External Links:[Link](https://openreview.net/forum?id=7JhGdZvW4T)Cited by:[Appendix C](https://arxiv.org/html/2512.04013#A3.p2.1)\.
- R\. Shahout, C\. Liang, S\. Xin, Q\. Lao, Y\. Cui, M\. Yu, and M\. Mitzenmacher \(2025b\)Fast inference for augmented large language models\.InThe Thirty\-ninth Annual Conference on Neural Information Processing Systems,External Links:[Link](https://openreview.net/forum?id=uNqTxj5brQ)Cited by:[Appendix C](https://arxiv.org/html/2512.04013#A3.p2.1),[§3\.1](https://arxiv.org/html/2512.04013#S3.SS1.p1.1)\.
- Y\. Sheng, L\. Zheng, B\. Yuan, Z\. Li, M\. Ryabinin, B\. Chen, P\. Liang, C\. Ré, I\. Stoica, and C\. Zhang \(2023\)Flexgen: high\-throughput generative inference of large language models with a single gpu\.InInternational Conference on Machine Learning,pp\. 31094–31116\.Cited by:[Appendix C](https://arxiv.org/html/2512.04013#A3.p1.1),[§2\.2](https://arxiv.org/html/2512.04013#S2.SS2.p1.1)\.
- W\. Su, Y\. Tang, Q\. Ai, Z\. Wu, and Y\. Liu \(2024\)DRAGIN: dynamic retrieval augmented generation based on the information needs of large language models\.arXiv preprint arXiv:2403\.10081\.Cited by:[§1](https://arxiv.org/html/2512.04013#S1.p1.1),[§2\.1](https://arxiv.org/html/2512.04013#S2.SS1.p1.1)\.
- Z\. Wang, S\. Li, Y\. Zhou, X\. Li, Z\. Zhang, N\. Cam\-Tu, R\. Gu, C\. Tian, G\. Chen, and S\. Zhong \(2025\)Revisiting service level objectives and system level metrics in large language model serving\.External Links:2410\.14257,[Link](https://arxiv.org/abs/2410.14257)Cited by:[§1](https://arxiv.org/html/2512.04013#S1.p3.1)\.
- G\. Wölflein, D\. Ferber, D\. Truhn, O\. Arandjelovic, and J\. N\. Kather \(2025\)LLM agents making agent tools\.InProceedings of the 63rd Annual Meeting of the Association for Computational Linguistics \(Volume 1: Long Papers\),W\. Che, J\. Nabende, E\. Shutova, and M\. T\. Pilehvar \(Eds\.\),Vienna, Austria,pp\. 26092–26130\.External Links:[Link](https://aclanthology.org/2025.acl-long.1266/),[Document](https://dx.doi.org/10.18653/v1/2025.acl-long.1266),ISBN 979\-8\-89176\-251\-0Cited by:[§2\.1](https://arxiv.org/html/2512.04013#S2.SS1.p1.1)\.
- B\. Wu, Y\. Zhong, Z\. Zhang, S\. Liu, F\. Liu, Y\. Sun, G\. Huang, X\. Liu, and X\. Jin \(2023\)Fast distributed inference serving for large language models\.arXiv preprint arXiv:2305\.05920\.Cited by:[Appendix C](https://arxiv.org/html/2512.04013#A3.p2.1),[§1](https://arxiv.org/html/2512.04013#S1.p3.1),[§1](https://arxiv.org/html/2512.04013#S1.p6.1),[§3\.1](https://arxiv.org/html/2512.04013#S3.SS1.p1.1),[5th item](https://arxiv.org/html/2512.04013#S6.I1.i5.p1.2)\.
- B\. Yao and V\. Yadav \(2025\)A toolbox, not a hammer–multi\-tag: scaling math reasoning with multi\-tool aggregation\.arXiv preprint arXiv:2507\.18973\.Cited by:[§1](https://arxiv.org/html/2512.04013#S1.p1.1),[§2\.1](https://arxiv.org/html/2512.04013#S2.SS1.p1.1)\.
- G\. Yu, J\. S\. Jeong, G\. Kim, S\. Kim, and B\. Chun \(2022\)Orca: a distributed serving system for\{\\\{transformer\-based\}\\\}generative models\.In16th USENIX Symposium on Operating Systems Design and Implementation \(OSDI 22\),pp\. 521–538\.Cited by:[Appendix C](https://arxiv.org/html/2512.04013#A3.p2.1),[§2\.2](https://arxiv.org/html/2512.04013#S2.SS2.p1.1)\.
- H\. Zhang, Y\. Tang, A\. Khandelwal, and I\. Stoica \(2023\)SHEPHERD: serving DNNs in the wild\.In20th USENIX Symposium on Networked Systems Design and Implementation \(NSDI 23\),pp\. 787–808\.Cited by:[§1](https://arxiv.org/html/2512.04013#S1.p3.1)\.
- Y\. Zhang, Z\. Ma, Y\. Ma, Z\. Han, Y\. Wu, and V\. Tresp \(2025\)WebPilot: a versatile and autonomous multi\-agent system for web task execution with strategic exploration\.InProceedings of the Thirty\-Ninth AAAI Conference on Artificial Intelligence and Thirty\-Seventh Conference on Innovative Applications of Artificial Intelligence and Fifteenth Symposium on Educational Advances in Artificial Intelligence,AAAI’25/IAAI’25/EAAI’25\.External Links:ISBN 978\-1\-57735\-897\-8,[Link](https://doi.org/10.1609/aaai.v39i22.34505),[Document](https://dx.doi.org/10.1609/aaai.v39i22.34505)Cited by:[§1](https://arxiv.org/html/2512.04013#S1.p1.1)\.
- Z\. Zheng, X\. Ren, F\. Xue, Y\. Luo, X\. Jiang, and Y\. You \(2023\)Response length perception and sequence scheduling: an llm\-empowered llm inference pipeline\.InProceedings of the 37th International Conference on Neural Information Processing Systems,NIPS ’23,Red Hook, NY, USA\.Cited by:[Appendix C](https://arxiv.org/html/2512.04013#A3.p2.1)\.
- Z\. Zheng, X\. Ji, T\. Fang, F\. Zhou, C\. Liu, and G\. Peng \(2025\)BatchLLM: optimizing large batched llm inference with global prefix sharing and throughput\-oriented token batching\.External Links:2412\.03594,[Link](https://arxiv.org/abs/2412.03594)Cited by:[§1](https://arxiv.org/html/2512.04013#S1.p7.1),[§3\.2](https://arxiv.org/html/2512.04013#S3.SS2.p1.1)\.
- Y\. Zhong, S\. Liu, J\. Chen, J\. Hu, Y\. Zhu, X\. Liu, X\. Jin, and H\. Zhang \(2024\)\{\\\{distserve\}\\\}: Disaggregating prefill and decoding for goodput\-optimized large language model serving\.In18th USENIX Symposium on Operating Systems Design and Implementation \(OSDI 24\),pp\. 193–210\.Cited by:[§1](https://arxiv.org/html/2512.04013#S1.p3.1)\.

## Appendix AState\-Aware Adaptive Scheduling Algorithm

Table 4:Notation and definitions of key symbols\.SymbolDefinitionRiR\_\{i\}Theii\-th request in the systemnin\_\{i\}Total number of service segments for requestRiR\_\{i\}Si,kS\_\{i,k\}Thekk\-th service segment of requestRiR\_\{i\}\.Pi,1P\_\{i,1\}Standard prompt prefill stage in the initial segment\.Di,kD\_\{i,k\}Decoding stage within segmentkk\.Wi,kW\_\{i,k\}Tool\-wait stage where the request awaits external responses\.Ri,kr​e​s​\(pi\)R\_\{i,k\}^\{res\}\(p\_\{i\}\)Context resumption stage, governed by policypip\_\{i\}\.Pi,kr​e​tP\_\{i,k\}^\{ret\}Incremental prefill for processing returned tool tokens\.Π\\PiSet of context\-handling policies:\{Preserve, Swap, Discard\}\\\{\\texttt\{Preserve, Swap, Discard\}\\\}\.VieV\_\{i\}^\{e\}Scheduling value for requestiiat iterationee\.wiew\_\{i\}^\{e\}Cumulative waiting time for requestiiup to iterationee\.β\\betaStarvation prevention aging factor\.xiex\_\{i\}^\{e\}Binary decision variable: 1 if requestiiis scheduled, 0 otherwise\.MeM^\{e\}Instantaneous GPU memory capacity constraint at iterationee\.mi​\(t\)m\_\{i\}\(t\)Instantaneous memory occupancy of requestiiat timett\.Ci,k​\(pi,k\)C\_\{i,k\}\(p\_\{i,k\}\)Space\-time cost \(action\) of segmentSi,kS\_\{i,k\}under policypi,kp\_\{i,k\}\.τi,k\\tau\_\{i,k\}Total residency duration of the request segment\.θi,k\\theta\_\{i,k\}Scheduling priority defined as the value densityVi/Ci,kV\_\{i\}/C\_\{i,k\}\.l^io​u​t\\hat\{l\}\_\{i\}^\{out\}Predicted output token length\.τ^ic​a​l​l\\hat\{\\tau\}\_\{i\}^\{call\}Predicted duration of the external tool call\.p^i,k\\hat\{p\}\_\{i,k\}Predicted context policy during the wait stage\.Ci,kf​bC\_\{i,k\}^\{fb\}Feedback\-driven realized cost term fork\>1k\>1\.pi,k−1\{p\}\_\{i,k\-1\}Context policy actually executed during the previous wait phase\.ℬt​o​k​e​n​\(t\)\\mathcal\{B\}\_\{token\}\(t\)Dynamic batch\-level token budget at timett\.Gf​r​e​e​\(t\)G\_\{free\}\(t\)Number of currently available free GPU memory blocks\.Gk​vp​r​e​e​m​p​t​\(t\)G\_\{kv\}^\{preempt\}\(t\)Reclaimable memory blocks held by paused request contexts\.μ\\muMemory footprint per token\.Tm​a​xT\_\{max\}Static offline reference token budget\.βl​o​w,βh​i​g​h\\beta\_\{low\},\\beta\_\{high\}Scaling factors for the smoothing range of the token budget\.Algorithm 1AugServe: State\-Aware Adaptive Scheduling with Dynamic Token Budget1:Input:Request queues:

running,swapped,waiting,paused\\mathrm\{running\},\\mathrm\{swapped\},\\mathrm\{waiting\},\\mathrm\{paused\}; Predictor

Pred\\mathrm\{Pred\}; Aging parameter

β\\beta; Scaling bounds

βl​o​w,βh​i​g​h\\beta\_\{low\},\\beta\_\{high\}\.

2:whileTruedo

3:// \(1\) Request arrival & Predictive Initialization

4:foreach

r∈r\\inarrivalsdo

5:

\(τ^ic​a​l​l,l^io​u​t\)←Pred​\(r\)\(\\hat\{\\tau\}\_\{i\}^\{call\},\\hat\{l\}\_\{i\}^\{out\}\)\\leftarrow\\mathrm\{Pred\}\(r\)
6:

p^i,1←arg⁡minp∈Π⁡Wasteip​\(l^io​u​t,τ^ic​a​l​l\)\\hat\{p\}\_\{i,1\}\\leftarrow\\arg\\min\_\{p\\in\\Pi\}\\text\{Waste\}\_\{i\}^\{p\}\(\\hat\{l\}\_\{i\}^\{out\},\\hat\{\\tau\}\_\{i\}^\{call\}\)// Select policy

7:Estimate

C^i,1\\hat\{C\}\_\{i,1\}using

p^i,1\\hat\{p\}\_\{i,1\}and

\(τ^ic​a​l​l,l^io​u​t\)\(\\hat\{\\tau\}\_\{i\}^\{call\},\\hat\{l\}\_\{i\}^\{out\}\)by[Equation 5](https://arxiv.org/html/2512.04013#S5.E5)

8:

r\.θi,1←\(1\+β⋅wi\)/C^i,1r\.\\theta\_\{i,1\}\\leftarrow\(1\+\\beta\\cdot w\_\{i\}\)/\\hat\{C\}\_\{i,1\}by[Equation 2](https://arxiv.org/html/2512.04013#S4.E2)and[Equation 4](https://arxiv.org/html/2512.04013#S5.E4)

9:

waiting\.push​\(r\)\\mathrm\{waiting\}\.\\text\{push\}\(r\)
10:endfor

11:// \(2\) State\-Aware refinement upon tool return

12:foreach

\(r,pi,k−1\)∈\(r,p\_\{i,k\-1\}\)\\inpaused\\mathrm\{paused\}do

13:if

r\.apiFinished​\(\)r\.\\mathrm\{apiFinished\}\(\)then

14:Update

Ci,kf​bC\_\{i,k\}^\{fb\}using realized policy

pi,k−1\{p\}\_\{i,k\-1\}by[Equation 9](https://arxiv.org/html/2512.04013#S5.E9)

15:

Ci,k←Ci,kf​b\+Ci,kd​e​c​o​d​e\+C^i,kc​a​l​lC\_\{i,k\}\\leftarrow C\_\{i,k\}^\{fb\}\+C\_\{i,k\}^\{decode\}\+\\hat\{C\}\_\{i,k\}^\{call\}
16:if

pi,k−1=Preserve\{p\}\_\{i,k\-1\}=\\mathrm\{Preserve\}then

17:

running\.push​\(r\)\\mathrm\{running\}\.\\text\{push\}\(r\)
18:elseif

pi,k−1=Swap\{p\}\_\{i,k\-1\}=\\mathrm\{Swap\}then

19:

swapped\.push​\(r\)\\mathrm\{swapped\}\.\\text\{push\}\(r\)
20:else

21:

waiting\.push​\(r\)\\mathrm\{waiting\}\.\\text\{push\}\(r\)// Discard policy

22:endif

23:Update priority

r\.θi,k←\(1\+β⋅wi\)/Ci,kr\.\\theta\_\{i,k\}\\leftarrow\(1\+\\beta\\cdot w\_\{i\}\)/C\_\{i,k\}
24:endif

25:endfor

26:// \(3\) Dynamic token budget adjustment

27:

ℬt​o​k​e​n​\(t\)←⌊\(Gf​r​e​e​\(t\)\+Gkvpreempt​\(t\)\)/μ⌋\\mathcal\{B\}\_\{token\}\(t\)\\leftarrow\\lfloor\(G\_\{free\}\(t\)\+G\_\{\\text\{kv\}\}^\{\\text\{preempt\}\}\(t\)\)/\\mu\\rfloorby[Equation 11](https://arxiv.org/html/2512.04013#S5.E11)

28:

ℬt​o​k​e​n​\(t\)←clip​\(ℬt​o​k​e​n​\(t\),βl​o​w⋅Tm​a​x,βh​i​g​h⋅Tm​a​x\)\\mathcal\{B\}\_\{token\}\(t\)\\leftarrow\\text\{clip\}\(\\mathcal\{B\}\_\{token\}\(t\),\\beta\_\{low\}\\cdot T\_\{max\},\\beta\_\{high\}\\cdot T\_\{max\}\)
29:// \(4\) Global queue ranking & Greedy packing

30:Sort all

rrin candidate queues by

θi,k\\theta\_\{i,k\}
31:

scheduled←∅\\mathrm\{scheduled\}\\leftarrow\\emptyset
32:foreach

r∈r\\insorted candidatesdo

33:if

active​\_​tokens\+tokens​\(r\)≤ℬt​o​k​e​n​\(t\)\\mathrm\{active\\\_tokens\}\+\\mathrm\{tokens\}\(r\)\\leq\\mathcal\{B\}\_\{token\}\(t\)then

34:

scheduled←scheduled∪\{r\}\\mathrm\{scheduled\}\\leftarrow\\mathrm\{scheduled\}\\cup\\\{r\\\}
35:

active​\_​tokens←active​\_​tokens\+tokens​\(r\)\\mathrm\{active\\\_tokens\}\\leftarrow\\mathrm\{active\\\_tokens\}\+\\mathrm\{tokens\}\(r\)
36:Update

r\.w​a​i​t​i​n​g​\_​t​i​m​er\.waiting\\\_time
37:else

38:break// Budget reached

39:endif

40:endfor

41:// \(5\) Execute one iteration

42:forward\(

scheduled\\mathrm\{scheduled\}\)

43:endwhile

[Table 4](https://arxiv.org/html/2512.04013#A1.T4)summarizes the symbols used throughout the paper\. The overall workflow ofAugServeis presented in[algorithm 1](https://arxiv.org/html/2512.04013#alg1), which integrates state\-aware adaptive scheduling with dynamic batch\-level token budget\.

Upon request arrival,AugServeinvokes a lightweight prediction module to estimate theexternal\_call\_durationandoutput\_length\. These estimates are used to select an initial context\-handling policy and to compute the request’s initial scheduling priority based on its expected execution characteristics \(Lines 4–10\)\.

When an external tool call completes,AugServeperforms state\-aware refinement by replacing predictive estimates with realized runtime feedback\. The scheduling cost and priority are updated based on the actual context\-handling policy and return length, and the request is reinserted into the appropriate queue according to its execution state \(Lines 12–25\)\.

To respect runtime memory constraints,AugServedynamically adjusts the batch\-level token budget based on available GPU memory and reclaimable memory from paused requests under different context\-handling policies\. Bounded smoothing is applied to prevent abrupt budget fluctuations and ensure system stability \(Lines 27–28\)\.

Finally,AugServeglobally ranks all runnable requests according to their refined scheduling priorities \(Line 30\)\. A batch is then greedily constructed under the current token budget constraint \(Lines 32–40\) and executed in the next forward iteration\.

## Appendix BContext\-Handling Policy

The construction of the predictive space\-time costC^i,k\\hat\{C\}\_\{i,k\}\(§[5\.3](https://arxiv.org/html/2512.04013#S5.SS3)\) is inherently tied to the choice of context\-handling policyπ^i,k\\hat\{\\pi\}\_\{i,k\}\. During an external tool call, the resource consumption of a request depends critically on how its KV cache is managed, reflecting a fundamental trade\-off between GPU memory occupancy and computational overhead\. Specifically, thePreservepolicy avoids recomputation by keeping the context in GPU memory throughout the call, but incurs high memory occupancy, whereas theDiscardpolicy releases GPU memory at the cost of recomputation when the request resumes\. As shown in[Figure 4](https://arxiv.org/html/2512.04013#S3.F4)and[Figure 10](https://arxiv.org/html/2512.04013#A2.F10), external call durations and cumulative context lengths exhibit highly heterogeneous distributions across both datasets\. This variability implies that a fixed context\-handling policy is suboptimal: short external calls with small context favor preserving context to avoid recomputation overhead, while long calls with large context benefit from releasing GPU memory via discarding or swapping\. To minimize the total resource overhead induced by external calls,AugServeselects the most efficient context\-handling policy based on the request’s current context lengthLiL\_\{i\}, its predictedoutput\_lengthl^io​u​t\\hat\{l\}\_\{i\}^\{out\}and predictedexternal\_call\_durationτ^ic​a​l​l\\hat\{\\tau\}\_\{i\}^\{\{call\}\}\(§[5\.2](https://arxiv.org/html/2512.04013#S5.SS2)\)\. To formalize this optimization, we adopt the memory\-waste formulation introduced by INFERCEPT\(Abhyankaret al\.,[2024](https://arxiv.org/html/2512.04013#bib.bib22)\), where the waste metric captures the opportunity cost of GPU memory being occupied or reclaimed during the external call\.

![Refer to caption](https://arxiv.org/html/2512.04013v3/x15.png)Figure 10:External call duration distribution in INFERCEPT and ToolBench datasets\.For a requestii, letMMdenote the per\-token memory footprint, letL~i=Li\+l^io​u​t\\tilde\{L\}\_\{i\}=L\_\{i\}\+\\hat\{l\}\_\{i\}^\{out\}denote the estimated context length at the moment the external call is issued, whereLiL\_\{i\}is the current context length andl^io​u​t\\hat\{l\}\_\{i\}^\{out\}is the predicted number of tokens generated before the call\. We denote byτ^ic​a​l​l\\hat\{\\tau\}\_\{i\}^\{\{call\}\}the predicted duration of the external call, and byτf​w​d​\(L\)\\tau^\{\{fwd\}\}\(L\)the execution time of a forward iteration with context lengthLL\. We further denote byLo​t​h​e​rL\_\{\{other\}\}the aggregate context length of other runnable requests,τs​w​a​p​\(L\)\\tau^\{\{swap\}\}\(L\)the time to swap a context of lengthLL, andNmaxf​w​dN^\{\{fwd\}\}\_\{\\max\}the maximum number of tokens that can be swapped per forward iteration\.

#### Preserve\.

Under thePreservepolicy, the request retains its context in GPU memory throughout the external call\. The resulting memory waste equals the memory footprint multiplied by the call duration:

WasteiPreserve=τ^ic​a​l​l⋅L~i⋅M\.\\small\\text\{Waste\}^\{\\text\{Preserve\}\}\_\{i\}=\\hat\{\\tau\}^\{\{call\}\}\_\{i\}\\cdot\\tilde\{L\}\_\{i\}\\cdot M\.\(12\)

#### Discard\.

With theDiscardpolicy, the context is freed during waiting and recomputed upon resumption\. The waste arises from recomputation overhead, including both the request itself and interference with other active requests:

WasteiDiscard=τf​w​d​\(L~i\)⋅L~i⋅M\+τf​w​d​\(L~i\)⋅Lo​t​h​e​r⋅M\.\\small\\text\{Waste\}^\{\\text\{Discard\}\}\_\{i\}=\\tau^\{\{fwd\}\}\(\\tilde\{L\}\_\{i\}\)\\cdot\\tilde\{L\}\_\{i\}\\cdot M\+\\tau^\{\{fwd\}\}\(\\tilde\{L\}\_\{i\}\)\\cdot L\_\{\{other\}\}\\cdot M\.\(13\)

#### Swap\.

Under theSwappolicy, the context is temporarily swapped to secondary storage and restored upon resumption\. The waste is dominated by bidirectional swapping overhead that may stall concurrent forward execution:

WasteiSwap=2⋅τs​w​a​p​\(L~i\)⋅Nmaxf​w​d⋅M\.\\small\\text\{Waste\}^\{\\text\{Swap\}\}\_\{i\}=2\\cdot\\tau^\{\{swap\}\}\(\\tilde\{L\}\_\{i\}\)\\cdot N^\{\{fwd\}\}\_\{\\max\}\\cdot M\.\(14\)

#### Policy Selection\.

We select the context\-handling policyp^i\\hat\{p\}\_\{i\}that minimizes the expected memory waste during the external call:

p^i=arg⁡minp∈\{Preserve,Discard,Swap\}⁡Wasteip\.\\small\\hat\{p\}\_\{i\}=\\arg\\min\_\{p\\in\\\{\\texttt\{Preserve\},\\texttt\{Discard\},\\texttt\{Swap\}\\\}\}\\text\{Waste\}^\{p\}\_\{i\}\.\(15\)
While INFERCEPT utilizes these formulas within a First\-Come\-First\-Served \(FCFS\) scheduling framework,AugServeintegrates this waste\-aware selection into our state\-aware cost model\. By quantifying waiting\-phase overheads in advance, the scheduler can internalize the downstream memory impact of external calls into its value\-density computation\. This enables state\-aware prioritization that aligns immediate execution decisions with long\-term global resource efficiency\.

![Refer to caption](https://arxiv.org/html/2512.04013v3/x16.png)Figure 11:Average normalized latency \(s/token\), TTFT \(s\), goodput \(req/s\) comparison among vLLM, INFERCEPT, Speculative\-SJF scheduling, andAugServewith OPT\-13B using mixed workloads of external\-call and non\-external\-call requests on an H800 GPU\.![Refer to caption](https://arxiv.org/html/2512.04013v3/x17.png)Figure 12:Average normalized latency \(s/token\), TTFT \(s\), goodput \(req/s\) comparison among vLLM, INFERCEPT, Speculative\-SJF scheduling, andAugServewith Llama\-3\-70B\-Instruct using INFERCEPT dataset on 4 A100 GPUs\.

## Appendix CRelated Work

Memory Optimizations\.vLLM\(Kwonet al\.,[2023](https://arxiv.org/html/2512.04013#bib.bib21)\)improves GPU memory utilization with PagedAttention, allocating KV cache in fixed\-size blocks to reduce fragmentation\. INFERCEPT\(Abhyankaret al\.,[2024](https://arxiv.org/html/2512.04013#bib.bib22)\)proposes dynamic context\-handling policies for augmented LLM inference, selectively preserving, swapping, or discarding KV cache during external\-call pauses\. Sarathi\(Agrawalet al\.,[2024](https://arxiv.org/html/2512.04013#bib.bib28)\)employs chunked prefill to interleave prefill and decoding for improved resource utilization\. FlexGen\(Shenget al\.,[2023](https://arxiv.org/html/2512.04013#bib.bib33)\)and FlashGen\(Jeong and Ahn,[2025](https://arxiv.org/html/2512.04013#bib.bib30)\)further optimize KV cache management by offloading data to CPU memory or SSDs\. These techniques primarily focus on memory efficiency and serve as complementary building blocks for high\-performance LLM serving\.

Scheduling\.Recent research has explored improving request scheduling for LLM inference\. Orca\(Yuet al\.,[2022](https://arxiv.org/html/2512.04013#bib.bib27)\)leverages iteration\-level batching to increase GPU utilization, while FastServe\(Wuet al\.,[2023](https://arxiv.org/html/2512.04013#bib.bib19)\)employs input\-length–aware, token\-level preemptive scheduling to mitigate HoL blocking\. Other approaches\(Jinet al\.,[2023](https://arxiv.org/html/2512.04013#bib.bib37); Fuet al\.,[2024](https://arxiv.org/html/2512.04013#bib.bib43); Huet al\.,[2025a](https://arxiv.org/html/2512.04013#bib.bib31); Zhenget al\.,[2023](https://arxiv.org/html/2512.04013#bib.bib45); Shahoutet al\.,[2025a](https://arxiv.org/html/2512.04013#bib.bib44)\)approximate Shortest\-Job\-First \(SJF\) scheduling by predicting output lengths to reduce queuing delay\. While effective for text\-only inference, these methods do not explicitly account for the heterogeneous and multi\-stage execution behavior introduced by external calls in augmented LLM inference\. MARS\(Shahoutet al\.,[2025b](https://arxiv.org/html/2512.04013#bib.bib46)\)approximates SJF scheduling by predicting memory usage and making scheduling decisions independently at each execution round\. Requests are treated as newly arriving jobs after external calls, without explicitly incorporating realized runtime feedback from prior execution stages\. As a result, it lacks an explicit coupling across rounds to model cross\-round execution dynamics or the resumption cost induced by cumulative context growth and variability in external call returns\. In contrast,AugServeintroduces a state\-aware adaptive scheduling strategy that continuously refines scheduling priorities using runtime feedback upon external call returns\. By explicitly capturing execution state transitions and realized resumption costs,AugServecorrects predictive inaccuracies and adapts to dynamic external environments, enabling more robust scheduling and higher effective throughput in augmented LLM inference\.

## Appendix DAdditional Experimental Results

### D\.1Mixed Workloads of External\-Call and non\-External\-Call Requests

[Figure 11](https://arxiv.org/html/2512.04013#A2.F11)reports the average normalized latency, TTFT, and goodput for vLLM, INFERCEPT, SSJF, andAugServeunder mixed workloads of external\-call and non\-external\-call requests\. We construct the mixed workload from the INFERCEPT dataset by disabling external calls for 50% of the requests, while preserving the original prompts and output lengths\. All experiments are conducted using OPT\-13B on an H800 GPU\. The results show thatAugServeconsistently achieves the best performance across all metrics\. Under mixed workloads, FCFS\-based systems suffer from severe HoL blocking when external\-call requests stall execution, which propagates queuing delays to non\-external\-call requests and degrades overall responsiveness\. SSJF partially mitigates this issue by prioritizing shorter requests, but remains unaware of external\-call\-induced execution states and thus yields limited gains\. In contrast,AugServeexplicitly accounts for heterogeneous execution states across requests, effectively mitigating the blocking impact of stalled external\-call requests on fast non\-external\-call requests and maintaining high goodput under mixed workloads\.

### D\.2Llama\-3\-70B\-Instruct Results

[Figure 12](https://arxiv.org/html/2512.04013#A2.F12)compares average normalized latency, TTFT, and goodput across vLLM, INFERCEPT, SSJF scheduling, andAugServewhen serving Llama\-3\-70B\-Instruct on four A100 GPUs using the INFERCEPT dataset\. Despite the significantly larger model size and KV cache footprint,AugServeconsistently outperforms all baselines across all metrics\. FCFS\-based systems suffer from severe queuing delays under external\-call\-augmented workloads, while SSJF provides only limited improvement due to its lack of awareness of external\-call\-induced execution states and cross\-round resumption dynamics\. In contrast,AugServemaintains low TTFT and high goodput, demonstrating that its state\-aware scheduling and dynamic batch\-level adaptation remain effective under large\-model, multi\-GPU inference serving\.

Table 5:Sensitivity to the balancing parameterβ\\betaon the INFERCEPT dataset with OPT\-13B on an H800 GPU\. The default value used in the main experiments is marked with∗\.MetricReq/sβ=10−3\\beta=10^\{\-3\}β=10−4\\beta=10^\{\-4\}β=5×10−5\\beta=5\{\\times\}10^\{\-5\}∗β=10−5\\beta=10^\{\-5\}β=10−6\\beta=10^\{\-6\}Goodput \(req/s\)3\.01\.011\.121\.071\.041\.025\.00\.820\.940\.900\.940\.86P99 TTFT \(s\)3\.0276\.02109\.0598\.66111\.89278\.105\.0298\.65152\.84157\.45166\.99226\.58
### D\.3β\\betaSensitivity

We further evaluate the sensitivity ofAugServeto the balancing parameterβ\\betain[Equation 2](https://arxiv.org/html/2512.04013#S4.E2), which balances throughput progress and waiting\-time reduction in the scheduling value\. All experiments are conducted on the INFERCEPT dataset with OPT\-13B on an H800 GPU\. The default value used in the main experiments isβ=5×10−5\\beta=5\\times 10^\{\-5\}\. As shown in[Table 5](https://arxiv.org/html/2512.04013#A4.T5),AugServeis not overly sensitive to the choice ofβ\\beta\. Across different request rates, strong performance is consistently achieved within a stable range around10−510^\{\-5\}–10−410^\{\-4\}, rather than at a single sharply tuned value\. The default valueβ=5×10−5\\beta=5\\times 10^\{\-5\}falls within this stable range and achieves balanced performance across workloads\. Whenβ\\betais too large, e\.g\.,β=10−3\\beta=10^\{\-3\}, the scheduler over\-emphasizes waiting time and may prioritize long\-waiting requests at the cost of execution efficiency, leading to worse tail latency and lower goodput\. Whenβ\\betais too small, e\.g\.,β=10−6\\beta=10^\{\-6\}, the scheduler behaves closer to a throughput\-dominant greedy policy, which weakens delay awareness and can degrade tail latency\. Overall,AugServeremains effective over a relatively wide range ofβ\\betavalues and does not require fine\-grained tuning for specific workloads\.

Table 6:Average per\-iteration scheduling overhead \(s\) under different numbers of paused requests\.Paused RequestsINFERCEPTAugServe∼\\sim500\.0020\.00250–1000\.0140\.008100–1500\.0130\.016150–200–0\.025≥\\geq200–0\.021
### D\.4Scheduling Overhead with Increasing Paused Requests

In §[6\.4](https://arxiv.org/html/2512.04013#S6.SS4), we report the average per\-iteration scheduling overhead ofAugServeunder different request rates\. Here, we further examine how this overhead changes as the number of paused requests increases, which is important for augmented LLM workloads where many requests may concurrently wait for external call returns\. As shown in[Table 6](https://arxiv.org/html/2512.04013#A4.T6), the per\-iteration scheduling overhead ofAugServeincreases slightly with the number of paused requests, but remains at the millisecond level even with hundreds of paused requests\. This indicates that iteration\-level scheduling does not become a bottleneck under high concurrency\. This behavior is expected, as the scheduling procedure is mainly dominated by sorting and greedy selection over candidate requests, whose cost scales smoothly with the number of active and paused requests\. Overall,AugServemaintains stable and efficient scheduling under high concurrency\.

Table 7:Goodput \(req/s\) comparison of vLLM, INFERCEPT, Speculative\-SJF scheduling, andAugServeunder different request rates and arrival burstiness \(CV\) on INFERCEPT dataset with OPT\-13B and an H800 GPU\.Request Rate \(req/s\)CVvLLMINFERCEPTSSJFAugServe2\.010\.210\.280\.490\.851\.50\.090\.130\.520\.8220\.060\.080\.390\.783\.010\.140\.200\.501\.031\.50\.070\.110\.540\.8120\.040\.060\.230\.42
### D\.5Robustness to Bursty Arrivals

To evaluate robustness under bursty traffic, we model request arrivals using a Gamma distribution and control burstiness via the coefficient of variation \(CV\)\. We fix the average request rate and vary CV to induce different levels of load fluctuation, using the INFERCEPT dataset with OPT\-13B on an H800 GPU\.[Table 7](https://arxiv.org/html/2512.04013#A4.T7)reports goodput under different burst levels\. Across all evaluated load conditions,AugServeconsistently exhibits more stable performance than baselines\. As burstiness increases, the goodput of FCFS\-based systems degrades sharply, while SSJF offers only limited improvement due to its lack of awareness of external\-call\-induced execution states\. At 2\.0 req/s with CV = 1\.5, the goodput of vLLM and INFERCEPT drops to approximately 0\.1 req/s, whereasAugServesustains a throughput of 0\.82 req/s\. This result demonstrates thatAugServeis significantly more resilient to bursty arrivals, benefiting from its state\-aware scheduling and adaptive capacity control that mitigate burst\-induced queue buildup\.

![Refer to caption](https://arxiv.org/html/2512.04013v3/x18.png)Figure 13:Average normalized latency \(s/token\), TTFT \(s\), goodput \(req/s\) comparison among vLLM, INFERCEPT, Speculative\-SJF scheduling, MARS, andAugServewith OPT\-13B using INFERCEPT dataset on an H800 GPU\.![Refer to caption](https://arxiv.org/html/2512.04013v3/x19.png)Figure 14:Average normalized latency \(s/token\), TTFT \(s\), goodput \(req/s\) comparison among vLLM, INFERCEPT, Speculative\-SJF scheduling, MARS, andAugServewith OPT\-13B using mixed workloads of external\-call and non\-external\-call requests on an H800 GPU\.
### D\.6Comparison with Memory\-Based SJF Scheduling

We further compareAugServewith MARS, a representative memory\-based SJF scheduler for augmented LLM inference, which prioritizes requests based on estimated memory cost\. Following MARS, each service round is treated as an independent scheduling unit with static, per\-call cost estimation, without explicitly modeling cross\-round execution state\. Since MARS does not provide a prediction model for the INFERCEPT workload, we re\-implement its scheduling policy and priority formulation within our system and evaluate it under the same prediction interface as other baselines to ensure a fair comparison\. Consistent with prior observations, memory\-based SJF improves over FCFS\-style baselines under light to moderate load, reducing TTFT and normalized latency while maintaining higher goodput\. However, as load increases and requests exhibit larger cumulative context growth and higher variability in external call returns, its per\-round static cost abstraction becomes increasingly brittle, leading to degraded performance under heavy load\. In some scenarios, its performance can approach or even fall below simpler length\-based SJF heuristics\. In contrast,AugServeexplicitly models execution\-stage\-dependent state and dynamically refines scheduling decisions across service rounds, enabling more stable performance across load levels\. As shown in[Figure 13](https://arxiv.org/html/2512.04013#A4.F13)and[Figure 14](https://arxiv.org/html/2512.04013#A4.F14),AugServeachieves a geometric mean goodput of3\.07×3\.07\\timesthat of MARS across the INFERCEPT and mixed datasets, and up to4\.78×4\.78\\timeshigher under heavy load\. It also reduces TTFT by 92\.1% and normalized latency by 38\.9%, demonstrating both higher efficiency and robustness\.

![Refer to caption](https://arxiv.org/html/2512.04013v3/x20.png)\(a\)INFERCEPT dataset\.
![Refer to caption](https://arxiv.org/html/2512.04013v3/x21.png)\(b\)ToolBench dataset\.

Figure 15:P95 Time\-to\-First\-Token \(TTFT\) \(s\) comparison among vLLM, INFERCEPT, Speculative\-SJF scheduling, andAugServeon INFERCEPT and ToolBench datasets with different models and GPUs\. Lower right is better, i\.e\., shorter response time and queuing time\.![Refer to caption](https://arxiv.org/html/2512.04013v3/x22.png)\(a\)INFERCEPT dataset\.
![Refer to caption](https://arxiv.org/html/2512.04013v3/x23.png)\(b\)ToolBench dataset\.

Figure 16:P95 normalized Latency \(s/token\) comparison among vLLM, INFERCEPT, Speculative\-SJF scheduling, andAugServeon INFERCEPT and ToolBench datasets with different models and GPUs\. Lower right is better, i\.e\., sustains higher serving load\.
### D\.7Tail Latency Performance

[Figure 15](https://arxiv.org/html/2512.04013#A4.F15)and[Figure 16](https://arxiv.org/html/2512.04013#A4.F16)report the P95 TTFT and P95 normalized latency under different load levels, using the same experimental setup as in §[6\.1](https://arxiv.org/html/2512.04013#S6.SS1)\. As load increases, the tail latency of vLLM and INFERCEPT grows sharply, reflecting severe queuing delays and resource contention under high load\. SSJF provides limited improvement by prioritizing shorter requests, but still exhibits high tail latency when queuing delay is dominated by external\-call\-induced stalls\. In contrast,AugServeconsistently maintains low P95 TTFT and normalized latency across load levels, demonstrating robust tail latency control under external\-call\-augmented workloads\.

![Refer to caption](https://arxiv.org/html/2512.04013v3/x24.png)\(a\)INFERCEPT dataset\.
![Refer to caption](https://arxiv.org/html/2512.04013v3/x25.png)\(b\)ToolBench dataset\.

Figure 17:SLO attainment \(%\) with SLOs comparison among vLLM, INFERCEPT, Speculative\-SJF scheduling, andAugServeon INFERCEPT and ToolBench datasets with different models and GPUs\. Higher is better\.![Refer to caption](https://arxiv.org/html/2512.04013v3/x26.png)Figure 18:GPU/CPU cache occupation comparison among vLLM, INFERCEPT, Speculative\-SJF scheduling, andAugServewith OPT\-13B on an H800 GPU using INFERCEPT dataset\.
### D\.8SLO Attainment

To better understand the source of goodput gains, we report SLO attainment under the same experimental settings as in §[6\.1](https://arxiv.org/html/2512.04013#S6.SS1)\. SLO attainment measures the fraction of requests that satisfy latency constraints and directly determines goodput\. As shown in[Figure 17](https://arxiv.org/html/2512.04013#A4.F17),AugServeconsistently achieves higher SLO attainment than all baselines, especially under higher load levels\. In contrast, FCFS\-based systems quickly violate SLOs as queuing delays grow, while SSJF provides only limited improvement due to its lack of awareness of external\-call\-induced execution states\. These results explain the goodput improvements observed in §[6\.1](https://arxiv.org/html/2512.04013#S6.SS1), confirming thatAugServesustains higher goodput by maintaining high SLO attainment under contention\.

### D\.9Memory Occupancy

[Figure 18](https://arxiv.org/html/2512.04013#A4.F18)illustrates the GPU and CPU cache occupation across inference iterations\. SSJF maintains low GPU utilization, with cache occupancy remaining below 50% in most iterations and negligible CPU offloading\. This conservative behavior avoids memory pressure but leads to underutilized GPU resources and limited throughput\. vLLM rapidly saturates GPU memory without CPU offloading, indicating a lack of mechanisms to manage paused requests under external calls\. As a result, memory pressure accumulates on GPU, exacerbating queuing delays and HoL blocking\. INFERCEPT actively offloads KV cache to CPU to relieve GPU pressure, but its CPU cache occupation increases steadily and remains high in later iterations, reflecting frequent context swapping and significant offloading overhead\. Aggressive CPU offloading improves memory availability but introduces substantial resumption overhead, which is particularly harmful under frequent external\-call\-induced pauses\.AugServeachieves high GPU utilization while maintaining moderate and stable CPU cache occupation\. By explicitly accounting for reclaimable memory and dynamically adapting batch capacity,AugServecontrols memory pressure and avoids excessive context eviction and CPU offloading, leading to more balanced resource utilization and stable performance\.

## Appendix EApproximation Guarantee

This section analyzes the value\-density greedy policy under a simplified per\-iteration scheduling formulation\. Consider a fixed candidate setUU, fixed scheduling valuesvi\>0v\_\{i\}\>0, fixed memory costsci\>0c\_\{i\}\>0, and a fixed memory budgetBB\. The per\-iteration scheduling problem is:

max∑i∈Uvixis\.t\.∑i∈Ucixi≤B,xi∈\{0,1\}\.\\max\\sum\_\{i\\in U\}v\_\{i\}x\_\{i\}\\quad\\mathrm\{s\.t\.\}\\quad\\sum\_\{i\\in U\}c\_\{i\}x\_\{i\}\\leq B,\\quad x\_\{i\}\\in\\\{0,1\\\}\.\(16\)This is a standard 0–1 knapsack problem\. We discard infeasible singleton actions withci\>Bc\_\{i\}\>B, since each candidate action is treated as indivisible in this simplified 0–1 formulation and thus cannot appear in any feasible solution\. Letρi=vi/ci\\rho\_\{i\}=v\_\{i\}/c\_\{i\}denote the value density, and sort requests such thatρ1≥ρ2≥⋯≥ρn\\rho\_\{1\}\\geq\\rho\_\{2\}\\geq\\cdots\\geq\\rho\_\{n\}\. LetGGbe the feasible set obtained by density\-based greedy packing, which scans requests in this order and includes a request whenever it fits\. LetSSbe the best feasible singleton:

S=arg⁡maxi:ci≤B⁡vi\.S=\\arg\\max\_\{i:c\_\{i\}\\leq B\}v\_\{i\}\.\(17\)The algorithm returnsALG=max⁡\{v​\(G\),v​\(S\)\}\\mathrm\{ALG\}=\\max\\\{v\(G\),v\(S\)\\\}\.

###### Theorem E\.1\.

For the simplified per\-iteration problem in[Equation 16](https://arxiv.org/html/2512.04013#A5.E16), the algorithm that returns the better of density\-based greedy packing and the best feasible singleton achieves a1/21/2\-approximation to the optimal 0–1 knapsack solution\.

###### Proof\.

LetOPT\\mathrm\{OPT\}be the optimal integral value\. LetOPTfrac\\mathrm\{OPT\}\_\{\\mathrm\{frac\}\}be the optimal value of the fractional relaxation, where each request can be partially selected, i\.e\., the binary decisionxi∈\{0,1\}x\_\{i\}\\in\\\{0,1\\\}is relaxed toxi∈\[0,1\]x\_\{i\}\\in\[0,1\]\. Clearly,OPT≤OPTfrac\\mathrm\{OPT\}\\leq\\mathrm\{OPT\}\_\{\\mathrm\{frac\}\}\. Since requests are sorted by non\-increasing value density, the optimal fractional solution takes a density\-ordered prefix and possibly a fraction of one additional request\. That is, for some indextt, requests1,…,t−11,\\ldots,t\-1are fully selected and requestttis partially selected, with

∑i=1t−1ci≤B≤∑i=1tci\.\\sum\_\{i=1\}^\{t\-1\}c\_\{i\}\\leq B\\leq\\sum\_\{i=1\}^\{t\}c\_\{i\}\.\(18\)Therefore,

OPTfrac≤∑i=1t−1vi\+vt\.\\mathrm\{OPT\}\_\{\\mathrm\{frac\}\}\\leq\\sum\_\{i=1\}^\{t\-1\}v\_\{i\}\+v\_\{t\}\.\(19\)
By construction, the greedy packing solutionGGincludes all requests1,…,t−11,\\ldots,t\-1, because their total cost is at mostBBand the greedy algorithm scans them before requesttt\. Thus,v​\(G\)≥∑i=1t−1viv\(G\)\\geq\\sum\_\{i=1\}^\{t\-1\}v\_\{i\}\. Moreover, since requestttis feasible as a singleton after infeasible requests are removed, the best singleton satisfiesv​\(S\)≥vtv\(S\)\\geq v\_\{t\}\. Combining these bounds with[Equation 19](https://arxiv.org/html/2512.04013#A5.E19), we have

OPT≤OPTfrac≤v​\(G\)\+v​\(S\)\.\\mathrm\{OPT\}\\leq\\mathrm\{OPT\}\_\{\\mathrm\{frac\}\}\\leq v\(G\)\+v\(S\)\.\(20\)Finally,

ALG=max⁡\{v​\(G\),v​\(S\)\}≥v​\(G\)\+v​\(S\)2≥OPT2\.\\mathrm\{ALG\}=\\max\\\{v\(G\),v\(S\)\\\}\\geq\\frac\{v\(G\)\+v\(S\)\}\{2\}\\geq\\frac\{\\mathrm\{OPT\}\}\{2\}\.\(21\)Hence, the algorithm achieves a1/21/2\-approximation\. ∎

#### Discussion\.

This guarantee applies only to the simplified per\-iteration subproblem with fixed values, fixed costs, and a fixed memory budget\. It characterizes the greedy packing step in isolation and does not directly extend to the full augmented LLM scheduling problem, where costs evolve across service segments, memory usage depends on external call returns, context\-handling policies introduce heterogeneous resumption costs, and scheduling decisions are continuously refined using runtime feedback\. Extending formal approximation or competitive guarantees to the full online, multi\-stage augmented LLM serving problem remains an important direction for future work\.