When is a Representation Sufficient? Probe $\mathcal{V}$-Information for Neural Architecture Search

When is a neural representation sufficient for a task? A representation Z is sufficient if I(X;Y | Z)=0, meaning no task-relevant information remains in the input. This provides a natural criterion for deciding when additional model capacity is unnecessary. However, estimating such information-theoretic quantities in high-dimensional neural networks is intractable in practice. We introduce V-NAS, a progressive architecture search method that replaces intractable Shannon information with probe-based V-information, a directly computable measure of extractable predictive information. Using the cross-entropy of a restricted probe, our method determines whether increasing width or depth yields meaningful gains, enabling principled capacity control. Across multiple datasets and architecture families, V-NAS discovers compact architectures that match the performance of significantly larger baselines at substantially lower cost. These results demonstrate that representation sufficiency can serve as a practical and interpretable foundation for neural architecture design.