Paper deep dive
BALANCE: Hybrid Autoregressive-Speculative LLM Inference in Wireless Edge Networks
Guanqiao Qu, Shuo Chen, Qian Chen, Kin K. Leung, Xianhao Chen
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 93%
Last extracted: 8/8/2026, 4:26:15 AM
Summary
The paper proposes BALANCE, a hybrid inference framework for edge Large Language Models (LLMs) that simultaneously supports Autoregressive Decoding (AD) and Speculative Decoding (SD). It addresses the latency-memory trade-off by jointly optimizing user scheduling and computing resource allocation to maximize task throughput under latency and memory constraints. The problem is formulated as NP-hard, and a polynomial-time algorithm with constant approximation guarantee is developed. Experiments show BALANCE outperforms conventional AD and SD approaches.
Entities (7)
Relation Signals (7)
Task Throughput Maximization → is → NP-hard
confidence 95% · Since the problem is NP-hard, we develop a polynomial-time algorithm
BALANCE → supports → Speculative Decoding
confidence 95% · In BALANCE, an edge server hosts both an SLM and an LLM, assigns each user to AD or SD, and performs the two modes simultaneously.
BALANCE → supports → Autoregressive Decoding
confidence 95% · In BALANCE, an edge server hosts both an SLM and an LLM, assigns each user to AD or SD, and performs the two modes simultaneously.
Speculative Decoding → uses → Small Language Model
confidence 95% · Speculative decoding (SD) accelerates inference by using a small language model (SLM) to generate multiple draft tokens
Autoregressive Decoding → causes → Long Latency
confidence 90% · Autoregressive decoding (AD) generates output tokens sequentially, resulting in long latency
Speculative Decoding → causes → Extra Memory Costs
confidence 90% · Speculative decoding (SD) ... incurs extra memory costs.
BALANCE → optimizes → Task Throughput Maximization
confidence 90% · To maximize the number of served users, we formulate a task throughput maximization problem
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Edge inference is a promising paradigm to provide large language model (LLM) inference services in next-generation mobile networks. LLM inference mainly relies on two approaches: Autoregressive decoding (AD) generates output tokens sequentially, resulting in long latency; Speculative decoding (SD) accelerates inference by using a small language model (SLM) to generate multiple draft tokens for LLM verification, but incurs extra memory costs. Due to this latency-memory tradeoff, neither approach alone can efficiently serve users with heterogeneous demands under limited edge computing resources. To address this challenge, we propose a hybrid autoregressive-speculative inference (BALANCE) framework for edge LLM inference. In BALANCE, an edge server hosts both an SLM and an LLM, assigns each user to AD or SD, and performs the two modes simultaneously. To maximize the number of served users, we formulate a task throughput maximization problem to jointly determine user scheduling and computing resource allocation between AD and SD under user latency requirements and server memory constraints. Since the problem is NP-hard, we develop a polynomial-time algorithm that transforms the original problem into two sub-problems and obtains a sub-optimal solution with a constant approximation guarantee. Experiments demonstrate that BALANCE consistently outperforms conventional AD and SD and significantly improves task throughput.
Tags
Links
- Source: https://arxiv.org/abs/2608.05926v1
- Canonical: https://arxiv.org/abs/2608.05926v1
Trouble viewing inline? Open PDF directly →
Full Text
72,525 characters extracted from source content.
Expand or collapse full text
BALANCE: Hybrid Autoregressive-Speculative LLM Inference in Wireless Edge Networks †thanks: Guanqiao Qu, Qian Chen, and Xianhao Chen are with the Department of Electrical and Computer Engineering, The University of Hong Kong, Hong Kong SAR, China (e-mail: gqqu@e.hku.hk; qchen@e.hku.hk; xcheneee@hku.hk). Shuo Chen is with the Electrical and Electronic Engineering Department, Imperial College, London SW7 2BT, U.K. (e-mail: shuo.chen22@imperial.ac.uk). Kin K. Leung is with the Electrical and Electronic Engineering, and Computing Departments, Imperial College, London SW7 2BT, U.K. (e-mail: kin.leung@imperial.ac.uk). The work was supported in part by the Research Grants Council of Hong Kong under Grant 27213824, Grant 17207826, and Grant CRS HKU702/24. Kin K. Leung is supported by the EPSRC grant EP/Y037243/1. (Corresponding author: Xianhao Chen.) Guanqiao Qu, , Shuo Chen, , Qian Chen, , Kin K. Leung, , Xianhao Chen Abstract Edge inference is a promising paradigm to provide large language model (LLM) inference services in next-generation mobile networks. LLM inference mainly relies on two approaches: Autoregressive decoding (AD) generates output tokens sequentially, resulting in long latency; Speculative decoding (SD) accelerates inference by using a small language model (SLM) to generate multiple draft tokens for LLM verification, but incurs extra memory costs. Due to this latency-memory tradeoff, neither approach alone can efficiently serve users with heterogeneous demands under limited edge computing resources. To address this challenge, we propose a hybrid autoregressive-speculative inference (BALANCE) framework for edge LLM inference. In BALANCE, an edge server hosts both an SLM and an LLM, assigns each user to AD or SD, and performs the two modes simultaneously. To maximize the number of served users, we formulate a task throughput maximization problem to jointly determine user scheduling and computing resource allocation between AD and SD under user latency requirements and server memory constraints. Since the problem is NP-hard, we develop a polynomial-time algorithm that transforms the original problem into two sub-problems and obtains a sub-optimal solution with a constant approximation guarantee. Experiments demonstrate that BALANCE consistently outperforms conventional AD and SD and significantly improves task throughput. I Introduction In next-generation mobile networks, large language model (LLM) inference at the network edge is emerging as an important paradigm for delivering LLM services to users [1]. In a typical edge LLM inference system, users upload their prompts to an edge server, which performs inference using the hosted LLM and returns the generated responses [2]. By placing LLMs on edge servers closer to end users, edge LLM inference can reduce transmission latency, compared with cloud-based serving [3, 4]. As such, edge LLM inference is becoming a key enabler for real-time LLM applications [5]. Autoregressive decoding (AD) and speculative decoding (SD) are two representative approaches in LLM inference. In AD, an LLM generates the response token by token, producing one new token in each forward pass based on the input and previously generated tokens [6, 7]. However, the sequential decoding process of AD incurs high response latency [8]. This issue becomes more severe for tasks with long output responses and stringent latency requirements [8]. To reduce decoding latency, SD has been proposed [9]. In SD, a small language model (SLM) first generates multiple draft tokens via AD, and the target LLM verifies them in parallel within a single forward pass. By accepting multiple verified draft tokens at once, SD reduces the number of serial LLM forward passes. This reduction can significantly reduce response latency, since each forward pass of the SLM is typically faster than the target LLM [10]. Meanwhile, SD maintains output quality, since the verification preserves the target LLM’s output distribution [11]. When applying SD to edge LLM inference, the SLM and LLM can be co-deployed on the edge server to serve users [12]. However, despite its latency advantage, SD introduces higher memory overhead due to the coexistence of the SLM and LLM as well as the memory for parallel draft verification [13]. (a) End-to-end latency vs. output length. (b) Required GPU memory vs. output length. Figure 1: Comparison between AD and SD when serving a single user using an NVIDIA GeForce RTX 4090 GPU, where the output length varies, and the input length is fixed at 500 tokens. In this experiment, the end-to-end latency denotes the time from feeding the prompt to the model to completing output generation. Llama-2-7B is used as the LLM in both AD and SD, and TinyLlama-1.1B is used as the SLM in SD. Challenge. Neither AD nor SD alone can efficiently serve users with heterogeneous demands on resource-constrained edge servers. Serving users with AD alone is memory-efficient but may fail to satisfy stringent latency requirements, whereas relying solely on SD reduces latency but may exceed available memory resources [14, 15]. As illustrated in Fig. 1, when serving a single user, SD reduces the average end-to-end (E2E) latency by 39.1% compared with AD, but increases the GPU memory consumption by 18.3%. This latency-memory tradeoff raises a key challenge: how to efficiently serve users with heterogeneous demands by jointly exploiting AD and SD under constrained computing and memory resources on edge servers. Solution. To address the above challenge, we propose a hybrid autoregressive-speculative inference (BALANCE) framework. In BALANCE, an edge server hosts both an LLM and an SLM, enabling the simultaneous support of AD and SD for different users. To serve users with heterogeneous demands under limited computing resources, the edge server jointly selects users for service, assigns each selected user to AD or SD, and allocates computing resources between the two modes. Based on this framework, we formulate a joint user scheduling and computing resource allocation problem to maximize the number of served users in edge LLM inference while satisfying users’ E2E latency requirements and the server’s memory constraint. This problem is combinatorial because different assignments of users with heterogeneous demands between AD and SD incur different latency and memory costs, and we show that it is NP-hard. To address this problem, we further design a polynomial-time algorithm with a constant approximation guarantee. To the best of our knowledge, this is the first work to study hybrid autoregressive-speculative inference for edge LLM inference. The main contributions are as follows. 1. We propose a hybrid autoregressive-speculative inference framework where an edge server simultaneously supports AD and SD for multiple users. We formulate a joint user scheduling and computing resource allocation problem to maximize the number of served users under E2E latency requirements and resource constraints. We show that this problem is NP-hard. 2. To facilitate efficient solution finding, we decompose the original problem into AD and SD sub-problems and design a polynomial-time algorithm with a constant approximation guarantee. 3. Experimental results show that the proposed BALANCE framework significantly improves the system performance compared with conventional AD and SD. The rest of this paper is structured as follows. Section I reviews the related work. Section I proposes the BALANCE framework and formulates the task throughput maximization problem. Section IV designs the algorithm and provides the theoretical analysis. Section V provides the experiment results, and Section VI concludes the paper. I Related Work Existing edge LLM inference systems commonly adopt AD to provide services to end users. To improve system throughput, prior studies have investigated batching techniques that group users requesting the same LLM into one inference batch [16]. Moreover, user scheduling and resource allocation for multi-user edge inference systems under heterogeneous user demands and constrained server resources have also been studied [17, 18]. Some works further explore collaborative inference, where an LLM is partitioned across end devices, edge servers, and cloud servers to exploit distributed computing resources [19]. These studies provide important system and scheduling foundations for edge LLM inference under AD. To reduce response latency, SD has been introduced into edge LLM inference. Similar to AD, existing studies investigate batching, user scheduling, and resource allocation for SD-based edge inference [20, 21], as well as collaborative SD at the network edge, where the SLM and the LLM are hierarchically deployed across end devices, edge servers, and cloud servers [22]. To further improve the efficiency of SD, some techniques, such as tree-structured draft generation [23] and parallel draft generation and verification [24], have been proposed. Together, these studies advance the efficient deployment of SD in edge networks. Most existing works focus on either AD or SD alone. Although several studies have explored hybrid LLM inference, they mainly consider distributed deployment of SLMs and LLMs [25], request routing between SLMs and LLMs [26], and selective LLM involvement during SLM token generation [27]. These hybrid inference methods coordinate SLMs and LLMs rather than jointly supporting AD and SD. Moreover, some works combine different decoding techniques, such as AD for early tokens followed by parallel decoding for subsequent tokens [28] and retrieval-based draft generation within SD [29]. However, such combinations represent a new inference paradigm rather than joint coordination of AD and SD under resource constraints. Therefore, user scheduling and resource allocation for hybrid autoregressive-speculative inference remain largely unexplored in edge LLM inference. I Framework I-A Network Scenario We consider a multi-user wireless edge network with a single edge server covering a set of users K, as shown in Fig. 2. Each user k∈k generates an inference task with an E2E latency requirement TkT_k and requests the edge server to perform inference by uploading the task data to the edge server. The edge server hosts both an LLM and an SLM and simultaneously supports the AD mode, where the LLM generates output tokens autoregressively, and the SD mode, where the SLM generates draft tokens and the LLM verifies them. To serve heterogeneous user demands, the edge server selects users and schedules each selected user to AD or SD mode. To indicate the user scheduling, we define binary variables xkx_k and yky_k, where xk=1x_k=1 if and only if user k is scheduled to the AD mode, and yk=1y_k=1 if and only if user k is scheduled to the SD mode. xk=yk=0x_k=y_k=0 indicates that user k is not served. To improve task throughput, users scheduled to the same mode are batched for inference. After inference, the generated outputs are returned to the users. Figure 2: Illustration of BALANCE, where an edge server simultaneously supports the AD and SD modes for different users. The blue and orange lines denote the data flows of the SD and AD modes, respectively. I-B BALANCE Framework The procedure of BALANCE is shown in Fig. 3. Before task execution, each user uploads its input length LkIL_k^I and expected output length LkOL_k^O, measured in tokens, to the edge server through a control signal111Reporting input and expected output lengths is commonly adopted in scheduling for LLM inference [30]. LkOL_k^O can be specified by the task requirements or obtained by efficient prediction methods, such as lightweight predictors [31] and distribution-based prediction [32].. Based on the reported information, the edge server determines the user scheduling and sends the scheduling results to the users. The scheduling problem will be formulated in Section I-G. (i) After receiving the scheduling results, the scheduled users upload their input prompts. Once the prompts of users scheduled for the same inference mode are received, the server processes them in a batch using that mode. (i-a-i) In the AD mode, the prompts for AD are first prefilled by the LLM. (i-a-i) Then, the LLM generates the output tokens through multiple decoding steps. (i-s-i) In the SD mode, the prompts for SD are first prefilled by the LLM and then by the SLM. (i-s-i) Then, the SLM and LLM generate output tokens over multiple iterations. (i) Once one mode is completed, the corresponding outputs are returned to the users scheduled to that mode. Figure 3: The procedure of the proposed BALANCE framework. I-C Communication Model We consider orthogonal frequency-division multiple access for both uplink and downlink transmissions. The data uploading time of user k is Δτkup=γLkIBkRk _k^up= γ L_k^IB_kR_k, where BkB_k and RkR_k denote the uplink bandwidth and uplink spectral efficiency of user k, respectively. γ is the number of bits per token, and γLkIγ L_k^I is the bit size of user k’s input prompt tokens. Thus, the data uploading times of the AD and SD modes are given by τad,up=maxΔτkup|xk=1,τ^ad,up= \ _k^up\ |\ x_k=1 \, (1) and τsd,up=maxΔτkup|yk=1,τ^sd,up= \ _k^up\ |\ y_k=1 \, (2) respectively. The output downloading time of user k is τkdown=(xk+yk)Δτkdown. _k^down= (x_k+y_k ) _k^down. (3) Here, Δτkdown=γLkOB¯kR¯k _k^down= γ L_k^O B_k R_k, where B¯k B_k and R¯k R_k denote the downlink bandwidth and spectral efficiency of user k, respectively. I-D Computing Model We model the computing procedures and workloads using a common Transformer architecture. Following previous works [33], we focus on matrix multiplication operations in workload analysis, including query, key, and value (QKV) projections, multi-head attention (MHA) computation, output projection, and feed-forward computation using a feed-forward network (FFN), while ignoring minor contributors. I-D1 Computing procedures and workload analysis of the AD mode After all user input prompts of the AD mode arrive, the edge server starts the AD mode. These prompts are batched and prefilled by the LLM in one forward pass, which generates the first output token for each request. We define the LLM workload for prefilling a single input prompt of LIL^I tokens as ΓL,p(LI)=ML[8LIDL,mDL,hHL+4(LI)2DL,hHL+4LIDL,mDL,f] ^L,p (L^I )=M^L [8L^ID^L,mD^L,hH^L+4 (L^I )^2D^L,hH^L+4L^ID^L,mD^L,f ], where DL,mD^L,m, DL,hD^L,h, HLH^L, DL,fD^L,f, and MLM^L denote the LLM hidden dimension, the hidden dimension of an attention head, the number of attention heads, the FFN hidden dimension, and the number of layers of the LLM, respectively. The three terms inside the bracket represent the workloads of the QKV and output projections, attention computation, and feed-forward computation in each layer, respectively. Thus, the LLM prefilling workload in the AD mode is given by Wad,p=ΓL,p(Lmaxad,I)∑k∈xk, W^ad,p= ^L,p (L_ ^ad,I )Σ _k x_k, (4) where ∑k∈xkΣ _k x_k is the number of users scheduled to the AD mode, and Lmaxad,I=maxk∈LkI|xk=1L_ ^ad,I= _k \L_k^I\ |\ x_k=1 \ is the maximum input length of users scheduled to the AD mode222Following previous works [34], we consider padding for efficient GPU matrix multiplication, as supported and recommended by PyTorch [35].. After prefilling, the LLM generates one token for each unfinished user request at each decoding step. Since prefilling has generated the first token, user k requires LkO−1L_k^O-1 decoding steps for output generation. Therefore, the total number of decoding steps in the AD mode is Lmaxad,O−1L_ ^ad,O-1, where Lmaxad,O=maxkLkO|xk=1L_ ^ad,O= _k \L_k^O\ |\ x_k=1 \ (5) is the maximum output length of users in the AD mode. We define the LLM workload for generating one token at the l-th decoding step for a single input prompt of LIL^I tokens as ΓlL,a(LI)=ML[8DL,mDL,hHL+4(LI+l)DL,hHL+4DL,mDL,f] _l^L,a (L^I )=M^L [ aligned 8D^L,mD^L,hH^L+4 (L^I+l )D^L,hH^L+4D^L,mD^L,f aligned ], where the attention workload depends on the sequence length LI+lL^I+l, since the query of the current token attends to the KV cache of the previous LI+l−1L^I+l-1 tokens as well as the key and value of the current token. Thus, the LLM workload at the l-th decoding step in the AD mode is given by Wlad,a=∑k∈xkl≤LkO−1ΓlL,a(Lmaxad,I), W_l^ad,a=Σ _k x_kI_ \l≤ L_k^O-1 \ _l^L,a (L_ ^ad,I ), (6) where users with l>LkO−1l>L_k^O-1 are excluded at decoding step l. I-D2 Computing procedures and workload analysis of the SD mode After all input prompts of users scheduled to the SD mode are received, the edge server starts the SD mode. These prompts are batched, first prefilled by the LLM, and then prefilled by the SLM. Following (4), the LLM prefilling workload in the SD mode is given by Wsd,L,p=ΓL,P(Lmaxsd,I)∑k∈yk, W^sd,L,p= ^L,P (L_ ^sd,I )Σ _k y_k, (7) where ∑k∈ykΣ _k y_k is the number of users scheduled to the SD mode, and Lmaxsd,I=maxk∈LkI|yk=1L_ ^sd,I= _k \L_k^I\ |\ y_k=1 \ is the maximum input length of users scheduled to the SD mode. Additionally, following ΓL,p(LI) ^L,p (L^I ), we define the SLM workload for prefilling a single input prompt of LIL^I tokens as ΓS,p(LI)=MS[8LIDS,mDS,hHS+4(LI)2DS,hHS+4LIDS,mDS,f] ^S,p (L^I )=M^S [8L^ID^S,mD^S,hH^S+4 (L^I )^2D^S,hH^S+4L^ID^S,mD^S,f ], where DS,mD^S,m, DS,hD^S,h, HSH^S, DS,fD^S,f, and MSM^S denote the SLM hidden dimension, the hidden dimension of an attention head, the number of attention heads, the FFN hidden dimension, and the number of layers of the SLM, respectively. Thus, the SLM prefilling workload in the SD mode is expressed as Wsd,S,p=ΓS,p(Lmaxsd,I)∑k∈yk. W^sd,S,p= ^S,p (L_ ^sd,I )Σ _k y_k. (8) After prefilling, SD proceeds over multiple iterations. In each iteration, the SLM autoregressively generates draft tokens for unfinished requests, and the LLM verifies the batched draft sequences in one forward pass. After verification, the accepted draft tokens and one additional token are retained for each request, and the KV cache of rejected draft tokens is removed. The additional token is used as the input token for the next draft generation. Let AkA_k denote the expected acceptance rate that a draft token is accepted by the LLM for user k’s task. The number of accepted draft tokens for user k’s task is given by LkA=Ak[1−(Ak)LD]1−AkL_k^A= A_k [1- (A_k )^L^D ]1-A_k. User k requires Nk=⌈LkOLkA+1⌉N_k= L_k^OL_k^A+1 SD iterations, where term 1 represents the additional token. Therefore, the total number of SD iterations is denoted by Nmaxsd=maxk∈Nk|yk=1.N_ ^sd= _k \N_k\ |\ y_k=1 \. (9) Moreover, let Lnsd,PL_n^sd,P be the prefix length of the retained tokens before draft generation in iteration n, which is given by Lnsd,P=Lmaxsd,I,n=1,Lmaxsd,I+(n−2)maxk∈yk=1LkA+1+maxk∈yk=1LkA,n≥2.L_n^sd,P= casesL_ ^sd,I,\ n=1,\\ aligned L_ ^sd,I+ (n-2 ) _ subarrayck \\ y_k=1 subarray \L_k^A+1 \+ _ subarrayck \\ y_k=1 subarray \L_k^A \ aligned,n≥ 2. cases (10) For n=1n=1, the retained prefix only consists of the input prompt tokens. For n≥2n≥ 2, it further includes the accepted draft tokens and additional tokens retained from previous iterations. Following ΓlL,a(LI) _l^L,a (L^I ), we define the SLM workload for generating one token for a single input prompt at the l-th decoding step of iteration n, given LnPL_n^P prefix tokens available at the beginning of iteration n, as Γn,lS,a(LnP)=MS[8DS,mDS,hHS+4(LnP+l)DS,hHS+4DS,mDS,f]. _n,l^S,a (L_n^P )=M^S [ aligned 8D^S,mD^S,hH^S+4 (L_n^P+l )D^S,hH^S+4D^S,mD^S,f aligned ]. Thus, the SLM workload at decoding step l of iteration n is Wn,lsd,a=∑k∈ykn≤NkΓn,lS,a(Lnsd,P), W_n,l^sd,a=Σ _k y_kI_ \n≤ N_k \ _n,l^S,a (L_n^sd,P ), (11) where users with n>Nkn>N_k are excluded in iteration n. We define the LLM workload for verifying LDL^D tokens in iteration n for a single input prompt, given LnPL_n^P prefix tokens available at the beginning of iteration n, as ΓnL,v(LnP,LD)=ML _n^L,v (L_n^P,L^D )=M^L [8LDDL,mDL,hHL+4∑l=1LD(LnP+l)DL,hHL+4LDDL,mDL,f] [8L^DD^L,mD^L,hH^L+4Σ _l=1^L^D (L_n^P+l )D^L,hH^L+4L^DD^L,mD^L,f ]. Thus, the LLM workload for verification in iteration n is Wnsd,v=∑k∈ykn≤NkΓ1L,v(L1sd,P,LD),n=1∑k∈ykn≤NkΓnL,v(Lnsd,P,LD+1),n≥2. W_n^sd,v= (12) In the first iteration, the LLM verifies LDL^D draft tokens for each request. When n≥2n≥ 2, the verification further includes the additional token generated in the previous iteration. I-E Memory Model Following previous works [36], we consider the memory required for storing model weights and the KV cache during inference when analyzing memory consumption. I-E1 Memory for hosting the LLM and SLM The GPU memory required to store the LLM and SLM weights is qL=MLθ(4DL,mDL,hHL+2DL,mDL,f),q^L=M^Lθ (4D^L,mD^L,hH^L+2D^L,mD^L,f ), (13) and qS=MSθ(4DS,mDS,hHS+2DS,mDS,f),q^S=M^Sθ (4D^S,mD^S,hH^S+2D^S,mD^S,f ), (14) respectively, where θ denotes the number of bytes required to represent one floating-point number [36]. I-E2 Memory for the AD mode In the AD mode, the required KV cache memory for prefilling is qad,p=MLθ(∑k∈xkLmaxad,I)2DL,hHLq^ad,p=M^Lθ (Σ _k x_kL_ ^ad,I )2D^L,hH^L, where 2DL,hHL2D^L,hH^L denotes the number of KV cache elements required by one token across all attention heads in each layer. During decoding, the peak KV cache memory is denoted by qad,a=MLθ[∑k∈xk(Lmaxad,I+LkO)]2DL,hHLq^ad,a=M^Lθ [Σ _k x_k (L_ ^ad,I+L_k^O ) ]2D^L,hH^L. Therefore, the peak KV cache memory in the AD mode is given by qad=maxqad,p,qad,a=qad,a.q^ad= \q^ad,p,q^ad,a \=q^ad,a. (15) I-E3 Memory for the SD mode In the SD mode, the required KV cache memory for prefilling is given by qsd,p=qsd,L,p+qsd,S,pq^sd,p=q^sd,L,p+q^sd,S,p, where qsd,L,pq^sd,L,p and qsd,S,pq^sd,S,p denote the KV cache memory required by the LLM and SLM during prefilling, respectively. Following qad,pq^ad,p, qsd,L,p=MLθ(∑k∈ykLmaxsd,I)2DL,hHLq^sd,L,p=M^Lθ (Σ _k y_kL_ ^sd,I )2D^L,hH^L and qsd,S,p=MSθ(∑k∈ykLmaxsd,I)2DS,hHSq^sd,S,p=M^Sθ (Σ _k y_kL_ ^sd,I )2D^S,hH^S. Following qad,aq^ad,a, the peak SLM KV cache memory during draft generation is given by qsd,a=MSθ[∑k∈yk(LNksd,P+LD)]2DS,hHSq^sd,a=M^Sθ [Σ _k y_k (L_N_k^sd,P+L^D ) ]2D^S,hH^S. During verification, the peak LLM KV cache is given by qsd,v=MLθ[∑k∈yk(LNksd,P+LD+1)]2DL,hHLq^sd,v=M^Lθ [Σ _k y_k (L_N_k^sd,P+L^D+1 ) ]2D^L,hH^L. Therefore, the peak KV cache memory in the SD mode is qsd=maxqsd,p,qsd,a+qsd,v=qsd,a+qsd,v.q^sd= \q^sd,p,q^sd,a+q^sd,v \=q^sd,a+q^sd,v. (16) I-F User E2E latency To model the inference latency under shared GPU computing resources, we consider the computing resource allocation between the AD and SD modes. Let z denote the fraction of GPU computing resources allocated to the AD mode, and thus 1−z1-z is allocated to the SD mode333In practice, GPU computing resource allocation can be implemented by partitioning GPU resources, e.g., streaming multiprocessors and GPU engines, across multiple tasks, which has already been supported by NVIDIA [37]. For simplicity, we refer to it as “GPU computing resource allocation” in this paper. Such allocation has been adopted in existing studies [38].. I-F1 Latency of the AD mode Following previous studies [39], the LLM prefilling time in the AD mode is τad,p=αLWad,pz+βLτ^ad,p= α^LW^ad,pz+β^L, where αLα^L and βLβ^L are model- and hardware-dependent constants measured offline. The time of decoding step l in the AD mode is τlad,a=αLWlad,az+βL _l^ad,a= α^LW_l^ad,az+β^L. Thus, the time from prefilling to the completion of step l in the AD mode is τlad=τad,p+∑l′=1lτl′ad,a. _l^ad=τ^ad,p+Σ _l =1^l _l ^ad,a. (17) I-F2 Latency of the SD mode The prefilling times of the LLM and the SLM in the SD mode are given by τsd,L,p=αLWsd,L,p1−z+βLτ^sd,L,p= α^LW^sd,L,p1-z+β^L and τsd,S,p=αSWsd,S,p1−z+βSτ^sd,S,p= α^SW^sd,S,p1-z+β^S, respectively. For iteration n, the time required by the SLM to generate LDL^D draft tokens for all users scheduled to the SD mode is τnsd,a=∑l=1LD−1(αSWn,lsd,a1−z+βS),n=1,∑l=1LD(αSWn,lsd,a1−z+βS), 2≤n≤Nmaxsd, _n^sd,a= casesΣ _l=1^L^D-1 ( α^SW_n,l^sd,a1-z+β^S ),\ n=1,\\ Σ _l=1^L^D ( α^SW_n,l^sd,a1-z+β^S ),\ 2≤ n≤ N_ ^sd, cases (18) where the first iteration requires only LD−1L^D-1 steps due to the prefilling. Moreover, the LLM verification time in iteration n is denoted by τnsd,v=αLWnsd,v1−z+βL _n^sd,v= α^LW_n^sd,v1-z+β^L. Thus, the time from prefilling to the completion of iteration n in the SD mode is τnsd=τsd,L,p+τsd,S,p+∑n′=1n(τn′sd,a+τn′sd,v). _n^sd=τ^sd,L,p+τ^sd,S,p+Σ _n =1^n ( _n ^sd,a+ _n ^sd,v ). (19) I-F3 E2E latency Based on (1), (2), (3), (17), and (19), the E2E latency of user k is expressed as tkE=xk(τad,up+τLmaxad,O−1ad)+yk(τsd,up+τNmaxsdsd)+τkdown.t_k^E=x_k (τ^ad,up+ _L_ ^ad,O-1^ad )+y_k (τ^sd,up+ _N_ ^sd^sd )+ _k^down. (20) I-G Problem Formulation To maximize the task throughput of BALANCE, i.e., the number of served users satisfying their latency requirements, we formulate the following optimization problem. 1:max,,zr(+)=∑k∈xk+ykP1: _ X, Y,z\ r ( X+ Y )=Σ _k x_k+y_k (21a) s.t.xk+yk≤1,∀k∈, s.t.\ x_k+y_k≤ 1,\ ∀ k , (21b) tkE≤Tk,∀k∈,t_k^E≤ T_k,\ ∀ k , (21c) z<1qS+qL+qad+qsd≤Q,I_ \z<1 \q^S+q^L+q^ad+q^sd≤ Q, (21d) xk∈0,1,∀k∈,x_k∈ \0,1 \,\ ∀ k , (21e) yk∈0,1,∀k∈,y_k∈ \0,1 \,\ ∀ k , (21f) z∈.z∈ Z. (21g) Here, xk∈x_k∈ X, yk∈y_k∈ Y, and z are the decision variables for AD-mode user scheduling, SD-mode user scheduling, and GPU computing resource allocation, respectively. In (21a), + X+ Y denotes the element-wise sum of X and Y. Constraint (21b) assigns each user to at most one inference mode. Constraints (21c) and (21d) enforce the user latency and GPU memory capacity constraints, respectively. Here, Q is the available GPU memory capacity, and the indicator function z<1I_ \z<1 \ equals 1 if z<1z<1 and 0 otherwise. When z=1z=1, the SD mode is inactive, so the SLM weights are not loaded into GPU memory. Constraints (21e) and (21f) are binary constraints. Constraint (21g) restricts z to =0,z1,…,zI,1 Z= \0,z_1,…,z_I,1 \, where 0<z1<⋯<zI<10<z_1<…<z_I<1. The values in Z represent the GPU computing resource allocation ratios supported by the system. IV Algorithm Design This section proves the NP-hardness of 1P1 and develops a polynomial-time constant-approximation algorithm. IV-A Problem Mapping The NP-hardness of 1P1 is stated below. Proposition 1. 1P1 is an NP-hard problem. Proof. The proof sketch is as follows. Consider a special case of 1P1 with fixed z. The problem then reduces to user scheduling under latency requirements and memory resource constraints, which can be mapped to a multi-dimensional multiple-choice knapsack problem (MMKP). Since the MMKP is NP-hard [40, 41], 1P1 is NP-hard, completing the proof. ∎ IV-B Equivalent Problem Transformation To facilitate the solution design, we introduce an auxiliary variable λ to represent the fraction of available GPU memory allocated to the AD mode. Since the memory consumption of the AD and SD modes can be characterized separately, 1P1 is equivalently transformed into the following 2P2. 2:max,,z,λr(+)=∑k∈xk+ykP2: _ X, Y,z,λ\ r ( X+ Y )=Σ _k x_k+y_k (22a) s.t.(21b),(21c),(21e),(21f),(21g), s.t.\ const_1, const_4, const_6, const_7, const_9, (22b) qad≤Q1,q^ad≤ Q_1, (22c) qsd≤Q2,q^sd≤ Q_2, (22d) λ∈Λ.λ∈ . (22e) Here, Q1=λ(Q−qL−z<1qS)Q_1=λ (Q-q^L-I_ \z<1 \q^S ) and Q2=(1−λ)(Q−qL−z<1qS)Q_2= (1-λ ) (Q-q^L-I_ \z<1 \q^S ) denote the memory reserved for the AD and SD modes, respectively. Constraint (22e) restricts λ to Λ=0,λ1,…,λJ,1 = \0, _1,…, _J,1 \, where 0<λ1<⋯<λJ<10< _1<…< _J<1. The set Λ contains all supported ratios for partitioning GPU memory between the AD and SD modes, ensuring that every feasible memory split can be represented by some λ∈Λλ∈ . Next, we state that solving 2P2 is equivalent to solving 1P1. Proposition 2. Solving 1P1 is equivalent to solving 2P2. Proof. After reserving memory for the model weights, Q1Q_1 and Q2Q_2 can be obtained according to λ. By the construction of Λ , any feasible solution to 1P1 corresponds to a feasible solution to 2P2. Conversely, any feasible solution to 2P2 satisfies the memory constraint in 1P1 since Q1Q_1 and Q2Q_2 are given. Thus, 1P1 and 2P2 are equivalent, completing the proof. ∎ To solve 2P2, we fix z and λ, and have the below proposition. Proposition 3. Given z and λ, solving 2P2 is equivalent to solving 3P3. 3:max,r(+)=∑k∈xk+ykP3: _ X, Y\ r ( X+ Y )=Σ _k x_k+y_k (23a) s.t.(21b),(21c),(21e),(21f),(22c),(22d). s.t.\ const_1, const_4, const_6, const_7, const_p2_2, const_p2_3. (23b) Proof. For fixed z and λ, constraints (21g) and (22e) can be removed, reducing 2P2 to 3P3 and completing the proof. ∎ IV-C Problem Decomposition Given the NP-hardness of 3P3, we decouple 3P3 into the following two sub-problems, 3.1P3.1 and 3.2P3.2, which schedule users in the AD and SD modes, respectively. We have 3.1:maxr()=∑k∈xkP3.1: _ X\ r ( X )=Σ _k x_k (24a) s.t.(21e),(22c) s.t.\ const_6, const_p2_2 (24b) xktad≤Tk′,∀k∈,x_kt^ad≤ T _k,\ ∀ k , (24c) where tad=τad,up+τLmaxad,O−1adt^ad=τ^ad,up+ _L_ ^ad,O-1^ad denotes the latency of the AD mode excluding output downloading, and Tk′=Tk−ΔτkdownT _k=T_k- _k^down denotes the remaining latency budget of user k after reserving the output downloading latency. Also, we have 3.2:maxr′()=∑k∈∖adykP3.2: _ Y\ r ( Y )=Σ _k ^ady_k (25a) s.t.(22d), s.t.\ const_p2_3, (25b) yktsd≤Tk′,∀k∈∖ad,y_kt^sd≤ T _k,\ ∀ k ^ad, (25c) yk∈0,1,∀k∈∖ad,y_k∈ \0,1 \,\ ∀ k ^ad, (25d) where tsd=τsd,up+τNmaxsdsdt^sd=τ^sd,up+ _N_ ^sd^sd denotes the latency of the SD mode excluding output downloading, and ad=k|xk=1K^ad= \k\ |\ x_k=1 \ is the set of users served by the AD mode. The following subsections will sequentially solve 3.1P3.1 and 3.2P3.2 to determine the optimal user scheduling for the AD and SD modes, respectively. The performance gap between the sequential solution and the optimal solution to 1P1 will be analyzed in Section IV-F. IV-D Solution to 3.1P3.1: User Scheduling for the AD Mode We obtain an optimal solution to 3.1P3.1 by enumerating the feasible values of Lmaxad,IL_ ^ad,I, Lmaxad,OL_ ^ad,O, tadt^ad, and τad,upτ^ad,up, and identifying the served users under each setting. When z=0z=0 or λ=0λ=0, the AD mode is inactive, and thus the optimal solution to 3.1P3.1 is ^= X= 0. The following analysis considers z>0z>0 and λ>0λ>0. First, given Lmaxad,I=L1L_ ^ad,I=L_1, Lmaxad,O=L2L_ ^ad,O=L_2, tad=t1t^ad=t_1, and τad,up=τ1τ^ad,up= _1, the candidate user set for the AD mode is 1=k|k∈,LkI≤L1,LkO≤L2,t1≤Tk′,Δτkup≤τ1K_1= \k\ |\ k ,L_k^I≤ L_1,L_k^O≤ L_2,t_1≤ T _k, _k^up≤ _1 \. For each candidate user k∈1k _1, its latency contribution is t~kad=αLW~kad,pz+∑l=1L2−1αLW~l,kad,az. t_k^ad= α^L W_k^ad,pz+Σ _l=1^L_2-1 α^L W_l,k^ad,az. (26) Here, W~kad,p W_k^ad,p and W~l,kad,a W_l,k^ad,a denote the contributions of user k to the LLM workloads during prefilling and at the l-th decoding step in the AD mode, respectively, where W~kad,p=ΓL,p(L1) W_k^ad,p= ^L,p (L_1 ) and W~l,kad,a=l≤LkO−1ΓlL,a(L1) W_l,k^ad,a=I_ \l≤ L_k^O-1 \ _l^L,a (L_1 ). Moreover, the contribution of user k∈1k _1 to the total memory consumption of the AD mode is given by q~kad=q~ad=MLθ(L1+L2)2DL,hHL. q_k^ad= q^ad=M^Lθ (L_1+L_2 )2D^L,hH^L. (27) Second, let Π1=1,…,d1…,|1| _1= \1,…,d_1…, |K_1 | \ denote a permutation of the users in 1K_1 sorted in a non-decreasing order of t~kad t_k^ad, i.e., t~Π1(d1)ad≤t~Π1(d1+1)ad t_ _1 (d_1 )^ad≤ t_ _1 (d_1+1 )^ad. Therefore, the number of served users under L1L_1, L2L_2, t1t_1, and τ1 _1 is given by d1∗=maxd1|d1≤⌊Q1q~ad⌋,∑d1′=1d1t~Π1(d1′)ad≤Δt1,d_1^*= \d_1\ |\ d_1≤ Q_1 q^ad ,Σ _d _1=1^d_1 t_ _1 (d _1 )^ad≤ t_1 \, (28) where Δt1=t1−τ1−Δτ1 t_1=t_1- _1- _1 and Δτ1=L2βL _1=L_2β^L denotes the fixed latency term of one forward pass in prefilling and L2−1L_2-1 forward passes in decoding. Based on (28), the served user set for the AD mode under L1L_1, L2L_2, t1t_1, and τ1 _1 is ^ad=Π1(1),…,Π1(d1∗) K^ad= \ _1 (1 ),…, _1 (d_1^* ) \, and the corresponding user scheduling decision x^k∈ x_k∈ X is x^k=1, if k∈^ad,0, otherwise. x_k= cases1, if k∈ K^ad,\\ 0, otherwise. cases (29) By enumerating all feasible L1L_1, L2L_2, t1t_1, and τ1 _1, we can obtain the maximum number of served users and the corresponding user scheduling decision under given z and λ for 3.1P3.1. Algorithm 1 summarizes the above procedures, and its optimality is established in the following proposition. Proposition 4. Algorithm 1 obtains an optimal solution to 3.1P3.1 under given z and λ. Proof. The proof sketch is below. For fixed z and λ, every feasible solution to 3.1P3.1 corresponds to a tuple (L1,L2,t1,τ1) (L_1,L_2,t_1, _1 ). For each tuple, all candidate users in 1K_1 have unit profit, identical memory contributions, and fixed latency contributions. Thus, (29) leads to the optimal user scheduling for this tuple. Since Algorithm 1 enumerates all feasible tuples, it obtains an optimal solution to 3.1P3.1, completing the proof. ∎ Input: z and λ. Output: X and ^ad K^ad. 1 Initialize: r1=0r_1=0, ^= X= 0, ^ad=∅ K^ad= . 2 if z=0z=0 or λ=0λ=0 then 3 Return ^= X= 0 and ^ad=∅ K^ad= . 4 5 end if 6for L1∈0⋃LkI|k∈L_1∈ \0 \ \L_k^I |k \, L2∈0⋃LkO|k∈L_2∈ \0 \ \L_k^O |k \, t1∈0⋃Tk′|k∈t_1∈ \0 \ \T _k |k \ do 7 for τ1∈0⋃Δτkup|k∈ _1∈ \0 \ \ _k^up\ |\ k \ do 8 Calculate d1∗d_1^* with (28). 9 if d1∗>r1d_1^*>r_1 then 10 r1=d1∗r_1=d_1^* and ^ad=Π1(1),…,Π1(d1∗) K^ad= \ _1 (1 ),…, _1 (d_1^* ) \. 11 12 end if 13 14 end for 15 16 end for 17Calculate X with (29). Algorithm 1 AD-Mode User Scheduling Algorithm IV-E Solution to 3.2P3.2: User Scheduling for the SD Mode We solve 3.2P3.2 similarly by enumerating the feasible values of Lmaxsd,IL_ ^sd,I, Lmaxsd,AL_ ^sd,A, NmaxsdN_ ^sd, tsdt^sd, and τsd,upτ^sd,up, and identifying the served users under each setting. When z=1z=1 or λ=1λ=1, the SD mode is inactive, and thus the optimal solution to 3.2P3.2 is ^= Y= 0. The following analysis considers z<1z<1 and λ<1λ<1. First, given Lmaxsd,I=L3L_ ^sd,I=L_3, Lmaxsd,A=L4L_ ^sd,A=L_4, Nmaxsd=N~1N_ ^sd= N_1, tsd=t2t^sd=t_2, and τsd,up=τ2τ^sd,up= _2, the candidate user set for the SD mode is 2=k|k∈′,LkI≤L3,LkA≤L4,Nk≤N~1,t2≤Tk′,Δτkup≤K_2= \k\ |\ k ,L_k^I≤ L_3,L_k^A≤ L_4,N_k≤ N_1,t_2≤ T _k, _k^up≤ . τ2 . _2 \, where ′=∖adK =K ^ad. The contribution of each candidate user k∈2k _2 to the total latency of the SD mode is t~ksd t_k^sd =αLW~ksd,L,p1−z+αSW~ksd,S,p1−z = α^L W_k^sd,L,p1-z+ α^S W_k^sd,S,p1-z (30) +∑l=1LD−1αSW~1,l,ksd,a1−z+∑n=2N~1∑l=1LDαSW~n,l,ksd,a1−z+∑n=1N~1αLW~n,ksd,v1−z. +Σ _l=1^L^D-1 α^S W_1,l,k^sd,a1-z+Σ _n=2 N_1Σ _l=1^L^D α^S W_n,l,k^sd,a1-z+Σ _n=1 N_1 α^L W_n,k^sd,v1-z. Here, W~ksd,L,p W_k^sd,L,p and W~ksd,S,p W_k^sd,S,p are the contributions of user k to the total LLM and SLM workloads during prefilling in the SD mode, respectively, where W~ksd,L,p=ΓL,p(L3) W_k^sd,L,p= ^L,p (L_3 ) and W~ksd,S,p=ΓS,p(L3) W_k^sd,S,p= ^S,p (L_3 ). Additionally, W~n,l,ksd,a W_n,l,k^sd,a and W~n,ksd,v W_n,k^sd,v denote the contributions of user k to the total SLM workload at the l-th decoding step of iteration n and the total LLM workload during verification in iteration n, respectively. Let L~nsd,P L_n^sd,P denote the prefix length of the retained tokens before draft generation in the n-th iteration under L3L_3 and L4L_4, where L~nsd,P=L3 L_n^sd,P=L_3 when n=1n=1, and L~nsd,P=L3+(n−2)(L4+1)+L4 L_n^sd,P=L_3+ (n-2 ) (L_4+1 )+L_4 when n≥2n≥ 2. Thus, W~n,l,ksd,a=n≤NkΓlS,a(L~nsd,P) W_n,l,k^sd,a=I_ \n≤ N_k \ _l^S,a ( L_n^sd,P ), W~n,ksd,v=n≤NkΓ1L,v(L~1sd,P,LD) W_n,k^sd,v=I_ \n≤ N_k \ _1^L,v ( L_1^sd,P,L^D ) when n=1n=1, and W~n,ksd,v=n≤NkΓnL,v(L~nsd,P,LD+1) W_n,k^sd,v=I_ \n≤ N_k \ _n^L,v ( L_n^sd,P,L^D+1 ) when n≥2n≥ 2. Moreover, the contribution of user k to the total memory consumption of the SD mode is given by q~ksd=q~ksd,a+q~ksd,v. q_k^sd= q_k^sd,a+ q_k^sd,v. (31) Here, q~ksd,a=MSθ(L~Nksd,P+LD)2DS,hHS q_k^sd,a=M^Sθ ( L_N_k^sd,P+L^D )2D^S,hH^S denotes the contribution of user k to the total memory consumption during SLM draft generation. q~ksd,v q_k^sd,v denotes the contribution of user k to the total memory consumption during LLM draft verification, where q~ksd,v=MLθ(L~Nksd,P+LD)2DL,hHL q_k^sd,v=M^Lθ ( L_N_k^sd,P+L^D )2D^L,hH^L when Nk=1N_k=1, and q~ksd,v=MLθ(L~Nksd,P+LD+1)2DL,hHL q_k^sd,v=M^Lθ ( L_N_k^sd,P+L^D+1 )2D^L,hH^L when Nk≥2N_k≥ 2. Second, let Π2=1,…,d2…,|2| _2= \1,…,d_2…, |K_2 | \ denote a permutation of the users in 2K_2 sorted in a non-decreasing order of t~ksd t_k^sd, i.e., t~Π2(d2)sd≤t~Π2(d2+1)sd t_ _2 (d_2 )^sd≤ t_ _2 (d_2+1 )^sd. Since both t~ksd t_k^sd and q~ksd q_k^sd are monotonically non-decreasing with NkN_k, sorting users by t~ksd t_k^sd also preserves the non-decreasing order of q~ksd q_k^sd. Therefore, the number of served users under L3L_3, L4L_4, N~1 N_1, t2t_2, and τ2 _2 is d2∗=maxd2|∑d2′=1d2q~Π2(d2′)sd≤Q2,∑d2′=1d2t~Π2(d2′)sd≤Δt2,d_2^*= \d_2\ |\ Σ _d _2=1^d_2 q_ _2 (d _2 )^sd≤ Q_2,Σ _d _2=1^d_2 t_ _2 (d _2 )^sd≤ t_2 \, (32) where Δt2=t2−τ2−Δτ2 t_2=t_2- _2- _2 and Δτ2=(N~1+1)βL+N~1LDβS _2= ( N_1+1 )β^L+ N_1L^Dβ^S denotes the fixed latency term in the SD mode. Based on (32), the served user set of the SD mode under L3L_3, L4L_4, N~1 N_1, t2t_2, and τ2 _2 is ^sd=Π2(1),…,Π2(d2∗) K^sd= \ _2 (1 ),…, _2 (d_2^* ) \, and the corresponding user scheduling decision y^k∈ y_k∈ Y is y^k=1, if k∈^sd,0, otherwise. y_k= cases1, if k∈ K^sd,\\ 0, otherwise. cases (33) By enumerating all feasible L3L_3, L4L_4, N~1 N_1, t2t_2, and τ2 _2, we can identify the maximum number of served users and the corresponding user scheduling decision under given z and λ for 3.2P3.2. Algorithm 2 summarizes the above procedures, and its optimality is established in the following proposition. Proposition 5. Algorithm 2 obtains an optimal solution to 3.2P3.2 under given z, λ, and ^ad K^ad. Proof. The proof is similar to that of Proposition 4. Since t~ksd t_k^sd and q~ksd q_k^sd are non-decreasing in NkN_k, (33) maximizes the number of served users for each tuple. Enumerating all feasible tuples yields an optimal solution to 3.2P3.2, completing the proof. ∎ Input: z, λ, and ^ad K^ad. Output: Y and ^sd K^sd. 1 Initialize: ′=∖^adK =K K^ad, r2=0r_2=0, ^= Y= 0, ^sd=∅ K^sd= . 2 if z=1z=1 or λ=1λ=1 then 3 Return ^= Y= 0 and ^sd=∅ K^sd= . 4 5 end if 6for L3∈0⋃LkI|k∈′L_3∈ \0 \ \L_k^I |k \, L4∈0⋃LkA|k∈′L_4∈ \0 \ \L_k^A |k \, N~1∈0⋃Nk|k∈′ N_1∈ \0 \ \N_k |k \, t2∈0⋃Tk′|k∈′t_2∈ \0 \ \T _k\ |\ k \ do 7 for τ2∈0⋃Δτkup|k∈′ _2∈ \0 \ \ _k^up\ |\ k \ do 8 Calculate d2∗d_2^* with (32). 9 if d2∗>r2d_2^*>r_2 then 10 r2=d2∗r_2=d_2^* and ^sd=Π2(1),…,Π2(d2∗) K^sd= \ _2 (1 ),…, _2 (d_2^* ) \. 11 12 end if 13 14 end for 15 16 end for 17Calculate Y with (33). Algorithm 2 SD-Mode User Scheduling Algorithm IV-F Algorithm Outline Algorithm 3 summarizes the overall procedure for solving 1P1. It enumerates all feasible pairs of (z,λ) (z,λ ). For each pair, it first solves 3.1P3.1 using Algorithm 1 to schedule users for the AD mode, and then solves 3.2P3.2 using Algorithm 2 to schedule the remaining users for the SD mode. The solution that serves the maximum number of users over all pairs gives the user scheduling decision ˙ X for the AD mode, user scheduling decision ˙ Y for the SD mode, and GPU computing resource allocation z˙ z. The approximation guarantee of Algorithm 3 is characterized in the following theorem. Theorem 1. Algorithm 3 achieves a constant approximation guarantee. Specifically, the produced solution ˙ X and ˙ Y satisfy r(˙+˙)≥12r(∗+∗)r ( X+ Y )≥ 12r ( X^*+ Y^* ), where ∗ X^* and ∗ Y^* denote the optimal user scheduling decisions of 1P1. Proof. The proof sketch is as follows. Since X and Y are disjoint, we have r(+)=r()+r()r ( X+ Y )=r ( X )+r ( Y ) and r′()=r()r ( Y )=r ( Y ). Let z∗z^* and λ∗λ^* denote the computing and memory resource allocations in an optimal solution. Since Algorithm 3 enumerates all feasible z and λ, it also examines z∗z^* and λ∗λ^*, and thus r(˙+˙)=r(^+^|λ=λ˙,z=z˙)≥r(^+^|λ=λ∗,z=z∗)r ( X+ Y )=r ( X+ Y\ |\ λ= λ,z= z )≥ r ( X+ Y\ |\ λ=λ^*,z=z^* ). By Proposition 4, r(^|λ=λ∗,z=z∗)≥r(∗)r ( X\ |\ λ=λ^*,z=z^* )≥ r ( X^* ). We decompose ∗ Y^* into disjoint 1∗ Y_1^* and 2∗ Y_2^*, where 1∗ Y_1^* includes the users in ∗ Y^* that are also selected by ^ad|λ=λ∗,z=z∗ K^ad |_λ=λ^*,z=z^*, and 2∗ Y_2^* includes the remaining users. By Proposition 5, r(^|λ=λ∗,z=z∗)≥r(2∗)r ( Y\ |\ λ=λ^*,z=z^* )≥ r ( Y_2^* ). Since 1∗ Y_1^* only contains users already selected by X, we have r(1∗)≤r(^|λ=λ∗,z=z∗)r ( Y_1^* )≤ r ( X\ |\ λ=λ^*,z=z^* ). Thus, r(∗)≤r(^|λ=λ∗,z=z∗)+r(^|λ=λ∗,z=z∗)r ( Y^* )≤ r ( X\ |\ λ=λ^*,z=z^* )+r ( Y\ |\ λ=λ^*,z=z^* ). Then, we have r(∗+∗)≤2r(^+^|λ=λ∗,z=z∗)≤2r(˙+˙)r ( X^*+ Y^* )≤ 2r ( X+ Y\ |\ λ=λ^*,z=z^* )≤ 2r ( X+ Y ), completing the proof. ∎ Input: K, Q, and TkT_k. Output: ˙ X, ˙ Y, z˙ z, and λ˙ λ. 1 Initialize: r3=0r_3=0, ˙= X= 0, ˙= Y= 0, z˙=0 z=0, λ˙=0 λ=0. 2 for z∈z∈ Z, λ∈Λλ∈ do 3 Obtain X and ^ad K^ad using Algorithm 1 with z and λ. 4 Obtain Y and ^sd K^sd using Algorithm 2 with z, λ, and ^ad K^ad. 5 if |^ad|+|^sd|>r3 | K^ad |+ | K^sd |>r_3 then 6 r3=|^ad|+|^sd|r_3= | K^ad |+ | K^sd |, ˙= X= X, ˙= Y= Y, z˙=z z=z, and λ˙=λ λ=λ. 7 8 end if 9 10 end for Algorithm 3 BALANCE User Scheduling Algorithm The time complexity of Algorithm 3 is stated below. Theorem 2. Algorithm 3 has a polynomial time complexity of O(K6logK)O (K^6 K ), where K is the total number of users in K. Proof. The proof sketch is as follows. Algorithm 1 enumerates O(K4)O (K^4 ) tuples (L1,L2,t1,τ1) (L_1,L_2,t_1, _1 ). For each tuple, constructing Π1 _1 and computing d1∗d_1^* in Line 1 require O(KlogK)O (K K ) time. Therefore, the time complexity of Algorithm 1 is O(K5logK)O (K^5 K ). Similarly, the time complexity of Algorithm 2 is O(K6logK)O (K^6 K ). Algorithm 3 enumerates O(|||Λ|)O ( | Z | | | ) pairs (z,λ) (z,λ ), where || | Z | and |Λ| | | denote the cardinalities of Z and Λ , respectively. For each pair, Lines 3 and 3 require O(K5logK)O (K^5 K ) and O(K6logK)O (K^6 K ) time, respectively. Since || | Z | and |Λ| | | are constants, Algorithm 3 has time complexity O(K6logK)O (K^6 K ), completing the proof. ∎ V Numerical Results This section evaluates the performance of BALANCE under different system settings, compares the algorithm running time, and conducts ablation studies. V-A Experimental Setup We adopt a hybrid testing method that combines device measurements and numerical simulations to evaluate the performance of the proposed BALANCE framework. Specifically, computing latencies are measured on a real server, while the communication latencies in multi-user scenarios are obtained through simulations. The inference is performed on an edge server using an AMD Ryzen Threadripper PRO 5975WX CPU, an NVIDIA GeForce RTX 4090 GPU with 24 GB of GPU memory, and 256 GB of DDR4 RAM. TinyLlama-1.1B and Llama-2-7B are used as the SLM and LLM, respectively, with FP16 precision. Accordingly, Q = 24 GB. The coverage radius of the edge server is set to 250 m. The uplink and downlink bandwidths allocated to user k are set to Bk=1 MHzB_k=1 MHz and B¯k=2 MHz B_k=2 MHz, respectively. The transmit power spectral densities of the users for uplink transmission and of the edge server for downlink transmission are set to -50 dBm/Hz and -29 dBm/Hz, respectively. The number of users K ranges from 20 to 70. The user latency requirement satisfies Tk∈[Tmin,Tmax]T_k∈ [T_ ,T_ ], ranging from 0.5 s to 13 s. The input length LkIL_k^I and output length LkOL_k^O are set within [LminI,LmaxI] [L_ ^I,L_ ^I ] and [LminO,LmaxO] [L_ ^O,L_ ^O ], respectively, both ranging from 1 to 1000 tokens. For SD, the draft token length LDL^D is set to 1, and the acceptance rate AkA_k is set within [0.6,0.8] [0.6,0.8 ]. We compare BALANCE with the following baselines. • AD-only [17]. In this baseline, all users are served only by the AD mode, and user scheduling is determined by Algorithm 1. By Proposition 4, this baseline achieves the maximum task throughput under the AD-only mode. • SD-only [20]. In this baseline, all users are served only by the SD mode. User scheduling is determined by Algorithm 2. By Proposition 5, this baseline achieves the maximum task throughput under the SD-only mode. • Exhaustive search. This baseline solves the original problem 1P1 by exhaustively searching all feasible solutions, thereby incurring exponential time complexity. We use this baseline as an exact solution method to evaluate the running time efficiency of the proposed algorithm. To evaluate system performance, we use normalized task throughput, defined as the ratio of the number of served users to the total number of users. V-B Performance Evaluation Figs. 4 and 5 evaluate the normalized task throughput of BALANCE under varying system settings. BALANCE consistently outperforms both AD-only and SD-only baselines. In Fig. 4, the throughput decreases with the number of users and increases under looser latency requirements. On average, BALANCE improves throughput over AD-only and SD-only baselines by 37.9% and 33.4%, respectively, under varying K, and by 31.5% and 27.3%, respectively, under varying TmaxT_ . In Fig. 5, BALANCE achieves average gains over AD-only and SD-only baselines of 38.8% and 23.9%, respectively, under varying LmaxIL_ ^I, and 30.4% and 27.3%, respectively, under varying LmaxOL_ ^O. (a) Results vs. number of users K. (b) Results vs. maximum latency requirement TmaxT_ . Figure 4: Performance of BALANCE under varying K and TmaxT_ . The default values of K, TminT_ , TmaxT_ are set to 30, 0.5, and 4, respectively. LminIL_ ^I, LmaxIL_ ^I, LminOL_ ^O, and LmaxOL_ ^O are set to 1, 300, 1, and 100, respectively. (a) Results vs. maximum input length LmaxIL_ ^I. (b) Results vs. maximum output length LmaxOL_ ^O. Figure 5: Performance of BALANCE under varying LmaxIL_ ^I and LmaxOL_ ^O. The default values of LminIL_ ^I, LmaxIL_ ^I, LminOL_ ^O, LmaxOL_ ^O are set to 1, 1000, 1, and 500, respectively. TminT_ and TmaxT_ are set to 2 s and 12 s, respectively. The default value of K is same as Fig. 4. V-C Algorithm Running Time Comparisons Fig. 6 compares the algorithm running time and task throughput of the proposed algorithm with exhaustive search under varying K. To run the exhaustive search efficiently, K is varied from 10 to 16. As shown in Fig. 6(a), the running time of the proposed algorithm grows nearly linearly with K, while exhaustive search increases nearly exponentially. The proposed algorithm achieves an average acceleration of about 5,100 times and up to 21,800 times at K=16K=16. Moreover, Fig. 6(b) shows that the proposed algorithm achieves near-optimal task throughput, with only about 0.9% average degradation. (a) Running time vs. number of users K. (b) Normalized task throughput vs. number of users K. Figure 6: Comparisons of algorithm running time and task throughput between the proposed algorithm and the exhaustive search under varying K. The system parameters are the same as those in Fig. 4(a). V-D Ablation Study We conduct ablation studies to evaluate the contribution of each component in the proposed algorithm. We compare the proposed algorithm with three variants, including equal computing resource allocation (ECRA), equal memory allocation (EMA), and equal computing resource and memory allocation (ECRMA). In ECRA, z=0.5z=0.5, while λ and user scheduling are optimized using Algorithm 3. In EMA, λ=0.5λ=0.5, while z and user scheduling are optimized using Algorithm 3. In ECRMA, both z and λ are 0.5, and only user scheduling is optimized using Algorithm 3. Fig. 7 illustrates the performance gains of the proposed algorithm over ECRA, EMA, and ECRMA under varying K and TmaxT_ . Specifically, in Fig. 7(a), the proposed algorithm improves the task throughput by 5.6%, 18.7%, and 23.7% on average compared with ECRA, EMA, and ECRMA, respectively. The corresponding average performance improvements are 9.0%, 4.9%, and 18.4% in Fig. 7(b). (a) Ablation results vs. number of users K. (b) Ablation results vs. maximum latency requirement TmaxT_ . Figure 7: Ablation study results for the proposed algorithm. The system parameters are the same as those in Fig. 4. VI Conclusion In this paper, we investigated a hybrid autoregressive-speculative inference (BALANCE) framework for edge LLM inference to balance the latency-memory tradeoff between conventional autoregressive decoding (AD) and speculative decoding (SD). In BALANCE, an edge server hosts both a small language model and a large language model, and simultaneously supports AD and SD for different users with heterogeneous demands. To maximize the number of served users, we formulated a joint user scheduling and computing resource allocation problem under end-to-end latency requirements and server memory constraints. Since this problem is an NP-hard problem, we transformed it into two sub-problems and developed a polynomial-time algorithm with a constant approximation guarantee. The experiment results showed that BALANCE consistently outperforms the conventional AD and SD schemes and achieves significant improvements in task throughput. Overall, BALANCE provides an effective and practical solution for resource-constrained edge LLM inference systems. References [1] Z. Chen, B. Zhu, J. Wang, H. Shin, A. Nallanathan, and D. T. Niyato, “Network edge inference for large language models: Principles, techniques, and opportunities,” ACM Comput. Surv., vol. 58, no. 12, p. 1–35, May 2026. [2] G. Qu, Q. Chen, W. Wei, Z. Lin, X. Chen, and K. Huang, “Mobile edge intelligence for large language models: A contemporary survey,” IEEE Commun. Surveys Tuts., vol. 27, no. 6, p. 3820–3860, Dec. 2025. [3] M. Hu, Q. He, and D. Wu, “QLLMS: Quantization-adaptive LLM scheduling for partially informed edge serving systems,” in Proc. IEEE Int. Conf. Comput. Commun. (INFOCOM), May 2025, p. 1–10. [4] S. Jang and R. Morabito, “Edge-first language model inference: Models, metrics, and tradeoffs,” in Proc. IEEE 45th Int. Conf. Distrib. Comput. Syst. Workshops (ICDCSW), Jul. 2025, p. 309–314. [5] D. Kafetzis, R. Khalili, and I. Koutsopoulos, “Large language model partitioning for low-latency inference at the edge,” in Proc. 23rd Int. Symp. Model. Optim. Mobile, Ad Hoc, Wireless Netw. (WiOpt), Aug. 2025, p. 1–8. [6] A. Agrawal, N. Kedia, A. Panwar, J. Mohan, N. Kwatra, B. S. Gulavani, A. Tumanov, and R. Ramjee, “Taming throughput-latency tradeoff in LLM inference with sarathi-serve,” in Proc. 18th USENIX Conf. Oper. Syst. Des. Implement. (OSDI), Jul. 2024. [7] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser, and I. Polosukhin, “Attention is all you need,” in Proc. Adv. Neural Inform. Process. Syst. (NeurIPS), Long Beach, CA, USA, Dec. 2017, p. 5998–6008. [8] A. K. Jaiswal, B. Hu, L. Yin, Y. Ro, T. Chen, S. Liu, and A. Akella, “FFN-SkipLLM: A hidden gem for autoregressive decoding with adaptive feed forward skipping,” in Proc. Conf. Empirical Methods Natural Lang. Process. (EMNLP), Miami, Florida, USA, Nov. 2024, p. 16 943–16 956. [9] H. Xia, Z. Yang, Q. Dong, P. Wang, Y. Li, T. Ge, T. Liu, W. Li, and Z. Sui, “Unlocking efficiency in large language model inference: A comprehensive survey of speculative decoding,” in Proc. Findings Assoc. Comput. Linguistics: ACL 2024, Aug. 2024, p. 7655–7671. [10] M. Yin, M. Chen, K. Huang, and M. Wang, “A theoretical perspective for speculative decoding algorithm,” in Proc. Adv. Neural Inform. Process. Syst. (NeurIPS), vol. 37, Dec. 2024, p. 128 082–128 117. [11] M. Yan, S. Agarwal, and S. Venkataraman, “Decoding speculative decoding,” in Proc. Conf. Nations Americas Chapter Assoc. Comput. Linguistics: Human Lang. Technol., Albuquerque, New Mexico, Apr. 2025, p. 6460–6473. [12] R. Svirschevski, A. May, Z. Chen, B. Chen, Z. Jia, and M. Ryabinin, “SpecExec: Massively parallel speculative decoding for interactive LLM inference on consumer devices,” in Proc. Adv. Neural Inform. Process. Syst. (NeurIPS), vol. 37, Dec. 2024, p. 16 342–16 368. [13] R. Tiwari, H. Xi, A. Tomar, C. R. C. Hooper, S. Kim, M. Horton, M. Najibi, M. W. Mahoney, K. Keutzer, and A. Gholami, “QuantSpec: Self-speculative decoding with hierarchical quantized KV cache,” in Proc. 42nd Int. Conf. Mach. Learn. (ICML), Jul. 2025, p. 59 668–59 686. [14] J. Zhang, J. Wang, H. Li, L. Shou, K. Chen, G. Chen, and S. Mehrotra, “Draft & verify: Lossless large language model acceleration via self-speculative decoding,” in Proc. 62nd Annu. Meeting Assoc. Comput. Linguistics (ACL), Bangkok, Thailand, Aug. 2024, p. 11 263–11 282. [15] H. Xia, Y. Li, J. Zhang, C. Du, and W. Li, “SWIFT: On-the-fly self-speculative decoding for LLM inference acceleration,” in Proc. Int. Conf. Learn. Represent. (ICLR), Apr. 2025, p. 1–24. [16] J. Jiang, Z. Chen, H. Shin, and A. Nallanathan, “Edge inference for large language models with pipeline parallelism and batching,” IEEE Trans. Commun., vol. 74, p. 8390–8406, Apr. 2026. [17] X. Zhang, J. Nie, Y. Huang, G. Xie, Z. Xiong, J. Liu, D. Niyato, and X. Shen, “Beyond the cloud: Edge inference for generative large language models in wireless networks,” IEEE Trans. Wireless Commun., vol. 24, no. 1, p. 643–658, Jan. 2025. [18] C. Liu and J. Zhao, “Resource allocation in large language model integrated 6G vehicular networks,” in Proc. IEEE 99th Veh. Technol. Conf. (VTC), Sep. 2024, p. 1–6. [19] K. Zhang, H. He, S. Song, J. Zhang, and K. B. Letaief, “Communication-efficient distributed on-device LLM inference over wireless networks,” IEEE J. Sel. Topics Signal Process., vol. 19, no. 7, p. 1301–1317, Oct. 2025. [20] B. Zhu, Z. Chen, L. Zhao, H. Shin, and A. Nallanathan, “Efficient LLM inference over heterogeneous edge networks with speculative decoding,” arXiv preprint arXiv:2510.11331, 2025. [21] Y. Xu, S. Zhou, and Z. Niu, “DiP-SD: Distributed pipelined speculative decoding for efficient LLM inference at the edge,” arXiv preprint arXiv:2604.20919, 2026. [22] X. Li, D. Spatharakis, S. Ghafouri, J. Fan, H. Vandierendonck, D. John, B. Ji, and D. S. Nikolopoulos, “SLED: A speculative LLM decoding framework for efficient edge serving,” in Proc. 10th ACM/IEEE Symp. Edge Comput. (SEC), Dec. 2025. [23] J. Wang, Y. Su, J. Li, Q. Xia, Z. Ye, X. Duan, Z. Wang, and M. Zhang, “OPT-tree: Speculative decoding with adaptive draft tree structure,” Transactions of the Association for Computational Linguistics, vol. 13, p. 188–199, Feb. 2025. [24] T. Liu, Y. Li, Q. Lv, K. Liu, J. Zhu, W. Hu, and X. Sun, “PEARL: Parallel speculative decoding with adaptive draft length,” in Proc. Int. Conf. Learn. Represent. (ICLR), vol. 2025, May 2025, p. 1085–1104. [25] A. Albaseer, E. Bentafat, M. Hamood, M. Abdallah, A. Al-Fuqaha, and M. Hamdi, “Think fast, infer smart: A hybrid distributed LLMs inference at the wireless edge,” in Proc. IEEE 36th Int. Symp. Pers., Indoor Mobile Radio Commun. (PIMRC), Sep. 2025, p. 1–6. [26] D. Ding, A. Mallick, C. Wang, R. Sim, S. Mukherjee, V. Ruhle, L. V. Lakshmanan, and A. H. Awadallah, “Hybrid LLM: Cost-efficient and quality-aware query routing,” in Proc. Int. Conf. Learn. Represent. (ICLR), Vienna Austria, May 2024, p. 1–19. [27] S. Oh, J. Kim, J. Park, S.-W. Ko, J. Choi, T. Q. Quek, and S.-L. Kim, “Communication-efficient hybrid language model via uncertainty-aware opportunistic and compressed transmission,” IEEE Trans. Commun., early access 2026. [28] H. Huang, F. Yang, Z. Liu, Y. Xu, J. Li, Y. Liu, X. Yin, D. Li, P. Ren, and E. Barsoum, “Jakiro: Boosting speculative decoding with decoupled multi-head via MoE,” arXiv preprint arXiv:2502.06282, 2025. [29] M. Fang, Z. Fu, Q. Zhao, and J. Wang, “When, what, and how: Rethinking retrieval-enhanced speculative decoding,” arXiv preprint arXiv:2511.01282, 2025. [30] H. Oh, K. Kim, J. Kim, S. Kim, J. Lee, D.-s. Chang, and J. Seo, “ExeGPT: Constraint-aware resource scheduling for LLM inference,” in in Proc. 29th ACM Int. Conf. Archit. Support Program. Lang. Operating Syst. (ASPLOS), Apr. 2024, p. 369–384. [31] H. Qiu, W. Mao, A. Patke, S. Cui, S. Jha, C. Wang, H. Franke, Z. T. Kalbarczyk, T. Başar, and R. K. Iyer, “Efficient interactive LLM serving with proxy model-based sequence length prediction,” in Proc. 5th Int. Workshop Cloud Intell./AIOps, vol. 5, San Diego, CA, USA, Apr. 2024, p. 1–7. [32] R. Gong, S. Bai, S. Wu, Y. Fan, Z. Wang, X. Li, H. Yang, and X. Liu, “Past-future scheduler for LLM serving under SLA guarantees,” in Proc. 30th ACM Int. Conf. Archit. Support Program. Lang. Oper. Syst. (ASPLOS), Mar. 2025, p. 798–813. [33] G.-I. Yu, J. S. Jeong, G.-W. Kim, S. Kim, and B.-G. Chun, “Orca: A distributed serving system for \Transformer-Based\ generative models,” in Proc. 16th USENIX Symp. Operating Syst. Design Implement. (OSDI), Jul. 2022, p. 521–538. [34] O. Khattab and M. Zaharia, “ColBERT: Efficient and effective passage search via contextualized late interaction over BERT,” in Proc. 43rd Int. ACM SIGIR Conf. Res. Develop. Inf. Retrieval (SIGIR), Mar. 2020, p. 39–48. [35] PyTorch, “Reference API.” [Online]. Available: https://docs.pytorch.org/docs/stable/generated/torch.n.utils.rnn.pad_sequence.html [36] Y. Sheng, L. Zheng, B. Yuan, Z. Li, M. Ryabinin, B. Chen, P. Liang, C. Ré, I. Stoica, and C. Zhang, “FlexGen: High-throughput generative inference of large language models with a single GPU,” in Proc. 40th Int. Conf. Mach. Learn. (ICML), Honolulu, Hawaii, USA, Jul. 2023, p. 31 094–31 116. [37] NVIDIA, “NVIDIA multi-instance GPU user guide release r580,” 2025. [Online]. Available: https://docs.nvidia.com/datacenter/tesla/pdf/MIG_User_Guide.pdf [38] F. Xu, J. Xu, J. Chen, L. Chen, R. Shang, Z. Zhou, and F. Liu, “iGniter: Interference-aware GPU resource provisioning for predictable DNN inference in the cloud,” IEEE Trans. Parallel Distrib. Syst., vol. 34, no. 3, p. 812–827, Mar. 2023. [39] W. Shi, S. Zhou, Z. Niu, M. Jiang, and L. Geng, “Multiuser co-inference with batch processing capable edge server,” IEEE Trans. Wireless Commun., vol. 22, no. 1, p. 286–300, Jan. 2023. [40] H. Shojaei, T. Basten, M. Geilen, and A. Davoodi, “A fast and scalable multidimensional multiple-choice knapsack heuristic,” ACM Trans. Design Autom. Electron. Syst., vol. 18, no. 4, p. 1–32, Oct. 2013. [41] M. Hifi, M. Michrafy, and A. Sbihi, “Heuristic algorithms for the multiple-choice multidimensional knapsack problem,” J. Oper. Res. Soc., vol. 55, no. 12, p. 1323–1332, Jul. 2004.