  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 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 decoding.
Additionally, we implement PPD and conduct preliminary experiments to
empirically validate its efficacy, addressing potential practical overheads not
covered by theoretical analysis.
