Exchange Barriers and Exact Recovery in Experimental Design

Batch active learning and optimal experimental design commonly select measurements through individual acquisition scores or greedy batch construction. We identify information and exchange barriers when a prediction target requires several measurements jointly. The closure objective's submodularity ratio is exactly zero, making ratio-based weak-submodularity guarantees vacuous. Any strategy accessing the instance only through order-$j$ information values and purchased responses cannot distinguish two targets whose minimal closing sets are disjoint and have size $j+1$, regardless of its number of oracle calls. With known features, even greedy selection using exact risk can terminate at strict local optima. For paired designs with cycle-structured nuisance, escaping a complete-pair starting batch requires $\Theta (\min \{b,1+\sqrt{t}\})$ replacements, where $t$ scales nuisance strength and $b$ is the budget. The same structure that obstructs local improvement enables global optimization: for paired designs with graph-structured nuisance, we recover hidden measurement pairs from the candidate Gram matrix and compute an exactly optimal batch in polynomial time. These results include full-row-rank designs with positive reconstruction residual. Witness search is polynomial on regular matroids; closing the uniform grand mean is NP-complete on complete three-factor interaction grids. On a real perovskite task, an automatically discovered three-measurement exchange reduces design risk by $13.4\%$ beyond complete one/two-measurement descent. Removing cross-candidate nuisance correlations while preserving singleton risk and information scores reverses this gain, isolating joint geometry as the mechanism that pointwise acquisition scores leave unresolved.