Approximate Top- π \bm{k} for Increased Parallelism
Oscar Key Luka Ribar Alberto Cattaneo Luke Hudlass-Galley Douglas Orr Β· 2024
Read Approximate Top- π \bm{k} for Increased Parallelism by Oscar Key Luka Ribar Alberto Cattaneo Luke Hudlass-Galley Douglas Orr (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-04358.txt.
Introduction
Oscar Key and four co-authors evaluated faster ways to find the largest values in a data array in twenty twenty-four. Picking the exact top k values forces a whole array to be funneled through one merge step, which wastes the parallel power of AI chips. Bucketed methods split the array into groups and take the top values of each group, giving an answer that is close but not exact.
The team studied the design choices of this method family with both theory and tests on real tasks. Their test cases come from sparsity methods for language models, which use top-k picks to keep only the most important weights or signals. They also released a fast bucketed top-k tool for PyTorch. The trade is small accuracy loss for large speed gains on parallel hardware.
Catalog record
| CREATOR | Oscar Key Luka Ribar Alberto Cattaneo Luke Hudlass-Galley Douglas Orr |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 42 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-04358
Browse the full library Β· About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Approximate Top- π \bm{k} for Increased Parallelism Oscar Key Luka Ribar Alberto Cattaneo Luke Hudlass-Galley Douglas Orr Abstract We present an evaluation of bucketed approximate top- k k algorithms. Computing top- k k exactly suffers from limited parallelism, because the k k largest values must be aggregated along the vector, thus is not well suited to computation on highly-parallel machine learning accelerators. By relaxing the requirement that the top- k k is exact, bucketed algorithms can dramatically increase the parallelism available by independently computing many smaller top- k k operations. We explore the design choices of this class of algorithms using both theoretical analysis and empirical evaluation on downstream tasks. Our motivating examples are sparsity algorithms for language models, which often use top- k k to select the most important parameters or activations. We also release a fast bucketed top- k k implementation for PyTorch. Figure 1: Our approximate top- k implementation ( Γ + ), compared with exact top- k implementations from PyTorch and RAFT , and a bucketed top- k using torch.argmax , tested in float32 on an H100 PCIe GPU with batch size m=128 . Total bandwidth is the minimum number of bytes transferred by top- k , divided by runtime. Left: Small fixed k=64 ; it is faster to retrieve k_{b}=1 element per bucket, varying the total number b\cdot k_{b} of elements retrieved, where b is the number of buckets. Right: Large k=n/4 ; best to set b\cdot k_{b}/k=1 and increase k_{b} . n 11 3 10 6 1 4 8 5 2 9 7 split into b buckets \bm{11} 6 8 \bm{9} 3 1 \bm{5} \bm{7} \bm{10} \bm{4} 2 \mathrm{top}\text{-}k_{b} \mathrm{top}\text{-}k_{b} \mathrm{top}\text{-}k_{b} 11 9 5 7 10 4 \mathrm{top}\text{-}k (if b\cdot k_{b}>k ) 11 9 7 10 k Figure 2: Left: An example of a bucketed top- k , with n=11 , k=4 , b=3 and k_{b}=2 . In Stage 1 , n elements are reduced to b\cdot k_{b} elements via b independent top- k_{b} . An optional Stage 2 takes final top- k . Right: The trade-off between top- k runtime duration and downstream task accuracy for SparQ Attention in SQuAD and a sequence repetition task (see Section B.2 ), when using different bucketed top- k settings with batch size m=1 . Good accuracy and speed-ups above 4\times are achieved with k_{b}\in\{2,4\} . 1 Motivation and existing work Top- k is an operation, common to most machine learning frameworks, that selects the k largest elements from a vector of length n . It appears in many machine learning algorithms, for example k -nearest neighbours (KNN) similarity search, and top- k sampling in language models ( Fan et al., 2018 ) . Of particular interest are its application to sparsity methods, often aimed at reducing the otherwise substantial costs of large language models (LLMs). These methods ignore part of the parameters or activations in order to reduce the amount of computation, either during training, during generation ( Sheng et al., 2023 ; Ribar et al., 2024 ) , or both ( Jayakumar et al., 2020 ) . Many sparsity methods discard the parameters or activations with the smallest magnitude, and implement this selection using top- k . Thus, these algorithms may call top- k frequently and on long vectors. For example, Jayakumar et al. (2020) applies top- k to each weight matrix of a Transformer during all training iterations, with each matrix potentially containing millions of parameters. Similarly, Sheng et al. (2023) ; Ribar et al. (2024) compute top- k over the sequence length, which might comprise tens of thousands of tokens, in each attention layer and for each token generated. However, for larger n , computing top- k can be slow: our experiments with Ribar et al. (2024) ( Section 4.3 ) show that top- k consumes >10 % of the time to generate each token and is not able to fully utilise compute resources. One reason for this is that parallelism over n is necessary β the batch dimension is rarely large enough to saturate the processor β but this is limited because substantial cooperation is required between threads. A common class of methods partitions the input vector into buckets, discards those buckets that fall outside the top- k , and recurses into buckets that are partially within the top- k . Parallelism is achieved by using many threads for the partitioning stage, however the buckets must be shared. Within this class, Alabi et al. (2012) introduce BucketSelect and RadixSelect , as used by PyTorch ( Paszke et al., 2019 ) ; see also Ribizel & Anzt (2019) ; Zhang et al. (2023) . Another approach is to use multiple threads to scan over the input while maintaining a shared priority queue of the k largest items ( Johnson et al., 2021 ; Zhang et al., 2023 ) . bitonic top-k ( Shanbhag et al., 2018 ) and Dr. Top-k ( Gaihre et al., 2021 ) are hierarchical approaches, which split the input into buckets, perform selection in each bucket in parallel, and then, possibly recursively, merge the buckets until the final top- k is obtained. Merging the buckets again requires cooperation between threads, limiting parallelism. More parallelism can be achieved by computing an approximate top- k . This approach is particularly relevant for sparsity algorithms because top- k is generally already a heuristic, thus an additional approximation may not impact the overall performance. In this paper we consider methods which split the input into buckets (a common strategy for parallel reduction, see e.g. Triton (2024) ), perform a smaller top- k_{b} in each bucket ( k_{b}\leq k ), and combine the outputs. This design is similar to the hierarchical exact algorithms. However, as the output must no longer be exact, less or no cooperation is required when combining the output of the buckets. An existing instance is TPU-KNN ( Chern et al., 2022 ) , implemented for TPUs as the approx_max_k operation in JAX and TensorFlow. Their design choices are tailored to KNN applications where k\ll n , for example n\sim millions and k<100 . We find that these choices are not optimal for sparsity applications, where k might be 5\% - 20\% of n . While the FAISS library contains several GPU-efficient approximate KNN implementations, these mostly rely on an exact top- k . A single approximate top- k method is documented ( Guzhva, 2023 ) , which only supports CPU (and for which we havenβt found any evaluations). We aim to make fast approximate top- k algorithms more readily available to practitioners by investigating the design choices of bucketed top- k , and by releasing our implementation as a PyTorch library 1 1 1 https://github.com/graphcore-research/pytorch-approx-topk . We evaluate cost-quality trade-offs of the algorithm using theoretical analysis and empirical experiments on a sparse attention method for LLMs, LLM vocabulary sampling, and knowledge graph completion. We demonstrate that substantial speed-ups of the top- k operation are possible in many settings. In particular, on the sparse attention method task, we observe the top- k to be over 4\times faster with little to no degradation in downstream task performance. 2 Algorithm design choices We consider bucketed algorithms consisting of two stages (see Figure 2