  Generative models of code, pretrained on large corpora of programs, have
shown great success in translating natural language to code (Chen et al., 2021;
Austin et al., 2021; Li et al., 2022, inter alia). While these models do not
explicitly incorporate program semantics (i.e., execution results) during
training, they are able to generate correct solutions for many problems.
However, choosing a single correct program from a generated set for each
problem remains challenging. In this work, we introduce execution result--based
minimum Bayes risk decoding (MBR-EXEC) for program selection and show that it
improves the few-shot performance of pretrained code models on
natural-language-to-code tasks. We select output programs from a generated
candidate set by marginalizing over program implementations that share the same
semantics. Because exact equivalence is intractable, we execute each program on
a small number of test inputs to approximate semantic equivalence. Across
datasets, execution or simulated execution significantly outperforms the
methods that do not involve program semantics. We find that MBR-EXEC
consistently improves over all execution-unaware selection methods, suggesting
it as an effective approach for natural language to code translation. We
open-source our code at github.com/facebookresearch/mbr-exec and data at
dl.fbaipublicfiles.com/mbr-exec/mbr-exec-release.zip
