Query Complexity of Forward-Only Hebbian Learning: Theory and a Native Fit for Diffusion Models

We study the query complexity of forward-only, gradient-free learning rules for training neural networks, motivated by settings where backpropagation is structurally unavailable: activation-tape memory that grows with depth and context, and objectives (quantized weights, non-differentiable rewards) whose exact gradient is zero almost everywhere. We analyze a three-factor Hebbian rule, an antithetic zeroth-order gradient estimator that perturbs parameters along a random probe and broadcasts a single scalar score to every synapse, and derive an exact, non-asymptotic identity for its gradient alignment as a function of probe count and problem dimension, yielding a closed-form query budget $M^{\ast }\approx (P+1)/3$. We relate this upper bound to known minimax lower bounds for zeroth-order stochastic convex optimization, characterizing how close the rule's query complexity comes to the best possible rate for any gradient-free method. We further identify an architecture-dependent separability criterion, a measurable coupling scope $S$ and feedback bandwidth $K$, that predicts when this query cost stays small, and confirm it empirically on a diffusion denoiser, where the per-noise-level residual gives $S=1$: the rule closes most of the gap to backpropagation from scratch while eliminating its activation-memory overhead entirely, and continues to descend the loss through a quantized codebook argmin where the exact gradient is identically zero.