Latest / EDGE AI POD / Tomorrow's Edge AI: Cutting-Edge Memory Optimization for Large Language Models with Seonyeong Heo of Kyung Hee University

Transcript

Tomorrow's Edge AI: Cutting-Edge Memory Optimization for Large Language Models with Seonyeong Heo of Kyung Hee University · EDGE AI POD

• 0:24
  Speaker 1: Hi Se-young, it's your time.
• 0:27
  Speaker 1: Thanks to join us, and the title of your presentation is Memory Optimization for On-Device LLM, which is a great topic.
• 0:38
  Speaker 1: So the floor is yours.
• 0:40
  Speaker 2: Okay, hello, I'm Seon-young from Kyung-hee University, so I'm very happy to share my recent investigation on memory optimization for on-device LLM.
• 0:52
  Speaker 2: So before starting my presentation, I would like to briefly introduce myself.
• 0:59
  Speaker 2: So I'm an assistant professor at Kyunghee University, which is located in South Korea.
• 1:04
  Speaker 2: Assistant professor at Kyunghee University, which is located in South Korea.
• 1:08
  Speaker 2: So before joining Kyunghee University, I was a postdoctoral researcher at ETH and research scholar at Virginia Tech.
• 1:11
  Speaker 2: So my research interests include tiny machine learning, especially for memory optimization, and also compiler optimization for machine learning and real-time embedded systems compiler optimization for machine learning and real-time embedded systems.
• 1:28
  Speaker 2: So our goal is to enable large language models on small computing systems, and we all know large language models are large in size.
• 1:36
  Speaker 2: So the most popular models considered for on-device AI is LLMs with 7 billion parameters, which requires around seven gigabytes for their model parameters when they are quantized for 8-bit precision.
• 1:50
  Speaker 2: Since small computing systems have limited memory size around four to eight gigabytes the even 7 billion models hardly fit in their memory.
• 2:02
  Speaker 2: So enabling on-device LLM is like putting a llama inside a refrigerator.
• 2:09
  Speaker 2: However, llms actually need much more memory than that, so in the next slide I will explain exactly for what they need more memory.
• 2:22
  Speaker 2: So at first, I would like to start with the original transformer.
• 2:28
  Speaker 2: So this is the overall structure of transformer first proposed in the NeurIPS 2017 paper.
• 2:35
  Speaker 2: So it basically consists of a pair of an encoder and a decoder, where the encoder extracts the features from the input and the decoder uses the features from both input and output to make a prediction.
• 2:49
  Speaker 2: Unlike the original transformer, many popular generative LLMs, such as GPT and LLAMA, are decoder-only transformers, which directly takes the input and makes a prediction based on the input.
• 3:08
  Speaker 2: In this talk, we will consider decoder-only transformers.
• 3:12
  Speaker 2: Those decoder-only LLMs are often called autoregressive transformers, in that they generate a new token and append the new token to the input to generate the next token after the token.
• 3:29
  Speaker 2: So, for example, let's assume that the model is given an initial input what is tiny Then the model processes the input and generates the next token.
• 3:41
  Speaker 2: So here the token tiny is chosen as the next token.
• 3:45
  Speaker 2: So then the next token is appended to the input and the model process the input with the new token.
• 3:54
  Speaker 2: So after then they generate the token again after the new token.
• 4:02
  Speaker 2: So the model repeats this process until it generates the maximum number of tokens or encounters the end of tax token.
• 4:10
  Speaker 2: So this recursive behavior is referred to as autoregressive.
• 4:16
  Speaker 2: So this autoregressive behavior requires one forward step per token generation.
• 4:27
  Speaker 2: That means when the model generates n tokens the model has to be processed n times in total.
• 4:35
  Speaker 2: So therefore autoregressive transformers may incur high computational overhead and it makes it difficult to deploy large language models in small computing systems.
• 4:50
  Speaker 2: Then how to reduce the high computational overhead of large language models?
• 4:54
  Speaker 2: So nowadays most of LLM frameworks support caching, the intermediate outputs of attentions.
• 5:02
  Speaker 2: So looking into the decoder architecture, it consists of a series of multi-head attentions.
• 5:09
  Speaker 2: So as the input gradually grows over time they try to avoid duplicate computations between different forward steps.
