acceptodds
Under review as a conference paper at ICLR 2027

FINITE ADAPTABILITY OF COUNTEREXAMPLE LIBRARIES

91 views

Abstract

How many fixed noise witnesses cover every measurement batch compatible with a pair of model predictions? Under diagonal error, requests and witnesses share a knapsack constraint. Identical best coverage and demand sizes within a factor of two can still yield exponentially different library sizes. We separate informa- tion lost by grouping requests from information lost by grouping completions. An input-level test computes the unique coarsest partition preserving compati- ble demand, constructing groups within a cap or certifying its insufficiency. Op- timistic and robust type programs then bracket the full fractional cover with a computable loss guarantee; partial-demand counts supply lower certificates when stability fails. Distinct-weight families isolate joint information beyond optimal packing and strengthened counting, and quantify unavoidable aggregation loss. On all 164 small instances, canonical grouping expands eight-group bracket appli- cability from 39 to 157; 107 of these 157 brackets have ratios at most 1.25. All 48 optimized witnesses require more than eight stable groups, exposing a substantial transfer boundary. Checked greedy libraries and matched-time counting/packing controls distinguish stronger certificates from changed integer decisions and from runtime gains.

Primary area:
optimization
Keywords:
batch experimental design, robust optimization, uncertainty quantification, countermodel learning, implicit hitting sets, measurement complementarity

Reviews

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

The paper studies the minimum number of fixed counterexamples needed to cover all compatible measurement batches of a given size for a fixed pair of models. Under diagonal ellipsoidal uncertainty, this becomes a set cover problem in which both queries and covering sets satisfy the same knapsack constraint. The authors develop grouped linear programming bounds, quantify aggregation loss under a demand-stability condition, and characterize the coarsest partition satisfying this condition. They also construct examples separating library size from aggregate coverage statistics and demonstrating gaps between joint LP bounds and counting or packing bounds. Experiments examine the applicability and tightness of the bounds, their impact on integer capacity decisions, and computational performance.

Critical strengths

The paper studies a meaningful structural question: how much information about covering cost can be retained after grouping coordinates? Distinguishing demand feasibility from covering-set feasibility identifies two different sources of aggregation loss.

The framework provides computable fractional-cover certificates. Theorem 2 quantifies the loss when only demand feasibility is preserved, with an order-tight worst-case dependence on the retention factor. Theorem 3 makes the demand-stability requirement constructive by computing its coarsest valid partition.

Critical weaknesses

The theoretical increment over established covering and symmetry methods is modest. Theorem 2 combines a model-specific safe-contraction condition with standard subset sampling and fractional-weight rescaling. The structural part of Theorem 3 follows from classical twin equivalence and threshold ordering. These results organize known techniques effectively, but provide limited new understanding of what makes the shared-knapsack covering problem substantially different.

More importantly, the grouping criterion does not control the covering information that the method aims to preserve. Theorem 3 minimizes the number of groups needed to preserve demand feasibility; Theorem 2 evaluates the loss after a partition has been chosen. This leaves the problem of finding a compact, accurate representation unresolved. Indeed, with the same two-group budget, an alternative partition can recover the fractional optimum exactly while the prescribed median refinement produces an upper-to-lower bound ratio of (\Omega(E^2)). Thus, the method can lose substantial information even when an exact representation is available at the same size.

The separation results do not resolve this central limitation. They show that coarse statistics and packing can miss covering complexity, but do not establish that joint LP constraints are essential once counting is allowed to select more informative demand classes. Consequently, the evidence for a substantial advance in preserving or recovering covering information remains limited.

Questions for authors

What connects the proposed grouping rule to the goal of preserving covering information? Consider (k=2), with (2m-2) coordinates of weight (1), two of weight (m-1), and (T=2m-3/2). All pairs are feasible, so the coarsest demand-stable partition has one group. With a two-group budget, median refinement yields (U\ge\binom{m}{2}) and (D\le6), whereas separating the light and heavy coordinates gives (D=U=\tau^*). The example persists under sufficiently small distinct perturbations. How does the framework address this unbounded loss relative to an exact representation at the same group budget? What theoretical guarantee supports the choice of groups beyond preserving demand feasibility?

Within the shared-knapsack model, does joint LP analysis retain a nonvanishing asymptotic advantage over the strongest uniform-counting bound on an arbitrary demand subfamily, [ \max_{\varnothing\ne S\subseteq\mathcal U_k} \frac{|S|} {\max_{C:,w(C)\le T}|{B\in S\subseteq C}|},? ] This directly tests whether joint pricing captures covering information that optimized counting cannot recover. Separations from aggregate statistics, packing, or unions of a prescribed set of demand types do not settle this question. What structural conclusion about the additional power of joint pricing can the paper establish at this level?

Reviewer_LsBkOpenReview ↗
Rating
1
Confidence
1
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper studies how large the noise tolerance (error witness) set should be to capture a batch of observations.

Critical strengths

For now, it is unable for the reviewer to identify the strength of the paper.

