acceptodds
Under review as a conference paper at ICLR 2027

Refit or Expand? Finite-Sample Certification of Interaction Surrogates under Compound Shifts

Abstract

Assessing multistage inference under compound distribution shifts requires repeated evaluations across parameter settings because interacting parameters and noncommuting operators can produce non-additive performance changes. Interaction surrogates approximate these joint effects using low-order marginal moments. However, when surrogate error exceeds a tolerance, empirical point estimates cannot establish whether the discrepancy can be resolved by coefficient refitting or requires additional features. We introduce a finite-sample certification framework based on empirical Bernstein confidence intervals. We solve two linear programs: a robust refit program provides an upper bound on the error achievable in the surrogate class, while a dual program provides a lower bound for every class member through the design matrix’s left nullspace. These bounds can certify parameter misfit or feature inadequacy and identify minimal adequate subsets among candidate terms. For bilinear surrogates, the same guarantees hold uniformly over continuous product mixtures of evaluated marginals. Vision and language experiments show when interactions can be omitted, when refitting suffices, and when feature expansion is required. For ResNet-50 on ImageNetV2 under resampling/JPEG shifts, the one-term class has certified error at least 0.185 pp while a two-term surrogate has certified error at most 0.135 pp. For blur/JPEG, order reversal changes error by over 6 pp. The interaction surrogates correct all three order selection errors made by the additive approximation.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
distribution shift, finite-sample guarantees, uncertainty quantification, surrogate modeling, model auditing

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_J2FXOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper investigates the reliability diagnosis of low-order interaction surrogate models under variations in compound parameter distributions. The authors construct linear surrogates using functional ANOVA and polynomial moment features, while constraining the true interaction response via simultaneous empirical Bernstein confidence intervals. By employing robust re-fitting linear programming to derive upper bounds on error, and utilizing left-null-space dual certificates to establish lower bounds on error for the entire surrogate class, the approach enables the diagnosis of specific issues: surrogate sufficiency, coefficient mismatch, feature insufficiency, or a lack of sufficient evidence.

The experiments encompass combinations of image pre-processing steps and language decoding parameters, demonstrating applications such as feature expansion, re-fitting after transfer, and the selection of operator sequences. The provided guarantees are restricted to product mixtures of the marginal distributions for which evaluations have been performed.

Critical strengths
  1. Category-level diagnostics are more valuable than the validation error of an individual model. The paper draws a clear distinction between cases where "the current coefficients are insufficient" and those where "no set of coefficients can meet the requirements." By establishing lower bounds for entire feature categories—while allowing for an "unresolved" status—this diagnostic approach becomes more rigorous and interpretable than simply examining fitting residuals.

  2. There is a strong alignment between the experiments and the theoretical claims. Elements such as independent fitting, the use of certified random samples, simultaneous coverage, the leveraging of covariance in shared evaluations, and the construction of distributions that share the same mean but differ in higher-order moments all directly support the core arguments. Sensitivity analyses regarding sample size and confidence levels further bolster the credibility of the results.

Critical weaknesses
  1. The theoretical contributions and the scope of applicability are not sufficiently highlighted. The core framework combines ANOVA, empirical Bernstein bounds, robust Chebyshev approximation, and LP duality. The paper needs to articulate more clearly what new theoretical capabilities or practical diagnostic advantages it offers compared to existing methods for testing models with set-based constraints. Furthermore, the guarantees provided are specific to fixed evaluation instances and designated distribution families; they do not constitute general out-of-distribution (OOD) generalization guarantees. Additionally, the empirical analysis is limited to two-parameter interactions.

  2. The certification process is computationally expensive, yet there is no comparative analysis to justify this cost. Some experiments require hundreds of full-dataset evaluations, yet the paper fails to compare its approach against alternatives—such as direct importance-weighted estimation or vertex-response caching—under equivalent computational budgets and precision requirements. Consequently, it remains unclear under what types of workloads the upfront certification costs are justified. Moreover, there is insufficient disclosure regarding numerical error budgets, the verification of LP feasibility, and key experimental configurations—details that are particularly critical for a paper centered on "rigorous certification."

Questions for authors

Compared to existing set-membership/model-invalidation and robust approximation methods, what new theoretical capabilities does this paper introduce? Could you illustrate this with specific differences in results or concrete examples? Given the same inference budget and certification precision, what advantages does this approach offer over direct estimation or vertex caching? Please provide data on the number of function calls, actual execution time, and cost amortization.

