A Beginning of Infinity: Generalization by Dreaming with Neural Languages

Generalization in neural networks is typically bounded by the amount and quality of the data used to train them. Recent neural models that learn a discrete language and its interpreter can represent programs far beyond their training distribution, but recovering these programs requires expensive search at test time. In this work, we show how this generalization capability can be transferred into a System 1 network, fully end to end. Once the learner has acquired a neural language, it can continue learning by dreaming. That is, it composes the primitives of its learned language into novel programs and executes them on inputs drawn from the training input distribution, generating new problems whose programs serve as exact training labels. The language thus becomes a source of new training problems, allowing the learner to acquire concepts that were never encoded in its original training set, without any domain-specific language, hand-written generator, or test-time search. If the learned language is universal for a problem class, dreaming can in principle reach every problem in it, even when the training data contains only a small fraction of the problems in that class. We evaluate our approach on several programming-by-example benchmarks and show that dreaming enables strong out-of-distribution generalization, matching or outperforming test-time search methods at orders of magnitude lower inference cost.