NoMAD-Attention: Efficient LLM Inference on CPUs Through Multiply-add-free Attention
Authors: Tianyi Zhang
Jonah Wonkyu Yi
Bowen Yao
Zhaozhuo Xu
Anshumali Shrivastava
Venue: NeurIPS 2024 poster (2024)
Keywords: large language model
efficiency
CPU inference
attention
Primary area: other

Abstract: Large Language Model (LLM) inference on Central Processing Units (CPU) is challenging due to the vast quantities of  Multiply-Add (MAD) matrix operations in the attention computations. This paper highlights a rare gem in modern CPUs, Single-Instruction-Multiple-Data (SIMD) registers, which allows for ultra-low-latency lookups in a batch. We leverage this unique capability to propose NoMAD-Attention, an efficient attention algorithm that replaces MAD operations with in-register lookups. Through hardware-aware algorithmic designs, NoMAD-Attention achieves the computation of attention scores using repeated fast accesses to SIMD registers. NoMAD-Attention works with pre-trained attention-based LLMs without model finetuning. Extensive empirical evaluations demonstrate that NoMAD-Attention maintains the quality of the original LLMs well and speeds up the 4-bit quantized LLaMA-7B-based model by up to $2 \times$ at 16k context length.

NoMAD--Atention: Efficient LLM Inference on CPUs Through Multiply-add-frre Attention
Tianyi Zhang
Jonah Yi Dept. of Computer Science, Rice University xMAD.ai Houston, TX juy4@rice. .du
Bowen Yao Dept. of Computer Science, Rice University Houston, TX by18@rice... edu
Dept. of Computer Science,
Rice University xMAD.ai
Houston, TX edu
Zhaozhuo Xu
Anshumali Shrivastava
Dept. of Computer Science, Stevens Institute of Technology
Dept. of Computer Science, Rice University Ken Kennedy Institute
xMAD.ai Hoboken, NJ zxu79@stevens.cm edu
ThirdAI Corp.
xMAD.ai Houston, TX anshumal cetemmll@rrcaa ieriiiireeeee edd
Abstract
Large Language Model (LLM) inference on Central Processing Units (CPU) is challenging due to the vast quantities of Multiply-Ade (MAD) matrix operations in the attention computations. This paper highlights a rare gem in modern CPUs, (SIMD) registers, which allows for ultra-low- latency lookups in batch. We leverage this unique capability to propose NoMAD- Attention, an efficient attention algorithm that replaces MAD operations with in- register lookups. Through hardware-aware algorithmic designs, NoMAD-Attention achieves the computation of attention scores using repeated fast accesses to SIMD registers. NoMAD-Attention works with pre-trained attention-based LLMs without model finetuning. Extensive empirical evaluations demonstrate that NoMAD- Attention maintains the quality of the original LLMs well and speeds up the 4-bit quantized LLaMA-7B 7B-based model by up to 2 at 16k context length.
cnsutructionMuulipphee
Introduction
Auto-regressive mansformer-basee Large Language Models (LLM) demonstrate remarkable abilities across wide range of natural language processing tasks without finctuning 35] and exhibit emergent abilities [49 for solving complex problems.
The Need for Deploying LLM CPUs. Despite the potential of LLMs, their deployment is costly [27]. Serving LLMs with billion-scale parameters requires specialized hardware such as NVIDIA 100 Graphics Processing Units (GPUs) (55). However, mainstream personal devices are predominately equipped with only Central Processing Units (CPUs) 43]. As a result, making L.LM-related services accessible to everyone remains major challenge. Reducing the LLM inference latency on CPUs would significantly influence its accessibility and adoption.
Expensive Multiply-ade Operations for Attention in LLM Inference. LLM inference CPUs compute-boune bound, and the primary computational bottleneck the calculation of attention scores 21 Attention, mechanism that models token interactions through all-pair dot products, heavily
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

relies on the multiply-ade (MAD) kernel on processors. The MAD operation involves computing the product of two numbers and adding that product to an accumulator 44 MAD plays a crucial role in determining the attention score between tokens and subsequently blending their embeddings within the attention mechanism. The computational cost of attention grows quadratically with the sequence length due to the cumulative MAD operations. Since CPUs have limited parallel cores, they are inefficient for handling highly repetitive and parallel workloads. The extensive MAD operations required by the attention mechanism thus become the primary bottleneck during inference.
The memory hierarchy of modern CPUs has undergone significant evolution. introducing new type of registers optimized for Single-Instruction Iittruction-Mulippe Data (SIMD) operations. The SIMD registers vary in size, ranging from 128 bits to 512 bits [41, and support specialized SIMD instructions for high- high-throughhut parallel
Opportunities and Challenges from Modern CPUs: In-Register Lookups.
processing [59] SIMD registers have become a standard feature in commodity hardware, including laptops and mobile devices [3]. In this context, an in-register lookup (or shuffle) refers to the low-lateney random access of information stored within SIMD registers. Storing information such as dot-product lookup tables (LUT) within SIMD registers, as opposed to cache memory, can accelerate LLM inference [4]. However, the limited size of SIMD registers poses challenges to fitting the computational paradigm of existing models.
Our Proposal: MAD-Free Attention with In-Register Lookups. Our paper demonstrates a new approach for speeding up LLM inference by leveraging the unique hardware capability of CPUs. We show how the vast quantities of MAD operations attention computation can be replaced with in-register lookups to mitigate the quadratic computational bottleneck of LLM inference on CPUs. NoMAD-Attention significantly speeds up LLM inference without sacrificing model quality and compatible with pre-trained attention- transformers without finetuning.
We summarize our contributions follows:
We identify the extensive MAD operations attention as the bottleneck of CPU LLM inference and we replace them with fast in in-register lookups.
2. We introduce NoMAD-Atteatoon a MAD-free framework of attention computation for pre-trained attention-basee LLMs. NoMAD-
leverages hardware- algorithmic designs to enable accurate and fast in-register lookup-based estimations of query-key dot products despite the limited capacity of SIMD) registers. NoMMAD-Attntion preserves model quality while yielding considerable speedups over MAD-based attention.
3. Our extensive experiments demonstrate that NoMAA--ttention achieves up 2x speedup on LLaMA-7B--ased models with 4-bit weights at a context length of 16k while maintaining the predictive performance of the original model.
2 LLM Inference on CPUs
This section introduces the attention mechanism used in LLMs and the key-value (KV) caching technique for avoiding redundant attention computations. We also discuss the CPU memory hierarchy, which motivates the use of fast in-register lookups.
2.1 LLM Attention
Most LLMs are decoder-only snteettion-baede models that are pre-trained on a next token prediction objective. LIMs use masked self-attention, which allows L.MMs to cache key and value embeddings to avoid future recomputations. However, this comes at the cost of memory overhead. The autoregressive generation of LLMs consists of two phases: 1. prompt processing: the sequence of token embeddings in the prompt is fed through by the model, and their key-value embeddings are cached by the model; and 2. decoding: a new token is sampled based the output embedding of the last token, and the embedding of the new token is fed through the model, the output of which becomes the basis for sampling the next token. The decoding process continues until an end-of-sequence token <EDS> is sampled.
At the decoding step I, a single-head masked self-attention computes its output in the following way. The embedding of the current token el is transformed into key, query, and value embeddings through distinct transformations K²' = fx((e), fo(e'), of fv())..
2

---