5 comments

Thank you very much for your thorough review and for highlighting the value of class-wide diagnostics and the close alignment between our theory and experiments! Our goal is certified model reduction of the interaction surrogate for a frozen predictor's pipeline, so as to determine which distributional moments a compact interaction surrogate must retain, when coefficient refitting suffices, and when its feature representation must expand.

1/ Capabilities beyond a coordinate-wise set membership test and scope of guarantees (Weakness 1 & Question 1). A coordinate-wise set membership test starts from an uncertainty box and asks whether a chosen model class contains a response compatible with it. With this, we turn shared randomized pipeline evaluations into simultaneous finite-sample certificates of adequacy, parameter misfit, and feature inadequacy, which provides three capabilities for choosing and maintaining a compact surrogate.

  • A) Covariance preserving dual certificates tighten class lower bounds on top of those obtained from coordinate intervals. By forming each prespecified dual score Su,ν=∑tνtSu,tS_{u,\nu}=\sum_t\nu_tS_{u,t} before estimating variance, we use the shared randomized evaluations to cancel out common per-image fluctuations across contrasted targets. For example, for ResNet-50 under resampling/JPEG shifts (Appendix B.1), this raises the one-term class lower bound from 0.17 percentage points (pp) with the coordinate box B\mathcal{B} alone for the same vector to 0.185 pp, alongside a similar improvement for the exchange-symmetric class.
  • B) Summary-based bounds (Proposition E.2) are not limited to a fixed polynomial surrogate class only, but they can also rule out unrestricted functions of insufficient distributional summaries. As shown in the matched-mean pairs in Section 5.2, every function of the ordered marginal means (including arbitrary nonlinear functions) has worst-case error at least 0.193 pp, but the two-term moment surrogate C2C_2 stays within 0.092 pp, which reveals the information loss from only using the mean-based summary statistics.
  • C) Nullspace certificates can guide feature expansion and be used to identify minimal adequate representations. If there exists a normalized vector ν\nu s.t. X⊤ν=0X^\top\nu=0 that certifies class inadequacy, then any adequate expansion with additional feature columns ZZ must satisfy Z⊤ν≠0Z^\top\nu\ne0 (Appendix E.4). For ResNet-50 under resampling/JPEG shifts on ImageNetV2, term-omission certificates establish {mjmk,mjsk}\lbrace m_jm_k,m_js_k\rbrace as the unique minimal adequate subset of the four-term shifted-Legendre dictionary at 0.15 pp (Section 4.3). Meanwhile, on ImageNet-R, refitting on 16 replicates repairs the transferred one-term surrogate and brings its independently certified error from [0.450, 0.496] pp down to [0.078, 0.125] pp.

Regarding scope, our experiments condition on fixed benchmark instances to isolate shifts in pipeline parameter distributions from the variability introduced by benchmark sampling. To achieve a population-level guarantee, these conditional certificates would need to be combined with an outer sampling bound over independently drawn instances. Across parameter distributions, the guarantees apply to continuous product mixtures of the evaluated marginals (Section 5.1) and specified perturbation families certified in Section 5.2, instead of unconstrained out-of-distribution shifts. Also, because the LPs in Section 3 require only predictions linear in coefficients (XbXb) and valid simultaneous response intervals, higher order tensor-moment dictionaries for three or more operators can be integrated into the same LP framework directly. As the number of operators increases, the main scaling challenge lies in controlling joint importance weights and score variances across larger target and feature sets, which actually further highlights the importance of determining when low order interaction terms shall suffice.

2/ Comparison to vertex caching and direct importance weighting under equal budget (Weakness 2 & Question 2). On ResNet-50 under ImageNetV2 resampling/JPEG shifts, the table below compares direct vertex response caching and C2C_2. One replicate experiment evaluates all 10K images using both operator orders for a total of 20K forward passes.

RepresentationSeparate fitting passesShared offline certification passesCertified upper bound over product mixtures (pp)
Direct vertex response table015.36 million (768 replicates)0.0406
Two-term surrogate C2C_280K (4 replicates)15.36 million (768 replicates)0.1349

