acceptodds
Under review as a conference paper at ICLR 2027

C3BO: Count-Conditioned Combinatorial Bayesian Optimization

Abstract

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.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
Combinatorial Bayesian optimization, Constrained subset selection, Posterior sampling, Cardinality constraints, Multi-objective optimization

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_MCBWOpenReview ↗
Rating
1
Confidence
4
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

This paper investigates a real but somewhat niche issue in black-box subset optimisation, claiming that while existing methods can explore over choices of subset for fixed subset size, they struggle to explore beyond the subset sizes present in the initial data used to warm-start the optimisation.

The proposed solution is simple and just includes the size of the subset as an additional input with a weak prior. This is shown to work against on artificial test problems carefully constructed to have additive +ve structure. On the only more realistic benchmark, the method performs poorly.

Unfortunately, the manuscript is full of poor explanations and inconsistencies that make it hard to understand and thus assess.

Critical strengths

None

Critical weaknesses
  1. The manuscript is very hard to follow. Key terms are used without definition or before they are defined. Much of the prose is compressed to the point of ambiguity (e.g., “a verdict on held-out instances,” “which sensor placement had no dispatch for”). The appendices read more like an experiment log than a structured supplement. A substantial rewrite is needed before the technical contribution can be properly assessed.

  2. Limited novelty. The core observation is that an i.i.d. zero-mean prior on item coefficients assigns the common mean a prior variance of s²/n. The proposed fix, a hierarchical prior with a diffuse common mean, is textbook, as the citation to Gelman et al. acknowledges. The authors’ own GP experiment shows that simply adding a linear mean in |x| recovers about 100% of the size effect. Please clarify why this contribution is substantial enough for an ICLR paper?

  3. The method’s additional components contribute little, meaning that C3BO effectively reduces to just adding an |x| feature with a diffuse prior and solving the resulting MIP.

  4. I found several places where the manuscript contradicts itself or refers to content that is missing. These issues reduce my confidence in the reliability of results in the paper. (i)The introduction describes the four benchmarks as “standard constrained problems,” but Section 6.1 states they are generated by the authors rather than taken from a benchmark suite. (iii) The external-method set differs between experiments (Bounce appears in Table 4 but not Table 3; MALIBO and Meta-MO-TPE appear in Table 3 but not Table 4). (iv) The 3.2% figure in the abstract and the 6.4%/2.6% annotations in Figure 1 are not explained in the main text.

  5. The paper repeatedly describes predictions and criteria as “registered” and uses this to support its credibility. However, what this means is unclear...

  6. The benchmark problems are unrealistic. All four families use additive objectives with item values drawn uniformly from {10,…,99}, so every item effect shares one sign and the shared size effect is 2.1 standard deviations by construction. This is precisely the regime in which the proposed fix (and a linear surrogate) is advantaged, The evidence that C3BO helps, outside this synthetic regime is weak.

.

Questions for authors

The paper needs to be completely rewritten and tested on more realistic problems.

2 comments
AuthorsOpenReview ↗

Response to Reviewer MCBW

Thank you for pointing out where the manuscript made the contribution and experimental protocol difficult to assess. We revised the presentation and added controlled comparisons for both the size prior and the fixed-size search.

W2. Technical contribution. The diffuse common-mean prior is standard. Our contribution is to identify a structural reason why common surrogates can miss good subset sizes and to test its effect on the decisions made during optimization. Proposition 1 shows that for binary-input kernels that depend only on which items differ, including RBF and Matérn kernels with ARD, the linear size direction receives exactly 1/n1/n of the first-order prior variance, whenever that variance is nonzero. Tuning the ARD lengthscales leaves this fraction unchanged. Proposition 2 explains why a narrow range of observed sizes can leave the shared size effect strongly shrunk in a linear surrogate.

On the same stored archives, replacing only the fitted size effect with its true value increased the fraction of proposals within ten items of an optimal size from 0–9% to 63–91% (Table 9). In a separate online comparison without GP proposal replacement, removing the diffuse size prior reduced mean AUC by 14.2–35.7% with centring, intercept treatment, and search fixed (Table 20). The diagnosis also motivated an online GP experiment. Adding a linear size term to the qLogNEHVI GP mean improved mean AUC by 3.5–6.8% with the acquisition and candidate search fixed (Table 2).

