  Modern natural language generation paradigms require a good decoding strategy
to obtain quality sequences out of the model. Beam search yields high-quality
but low diversity outputs; stochastic approaches suffer from high variance and
sometimes low quality, but the outputs tend to be more natural and creative. In
this work, we propose a deterministic search algorithm balancing both quality
and diversity. We first investigate the vanilla best-first search (BFS)
algorithm and then propose the Best-$k$ Search algorithm. Inspired by BFS, we
greedily expand the top $k$ nodes, instead of only the first node, to boost
efficiency and diversity. Upweighting recently discovered nodes accompanied by
heap pruning ensures the completeness of the search procedure. Experiments on
four NLG tasks, including question generation, commonsense generation, text
summarization, and translation, show that best-$k$ search yields more diverse
and natural outputs compared to strong baselines, while our approach maintains
high text quality. The proposed algorithm is parameter-free, lightweight,
efficient, and easy to use.