• 5:20
  Speaker 2: So the basic computation of attention is illustrated in this slide.
• 5:26
  Speaker 2: So first the attention generates the query, key and value arrays by applying the separate linear layers to the input, and then it multiplies the query and key arrays and softmax, the key QK array, to compute to the attention score.
• 5:51
  Speaker 2: So here softmax is omitted for simplicity, but it is applied to the QK array and the output array is multiplied to the V array.
• 6:06
  Speaker 2: So here the key value cache is introduced to reduce the overhead of obtaining the key and value arrays.
• 6:16
  Speaker 2: So, as explained earlier, the new token is appended to the input every forward step.
• 6:23
  Speaker 2: So therefore, we don't have to calculate the k and v values for the previous tokens.
• 6:29
  Speaker 2: So then, instead of generating the key and value arrays every time, it stores the k and v values in the memory and reuses them for the next forward step.
• 6:40
  Speaker 2: So since the linear layer, which entails matrix multiplication, is generally computationally very expensive, using KV cache can largely reduce the computational overhead.
• 6:56
  Speaker 2: The memory usage of KV cache can be calculated with this formula the KV cache size is 2 times p, times the number of layers and the number of attention head times and the token dimension and w.
• 7:15
  Speaker 2: So here 2 is multiplied because it has to store k and v, and then p indicates the number of bits for representing the k and v, and then p indicates the number of bits for representing the k and v values.
• 7:26
  Speaker 2: And then also, here w denotes the context window size, which is the number of tokens to be used for generating the next token.
• 7:37
  Speaker 2: So it is also called sequence length.
• 7:39
  Speaker 2: To show how large KVCache is, we measured the memory usage of a couple of large language models on top of the LAMA C++ framework.
• 7:54
  Speaker 2: The graph shows the memory usage of each model for sorting their weights the blue bars and KVCache, the orange bars and the activations yellow bars.
• 8:04
  Speaker 2: So here it is shown that for 7 billion models KV cache can be almost as large as the model parameter size.
• 8:13
  Speaker 2: So in the case of Mistral 7 billion model the size of KV cache is 4 gigabytes.
• 8:20
  Speaker 2: So that is, if we quantize the model for lower precision, then the memory overhead of KVCache would become dominant compared with the other components.
• 8:37
  Speaker 2: There have been various approaches to reducing the memory overhead of KV cache.
• 8:42
  Speaker 2: One popular approach is to redesign a model with a different type of attention, as illustrated in the figure.
• 8:51
  Speaker 2: Multi-head attention is a typical type of attention used in transformers.
• 8:56
  Speaker 2: Groove query attention and multi-query attention are newly introduced types of attention which can reduce the size of KV cache by using a less number of key and value tokens.
• 9:09
  Speaker 2: So this grouped query attention is already applied to the LAMA2 model, which is one of the new features of the model.
• 9:21
  Speaker 2: So another approach is to manage KV cache in a page fashion.
• 9:25
  Speaker 2: So in general KV cache is implemented as a ring buffer, but it may suffer from internal or external fragmentation when there are multiple users that share the KV cache.
• 9:38
  Speaker 2: So it can result in underutilization of the memory space.
• 9:43
  Speaker 2: So therefore this SOSP paper proposes to bring the concept of paging to manage KV cache.
• 9:53
  Speaker 2: So it swaps in the cached values into GPU memory when they are needed.
• 9:59
  Speaker 2: So, however, this approach assumes a very large system with multiple users and multiple batches and also a dedicated GPU that has its own memory.
• 10:12
  Speaker 2: So this approach is not appropriate for optimizing on-device LLMs.
• 10:22
  Speaker 2: So to further reduce the memory usage of KV cache, we tried dynamically compressing KV values before we put the values into the cache so that they consume less memory space.
• 10:36
  Speaker 2: So we investigated a variety of compression methods, so dynamic quantization, dynamic pruning and dynamic dimensionality reduction.
• 10:47
  Speaker 2: So first I would like to discuss the dynamic quantization of KV values.
• 10:54
  Speaker 2: So there are three main types of quantization.
• 10:57
  Speaker 2: The first one is linear quantization, which is the most common type of quantization and it chooses the linearly spaced values for quantization, as illustrated in this graph.
