Top-K Vector Theory

  • April 18th, 2026
  • by David Spuler, Ph.D.

What is Vector Top-K?

The top-k algorithm for a vector is finding the largest or smallest k elements. This is also known as "k-selection" and "max-k" or "min-k". There are various efficient algorithms for both sequential and parallel versions of this algorithm. Note that this algorithm is about finding the top-k values in an array (which may or may not have any duplicate values), not the "top-k frequency" question, which is about finding the most common element in an array (which typically has many duplicates).

The top-k algorithm is just some theoretical data structure problem. Some of the uses of Top-K in LLM algorithms include:

  • Top-K decoding (possibly with Top-P and Min-P)
  • Top-K attention (sparsification along token sequence, e.g., DeepSeek Sparse Attention)
  • Top-K sparsification along embedding dimension (i.e., dynamic sparsity of activations)
  • Top-K sparsification of the KV cache data (KV cache compression)
  • Rate limits (i.e. tracking the top-k timestamps)

Max-K versus Min-K: Mirror Images

An important point to note is that the maximum and minimum versions of top-k are mirror images of each other. Changing the comparison operator in your code is almost enough to create the opposite algorithm. For example, if you use a max-heap as the data structure for one, you can use a min-heap for the other algorithm.

This symmetry in the algorithms gives rise to an important trick: use the smaller value for k. The idea is this: 

    r = n - k;
    if (r < k) 
        min-r version
    else 
        max-k version

In many applications, this trick isn't that useful. For example, in top-k decoding for an LLM, the vocabulary size may be n=100,000 with the top-k algorithm requiring k=100. Furthermore, the values of n and k are fixed for this approach, and known at compile-time.

Trivial Top-K Cases

If k is a varying value, it can make sense to first check for the trivial cases. Some examples include:

  • k = 1 — use maximum of vector algorithm O(n).
  • n <= k — use the entire vector.
  • n = k + 1 — use O(n) minimum algorithm and delete that element.

Major Requirement of Top-K

One of the key requirements is that it's not usually just about numbers. The input data may contain an implicit ordering, such as the LLM logit array, where the array index is the number of the token ID and the values are the probabilities. Similarly, other methods may contain a large record of data, where it is being top-k sorted based on one particular numeric field. In this latter case, we may not need to track the array index, but we still need some way to map the top-k values back to their original records with the additional data. Hence, a key requirement at the end of the top-k algorithm:

  • Indexes available (i.e. permutation-based results)

What these means it that we don't just need the numbers in sorted order, but we need to know the array index from which each number came. To achieve this, we can either perform top-k with a permuted index of array indices, or we can pair the index and value.

Relaxing Some Top-K Requirements

Some of the constraints on top-k sorting are not always necessary:

  • Sorted results — we don't always need the k items sorted at the end.
  • Duplicate handling (stable) — don't need duplicates to maintain their order.

Note that we obviously don't need the input array to be sorted, since the top-k algorithm is trivial in this case.

Useful C++ Class Functions

Some of the useful C++ primitives in <algorithm> include:

  • std::partial_sort()
  • std::sort()
  • std::nth_element()
  • std::priority_queue in <queue>

Low Latency Coding of Top-K on CPU

Some of the methods for sequential low-latency coding of a top-K algorithm are not intuitive. For example, maintaining a heap actually involves lots of branching. Some of the issues to consider for low-latency top-k include:

  • Branchless coding
  • Compare-and-swap primitives
  • SIMD vectorization (AVX on x86 or Arm Neon/SVE)
  • Instruction-Level Parallelism (ILP)
  • Using STL versions (pre-optimized by others!)

Overview of General Top-K Algorithms

The main approaches are:

  • Iteration (repeatedly choosing the maximum)
  • Sorting-based algorithms (sort first, then choose)
  • Binary-tree data structure methods (e.g. tournament tree).
  • Heap-based methods (incrementally maintain a priority queue or heap data structure)
  • Layer-Ordered Heaps (LOH) versions
  • Partition-based algorithms (e.g. QuickSelect or Median-of-Medians)
  • Bucket sorting methods (bucket selection)
  • Radix sorting approaches (e.g. RadixSelect)
  • Bitonic sequence methods
  • Binary-search-like algorithms

