Striking the Right Balance between Compute and Copy: Improving LLM Inferencing Under Speculative Decoding
Arun Ramachandran 1 , R. Govindarajan 2 , Murali Annavaram 3 , Prakash Raghavendra 1 Hossein Entezari Zarch 3 , Lei Gao 3 , Chaoyi Jiang 3 · 2025
Read Striking the Right Balance between Compute and Copy: Improving LLM Inferencing Under Speculative Decoding by Arun Ramachandran 1 , R. Govindarajan 2 , Murali Annavaram 3 , Prakash Raghavendra 1 Hossein Entezari Zarch 3 , Lei Gao 3 , Chaoyi Jiang 3 (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-12031.txt.
Introduction
Arun Ramachandran and six co-authors cut the cost of running large language models on CPUs by rethinking the key-value cache, the memory that stores attention context token by token. Updating that cache with fresh allocation and copying for every token quietly dominates runtime as sequences grow, while pre-allocating huge padded caches wastes computation instead.
Their mechanism, Balancing Memory and Compute, allocates cache blocks once every few iterations with a few redundant rows, allowing copy-free in-place updates in between. The redundant computation is then repurposed to power speculative decoding, which drafts tokens ahead for verification. One trade, tuned well, pays for the other, a neat accounting trick for CPU inference budgets.
Catalog record
| CREATOR | Arun Ramachandran 1 , R. Govindarajan 2 , Murali Annavaram 3 , Prakash Raghavendra 1 Hossein Entezari Zarch 3 , Lei Gao 3 , Chaoyi Jiang 3 |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 61 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-12031
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Striking the Right Balance between Compute and Copy: Improving LLM Inferencing Under Speculative Decoding Arun Ramachandran 1 , R. Govindarajan 2 , Murali Annavaram 3 , Prakash Raghavendra 1 Hossein Entezari Zarch 3 , Lei Gao 3 , Chaoyi Jiang 3 Abstract With the skyrocketing costs of GPUs and their virtual instances in the cloud, there is a significant desire to use CPUs for large language model (LLM) inference. KV cache update, often implemented as allocation, copying, and in-place strided update for each generated token, incurs significant overhead. As the sequence length increases, the allocation and copy overheads dominate the performance. Alternate approaches may allocate large KV tensors upfront to enable in-place updates, but these matrices (with zero-padded rows) cause redundant computations. In this work, we propose a new KV cache allocation mechanism called Balancing Memory and Compute ( BMC ). BMC allocates, once every r r iterations, KV tensors with r r redundant rows, allowing in-place update without copy overhead for those iterations, but at the expense of a small amount of redundant computation. Second, we make an interesting observation that the extra rows allocated in the KV tensors and the resulting redundant computation can be repurposed for Speculative Decoding (SD) that improves token generation efficiency. Last, BMC represents a spectrum of design points with different values of r r . To identify the best-performing design point(s), we derive a simple analytical model for BMC . The proposed BMC method achieves an average throughput acceleration of up to 3.2 × \times over baseline HuggingFace (without SD). Importantly when we apply BMC with SD, it results in an additional speedup of up to 1.39 × \times , over and above the speedup offered by SD. Further, BMC achieves a throughput acceleration of up to 1.36 × \times and 2.29 × \times over state-of-the-art inference servers vLLM and DeepSpeed, respectively. Although the BMC technique is evaluated extensively across different classes of CPUs (desktop and server class), we also evaluate the scheme with GPUs and demonstrate that it works well for GPUs. I Introduction LLMs have been deployed for a variety of tasks such as chatbots and virtual assistants [ 2 , 13 , 7 ] . Improving their execution efficiency is key to making them affordable to the broader societal needs. But LLM inference latency is hobbled by large memory management overheads for the KV (key-value) cache, which is a constantly expanding data structure. In this paper, we focus on the LLM decode phase, which consists of L transformer layers, and within each layer, there is an attention block and a multilayer perceptron (MLP) computation. The attention block computes self attention using Key ( K ) and Value ( V ) tensors which are of dimension [B,L,n,D] , where B is the batch size, D is the embedding or hidden dimension size, n is the number of tokens generated so far (including the initial prompt), and L is the total number of layers in the model 1 1 1 Some literature reports the dimension as [L,B,n,D] , with the layer dimension ( L ) as the first dimension, since the tensors are stored separately for each layer. . The computation of self attention is performed as a Scaled Dot Product Attention (SDPA). SDPA involves two matrix multiplications: (i) Query ( Q ) with Key Transpose, which is scaled to get the Attention scores and (ii) Attention scores with Value matrix. With a batch size greater than 1 or with multiple heads, self-attention computation can be performed efficiently as a batch matrix multiplication (BMM). To avoid performance drops and maintenance burdens of custom kernels, efficient BMM computation demands that the Key and Value tensors occupy contiguous blocks of virtual memory [ 44 ] . Due to the auto-regressive nature of the decode stage, the size of K and V tensors increases by one column for each iteration. Typically, this growth in memory size is handled by allocating larger K and V tensors of dimension [B,L,(n+1),D] after each token generation. This approach, referred to as the iterative allocation approach, was followed in HuggingFace’s implementation [ 28 ] . The self-attention computation for the (n+1) -th token depends on values of K and V calculated in the previous n iterations. To avoid recomputing these tensors, the Key-Value (KV) cache mechanism [ 22 ] was proposed which copies the K and V tensors of the n -th iteration in the respective tensors of the current iteration in a strided manner to account for the increase in the second last dimension. This operation, referred to as the KV cache update , involves two major tasks, allocating memory for the K and V tensors in each iteration and copying the K and V tensors. These two tasks incur significant overhead in the attention block computation. To overcome the above overheads, one could propose an upfront allocation , which allocates the K and V tensors once for the maximum context length ( N ). The unused elements (corresponding to future tokens) are initialized to 0. The K and V vectors computed in each iteration are written in the appropriate location in the larger K and V tensors. Static upfront memory allocation might create internal fragmentation limiting batchsize and throughput as noted in [ 44 ] . The other challenge with upfront allocation is whether to perform matrix multiplications on the entire KV cache, including the dummy values, or to selectively use only the valid values in the KV cache. Selective use of only valid values requires BLAS kernel with strided access (to filter out the dummy zero values). Our experimental results (see Section VIII-H5 ) show that the SDPA computation is up to 14.4 \times slower with strided access, compared to performing GeMV operations on a full matrix of K and V tensors, including the computations on padded zeros. Contribution #1: Given these tradeoffs, we make the case for using a hybrid approach that straddles between iterative and upfront allocations, ensuring contiguity in virtual address space. More specifically, we design a new memory allocation scheme, called Balancing Memory and Compute or BMC , which enables iterative allocation, once every r iterations, of K and V tensors having r additional rows and performing a limited number of wasteful computations (of at most r elements) in the next (r-1) iterations. Thus it balances the overheads due to wasteful computation with memory allocation and copying operations, while continuing to leverage the vast set of optimized libraries enabled out-of-box. Contribution #2: This approach of allocating r redundant memory rows can still lead to wasteful computations, albeit much less than upfront allocations. We then make an interesting observation to exploit these wasteful redundant rows: Most LLMs today use Speculative Decoding (SD) [ 35 , 36 , 10 ] . SD is a technique that significantly accelerates LLM inference latency without sacrificing output quality, and with minimal resource overhead. SD leverages one or more smaller draft models to generate predictions efficiently for future tokens. Given that BMC allocates r redundant rows we make the case for repurposing these r redundant rows to temporarily store the speculatively decoded K and V tensors thereby significantly eliminating padded zero computations. As SD verifies the speculated tokens together,