  We combine beam search with the probabilistic pruning technique of nucleus
sampling to create two deterministic nucleus search algorithms for natural
language generation. The first algorithm, p-exact search, locally prunes the
next-token distribution and performs an exact search over the remaining space.
The second algorithm, dynamic beam search, shrinks and expands the beam size
according to the entropy of the candidate's probability distribution. Despite
the probabilistic intuition behind nucleus search, experiments on machine
translation and summarization benchmarks show that both algorithms reach the
same performance levels as standard beam search.
