Aggregation/Optimization Stability Gap in Neuro-Symbolic Inference

Neuro-symbolic systems compute two structurally different kinds of query over the same representation: aggregation (marginalizing or averaging over hypotheses) and optimization (selecting a single best witness). We show these obey different stability laws. Aggregation is provably Lipschitz-continuous under belief perturbations, for any bounded-weight aggregation and any Lipschitz neural scorer. Optimization is not: we construct, explicitly, a neural scorer of arbitrary smoothness under which an arbitrarily small input perturbation produces an arbitrarily large change in the selected witness. We show both the magnitude and frequency of an optimization failure. We instantiate this result on three structurally unrelated representations – model-based diagnosis, abductive explanation, and constrained route planning under belief uncertainty – and validate it empirically on all three, including a controlled, timed comparison of aggregation and optimization on identical trained representations. We further show optimization-side intractability is not inevitable: two independent mechanisms, structural (bounded treewidth) and algorithmic (randomized restart), recover practical tractability.