Given a labeled dataset {(xᵢ, yᵢ)}_(i = 1)ⁿ, consider drawing a parameter vector θ̂ uniformly at random from those that interpolate the data within a width-W depth-D ReLU architecture with continuous weights bounded within [-M, M]. We study the generalization properties of θ̂ in the case where the dataset can, in fact, be explained by a smaller w-by-d ReLU network. Despite the obliviousness of the selection rule for θ̂, it adaptively generalizes at the rate Õ(wdWD/n), rather than being governed by the VC dimension of the full W-by-D hypothesis class. The reason is due to a particular inductive bias in ReLU networks: the w-by-d parameter *witnesses* an exponential volume of W-by-D interpolating parameters, which dwarfs the volume of poorly generalizing parameters (conditioned on interpolation). We explicitly construct this set of near-equivalent W-by-D parameters by a proof technique called *deep lifting*, and then tie the achievable volume to stability properties of the w-by-d witness. Examples show that these techniques allow us to convert approximation-theoretic results into generalization guarantees for nonparametric classes. We further show that generalization of uniform-random interpolators can survive label corruptions.