llama.cpp b10707 Optimizes KV-Cell Scan for Faster Long-Context Inference
llama.cpp release b10707 introduces an optimization to the KV-cell sequence scan by stopping the scan once all sequences for a cell have been seen, rather than scanning all possible sequences. This change specifically targets the get_prev_tokens function used in the n-gram speculative decoding path. This optimization delivers a 30% to 50% speedup in token generation for long-context Large Language Model (LLM) inference. It significantly improves performance for applications handling massive context windows (e.g., 55k to 132k tokens) without altering the model's output behavior. The performance gain scales with the number of used KV cells, meaning it is highly visible in long-context scenarios but has no impact on short prompts or prompt processing. Benchmark tests on an RTX PRO 6000 GPU showed generation speeds increasing from 33.6 to 50.9 tokens per second for a 132k context.
## BACKGROUND
During LLM inference, the Key-Value (KV) cache stores previously computed attention keys and values to avoid redundant calculations for subsequent tokens. Speculative decoding, such as n-gram speculative decoding, uses statistical patterns from the input to predict multiple tokens at once, which requires scanning the KV cache to retrieve previous tokens.