Critical weaknesses

The paper is hard to read, for that a list of issues in abstract is given as follows.

  • The keyword "counterexample" is not explained, and it is not clear how the "counterexample library" is used.
  • Line 11: the key term "noise witnesses" is not clearly defined (or not even defined). As it is further used to cover the measurement batches for a pair of model predictions, it is very hard to understand what problem was studied.
  • Line 12: "diagonal error" is not specified.
  • Line 21: how are small instances used to access the proposed method?

The issues are not just in the abstract, it is everywhere. Generally, the paper is not well written. The authors are recommended to revise the paper such that it is readable to more general audience.

Questions for authors

See weaknesses.

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

The paper studies a specific experimental design problem. Suppose that two models differ by some parameter difference dd, and that one wants to choose a batch of size kk that makes the two models distinguishable despite bounded observation error. Equivalently, for a given model difference dd one can consider the collection of kk coordinate batches that are compatible with that difference, i.e., batches for which the prediction difference can be hidden by the measurement error. Once this collection of compatible batches is characterized, the problem can be formulated as a covering problem by constructing a small collection of "completions" such that every compatible batch is covered by at least one completion. The main contribution of the paper is to avoid explicitly enumerating this potentially exponential collection of batches. The authors partition the coordinates into groups, represent batches and completions by their type (the number of coordinates selected from each group), count how many batches have each type and formulate a reduced LP. This provides lower bounds on the required collection size and under stronger assumptions characterizes the exact fractional optimum.

Critical strengths

The paper approaches the problem from a combinatorial perspective, using compatible batches and cover characterization from [1]. Perhaps this is a promising way of exploiting the underlying structure of the experimental design problem. In particular, the reduction based on grouping coordinates and considering batch and completion types is potentially useful because it replaces an explicit enumeration of batches by a substantially smaller combinatorial representation. The geometric structure of the problem is also used in a natural way in this reduction.

Critical weaknesses

My main concern is that the paper is currently difficult to read and, in several places, difficult to understand without already being familiar with the related work. In particular, several central notions are used before they are sufficiently defined or motivated. For example, at the beginning of the paper, notions such as model differences, prediction differences, and target differences are used (lines 85-86) without what I found to be sufficiently explicit definitions. Similarly, terms such as "compatible requests" and "legal cancellation" (line 92) appear before their meaning and role in the argument are made clear. Since these concepts are fundamental to the subsequent combinatorial formulation, I think the paper has to introduce them carefully and providing a simple motivating example.

More generally, the exposition appears to rely quite heavily on the reader already being familiar with the framework and notation of the [1] on which the present work builds. Reusing established terminology is reasonable, but the paper should nevertheless be sufficiently self-contained to allow a reader who knows the general problem but not the previous paper to understand the definitions and the motivation. At present, I found that the lack of explicit definitions made it difficult to identify the precise problem being solved and to understand the significance of the subsequent results.

I also think the abstract should substantially improved. The current version introduces specialized notions such as "diagonal error" and "witnesses" very early, before clearly stating the general problem and the main result. I would recommend starting with a concise description of the experimental design problem explaining why the covering formulation is relevant and only then introducing the specialized terminology. This would make the contribution much easier to understand for readers who are not already familiar with the terminology.

A related issue concerns the main question stated in the abstract and introduction, if I understand it, this question suggests that the paper will provide a characterization or answer for the minimum number of witnesses required. However, the main results seem to provide bounds on the required number of witnesses rather than a general answer to this question. If this is indeed the intended scope of the results, I think the question in the abstract and introduction has to be changed to better reflect what is actually established. Alternatively, the paper should make more explicit which assumptions are required to obtain an exact answer and distinguish this from the more general lower bound.

Questions for authors
  • How is the set Ξ\Xi chosen in practice? From my understanding, the setting considered in the paper is deterministic, and the error set Ξ\Xi plays an important role in the formulation. I would therefore be interested in understanding hown this set is expected to be specified in practical applications. In particular, the usefulness of the framework seems to depend significantly on whether the sets determined by cc or Σ\Sigma provide a realistic description of the observation error. In applications, these error sets may have considerably more complicated geometry than the idealized structure considered in the paper. It would be helpful if the authors could discuss how Ξ\Xi can be obtained or estimated from data and how sensitive the proposed bounds are to the choice of Ξ\Xi.

  • In line 788, the paper states: "There are at most (E+1)G(E+1)^G completion types; counting compatible requests can still be expensive when kk grows." Can you provide a more explicit complexity analysis of this step? In particular, how does the computational cost depend on EE, GG and kk. The asymptotic expression alone may not fully characterize the practical usefulness of the reduction since the constants and the typical values of these parameters could be important. It would therefore be useful to provide either a complexity bound with explicit dependence on these parameters or in the experiments, giving hints to regimes in which type enumeration remains tractable.

[1] Jannis Kurtz. Bounding the optimal number of policies for robust K-adaptability. Mathematical Programming, 2026. doi: 10.1007/s10107-026-02329-1

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.