Minimax Bounds for Learning Compositional Rules Unde Structural Priors

Modern AI systems fail systematically at identifying novel compositional rules even when they perform well within their training distribution. We formalize this gap as the Curse of Discovery, an information-theoretic barrier that prevents any algorithm from efficiently recovering the correct compositional structure across exponentially large hypothesis spaces without structural prior knowledge. For a hypothesis space with N primitive components, we prove the minimax sample complexity scales as \Omega(2^{N(1-\eta)}) under passive uniform queries (i.i.d. \mathbf{x} \sim \text{Unif}(\{0, 1\}^N)), where \eta \in [0, 1] quantifies prior informativeness, making unconstrained discovery statistically infeasible for large N. We then show that three structural priors each collapse this exponential barrier. Under k-sparsity the complexity reduces to \tilde{\Theta}(N^k), under permutation symmetry to \tilde{\Theta}(\log N), and under Lipschitz smoothness to \tilde{\Theta}(N \text{polylog} N). All bounds are tight: matching algorithms via successive elimination, binary search, and greedy local search achieve the lower bounds in each regime. These results explain compositional generalization failures in foundation models, identify the minimal structural assumptions that render discovery tractable, and supply concrete sample-complexity targets for AI systems intended for scientific discovery.