Predictive Pipelined Decoding: A Compute-Latency Trade-off for Exact LLM
  Decoding
Seongjun Yang Gibbeum Lee Jaewoong Cho Dimitris Papailiopoulos Kangwook Lee
This paper presents "Predictive Pipelined Decoding (PPD)," an approach that
speeds up greedy decoding in Large Language Models (LLMs) while maintaining the
exact same output as the original decoding. Unlike conventional strategies, PPD
employs additional compute resources to parallelize the initiation of
subsequent token decoding during the current token decoding. This innovative
method reduces decoding latency and reshapes the understanding of trade-offs in
LLM decoding strategies. We have developed a theoretical framework that allows
us to analyze the trade-off between computation and latency. Using this
framework, we can analytically estimate the potential reduction in latency
associated with our proposed method, achieved through the assessment of the
match rate, represented as p_correct. The results demonstrate that the use of
extra computational resources has the potential to accelerate LLM greedy
decoding.