Richer or More Gates? Fan-In Trade-offs in Learnable Logic Circuits

In learnable logic gate networks, each neuron implements a $k$-input Boolean function. The dominant setting $k{=}2$ was chosen for tractability. We ask: when does wider fan-in help? At fixed parameter budget, each gate costs $2^k$ parameters, so increasing $k$ exponentially reduces width. Combined with the depth--fan-in bound $L \geq \lceil \log_k d \rceil$, this partitions tasks into two regimes: width-dominated (image classification), where more gates beat richer gates, and degree-dominated (parity, arithmetic), where $k{>}2$ is necessary. Our main finding is that representability does not imply learnability: at the regime boundary, the selection mechanism determines training success at identical architecture, and the optimal mechanism inverts between regimes. We formalize this via a Jacobian analysis: the softmax mechanism's positive-semidefinite (PSD) structure gives basin attraction absent from sigmoid. We train multilinear coefficients with exact gradients and Möbius-transform snapping (zero deployment error), and validate on 28 tasks and 5 real-world datasets across multiple selection mechanisms.