Within the evaluated product-mixture family, the 16-vertex table retains all grid estimates without representation truncation and thus achieves the tighter upper bound. In comparison, C2C_2 compresses the response into two fitted coefficients multiplying moment features, while still meeting the 0.15 pp tolerance. Both approaches allow for the subsequent product-mixture queries to be answered in 3-5 microseconds without any model calls. Beyond response querying, our framework provides a certified choice of representation, which determines when interaction terms can be omitted altogether (C=0C=0 in ResNet-50 tone/noise and MMLU), when coefficients can be adjusted, and which moment features are essential. In fact, the computational cost required to derive these structural conclusions is significantly lower than the full evaluation figures shown in the table, as Figure 6 (Appendix B.3) already certifies both class exclusions at 192 replicates and C2C_2 adequacy at 384 replicates. Also, larger decision margins in operator-order selection allow for the use of even coarser bounds (Section 6).

In addition to the evaluated mixture hull, the matched-mean construction in Section 5.2 includes a distribution with second shifted-Legendre moment s=−0.4s=-0.4. This distribution belongs neither to the family of probability mixtures of exponential tilts (see Appendix F.2) nor to the 16-vertex interpolation guarantee. To cover new target families outside this hull via direct importance weighting, one would either need to collect fresh evaluations or to reuse evaluation data from a proposal distribution that covers the new targets. By contrast, C2C_2 retains only the two scalar coefficients from its initial 4-replicate fit to generate predictions based on the moments of a target distribution. This process requires no new model calls and no refitting at all, while a separate 64-replicate (1.28 million pass) evaluation independently certifies that the transfer error for the matched-mean pairs remains within 0.092 pp.

3/ Runtime and workload (Weakness 2 & Question 2). Collecting all 26.88 million forward passes for the four primary ImageNetV2 settings took 16.9 GPU hours in total. In contrast, solving each prepared class-lower-bound or robust-refit LP over the 16 non-reference targets takes about 1 ms on a single CPU thread. Thus, the collection of evaluation data dominates runtime, which is necessary in any case to reduce finite-sample uncertainty and also already shared across all shifted targets under our framework. Without a reusable surrogate model, evaluating new distribution shifts would ask for fresh GPU-based benchmarking for every uncached shift category. In contrast, our upfront inference distributes across two regimes: (1) Lightweight fitting or re-fitting (4-16 replicates or 80K-320K passes in ResNet-50) takes only minutes to estimate a set of shared coefficients to serve repeated queries across shifting distributions with no additional GPU calls. (2) Full offline certification (192-768 replicates) serves as a one-time qualification audit for a stable predictor. A single shared audit can then justify omitting the interaction term (C=0C=0) and establish a minimal moment basis or operator order, which covers all continuous product mixture distributions of the audited marginals without further model evaluations.

4/ Numerical error budgets and solver-independent verification (Weakness 2). Neither our structural exclusions nor our candidate adequacy certificates depend on floating-point LP solver tolerances. For lower bounds, our central class and term-omission exclusions rely on closed-form analytic dual vectors whose feasibility identities (X⊤ν=0X^\top\nu=0 and ∥ν∥1≤1\lVert\nu\rVert_1\le 1) hold in exact arithmetic and don't rely on numerical LP solvers. For upper bounds, any fitted or HiGHS-refitted coefficient vector bb is treated only as a candidate. Then, it is verified post-hoc through UXb\mathcal{U}_{Xb} in Eq. (3) using interval enclosures of XX and XbXb with outward rounding. Therefore, at worst, HiGHS stopping tolerances can yield a slightly more conservative upper bound but never an invalid certificate. Through independent cross-verification using exact rational arithmetic, we reproduced the central structural and candidate bounds reported in the paper. In the primary vision evaluation, the total numerical allowance Δm\Delta_m added to each score interval in Algorithm 1 remains strictly below 3.27×10−73.27\times 10^{-7} pp, which is orders of magnitude below the 0.15 pp tolerance.

Under a 10-page budget, we will clarify the connection to set-membership invalidation and cost amortization in the main text. We can also include the caching comparison, forward pass and runtime summary, and Δm\Delta_m verification details reported above in Appendix C.3.

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

