Learn Locally, Recurse Globally: Neural Circuit Synthesis Beyond Training Depth

Reasoning, planning, and agentic systems demand that neural models extrapolate from the easy training instances to harder, more compositional problem instances they encounter at deployment. Neural networks trained by gradient descent are reliable interpolators \emph{within} their training domain but struggle to extrapolate beyond it: they learn local generalizers even when global solutions are representable in their architecture class. We propose a \emph{learn locally, recurse globally} paradigm-: train a neural model on in-distribution sub-problems and apply it iteratively under a verifiable outer loop that decomposes hard instances into a sequence of in-distribution sub-instances and reassembles the result. We instantiate this paradigm in Boolean circuit synthesis from truth-tables, which we adopt as a faithful, controllable abstraction of logical reasoning: any propositional inference reduces to evaluating a Boolean circuit, and circuit \emph{depth} is a clean proxy for the difficulty of the underlying reasoning task. Empirically, a $2.2$M-parameter encoder-decoder Transformer trained on depth-$\leq 2$ circuits, wrapped in our outer loops, synthesizes circuits at $5\times$ training depth and at input arities for which the base model's encoder is too small for direct inference, with synthesis quality matching a standard EDA tool while producing markedly shallower circuits. We connect the algorithms to classical Boolean decomposition theory (Shannon, Ashenhurst-Curtis, Reed-Muller) and to recent formal results on the AC$^0$ barrier for constant-depth Transformers.