Algorithm Attention Score Computation in LLM
1: Input: query g', key k", key cache K
K Kt- cache
2: let K cache +
b Append the current key to key cache
h
o (KKK mncian
3: return softmax
vd
Then, the key and value embedding of the current token are appended the key and value cache, respectively. The KV cache cache: Vihcl of the step t 1 contains the key/value embeddings of all previous tokens, and after appending, the KV cache become
h k2
[K-- enche
Vt-1 cagha
2
Kt rache
Vt cache
ke
Finally, the attention output is computed as
g" (accea
attention(e") softmax
Vicche
Vd
where d is the dimensionality of q². We will refer to the result of softmax( scores since they dictate how much "attention" each token pays to other tokens. Computations in the prompt processing phase are similar to those in the decoding phase, except all the prompt tokens computed in batch. LLMs use multi-head attention, which transforms the concatenation of the outputs of multiple single-head attentions to form an output embedding.
vi as the attention
MAD-based Attention. The attention mechanism models the interaction between tokens by perform- ing all- ulli dot products, where each dot product is computed via d Multiply-Add (MAD) operations. Since attention computes the interaction between all pairs of tokens, the amount of MAD operations scales quadratically with the sequence length, quickly overwhelming the computing capability of CPUs. CPUs are designed to handle complex workloads with granular control, while GPUs are opti- mized for processing simple and repetitive tasks in high throughput. Hence, the success of attention has largely been fueled by the development of highly parallel throughput-oriented processors, such as GPUs 12].
MAD-based Attention as Bottleneck of LLM Inference. The computation of attention scores becomes the bottleneck of LLM inference as the sequence length increases (see our analysis in Figure 4. At the t-th step of the decoding phase, the time complexity of computing attention score with MAD Ott) due dot products, while all other components of LLMs such as MLP, skip connections. and normalization have time complexity of O(1). We will focus optimizing the efficiency of attention score computations our proposed approach. Algorithm presennts the pseudocode for attention score computation, including key caching, for single-head masked self-attention in L.M.. This algorithm will serve as a point of comparison our proposed approach.
I
2.2 Memory Hierarchy of Modern CPUs
CPU memory is organized into a pyramidal hierarchy, as shown in Figure 1 with faster memory significantly smaller than slower memory. The memory unit with the fastest access speed is the registers. Fach compute core accesses its dedicated registers in just 1-2 CPU cycles, but these registers limited in size, usually not exceeding 64 bits. Modern processors include new type registers optimized for 128 bits to 512 bits size and support limited set of SIMD instructions for throughput-oriented parallel processing. SIMD registers are common mobile devices. Using SIMD operations can speed up deep learning models on CPUs by parallelizing matrix multiplications. However, due to the limited number of cores in CPU, its efficiency in deep learning still considerably worse than GPU. Prior works 42 have resorted to sparsity and sampling-bul baasdd approaches, but they require training models from scratch and may not apply to all architectures. Our approach exploits the SIMD registers to shift the computation paradigm from MAD to in-register lookups, which demonstrates significant speedup over MAD-based models.
-uuructeon-MMliileeee- Data (SIMD) operations. These SIMD registers range from
commodity hardware, including laptops and
3

---

NoMAD Attention
LLM Attention Koodis
NoMAD Lookup-based baseddd-aeeddd Astention-scom Computation
Transposed Blocked code
fp32
byte
Guantoed
SIMD Registers 2072
SIMD Shuflo Acoumulato
of (o..... 15)
Figure I: A comparison of memory layouts of the key cache LLM attention (left) and the key-code cache of NoMAD-Attente (middle)) and an illustration of how attention scores computed through in-register lookups NoMAD-Attentin (right).
When describing our proposed algorithm, we assume SIMD registers are 128 bits wide. Some systems with wider SIMD registers support parallelism, e.g.. 256-bit registers in AVX-2 and 512-bi bit registers AVX-512. However, the most universal form of SIMD registers uses 128 bits, which is supported by Arm NEON and AVX-compatible processors.
Methodology
This section describes proposed approach, NoMAD-Attenions which replaces MAD operations with in-register lookups to enable faster attention computations on CPUs. NoMAD-Attention utilizes three techniques enable lookup-based attention: 1. transforming dot product computations to memory lookups through product quantization, 2. compressing lookup tables into SIMD registers for low-latency access, 3. reorganizing the memory layout of key cache for batch parallel dot product lookups.
3.1 Transforming Dot-prot Dot-products into Lookups
Previous works have shown that inexact attention scores in transformers work well for sequence mod- cling [53] NoMAD leverages Product Quantization (PQ) [23 to compute high-quality estimations of dot products through in-register lookups. PQ, originally designed for compressing high- -igeediiensional vectors, quantizes a floating point vector into discrete codes. It makes use of sub- wub-quantizers; for d-dimensional vector space, vector divided evenly in dimension into sub-vectors where each sub-vector has dimension dgub 3, and each sub-vector space is quantized independently. We use (e), where E (1... 5}. to denote the function that maps a d-dimensional vector to its -ineennnnii sub-vector of the s-th sub-quantizer. Codebooks are used quantize sub-vectors codes, which are collections of cluster centroids learned from a set of calibration vectors. We use by.c to denote the c-th centroid in the codebook of the s-th sub- quantuuntizer. For given vector e, the product-quantizee quantized codes of denoted Cı.... CS, are the indexes of the nearest centroid of each sub-quantizer, i.e.,
PQ(e) [cr cs], where c, arg min ||
IT (e) ba.ell
Once base vectors have been product-quantized to codes, PQ leverages asymmetric distance com- putation to keep estimation errors low. In the computed distances, the original query vector used while the quantized base vectors used, hence the asymmetry. For given query q. the distances to the centroids of each sub-quantizer are computed and stored a lookup table (LUTT). Then, the corresponding distances in the LUT are looked up based on the codes of base vectors and accumulated to produce the final distance estimation. More concretely, denoting the distance between query and the c-th centroid for the s-th sub-quantizer using LUT.[c dist(==(u) ba.c). , then the estimated distance between query q and a product-quantizet base vector e, where PQ(e) [c.... cs). is
8
dist(g, e)
E [U3,(ca)

---

Building upon previous work 77 we employ product quantization to approximate dot products within the attention mechanism. We product-quantize the key vectors in attention to produce key codes, which will be stored in place of the key cache of LLM attention. The codebooks are learned by performing clustering on set of key vectors from calibration set. The key vectors are quantized to the nearest centroid with respect to 1.2 distance. For a given query, the query-dependent LUT is computed to hold dot products with respect to centroids. Dot products of sub-vectors are retrieved from the LUT based on key codes and accumulated to produce the final dot product estimates. This procedure allows us to compute attention scores through lookups.
3.2 Compressing Lookup Tables into SIMD Registers
Estimating dot products through PQ mostly eliminates the use of MAD kernels in the computation of attention scores. However, this approach yields limited speedup over dot-product attention since a high proportion of the CPU cycles are wasted due to cache/memory access stalling. Ll-cache-resident
LUT is not enough to offer high- hegg-performance PQ [3]. The full potential of bookup-based attention can only be unlocked by having the LUT stored registers, which take only 1-2 CPU cycles to access. However, the highly limited size of registers poses challenge to fitting the LUT. In PQ, each sub-quantizer commonly uses 256 centroids, which translates to 8-bit codes. Combined with 32-bit floating-poin point (FP32) dot products, the LUT for each sub-quantizer consumes 8192 bits of memory, while the SIMD registers are only 128 bits wide. We leverage hardware-awarr techniques proposed in 4 to enable low-latency retrieval from register-resident LUT.
8-bit Quantized Dot Products in LUT Due to the 128-bit width of SIMD registers, the FP32 representation of dot product is too costly to store. Adopting FP32 dot products in LUT implies that each codebook can only contain up to 4 centroids, which will lead to significant quantization errors. Therefore, we adopt the 8-bit dynamically quantized representation of dot products. Compressing beyond 8-bit is infeasible since most SIMD instruction sets do not support parallel lookups below bits. The quantization is done dynamically for each query to minimize quantization errors. For a given query and sub-quantizer, dot products to centroids are first computed full FP32 precision. Then, the quantization range is determined by the minimum and maximum dot products to the centroids. Finally, the range is evenly divided into 2 buckets, and dot products are quantized to the bucket they fall into. More formally, suppose dPmin the minimum and maximum dot products of the query q to the centroids of the s-th sub-quantizer, then the LUT stores the quantized dot products to centroid as
( -b.c) and dpmaa maxx(Tx(q)) -b,c) are
(T (g) be.0) dp
LUT,[c]
(dpmax dpmmn 1/(2
The quantization and de-quantization process can be done efficiently without much computational overhead, and the quantization error is kept low thanks to dynamic query-dependent quantization (we analyze its effects T
Constrained Codebook Size By adopting 8-bit quantized dot products in LUT,, we can fit 16 dot products 128-bit SIMD registers. This implies that the codebook size of each sub-quantizer is constrained to 16 centroids, and evidence suggests this limited size may work well with attention: it has been shown that the output of attention loses rank extremely quickly (15), implying that the intermediate embeddings of transformers may exhibit clear clustering structures.
3.3 Reorganizing Key Cache Memory Layout
Quantized dot products and constrained codebooks enable LUT to be stored in SIMD registers, but the layout format of the key cache needs to be reorganized for SIMD instructions. The original key cache in LLM attention stores each key vector contiguously in a row to optimize single vector reads. NoMAD-Attentin
uses the key-code cache in place of the key cache, which stores the quantized codes of keys. To allow fast lookups of LUT entries based on key codes, we store the key codes in a transposed blocked format. A comparison between the LLM key cache and the NoMAD key-code cache is given in [
The storage format of the NoMAD key-code cache is transposed: stored in column-major order instead of row-major, and blocked: with 32 keys as a block. The SIMD instruction shuffle, leveraged for performing low-latency batch lookups, takes a batch of byte-size integers as input and
5

---

Algorithm 2 NoMADD-Atenntin Score Computation
Input: query q'. key k', key-code cache K
2: let e', t- arg (o..... IT, (k"), 2 for S
P Compute codes for the current key
3: Koode <- insert e₂ into K for ....S
Insert codes of the current key into the key-code cache I... S. 0... 15
4: let &UT +- quantize(T=(g) bs.c) for a
D Store 8-bit quantized dot products (Equation D in LUT
5: let accu ... +-
Initialize accumulators > Perform in-register lookups batch of 32 keys
6: for + 1... 32 do
7: for s + 1.... do
8: simd simd_loadLLUTT,
D Load LUT into registers
9: accu[32i 31 ... 32i] <
simd Jaccu (32i 31... ...... .2i]. cendd_shuffleeLn 3-325-53 22221-31...326. .1..)))))..)))
10: end for
11: end for dequantisefaccuull.... Vil
12: return softmax
retrieves the values held in the registers corresponding to the integer indices. The original storage format of the key cache stores all dimensions of a key contiguously, which precludes efficient use of shuffle. To maximize the usage of the LUT held in registers, to the same sub-quantizer contiguously in rows of 32 codes. Since shuffl. fle performs lookups in batch size of 16, the keys within the same block are stored in alternating order. Each quantized code occupies half byte as there are 16 centroids in a codebook, while the shuffle instruction uses block of
store key codes belonging
each byte as an input argument. By performing SIMD bit-shifting and bit-masking alternating keys, we obtain the key codes in the original order, ready for use with shuffle. Section in the Appendix describes additional details how shuf fllffle is performed on each block of key-code cache, and provides pseudocode.
3.4 NoMAD--Atenniio
By combining these three techniques, NoMAD-Attentinn achieves fast MAD-free attention score computations through SIMD in-register lookups. For a given query, first, LUT's with 8-bit quantized dot products are computed for each sub-quantizer. Then, an LUT is loaded into registers, followed by SIMD shuffle instructions to retrieve dot products in the LUT in batch based on key codes. The loading and lookup are repeated for all sub-quantizers, and the retrieved dot products are accumulated in batch through SIMD add. Finally, the quantized dot products accumulated over all sub-quantizers de-quantized, scaled, and fed through softmax to produce the attention scores. The pseudocode for NoMAD-Attention score computations is given in Algorithm
3.5 Learning Key Compression
Compressing each segment of key activation embeddings into 4-bit codes, without degrading model quality, is challenging. The straightforward approach is to first cache key activation embeddings calibration dataset, and then learn the centroids through k-means clustering (29) the embeddings. However, this first-cut approach significantly degrades model quality, especially for dsub > (we analyze its effects in Section 4.2). The first-cut approach performs sub-optimally since it is uninformed; clustering is performed with the aim to minimize the reconstruction error with all tokens. However, shown previously (60 28). the key cache of certain tokens model quality. Therefore, leverage the Fisher Information Matrix (FIM) to bias the centroids towards important activations. Specifically, we approximate the Hessian using diagonals the FIM, which is the element- wise square of the gradient, and use it to weigh the reconstruction errors. Using the FIM to minimize reconstruction error was first proposed in (26). Our optimization objective for
pivotal for preserving

---

Table 1: Perplexity on WikiText-2 and C4 and accuracy on 6 benchmarks of LLMs with Attention and NoMAD-Attention.
WT-21 C41
SaiQt
Arc-E
Arc-Ct
Hellaswagt
WinoGrandet
PIQAT
Avg/T
Attention
5.68
7.08
94.6
75.21
41.89
56.93
70.09
78.67
69.57
NoMAD-AAlentin (deah
1)
5.74
7.14
94.9
75.34
41.11
56.57
70.56
78.56
69.62
LLaMA-bb
NoMAD-Atentton (duub
6.11
93.3
73.65
67.56
77.86
NoMAD-Atcttion (deab
9.23
12.66
84.4
66.41
32.59
46,74
59.75
74.32
60.70
Attention
5.09
6.61
95.0
77 40
46.42
$9.93
72.85
79.16
71.79
NoMAD-Attentinn (deah 1)
5.14
6.65
95.1
77.15
46.67
59.74
72.85
79.22
71.79
LLaMA-13h
NoMAD-Atemtion (d.ub
NoMAD-Attation (deuh 4)
8.19
10.66
89.1
73.53
37.71
51.19
60.93
76.71
64.86
Attention
5.47
6.97
94.0
76.30
43.43
57.16
69.06
78.07
69.67
NoMAD-Attsntion (deub 1)
5.53
7.02
93.9
75,80
42.92
56,71
69.30
77.97
69.43
LLaMA-2-7b
(d.ub
5.97
76.93
67.67
NoMAD-Atention (deub 4)
10.19
13:24
85.1
68.77
33.70
47.11
56.51
74.27
60.91
Attention
4.88
6.47
94.6
79.42
48.46
60.07
72.30
79.00
72.31
NoMAD-Aftsmtinn (deub 13
4.92
6.50
94.8
79.00
47.87
59.81
71.51
78.94
71.99
LLaMA-2-13b
SoMAD-Atentinn (d.ub
77.61
45.39
70.72
77.75
NoMAD-Atention (deub 4)
8.22
10.86
90.8
72.81
37.80
51.24
$5.96
76.33
64.16
learning the centroids for the s-th sub-quantizer is
15
62.0 13
arg min
Σ
wi
To To bs.c
b.. 15 buub can 1=
pertial sum of dingonals of FIM
(2)
where wf grad(T.. grad(T.(k:))
if = arg (ITa
ba.al12
otherwise
kn where ....k are cached key activation embeddings on the calibration dataset. We use weighted k-means++ [5] to optimize the objective.
4 Experiments
This section evaluates the effectiveness of our proposed NoMAD-Attention in preserving model quality and speeding up LLM inference on CPUs. We first introduce the software, hardware, models, benchmarks, and baselines, then provide detailed results and discussions, and finally perform an ablation study to validate each component of our proposal.
Software and Hardware Our implementation of NoMAD-Attention is built C and C++, based on the open-source projects llama.cpp [20] and FAISS [16]. We also built a GPU implementation of NoMAD-Attentn for quick prototyping and key-compression learning, which based on PyTorch and HuggingFace Transformers [51]. Experiments for latency and throughput are performed on Linux server equipped with an Intel Xeon E5-2695 V3 14-core CPU, which supports AVX2 SIMD instructions, and 51 312GB of DDR4 RAM. Experiments for accuracy and perplexity are performed on two NVIDIA A100-00GB GPUs.
33
Models and Benchmarks We evaluate the quality of NoMAD-AAttention with 4 popular LLMs:
LLLMA-7b LLaMA-13b [45] LaMA-2-76 4. LLaMA-2-13b [46]. We measure the model quality with perplexity on WikiText-2 [30 and C4 [44 at the context length of 2048, and zero-shot
accuracy (using the default configurations of im-evaluation-hamee
19 on SciQ (50 Are Easy
38 and PIQA 6 The centroids for key compression of NoMAD-Attention are learned on calibration set of 16 sequences from WikiText-2, each with 2048 tokens. To test the model efficiency, we benchmark the latency and throughput of CodeLlama-77 (37 (with 16-bit weights and 4-bit q4_0 quantized weights), which has longer context length of 16,384 than the LLaMA family of models. We compare the efficiency of NoMAAD-Attention-baann models (with daub E (1,2, 4)) against Attention- based models with Hama.cpp-based implementation.
(Arc-E), Are Challenge (Arc-C) [11), Hellaswag 54 WinoGrande
7

---

Codeellama-Tu (4-it wrights)
Codee- (4-bit wnights)
lama-7 (16-5t wrights
Taraa [16-bi weight))
Through and (sakens
Litenny (ms)
500
500
22
200
24R91
10000
13000
3300
110031
13933
14091
20000
25000
1300
100003
13902
Connod Leugth
Contert Length
Connot Longth
Contert Lenget
Attercinn
NosAAD-Kieeion dups
Figure 2: Latency and throughput of decoding for CodeLlama-7h1 (4-bit and 16-bit weights) with Attention and NoMAD-Attention NoMAD-Attentn achieves 1.78 1.78-2.07% higher throughput than Attention with 4-bit CodeLlama- lb, and 1. 1.46-1.566 higher throughput with 16-bit CodeLlama-701
CodeLlama-7b (4-bit weights)
CodeLlama-77 (16-bit weights)
Time to First Token (sec)
Attention
4000
MoMAAD-rttentin dabb
Axtentiinttnionnn dash =
NoMAD--Attetion dasb =
1000
1000
3013
4K Tokens
8K Tokens
16K Takens
Tokens
8K Takens
16K Tokens
Prompt Length
Prompt Longth
Figure Time for processing prompts different lengths for Code (4-bit and 16-bit weights) with Attention and NoMAD-Attentin NoMAD-Attention achieves 1.63-1.79x speedup over Attention to process prompt of 16k tokens.
4.1 Results
Model Quality Table I presents the perplexity and accuracy of NoMAD--ttention on different bench- marks with comparisons Attention. NoMAD-Attentnn (d.ub incurs negligible perplexity and accuracy loss, daub 2 incurs minimal degradation, and daub = 4 incurs some degradation due to the high key compression factor.
Decoding Efficiency The latency and throughput for decoding 16,384 tokens for NoMAD-Attention based and Attention-based CodeLlama-7b are presented in Figure For 4-bit CodeLlama-77 NoMAD-Attention achieves 1.78x, 1.95x, and 2.07 x higher throughput (tokens per second) than Attention for dsub 1, 2, respectively. For 16-bit CodeLlama, NoMAD-Attention achieves 1.46x, 1.54x, and 1.56x higher throughput (tokens per second) than Attention for daub = 1, 2, 4, respectively.
Prompt Processing Efficiency We investigate the efficiency of NoMAD-Attention for prompt processing. We generate prompts of length 4,000, 8,000, and 16,000 tokens and record the time until the first token decoded. preusettsss prompt processing time for CodeL At the prompt length of 16k tokens, NoMAD-Attent for the 4- model, and 1.64 1.79x for the 16-bit model. Prompt processing times are similar for 16-bit and 4-bit model, since weight quantization ineffective for speeding up batch processing.
speeds up prompt processing time by 1.63 1.78x
4.2 Ablation Study
We perform of ablative experiments to study the latency breakdown, and the effects of FIM- informed clustering and 8-bit LUT quantization on model quality.
Latency Breakdown We investigate the makeup of latency in each decoding step. Figure presents the latency breakdown of 4-bit Codel.lama-71 for decoding 16.384 tokens, and Figure in the appendix shows the latency breakdown for 16-bit CodeLlama-7b. The latency of lincar projections

---

Arteation
N-AAA D-Areetion day
N:AAAD- N:AMAT--Aaaiie Arsenios
N-MAFT-AMeTth Azteriion A.
-20
250
Soor
100
MLP Unass
34.00
10030
19400
110M)
1900
3603
1000)
1903
30.1
10:0
3300
lengh
Leugh
Figure 4: The breakdown of decoding latency of 4-bit CodeLlama-76 for Attention and NoMAD- Attention. VoMAD-Attentinn effectively reduces the latency of computing query-key dot-produets by 5.24-14.77X x over Attention.
in MLP and Attention stays constant context length increases, and the latency of key caching is insignificant compared to other components. The latency of dot-produce between queries and keys, as well as the multiplications between attention scores and values, grows linearly with increasing context length. In the original Attention, computing attention scores quickly becomes the latency bottleneck as context length increases. NoMADD-ttention mitigates this bottleneck by speeding up query-key dot-product computation by 5.24x, 9.75x, x, and 14.77x for duub = 1,2, 4, respectively.
FIM-Informed Clustering We study the effects of FIM-informed centroid learning for preserving model quality. Tableppresent the perplexity of NoMAD-Attention--aee with uninformed centroids and FIM-informed centroids. FIM-informed centroids consistently achieve better model quality, shown by the lower perplexity.
LLaMA-7b on WikiText-2
LUT Quantization We examine the effects of 8-bit quantized dot products in LUT model quality, Table 3 presents the perplexity of NoMAA--ttention quantized LUT and 32-bit unquantized LUT. 8-bit quantization of LUT incurs negligible loss in perplexity.
LLaMA-7b on WikiText-2 with 8-bit
Table 2: Ablative experiments on the effects of FIM-informed centroid learning on the perplex- ity of LLaMA-7b on WikiText-2.
Table 3: Ablative experiments on the effects of quantized LUT on the perplexity of LLaMA-78 7b WikiText-2.
Perplexity J Uninformed HIM-informed
Perplexity
L-b 32-bit LUT
HoMMAD-Atenninn (deab 1)
5.76
5,74
ToMAD-Atteation (deab = 1)
5.74
5.74
CoMMAD-Attntionn (dout 2)
7.05
6.11
NoMAD-Atlenian (dunh
6.11
NoMAD-Arentton (dyub 4)
21.39
9.23
NoMAD-Attenion (deub = 4)
9.23
9.23
Atteation
5.68
Attention
5.68
5 Related Works
Approximate Attention and Efficient Transformer Since the introduction of attention in trans-
formers [47], there has been a body of work on approximating the attention mechanism for efficient training and inference. Dynamically sparse attention was achieved using LSH (24), Nyström method
(52), and random sampling [53]. Low-rank attention has also been extensively explored 488] 10
and shown to have compute- and memory-efficiency advantages. Hardware-aware attention mecha-
nisms such as FlashAttention [12 propose to mitigate the IO bottleneck in GPUs. In large language 28 58) have been proposed to reduce the high memory overhead of the KV cache. For CPU-only environments, [39 proposes to speed up LLM inference through weight quantization. Weight quantization [18] [6] is an effective approach for accelerating LLM inference and fine-tuning 57 by mitigating the 10 bottleneck.
models, multiple approaches (60]
Matrix Multiplication Optimization and Compression Approximate matrix multiplication is applicable a wide range of computational problems, and its optimization has been a topic of interest for years 32 Modern researchers have begun optimizing matrix multiplication around the specific limitations of computers, including mitigating the IO bottleneck between the CPU and main memory (25). Compression techniques were developed to accelerate large-scale matrix multiplications and

---

scale up the size of multiplication 31 7 25 1. However, many of these algorithms still had limitations that make them too inaccurate or costly for approximating matrix multiplications LLMs
2
6
Conclusion
This study addresses the challenges large language model inference on Central Processing Units (CPUs), particularly the difficulties associated with the expensive Multiply-Add (MAD) matrix operations in attention mechanisms. The investigation highlighted the untapped potential Single- Instructon-Muultilee-Dee (SIMD) registers and their fast in-register lookup capabilities within CPUs. The proposed NoMAD-Altention algorithm serves as an efficient alternative to traditional MAD- based approaches, leveraging in-register lookups and optimizing memory access SIMD registers. The implementation of NoMAD-Attentinn resulted in a significant acceleration of LLaMA-7B-basse model inference, achieving up 2x speedup CPUs.
Acknowledgements
This work was supported by National Science Foundation SHF-2211815, Ken Kennedy Institute, and grants from Adobe and VMware.
Limitations and Broader Impacts
Our proposed method is targeted towards CPUs with SIMD capabilities, and may not generalize to other types of processors. We make LLMs more accessible on commodity hardware, which contributes to the democratization of artificial intelligence and reduces the carbon footprints. Other than the negative societal impacts already presented by LLMs, we expect no additional negative impacts from our work.
References
[1] Ahmed F AbouElhamayed, Angela Cui, Javier Fernande--Maqqus. Nicholas D Lane, and Mohamed S Abdelfattah. Pqa: Exploring the potential of product quantization in dnn hardware acceleration. ACM Transactions Reconfigurable Technology and Systems, 2024.
[2] Joshua Ainslie, James Lee-Thorp. Michiel de Jong, Yury Zemlyanskiy, Federico Lebron, and Sumit Sanghai. Gqa: Training generalized multi-query transformer models from multi-head checkpoints. Proceedings of the 2023 Conference on Empirical Methods Natural Language Processing, pages 4895-4901, 2023.
[3] Fabien André, Anne-Marie Kermarrec, and Nicolas Le Scouarnec. Cache locality is not enough: High-performance nearest neighbor search with product quantization fast scan. In 42nd International Conference Very Large Data Bases, volume 9, page 12, 2016.
[4] Fabien André, Anne-Marie Kermarree, and Nicolas Scouarnee. Accelerated nearest neighbor search with quick adc. In Proceedings of the 2017 ACM on International Conference on Multimedia Retrieval, pages 159 166, 2017.
[5] David Arthur, Sergei Vassilvitskii, et al. k-means++: The advantages of careful seeding. In Soda, volume 7, pages 1027-1035, 2007.
[6] Yonatan Bisk, Rowan Zellers, Jianfeng Gao, Yejin Choi, et al. Piqa: Reasoning about phys- ical commonsense in natural language. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pages 7432-7439, 2020.
[7] Davis Blalock and John Guttag. Multiplying matrices without multiplying. In Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference Machine Learning, volume 139 Proceedings of Machine Learning Research, pages 992-1004, PMLR, 18-24 Jul 2021.
10

---

[8] Beidi Chen, Tri Dao, Eric Winsor, Zhao Song, Atri Rudra, and Christopher Ré. Scatterbrain: Unifying sparse and low-rank attention. Advances Neural Information Processing Systems, 34:17413-17426, 2021.
[9] Beidi Chen, Tharun Medini, James Farwell, Charlie Tai, Anshumali Shrivastava, et al. Slide: In defense of smart algorithms over hardware acceleration for large-scale deep learning systems. Proceedings of Machine Learning and Systems, 2:291-306, 2020.
[10] Krzysztof Choromanski, Valerii Likhosherstov, David Dohan, Xingyou Song, Andreea Gane, Tamas Sarlos, Peter Hawkins, Jared Davis, Afroz Mohiuddin, Lukasz Kaiser, et al. Rethinking attention with performers. arXiv preprint arXiv:2009. /4794, 2020.
[11] Peter Clark, Isaac Cowhey, Oren Etzioni, Tushar Khot, Ashish Sabharwal, Carissa Schoenick, and Oyvind Tafjord. Think you have solved question answering? try arc, the ai2 reasoning challenge. arXiv preprint arXiv: /003.v088000000 004505 2018.
[12) Tri Dao, Dan Fu, Stefano Ermon, Atri Rudra, and Christopher Ré. Flashattention: Fast and memory-efficient exact attention with io-awareness. Advances Neural Information Processing Systems, 15:16344--6359, 2022.
[13] Ganesh Dasika, Mark Woh, Sangwon Seo, Nathan Clark, Trevor Mudge, and Scott Mahlke. hightt- power-simd. In Proceedings of the 2010 international conference on Compil- ers, architectures and synthesis for embedded systems, pages 67-76, 2010.
[14] Jesse Dodge, Maarten Sap, Ana Marasović, William Agnew, Gabriel Ilharco, Dirk Groeneveld, Margaret Mitchell, and Matt Gardner. Documenting large webtext corpora: case study on the colossal clean crawled corpus. arXiv preprint (:X.x:2214.0875:: 2021.
[15] Yihe Dong, Jean- Mann-Bapisste Cordonnier, and Andreas Loukas. Attention not all you need: Pure attention loses rank doubly exponentially with depth. In International Conference on Machine Learning, pages 2793-2803. PMLR, 2021.
[16] Matthijs Douze, Alexandr Guzhva, Chengqi Deng, Jeff Johnson, Gergely Szilvasy, Pierre- Emmanuel Mazaré, Maria Lomeli, Lucas Hosseini, and Hervé Jégou. The faiss library. 2024.
[17] Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akhil Mathur, Alan Schelten, Amy Yang, Angela Fan, al. The llama 3 herd of models. arXiv preprint urXiv:2407.21788. 2024.
[18] Elias Frantar, Saleh Ashkboos, Torsten Hoefler, and Dan Alistarh. Optq: Accurate quantization for generative pre-trained transformers. In The Eleventh International Conference on Learning Representations, 2022.
[19] Leo Gao, Jonathan Tow, Baber Abbasi, Stella Biderman, Sid Black, Anthony DiPofi, Charles Foster, Laurence Golding, Jeffrey Hsu, Alain Le Noac'h, Haonan Li, Kyle McDonell, Niklas Muennighoff, Chris Ociepa, Jason Phang. Laria Reynolds, Hailey Schoelkopf. Aviya Skowron, Lintang Sutawika, Eric Tang, Anish Thite, Ben Wang, Kevin Wang, and Andy Zou. A framework for few-shot language model evaluation, 12 2023.
[20] Georgi Gerganov. GitHuu ggerganov/llama.cp:: LLM inference in C/C++ github.com. https: http://ggtttt....// com/ www.:/ggeerraoo/lllaaa.ooommmm cpp. 2023.
[21] Insu Han, Rajesh Jayaram, Amin Karbasi, Vahab Mirrokni, David P Woodruff, and Amir Zandieh. Hyperattention: Long-context attention in near-linear time. arXiv preprint arXiv:2310.05869, 2023.
[22] Dan Hendrycks, Collin Burns, Steven Basart, Andy Zou, Mantas Mazeika, Dawn Song, and Jacob Steinhardt. Measuring massive multitask language understanding. arXiv preprint STt1:20009033000 2020.
[23] Herve Jegou, Matthijs Douze, and Cordelia Schmid. Product quantization for nearest neighbor search. IEEE transactions pattern analysis and machine intelligence, 33(1):117-128, 2010.
11

---

[24] Nikita Kitaev, Lukasz Kaiser, and Anselm Levskaya. Reformer: The efficient transformer. arXiv preprint arXiv:2001.0444 04451,, 2020.
[25] Sudhindra Gopal Krishna, Aditya Narasimhan, Sridhar Radhakrishnan, and Richard Veras. On large-scale matrix-matrin multiplication on compressed structures. 2021 IEEE International Conference Big Data (Big Data), pages 2976-2985, IEFE, 2021.
[26] Yuhang Li, Ruihao Gong, Xu Tan, Yang Yang, Peng Hu, Qi Zhang, Fengwei Yu, Wei Wang, and Shi Gu. Brecq: Pushing the limit of post-training quantization by block reconstruction. arXiv preprint arXiv:2 102. 022600 2021.
[27] Zheng Lin, Guanqiao Qu, Qiyuan Chen, Xianhao Chen, Zhe Chen, and Kaibin Huang. Pushing large language models to the 6g edge: Vision, challenges, and opportunities. arXiv preprint 17Xiv23309.16733 2023.
[28] Zichang Liu, Aditya Desai, Fangshuo Liao, Weitao Wang. Victor Xie, Zhaozhuo Xu, Anastasios Kyrillidis, and Anshumali Shrivastava. Scissorhands: Exploiting the persistence of importance hypothesis for Ilm kv cache compression at test time. arXiv preprint 2rXiv:2305.17118, 2023.
[29] Stuart Lloyd. Least squares quantization in pem. IEEE transactions information theory, 2892)112--137, 1982.
[30] Stephen Merity, Caiming Xiong, James Bradbury, and Richard Socher. Pointer sentinel mixture models, 2016.
[31] Michael Nelson, Sridhar Radhakrishnan, and Chandra N Sekharan. Billion-scale matrix com- pression and multiplication with implications data mining. In 2019 IEEE 20th International Conference on Information Reuse and Integration for Data Science (IRI), pages 395-402 402. IEEE, 2019.
[32] Rasmus Pagh. Compressed matrix multiplication. ACM Transactions Computation Theory (TOCT), 5(3):1-17, 2013.
[33] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems, 32, 2019.
[34] Ofir Press, Noah Smith, and Mike Lewis. Train short, test long: Attention with linear biases enables input length extrapolation. In International Conference on Learning Representations.
[35] Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, al. Language models are unsupervised multitask learners. OpenAl blog. 188):9, 2019.
[36] David Rein, Betty Li Hou, Asa Cooper Stickland, Jackson Petty, Richard Yuanzhe Pang, Julien Dirani, Julian Michael, and Samuel R Bowman, Gpga: A graduate-level google- poogle-proof q&a benchmark. arXiv preprint arXiv:2311.12022 2023.
[37] Baptiste Roziere, Jonas Gehring, Fabian Gloeckle, Sten Sootla, Itai Gat, Xiaoqing Ellen Tan, Yossi Adi, Jingyu Liu, Tal Remez, Jérémy Rapin, al. Code llama: Open foundation models for code. arXiv preprint arXiv:23088 12950, 2023.
[38] Keisuke Sakaguchi. Ronan Le Bras, Chandra Bhagavatula, and Yejin Choi. Winogrande: An adversarial winograd schema challenge at scale. Communications of the ACM, 64(9):99-106, 2021.
[39] Haihao Shen, Hanwen Chang, Bo Dong, Yu Luo, and Hengyu Meng. Efficient Ilm inference on cpus. arXiv preprint arXiv:231 1.222311000000 1.00002 2023.
[40] Freda Shi, Mirac Suzgun, Markus Freitag, Xuezhi Wang, Suraj Srivats, Soroush Vosoughi, Hyung Won Chung, Yi Tay, Sebastian Ruder, Denny Zhou, et al. Language models are multilingual ofain-of-though reasoners, 2022. URL https:/arxxv org/abs/2210.03055.
12

---

[41] Seo-Ran Shin, Se- Yeon Choo, and Joon-Sang Park. Accelerating random network coding using 512-bit simd instructions. In 2019 International Conference on Information and Communication Technology Convergence (ICTC), pages (099-1103, IEFE, 2019.
[42] Ryan Spring and Anshumali Shrivastava. Scalable and sustainable deep learning via randomized hashing. In Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pages 4454444,70 2017.
[43] Yifan Sun, Nicolas Bohm Agostini, Shi Dong, and David Kaeli. Summarizing epu and gpu design trends with product data. arXiv preprint arXiv:191.113311 2019.
[44] Seunghwan Sung, Sujin Hur, Sungwoo Kim, Dongho Ha, Yunho Oh, and Won Woo Ro. Mad macce: Supporting multiply-add operations for democratizing matrix-multplicationn accelerators. In Proceedings of the 56th Anmual IEEE/ACM International Symposium on Microarchitectuve, pages 367-379, 2023.
[45] Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timo- thée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al. Llama: Open and efficient foundation language models. arXiv preprint arXiv:2302.1397,, 2023.
[46] Hugo Touvron, Louis Martin, Kevin Stone, Peter Albert, Amjad Almahairi, Yasmine Babaci, Nikolay Bashlykov, Soumya Batra, Prajjwal Bhargava, Shruti Bhosale, et al. Llama 2: Open foundation and fine-tuned chat models. arXiv preprint wrXiv:2307.09266 2023.
[47] Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan Gomez, tukasz Kaiser, and Illia Polosukhin. Attention is all you need. Advances in neural information processing systems, 30, 2017.
[48] Sinong Wang, Belinda Li, Madian Khabsa, Han Fang, and Hao Ma. Linformer: Self-attention with linear complexity. arXiv preprint 0rXiv:2006.04768, 2020.
[49] Jason Wei, Yi Tay, Rishi Bommasani, Colin Raffel, Barret Zoph, Sebastian Borgeaud, Dani Yogatama, Maarten Bosma, Denny Zhou, Donald Metzler, et al. Emergent abilities of large language models. arXiv preprint arXiv:2206. 07682, 2022.
[50] Johannes Welbl, Nelson F Liu, and Matt Gardner. Crowdsoureing multiple choice science questions. arXiv preprint arXiv: 2017.
[51] Thomas Wolf. Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue. Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, et al. Huggingface's ' transform- ers: State-of-the-art natural language processing. arXiv preprint 1rXivv11100.0377,,,00
[52] Yunyang Xiong, Zhanpeng Zeng, Rudrasis Chakraborty, Mingxing Tan, Glenn Fung, Yin Li, and Vikas Singh. Nyströmforner: A nyström-base based algorithm for approximating self-attention. In Proceedings of the AAAI Conference Artificial Intelligence, volume 35, pages 14138-14148, 2021.
[53] Manzil Zaheer, Guru Guruganesh, Kumar Avinava Dubey, Joshua Ainslie, Chris Alberti, Santi- ago Ontanon, Philip Pham, Anirudh Ravula, Qifan Wang, Li Yang, et al. Big bird: Transforners for longer sequences. Advances in neural information processing systems, 33:17283-17297, 2020.
[54] Rowan Zellers, Ari Holtzman, Yonatan Bisk, Ali Farhadi, and Yejin Choi. Hellaswag: Can machine really finish your sentence? arXiv preprint arXiv:1905.072 2019.
[55] Hengrui Zhang, August Ning, Rohan Prabhakar, and David Wentzlaff. A hardware evaluation framework for large language model inference. arXiv preprint arXiv:2312.03134, 2023.
[56] Tianyi Zhang and Anshumali Shrivastava. Leanquant: Accurate and scalable large language model quantization with loss-error-aware grid. arXiv preprint arXiv:2407.10032 2024.
[57] Tianyi Zhang, Junda Su, Oscar Wu, Zhaozhuo Xu, and Anshumali Shrivastava. Spallm: Unified compressive adaptation of large language models with sketching. arXiv preprint 2xX1v22410.06364, 2024.
13

---

[58] Tianyi Zhang, Jonah Yi, Zhaozhuo Xu, and Anshumali Shrivastava. Kv cache is 1 bit per channel: Efficient large language model inference with coupled quantization. arXiv preprint arXiv:2405.03917, 2024.
[59] Weihua Zhang, Zhaofeng Yan, Yuzhe Lin, Chuanlei Zhao, and Lu Peng. A high throughput b+ tree for simd architectures. IEEE Transactions on Parallel and Distributed Systems, 31(3)7707-
720, 2019.
[60] Zhenyu Zhang. Ying Sheng, Tianyi Zhou, Tianlong Chen, Lianmin Zheng, Ruisi Cai, Zhao Song, Yuandong Tian, Christopher Ré, Clark Barrett, et al. H _ o: Heavy-hitter oracle for efficient generative inference of large language models. arXiv preprint arXiv:2306. 140448880.4448, 2023.
14

---

Appendix / Supplemental Material
A Details Regarding SIMD Instructions
The SIMD shuffle presented in Algorithm 2 is simplification of the actual hardware implementa- tion. We give full details of lines 5 to 11 in Algorithm in Algorithm 3] Keys stored in blocks of 32, in which keys are stored in an alternating order (see Figure [ for an illustration). After a the sub sub-quantizer is LUT is loaded into registers, the row of key codes in the block corresponding used to perform shuffle. First, each byte in the row is bit-shifted to the right by 4 bits via a SIMD instruction, which produces the codes of the first 16 keys in the block. The codes are fed shuffle to retrieve the quantized dot products of the first 16 keys from the LUT. Then, the first 4 bits of each byte in the row masked out via SIMD instruction, which produces the code of the last 16 keys in the block. They are similarly used to retrieve the quantized dot products from the LUT. The retrieved quantized dot products of 32 keys are accumulated in the accumulator. Since quantized dot products are 8 bits wide, accumulating them in bit accumulators easily results in overflows. Therefore, 16-bit accumulators are used to accumulate quantized dot products.
Algorithm 3 NoMAD Dot- Product Lookup Accumulation Loop
1: let accu 1 f
Initialize 16-bit unsigned accumulators
2: for 1 32 do
3: for 1...S do
4: Lind__oad(LUT)) 3-321-31...321-166
Load LLT registens
5: let cache
Obtain the first 15
key codes through bit shifting
6:
(32i accu(32i
accu
31... 32i 16] + simd simd_add
accu 32: 16).
simd shuffle(LUT, Kati 32 16.a))
7:
32...-15....32. simd wwwwwsttwwwt...........w..wwweet andeeannn((dda let Sache
(
cache
325,, Oxf)
Obtain the 15 key codes
through bitwise and
8:
accu[32i 15... 32i] <- simd_
accu[32i 15...32.. 321].
simd siid_sshffleeLUUT 32: 12. 321.))
9:
for end for
B Visual Explanations on K Cacce and Lookup Table (LUT) Construction
Figure 5 illustrates the process mapping and compressing key vector k construct K Kacche For input key vector kt, functions T., where k' = (k'), (k(kk),.... TT (k*).. Subsequently, each sub-quantizer ग. (A*) ) is mapped to its nearest centroid ct by referencing the codebook b., where e 1...S, S, among 16 centroids in the codebook. The resulting values are then stored in the key cache Kt Ktache
1...S, split the vector into sub-vectors
Similarly, Figure G illustrasss the process of mapping and compressing query vector q" to construct the Look-up Tables (LUT).. Given query vector q', functions n., where s 1. first split the query into sub-queries y (Ti (q*), sub-query n. (4') and the 16 centroids from the codebook b, are computed and then quantized to values within the range of 0-255. Lastly, the quantized vectors are converted into 8-bit codes and stored in LUT!!
Ts(q')). Subsequently, the distances between each
C Overhead of Centroid Learning and Storage
Table details the time overhead for learning centroids, which involves saving activations and gradients, and weighted k-means on the saved embeddings. NoMAA-Atttntion has low learning overheads and can easily scale to larger models.
15

---

Map Cloca Centrid
h
%
Figure 5: Illustattoon demonstrating the mapping of an input key k" to its s-th sub-quantizer using Ts (k*), where E 1.... S. Subsequently, each sub-quantizer maps to closest centroid c/, where i 1...S. S, and the results are stored in the key cache Ktt caacee
Quaitize distunces to numbers between 0-255
Convert quantatd distanze
counoids the currapunding
bii oodes
1.31
90.49
124.20
64
154
154
die
das
deta
LiT!!
22.14
76.00
582,
15
US
231
LUT
168
Figure 6: Illustration depicting the mapping query vector g to its s-th sub-quantizer using n. TT(.). where E I. Subsequently, the distance between n. (g) and 16 centroids is computed. This distance is quantized to a value within the range 0-255, and the resulting quantized distance further converted into 8-bit codes, which are stored in LUT,.
The learned centroids of NoMAD-Atteninn introduce small amount memory overhead. The storage overhead of centroids can be calculated as x h d x 16 x 4 bytes, where I represents the number layers, h the number attention key heads, d the dimensionality of each attention head, 16 the number of centroids, and 4 the number of bytes for storing each centroid parameter. Therefore, the codebook memory overhead for LLaMA-7b/LLaMA the memory overhead for LLaMA- 33/LLLMM-22 13b with deub {1, 4) is 13. IMB, which is modest memory footprint compared to the overall model size.
with dsub = {1, 2, 4] is 8.4MB, and
Table 4: Overhead of learning centroids for key compression.
Model
NoMAD Config. Saving Activations & Gradients Weighted K-means
denh
LLaMA-76
deub daub
mins
14 mins
daub
mins mins
42 mins
LLaMA-13b
deuh
deub
mins
11 mins
deuh
mins
mins
LLaMA-2-7h
doub
mins
14 mins
daub
mins
mins
daub
LLaMA-2-138
deub mins
mins
doub
mins
mins
16

---

Arteation
N-AAA D-Araetion
N:AAAT-Araaiin Arseiios
N:MAA
Locky (h0)
100
Soor
MLP Unass
3.00
10030
19400
34.0
(100))
1900
3401
1000)
1903
3001
1600
3900
lengh
Leugh
Figure 7: The breakdown of decoding latency of 16-bit CodeLlama-P for Attention and NoMAD- Attention. NoMAD-Attention effectively reduces the latency for computing dot-products of queries and keys.
D Latency Breakdown
Figure presents the latency breakdown of CodeLlama-75 with 16-bit weights.
E
Comparison with Integer Quantization
We empircally compare NoMAD-Attentin and Attention with integer quantized key cache. We test the accuracy of LLaMA-7b, using NoMAD-Attention (dsub 1) and 8-bit and 4-bit integer quantized key cache (q8_ 0 and q4_0 in Ilama.cpp). Furthermore, we test the decoding latency at context length 16K tokens, and measure the speedup compared to the full model. As shown in 5 --ttenttnnn (dous = 1) demonstrates better model quality than INT4-quantize key cache and significantly higher speedup than INT4- and INT8 -eT---gantized key cache.
Table 5: Zero-shot accuracy and decoding latency (at context length of 16K) comparison between NoMAD- and Attention with integer quantized key cache, for LLaMA-7b.
SoiQ
Arc-E
Arc-C
Hellaswag
WinoGrande
PIQA
Avg
Larency Per Token (ms)
Spocdup
Original Attention
94.6
75.21
41,89
$6.93
70.09
78.67
69.565
572.497
INT8 Key Cache
94.7
42.15
$7.00
69.643
562.377
INT4 Key Cache
93.6
74.33
41.04
55.34
67.96
77.69
68.327
540.319
1 1.000x
AoMen--ttention (d,,.
94,9
75.34
41.81
56.57
70.56
78.56
69.623
391,098
1.464x
F
Results Llama-3
We evaluate the effectiveness of NoMADD-Atention on the Llama-3-8b [17 model, which uses grouped query attention [2]. Table/ppreeentss the accuracy of Llama-3-8b with Attention and NoMAD- Attention across a range of downstream tasks. The results demonstrate that NoMAD-Attention with deub effectively maintains model quality for Llama 3.
Table 6: Accuracy of the Llama-3-8b model with NoMAD-Attention on downstream tasks.
SaiQ
Arc-F.
Arc-C
Hellaswag
WineGrande
PIQA
Attention
96.4
80.09
50.51
60.18
72.77
NoMAD-Atiention (doub 1) 96.1
80.05
49.49
59.86
73.16
79.65
(dants 94.8
78.32
46.59
57.52
70.17
78.35
NoMAD-Arttntion (daab = 4)
86.3
70.08
37.54
47.38
57.38
76.61
G Additional Evaluations
We evaluate NoMAD-Attention on the more challenging MMLU 22 GPQA 36). and MGSM (English) 44 benchmarks. We use In-evaluation-haaress the task names are mmlu_stem, mmlu_socia poccialsscienes,, spqa_main zeroshot, mgam_dis en. en. shown Table 1 effectively maintains model quality across these diverse challenging tasks.
19 for accuracy evaluation, and
mm 1 humanities, mmlu, mmlu_othes other,
7 NoMAA-Attention with d
17

---

Table 7: Accuracy of LLaMA models on the challenging MMLU, GPQA, and MGSM (English) benchmarks.
MMLU
Model
Method
GPQA
MGSM
STEM Social Sciences
Humanities
Other
Attention
26.39
29.57
29.73
33.15
20.98
NoMAD-Attentn (daus 1)
27.31
29.12
29.44
32.8
23.66
4.0
LLaMA-7b
NoMAD-Attentin (d.u. 2)
25.25
24.99
26.82
30.09
20.08
2,0
NoMAD--Attnttion (daub 4)
25.21
22.98
24.85
26.94
25.67
1.6
Attention
34.13
44.39
40.60
46.48
28.35
7.2
NoMAD-Attenten (d.ns 33.43
43.71
39.57
45.83
28.35
7.6
LLaMA-13b
NoMAD-Attention (d.us
30.70
37.96
34.39
40.20
27.01
NoMAD-Attention (daub = 4) 25.88
25.58
27.46
27.55
25.67
1.2
H
Clarification on dsub
NoMAD-Attention achieves speedup relative to full Attention when dsub primarily due two factors: 1. Leveraging Lower-Latency,
Instructions. Unlike the vanilla multiply-add attention, which relies on batched multiplication and addition SIMD instructions (e.g.. .m25mmmmmmm..mmmm @am256_mul_ps and ___mmmm__aa__aa aad_26___dd__a______ _dd__s in AVX2). NoMAD-Attente
utilizes the SIMD lookup in- struction (_mm256 __mm2_6__sufffi________________ shuffle epi8). This latter instruction operates on more elements at once (32 elements versus 8) and exhibits lower latency (1 cycle vs. 4 cycles on most architectures) | contribut- ing significantly to the efficiency gains. Minimized Data Movement. The product-quantize key cache employed in NoMAD-Attentinn effectively reduces the volume of data transferred between RAM and registers, hence speeding up computations.
I Generalizing to More Attention Types
NoMAD-Attentin generalize to other pretrained transformer models and attention variants such as grouped-qued attention (GQA) [2] and Attention with Linear Biases (ALiBi) (34), Given that GQA employs shared key head across multiple query heads, can adapt NoMAD-Attention to reuse the same key codes for performing in-register lookups. The ALiBi method adds a linear bias term the query-key dot products, process fully compatible with the NoMAD-Attente approach.
https://ww.intell. http://www..kkkkooe///////ssssst
18

---

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

---

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

---

reproducible, they Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [No]
Justification: The code is proprictary to xMAD ai. However, anyone is able to reproduce our results using the algorithm and procedure we describe in the paper. We will provide mechanism to reproduce our numbers in the future.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips. cc/
aablit//giide//odeeebbbiiissss sow.essubbbsiiiooocoocoo.. for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
/mipss.cc/pulli/giidiee
ssisssssicyyyyy for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data,
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permirted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: All training and test details necessary to understand the results are specified in the Experiments section.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Error bars or other appropriate information about the statistical significance are correctly defined wherever applicable.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoo bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
21

---

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

---

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

---

For scraped data from a particular source (e.g., website). the copyright and terms of service of that souree should be provided.
If assets are released, the license, copyright information, and terms use in the datasets.paperssiii paperswi thcode. www.com//aaaa datasets package should be provided. For popular datasets,
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: New assets introduced in the paper are documented wherever applicable.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moddl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
The paper does not involve crowdsoureing nor reserach with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
24

---

Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
25


Reviews:
[{"review_id": "FbpSnEORFH", "reviewer": "Reviewer_QJwg", "summary": "This paper proposes an algorithm to compute vector inner product efficiently on CPU by exploiting the fast access speed of in-register memory for fast self-attention computation on CPU for model inference. Instead of use multiply and add to compute the inner product between query and key vectors, the authors propose to break down the inner product between two vectors to the summation of multiple inner product between sub-vectors. For each sub-vector product, given a query vector, the algorithm enumerates all possible dot-product results with all possible key sub-vectors in a lookup table during preprocessing. The key sub-vectors are quantized so that the the lookup table is small enough to fit into the in-register memory. The authors further optimize the efficiency via optimizing key cache memory layout.", "questions": "see weakness section.", "limitations": "The authors discussed limitations and societal impact.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The algorithm uses lookup operation to avoid multiplication and allows calculating multiple dimensions at once when the dimension of sub-vectors is larger than 1. \n2. The algorithm is able to utilize an extremely small memory (128 bits) to accelerate the calculation.", "weaknesses": "1. It would be better to also give some data about the latency of GPU decoding so that we know how far CPU is behind the GPU in Figure 2. \n2. When the $d_{sub} > 1$, as shown in Table 1, the performance of these models got a severe hit, so it seems that the algorithm only works well on enumerating all possible scalar products for $d_{sub} = 1$.\n3. Even when $d_{sub} = 1$, there are still latency improvement on Figure 2, but I think the number of operations should be the same as the vanilla multiply-add attention, except that each multiply is replaced with a lookup. I am wondering where is the efficiency improvement.\n4. For $d_{sub} = 1$, the algorithm is quite relevant to quantized matmul for self-attention computation, I am wondering how the method performs compared to int8 or lower bit width quantization in terms of model accuracy and efficiency.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely appreciate the reviewers' careful consideration of our paper and their valuable feedback. We have addressed each of their comments below.\n\n**[W1] It would be better to also give some data about the latency of GPU decoding so that we know how far CPU is behind the GPU in Figure 2.**\n\n- We thank the reviewer for their valuable suggestion. We will incorporate the latency of GPU decoding into the final version of the paper to provide a more comprehensive evaluation.\n\n**[W2 & W3] Values of $d_{sub}=1$.**\n- As demonstrated in Table 1, a $d_{sub}$ value of 2 still yields reasonable model performance, as measured by perplexity and accuracy.\n- The $d_{sub}=1$ configuration already achieves significant speedups compared to the original model, with a 1.78x improvement observed at a context length of 16K (Figure 2).\n- The efficiency improvement achieved when $d_{sub}=1$ is primarily due to two factors: **1. Leveraging Lower-Latency, Higher-Throughput Instructions.** Unlike the vanilla multiply-add attention, which relies on batched multiplication and addition SIMD instructions (e.g., `_mm256_mul_ps` and `_mm256_add_ps` in AVX2), NoMAD-Attention utilizes the SIMD lookup instruction (`_mm256_shuffle_epi8`). This latter instruction operates on more elements at once (32 elements versus 8) and exhibits lower latency (1 cycle vs. 4 cycles on most architectures) [1], contributing significantly to the efficiency gains. **2. Minimized Data Movement.** The product-quantized key cache employed in NoMAD-Attention effectively reduces the volume of data transferred between RAM and registers, hence speeding up computations.\n\n**[W4] How does the method perform compared to int8 or lower bit width quantization in terms of model accuracy and efficiency? --- Here is a comparison.**\n\n- We present additional experiments comparing NoMAD-Attention with INT8 and INT4 key cache quantization (q8_0 and q4_0 in llama.cpp). We report the accuracy on various benchmarks and the decoding latency at a context length of 16K tokens for LLaMA-7b.\n- NoMAD-Attention ($d_{sub}$=1) demonstrates better model quality than INT4 quantized key cache and significantly higher speedup than INT4 and INT8 quantized key cache.\n\n|                        | SciQ | Arc-E | Arc-C | Hellaswag | WinoGrande | PIQA  | Avg    | Decoding Latency (16K) | Speedup |\n|------------------------|------|-------|-------|-----------|------------|-------|--------|---------------------------------------|---------|\n| Original Attention     | 94.6 | 75.21 | 41.89 | 56.93     | 70.09      | 78.67 | 69.565 | 572.497                               | -       |\n| INT8 Quantized Key Cache | 94.7 | 75.29 | 42.15 | 57.00        | 70.09      | 78.63 | 69.643 | 562.377                               | 1.018x   |\n| INT4 Quantized Key Cache | 93.6 | 74.33 | 41.04 | 55.34     | 67.96      | 77.69 | 68.327 | 540.319                               | 1.060x   |\n| NoMAD (d_sub=1)        | 94.9 | 75.34 | 41.81 | 56.57     | 70.56      | 78.56 | 69.623 | 391.098                               | **1.464x**   |\n\n**References**\n\n[1] https://www.intel.com/content/www/us/en/docs/intrinsics-guide/index.html", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "BbYeCr89Zd", "reviewer": "Reviewer_CZ4j", "summary": "This paper utilizes product quantization (PQ) to replace dot product operations in the matrix multiplications involved in the attention mechanism of transformers with memory lookup operations, showcased on language models. To my knowledge, this technique has been first introduced by Blalok et al (reference [5] in the paper). This paper goes further into the systems aspect of deploying PQ on GPUs by specifically utilizing SIMD registers to store the codebook used in PQ. This promises to significantly improve the memory access overhead even compared to alternative implementations that keep the PQ codebook in the L1 cache. However, this poses very stringent codebook size constraints that are addressed in the paper. PQ is done completely post-training unlike prior work, but uses a calibration dataset.", "questions": "see above", "limitations": "N/A", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- This paper is addressing an important topic: LLM optimization on commodity CPUs.\n- The use of SIMD registers is innovative and results in significant speedup.\n- PQ has been demonstrated a number of times in the past couple of years, but never with strong results on LLMs.", "weaknesses": "- d_sub is very confusing to me. What is the length or your codeword? if d_sub = 1, is the size of the codeword = 1? how is that product quantization? How does it result in a speedup?\n- the proposed product quantization has been proposed to replace MAD in  matrix multiplications in reference [5]. Line 148 in this paper is overclaiming its contribution suggesting that this submitted paper has proposed this method.\n- Can you please clarify the additional memory overhead introduced by the codebook?\n- \"double quantization\" of PQ has been introduced in prior work and is not cited: Abouelhamayed et al: PQA: Exploring the Potential of Product Quantization in DNN Hardware Acceleration.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We are grateful for the reviewers' careful review and insightful comments. We have addressed their feedback in detail below.\n\n**[W1] d_sub is very confusing to me. What is the length or your codeword? if d_sub = 1, is the size of the codeword = 1? how is that product quantization? How does it result in a speedup?**\n\n- We are sorry for the confusion. To clarify, $d_{sub}$ represents the dimensionality of each sub-quantizer, which is equivalent to the dimensionality of each cluster centroid or the number of dimensions encoded by each product-quantized key code. Notably, the special case where $d_{sub}=1$ can be considered a generalization of multi-dimensional product quantization.\n- $d_{sub}=1$ results in a speedup primarily due to two reasons: **1. Leveraging Lower-Latency, Higher-Throughput Instructions.** Unlike the vanilla multiply-add attention, which relies on batched multiplication and addition SIMD instructions (e.g., `_mm256_mul_ps` and `_mm256_add_ps` in AVX2), NoMAD-Attention utilizes the SIMD lookup instruction (`_mm256_shuffle_epi8`). This latter instruction operates on more elements at once (32 elements versus 8) and exhibits lower latency (1 cycle vs. 4 cycles on most architectures) [1], contributing significantly to the efficiency gains. **2. Minimized Data Movement.** The product-quantized key cache employed in NoMAD-Attention effectively reduces the volume of data transferred between RAM and registers, hence speeding up computations.\n\n**[W2] Line 148 in this paper is overclaiming its contribution.**\n\n- We apologize for this oversight. We will revise line 148 in the final paper to the following: \"Building upon previous work [5], we employ product quantization to approximate dot products within the attention mechanism.\"\n\n**[W3] Can you please clarify the additional memory overhead introduced by the codebook? --- Sure!**\n\n- The memory overhead introduced by the codebook can be computed as $l \\times h \\times d \\times 16 \\times 4$ bytes, where $l$ represents the number of layers, $h$ the number of attention key heads, $d$ the dimensionality in an attention head, $16$ the number of centroids, and $4$ the number of bytes for storing each centroid parameter.\n- Therefore, the codebook memory overhead for LLaMA-7b/LLaMA-2-7b with $d_{sub} \\in \\\\{1,2,4\\\\}$ is 8.4MB, and the memory overhead for LLaMA-13b/LLaMA-2-13b with $d_{sub} \\in \\\\{1,2,4\\\\}$ is 13.1MB, which is a relatively modest memory footprint compared to the overall model size.\n- We thank the reviewer for highlighting this point, and we will incorporate a detailed discussion of codebook memory overhead into the final paper.\n\n**[W4] \"double quantization\" of PQ has been introduced in prior work and is not cited.**\n\n- We thank the reviewer for bringing PQA to our attention. We will incorporate a citation to this relevant work in the final version of our paper.\n\n**References**\n\n[1] https://www.intel.com/content/www/us/en/docs/intrinsics-guide/index.html", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "FswKA3w5A6", "reviewer": "Reviewer_z7Yd", "summary": "This paper proposes using SIMD instructions on CPUs to speed up Transformers by removing multiply-add instructions. The paper replaces the attention operation a lookup-table based alternative. The paper motivates the application well for Transformer inference on CPUs.", "questions": "How well does the method generalize to other open models and to changes in the attention algorithm?", "limitations": "Yes", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "Strengths:\n* Important problem (efficiency) on an understudied platform (CPUs)\n* Shows speedup compared to standard attention\n* The quality studies are strong, with evaluation on upstream and downstream benchmarks. There is some degradation in quality, but it can be adjusted based on hyperparameters.\n\nI have also reviewed this paper in a previous conference (ICML) and I see that the paper is much improved from that version. I recommend accept based on the strength of the motivation and quality of the evaluation.", "weaknesses": "Evaluation on additional and more recent open models (LLaMa-2, LLaMa-3, Gemma, QWEN) would make the paper more convincing. Two open questions from the current evaluation are how well the method generalizes to other pretrained models, and whether changes in the attention algorithm from more recent models change it.\n\nThese are not necessary for the paper, but are natural follow-ups for the work and would improve the paper's impact.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for their support of our paper and the thoughtful suggestions. We address the reviewer's concerns as follows.\n\n**[W1] Evaluation on additional and more recent open models.**\n\n- We conducted additional experiments on the LLaMA-3-8b model with NoMAD-Attention across a range of downstream tasks. Our results demonstrate that NoMAD-Attention with $d_{sub}=1$ effectively maintains model quality.\n\n|                                      | SciQ | Arc-E | Arc-C | Hellaswag | WinoGrande | PIQA  |\n|--------------------------------------|------|-------|-------|-----------|------------|-------|\n| LLaMA-3-8b (Attention)               | 96.4 | 80.09 | 50.51 | 60.18     | 72.77      | 79.71 |\n| LLaMA-3-8b (NoMAD-Attention d_sub=1) | 96.1 | 80.05 | 49.49 | 59.86     | 73.16      | 79.65 |\n| LLaMA-3-8b (NoMAD-Attention d_sub=2) | 94.8 | 78.32 | 46.59 | 57.52     | 70.17      | 78.35 |\n| LLaMA-3-8b (NoMAD-Attention d_sub=4) | 86.3 | 70.08 | 37.54 | 47.38     | 57.38      | 76.61 |\n\n**[W2, Q1] How well does the method generalize to other open models and to changes in the attention algorithm?**\n\nNoMAD-Attention can generalize to other pretrained models and attention variants such as grouped-query attention (GQA) [1] and Attention with Linear Biases (ALiBi) [2]. Given that GQA employs shared key heads across multiple query heads, we can adapt NoMAD-Attention to reuse the same key codes for performing in-register lookups. The ALiBi method adds a linear bias term to the query-key dot products, a process fully compatible with the NoMAD-Attention approach.\n\n**References**\n\n[1] Ainslie, Joshua, et al. \"GQA: Training Generalized Multi-Query Transformer Models from Multi-Head Checkpoints.\" Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing. 2023.\n\n[2] Press, Ofir, Noah Smith, and Mike Lewis. \"Train Short, Test Long: Attention with Linear Biases Enables Input Length Extrapolation.\" International Conference on Learning Representations.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "SHQzm8Vwtv", "reviewer": "Reviewer_hE7X", "summary": "The paper presents NoMAD-Attention, using  SIMD registers in CPU, to speedup LLM inference in CPU.", "questions": "Please see weakness.", "limitations": "The authors include the limitation that this only works on CPUs with SIMD, but the reviewer thinks this is not a significant limitation.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "(1) Important problem with interesting solution.\n(2) The idea is straightforward, and the figure is very clear.\n(3) Good system speedup and maintaining the original performance of attention.", "weaknesses": "The ML benchmarks seem a bit weak (e.g. perplexity, and PIQA-like easy benchmark). Can you evaluate on harder tasks like MT-Bench?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We greatly appreciate the reviewer's careful review and valuable suggestions. We address their comments as follows.\n\n**[W1] Evaluations on harder tasks.**\n\nTo further assess NoMAD-Attention, we conducted additional evaluations on the more challenging MMLU, GPQA, and MGSM (English) benchmarks. Our results demonstrate that NoMAD-Attention with $d_{sub}=1$ effectively maintains model quality across these diverse tasks.\n\n|                                     | MMLU (STEM) | MMLU (Social Sciences) | MMLU (Humanities) | MMLU (Other) | GPQA  | MGSM |\n|-------------------------------------|-------------|------------------------|-------------------|--------------|-------|------|\n| LLaMA-7b (Attention)                | 26.39       | 29.57                  | 29.73             | 33.15        | 20.98 | 4.8  |\n| LLaMA-7b (NoMAD-Attention $d_{sub}=1$)  | 27.31       | 29.12                  | 29.44             | 32.8         | 23.66 | 4.0    |\n| LLaMA-7b (NoMAD-Attention $d_{sub}=2$)  | 25.25       | 24.99                  | 26.82             | 30.09        | 20.08 | 2.0    |\n| LLaMA-7b (NoMAD-Attention $d_{sub}=4$)  | 25.21       | 22.98                  | 24.85             | 26.94        | 25.67 | 1.6  |\n| LLaMA-13b (Attention)               | 34.13       | 44.39                  | 40.60              | 46.48        | 28.35 | 7.2  |\n| LLaMA-13b (NoMAD-Attention $d_{sub}=1$) | 33.43       | 43.71                  | 39.57             | 45.83        | 28.35 | 7.6  |\n| LLaMA-13b (NoMAD-Attention $d_{sub}=2$) | 30.70        | 37.96                  | 34.39             | 40.20         | 27.01 | 6.8  |\n| LLaMA-13b (NoMAD-Attention $d_{sub}=4$) | 25.88       | 25.58                  | 27.46             | 27.55        | 25.67 | 1.2  |", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We sincerely appreciate the reviewers' careful evaluation of our paper and their valuable feedback. In the following section, we address common concerns raised by multiple reviewers. We are happy to provide further clarification during the discussion period.

**1. Regarding $d_{sub}$**

NoMAD-Attention achieves speedup when $d_{sub}=1$ primarily due to two factors: **1. Leveraging Lower-Latency, Higher-Throughput Instructions.** Unlike the vanilla multiply-add attention, which relies on batched multiplication and addition SIMD instructions (e.g., `_mm256_mul_ps` and `_mm256_add_ps` in AVX2), NoMAD-Attention utilizes the SIMD lookup instruction (`_mm256_shuffle_epi8`). This latter instruction operates on more elements at once (32 elements versus 8) and exhibits lower latency (1 cycle vs. 4 cycles on most architectures) [1], contributing significantly to the efficiency gains. **2. Minimized Data Movement.** The product-quantized key cache employed in NoMAD-Attention effectively reduces the volume of data transferred between RAM and registers, hence speeding up computations.

**References**

[1] https://www.intel.com/content/www/us/en/docs/intrinsics-guide/index.html

Meta-review: This paper presents an effective method for accelerating LLMS on commodity CPUs, and the reviews clearly indicate acceptance.
Decision: Accept (poster)