This paper proposes Bernstein confidence intervals that answer the question whether or not model coefficients should be refit or expanded under compound distribution shifts. They define f(a,b)f(a, b) as the expected response over the dataset and decompose it into the average effect M0M_0, the effect of a,ba, b, and the effect of the interaction between a,ba, b. They define shifted Legendre polynomials so that the basis coefficients are independent of each other. Then, the authors refit these coefficients to bound error and define confidence bounds. They include experiments on both vision and language (ResNet-40, ViT-B/16, and ConvNeXt-Tiny on ImageNetV2; ResNet-20 on CIFAR-10; and Qwen2.5-1.5B-Instruct on a stratified massive multitask language understanding (MMLU) sample).

Critical strengths
  • The proposed framework is relevant for real world data where distribution shifts make it hard to understand how well your model is performing.
  • The proposed method provides insight into deep neural networks performance under distribution shifts.
  • The paper includes extensive experiments on both vision and language (ResNet-40, ViT-B/16, and ConvNeXt-Tiny on ImageNetV2; ResNet-20 on CIFAR-10; and Qwen2.5-1.5B-Instruct on a stratified MMLU sample).
Critical weaknesses
  • No comparison to other bounds for this task. It is hard to understand the significance of the proposed method without a comparison to relevant literature. I am not sure what is the most relevant method to compare to is. Zhai et al. (ICLR 2020) and Delattre (ICLR 2024) both proposed Bernstein bounds for noisy inputs and adversarial attacks. The framework proposed in Regol et al. (ICML 2025) is quite relevant for retraining under distributional shift.
  • The authors do not discuss the advantages of the proposed method compared to fine-tuning. No engagement with the continual learning or transfer learning literature. Methods like elastic weight consolidation (EWC) and fine-tuning with wider networks (Net2Net) feel relevant to the proposed framework.
  • Computational complexity is not discussed. How many forward passes per image TT are computed? What is the cost compared to linear probing or fine-tuning?
Questions for authors
  • Why use the chosen operators a,ba, b? Do these capture realistic distributions shifts?
  • L205-206 says “Let VX⊆{ν∈null(X⊤):∥ν∥≤1}\mathcal{V}_X \subseteq \{ \nu \in \text{null}(X^\top) : \| \nu \| \le 1 \} be a finite set fixed before observing the evaluation sample”. Can we use any vector(s) ν\nu in the nullspace of XX? Or do we need every vector ν\nu in the nullspace of XX? Would this only be a lower bound if we had every vector?
  • What does the impact of the number of basis coefficients have on being able to model more functions that aren’t locally smooth (e.g., adding Gaussian noise with a small variance might degrade performance quickly but as the variance increases performance might be more stable).
5 comments

Thank you very much for your review and for recognizing the value in our work! We also appreciate your comment on the presentation gap that, if we do not emphasize upfront that the underlying predictor is frozen, terms such as "refit," "expand," and "transfer" may evoke neural weight adaptation.

1/ Realistic pipeline shifts vs. neural weight adaptation (Question 1 & Weakness 2). Our framework aims to model the interaction effects of processing controls and input degradations whose parameter distributions can vary jointly in deployment, such as tonal changes and additive Gaussian noise across client devices (tone/noise), client-side image downsampling and resizing before lossy upload (resampling/JPEG), Gaussian blur combined with compression (blur/JPEG), and decoding controls across multi-tenant LLM requests (temperature and top-p truncation in standard decoding). Because transformations such as JPEG quantization depend on input resolution and sharpness, composition can be non-additive and order-sensitive. One example we mentioned in the paper is that, for blur/JPEG, reversing execution order changes classification error by over 6 percentage points (pp).

This setting is complementary to continual learning, transfer learning, and retraining schedules. Fine-tuning and linear probing train a predictor or its head. EWC constrains weight updates to reduce forgetting. Net2Net transfers an existing function to a wider or deeper network. Regol et al. (2025) discuss when to trigger predictor retraining. All these works aim to address the training of the predictors themselves.

By contrast, our framework certifies an interaction surrogate for a frozen predictor's pipeline. "Refitting" updates the surrogate's scalar coefficients (one to four in our low order polynomial models) and "expanding" adds distributional features to the surrogate (instead of adding any network units to the underlying frozen model). For example, adding mjskm_js_k alongside mjmkm_jm_k incorporates the second shifted-Legendre moment sks_k of JPEG severity into the surrogate. Because our certification requires no weight updates, it acts as a modular downstream step to be reapplied after a predictor is fine-tuned or retrained.