• 11:11
  Speaker 2: And the second one is log quantization, where the gap between two values grows in a log scale.
• 11:20
  Speaker 2: And the last one is weighted quantization, which is relatively newer quantization method than the others.
• 11:27
  Speaker 2: So the method clusters the values to reflect the distribution of values and then use the clustering information for quantization.
• 11:39
  Speaker 2: Clustering information for quantization.
• 11:43
  Speaker 2: So the histogram on the left side illustrates the distribution of KV values for some sample inputs.
• 11:50
  Speaker 2: So first we can see that the KV has a very wide range of values, from minus 20 to 20.
• 11:58
  Speaker 2: So while convolutional neural networks models usually have a much smaller value range, from 0 to 1 or minus 1 to 1, the deviation of values in KV is relatively large.
• 12:14
  Speaker 2: And also there are not many small values in KV.
• 12:19
  Speaker 2: So we can only see a very thin bar in the histogram around the zero.
• 12:26
  Speaker 2: So we measured the average quantization error to compare different quantization methods.
• 12:34
  Speaker 2: So the results show that the quantization error decreases when the data precision becomes higher.
• 12:42
  Speaker 2: So for the 5-bit quantization it obtains the high compression quantization error and then with the 8-bit quantization it obtains much less quantization error.
• 12:59
  Speaker 2: So when the precision is low, weight quantization obtain much less quantization error than the other method.
• 13:08
  Speaker 2: However, with higher data precision weight quantization does not perform very well.
• 13:14
  Speaker 2: We guess that with high data precision it has to have more clusters for quantization.
• 13:26
  Speaker 2: So maybe it has some difficulty in finding a good clustering from the data.
• 13:37
  Speaker 2: And we also tried unstructured pruning and structured pruning to compress kV values.
• 13:42
  Speaker 2: In structured pruning the values that are smaller than the pruning threshold are pruned separately.
• 13:52
  Speaker 2: In structured pruning the entire tokens with small values are pruned from the token array and compared to unstructured pruning, structured pruning has an advantage in storing sparse data because it does not need a very complex data structure to memorize the location of each value.
• 14:15
  Speaker 2: So for measuring the compression error we set the target sparsity, which gives a similar compression rate to quantization.
• 14:25
  Speaker 2: So as expected, structured pruning obtained much higher compression error than unstructured pruning.
• 14:33
  Speaker 2: But overall unstructured pruning failed to outperform the quantization method.
• 14:40
  Speaker 2: Structure pruning failed to outperform the quantization method.
• 14:44
  Speaker 2: So, as we saw in the previous slide, the KV arrays have very few small values around 0, so pruning may not work very effectively for compressing their values.
• 14:59
  Speaker 2: So lastly, we tried reducing the dimension of KV tokens using an autoencoder.
• 15:04
  Speaker 2: So an autoencoder model consists of an encoder and a decoder, where the encoder encodes the input data, lowering its dimension, and the decoder decodes the encoded data to recover the original dimension.
• 15:21
  Speaker 2: Then we can reduce the memory usage of KV cache by storing the encoded data in the middle into the KV cache.
• 15:31
  Speaker 2: So applying the dimensionally reduction dynamically means that we have to run the encoder and decoder in the middle of the model execution.
• 15:46
  Speaker 2: Therefore we have to make sure that the autoencoder should be lightweight enough not to incur large computation and memory overheads.
• 15:57
  Speaker 2: Then we designed a very small autoencoder which applies 1D convolutions to each token of KV, then it can like halve the dimension of the token.
• 16:10
  Speaker 2: So we can formally define the compression overhead of the autoencoder as follows Assuming that the encoder consists of two one-dimensional convolution layers, the number of floating-point operations is approximately the token dimensions times kernel size, times the number of input and output channels, then this compression overhead has to be lower than the GenV overhead, because if the compression overhead is higher than the GenV overhead then there is no point of compressing KV values.
• 16:54
  Speaker 2: Then there is no point of compressing kv values.
• 16:56
  Speaker 2: So, considering the compression overhead, we designed a very small autoencoder with three one-dimensional convolution layers and measured the compression error for comparison.
• 17:09
  Speaker 2: So, compared to quantization and pruning, the autoencoder suffers from high compression error, although some more optimization may be possible by tuning the hyperparameters of the autoencoder.
