Fast TopK Batched: A Sampling Acceleration Tool for CPU-side LLM Inference

Fast TopK Batched is a project focused on optimizing the sampling phase of LLM inference on CPUs. It addresses the performance bottleneck in Top-K sampling (a key decoding strategy) for large vocabularies by leveraging batched processing, SIMD vectorization, and memory layout optimizations. The goal is to achieve low latency and high throughput in text generation, making it suitable for edge deployment, high-concurrency services, and hybrid inference architectures.

Top-K sampling balances output quality and diversity by selecting from the K highest-probability tokens. Naive implementations (full sort, O(V log V)) are inefficient for large vocabularies (50k+ tokens). Even Quickselect (O(V) average) struggles with modern CPU memory access patterns and vectorization potential, leading to performance issues in CPU inference.

Fast TopK Batched uses three key strategies:

1. Batched Processing: Groups multiple sequences to share memory access and merge SIMD execution, improving cache utilization and throughput.
2. SIMD Vectorization: Uses AVX2/AVX-512 to parallelize probability comparisons, chunk large vocabularies for cache efficiency, and optimize branch prediction.
3. Memory Layout: Adopts SOA (Structure of Arrays) for better spatial locality, uses prefetching to load data into cache, and aligns data for efficient SIMD operations.

Performance gains include:

• Single sequence latency: 50-80% reduction vs naive implementations.
• Batch throughput: 2-4x improvement for large batches.

Key use cases:

• Edge devices: Optimizes CPU inference for resource-constrained environments.
• High-concurrency services: Supports more requests with same CPU resources.
• Hybrid architectures: Enhances CPU-side light model performance in layered systems.

To integrate Fast TopK Batched:

1. Ensure target CPU supports AVX2/AVX-512 (degradation available but less optimal).
2. Adjust batch size to maximize performance (larger batches better utilize parallelism).
3. Integrate with frameworks like llama.cpp or ggml via their operator registration mechanisms.

Fast TopK Batched reflects the trend of full-stack, hardware-specific LLM inference optimization. Future CPU optimizations may target Softmax, Layer Normalization, etc. Optimized CPU inference will remain valuable for resource-limited or cost-sensitive scenarios, complementing GPU solutions.