C3BO: Count-Conditioned Combinatorial Bayesian Optimization

Evaluation-limited subset optimization must choose both how many items to select and which ones. Across four constrained benchmarks with additive objectives, the nine surrogate-based methods we evaluate reach an optimal count in at most 3.2% of proposals. We analyze a prior–archive mismatch in linear and Gaussian-process surrogates. For kernels depending only on which items differ, including RBF and Matérn kernels with ARD, we prove that the linear size direction receives only the average prior variance of individual-item directions. The benchmarks have a dominant size effect but narrow count coverage in their repaired archives, and posterior refits severely underestimate that effect. We propose C3BO, which corrects the surrogate's prior on the size direction and lets the corrected posterior choose the count. When the joint solve is not certified in time, it compares candidates from fixed-count subproblems, where size-only errors leave candidate rankings unchanged. With 100 evaluations, C3BO and count sampling, a baseline that keeps the standard prior and samples counts, both outperform all thirteen external methods across the four benchmarks. C3BO improves hypervolume AUC over count sampling by 10.4–17.8% on held-out instances. Ablations link the main gains to size-aware modeling combined with posterior-based count selection. Sampling counts independently of surrogate predictions also improves optimization with a tabular foundation model on all four benchmarks. On two nonlinear optimal-design problems, duplicate proposals expose a separate failure mode; rejecting repeats brings C3BO's mean hypervolume AUC within 1% of count sampling on fresh scenarios.