W3. Contribution of fixed-size search. Disabling fixed-size search reduced mean hypervolume AUC by 13.77% across the five equally weighted OR-Library markets (nominal 95% market-bootstrap interval [−18.09%, −9.76%]). Repeat evaluations rose from 186 to 1,021, with 2,000 post-initial evaluations per variant. Both variants used the same prior, 2.5-second unrestricted solve limit, and duplicate handling. The ablated variant left the remaining solver time unused (Appendix H).

OR-Library marketC3BOC3BO w/o fixed-size solves
Hang Seng0.7160.559
DAX0.9000.761
FTSE 1000.7890.676
S&P 1000.9890.868
Nikkei 2250.9270.862
Mean hypervolume AUC over five paired seeds per market (Table 4, Appendix H).

When the unrestricted MIP fails to certify an unseen design in time, C3BO uses the remaining budget to solve fixed-size MIPs and adds their candidates to the pool. A size-only error can change which size wins while leaving the ranking of designs within each fixed size unchanged (Algorithm 1, Lemma 4). Enabling the fixed-size solves improved mean AUC by 4.69% on Set Cover and 2.01% on MWIS, with smaller gains on the knapsacks (Table 1). On PyOED, the fallback was never called, and both variants evaluated the same designs in the same order (Appendix G).

W6. Evidence outside the original setting. On OR-Library, C3BO achieved higher mean AUC than the 14 external methods in Table 4 on all five markets. C3BO’s mean AUC across the five markets was 6.36% lower than that of a rule that samples near both feasible size limits (Appendix H). On PyOED, C3BO led in mean AUC on tomography and trailed several baselines on sensor placement. In the mixed-sign experiments at a mean-to-SD ratio of 0.5, fitting the size-prior scale improved mean AUC over centred L=0L=0 by 4.8% on MOKP and 17.2% on Set Cover. At zero mean, the differences were −0.9% and +0.8%, respectively, with both intervals including zero at the reported precision. Both variants used the same GP proposal schedule. Table 18 reports the full comparison. These results clarify where the size-prior correction is supported.

W1, W4, and W5. Presentation and reporting. Algorithm 1 now shows the full batch procedure, and Section 6.1 defines the comparison policies. We identify the four main benchmarks as generated, clarify the baseline sets in Tables 1 and 4, and remove the unexplained Figure 1 annotations. Appendix K defines an optimal-size hit and reports the updated maximum of 44 out of 1,600 post-initial evaluations. Appendix J distinguishes comparisons prespecified in dated internal protocols from later amendments.

The submitted manuscript omitted the use of GP proposals in four of eight slots per batch for the final six batches of the four internal linear policies. We reran those policies without proposal replacement on the main and held-out generated instances (640 runs). Appendix E identifies which results use the reruns and which auxiliary controls retain the original schedule. The main conclusions on the generated benchmarks hold when each policy makes all its own proposals.

Thank you for your response. I will maintain my score as I believe the advance to be incremental and I still think the paper requires a significant rewrite.

Reviewer_jc3rOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The authors argue that surrogate-based BO for subset selection gets the count wrong. The surrogate’s prior underweights the effect of total size, and the repaired initial data covers too narrow a range of sizes to correct this. They also propose a solution called C3BO which adds subset size as a feature with a diffuse prior so the model learns the size effect and picks the count itself. It falls back to fixed-size subproblems when the solver runs out of time.

Critical strengths
  1. The authors make an interesting observation that standard surrogates, including the default BoTorch GP with RBF/Matérn ARD kernels, give the subset size only a 1/n share of the prior variance (Prop. 1). As a result, the model barely learns how much size matters, and the narrow repaired initial data cannot correct it (Prop. 2). This factors in my assessment as the observation applies to widely used BO methods and not just C3BO, and the proposed fix is simple and easy to adopt.

  2. The authors also test the mechanism directly, not just through benchmark wins. Restoring only the size effect moves most proposals close to the best count, while the original runs almost never get there (Table 7). In Fig. 2, they show the gain appears only when the corrected prior and the model’s own count are combined. I factor this into my assessment as it gives more empirical intuition connecting the theory to the actual gains. Also even simply sampling the count, without fixing the prior, seems to work well and has a good practical takeaway on its own.

Critical weaknesses
  1. My main concern is that the benefit of learning the count is only shown on linear benchmarks where the best count sits at/near the edge of the feasible range. On the two nonlinear PyOED problems, it seems what helps C3BO is deduplication rather than the size correction. This is important to my assessment since it is unclear whether the main idea helps when the count involves a real trade-off.

  2. Although the diagnosis covers standard GP surrogates (Prop. 1), the method itself is only tested with a linear surrogate and an exact solver. The authors show a size-aware GP can recover the size effect, but only offline and never in a full optimization run. Is there a specific reason for this?

  3. For GPs and foundation models, only simple add-ons like count sampling are tested, with mixed results. This is important to me as I am not sure whether the fix actually works for more practical use cases.

Questions for authors
  1. How does C3BO’s runtime compare with the baselines, and how does the solver cost scale beyond 250 items, given that the unrestricted solve already struggles to finish in time on set cover and MWIS?

  2. C3BO appears to optimize the posterior mean (c^)(\hat c), so there is no explicit exploration over counts or compositions. Is this correct? If so, how would the method behave with noisy or nonlinear objectives, where the batch collapse seen on PyOED suggests exploration matters?

  3. Once the prior is corrected, the learned count tends to go to the edge of the feasible range (Prop. 4). So I think it is unclear how much of the gain comes from "learning" the count versus simply knowing where the edge is. Count sampling ignores the feasible range, while C3BO uses a greedy estimate of it, which may inflate the margin between them. Maybe running the backbone with counts sampled near the edge would help separate the two?

2 comments
AuthorsOpenReview ↗

Response to Reviewer jc3r

Thank you for suggesting the online GP test and the boundary-informed control. Adding a linear size term to the qLogNEHVI GP mean raises mean AUC by 3.5–6.8% across the four benchmarks. AUC improves in all 20 paired comparisons (Table 2). We address the boundary control in Q3.

W1. When the best size involves an interior trade-off.

  • OR-Library portfolios (Table 4, Section 6.5, Appendix H): A portfolio at an interior size is certified to beat both feasible size limits in 26 of 40 market–weight pairs. The full C3BO policy has the highest mean AUC among the 14 external methods in Table 4 on every market. Section 6.5 compares the full policy with a rule that samples near both size limits.
  • PyOED optimal design (Table 4, Section 6.5, Appendix G): Across five scenarios per task, C3BO shares the highest mean AUC on tomography (0.524) and trails several baselines on sensor placement (1.194 vs. 1.205 for PBIL). On sensor placement, seven of eight trade-offs have interior optimal sizes.
  • Weaker size effects (Tables 18–19): At mean/SD = 0.5, fitting LL over centred L=0L=0 improves mean AUC by 4.8% on MOKP and 17.2% on Set Cover. At zero mean, neither benchmark shows a clear gain in the matched prior comparison. The full policy still leads random count by 6.65% and 7.00%, respectively. Each paired comparison uses the same GP proposal schedule in both variants.

W2–W3. Applying the size correction to a Gaussian process. We use a linear surrogate in C3BO because its posterior mean can be maximized by a mixed-integer linear solver under the exact constraints. For the online GP test, we add an unpenalized linear term in centred ∣x∣/n|x|/n to the GP mean and hold the qLogNEHVI acquisition, Sobol starts, and repair fixed (Table 2, Appendix K.4). Figure 8 separately reports mixed effects from random count with qLogNEHVI and GIT-BO (−0.9% to +9.7%).

Q1. Runtime and scaling beyond 250 items. At n=250n=250, median wall time per evaluation for full C3BO is 0.57 s on MOKP, 2.64 s on MDK, 3.59 s on Set Cover, and 3.35 s on MWIS (Table 7). The 5 s unrestricted-only comparator takes about 5 s on Set Cover and MWIS. In the matched ablation that fixes the 2.5 s unrestricted stage and duplicate handling, adding fallback improves mean AUC by 4.69% on Set Cover and 2.01% on MWIS (Table 1). In solver-only scaling tests from 250 to 2,000 items (Table 8), median solver time per C3BO proposal stays below 5 s at every size (2.50–4.63 s at 2,000 items). In full online campaigns at 2,000 items (Figures 4–5, Appendix C.1):

  • On MOKP and MDK, early certification reduces full C3BO wall time to 2.62 s and 2.70 s per evaluation while matching unrestricted-only AUC.
  • On Set Cover and MWIS, wall times are similar (~5.0 s), while full C3BO (including fallback and duplicate avoidance) raises mean AUC by 12.2% and 42.6% over unrestricted-only search.
  • Figure 3 shows that allocating 0.5 s instead of 2.5 s of the 5 s budget to the unrestricted stage on Set Cover raises mean AUC by 11.9% and reduces wall time from 5.13 s to 3.12 s per evaluation.

