How Should We Search in Neural Language Spaces? A Study on Test-Time Search

Recently, learning neural languages and their interpreters using data has been shown to be effective in generalizing to out-of-distribution tasks. In particular, the structure of neural languages can be leveraged via test-time search in a paradigm like programming by example (PBE). Several existing works use the differentia- bility of neural languages and their interpreters to search the language space in a gradient-guided fashion. We examine existing frameworks and study their effec- tiveness when searching the language space in a policy-guided fashion, where the encoder that induces a program in the neural language to solve a task acts as a policy. We show that frameworks enabling policy-guided search in the language space naturally exhibit length generalization via test-time search. Moreover, our results indicate that, depending on the nature of the neural language and its in- terpreter, using policy-guided search techniques such as Levin Tree Search (LTS) during test time both improves out-of-distribution generalization and requires sig- nificantly less computational overhead.