Not all of these methods are amenable to parallelization on GPU.

Extensions to Top-K

Some generalization to the Top-K algorithm for possible research include:

  • Parallelized GPU top-k versions — already plenty of LLM research on this!
  • Distributed top-k computations — generalize the parallelism.
  • Ranged Top-K — choose between k1 and k2 items according to some criteria.
  • Approximate Top-K — choose k items that are "big enough" even if not necessarily the biggest (within error bounds).
  • Top-K LLM attention algorithms — using top-k sparsity optimizations.
  • Top-K MoE routing methods — a hot topic around the FFN.

References

  1. Xi Xie, Yuebo Luo, Hongwu Peng, Caiwen Ding, 2015, RTop-K: Ultra-Fast Row-Wise Top-K Selection for Neural Network Acceleration on GPUs, ICLR 2025, https://xiexi51.github.io/assets/pdf/RTopK.pdf
  2. Xi Xie, Yuebo Luo, Hongwu Peng, Caiwen Ding, 2 Apr 2025 (v4), RTop-K: Ultra-Fast Row-Wise Top-K Selection for Neural Network Acceleration on GPUs https://arxiv.org/abs/2409.00822
  3. Anil Gaihre, Da Zheng, Scott Weitze, Lingda Li, Shuaiwen Leon Song, Caiwen Ding, Xiaoye S Li, Hang Liu, 16 Sep 2021, Dr. Top-k: Delegate-Centric Top-k on GPUs, https://arxiv.org/abs/2109.08219
  4. Sanskar Chouhan, Ashwin Sonawane, 2018, Literature Survey on Top-K Query Processing Algorithms and the Bitonic Top-K Algorithm for GPU Optimization, https://github.com/Prim3-007/GPU-Based-Top-K-Query-Processing/blob/main/literature_survey.pdf
  5. Ashwin Sudhir Sonawane, 2018, Top-K GPU Query Processing, https://github.com/Prim3-007/Top-K-Query-Processing-on-CUDA-SIGMOD-Implementation-
  6. Christina Zhang & Yong Wang, 2020, Acceleration Top-K Computation on GPU, https://live.nvidia.cn/gtc-od/attachments/CNS20315.pdf
  7. Anil Shanbhag, Holger Pirk, and Samuel Madden. 2018. Efficient Top-K Query Processing on Massively Parallel Hardware. In Proceedings of the 2018 International Conference on Management of Data (SIGMOD '18). Association for Computing Machinery, New York, NY, USA, 1557–1570. https://doi.org/10.1145/3183713.3183735 https://dl.acm.org/doi/abs/10.1145/3183713.3183735 https://www.doc.ic.ac.uk/~hlgr/pdfs/MassivelyParallelTopK.pdf
  8. Jeff Johnson, Matthijs Douze, Hervé Jegou. 28 Feb 2017, Billion-scale similarity search with GPUs https://arxiv.org/abs/1702.08734
  9. J. Johnson, M. Douze and H. Jégou, "Billion-Scale Similarity Search with GPUs," in IEEE Transactions on Big Data, vol. 7, no. 3, pp. 535-547, 1 July 2021, doi: 10.1109/TBDATA.2019.2921572. https://ieeexplore.ieee.org/document/8733051
  10. Leo Mao, March 1st, 2024, CPU TopK Algorithm, https://leimao.github.io/blog/CPU-TopK-Algorithm/
  11. Vasileios Zois, 2018, TopK Algorithms Benchmark, https://github.com/vazois/TopK
  12. Nil Mamano, July 31, 2025, Top-K Problems: Sorting vs Heaps vs Quickselect, https://nilmamano.com/blog/top-k-problems
  13. Oliver Serang, 5 Oct 2020 (v2), Optimally selecting the top values from with layer-ordered heaps, https://arxiv.org/abs/2001.11607
  14. Wikipedia, Apr 2026 (accessed), Median of medians, https://en.wikipedia.org/wiki/Median_of_medians
  15. Donald Knuth, 1998, Tournament algorithm, in Art of Programming, Volume 3, Page 212.

More AI Research Topics

Read more about: