Fast Inference for Augmented Large Language Models
Authors: Rana Shahout
Cong Liang
Shiji Xin
Qianru Lao
Yong Cui
Minlan Yu
Michael Mitzenmacher
Venue: NeurIPS 2025 poster ()
Keywords: LLM inference and serving
Augmented LLM requests
Primary area: applications

Abstract: Augmented Large Language Models (LLMs) enhance standalone LLMs by integrating external data sources through API calls. In interactive applications, efficient scheduling is crucial for maintaining low request completion times, directly impacting user engagement. However, these augmentations introduce new scheduling challenges: the size of augmented requests (in tokens) no longer correlates proportionally with execution time, making traditional size-based scheduling algorithms like Shortest Job First less effective. Additionally, requests may require different handling during API calls, which must be incorporated into scheduling.
This paper presents MARS, a novel inference framework that optimizes augmented LLM latency by explicitly incorporating system- and application-level considerations into scheduling. MARS introduces a predictive, memory-aware scheduling approach that integrates API handling and request prioritization to minimize completion time. We implement MARS on top of vLLM and evaluate its performance against baseline LLM inference systems, demonstrating improvements in end-to-end latency by 27%-85% and reductions in TTFT by 4%-96% compared to the existing augmented-LLM system, with even greater gains over vLLM. Our implementation is available online.

