Finite Black-Box Observations Cannot Identify Decompositions for Efficient Optimization

The No-Free-Lunch theorem provides an algorithm-level statement: no decomposition strategy can be universally dominant across black-box optimization problems. We focus on a more basic, information-level question about decomposition itself rather than the strategy that implements it: $\text{can decompositions for efficient optimization be identified from finite black-box observations?}$ To this end, we establish a general theoretical framework for analyzing decomposition in black-box optimization, which explicitly characterizes the decomposition space and the intrinsic complexity of optimal decomposition identification. Building on this framework, we establish a non-identifiability theory and answer the question in the negative: decompositions for efficient optimization cannot be reliably identified from finite black-box observations. Through theory-driven counterexample analysis, we reveal a fundamental objective mismatch in prevailing decomposition strategies that infer problem structure from finite information: their long-standing emphasis on structural recovery may not align with the ultimate goal of efficient optimization. We further revisit the random decomposition strategy, which is generally considered ineffective, and show that it provides a minimax-robust strategy under finite information. Together, the theoretical and empirical findings provide guidance for several promising directions in future research on decomposition strategy design.