• 17:27
  Speaker 2: So here is the comparison table of dynamic compression methods.
• 17:34
  Speaker 2: So in terms of compression error, we saw that the weighted quantization can obtain much lower compression error than the other method.
• 17:43
  Speaker 2: So, conversely, dynamic pruning obtained relatively higher compression error because, as we saw in the histogram, the original sparsity of kv arrays is not that high.
• 18:00
  Speaker 2: And then, regarding the computational overhead, the dynamic quantization incurs very low overhead because it only has to find the nearest value among the possible values.
• 18:15
  Speaker 2: And then dynamic pruning requires some computational overheads for processing the sparse data because it has to format the sparse data with some sparse data formats such as compressed, sparse load.
• 18:33
  Speaker 2: So it incurs some overhead for processing the sparse data format.
• 18:40
  Speaker 2: And dynamic dimensionality reduction incurs more overhead because it has encode and decode the data in the middle of the execution.
• 18:53
  Speaker 2: And next, the memory overhead for dynamic quantization is almost none because we only need to store a few quantization parameters for dynamic quantization.
• 19:10
  Speaker 2: And then, in terms of compression rate control, dynamic pruning can allow fine-grained control of sparsity by changing the pruning threshold.
• 19:23
  Speaker 2: And then the dynamic pruning also does not need fine-tuning because it only prunes values that are less than the threshold.
• 19:35
  Speaker 2: However, the dynamic quantization, especially weighted quantization, needs fine-tuning to find the optimal clustering for KV values.
• 19:46
  Speaker 2: So in conclusion, kv cache is introduced to reduce the computational overhead of autoregressive transformers.
• 19:57
  Speaker 2: However, the KV cache can be as large as model size, which is not ideal for small computing systems with limited memory size.
• 20:09
  Speaker 2: So this talk explores various methods for reducing the memory overhead of KV cache for on-device LLMs.
• 20:19
  Speaker 2: This talk shows that weighted quantization can obtain high compression rate with small errors compared with different dynamic compression methods.
• 20:30
  Speaker 2: This is the end of my talk.
• 20:34
  Speaker 2: Thank you for your attention and I will be happy to take any questions.
• 20:43
  Speaker 1: Thank you so much for your great talk, kacen Young.
• 20:45
  Speaker 1: You know optimizing the memory for llms and and gen I is a super important topics, especially with respect to the energy efficiency, even if I'm not a great expert.
• 21:03
  Speaker 1: Maybe I would like to let you comment a bit about two aspects.
• 21:10
  Speaker 1: One is about the kiwiache and, in particular, the accesses.
• 21:17
  Speaker 1: During your studies, did you observe the correlations that can be exploited in both the accesses and the usage of the cache?
• 21:32
  Speaker 2: What do you mean by the correlation?
• 21:34
  Speaker 1: The correlation between, correlation between accesses over the time, or even the values which are accessed.
• 21:47
  Speaker 2: Ah, so between the over time you mean correlation over time, yeah, of the addresses generated.
• 21:57
  Speaker 1: For example, you tend to access, during the operation of the LLM, this part of the cache which is very close to another part of the cache, because of the natural, let's say, operations of the LLM.
• 22:14
  Speaker 1: If there are patterns which are privileged.
• 22:18
  Speaker 2: Yeah, kv cache is not hardware cache, so it's stored in memory.
• 22:24
  Speaker 2: So actually it is accessed sequentially when the model predicts it generates its token.
• 22:33
  Speaker 2: So I think the access pattern of kvcache is quite regular.
• 22:41
  Speaker 1: so, but um the access can be even predicted ahead of time yes, yes, uh.
• 22:48
  Speaker 2: So yeah, it can like um accelerate the the access of the memory if we can free fetch the KV cache for future processing.
• 23:01
  Speaker 1: There is a question from Chris.
• 23:02
  Speaker 1: Do you have an example of compression on a common LLM?
• 23:10
  Speaker 2: Compression on a common LLM.
• 23:11
  Speaker 1: Yeah, maybe models from Jürgen's phase on which you tested more or less extensively the effect of compression.
• 23:24
  Speaker 1: I tested and you know the techniques you mentioned during the presentation.
