Many applications today provide users with multiple auto-complete drafts as they type, including GitHub’s code completion, Gmail’s smart compose, and Apple’s messaging auto-suggestions.
Under the hood, language models support this by running an autoregressive inference pass to provide a draft. Consequently, providingdrafts to the user requires running an expensive language modeltimes. To alleviate the computation cost of runninginference passes, we propose Superposed Decoding, a new decoding algorithm that generatesdrafts at the computation cost of one autoregressive inference pass. We achieve this by feeding a superposition of the most recent token embeddings from thedrafts as input to the next decoding step of the language model. At every inference step we combine thedrafts with the top-tokens to getnew drafts and cache themost likely options, using an n-gram interpolation with minimal compute overhead to filter out incoherent generations. Our experiments show thatdrafts from Superposed Decoding are at least as coherent and factual as Nucleus Sampling and Greedy Decoding respectively, while being at leastfaster for. In a compute-normalized setting, user evaluations demonstrably favor text generated by Superposed Decoding over Nucleus Sampling. Code and more examples open-sourced athttps://github.com/RAIVNLab/SuperposedDecoding.