Q2. Exploration and posterior-mean optimization. Yes. C3BO maximizes the posterior mean for each of eight scalarization weights. Batch diversity comes from the weights, fixed-size candidates, and duplicate avoidance. On the portfolios, disabling fixed-size search increases repeats from 186 to 1,021 out of 2,000 evaluations (Appendix H). We have not tested robustness to observation noise. Thompson sampling with the same MILP solver would be a way to test explicit exploration.

Q3. Learning the count versus knowing the size limit. Both policies use the same precomputed feasible size limits when solving fixed-size subproblems (neither is given K⋆K^\star). In the near-boundary control, the sampler is supplied with the binding size limit KbK_b—specifying which limit good designs lie near (the lower limit for Set Cover and the upper limit for the other three benchmarks)—and draws offsets from D={2,5,10,20,40}\mathcal{D}=\{2,5,10,20,40\} toward the interior (Section 6.1, Section 6.3, Appendix K.3). C3BO instead uses the fitted size effect to choose which limit to search toward. With the size-aware prior, the sampler reaches 98–99% of full C3BO's mean AUC. Using the same size-aware surrogate fit, posterior size selection leads the sampler by 0.5–1.4%. The full policy leads by 1.4–2.2% and combines unrestricted search, fallback, and duplicate avoidance (Figure 2, Table 15).

Thank you for your response. I will maintain my score.

Reviewer_kDXWOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
1
Soundness
2
Read review
Paper summary

This paper studies a failure mode in constrained subset optimization: surrogate-based search can choose the wrong subset cardinality even when it optimizes the composition effectively. The authors attribute this to a mismatch between a dominant shared item effect, priors that do not privilege cardinality, and repaired archives with limited count variation. C3BO addresses this through a hierarchical linear prior with a diffuse shared coefficient, followed by an unrestricted mixed-integer solve and fixed-count fallback subproblems. Experiments show substantial improvements on four synthetic additive benchmark families, with more mixed results on two nonlinear optimal-design problems.

Critical strengths
  1. The diagnosis is concrete and supported by controlled interventions. The decomposition into size loss and composition loss is useful. Restoring only the true shared size effect on fixed archives provides stronger evidence for the proposed mechanism than comparisons between complete optimization methods alone.

  2. The additive benchmark gains are large and consistent. C3BO improves held-out hypervolume AUC over count sampling by 10.4–17.8%. Count sampling itself is a useful baseline, showing that explicitly controlling cardinality can improve optimization without modifying the surrogate prior. Also, the experiments compare against extensive relevant baselines.

  3. The paper documents failed predictions, solver-budget defects and reruns, development choices, and the sensor-placement limitation. This transparency makes the empirical conclusions easier to assess.

Critical weaknesses
  1. The paper is difficult to follow. Although my limited familiarity with the area may contribute, the main body introduces several technical concepts without sufficiently explaining how they connect. In particular, the respective roles of the size-aware prior, fixed-count fallback, and deduplication could be presented more clearly. An overview of the algorithm before the theoretical analysis would improve readability.

  2. The strongest evidence comes from a narrow setting that closely matches the proposed model. All four main families use additive objectives with same-sign coefficients drawn from the same distribution. Consequently, they share a strong cardinality effect, and the linear surrogate has the correct functional form. Held-out instances establish replication within these generators, but do not establish robustness to weaker size effects, mixed signs, interactions, or different dimensions. The nonlinear experiments help identify limitations, yet do not demonstrate a consistent advantage over simple alternatives: C3BO trails several methods in mean performance on sensor placement, and its margins over count sampling after deduplication are small.

  3. Most performance gains are explained by the prior correction rather than the count-conditioned fallback. At five seconds, C3BO without fallback is already very close to the full method, and the reported held-out differences against the better single remedy all include zero. The fallback's principal demonstrated benefit is stability under short solver limits. This is useful, but the contribution should be framed primarily as size-aware surrogate modeling, with count-conditioned search as a solver-budget remedy. The hierarchical prior is standard, so the methodological novelty rests substantially on the diagnosis and its validation.

Questions for authors
  1. How sensitive are results to (L=50), the count-offset ladder, and initialization? Would deliberately spreading initial evaluations across feasible counts substantially close the gap?
3 comments

Thank you for highlighting the controlled interventions and asking how initialization and fallback contribute. The size prior still helps with size-stratified starts (Tables 3 and 17), and the fallback reduces run-to-run variability in the 1 s tests on Set Cover and MWIS (Appendix C).