2/ Comparison to alternative bounds and smoothing certificates (Weakness 1). While Zhai et al. (2020) and Delattre et al. (2024) certify robustness around individual inputs via randomized smoothing, our framework certifies interaction surrogates across shifting parameter distributions, with responses averaged over a fixed evaluation dataset. To benchmark concentration bounds fairly, we compared empirical Bernstein against Hoeffding across all coordinates in the four ImageNetV2 settings (α=0.05\alpha=0.05). In vision, the paired error difference Du∈{−1,0,1}D_u\in\lbrace-1,0,1\rbrace vanishes whenever both orders are correct or both are wrong. Empirical Bernstein adapts to the observed variance of the importance-weighted scores, which for the interaction coordinates is much smaller than the worst-case scale Bm2B_m^2, whereas Hoeffding uses only the bounded range. At the 0.15 pp tolerance, empirical Bernstein certifies the selected surrogate in 3 out of 4 settings, while Hoeffding certifies 0 out of 4. For ResNet-50 under resampling/JPEG shifts, the two-term surrogate's error upper bound tightens from 0.4235 pp with Hoeffding to 0.1349 pp with empirical Bernstein (over 3x tighter). Furthermore, empirical Bernstein enables the prespecified dual vectors to certify the exclusion of both exchange-symmetric and one-term classes, while the corresponding Hoeffding checks remain inconclusive.

3/ Computational complexity and forward pass cost (Weakness 3). First, we note that unlike linear probing or fine-tuning, surrogate fitting updates no backbone or head parameters and requires no backward passes or neural-network optimizer states. Compute is dominated by forward evaluations, with LP solve times reported below. Using ResNet-50 (resampling/JPEG) as an illustrative example, the costs from forward passes separate into three stages:

  • For surrogate fitting (8 forward passes/image), four dataset replicates, each evaluating both operator orders with fresh severity draws from the uniform reference distribution, estimate the surrogate coefficients once for all target shifts.
  • For downstream shift queries (0 forward passes), interaction predictions use low order marginal moments. For bilinear surrogates, the bound certified on all evaluated product pairs extends to their entire continuous product-mixture family (Section 5.1), with no additional model calls or labels for these queries.
  • Then, one-time offline certification (384 to 1536 forward passes/image) is performed. Crucially, a single set of forward passes is reused across all shifted target distributions via importance weighting. Our primary audit prespecified 768 replicates (1536 passes/image, at 2 passes/replicate across both orders) for simultaneous 95% certification across all candidates and term-omission tests at the stringent 0.15 pp tolerance. Under this same 0.15 pp tolerance and confidence allocation, the evaluations at fixed prefixes in Figure 6 (Appendix B.3) show that 192 replicates (384 passes/image) already certify the class exclusions and 384 replicates (768 passes/image) certify two-term adequacy. Also, we showed that larger ordering margins (Section 6) permit coarser bounds.

Once score summaries are aggregated, solving the class lower bound and robust-refit LPs across the shifted targets (Eqs. (5) and (6)) takes about 1 ms per solve on a single CPU thread (warm median), so runtime is dominated by collecting forward evaluations. Importantly, surrogate fitting at 8 forward passes/image remains far lighter than fine-tuning or linear probing across shifts, since a single fit serves all target distributions and subsequent queries don't require new target labels or model calls. Note that linear probing cannot bypass these evaluations by caching clean-image features either, because pixel-level transformations act before the first network layer and require re-evaluating transformed inputs. By contrast, the larger one-time audit budget is incurred only to certify guarantees at a 0.15 pp tolerance across the entire shift family.

4/ Role of the prespecified dual-vector set VX\mathcal{V}_X (Question 2). For the design matrix XX, you do not need every vector in its left nullspace null⁡(X⊤)\operatorname{null}(X^\top) for a valid lower bound. Any vector ν\nu with X⊤ν=0X^\top\nu=0 and ∥ν∥1≤1\lVert\nu\rVert_1\le1 satisfies, for every coefficient vector bb, ∣ν⊤F∣=∣ν⊤(F−Xb)∣≤∥F−Xb∥∞|\nu^\top\mathbf F|=|\nu^\top(\mathbf F-Xb)|\le\lVert\mathbf F-Xb\rVert_\infty by Hölder's inequality. Then we take the infimum over bb for the class-wide lower bound. The class approximation error equals the supremum over all such normalized nullspace vectors, so restricting to any subset can only make the lower bound more conservative and never invalid.