• 23:30
  Speaker 2: Yeah, I tested the dynamic compression methods with LAMA 2, 7 billion models.
• 23:38
  Speaker 2: So I am considering of open opening my code for public so that you can easily apply the dynamic dynamic compression for for your any like large language models.
• 24:10
  Speaker 1: So that would be very interesting.
• 24:13
  Speaker 1: Yes for the community, I guess.
• 24:16
  Speaker 1: When do you plan to do that in the near future?
• 24:22
  Speaker 2: In the near future, maybe before the 2024 ends.
• 24:31
  Speaker 1: Okay, thank you.
• 24:31
  Speaker 1: Okay, thank you In terms of implementation.
• 24:35
  Speaker 1: Did you also study KiwiCache with respect to memory computing?
• 24:47
  Speaker 1: Are there operations which could be nicely accelerated within the memory.
• 24:59
  Speaker 2: Okay, Dynamic quantization dynamic pruning.
• 25:02
  Speaker 1: you know this type of operations that could have a place in some hardware tightly coupled or inserted within the memory itself, even if it's large.
• 25:19
  Speaker 2: That's a good point because KV cache is for reducing the overhead of computing the K and V values.
• 25:28
  Speaker 2: So I think if the dimension is very large, then it can be processed in memory.
• 25:35
  Speaker 2: The dimension is very large, then it can be processed in memory, processed with in-memory computing without like a heavy, like memory accesses from between CPU and memory.
• 25:45
  Speaker 2: So I think there will.
• 25:47
  Speaker 2: There are many opportunities for processing very large data inside memory.
• 25:55
  Speaker 2: But as far as I know, there are many approaches to apply and accelerate well, matrix and vector multiplication inside the processing memory.
• 26:11
  Speaker 2: So yeah, and also I think the dynamic compression can be done inside the memory if we need to save more, reduced, more computational overhead do you think I'm, I'm trying to you know, to look ahead?
• 26:39
  Speaker 1: do you need, do you think there are opportunities maybe for other type of lms, to push the dynamic quantization at the extreme?
• 26:50
  Speaker 1: Which means one bit.
• 26:52
  Speaker 1: One bit per sample, per data.
• 26:57
  Speaker 2: Because I tested five-bit quantization but already it suffered from large quantization error even with the-bit.
• 27:09
  Speaker 2: Because I think for the weight we can apply lower precision quantization but for activation it is more difficult to apply the quantization because of this region of the data, because it depends on the input data, so it is more difficult to predict the characteristics of data.
• 27:41
  Speaker 2: Yeah, I want to more investigate the data distribution to optimize the quantization method, because I think maybe the weighted quantization is not still suboptimal for large language models.
• 28:09
  Speaker 2: So I think there is the next step to forward the research.
• 28:18
  Speaker 1: Thank you.
• 28:19
  Speaker 1: Another question from Chen Liu.
• 28:23
  Speaker 1: I just asked Arniban.
• 28:28
  Speaker 1: One further minute of patience, please.
• 28:30
  Speaker 1: Chen Liu is asking how do people manage memory of KV cache in hardware like GPU, for example, reserve a maximum token size and date KV cache token by token, or allocate new memory section for each new token of the cache?
• 28:51
  Speaker 1: That's the last question for you.
• 28:53
  Speaker 2: Yeah, that's a good question.
• 28:55
  Speaker 2: So I tested the measure, the memory usage, on top of llama c plus plus framework.
• 29:02
  Speaker 2: In the case of the framework, it allocates the maximum of the framework.
• 29:14
  Speaker 2: It allocates the maximum token size, the KV cache for the maximum token size.
• 29:17
  Speaker 2: So it reserves large space at the beginning and it gradually puts tokens inside the KV cache cache and then.
• 29:35
  Speaker 2: Yeah, so I think the paper I introduced in the presentation wants to move from the fixed allocation to page allocation to reduce the internal memory fragmentation.
• 29:49
  Speaker 1: Thank you so much, Chen.
• 29:50
  Speaker 1: It was really appreciated your time and your contribution for today.
• 29:56
  Speaker 1: Thanks a lot also for your availability to answer some questions.
• 30:01
  Speaker 1: Really appreciated this and Jung Bye.