W1. Readability and component roles. Algorithm 1 shows how the three steps work together. We first fit a surrogate with a separate prior scale for the size effect, then search over all feasible sizes. If the solver cannot certify a new design in time, fixed-size subproblems supply alternative candidates. We select the highest-scoring unseen candidate if one is available. Section 6.1 defines the comparison policies.

W2. Weaker size effects, interactions, and different dimensions.

  • Weaker size effects (Tables 18–19): We shift the coefficients in MOKP and Set Cover while keeping the same GP proposal schedule in both variants of each comparison. Fitting the size-prior scale improves mean AUC over centred L=0L=0 by 4.8% on MOKP and 17.2% on Set Cover at mean/SD = 0.5, and by 12.5% and 31.7% at 1.0. At zero mean, the differences are −0.9% and +0.8%, with both intervals including zero at the reported precision. The separate full-policy comparison still favours C3BO over random count at all three strengths, including gains of 6.65% and 7.00% at zero mean.
  • Nonlinear interactions and scaling: On all five OR-Library portfolio markets (coupled quadratic variance), C3BO achieves the highest mean AUC among the 14 external methods in Table 4. On PyOED sensor placement, where seven of eight trade-offs have interior optimal sizes, C3BO trails several baselines (1.194 vs. 1.205 for PBIL), which we discuss in Section 6.5. Figures 4–5 and Table 8 evaluate online optimization quality and solver runtime up to 2,000 items.

W3. Statistical contribution and the role of fallback. We revised the framing to emphasize size-aware surrogate modeling as the primary statistical contribution, with count-conditioned search as a solver-budget and diversity mechanism:

  • Prior contribution: In the matched online comparison, centring, intercept treatment, and search stay fixed. Setting L=0L=0 instead of L=50L=50 lowers mean AUC by 14.2–35.7% across the four generated benchmarks (Table 20).
  • Fallback contribution: Holding the prior, the 2.5 s unrestricted stage, and duplicate handling fixed, enabling fixed-size solves raises mean AUC by 4.69% on Set Cover, 2.01% on MWIS, and 0.68–1.06% on the knapsacks (Table 1, Appendix E). On OR-Library portfolios, disabling fixed-size solves increases duplicate proposals from 186 to 1,021 out of 2,000 evaluations and lowers mean AUC by 13.77% (Appendix H).

Q1. Prior scale, offset ladder, and initialization.

  • Prior scale: On fixed archives, median size-effect recovery exceeds 99% at L=3L=3 and remains near 100% at L=50L=50 (Figure 7). Table 20 compares L=0L=0 and L=50L=50 online.
  • Offset ladder: We use offsets D={2,5,10,20,40}\mathcal{D}=\{2,5,10,20,40\} from the size limit, clip the candidate sizes to the feasible interval used by the solver, merge duplicates, and solve from the interior outward (Section 5.1). Figure 3 varies the solver time split. Sensitivity to the offset set itself remains open.
  • Initialization: Size-stratified starts raise isotropic-prior AUC by 2.8–28.1%. With stratified starts in both variants of the prior comparison, fitting LL improves mean AUC by 1.8–9.8% over centred L=0L=0 across all four benchmarks. These comparisons use the same GP proposal schedule in both variants (Tables 3 and 17).

Dear Reviewer kDXW,

Thank you very much for your help with reviewing for ICLR'27!

The authors have now responded to your reviews. As the discussion period is approaching the end, I'm wondering if you could have a look at the authors' responses and see whether they have addressed your concerns. And could you also leave a comment to let the authors know your thoughts? If any concerns remain, please explain which ones have not been addressed and why.

Warm regards, Your AC

Reviewer_kDXWOpenReview ↗

Official Comment by Reviewer kDXW

Thank you for the response. Some of my concerns have been addressed. I will maintain my score.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General response to all reviewers

Thank you for the feedback. Our revision reports four main findings:

  • For the binary kernels covered by Proposition 1, including the RBF and Matérn ARD kernels we study, the linear size direction receives only 1/n1/n of the first-order prior variance.
  • On the same archives, restoring only the size effect raises the share of proposals within ten items of an optimal size from 0–9% to 63–91% (Table 9).
  • With centring, intercept treatment, and search fixed, removing the extra prior variance for size lowers mean AUC by 14.2–35.7% across the four generated benchmarks (Table 20).
  • In a separate GP pilot, adding a linear size term raises online mean AUC by 3.5–6.8% across the four benchmarks. AUC improves in all 20 paired comparisons, five per benchmark (Table 2).

Algorithm 1 now shows the steps of a C3BO batch, and Section 6.1 defines the comparison policies.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.