Moreover, although the dual LP in Eq. (5) already optimizes over the entire normalized left nullspace using the coordinate-wise confidence box B\mathcal{B}, evaluating prespecified dual vectors in Eq. (7) preserves cross-target covariance. For our prespecified contrasts, forming Su,ν=∑tνtSu,tS_{u,\nu} = \sum_t \nu_t S_{u,t} on shared evaluation units before computing empirical variance cancels out common per-image fluctuations across the contrasted targets. In our examples, this helps tighten ResNet-50's one-term lower bound under resampling/JPEG from 0.17 pp using B\mathcal{B} alone to 0.185 pp (Appendix B.1). Requiring VX\mathcal{V}_X to be finite and fixed before observing the evaluation sample is what preserves simultaneous (1−α)(1-\alpha) coverage in Proposition 2, which keeps the union-bound count MM finite and avoids post-hoc selection on the evaluation data.

5/ Locally non-smooth responses and basis capacity (Question 3). Rapid transitions (e.g., accuracy dropping sharply at small Gaussian-noise variance before plateauing) compromise neither statistical validity nor diagnosis. First, Proposition 2 requires only bounded scores and independent sampling units with no smoothness assumptions. But also, our surrogate targets the distribution-averaged interaction response F(P)=⟨g,hP⟩L2(P0)F(P)=\langle g,h_P\rangle_{L^2(P_0)}, where integration over the exponential-tilt family gives a smooth response as the distribution parameters vary (compared to interpolating pointwise jumps). Then, for basis capacity, Proposition E.1 separates truncation error by omitted basis terms from coefficient error. When steep transitions require more capacity than low order polynomials provide, the basis can be expanded (up to the 64 term spline benchmark in Table 4, Appendix B.1). Also we note that if an underparameterized class is retained whose best approximation still exceeds tolerance, at confidence 1−α1-\alpha it cannot be certified as adequate. In this case our procedure either flags "feature inadequacy" across all coefficient choices when the class lower bound exceeds tolerance, or returns "unresolved" when sampling uncertainty leaves the diagnosis inconclusive.

Under a 10-page budget, we will revise Section 1 to distinguish predictor weight adaptation from interaction-surrogate certification upfront, and include both the Hoeffding benchmark and the forward pass cost breakdown in the appendix.

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

This paper proposes a method to assess whether coefficient refitting is sufficient for an interaction surrogate to meet an error tolerance or additional features are needed.

Critical strengths

The paper provides theoretical analysis and experiments to evaluate when refitting is sufficient and when feature expansion is needed.

Critical weaknesses

The practical usefulness of the method is still unclear to me. The paper could better explain when these surrogates are needed in computer vision or language tasks.

Questions for authors
  1. Can this method be applied to scaling laws for LLMs?
  2. In practice, how should users decide whether to refit or expand the surrogate, collect more data, or use a larger underlying model?
5 comments

Thank you very much for your review and for prompting us to emphasize the importance of practical workflows more clearly!

1/ Usefulness. In large-scale vision services or multi-tenant LLM platforms, pipeline controls (such as client-side image resize/compression levels or request-level decoding parameters) vary across user cohorts, network conditions, policy updates, and more. Re-evaluating a frozen model across a full benchmark for every new joint parameter distribution is costly, but then, summing each control's separate marginal effect (an additive approximation) can miss interactions that flip the best pipeline setting. An interaction surrogate avoids repeated model inference, because once fitted and certified offline, it predicts interaction effects for new operating distributions directly from low order marginal moments without any additional model calls. For the same model and benchmark, bilinear moment surrogates retain their certified bound across continuous product mixtures of evaluated marginals at no extra evaluation cost (Section 5.1). When the operating distribution shifts, our certification diagnoses whether to retain this lightweight surrogate, refit its coefficients, or expand its distributional features.

