FAFO: Lossy KV Cache Compression for Lossless Inference Acceleration via Draftless Fumble Decoding

Lossy KV cache compression is a well-explored subfield of machine learning efficiency, with improved latency being one of its major gains. However, lossy compression techniques can fumble from time to time, exhibiting various, and often catastrophic, failure patterns that are not only difficult to resolve but sometimes even hard to identify, making direct deployment of models with compressed KV cache a risky endeavor. In this work, we explore a way to preserve lossless generation quality while still benefiting from the acceleration provided by KV cache compression. Specifically, we draw inspiration from the n-gram candidate pool decoding paradigm where we purposely allow the model to Fumble Around with compressed KV cache to generate multiple lossy "n-gram guesses", while in parallel Find Out via lossless verification in the same forward pass. From a conceptual standpoint, our proposed framework is compatible with all typical static or dynamic KV cache compression methods from the token dropping realm, thus opening up a new avenue for the stagnant n-gram decoding paradigm. Practically, we show that this framework presents many useful traits that similar draftless baselines (e.g., Self-Speculative Decoding) cannot achieve, such as requiring only one set of KV cache and being far less sensitive to model, task, and input-length scenarios. Our comprehensive empirical results show FAFO provides 1.20-2.71× latency speedup over the original model, while consistently outperforming other lossless + draftless solutions.

Modern chatbots like ChatGPT remember every word of your conversation in a fast-access scratchpad that grows as you keep talking, eventually slowing the chatbot down. Researchers have tried shrinking this scratchpad by discarding parts of it, but doing so can subtly degrade the chatbot's answers in ways that are hard to detect. We propose Fumble Around and Find Out (FAFO): let the chatbot guess a few upcoming words using a shrunken, lower-quality scratchpad, then double-check each guess against the full, original scratchpad in a single pass — accepting correct guesses and discarding wrong ones. The result is up to 2.7× faster responses with no change to what the chatbot would have said otherwise. Unlike previous speed-up tricks, FAFO holds up reliably across many tasks, from writing assistance to long-document reasoning, making fast and trustworthy chatbot responses easier to deploy in practice.