Optimizing Token Probability Sorting in llama.cpp: A 12x Speedup for Server Logprobs

In the ongoing effort to reduce CPU overhead during local large language model (LLM) serving, the latest release of llama.cpp introduces a highly effective micro-optimization targeting token probability sorting. According to the llama.cpp b9731 release notes on GitHub, replacing full vocabulary sorting with partial sorting delivers an over 12x speedup in server logprob retrieval. This is a critical enhancement for API endpoints handling structured outputs, evaluation frameworks, and speculative decoding.

The Growing Vocabulary Bottleneck

As open-weight models evolve, one of the most consistent architectural changes is the expansion of vocabulary sizes. While earlier models like Llama 2 utilized a vocabulary of 32,000 tokens, newer architectures such as Llama 3 feature vocabularies of 128,000 tokens. This expansion improves token compression rates and multilingual capabilities, but it introduces a secondary performance penalty during inference: the computational cost of processing logits.

When a client requests log probabilities (logprobs) for the top-n most likely next tokens, the inference server must sort the output distribution. Historically, llama.cpp executed a full sort of the entire vocabulary array to extract these top values. For a 32,000-token vocabulary, the CPU overhead of this operation was often negligible compared to the matrix multiplications occurring on the GPU or NPU. However, as vocabularies quadrupled in size, the O(N log N) complexity of a full sort transformed a trivial host-side operation into a measurable latency bottleneck, particularly on edge devices with constrained CPU resources.

Algorithmic Shift to Partial Sorting

The b9731 release addresses this bottleneck directly through a pull request (#24796) implemented by Adrien Gallouët from Hugging Face. The optimization targets the get_token_probabilities function within the llama.cpp server architecture. By replacing the standard full sort with std::partial_sort, the server now only orders the specific top-n tokens requested by the API client, leaving the remainder of the 128,000-token array unsorted.

The performance gains demonstrated in the release benchmarks are substantial. For a vocabulary size of 128,000 run over 100 iterations, the full sorting method required 8555.6 microseconds per operation (us/op). The implementation of partial sorting reduced this overhead to just 704.3 us/op. This represents a greater than 90% reduction in latency for this specific function. By shifting the time complexity from O(N log N) to O(N log K)-where K is the number of requested top tokens-the optimization ensures that the CPU overhead scales with the client's request rather than the model's architectural dimensions.

Implications for Advanced Inference Workloads

This micro-optimization carries significant implications for modern LLM serving, where logprob retrieval is no longer an edge case but a core requirement for advanced inference techniques.

First, structured generation relies heavily on token probabilities. When forcing an LLM to output valid JSON or adhere to a specific formal grammar, the inference engine must frequently evaluate the probabilities of multiple valid next tokens to navigate the constrained decoding tree. Reducing the sorting latency by 12x directly accelerates grammar-constrained generation.

Second, speculative decoding architectures depend on logprobs to verify draft tokens generated by a smaller, faster model. The target model must score the draft tokens, requiring rapid access to the top probabilities to determine acceptance or rejection. Any host-side delay in sorting these probabilities diminishes the net speedup gained from the speculative drafting phase.

Finally, this update is highly relevant for the broader hardware ecosystem supported by llama.cpp. The b9731 release also includes support for CUDA 13.3 DLLs on Windows and ROCm 7.2 on Linux, highlighting the project's commitment to diverse hardware acceleration. However, GPU and NPU acceleration only apply to the neural network's forward pass. Post-processing steps like logit sorting remain CPU-bound. By optimizing the host-side code, llama.cpp prevents high-end accelerators from idling while the CPU struggles to sort 128,000 floating-point values.

Limitations and Open Questions

While the micro-benchmark results are definitive, the release notes leave several variables unquantified regarding real-world deployment.

The most prominent ambiguity in the provided benchmark data is the listed parameter n_top=0. In the context of partial sorting, a top-k value of zero is logically inconsistent, as std::partial_sort requires a defined range to sort. It is highly probable this is a typographical error in the release notes, but it obscures the exact parameters under which the 12x speedup was achieved.

Furthermore, the scaling behavior of this optimization remains undocumented. The performance delta between retrieving the top 5 tokens versus the top 50 or top 100 tokens is unknown. As the requested n_top value increases, the O(N log K) complexity will naturally consume more CPU cycles, and the exact crossover point where partial sorting loses its dramatic advantage over full sorting is not detailed.

Lastly, the impact on overall end-to-end inference latency is not specified. According to Amdahl's Law, the total system speedup is limited by the fraction of time the optimized function originally consumed. While an 8.5-millisecond sorting delay per token is severe for high-throughput serving, its removal must be contextualized against the total time-to-first-token (TTFT) and inter-token latency (ITL) of the specific model and hardware combination to understand the true user-facing benefit.

The transition to partial sorting in llama.cpp is a textbook example of how algorithmic fundamentals remain critical in the era of accelerated AI computing. As open-weight models continue to scale their vocabularies to achieve better compression and multilingual fluency, naive host-side operations will increasingly surface as performance bottlenecks. By addressing the token probability sorting overhead, this release ensures that the CPU does not throttle the GPU, maintaining the high-efficiency, low-latency serving characteristics that have made llama.cpp a foundational component of the local AI ecosystem.

Key Takeaways

• llama.cpp b9731 replaces full vocabulary sorting with std::partial_sort, reducing server logprob retrieval latency by over 90%.
• The optimization is particularly impactful for modern large-vocabulary models like Llama 3, dropping sorting overhead from 8555.6 us/op to 704.3 us/op.
• Faster logprob retrieval directly benefits advanced inference techniques, including speculative decoding and grammar-constrained structured generation.
• While micro-benchmarks show a 12x speedup, the exact impact on end-to-end inference latency and scaling behavior with larger top-n requests remains undocumented.