Concrete engineering decisions in CV and NLP. In vision, we track how shifted distributions of transformation severities affect the classification-error gap between two preprocessing orders. Under shifted distributions of image resampling (downsampling/resizing) and JPEG compression severities for ResNet-50, transferring the one-term surrogate fitted on ImageNetV2, which uses only the product of centered and scaled mean features (mjmkm_jm_k), gives a certified worst-case error in [0.450, 0.496] percentage points (pp) on ImageNet-R and exceeds the 0.15 pp tolerance. However, as our framework suggests, refitting the single coefficient on 16 replicates (randomized dataset evaluations of both orders with fresh severity draws), followed by independent certification, reduces certified error to [0.078, 0.125] pp and establishes adequacy with the upper bound less than 0.15 pp. By contrast, for the same frozen ResNet-50 pipeline across the primary shifted severity distributions on ImageNetV2, every coefficient choice in this one-term class has error at least 0.185 pp, whereas expanding to a two-term surrogate by adding the feature mjskm_js_k, where sks_k is the second shifted-Legendre moment of JPEG severity, yields a certified error upper bound of 0.135 pp, below the 0.15 pp tolerance. Together, these cases separate repairable parameter misfit from feature inadequacy.

As such, these certified bounds are able to provide guidance on downstream pipeline order choices. When composing Gaussian blur and JPEG compression, reversing operator order changes classification error by over 6 pp under some target distributions. Across ResNet-50 and ViT-B/16 (16 compound shift distributions per model), the certified interaction surrogates identify the order with a lower error on every target distribution and fixes all three ordering mistakes made by the additive baseline. Conversely, in standard Qwen2.5-1.5B-Instruct decoding on MMLU under the tested joint shifts in temperature and top-p distributions, the zero interaction surrogate (C=0C=0, omitting the interaction) has a certified error upper bound of 1.02 pp, within the 2.0 pp tolerance. Here, certification justifies summarizing temperature and top-p effects additively across these distributions with no interaction term needed at the stated tolerance.

2/ Connection to LLM scaling laws (Question 1). Our framework doesn't certify extrapolation to unseen scales, but it could be used prospectively to audit scaling-law fits, by asking "when a scaling relationship fails in a new regime, can its coefficients be refitted, or is a richer functional form needed?" For candidate forms that are linear in their coefficients (e.g., power-law terms with fixed exponents, or prespecified interactions among log model size, data-mixture ratio and log inference budget), the same linear programs can test whether refitting suffices or basis expansion is required across a grid of evaluated checkpoints. This requires valid simultaneous intervals for checkpoint performance, which can be obtained, for example, from independent evaluation batches on a bounded benchmark metric.

3/ Practical decision rule (Question 2). The decisions separate predictor performance from surrogate maintenance.

  • Upgrade the underlying model: Move to a larger or adapted predictor when the absolute task accuracy falls below application requirements. Usually, this can be observed either during baseline checks, which in practice take place before deployment or before treating a model as frozen (and thus well before a surrogate is needed), or after a shift even under the best preprocessing or decoding setting.
  • Retain: Keep the current surrogate when its certified error upper bound meets tolerance.
  • Refit: Update coefficients when the current surrogate is certified to exceed tolerance while another coefficient vector in the same feature class is certified adequate.
  • Expand: Add distributional features when the class lower bound exceeds tolerance, ruling out every coefficient choice in the current representation.
  • Collect more data: This question has two separate layers. For whether more data is needed for the underlying model, the same guidance can be applied as "Upgrade the underlying model". To reduce uncertainty in the surrogate certificate, add evaluation replicates when sampling uncertainty causes the relevant certified bounds to cross the tolerance threshold and makes the diagnosis inconclusive.

Under a 10-page budget, we will revise Section 1 to lead with this pipeline workflow and distinguish predictor selection from surrogate maintenance upfront.

Thank you again for your thoughtful review and constructive feedback!

We have now uploaded a revised version of the manuscript that has incorporated the clarifications and improvements in response to the concerns raised in your review.

We would greatly appreciate it if you could take another look at the revised manuscript. If any questions or concerns remain, we would be happy to clarify them anytime. Thank you very much for your time and consideration!

Comments on the paper

2 comments
AuthorsOpenReview ↗

Summary of Manuscript Revisions

Dear Reviewers and Area Chair,

Thank you very much for your constructive feedback. We have uploaded a revised version of the paper, in which we address the concerns raised by the reviewers and provide additional analysis. The key revisions are summarized below:

1. Deployment setting and terminology (73RH, zfTE). Section 1 now opens with the practical setting, in which a frozen predictor runs inside configurable processing or decoding stages, where the distribution of the controls for these stages is subject to shift. We clarify that coefficient refitting and feature expansion act on the interaction surrogate instead of on the frozen predictor itself.

