ApproxBrain: Certified Sufficiency Frontiers in Connectome-Constrained Neural Systems

arXiv:2611.06929v1 Announce Type: cross Abstract: Background. A connectome specifies the substrate available to a nervous system, not how much of it a given computation requires. Reported compact sufficient circuits are point estimates: one subset, one task, one fidelity threshold, one parameterisation. Methods. We formalise computational sufficiency as a cost-indexed family of neuron subsets conditioned on a task and a tolerance pair (permitted degradation epsilon, permitted failure fraction rho), separate task adequacy from phenotype fidelity, and certify candidates on held-out parameter draws with one-sided bounds rather than reporting a single minimum. We measure three quantities a single circuit cannot express: non-decomposability, degeneracy, and an intervention-derived role taxonomy. Results. On a released walking simulator, the published 148-neuron circuit is certified sufficient with margin (mean Dtask = 0.017 over 32 held-out draws, no failure), no 146- or 147-neuron subset of it is sufficient, and removing any one of its three interneurons destroys adequacy. Complement splitting recovers the published set exactly in three of seven seeds and reaches its size in five, within 66-97 evaluations, against 221 neurons for the bundle hierarchy at the same budget. Varying only the task changes which neurons are needed: our best-found solutions retain 155 and 149 neurons and share only 3 of 11 searchable neurons. Relaxing the tolerance reveals alternative sufficient circuits, and the whole-CNS interface alone fails every replicate while 93 search-chosen neurons give a certified solution. Conclusions. Sufficiency is set-valued and conditioned jointly on task and tolerance, and no single search strategy dominates across regimes. A frontier is interpretable only alongside its interface-only baseline, its tolerance and its budget. Every result here is model-relative.