Probabilistically-sound beam search with masked language models
Charlie Cowen-Breen Creston Brooks Robert Calef Anna Sappington
Beam search with masked language models (MLMs) is challenging in part because
joint probability distributions over sequences are not readily available,
unlike for autoregressive models. Nevertheless, estimating such distributions
has applications in many domains, including protein engineering and ancient
text restoration. We present probabilistically-sound methods for beam search
with MLMs. First, we clarify the conditions under which it is theoretically
sound to perform text infilling with MLMs using standard beam search. When
these conditions fail, we provide a probabilistically-sound modification with
no additional computational complexity and demonstrate that it is superior to
the aforementioned beam search in the expected conditions. We then present
empirical results comparing several infilling approaches with MLMs across
several domains.