Fast Inference for Augmented Large Language Models
Rana Shahout Harvard University
Cong Liang Tsinghua University
Shiji Xin Harvard University
Qianru Lao Harvard University
Yong Cui Tsinghua University
Minlan Yu Harvard University
Michael Mitzenmacher
Harvard University
Abstract
Augmented Large Language Models (LLMs) enhance standalone LLMs by inte- grating external data sources through API calls. interactive applications, ef- ficient scheduling is crucial for maintaining low request completion times, di- rectly impacting user engagement. However, these augmentations introduce new scheduling challenges: the size of augmented requests (in tokens) no longer corre- lates proportionally with execution time, making traditional size-based scheduling algorithms like Shortest Job First less effective. Additionally, requests may require different handling during API calls, which must be incorporated into scheduling.
This paper presents MARS, a novel inference framework that optimizes augmented LLM latency by explicitly incorporating system- and application-lest levell consider- ations into scheduling. MARS introduces predictive, memory-aware scheduling approach that integrates API handling and request prioritization minimize com- pletion time. We implement MARS on top of vLLM and evaluate its performance against baseline LLM inference systems, demonstrating improvements end-to- end latency by 27%-85% and reductions in TTFT by 4%-96% compared to the existing augmented-LLM, system, with even greater gains over vLLM. Our imple- mentation is available online (code n. d.
Introduction
Recent progress in large language models (LLMs) has initiated new wave of interactive Al appli- cations. A prominent example is OpenAl's ChatGPT (OpenAl 2022). which facilitates conversa- tional interactions across various tasks. One way to extend LLM capabilities is to augment them with external tools (Mialon et 2023). resulting in what we refer to APl-augmented requests. These augmentations include arithmetic calculation (Hao et al.) 2024), ChatGPT plugins (OpenAL, 2023), image generation (Betker et al. 2023), and virtual environments (Shridhar et al. 2020). Con- sequently, AI development is increasinlyy moving towards compound Al systems (Zabaria et al., 2024) that integrate multiple interacting components, such as model calls, retrievers, and external tools, rather than relying solely on monolithic models.
APl-augmented requests present several challenges, particularly regarding memory consumption during the LLM decoding phase, which is memory-bound. Each request has associated key and value matrices that grow in size during the request. LLMS cache these matrices in key-value (KV) cache throughout the sequence generation process to enhance efficiency, eliminating the need to recompute them at every iteration. This caching significantly reduces computation time but requires substantial memory. High memory consumption during decoding can translate to higher latency
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

and lower throughput, as it limits the system's 's ability to process multiple requests concurrently. (Appendix (AnpenndiAAjjncuudes the background for LLM execution and API interactions.)
With API augmentation, memory demands can increase further based on how the system manages requests during API calls. There are three primary memory handling strategies: Preserve, which retains the KV cache in memory while awaiting the API response; Discard and Recompute, which discards the KV cache and recomputes it once the API returns; and Swap, which offloads the KV cache to CPU memory and reloads it after the API call. Each strategy has its drawbacks. Preserve leads to excessive memory usage, Discard and Recompute incurs additional computational overhead, and Swap introduces latency due to data transfers.
Existing LLM inference systems are primarily designed for standalone LLMs and struggle to main- tain low request completion times for augmented I.LMs. A key issue that can lead to delays is head-of-line (Hol.) blocking, where long-running requests, including those awaiting API responses, prevent shorter ones from being processed efficiently. Scheduling strategies can reduce Hol. by prioritizing requests. Traditional size-based scheduling prioritizes jobe with shorter execution times, which works well for standalone LLM requests where execution time correlates with out- put size (Shahout et al. 2024, Fu et al. 2024). However, in API-augmented requests, output size no longer reliably indicates total request time, as a request with a short output might involve a lengthy API call, while longer output might require minimal API interaction.
To address this challenge, we propose integrating the scheduling and memory handling of requests rather than treating L.M execution and API calls separate processes. We introduce MARS (Memory- and API- Rooted Scheduler), a novel inference framework designed to optimize aug- mented LLM latency. MARS utilizes two steps: (1) assigning handling strategy to APl-augmented requests prior to scheduling, based on predictions of output size and API call duration, and (2) scheduling requests by ranking them according to their predicted total memory, which estimates the memory footprint across a request's 's lifecycle, factoring in both request size and API interactions.
INFERCEPT (Abhyankar et al. 2024), closely related system, dynamically classifies API- augmented requests into handling strategies (preserve, discard, or recompute) only when a request reaches its API call. However, it relies on first-come, first-served (FCFS) scheduling, which may cause Hol. blocking and hinder latency guarantees. In contrast, MARS integrates handling strategy assignment with scheduling by leveraging predictive information. This allows us to schedule re- quests based on our newly proposed predicted (remaining) total memory. While it is theoretically possible to collectively optimize handling and scheduling decisions, such an approach is impractical in an online setting, Consequently, we employ a greedy algorithm that first minimizes memory usage for each individual request and then schedules requests based on their total memory requirements.
Our approach begins with a prediction model that estimates pre-API output sizes from input prompts and predicts API durations by API type, enabling us to assign each request's 's handling strategy before scheduling. We then introduce a scheduling policy that ranks requests according to their predicted total memory, thereby minimizing request completion time. We integrate optimizations into our scheduling policy to mitigate starvation and reduce scheduling overhead. Finally, we build our system top of vLLM (Kwon et al., 2023). , ofate-of-the-art LLM inference system. We evaluate MARS on three datasets, comparing MARS against baseline systems. Our results show that MARS consistently outperforms INFERCEPT and vLLM across various datasets and request rates, achieving improvements in end-to-end latency ranging from 27% to 85% and reductions in TTFT from 4% to 96%, with even greater improvements over vLLM. We also analyze the components of MARS and the effect of prediction accuracy on its performance. To ensure scalability, we designed MARS to support multi-GPU setups, which was validated through testing with Llama 70B.
2 The Challenge of Scheduling API-augmented Requests
Swapping KV cache to host memory at API calls may appear straightforward but incurs hidden costs. Even with full PCIe bandwidth, transfers bottleneck foreground tasks and block new requests. Large and fragmented contexts add overhead from multiple kernel launches. Despite pipelined swaps Abhyankar et al. (2024). bandwidth remains a limit. INFERCEPT shows swapping still
'The terms job and request used interchangeably in this paper.

---

7AP1
API
4
R
AAR
10
14
15
19
(a) FCFS
(b) SJF (request size)
AFI
K
10
12
14
15
18
19
20
19
(c) SJF (request+ API duration)
(d) Preferred
Figure 1: Comparison of scheduling policies for APl-augmented requests with memory budget of 6 units. Average completion times: (a) FCFS: 11.66 units, (b) SJF: 10.33 units, (c) SJF (size API): 11 units, (d) Optimized: 10 units.
wastes 26% of GPU resources and 25% of runtime in mixed workloads. Thus, no single handling strategy fits all requests.
Our goal is to minimize average and typical request times by scheduling requests across different handling strategies. Size-based scheduling methods, such as Shortest Job First (SJF), can reduce request completion time by utilizing known or predicted request sizes (where, in this context, size specifically refers the execution time needed to finish the job). Traditional scheduling methods, however, encounter challenges with APl-augmented requests. Indeed, it is not clear what the appro- priate notion of "size" should be with API calls for size-based scheduling: should the API delay be included or not?
Example. Consider three requests RI, R2, and R3 that all arrive time O. Each request includes one API call, triggered at different times during decode generation. Their output sizes are 6, 2, and tokens, respectively, with API durations (in token generation units) of 7, and units, respectively. The strategies to handle requests during the API for each request are Preserve for R1, Discard for R2, and Swap for R3.
In this example, we assume that only one request can run at a time and the memory budget limited to units.
The strategy for handling each request during API call was determined dynamically at runtime using the INFERCEPT equations (1,2 and 3 in (Abhyankar et al., (224))) For simplicity, assume complete information is known about the total size and API duration of each request. A request is scheduled only if there is enough memory available.
Figure T shows different scheduling policies for this example. Although all requests arrive at the same time, the FCFS scheduling policy used by INFERCEPT determines their order based on re- quest ID, processing them as R1, R2, R3, With memory budget of 6 units, the scheduler processes the pre-API part of R2 during Ri 's API call, as Rt will be discarded after one unit, freeing mem- ory to continue with Ri- In contrast, R33s pre-API part cannot run during R 's API call because it will not release memory before the API response completes, preventing R2 from resuming. This scheduling yields an average request completion time 11.66 units (Figure I(a)). The SJF policy schedules requests based only size, processing them from shortest to longest: R2, R3, Rj. At time unit 8, the API of Rg completes, leaving post-API part of size 2 (including recomputation). However, the running request, RG also has two units remaining, so Rg must wait. At time unit 9, Rj enters its API call, consuming five units of memory, leaving only unit available, which is insufficient to start the post-API part of Rg. As result, R2 must wait until R₁ finishes. This policy results in an average request completion time of 10.33 units.
These approaches fall short of optimal scheduling because they ignore the interaction between scheduling and request handling during API calls. naive strategy, referred to SJF by total size (Figure [(c)), orders requests by output size plus API duration. Again, in this example, the pre-

---

CTU
mantory
Fucniing
cashe
Ampanty
Presiitio
Scheduler
LUM
Secpped Queu
Fassed Busus
Figure 2: MARS architecture. MARS minimizes completion time for APl-augmented requests through two steps: determining request handling strategies (preserve, discard, swap) to mini- mize memory waste by predicting pre-API output size and API properties before scheduling, and implementing scheduling policy based on the handling method and request output size.
API part of R2 can run during Rí 's API call. This policy achieves an average request completion time of 11 units, worse than SJF. more effective scheduling policy (Figure I(d) integrates total size and the API handling strategy. Our intuition is that, under memory constraints, Rs, the least memory-intensive request, should run first to release memory quickly. should be followed by Rg, with Ri (the most memory memory-consuming request due to its Preserve handling) scheduled last. This approach yields an average request completion time of units, outperforming previous methods. Notably, the post-API part of Rg becomes ready at time unit 10, but due to memory constraints, it waits until R finishes.
The insight from this example informs our proposal to incorporate API handling strategies into the scheduler, ranking requests based on their total memory consumption.
MARS Design
Problem Formulation. Let R be of APT-augmented requests. Each request E R is modeled as an ordered list of tuples corresponding to its API calls. Given a limited KV memory budget, the goal is to minimize the average end-to-end latency of requests, defined the time from submission to completion, while satisfying GPU memory capacity constraints by assigning an API handling strategy per request and determining the optimal processing order.
System Overview. MARS employs two main steps to reduce LLM inference response time: (1) determining the handling strategy for requests during API calls prior to scheduling to minimize memory waste by predicting the pre-API output size and API duration, and (2) implementing a scheduling policy that considers both request size and the chosen handling strategy, ranking requests based on remaining memory consumption.
Figure illustrates the MARS architecture. Users submit requests to the request pool. MARS pre- diets APe-API output size and estimates API properties (duration and response size, Table T in Ap- pendix B based on input prompts. Using these predictions, MARS estimates total memory consump- tion, considering this in API handling decisions and scheduling policy ranking. MARS determines how to handle requests during API calls to minimize memory waste. Based on this handling method and request output size, MARS implements scheduling policy tailored for API-augmented requests. The pscudocode of the MARS scheduler is provided in Algorithm [ in Appendix
B
Step 1: Handling Strategy Assignment. Our goal is choose the API handling strategy that is
predicted to minimize memory waste before request is processed, enabling the scheduler to rank each request based on chosen handling strategy. We explain here how predict the best handling strategy for requests with API calls under single-API call assumption; extensions to multiple API calls are discussed later this section. We first predict the output size and API duration. Our approach generalizes beyond the dataset by using a predictor to estimate pre-API output size based on the prompt. Output size prediction has been studied the context L.LMs (Jin et al. 2023
Stojkovie et al. 2024 Cheng et al.) 2024
Shahout et al. 2024). For API duration, we leverage

---

15
Memory
Memory
API Call
APICaal
Time
Time
Time
(a) Preserve
(b) Discard
(c) Swap
Figure 3: Memory consumption for request over time, from arrival to completion, with one API call using handling strategies: (a) Preserve, (b) Discard and Recompute, and (c) Swap. The high- lighted area indicates the memory waste for single request.
the fact that APIs belong to fixed classes (e.g.. Math, Image), each with consistent functionality and a similar duration. By extracting the API type from the prompt, we estimate the API response size using the average size from the training set for that API class. This method relies the standardized outputs and consistent behaviors APIs within each class The handling strategy for an API call is determined by predicting memory waste, using pre-API and API duration estimates. Unlike INFERCEPT, which selects handling strategies only when a request reaches an API call, MARS predicts the handling strategy in advance, enabling the integration of strategy assignments with scheduling.
Figure 3 shows the memory consumption of request over time, from its arrival to completion. We denie total memory usage as the integral of memory consumption throughout the request's execution until completion. The shaded regions in Figures 3(a) 3(b) B(c) represent wasted memory, which is defined as the integral of memory consumption over the time period during which is not utilized for actual inference. Memory waste varies depending on the chosen strategy. In the Preserve strategy (Figure )(a),, memory remains allocated throughout the API call, causing idle memory waste during the wait time. In the Discard strategy (Figure ((b)., memory is released during the API call, reducing waste but requiring recomputation afterward. In the Swap strategy (Figure B(c)), memory is temporarily swapped out and reloaded after the API call, resulting in spike memory usage when swapping back in. We combine this waste with our estimation of the context size for batched requests according the setup. Using pre-API and API duration predictions, we estimate the wasted memory for each handling strategy based on the behavior of each strategy, as shown in Figure MARS then selects the strategy that minimizes this total waste.
Instantaneous memory measurements fail reflect how long memory resources are occupied, which is particularly important in the decoding phase of LLMs. It is not just the amount of memory request consumes at a particular moment, but also how long that memory remains in use. A strategy that uses more memory for shorter period can be more efficient than one that uses less memory but occupies it longer.
To generalize to requests with multiple APIS, we divide each request into segments, each ending with a single API call. After completing an API call, the request re-enters the system as a new request for the next API call. Each segment is classified based on the current API's characteristics. For example, a job with initial processing followed by two API calls is divided into segments, each consisting of processing phase and API call, with the final segment representing the last processing phase. We estimate the returned token size each segment based on the specific API. While this approach does not account for cumulative memory usage, predicting the total number of API calls and their resource usage is challenging, and is left for future work. This segmentation aligns with INFERCEPT, which processes multi-APl requests incrementally as they reach each API.
Multi-API.
Effeet of Mispredictions. Mispredictions are to be expected. Small mispredictions API duration or output size will typically have small effect; indeed, they may not change the overall ranking of jobs. Mispredicting short API or output as long may have large effect on that particular job,
"This approach could be further extended by incorporating predictions for API response size, which we leave for future work.

---

but does not typically harm other jobs in the system (Mitzenmacher 2021). A long-running API call incorrectly predicted as short may lead the system to select memory memory-wasteffu wasteful strategy, such as Preserve. This unnecessary memory consumption may limit the system's 's ability to process addi- tional requests. A request with a long output misclassified as short may cause head-of-line blocking and delay other requests. Importantly, better predictions would only further improve system perfor- mance by reducing these misclassification.. At the same time, using simple averages from training provides a lightweight, low-overhead predictor that we show already yields practical benefits. Im- proving prediction accuracy remains a promising future work.
Step 2: Scheduling Policy through Ranking. Once a handling strategy is assigned to each request, the second step of MARS focuses on scheduling the requests. Minimizing request completion time requires a unified scheduling method that considers both the total size of requests and their specific handling strategies during API calls. For example, may order two requests with the same total size based on the handling strategy during the API call. Or it may prioritize a request with a longer total size but a more memory- cenoory-rrienly handling strategy over a shorter request with a handling strategy that may more negatively impact system performance. Intuitively, requests should be ranked based on their memory consumption. We emphasize that without API calls, ranking based on memory consumption aligns with ranking based on execution time (or request size), as memory consumption has a linear relationship with request size. With API calls, this relationship breaks, and a request's handling strategy is selected to minimize memory consumption during the API. Consider Figure which shows the total memory; we consider the area (integral) as a rank function of a request and se- lect the function based on the predicted handling strategy during the API call. Referencing Figure among the three requests, R3 consumes the least memory and should be prioritized, followed by Re- Ri consumes the most memory due to its size, API duration, and the preserve handling strategy, so it should be scheduled last.
Starvation Prevention. Scheduling policies can cause certain requests to experience long wait times, leading to high tail latency, a form of starvation that degrades system performance and user experience. This issue arises when longer resource-intensive requests are continually deferred in favor of shorter ones, exacerbating tail latency. Our memory-focusee scheduling policy alone does not detect and mitigate starvation, which can result in extended wait times and reduced fairness. To solve this, we have implemented a starvation prevention mechanism to improve the scheduler's tail latency using per-request counter. The counter increments when a request remains in the waiting queue for a new iteration. Upon reaching a predefined threshold, MARS tags the request as starving and prioritizes it by placing at the head of the scheduled requests for the current iteration. The relative order of prioritized and non-prioritized requests is maintained according to MARS's ranking decisions. Prioritization continues until request completion, avoiding memory waste from preempted (half-finished) requests. If the request has not been prioritized and encounters API calls or scheduled, the counter resets O. Parameter experiments led us to set the predefined threshold at 100 (testing with the datasets in Section 4). Additionally, while SRPT scheduling is often considered as unfair, (Bansal and Harchol-Bain Balter (2001) shows that SRPT can achieve better faimesss compared to FCFS under many practical conditions.
Handling mixed workloads of API- and non-API requests. MARS naturally handles mixed work- loads by ranking non-API requests based on their estimated memory consumption (i.e., prompt and output size), which is equivalent to execution-ting ordering due to their near-linear relationship, consistent with existing LLM scheduling methods Fu el al. (2024); (Shaoout et al.] (2024). Ap- pendix C.2 presents evaluations on mixed workloads of API and non-API requests, showing that MARS consistently reduces mean response time compared to both INFERCEPT and vLLM.
Comparison with INFERCEPT. While MARS builds INFERCEPT's concept of measuring memory waste over time, our system is significantly different in at least three aspects: (I) Use of Predictions: MARS predicts output sizes and API durations to assign handling strategies before scheduling, efficiently integrating them into the scheduling process. In contrast, INFERCEPT dy- namically selects strategies during API calls without proactive scheduling. (2) Scheduling: MARS prioritizes requests based on predicted total memory requirements, combining scheduling with han- dling strategy, while INFERCEPT schedules the request by FCFS (3) System Optimization: MARS introduces a starvation prevention mechanism to balance efficiency and fairness.
MARS Limitation. MARS currently approximates API output size using average response length. However, actual API responses can be highly variable. In future work, MARS could incorporate

---

Vean anerg
5
100
100
31.01 Tectooch
V1.81 kelteam
MUT
Datkeet
Danaase
Datsine
GPT-J
(b) GPT-J 6B (c) Vicuna 13B
Vicuna 13B
(e) Llama 70B
Llama 70B
vanilla
INFERCEPT
Figure 4: End-to-end performance (mean and P99 of latency and TTFT) of single-API, multi-API, ToolBench datasets with request arrival rate fixed to five when serving GPT-J 6B and Vicuna 13B.
more accurate response-size predictors. An additional possibility, if API responses are highly vari- able, is to first do a 1-bit prediction to determine if the output size short or long. The survey in Mitzenmacher and Shahout (2025) details this approach.
4 Evaluation
Our primary evaluation metrics are end-to-end latency (the time from when request is submitted to the system until its completion) and datasets and four model sizes, comparing MARS's performance against INFERCEPT (Abhyankar et al.] (024) and vanilla vLLM (Kwon et al.) 2023). In addition, we provide a breakdown of MARS's components evaluate the contribution of each. Our experiments also evaluate the impact of pre- diction noise (simulated mispredictions), measure prediction accuracy, overhead, and test different starvation thresholds. MARS implemented top of vLLM, using the OPT-125M model (Zhang et al. 2022) for predictions. Implementation details are provided in Appendix C.1
(TTFT) (both mean and P99) across three
LLM models. We four models with different sizes: the TinyLlama-vL.J model with 1.IB (results in appendix C.3 the 6B-parameter GPT-J model (GPT-J 6B), the 13B- 3BB-parameter Vicuna model (Vicuna 13B) and Meta-Llama-3-70B (Llama 70B).
Testbed. We used a machine with dual AMD EPYC 7313 CPUs (16 cores each, 64 threads total), 503 GB RAM, and two NVIDIA A100 GPUs (80 GB each) connected via NVLink. For GPT-J 6B and Vicuna 13B, GPU memory usage was capped at 40 GB to match INFERCEPT's setup. Llama 70B was served using vLLM's default tensor parallelism (set to 2) across the two GPUs.
Datasets. We evaluate our system using three datasets. The first two, based on INFERCEPT. The single-API dataset is a subset containing only single API, while the multi-API dataset is the full INFERCEPT dataset. The third dataset, ToolBench (Qin et al. (2023), instruction-tuninn ceanetiion-ninnggggg dataset for tool-use tasks, featuring over 16,000 real-world APIs across 49 categories. We use it to predict output size, API duration, and response size.
End-to-end Performance. Figure illustrates how MARS consistently achieves lower latency and TTFT across all datasets at request rate of 5, highlighting its advantage over vLLM and IN- FERCEPT. At this rate, using different model sizes, MARS demonstrates improvements across the datasets. Figure 5 shows how varying the request arrival rate affects the mean and P99 of end-to- end latency and TIFT across the three datasets using GPT-J 6B and Vicuna 13B, while Ilaaa 70B results appear in Appendix C MARS consistently outperforms vLLM and INFERCEPT in mean TTFT and end-to-end latency across all tested datasets for both GPT-J 6B and Vicuna 13B. At lower request rates (c.g., 3) on the single-API dataset, MARS reduces mean TTFT by around 4-5% com- pared to INFERCEPT and 18 23% compared to vLLM, while showing mean end-to-end latency improvements of up to 1% over INFERCEPT and 15% over vLLMM the arrival rate increases (e.g.,4 or 5), these gains become more pronounced: MARS achieves TTFT reductions of over 90% and latency improvements of up to 80-90% compared to both baselines. On the multi-APl dataset, similarly reduces TTFT by more than 89% and end-to-end latency by up to 78%. For the ToolBench dataset, MARS yields TTFT improvements of 75-99% and latency gains of over 60% compared to INFERCEPT and vL..M at a request rate of 3.

---

GPT-J 6B
Vicuna 13B
Single
12t Leieres
Ede Lanneyy
3
400
13 34
720
T1PT
200
200
520
TIPT
Multi
20
Nean
R2 Legoo
Rasod
750
Meat
TIT 08
1000
150
200
Yean
Est Saa
P22
TIFT C2
Pean
20200
TIFT
Ezt
10
250
ToolBench
E24 Latororf
Noan
D2 Lateec
22500
400
500
202
Ext Lateero
Bisco
Soco
ITFT
1000
220
sco
Figure 5: End-to-end performance (mean and P99 latency and TTFT) as a function of request arrival rate when serving GPT-J 6B and Vicuna 13B (results using Llama 70B appear in Appendix using different datasets (single-API, multi-API, ToolBench).
Mean
P99
Mean
P99
Throu MROuRRRAA (regis)
600
Latency
EXE Lattenn]
1000
1.22
TTFT
5
5
6
5
6
Request Rata (neqls)
Request Rote (req/s)
Request Rate (ren/s)
Request Rate (reqis)
Request Rate (reqis)
(a) Mean E2E Latency (b) P99 E2E Latency
(c) Mean TTFT
(d) P99 TTFT
(e)
Throughput
INFERCEPT
MARS w/o scheduling
MARS
Figure 6: Breakdown of MARS components, using Multi-API dataset with Vicuna 13B.
Starvation thresholds. Figure 16 in Appendix compares the throughput and tail latency of MARS under various starvation prevention thresholds.
Breakdown of MARS Components. To further understand the benefits of MARS, we incrementally added its components to vLLM and compared the results with INFERCEPT. We used the Multi-API dataset because it has the highest latency among the datasets, Figure 6 shows throughput, end- to-end latency and TTFT. First, we added the predicted API handling component to vLLMM while keeping the scheduling policy FCFS (referred to as MARS w/o scheduling). With this addition, the performance was close to INFERCEPT but slightly worse. The key difference between INFERCEPT and MARS w/o scheduling is that MARS uses predicted information pre-determine API handling, while INFERCEPT makes dynamic decisions at the API call. Integrating our scheduling policy brought improvements across all metries, but API handling predictions remain crucial prerequisite for implementing the scheduler.
Effect of Mispredictions. Using the INFERCEPT dataset, we inject Gaussian errors into API du- ration and output size predictions: error ~ (N0 p m)), where p is the error parameter and m the measured value. Predictions are calculated as predicted value measured value + error By varying p. we assess how prediction inaccuracies affect MARS's performance. Figure 7(a) shows the impact of prediction errors end-to-end latency and throughput. As increases (c.g.. 5%,

---

P99
P99
E2E Latency (s)
120
Median
Throughta (reais)
TTFT (6)
Latancy
110
100
5%
10%
60%
5%
10% 60%
Request Rate (rea/s)
Request Rate (rea/s)
Prediction Error
Prediction Error
(a) Median E2E Latency
(b) Throughput
(c) P99 E2E Latency
(d) P99 TTFT
prediction
30% 50%
Figure Error injection, Multi-API dataset with GPT-J 6B.
10%, 30%, 50%), median latency rises, especially at higher request rates (8-10 req/s), indicating longer waiting times due inaccuracies. Throughput (Figure (7b) also decreases higher error rates, particularly under heavy loads. Figures [[c) 7(d) we increase error injection further under reg/sec 3. The figures show that while higher prediction error raises p99 latency and TTFT, the overall impact remains modest.
Prediction Accuracy and Overhead. Appears in Table
2 in Appendix
Memory Oceupancy, Appendix C.7 p.7peesett GPU and host memory--ocupaanee profiles over time.
5
Related Works
Several studies focus on improving inference throughput through optimized scheduling strategies.
Orca (Yu et al.) 2022 introduces iteration-level scheduling, where batch is created at the end of each model forward pass. vL.LM (Kwon et al. 2023) introduces paged attention, treating the KV cache as virtual memory mapped to non-contiguous physical GPU memory. Another line of work addresses the imbalance between the prefill and decoding stages. Sarathi (Agrawal et al. 2024) employs chunked prefill, which divides prompt tokens into smaller chunks merged with decoding requests to form batch for each iteration. Splitwise (Patel et al. (2024) separates the prefill and decoding stages across different machines to match their distinct computational demands. These techniques are complementary and can be integrated with MARS.
Different approaches have been explored design effective scheduling policies for LLMs. Fast- Serve (wu et al.) 2023) builds upon Orea by scheduling each output token individually using a Multi-Level Feedback Queue. However, this approach leads to frequent preemptions, increasing the cost of managing the KV cache memory and offloading to the CPU. AQUA Vijaya Kumar et al. (2025) addresses GPU memory contention during LLM inference by proposing memory offloading and a preemptive scheduling framework that reduces paging overheads and en- ables responsive, high-throughput inference. Prediction- based scheduling methods have been troduced to address these challenges. Trail (Shahout et al.) 2024) obtained output size predictions directly from the target LLM by feeding the embedding of its internal structures into a lightweight classifier. LTR [uu et al. 2024) learns to rank requests based their output size. Importantly, however, these previous works focus on requests without API augmentations.
6 Conclusion
We have introduced MARS (Memory- and API- Rooted Scheduler), an LLM inference framework designed explicitly for APl-augmented requests. MARS optimizes request completion time through a unified scheduling strategy that ranks requests based on their total memory consumption, inte- grated over time. Our approach enables MARS to handle varying output sizes and API interactions, with a starvation prevention mechanism to improve tail latency. Experimental results demonstrate that MARS improves end-to-end latency by 27%-85 -55% and reduces TTFT by 4%.96% compared to INFERCEPT, with even greater gains over vL..M.

---

Impact Statement. We believe that this work serves starting point for APl-augmented requests. Generally, we suggest that scheduling with API calls appears to open the door many interesting algorithmic problems. We are not aware of API calls of the form considered here being studied in the (theoretical) scheduling algorithms literature. More consideration of algorithmic bounds for problems may yield more additional practical strategies for APl-augmented requests.
Acknowledgments. Rana Shahout was supported in part NSF grants DMS-2023522 Michael Mitzenmacher was supported in part by NSF grants CCF-2101140, CNS-2107078, and DMS- 2023528..

---

References
Reyna Abhyankar, Zijian He, Vikranth Srivatsa, Hao Zhang, and Yiying Zhang. 2024. InferCept: Efficient Intercept Support for Augmented Large Language Model Inference. In Forty-first Inter- national Conference on Machine Learning.
Amey Agrawal, Nitin Kedia, Ashish Panwar, Jayashree Mohan, Nipun Kwatra, Bhargav S Gulavani, Alexey Tumanov, and Ramachandran Ramjee. 2024. Taming throughput-latency tradeoff in Ilm inference with sarathi-serve. arXiv preprint arXiv:2403.00 023310 (2024).
Ricardo Batea-Yates, Berthier Ribeiro-Neto, et al. 1999. Modern information retrieval. Vol. 463.
ACM press New York.
Nikhil Bansal and Mor Marchol-Balter. 2001. Analysis of SRPT scheduling: Investigating unfair- ness. In Proceedings of the 2001 ACM SIGMETRICS International conference Measurement and modeling of computer systems. 279-290.
James Betker, Gabriel Goh, Li Jing, Tim Brooks, Jianfeng Wang, Linjie Li, Long Ouyang, Juntang Zhuang. Joyce Lee, Yufei Guo, al. 2023. Improving image generation with better captions. Computer Science. https://cdn. openai. com/papers/dallee.. pdf 2. (2023). 8.
H. LangChain Chase. [n. d.]. LangChain. http:///gtttatb.oo/aaaaaaaaaaaaa
Lu Chen, Zhi Chen, Bowen Tan, Sishan Long, Milica Gašić, and Kai Yu. 2019. AgentGraph: Toward universal dialogue management with structured deep reinforcement learning. JEEE/ACM Transactions Audio, Speech, and Language Processing 27, 9 (2019),
Ke Cheng. Wen Hu, Zhi Wang, Peng Du, Jianguo Li, and Sheng Zhang. 2024. Enabling Efficient Batch Serving for LMaaS via Generation Length Prediction. arXiv preprint arXiv:2406.04785 (2024).
MARS code. [n.d.]. MARS implementation.
httpss//gthhub.ccm/rrssrpppppppp
codebaeee
Yichao Fu, Siqi Zhu, Runlong Su, Aurick Qiao. Ion Stoica, and Hao Zhang. 2024. Efficient LLM Scheduling by Learning to Rank. arXiv preprini arXiv:2408. 15792 (2024).
Shibo Hao, Tianyang Liu, Zhen Wang, and Zhiting Hu. 2024. Toolkengpt: Augmenting frozen lan- guage models with massive tools via tool embeddings. Advances in neural information processing systems 36 (2024).
Yunho Jin, Chun-Feng Wu, David Brooks, and Yeon Wei. 2023. $S: Increasing GPU Utiliza- tion during Generative Inference for Higher Throughput. In Thirty-seventh Conference on Neural Information Processing Systems. htttps://openrevieee
Omar Khattab, Arnav Singhvi, Paridhi Maheshwari, Zhiyuan Zhang, Keshav Santhanam, Saiful Haq. Ashutosh Sharma, Thomas T Joshi, Hanna Moazam, Heather Miller, et al. 2024. DSPy: Compiling Declarative Language Model Calls into State-of-the-Art Pipelines. In The Twelfth In- ternational Conference on Learning Representations.
Woosuk Kwon, Zhuohan Li, Siyuan Zhuang, Ying Sheng, Lianmin Zheng, Cody Hao Yu, Joseph Gonzalez, Hao Zhang. and Ion Stoica. 2023. Efficient memory management for large language model serving with pagedattention. In Proceedings of the 29th Symposium Operating Systems Principles. 61 1-666.
Grégoire Mialon, Roberto Dessi, Maria Lomeli, Christoforos Nalmpantis, Ram Pasunuru, Roberta Raileanu, Baptiste Rozière, Timo Schick, Jane Dwivedi- Yu, Asli Celikyilmaz, et al. 2023. Aug- mented language models: a survey. arXiv preprint arXiv: (2023).
Michael Mitzenmacher. 2021. Queues with Small Advice. In Proceedings of the 2021 SIAM Con- ference on Applied and Computational Discrete Algorithms (ACDA 21). 1-12.
Michael Mitzenmacher and Rana Shahout. 2025. Queueing, predictions, and Ums: Challenges and open problems. arXiv preprint arXiv:2503.07544 (2025).

---

OpenAl. 2022. Introducing ChatGPT.
OpenAl. March 2023. ChatGPT plugins. httpp://pppeaa...cooooo////aaaap
Pratyush Patel, Esha Choukse, Chaojie Zhang, Aashaka Shah, fïigo Goiri, Saeed Maleki, and Ri- cardo Bianchini. 2024. Splitwise: Efficient generative Ilm inference using phase splitting. In 2024 ACM/IEE 51 Annual International Symposium on Computer Architecture (ISCA), IEEE, 118-132.
Shishir G Patil, Tianjun Zhang. Xin Wang, and Joseph E Gonzalez. 2023. Gorilla: Large language model connected with massive apis. arXiv preprint arXiv:2305. 15334 (2023).
Yujia Qin, Shihao Liang, Yining Ye, Kunlun Zhu, Lan Yan, Yaxi Lu, Yankai Lin, Xin Cong, Xiangru Tang. Bill Qian, Sihan Zhao, Runchu Tian, Ruobing Xie, Jie Zhou, Mark Gerstein, Dahai Li, Zhiyuan Liu, and Maosong Sun. 2023. TooILLM: Facilitating Large Language Models to Master 16000+ Real-world APIs arXiv:2307.1673 [cs.Al]
Rana Shahout, Eran Malach, Chunwei Liu, Weifan Jiang. Minlan Yu, and Michael Mitzen- macher. 2024. Don't Stop Me Now: Embedding Based Scheduling for LLMs. arXiv preprint arXiv:2410.01035 (2024).
Mohit Shridhar, Xingdi Yuan, Mare- Alexandee Côté, Yonatan Bisk, Adam Trischler, and Matthew Hausknecht. 2020. Alfworld: Aligning text and embodied environments for interactive learning. arXiv preprint ar arXiv:2010.03768 (2020).
Jovan Stojkovic, Chaojie Zhang, fñigo Goiri, Josep Torrellas, and Esha Choukse. 2024. Dy- namollm: Designing IIm inference clusters for performance and energy efficiency. arXiv preprint 1xXiv:240..00744 (2024).
Abhishek Vijaya Kumar, Gianni Antichi, and Rachee Singh. 2025. Aqua: Network-Acceleran Memory Offloading for LLMs in Scale-Up GPU Domains. In Proceedings of the 30th ACM In- ternational Conference on Architectural Support for Programming Languages and Operating Sys- tems, Volume 2. 48-62.
Lei Wang, Chen Ma, Xueyang Feng, Zeyu Zhang, Hao Yang, Jingsen Zhang, Zhiyuan Chen, Jiakai Tang, Xu Chen, Yankai Lin, et 2024. survey on large language model based autonomous agents. Frontiers of Computer Science 18, 6 (2024), 186345.
Wolfram. [n. d.j. Chatgpt gets its 'wolfram com/ 21t//////////a////-/// -tw--gggtsttttteeeee
http::///rrtttggg..ooooooooo.oo. its wekts-woofrant -orr-ooooosaassssroorrreeeee
Bingyang Wu, Yinmin Zhong, Zili Zhang, Gang Huang, Xuanzhe Liu, and Xin Jin. 2023. Fast distributed inference serving for large language models. arXiv preprint arXiv:2305 2305.0220000 (2023).
Gycong-In Yu, Joo Scong Jeong, Geon-Woo Kim, Soojeong Kim, and Byung-Gon Chun. 2022. Orca: A distributed serving system for (Transformer-Baseel generative models. In 16th USENIX Symposium on Operating Systems Design and Implementation (OSDI 22). 521-538.
Matei Zaharia, Omar Khattab, Lingjiao Chen, Jared Quincy Davis, Heather Miller, Chris Potts, James Zou, Michael Carbin, Jonathan Frankle, Naveen Rao, and Ali Ghodsi. 2024. The Shift from Models to Compound AI Systems. https::/baal: berkeley. edtu/blog/0224/2//15 compound-ai-ssttens
Susan Zhang, Stephen Roller, Naman Goyal, Mikel Artetxe, Moya Chen, Shuohui Chen, Christo- pher Dewan, Mona Diab, Xian Li, Xi Victoria Lin, et al. 2022. Opt: Open pre-trained transformer language models. arXiv preprint arXiv:2205.01063 (2022).
Lianmin Zheng, Liangsheng Yin. Zhiqiang Xie, Jeff Huang, Chuyue Sun, Cody Hao Yu, Shiyi Cao, Christos Kozyrakis. Ion Stoica, Joseph E Gonzalez, et al. 2023. Efficiently programming large language models using sglang. arXiv preprint arXiv:2312.07104 (2023).

---

Appendix
Table of Contents
Background
13
Transformer Based Generative Models
Augmented L.LMs
14
A.3
Handling Requests During API
14
Scheduler
C
Evaluation
17
C.I
Implementation Details
17
Mixed workloads of API- and non-APl requests,
17
TinyL vI.1 (1.18) Results
19
Llama 70B Results
21
Starvation thresholds
22
C6 Prediction Accuracy and Overhead,
22
Memory Occupancy
22
A Background
A.1 Transformer-Basee Generative Models
At each step, Transformer model generates the probable next token based on the sequence of previously generated tokens. A model generating a sequence of length n needs to perform n itera- tions, with each token passing through several layers of self-attention and feed-forward networks.
During the i-th iteration, the model operates on all prior tokens (to, tob..,,..,t. f/-1) using self-attention mechanisms. The resulting output can be represented as:
gi K VTh
hour softmax
V
Here, is the query vector for the current token 4, while K and V are matrices containing the key and value vectors for all preceding tokens, where K, V E Rixds
A.1.1 Key-Value (KV) Cache
To reduce computational overhead, LLMs cache the key and value matrices (KV cache) during sequence generation. This approach avoids recomputing these matrices at each step, improving efficiency but leading to high memory usage, which scales with the sequence length, number of layers, and hidden dimensions. As more tokens are generated, memory demands grow, particularly for long sequences. For instance, the GPT-3 175B model requires around 2.3 GB of memory to store key-value pairs for a sequence length of 512 tokens. This high memory consumption poses challenges for efficient preemptive scheduling, especially when working with limited GPU memory.

---

A.2 Augmented LLMs
Can computer scientist win Nobel Prize?
Prefill
API call
Decode
API return
Search (Nobel Prize 2024)
Nobel Prizes don't include CS
a computer scientist can win by applying to another field
Figure 8: Illustration of an augmented-LLM request. The API fetches detailed information about the 2024 Nobel Prize.
Augmented Language Models (Mialon et al. 2023 Wang al. 2024) refer to language models that enhance their capabilities by incorporating external tools, retrieval mechanisms, or reasoning strategies overcome the limitations of traditional LLMs.. Unlike pure LLMs,, which rely solely on pre-trained parameters to generate responses, augmented LLMs can query external data sources expand their capabilities. Figure shows an example an augmented LLM request. These augmentations, which we refer to as API (Application Programming Interfaces), fall into three main categories described in (Mialon al. 2023); ; incorporating non-LLM tools during decoding (such as calculators (Wolfram nn. d. information retrieval systems (Baeza- Yates et al. 1999)), iterative self-calling of an LLM (like chatbots maintaining conversation history), and complex compositions involving multiple LLMs, models, and tools (exemplified by frameworks like LangChain (Chase) [n. d.]). DSpy (Khattab al. 2024), Gorilla (Patil et al. 2023), SGLang (Zheng al. 2023), and AgentGraph (Chen et 2019)).
LLM API time varies significantly based augmentation types, with clear distinction between short-running and long-running augmentations. Despite this variation, today's 's systems still rely on FCFS scheduling. This suggests that API handling strategies should be tailored specific augmen- tation types rather than using one-size-fits-al approach.
With API augmentation, memory demands increase further, depending how the system handles requests during API calls. Figure 9 shows the impact of including API calls: using a subset of INFERCEPT (Abhyankar
variations of the dataset-one with API calls and one without in terms of KV cache usage (%) over time when all API calls are handled using Preserve and in terms of completed requests number time using Preserve.
al. 2024), we compare
KV cache usage (%)
100
150
150
w/o API calls
#Finished Reqs
w/o API calls
#inishedd Reqs
w/o API calls
80
w/ API calls
w/ API calls
w/ API calls
100
100
60
50
50
20
5 10
20
40
80
20
80
Time (s)
Time (s)
Time (s)
(a) Preserve, KV cache usage
(b) Preserve, completed requests
(c) Discard, completed requests
Figure 9: Impact of including API calls: (a) KV cache usage (%) over time when all API calls are handled using Preserve. (b) Number of completed requests over time using Preserve, (c) Number of completed requests over time using Discard.
A.3 Handling Requests During API
Optimizing memory management during API calls involves selecting a strategy that minimizes GPU memory waste. In an augmented LLM inference system, this choice depends on two factors: the

---

duration of the API call and the length of the pre-APl output. For brief API calls, the Preserve strat- egy may be advantageous
avoiding recomputation overhead. For longer API calls, either Discard or Swap is preferable. If the pre-APl portion of the request is computationally light (short), Discard beneficial. Otherwise, Swap may more efficient despite the potential delays it introduces.
INFERCEPT addresses this optimization challenge by developing the following equations (equa- tions 1-3 in (Abhyankar et al. 2024)) that model the memory wastage associated with each handling strategy.
WastePreserve, = TiNT x C2 X M
(I)
WasteDiscard; = (C,) Cj x M + (Ci)(Ci) Cother M
(2)
WasteSwap, = x Tswap (C,) x Obatch M
(3)
Here Tik is the duration of the API call for request i, and C,, Cather- and Chutch represent the context size (in tokens) request before the API call, the context size other requests in the batch with request and the total context size of all requests in the batch, respectively. M denotes the memory consumed per token for the KV cache. Tiwa (C,) and Tswap (C.) represent the time required for model forwarding with context C, and the time swap context C, respectively. INFERCEPT dynamically selects strategy that minimizes memory waste. However, its scheduling policy remains FCFS.
B MARS Scheduler
The pscudocode of the MARS scheduler is provided in Algorithm |

---

Algorithm MARS Scheduler
1: Input: Request pool P, predictor model Predictor, waiting queue WailingQuene, running batch cunningBalchs starvation threshold SlarvalionT
2: while True do
3: for all r do
4: predictions, + Predictor(x.prompll
5: r.handling H buullnngStrrteegyyprcciiioo
6: W w'iitinguuue, put(r)
7: end for
8: for all r e PQueue U DQueue U SQueue do
9:
Alicalliiinss then
10: W wiilingQueue.pung ppttr)
end if end for
12:
13: for all r E WaitingQueue
14:
r.score +- HondlliggRonknnn(r)
15:
end for
16: W WiitingQueue <- Sort aitingQueue) by r.score
17:
running Batch t
18:
for all W WaitingQueue do
19:
if runming Batch not full then
20:
running Batch runningBalch + r. StarvationCnt +-
21:
else
23:
y.StarvationCnt + r.StarvationCnt + 24: end if
25:
end for
for all r E WWaiiingQueee do
27:
if r.StarvationCnt 2 StarvationT then
Place r at W aWaiingnQuue head
29:
r:StarvationCnt +-
30:
end if
31:
end for
32:
Remove finished requests from W Qiten
33:
Execute ConningBatel
34:
for all r E Batch do
35:
if P.clcol then
36:
r handling = Preserve then
37:
PQueuc.put(?)
38:
else r.rhandling = Discard then
39:
DQuene-putly
40:
else r.handling = Swap then
41:
SQueue.putie put(() end if end if
42:
44:
end for
end while
Table I shows API call properties (duration and number) based on their type.

---

Dataset
Type
Duration (sec)
Num
Math
(9e-5, 6e-5)
(3.75. 1.3)
QA
(0.69, 0.17)
(2.32, 1.73)
VE
(0.09, 0.014)
(28.18. 15.2)
INFERCEPT
Chatbot
(28.6. 15.6)
(4.45, 1.96)
Image
(20.03,
(6.91,
TTS
(17.24, 7.6)
(6.91, 3.93)
ToolBench
3.33)
(2.45. 1,81)
Table 1:
API durations and number for two different datasets: INFERCEPT (Abhyankar et al. 2024) and ToolBench (Qin et al. 2023). First part of this table taken from INFERCEPT (Ab- hyankar et al. 2024) (Table 1).
C Evaluation
C.1 Implementation Details
Our implementation supports multi-GPU setups, as evidenced by our evaluation with the Llama 70B model using vLLM's default tensor parallelism across two GPUs. To implement the prediction mechanism, we use the OPT- 125M language model (Zhang al. 2022). a transformer-bast developed by Meta. With 125 million parameters and support for context length of 2048 tokens, OPT-125M can effectively handle datasets with long contexts, such as the multi-APl dataset. Al- though smaller than many larger language models, OPT-125M delivers strong language generation capabilities. Our approach utilizes the embeddings generated by OPT-125M during the initial pro- cessing of input prompts. After tokenizing the input and processing it through the model's 's layers, extract the final token's 's embedding, which is then fed into a linear classifier. This classifier assigns the input of 50 bins, each representing a range of 10 tokens, and is trained using cross-entropy loss.
model
The model estimates the completion length for each prompt based on learned representations from the ToolBench dataset (Qin et al., (202)), which involves complex conversations with API interac- tions. We train the model using an 80-20 split for training and validation, classifying output lengths into bins. We apply this model specifically to the ToolBench dataset because the other dataset already includes detailed output length information, making prediction unnecessary in that case. MARS evaluated using the test portion of the ToolBench data to ensure accuracy.
C.2 Mixed workloads of API- and non-API requests.
Figure shows the mean end-to-end latency and TTFT as functions of request arrival when serving Vicuna 13B using a mixed workload of API- and non-API requests. The workload is derived from the InferCept Multi-API dataset, where 50% of the requests are set as non-API (i.e., the API call is disabled but the request is kept). The evaluation demonstrates that MARS consistently outperforms INFERCEPT and vL..M on mixed workload of requests with and without API calls.

---

Mean
Median
P99
E2E Latency (s)
E2E Latency (s)
E2E Latency (s)
400
400
1000
200
200
500
0
4
5
3
5
3
5
(a) Mcan Latency
(b) Median Latency
(c) P99 Latency
Mean
Median
P99
400
400
1000
TTFT (s)
ITFT (s)
[TFT (s)
200
200
500
0
0
0
4
5
6
3
4
5
3
5
6
(d) Mean TTFT
(e) Median TTFT
P99 TTFT
vanilla vLLM
INFERCEPT
MARS
Figure 10: End-to-end performance as a function request arrival rate when serving Vicuna 13B using mixed workload of API- and non -API requests.

---

C.3 TamyL v1.1 (1.1B) Results
Mean
Median
P99
E2E Latency (s)
E2E Latency (s)
E2E Latency (s)
200
750
200
100
500
100
4
5
3
5
(a) Mean Latency
(b) Median Latency
(c) P99 Latency
Mean
Median
P99
100
ITFT (s)
200
50
LE
50
EET
100
0
0
4
5
3
4
5
3
5
6
(d) Mean TTFT
(e) Median TTFT
( P99 TTFT
vanilla vLLM
INFERCEPT
MARS
Figure 11: End-to-end performance as function of request arrival rate when serving TinyLlama 1.1B using different INFERCEPT datasets.

---

Mean
Median
P99
E2E Latency (s)
7.25
E2E Latency (s)
3.0
EZE Latency (9)
111.0
7.00
10.5
2.5
6.75
10.0
4
5
3
5
3
5
(a) Mcan Latency
(b) Median Latency
(c) P99 Latency
Mean
Median
P99
0.10
0.6
0.04
TIFT (s)
ITFT (s)
0.4
ITFT
0.05
0.2
0.02
3
4
5
6
3
4
5
3
5
6
(d) Mean TTFT
(e) Median TTFT
P99 TIFT
vanilla vLLM
INFERCEPT
MARS
Figure 12: End-to-end performance as a function of request arrival rate when serving TinyLlama
1.1B using different Toolbench dataset.
Figure II and 12 compare MARS. INFERCEPT, and vLLM using the small TinyLlama v1.1 model with I.T billion parameters. Specifically, they report mean, median, and P99 end-to-end latency and TTFT as functions of request arrival rate, using the INFERCEPT and ToolBench datasets, re- spectively. The results show that MARS consistently improves both end-to-end latency and TTFT over vLLM and INFERCEPT.

---

C.4 Liama 70B Results
Mean
Mean
E2E Latency (s)
750
500
500
TTFF
250
3
4
5
6
3
4
5
6
(a) SingleAPI
(b) SinglcAPI
Mean
Mean
E2E Latency (s)
750
LIFT (s)
400
500
200
250
3
5
3
(c) MultiAPI
(d) MultiAPI
Mean
Mean
E2E Latency (s)
750
ITFT (s)
500
500
250
0
3
4
5
3
4
5
(c) ToolBench
(f) ToolBench
vanilla vLLM
INFERCEPT
MARS
Figure 13: End-to-end performance as a function of request arrival rate when serving Llama 70B
using different datasets (single-API, multi-API, ToolBench).
Figure 13 illustrates the mean end-to-end latency and TTFT as functions of request arrival rate across three datasets: Single API, MultiApi, and ToolBench, when serving Llama 70B. The results demonstrate that MARS achieves improvements in both end-to-end latency and TTFT compared to vLLM and INFERCEPT.

---

C.5
Starvation thresholds
Throughput (req/s)
P99
E2E Latency (s)
2
1000
1
500
0
0
3
4
5
6
3
4
5
Request Rate (req/s)
Request Rate (req/s)
(a) Throughput
(b) P99 E2E Latency
10
100
1,000
10,000
off
Figure 16: Starvation threshold, Multi-APl dataset with GPT-J 6B.
Figure 16 compares the throughput and tail latency MARS under various starvation prevention thresholds. We observe that introducing starvation prevention threshold reduces tail latency and enhances throughput, with a threshold of 100 providing good balance between both metrics.
C.6
Prediction Accuracy and Overhead.
Bin num
7
8
9
10
Acc-5
0.0
0.75
0.834
0.813
0.713
0.769
0.568
0.5
0.321
0.333
0.3
Acc-15
0.0
0.75
0.921
0.933
0.867
0.851
0.691
0.545
0.321
0.462
0.3
Table 2: Bin accuracy for top 10 bins.
We evaluated the precision of our response length predictions using the ToolBench dataset by mea- suring the absolute difference between the predicted and actual word lengths (which is part of the dataset). Table shows the results.
We used two accuracy metrics, Acc-5 and Acc-15 that represent the percentage of predictions that differ from the actual length by no more than words and 15 words, respectively. The results show 68.5% accuracy for Acc-5 and 78.3% accuracy for Acc-15, with Mean Absolute Error (MAE) of 3.06. When focusing on the first 20 bins (responses up to 200 words), the MAE improves to 1.366, indicating higher accuracy for shorter responses. We used an NVIDIA A100 GPU for inference, achieving an average prediction time of 13.7 ms per input on the ToolBench dataset. Table shows Acc-5 and Acc-15 per bin for the first ten bins.
C.7 Memory Occupancy
Figure 17 GPU and host memory occupancy by replaying mixed API workload the Vicuna 6B model using the multi-API INFERCEPT dataset. We record the amount of KV cache resident on the GPU and any swapped-out context held in host memory.

---

varia VILM ops 14, GFT: 68
van la VILM aps (IT) 4B
variis vLLM qe 5.0, GPT) (B
100
GPU Cocle Occupacion 180
6b
100
GPU Cache Ocoupstion (e)
100-
GPU Cache occupatin 1867
80
CPU Cachs Ocoupation 196)
Lateryy (necombel
Carhe Donuoation (5))
64
CFU Cache Occupat on (50
Sccomdes
(86)
BD
CIU Cache Ocoupation (S)
60
54
-0
40
60
Z0
20
Laterey
100
155
200
160
250
50
200
vLLM, gps 3
(b) vLLM, qps
vLLM, qps
InferCest, ass G.T. 66
InforCopt. qps 4.0. GPT
InferCost: 5.0..0 GPT) 68
100
Cache Occupation (9))
120
CPU Cathe Oraupation
60
100
Cache occupation (6)
80
Carbe Dccupatión 180
E2R Lewvery becommae
Car orruueeeam
80
Cachte Oecupal
Coche Occuparonn
Ceche Orrupetion (s)
60
60
30
60
20
(oecandlu)
(seconds)
Time (uecondi))
(d) INFERCEPT, ops 3
(e) INFERCEPT, qps
(l) INFERCEPT, qps
MARS, gos 30, GPT1
MARS, aps GPF/
MARS, aps 5.0 GPTI 68
100
Occupacion
Gcopptiinn
100-
Cacha Ocoupatio 16)
80
Ocoupation (5))
Laberryy (swernah))
Chette Desupation 193)
Gccupat
Cache Oeoupation Osl
8 18 Eit Latenay (4NONELL
10
(atenry By
Mean E2E Laberiy
Labency By
200
100
230
Time (acconda)
Time Isacands)
Time (seconds))
MARS, qps 33 3
(h) MARS, qps
(i) MARS, 9ps = 5
Figure 17: GPU/CPU cache occupation and mean end-to-end latency over time on the Vicuna 6B model using the multi-API INFERCEPT dataset.

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The claims justified by MARS discussion in Section 3 and experiments in Section 4 and Appendix C
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We discuss our approach limitations in the last paragraph of Section
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specificatton, asymptotic approximations only holding locally). The au- thors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, c.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low images taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to ad- dress problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't i acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [NA]

---

Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theo- rems.
The proof' can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: Section and Appendix C.I detail the LLM models, testbed configuration,
datasets, and evaluation metrics used.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is a dataset and/or model, the authors should describe the steps taken make their results reproducible verifiable.
Depending on the contribution, reproducibility can accomplished in various ways. For example, if the contribution is novel architecture, describing the architecture fully might suffice, or the contribution is a specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, or provide access to the model. In general. releasing code and data also be provided via
often one good way accomplish this, but reproducibility detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of model checkpoint, other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) If the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g.. a large language model), then there should either be way to access this model for reproducing the results or a way to re- produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case au- thors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models. it may be that access to the model is limited in some way (e.g., to registered users), but it should possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code

---

Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: Our implementation is available online (code) [n. d.I) including instructions
in readme file. We have also included benchmark scripts to reproduce the results.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co cc/
Sobllic/guids/Ceee https//ooeooooosssoooooiiieeeiie
for more details.
While we encourage the release code and data, we understand that this might not be possible, so "No" is acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed reproduce the results. See the NeurlPS code and data submission guidelines (https:
//nips.ccppubll
gwwdee/idd/eee https//CooSSuuiiseeeeeeee ssi onsoiicyy for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: In Section Appendix and in Figure captions.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer: [No]
The paper does not report error bars because we calculating the response time in a system in equilibrium (stcady-state), and the reported data points represent the average, median, and P99 behavior of the system in this steady-state condition. (We note that, because the large size of the used datasets, results are concentrated and errors would be very small. We can add error bars if desired for simulated data in the next version, given more time.)
Justification:
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report I-sigma error bars, but one should state it. The authors should prefer- ably report 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: In Section
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No. they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (c.g., there is a special consid- eration due to laws regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer:
[Ys]]
Justification:
We include "Impact Statement" in Section
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.

---

Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper deseribe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by re- quiring that users adhere to usage guidelines restrictions access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: In Section and Appendix C.I
Guidelines:
The answer NA means that the paper does not use existing assets. The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g.. CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
license, copyright information, and terms of use the pack- age should be provided. For popular datasets, wwwppaapp thhoode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the li- cense of dataset.
If assets are released,

---

For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Answer: [Yes]
Justification: Our system implementation is available online (code instructions provided in the README file.
nn. d.
with detailed
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects Question:
For crowdsourcing experiments and research with human subjects, does the pa- per include the full text instructions given participants and sereenshots, applicable, well as details about compensation (if any)?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code Ethics, workers involved in data collection, cura- tion, or other labor should be paid at least the minimum wage in the country of the data collector.
Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research conducted, IRB approval (or equiva-
lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.

---

For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification:
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original,
non non standaad components.
Please refer to our LLM policy hbtp:s///eeriipp.cc//oeereeeeeep for what should or should not be described.


Reviews:
[{"review_id": "hfXlZV4V4z", "reviewer": "Reviewer_VwsY", "summary": "The paper introduces MARS, an inference framework designed to optimize completion latency for API-augmented large language model requests by introducing a predictive, memory-aware scheduling approach.\n\nMARS first predicts each request’s pre-API output size and API call duration to select one of three handling strategies (Preserve, Discard & Recompute, Swap) that minimizes memory waste. It then ranks requests by their predicted cumulative memory footprint and schedules them accordingly.\n\nImplemented on top of vLLM, MARS demonstrate 27–85% end-to-end latency reductions and 4–96% TTFT improvements compared to the existing system, INFERCEPT.", "questions": "See the Strengths & Weaknesses section.", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "## Strengths\n\n- The proposed approach is technically sound. It is reasonable to estimate each request’s cost with the API call duration considered. It is intuitive that predicting the cost in advance will be helpful for request scheduling.\n    \n- Extensive evaluation across diverse models, datasets, and request rates is conducted, showing substantial performance gains.\n    \n- Open-source implementation on vLLM ensures reproducibility and real-world applicability.\n    \n\n## Weaknesses\n\n- Missing critical technical descriptions. While the big picture of the two-step pipeline (e.g., L138-L141) is clear, how each step is implemented remains obscure, making the methodology part difficult to follow\n    \n    - How are the output size and API duration? How is the handling strategy predicted, and when does it exactly happen? It is advisable to illustrate these designs with formalized descriptions and diagrams.\n        \n    - How are requests ranked, or more specifically, how is the rank index calculated? Formalized descriptions or an algorithm may make this step clearer.\n        \n- Lack of overhead analysis. Prediction and scheduling overheads and their impact on throughput are mentioned but not analyzed and deeply quantified.\n    \n    - In L312-313, critical issues are mentioned with a phrase and then abruptly point to the Appendix without any analysis, making this paper look incomplete and submitted in a hurry.", "was_revised": true, "final_justification": "The concerns I raised—particularly around the technical descriptions and overhead analysis—are suitably addressed. I believe this paper has only some minor writing issues that can be improved prior to camera-ready submission.", "rebuttal": "We thank the reviewer for the thoughtful suggestions and for recognizing the potential impact of our approach on practical applications.\n\n1. While we acknowledge the concern regarding the clarity of presentation, we emphasize that this is due to space limitations.  In particular, limited space led us to place the pseudocode in Appendix B, which may have made the methodology harder to follow. Below, we clarify the implementation details of each step.\n\n**Step 1: Handling Strategy Assignment**\n\nUpon request arrival, before scheduling or batching, we predict two quantities:\nPre‑API output length $C$: embed the entire prompt with OPT‑125M (and optionally a BERT‐based variant that we have added as part of the rebuttal), extract the final‐token embedding, and feed it into a two‐layer MLP (512 → 50 bins), trained via cross‐entropy.\nAPI duration $T_{API}$: parse the prompt for API type and look up its mean and variance of call duration and response size from Table 1.\n\nUsing these predictions, we compute the projected memory waste for each strategy via equations (Appendix A.3):\n$$Waste_{Preserve} = T_{API} \\cdot C \\cdot M$$\n$$Waste_{Discard} = T_{fwd}(C) \\cdot (C + C_{other}) \\cdot M$$\n$$Waste_{Swap} = 2 \\cdot T_{swap}(C) \\cdot C_{batch} \\cdot M$$\n\n\nWe then assign:\n$r.\\text{handling} = \\arg\\min_{s \\in \\{\\text{Preserve}, \\text{Discard}, \\text{Swap}\\}} \\text{Waste}_s$\nThis logic appears in Appendix B (Lines 149–182 and Algorithm 2–5).\n\n**Step 2: Scheduling via Ranking**\n\nAfter labeling each request with its handling strategy, we compute its rank as the area under its memory‐consumption curve:\n\n$$\\text{rank}(r) = \\int_0^{t_{\\text{end}}(r)} \\text{mem}_r(t) \\, dt$$\n\nWhere $t_{\\text{end}}(r)$ denotes the estimated time when request $r$ completes, and $\\text{mem}_r(t)$ follows the piecewise consumption curve from Fig. 3 under the chosen strategy. We schedule the lowest first. The code r.score ← HandlingRanking(r) in Algorithm 1 (App. B, line 14) references this definition.\n\n*Prediction Timing*:\n\nWe perform both output‐size and API‐duration predictions immediately upon request arrival, in the scheduler’s first loop, before any batching or memory allocation.\n\nWe aim to enhance the presentation of our work in the following ways:\n- Flowcharts illustrate each pipeline step.\n- Rank function definition in the main text.\n- A concise pseudocode in Section 3.\n- Timeline diagram showing when predictions and ranking occur.\n\nWe hope these enhancements will make our methodology more self‐contained and straightforward to follow.\n\n2 - We acknowledge the importance of minimizing scheduling and prediction overhead.\nOur approach adds two steps: computing a score based on predictions and sorting requests by this score during scheduling.\n\n*Prediction Overhead*\n\nWe use the OPT‑125M model (125 M parameters) to predict output length. On the ToolBench dataset with multiple API, this prediction takes on average 13.7 ms per request, as reported in Appendix C.6 (with a single API ToolBench dataset takes 10.22ms while the BERT-based predictor takes 7.63 ms per request). To reduce overhead, we can compute predictions on the CPU in parallel with GPU execution. This avoids stalling the GPU pipeline; the prompt is transferred to the CPU upon arrival, and prediction proceeds while the GPU begins LLM inference.\n\nIn terms of FLOPs, the predictor is lightweight. For comparison, the smallest LLM we serve is GPT‑J (6 B parameters), which is over 40× larger than OPT‑125M. Even if prediction ran on the GPU, the overhead would be approximately 2% for GPT‑J, 1% for Vicuna‑13B, and 0.18% for Llama‑70B as an upper bound. We will add these numbers and descriptions to Appendix C.\n\n*Scheduling Overhead*\n\nEach incoming request receives a score via a simple arithmetic computation, followed by insertion into a sorted queue. The sorting step operates over small batch sizes (typically tens of requests) and adds negligible latency compared to the millisecond‑scale cost of model inference.\nAs a potential optimization, we could update scores only for newly arrived requests or sort every N requests, trading off a small amount of score freshness for efficiency. \n\n*Starvation Prevention*\n\nTo ensure throughput and fairness, we implement a starvation counter that increments for requests stuck in the queue. Once the counter exceeds a threshold, we prioritize the request. This adds minimal overhead (one integer update per iteration). \nAs part of the rebuttal, we evaluated throughput for MARS, INFERCEPT, and vLLM using Vicuna‑13B on both the SingleAPI and MultiAPI workloads. The results show that MARS consistently achieves higher throughput across all request rates.\n\nSingleAPI result:\n\n| req/s | MARS | InferCept | vLLM |\n|-------|------|-----------|------|\n| 3.0   | 2.94 | 2.94      | 2.94 |\n| 4.0   | 3.99 | 3.78      | 3.57 |\n| 5.0   | 4.78 | 3.54      | 3.25 |\n| 6.0   | 5.29 | 3.61      | 3.09 |\n\n\nMultiAPI result:\n\n| req/s | MARS | InferCept | vLLM |\n|-------|------|-----------|------|\n| 3.0   | 1.98 | 1.40      | 0.98 |\n| 4.0   | 2.04 | 1.36      | 0.83 |\n| 5.0   | 1.74 | 1.33      | 0.69 |\n| 6.0   | 1.63 | 1.35      | 0.67 |\n\n\n\nThese clarifications and throughput evaluation, along with overhead quantification, will be added to the main text in the final version."}, {"review_id": "Pt1Q3tqlN5", "reviewer": "Reviewer_tDDi", "summary": "This paper introduces MARS, a scheduling framework tailored for API-augmented LLMs—language models that interleave generation with external tool or API calls. The key insight is that these requests break the assumptions of traditional scheduling approaches (e.g., token-length-based methods), due to their unpredictable latency and memory behavior. MARS addresses this by (1) predicting each request’s pre-API output length and API call duration, (2) dynamically selecting a memory handling strategy (Preserve, Discard, or Swap) to manage GPU memory usage, and (3) scheduling requests based on their estimated total memory footprint rather than output length. To ensure fairness, it also integrates a starvation prevention mechanism. The system is implemented atop vLLM, supports multi-GPU inference, and is evaluated on ToolBench and INFERCEPT across multiple LLMs (e.g., GPT-J, Vicuna, LLaMA-2 70B). Results show consistent improvements in latency (up to 4.2× reduction in TTFT and 85% reduction in end-to-end latency) over strong baselines like INFERCEPT and vLLM.", "questions": "1. Could the authors discuss if MARS's performance is sensitive to the choice of the prediction model? Have preliminary investigations been conducted using other lightweight models for predictions? Providing a brief discussion on this (even if no extensive results are available) would be valuable.\n\n2. Starvation Prevention Threshold Rationale: Could the authors provide a more detailed explanation or sensitivity analysis for the choice of this specific threshold (100)? For example, discussing the trade-offs observed with different thresholds (e.g., how a much lower or higher threshold impacts both tail latency and overall throughput/fairness) would strengthen the justification for this parameter.\n\n3. What should the MARS system do if an API is added or removed?", "limitations": "1. Multi-API Cumulative Memory: The paper explicitly states that the current multi-API approach \"does not account for cumulative memory usage,\" and that \"predicting the total number of API calls and their resource usage is challenging, and is left for future work.\"\n\n2. They acknowledge that \"Improving prediction accuracy remains a promising future work,\" implying that while their simple, lightweight predictor yields benefits, it's not the ultimate solution for prediction.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\n\n1. The paper targets a timely and impactful problem—how to efficiently schedule LLM inference with external API calls, a common pattern in modern LLM-powered applications (e.g., tool use, function calling, plugin ecosystems). This makes the work immediately useful for system designers and platform engineers.\n\n2. Extensive evaluations are performed on multiple real-world benchmarks (ToolBench, INFERCEPT) and across multiple LLM backends (GPT-J, Vicuna-13B, LLaMA-2-70B), demonstrating up to 4.2× reduction in TTFT and 85% latency improvement. The ablations are meaningful and help isolate component contributions.\n\n3. The proposed MARS system is implemented atop vLLM, supports multi-GPU inference, and includes practical engineering components such as starvation prevention and per-request memory estimation. The framework is modular and extensible.\n\nWeakness:\n\n1. OPT-125M is mentioned for predictions , more specifics on how it's trained to classify into \"50 bins\" and how the \"average size from the training set for that API class\" is used for API response size estimation could be clearer. This could be elaborated in the appendix\n\n2. The experiments are not comprehensive enough, as the study didn't test models other than OPT-125M for predictions.", "was_revised": true, "final_justification": "No further question about author's paper.", "rebuttal": "Thank you for recognizing the motivation behind our work and its potential impact on practical applications, especially for system designers and platform engineers.\n We appreciate your request for additional details on our length predictor. Below, we summarize how we train the OPT‑125M model and estimate per‑API response size. Additionally, as part of the rebuttal, we introduced a BERT-based variant to demonstrate that MARS’s gains are not tied to a specific model architecture.\n\n**OPT‑125M Training Summary**\n\nWe selected OPT‑125M for its tradeoff between accuracy and overhead, and because it supports long contexts (2048 tokens), which is userful for workloads that include multiple dialogue turns and API interactions.\n\n*Dataset & Labels*.\n- For each dataset, we split 80 % for training and 20 % for testing. \n- Each example’s true completion length is binned into one of 50 equal-width bins (10 tokens each), covering output lengths in the range 0–500 tokens.\n\n*Model & LoRA Fine-Tuning.*\n- Base model: facebook/opt-125m (125 M parameters). All base weights are frozen.\n- Adapter config: LoRA is applied to the classification head with r = 32, $\\alpha = 64$, and a dropout rate of 0.1.\n- Architecture: After tokenizing each prompt (up to 2048 tokens, with left-padding), we extract the final token’s hidden vector and \npass it through a two-layer MLP (512 → 512 → 50) with ReLU and softmax.\n\n*Training*: 15 epochs using AdamW (learning rate = 3e‑4, batch size = 64) and a linear warmup over 6 % of total steps. We use cross-entropy loss and log training progress in TensorBoard. Adapters are saved every 5 epochs.\n\n*Prediction API*: At inference, our Predictor class loads the trained LoRA adapter (e.g., epoch 15), tokenizes the input prompt, and computes the predicted bin. The output prediction is interpreted as the midpoint of the predicted bin, computed as\n(predicted_bin×10)+5.\n\n*API Response Size Estimation*\nWe group examples in the training set by their API name (e.g., Math, QA, Image).\nFor each API class, we compute the mean and standard deviation of both response length (in tokens) and API duration.\nAt runtime, we use the class mean as the predicted API response size and duration. These values are summarized in Table 1, and we will include a detailed table in Appendix C.6 listing per-class statistics.\n\nThe code for this predictor is available in the prediction folder at the provided code repository link and we will add additional description about it to Appendix C based on the reviewer’s comment.\n\n**BERT‑Base Variant Results**\n\nWe replace OPT‑125M with a standard BERT‑base encoder, keeping the same MLP head and training setup. We evaluate the BERT-based predictor and compare it against OPT‑125M in terms of accuracy and inference overhead. We also evaluated MARS using both predictors on the Single-API ToolBench dataset with GPT-J 6B and Vicuna 13B LLMs. The results confirm that MARS’s performance gains are robust across different predictor architectures and LLM backends.\n\n*Prediction Model Accuracy*\n\n| Predictor | Avg. Eval. Loss | Accuracy (%) |\n| --------- | --------------- | ------------ |\n| BERT-base | 0.6492          | 86.46        |\n| OPT-125M  | 0.5614          | 88.06        |\n\nBoth models achieve strong accuracy, with OPT‑125M performing slightly better. To further generalize, we injected synthetic noise into the predictions (Figure 7), and MARS continued to outperform FCFS under a wide range of errors.\n\n*Single-API ToolBench (GPT-J 6B Model)*\n\n| Metric          | Stat  | Model     | 3.0 req/s | 4.0 req/s | 5.0 req/s | 6.0 req/s |\n| --------------- | ----- | --------- | --------- | --------- | --------- | --------- |\n| E2E Latency (s) | Mean  | OPT-125M  | 3.15      | 3.31      | 3.73      | 4.22      |\n|                 |       | BERT      | 3.40      | 3.62      | 3.90      | 4.49      |\n|                 | Median| OPT-125M  | 1.77      | 1.97      | 2.23      | 2.71      |\n|                 |       | BERT      | 1.83      | 2.04      | 2.32      | 2.90      |\n|                 | P99   | OPT-125M  | 27.68     | 25.51     | 28.35     | 28.78     |\n|                 |       | BERT      | 24.97     | 25.18     | 25.84     | 27.10     |\n| TTFT (s)        | Mean  | OPT-125M  | 0.06      | 0.10      | 0.14      | 0.24      |\n|                 |       | BERT      | 0.06      | 0.10      | 0.15      | 0.26      |\n|                 | Median| OPT-125M  | 0.03      | 0.03      | 0.04      | 0.07      |\n|                 |       | BERT      | 0.03      | 0.03      | 0.04      | 0.08      |\n|                 | P99   | OPT-125M  | 0.48      | 0.81      | 1.11      | 1.64      |\n|                 |       | BERT      | 0.55      | 0.82      | 1.22      | 1.70      |\n| Throughput      | -     | OPT-125M  | 2.96      | 4.03      | 5.02      | 6.03      |\n| (req/s)         |       | BERT      | 2.96      | 4.03      | 5.02      | 6.03      |\n\n*Single-API ToolBench (Vicuna 13B Model)*\n\n| Metric          | Stat   | Model     | 3.0 req/s | 4.0 req/s | 5.0 req/s | 6.0 req/s |\n| --------------- | ------ | --------- | --------- | --------- | --------- | --------- |\n| E2E Latency (s) | Mean   | OPT-125M  | 3.60      | 3.63      | 3.68      | 3.79      |\n|                 |        | BERT      | 3.73      | 3.73      | 3.96      | 4.09      |\n|                 | Median | OPT-125M  | 2.02      | 2.09      | 2.15      | 2.28      |\n|                 |        | BERT      | 2.01      | 2.15      | 2.22      | 2.36      |\n|                 | P99    | OPT-125M  | 28.40     | 28.26     | 28.41     | 28.44     |\n|                 |        | BERT      | 24.94     | 25.51     | 28.12     | 25.38     |\n| TTFT (s)        | Mean   | OPT-125M  | 0.05      | 0.06      | 0.06      | 0.07      |\n|                 |        | BERT      | 0.05      | 0.06      | 0.06      | 0.08      |\n|                 | Median | OPT-125M  | 0.04      | 0.05      | 0.05      | 0.05      |\n|                 |        | BERT      | 0.04      | 0.05      | 0.05      | 0.05      |\n|                 | P99    | OPT-125M  | 0.16      | 0.22      | 0.31      | 0.33      |\n|                 |        | BERT      | 0.20      | 0.24      | 0.29      | 0.38      |\n| Throughput      | -      | OPT-125M  | 2.96      | 4.03      | 5.02      | 6.03      |\n| (req/s)         |        | BERT      | 2.96      | 4.03      | 5.02      | 6.03      |\n\n\n*Prediction Overhead (Single-API Toolbench)*\n\nOPT‑125M: 10.22 ms/request (updated from 13.7 ms in the paper, which was measured on the multi-API dataset)\nBERT‑base: 7.63 ms/request\n\n**Questions:**\n1. \"Could the authors discuss if MARS's performance is sensitive to the choice of the prediction model?\"\n\nThe close performance results indicate that MARS’s scheduling benefits are not tied to OPT‑125M; any lightweight encoder with sufficient context understanding is effective. We have aimed to make our experimental analysis more general by injecting errors into the predictor (to mimic cases with larger and different errors) and have shown the results in Figure 7.\n\nWe will include these additional training details, prediction accuracy results, and the extended evaluation in Appendix C.6 of the camera-ready version.\n\n2. \"Could the authors provide a more detailed explanation or sensitivity analysis for the choice of this specific threshold (100)?\"\n\nWe appreciate the reviewer’s request for a more detailed explanation of the starvation threshold.\nWe included a sensitivity study in Figure 16 (which appears in Appendix C.5 due to lack of space) to justify our choice of a threshold value of 100. This figure compares throughput and P99 latency under several threshold settings.\n\n- No prevention (“off”): Long‐running requests never get preempted, leading to head-of-line blocking.\n- Very low threshold (10): Starvation prevention triggers too aggressively, flattening priority differences. As a result, the benefits of memory-aware scheduling are lost.\n- Very high threshold (1 000 or 10 000): Starvation prevention rarely activates, leading to high tail latency and reduced throughput under load.\n- Threshold = 100: Achieves the best trade-off: starvation prevention triggers often enough to improve tail latency but infrequently enough to retain the efficiency of memory-aware ranking.\n\nWe will expand the discussion in Appendix C.5 to make these trade-offs explicit and guide the reader in the main paper to the corresponding curves in Figure 16.\n\n\n3. \"What should the MARS system do if an API is added or removed?\"\n\nWhen an API is added to or removed from a pending request, its predicted handling strategy and rank score must be updated to reflect the new memory and API profile. As soon as the API set changes, we recompute the memory waste (Preserve/Discard/Swap) and update the rank score for that request.\nIf the request has not yet begun execution, we remove it from its current position in the waiting queue, update r.score, and re-sort the queue so that its new priority takes effect immediately.\nIf the request is already running (i.e., partway through decoding or in an API call), we let it finish under its originally selected strategy. Preempting a request mid-flight would incur additional memory or swap overhead and is unlikely to yield performance gains, especially since API set changes during execution are rare in practice. In the camera-ready version, we will include an experiment to evaluate MARS's performance when API calls are added or removed dynamically."}, {"review_id": "IC70wxS6ZL", "reviewer": "Reviewer_H8aQ", "summary": "This pager introduces MARS, a brand-new inference framework that targets at optimizing augmented LLM latency by explicitly considering system and application level in LLM scheduling. It provides a predictive and memory aware scheduling approach that integrates API handling and prioritizing requests to minimize completion time. MARS is implemented upon vllm and is evaluated against baseline LLM inference systems. It shows large end-to-end latency reduction and TTFT improvements.", "questions": "1. Why did the authors choose a decoder-based model (OPT-125M) over encoder-based models (like BERT) for the prediction task, given that encoders typically excel at classification with full context visibility?\n2. Can the authors provide detailed training specifications for the predictor, including dataset size, training epochs, loss convergence, and strategies for handling output length distribution imbalance?\n3. How does the 13.7ms prediction overhead scale with increasing request rates, and what is the break-even point where prediction benefits outweigh the computational cost?", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength:\n1. API-augmented LLMs are becoming common in practice, and this work addresses real performance issues that matter.\n2. Instead of deciding handling strategies on-the-fly like INFERCEPT, MARS predicts them upfront. This lets them optimize scheduling and memory handling together, which is clever.\n3. They test on multiple models (1.1B to 70B), different datasets, and analyze what happens when predictions are wrong. The ablation studies and memory profiling add good depth.\n\nWeakness:\n1. The paper uses OPT-125M (a decoder-based model) as the predictor but doesn't justify why this is better than encoder-based models like BERT for this prediction task. Encoders typically perform better on classification tasks since they can see the entire input context bidirectionally.\n2. Critical training information is absent - how much training data was needed, learning rate and epochs, what the training procedure looked like, convergence criteria, and how they handled the class imbalance across different output length bins.\n3. While they mention 13.7ms prediction time, there's no analysis of how this overhead affects overall system throughput or how it scales with request rates. This could be significant in high-throughput scenarios.", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for your thoughtful and supportive review. We’re glad you found our work relevant and timely, and we appreciate your recognition of our joint handling of memory and scheduling decisions, and the breadth of our evaluation across models and datasets. We also understand your concerns and appreciate your constructive feedback. Below, we address them in detail and will incorporate the discussion into the paper as part of our revision.\n\n1. \"Why did the authors choose a decoder-based model (OPT-125M) over encoder-based models (like BERT) for the prediction task, given that encoders typically excel at classification with full context visibility?\"\n\nWe thank the reviewer for the thoughtful question. MARS’s scheduling benefits are not specific to the choice of OPT‑125M; any lightweight encoder with adequate context handling suffices. In the rebuttal, we have included a BERT-based variant as an alternative predictor to support this point. We also made the analysis more general in the paper by injecting synthetic prediction errors and presenting the results in Figure 7, which show that MARS remains robust even under noisy predictions.\nWe selected OPT‑125M for its favorable trade-off between accuracy and inference overhead, and because it supports long contexts (up to 2048 tokens), which is useful for workloads involving multi-turn conversations and interleaved API calls.\nTo evaluate robustness across model choices, we trained a BERT‑base variant using the same two-layer MLP head and training setup as OPT‑125M. We include below its accuracy and overhead compared to the OPT‑125M model. We also evaluated MARS using both predictors on the Single-API ToolBench dataset with GPT-J 6B and Vicuna 13B LLMs. The results confirm that MARS’s performance gains are robust across different predictor architectures and LLM backends.\n\n*Prediction Model Accuracy*\n\n| Predictor | Avg. Eval. Loss | Accuracy (%) |\n| --------- | --------------- | ------------ |\n| BERT-base | 0.6492          | 86.46        |\n| OPT-125M  | 0.5614          | 88.06        |\n\nBoth models achieve strong accuracy, with OPT‑125M performing slightly better. To further generalize, we injected synthetic noise into the predictions (Figure 7), and MARS continued to outperform FCFS under a wide range of errors.\n\n*Single-API ToolBench (GPT-J 6B Model)*\n\n| Metric          | Stat  | Model     | 3.0 req/s | 4.0 req/s | 5.0 req/s | 6.0 req/s |\n| --------------- | ----- | --------- | --------- | --------- | --------- | --------- |\n| E2E Latency (s) | Mean  | OPT-125M  | 3.15      | 3.31      | 3.73      | 4.22      |\n|                 |       | BERT      | 3.40      | 3.62      | 3.90      | 4.49      |\n|                 | Median| OPT-125M  | 1.77      | 1.97      | 2.23      | 2.71      |\n|                 |       | BERT      | 1.83      | 2.04      | 2.32      | 2.90      |\n|                 | P99   | OPT-125M  | 27.68     | 25.51     | 28.35     | 28.78     |\n|                 |       | BERT      | 24.97     | 25.18     | 25.84     | 27.10     |\n| TTFT (s)        | Mean  | OPT-125M  | 0.06      | 0.10      | 0.14      | 0.24      |\n|                 |       | BERT      | 0.06      | 0.10      | 0.15      | 0.26      |\n|                 | Median| OPT-125M  | 0.03      | 0.03      | 0.04      | 0.07      |\n|                 |       | BERT      | 0.03      | 0.03      | 0.04      | 0.08      |\n|                 | P99   | OPT-125M  | 0.48      | 0.81      | 1.11      | 1.64      |\n|                 |       | BERT      | 0.55      | 0.82      | 1.22      | 1.70      |\n| Throughput      | -     | OPT-125M  | 2.96      | 4.03      | 5.02      | 6.03      |\n| (req/s)         |       | BERT      | 2.96      | 4.03      | 5.02      | 6.03      |\n\n*Single-API ToolBench (Vicuna 13B Model)*\n\n| Metric          | Stat   | Model     | 3.0 req/s | 4.0 req/s | 5.0 req/s | 6.0 req/s |\n| --------------- | ------ | --------- | --------- | --------- | --------- | --------- |\n| E2E Latency (s) | Mean   | OPT-125M  | 3.60      | 3.63      | 3.68      | 3.79      |\n|                 |        | BERT      | 3.73      | 3.73      | 3.96      | 4.09      |\n|                 | Median | OPT-125M  | 2.02      | 2.09      | 2.15      | 2.28      |\n|                 |        | BERT      | 2.01      | 2.15      | 2.22      | 2.36      |\n|                 | P99    | OPT-125M  | 28.40     | 28.26     | 28.41     | 28.44     |\n|                 |        | BERT      | 24.94     | 25.51     | 28.12     | 25.38     |\n| TTFT (s)        | Mean   | OPT-125M  | 0.05      | 0.06      | 0.06      | 0.07      |\n|                 |        | BERT      | 0.05      | 0.06      | 0.06      | 0.08      |\n|                 | Median | OPT-125M  | 0.04      | 0.05      | 0.05      | 0.05      |\n|                 |        | BERT      | 0.04      | 0.05      | 0.05      | 0.05      |\n|                 | P99    | OPT-125M  | 0.16      | 0.22      | 0.31      | 0.33      |\n|                 |        | BERT      | 0.20      | 0.24      | 0.29      | 0.38      |\n| Throughput      | -      | OPT-125M  | 2.96      | 4.03      | 5.02      | 6.03      |\n| (req/s)         |        | BERT      | 2.96      | 4.03      | 5.02      | 6.03      |\n\n\n*Prediction Overhead (Single-API Toolbench)*\n\nOPT‑125M: 10.22 ms/request (updated from 13.7 ms in the paper, which was measured on the multi-API dataset)\nBERT‑base: 7.63 ms/request\n\n\n2. \"Can the authors provide detailed training specifications for the predictor, including dataset size, training epochs, loss convergence, and strategies for handling output length distribution imbalance?\"\n\nWe thank the reviewer for the request for more details. Below, we summarize how we train the OPT‑125M predictor to classify into 50 output-length bins, how we estimate API response sizes, and how we extend our approach to a BERT-based predictor.\nFor each dataset used in our experiments (as listed in the main paper), we split 80% of the data for training and 20% for testing. Each example’s true completion length is discretized into one of 50 equal-width bins (10 tokens each), covering outputs up to 500 tokens.\n\nWe use OPT‑125M (125M parameters) as the base model, with all base weights frozen. A LoRA adapter is applied to the classification head, configured with rank = 32, $\\alpha = 64$, and a dropout rate of 0.1. Inputs are tokenized up to 2048 tokens (left-padded, following OPT conventions). The final token’s hidden representation is passed through a two-layer MLP (dimensions 512 → 512 → 50) with ReLU and softmax activation.\n\nTraining proceeds for 15 epochs using AdamW (learning rate 3e‑4, batch size 64), with a linear warmup over 6% of the total steps. We use cross-entropy loss, log progress to TensorBoard, and save LoRA adapter checkpoints every 5 epochs. The trained predictor achieves an average evaluation loss of 0.561 and classification accuracy of 88.1% on the ToolBench dataset.\nAt inference time, our Predictor class loads the trained adapter (e.g., epoch 15), tokenizes the prompt, and predicts the output bin. The output is interpreted as the midpoint of the predicted bin: (predicted_bin×10)+5. The implementation is available in the prediction/ folder of the released codebase, and we will include a detailed description in Appendix C of the camera-ready version.\nRegarding distribution imbalance, we found that binning into equal-width intervals over a 0–500 token range sufficiently spreads examples across bins. We did not apply oversampling or reweighting. In the camera-ready version, we will explore those, particularly for skewed datasets.\n\n3. \"How does the 13.7ms prediction overhead scale with increasing request rates, and what is the break-even point where prediction benefits outweigh the computational cost?\"\n\nOn the ToolBench with multi-API workload, our OPT‑125M predictor takes 13.7 ms per request on average (Appendix C.6), on ToolBench single API it takes 10.22 ms/request . To reduce this overhead, we can offload prediction to the CPU, without blocking GPU inference, by initiating prediction in parallel as soon as the prompt arrives. We also explore lighter alternatives such as BERT, which we added in the rebuttal, which takes  7.63 ms/request on ToolBench single API dataset. As for the break-even point in end-to-end latency, the 13.7 ms prediction cost is offset by MARS’s scheduling gains, which routinely save tens of milliseconds per request (see Figures 4–5). As long as the latency reduction exceeds 13.7 ms, which holds across all tested arrival rates, the system achieves a net benefit. We will add CPU scaling measurements and a brief discussion of this trade-off in Appendix C."}, {"review_id": "JC7h9ZGAKh", "reviewer": "Reviewer_asX2", "summary": "This paper introduces MARS, a novel scheduling framework designed for API-augmented Large Language Model (LLM) requests. Addressing the limitations of traditional scheduling algorithms in handling the additional latency and memory usage introduced by API calls, MARS integrates predictive, memory-aware scheduling with API handling and request prioritization mechanisms to minimize end-to-end latency. Implemented on top of vLLM and utilizing an OPT-125M model for output length prediction, experimental results demonstrate that MARS significantly outperforms existing systems in both end-to-end latency and Time-To-First-Token (TTFT)..", "questions": "1. The paper uses OPT-125M for predicting output length with 50 bins of 10 tokens each. What is the impact on MARS's scheduling performance if the prediction model significantly underestimates or overestimates the output length for API-augmented requests? Specifically, how does prediction error propagate through the scheduling decisions and affect the claimed 27%-85% latency improvements?\n﻿\n2. The paper mentions several relevant methods in the related work section but only provides comparisons with INFERCEPT and vLLM. Why were other state-of-the-art augmented LLM serving systems (such as those handling function calling or retrieval-augmented generation) not included in the experimental comparison? Could you provide performance comparisons with at least one other recent system that specifically addresses API-augmented LLM scheduling?", "limitations": "See weakness", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength\n1. The paper provides extensive experimental results to demonstrate the effectiveness of the proposed framework.\n2. The paper provides a detailed introduction of scheduling API-augmented requests.\n\nWeakness\n1. The prediction module uses OPT-125M, and predicts output length by extracting the final token's embedding and classifying it into 50 bins, each representing a range of 10 tokens. However, results of prediction module with other models and different granularity of bins and tokens are absent.\n2. The paper conducts comparisons between MARS and INFERCEPT as well as vLLM. It also mentions some other relevant methods in the related work section. However, it does not provide comparative results between these mentioned methods and MARS.", "was_revised": false, "final_justification": "", "rebuttal": "Thank you for the thoughtful and encouraging review. We're glad you found the introduction clear and the scheduling problem well-motivated, and we appreciate your recognition of the scope of our experimental evaluation. We also value your constructive feedback and address your concerns below. We will incorporate these clarifications into the revised version.\n\n1. \" What is the impact on MARS's scheduling performance if the prediction model significantly underestimates or overestimates the output length for API-augmented requests? ..\"\n\n\nWe thank the reviewer for the thoughtful question. MARS’s scheduling gains degrade gracefully under noisy predictions. In Figure 7, we inject Gaussian noise into both the pre‑API output‑length and API‑duration estimates (error ∼ N(0, p·m), where m is the measured value). At small noise levels, median end‑to‑end latency increases only marginally at high load, and throughput drops by only a few percent. At higher noise levels, some request rankings invert, causing occasional head‑of‑line blocking and pushing performance toward the FCFS baseline. Even so, since FCFS is the default in systems like INFERCEPT and vLLM, MARS still outperforms those baselines under realistic error. Moreover, because MARS combines both output‑length and API‑duration estimates, and only misranks when both are severely off, its end‑to‑end improvements hold across nearly all practical error regimes.\n\nThese results do not depend on the specific choice of OPT‑125M: any lightweight predictor  (e.g., BERT‑base predictor) yields similar scheduling benefits. We will add the above discussion to the paper. In addition, as part of the rebuttal, we added a BERT-based predictor and included below its accuracy and overhead compared to the OPT‑125M model. We also evaluated MARS using both predictors on the Single-API ToolBench dataset with GPT-J 6B and Vicuna 13B LLMs. The results confirm that MARS’s performance gains are robust across different predictor architectures and LLM backends.\n\n*Prediction Model Accuracy*\n\n| Predictor | Avg. Eval. Loss | Accuracy (%) |\n| --------- | --------------- | ------------ |\n| BERT-base | 0.6492          | 86.46        |\n| OPT-125M  | 0.5614          | 88.06        |\n\nBoth models achieve strong accuracy, with OPT‑125M performing slightly better. To further generalize, we injected synthetic noise into the predictions (Figure 7), and MARS continued to outperform FCFS under a wide range of errors.\n\n*Single-API ToolBench (GPT-J 6B Model)*\n\n| Metric          | Stat  | Model     | 3.0 req/s | 4.0 req/s | 5.0 req/s | 6.0 req/s |\n| --------------- | ----- | --------- | --------- | --------- | --------- | --------- |\n| E2E Latency (s) | Mean  | OPT-125M  | 3.15      | 3.31      | 3.73      | 4.22      |\n|                 |       | BERT      | 3.40      | 3.62      | 3.90      | 4.49      |\n|                 | Median| OPT-125M  | 1.77      | 1.97      | 2.23      | 2.71      |\n|                 |       | BERT      | 1.83      | 2.04      | 2.32      | 2.90      |\n|                 | P99   | OPT-125M  | 27.68     | 25.51     | 28.35     | 28.78     |\n|                 |       | BERT      | 24.97     | 25.18     | 25.84     | 27.10     |\n| TTFT (s)        | Mean  | OPT-125M  | 0.06      | 0.10      | 0.14      | 0.24      |\n|                 |       | BERT      | 0.06      | 0.10      | 0.15      | 0.26      |\n|                 | Median| OPT-125M  | 0.03      | 0.03      | 0.04      | 0.07      |\n|                 |       | BERT      | 0.03      | 0.03      | 0.04      | 0.08      |\n|                 | P99   | OPT-125M  | 0.48      | 0.81      | 1.11      | 1.64      |\n|                 |       | BERT      | 0.55      | 0.82      | 1.22      | 1.70      |\n| Throughput      | -     | OPT-125M  | 2.96      | 4.03      | 5.02      | 6.03      |\n| (req/s)         |       | BERT      | 2.96      | 4.03      | 5.02      | 6.03      |\n\n*Single-API ToolBench (Vicuna 13B Model)*\n\n| Metric          | Stat   | Model     | 3.0 req/s | 4.0 req/s | 5.0 req/s | 6.0 req/s |\n| --------------- | ------ | --------- | --------- | --------- | --------- | --------- |\n| E2E Latency (s) | Mean   | OPT-125M  | 3.60      | 3.63      | 3.68      | 3.79      |\n|                 |        | BERT      | 3.73      | 3.73      | 3.96      | 4.09      |\n|                 | Median | OPT-125M  | 2.02      | 2.09      | 2.15      | 2.28      |\n|                 |        | BERT      | 2.01      | 2.15      | 2.22      | 2.36      |\n|                 | P99    | OPT-125M  | 28.40     | 28.26     | 28.41     | 28.44     |\n|                 |        | BERT      | 24.94     | 25.51     | 28.12     | 25.38     |\n| TTFT (s)        | Mean   | OPT-125M  | 0.05      | 0.06      | 0.06      | 0.07      |\n|                 |        | BERT      | 0.05      | 0.06      | 0.06      | 0.08      |\n|                 | Median | OPT-125M  | 0.04      | 0.05      | 0.05      | 0.05      |\n|                 |        | BERT      | 0.04      | 0.05      | 0.05      | 0.05      |\n|                 | P99    | OPT-125M  | 0.16      | 0.22      | 0.31      | 0.33      |\n|                 |        | BERT      | 0.20      | 0.24      | 0.29      | 0.38      |\n| Throughput      | -      | OPT-125M  | 2.96      | 4.03      | 5.02      | 6.03      |\n| (req/s)         |        | BERT      | 2.96      | 4.03      | 5.02      | 6.03      |\n\n\n*Prediction Overhead (Single-API Toolbench)*\n\nOPT‑125M: 10.22 ms/request (updated from 13.7 ms in the paper, which was measured on the multi-API dataset)\nBERT‑base: 7.63 ms/request\n\n\n2. \"Why were other state-of-the-art augmented LLM serving systems (such as those handling function calling or retrieval-augmented generation) not included in the experimental comparison? Could you provide performance comparisons with at least one other recent system that specifically addresses API-augmented LLM scheduling?\"\n\nWe focused our experimental comparisons on INFERCEPT and vanilla vLLM because, to our knowledge, they are the only publicly available inference platforms that (a) natively support API‑augmented requests and (b) expose a pluggable scheduler for direct evaluation. Most other related systems—Trail, LTR, FastServe, DSPy, Gorilla, retrieval‑augmented frameworks, function‑calling extensions, etc., either operate at the task or pipeline level on top of an existing serving layer (often vLLM), or target pure LLM outputs without modeling in‑flight API calls. None provide an end‑to‑end service where one can swap in a custom scheduler and measure real API‑augmented latency or TTFT.\n\nSince MARS’s core contribution is an API‑aware scheduler, we compare it against INFERCEPT—which dynamically selects handling strategies but still uses FCFS—and against vanilla vLLM, the state-of-the-art LLM serving system. Because MARS builds on vLLM, any task‑level system layered atop vLLM would inherit the same latency improvements."}]

Author rebuttal:

Meta-review: This paper presents an inference framework for scheduling API-augmented LLM requests with the goal of optimizing completion time. Initial reviews were mixed, but after rebuttal and discussion, all reviewers recommended borderline accept. Reviewers agreed that the problem of scheduling API-augmented LLM requests is both timely and important, and noted the extensive results. Most concerns centered on technical details, which appear to have been satisfactorily addressed in the rebuttal. After considering the paper, reviews, and discussion, and given the significance of the problem, the AC recommends acceptance. The authors are encouraged to incorporate the rebuttal clarifications into the camera-ready version.
Decision: Accept (poster)