guided search over programs [@Yin2017-my; @EUPHONY], but because these methods are top-down, it is much more difficult to guide them by execution information. Finally, @INFERSKETCHES learns to emit a partial program and fill in the holes with a symbolic search.

The most closely related work to ours is *neural execution-guided synthesis*, which like us, uses values produced by intermediate programs within a neural network. @GARBAGECOLLECTOR process intermediate values of a program using a neural network for a small, straight-line DSL, but they do not use the model to evaluate intermediate programs. Another approach is to rewrite a programming language so that it can be evaluated “left-to-right”, allowing values to be used to prioritize the search in an actor-critic framework [@REPL]. Similarly, @ChenLS19 use intermediate values while synthesizing a program using a neural encoder-decoder model, but again this work proceeds in a variant of left-to-right search that is modified to handle conditionals and loops. None of these approaches exploit our main insight, which is that bottom-up search allows the model to prioritize and combine small programs that solve different subtasks.

*Learning to search* has been an active area in machine learning, especially in imitation learning [@Daume2009-lm; @Ross2011-li; @Chang2015-od]. Combining more sophisticated 