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 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 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 depth is a clean proxy for the difficulty of the underlying reasoning task. Empirically, a 2.2M-parameter encoder-decoder Transformer trained on depth-<=2 circuits, wrapped in our outer loops, synthesizes circuits at 5x 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, and we give a simple algebraic criterion for when an outer loop helps: residual refinement contracts because model errors sparsify the residual, keeping every sub-instance in-distribution, whereas projection-based decomposition of a typical hard instance is provably driftless - restrictions of hard functions stay hard. The criterion predicts, and a matched-pairs selector study confirms, that on wide instances no variable selector (greedy, mutual-information, structural, or learned) can improve the headline residual error; learning instead shows up in how compactly each correction is expressed.