2. Positioning and contributions (zfTE, J2FX). We have expanded the discussion (Section 7.1) to include predictor adaptation (fine-tuning, EWC, Net2Net), retraining schedules (Regol et al.), and randomized smoothing (Zhai et al., Delattre et al.). Furthermore, we clarify what our certificates add to set-membership tests for model invalidation, namely class lower bounds that use cross-target covariance and summary mappings, and an explicit Unresolved outcome (Sections 1 and 7.1).

3. Comparison between empirical Bernstein and Hoeffding bounds (zfTE). We include a new comparison that shows that empirical Bernstein bounds establish adequacy in many cases that Hoeffding bounds fail (Section 4.3, Appendix B.3).

4. Computational cost and alternatives (zfTE, J2FX). We report the number of forward passes used for fitting and certification, the time for the prediction and LP solving, and how the cost of the initial evaluations is amortized. We also compare the surrogate model with interpolation of cached responses and with direct importance weighting (Section 7.2, Appendices C.2 and C.3).

5. Numerical verification (J2FX). We document the numerical error budget Δm\Delta_m, the feasibility of the closed-form dual vectors, and the post hoc verification of upper bounds (Appendix C.3).

6. Scope of the guarantees and extensions (J2FX). We state that the intervals are with respect to a fixed evaluation dataset and can be combined with an outer sampling bound for population risk. Also, we state that the bounds of one certification run apply to both the evaluated targets and their continuous product mixtures. Furthermore, we describe how the framework extends to three or more pipeline stages (Section 7.2, Appendices C.3 and G.1).

7. Operators, dual vectors, and basis capacity (zfTE). We explain why resampling and JPEG do not commute (Section 4.3), why the dual scores use vectors fixed before evaluation (Section 3.2), and how truncating the basis separates truncation error from coefficient error (Section 2.2). The third-moment test that was previously in the appendix is now summarized in the main text (Section 5.2).

8. Presentation (73RH, zfTE, J2FX). We improve the presentation by remaking the figures and further polishing the language.

We hope these revisions further clarify the practical utility, computational cost, and scope of the framework. Should you have any further questions, we would be happy to address them any time.

Thank you again for your time and consideration!

AuthorsOpenReview ↗

Closing summary and appreciation

Dear Reviewers, Area Chair, and Senior Area Chair,

As the discussion period is ending in less than 1 hour, we want to thank you for the time you have put into this submission. The reviews made the paper clearer and more complete, and we summarize below what changed because of them.

Main idea of the paper. When using a compact interaction surrogate model (as a lightweight alternative) for a frozen prediction model (which is usually computational expensive), there are not established validation methods to distinguish whether a failure to meet error tolerance requirements stems from the need to refit the coefficients, or from the feature class being fundamentally inadequate. In this work, we propose finite sample certification framework to distinguish these two cases that's both supported theoretically and validated with experiments across various deployment scenarios.

Improvements in the revised manuscript based on reviewers' feedback.

  • More intuitive opening for broader audience (73RH, zfTE). Section 1 now opens with the more context in deployment setting. We also highlighted that both coefficient refitting and feature expansion are performed on the surrogate model, for how to improve the lightweight alternative, over a frozen underlying predictor.
  • New comparison with alternative choice of bounds (zfTE). A new comparison demonstrates empirical Bernstein certifies 3 of 4 ImageNetV2 settings at the target threshold where Hoeffding certifies none.
  • Computational cost (zfTE, J2FX). We have added the number of forward passes, GPU hours, LP solve times, and the decomposed compute required by each single step to complete the one-time audit from the beginning at GPU evaluation data generation to the end.
  • Alternatives at matched budget (J2FX). We have included the comparison against vertex caching and direct importance weighting.
  • Relation to set-membership tests and numerical verification (J2FX).

Our work aims at enabling both the interaction surrogate models as a computationally inexpensive solution for current AI models increasingly larger and thus the evaluation of control interactions increasingly prohibitive, and its value in its provision of a certified representation choice and its support for transfer beyond the evaluated family of features.

Thank you again for your service. We are glad to clarify anything further in the remaining window if it would help.

Best wishes, The Authors of Submission 46699

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.