acceptodds
Under review as a conference paper at ICLR 2027

KakeyaShare: Incidence-Structured Query Sharing for Simultaneous Directional Risk Certification

Abstract

Estimating local model risk along several directions can require many black-box evaluations. Overlapping neighborhoods offer reusable observations, yet exploiting them while controlling every directional error requires more than pooling queries. We introduce KakeyaShare, a simultaneous auditor for bounded loss averages over tubes in a three-dimensional input chart. The method groups locations by their exact tube memberships, so one estimated intersection mean contributes to all member directions. A geometry-only criterion selects a budget-feasible core, residual regions preserve the remaining mass, and an exact integer allocation distributes evaluations across the resulting strata. Independent volume measurements and weighted concentration yield simultaneous finite-sample intervals, while a finite-incidence bound relates the ideal sharing gain to mean tube multiplicity. At the main geometry, interpolation gives about 33.5% fewer queries than independent Monte Carlo at matched radius and 95% simultaneous confidence. Independent reference evaluation shows that median dataset RMSE decreases from 0.00619 to 0.00484; controlled ablations and cross-predictor execution expose the effects of allocation, geometry uncertainty, and rejection cost. These results show how finite tube incidence supports query reuse in simultaneous certification of local risk averages.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
uncertainty quantification, model auditing, Monte Carlo sampling, stratified sampling, finite-sample certification, query-efficient estimation, geometric incidence, black-box models

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

This paper proposes the KakeyaShare procedure for simultaneously estimating bounded loss averages over directional tubes in a three-dimensional input chart by grouping locations according to exact tube memberships. The main contribution lies in combining incidence-based stratification, resource allocation, and volume calibration, which yields simultaneous risk coverage guarantee.

Critical strengths

The sharing construction is intuitive, and the integer allocation is optimal for its stated sampling objective. The risk coverage argument explicitly accounts for geometry-estimation error, which is essential for a valid certification method.

Critical weaknesses

1. Optimization criterion and novelty. The proposed allocation scheme is optimal for the objective in Equation (7), but not necessarily for the final certified interval width, which also involves geometric uncertainty. Moreover, the resource allocation is closely related to classical stratified sampling and Neyman allocation, which limits the methodological novelty.

2. Practical efficiency. The query savings are reported only against Monte Carlo with Hoeffding intervals. It is unclear whether the saving persists when Monte Carlo uses tighter confidence bounds. It would be better to establish whether fewer model calls actually reduce total runtime after accounting for the additional geometry computation.

Questions for authors

1. (Optimality) Why minimize the sum of squared sampling radii in Equations (6)-(7) rather than the final R2R_2 or R∞R_\infty, which include geometry uncertainty? How would these alternative criteria affect the core selection and budget allocation?

2. (Theoretical guarantee) Theorem 1 establishes the simultaneous risk coverage, and Equation (13) bounds the sharing gain under the full partition. But there seem to be no theoretical conditions on NN, KK, or GgG_g that ensure a narrower certified radius than IMC at the same query budget.

3. (Simulation) In Table 2, how would incorporating geometry uncertainty into core selection change the selected core and the final R2R_2?

4. (Presentation) A small concern about Figure 2. It is overly dense, which makes the key idea hard to understand.

3 comments
AuthorsOpenReview ↗

Response to Reviewer MgcE (Q1, Q2)

We sincerely thank the reviewer for identifying the core technical questions and for recognizing the validity of the geometry-aware coverage argument and the exact integer allocation. Your review prompted us to strengthen the theory rather than simply restate the original claims. The revised paper adds two formal results that directly address Q1 and Q2 (Propositions 1–2, p. 6; complete proofs in Appendices B.8–B.9), while preserving the original algorithm and experimental protocol.

Q1. Why minimize the squared sampling radii rather than the final certified radius?

Equation (7) is an intentional optimization target: it measures how one accepted observation contributes across all directional estimates and has an exact integer minimizer, not a rounded continuous heuristic. The revised Proposition 2 now quantifies what this choice costs relative to optimizing the final, geometry-calibrated RMS radius.

Fix the core, calibrated reconstruction matrix, and geometry-error vector. Let nΦn_\Phi minimize Eq. (7) and let n⋆n^\star minimize the final R2R_2 over the same feasible integer allocations. Write S⋆S_\star for the RMS sampling radius attained by nΦn_\Phi and GG for the RMS geometry-error term. Then

\leq S_\star+G-\sqrt{S_\star^2+G^2} \leq\min\{S_\star,G\}.$$ Moreover, $$\frac{R_2(n_\Phi)}{R_2(n^\star)}\leq\sqrt{2}.$$ This is a uniform approximation guarantee for the final certified RMS radius, not merely a statement about a surrogate. In particular, the additive gap vanishes as the geometry error vanishes. We distinguish this fixed-core $R_2$ guarantee from optimizing the maximum-direction radius $R_\infty$, which is a separate objective. The proof is in Appendix B.9. Q2. When does KakeyaShare provably outperform IMC at equal budget and confidence? We now provide the requested finite-budget sufficient condition for the final certified radius, rather than relying on the ideal full-partition gain of Eq. (13). The revised Proposition 1 fixes the design-selected core, assumes $N > K+D$, $D\mid N$, and feasible exact stratum sampling, and incorporates its actual incidence benefit $$B_C=\sum_{S\in C}\bigl(\lVert w_{S:}\rVert_1-\lVert w_{S:}\rVert_2\bigr).$$ For total failure allowance $\delta=\delta_s+\delta_g$, define $$\alpha=\sqrt{\frac{\log(2D/\delta_s)}{2D(N-K-D)}},\qquad \beta=\frac{\sqrt{K}+\sqrt{2\log(D/\delta_g)}}{\sqrt{G_g}},$$ $$r_0=\sqrt{\frac{D\log(2D/\delta)}{2N}}.$$ If $$\boxed{\alpha\bigl(D-B_C+D\beta/2\bigr)+\beta/2 < r_0,}$$ then the final, unclipped KakeyaShare RMS certified radius is strictly smaller than IMC's Hoeffding radius at the same total budget and confidence, with conditional probability at least $1-\delta_g$ over the independent geometry-calibration stream. Theorem 1 continues to guarantee simultaneous coverage at level $1-\delta$. Appendix B.8 proves the bound, explicitly accounts for integer initialization and weight-calibration perturbations, and gives a sufficient lower threshold on $G_g$. Crucially, this is a sufficient, not necessary, condition; it does not assert favorable overlap for every tube family. The observed calibrated main-geometry result is already compelling: at $D=12$, $N/D=512$, and common 95% simultaneous confidence, KakeyaShare gives $R_2=0.063860$ versus IMC's $0.077647$, a 17.8% narrower RMS certificate. The interpolated matched-radius crossing is 340.5 versus 512 accepted queries per direction, a 33.5% reduction (Appendix C.7). We deliberately distinguish this observed comparison from numerical verification of the conservative true-volume sufficient condition, for which the reported aggregate tables do not provide all inputs.
AuthorsOpenReview ↗

Response to Reviewer MgcE (Q3, Q4)

Q3. How would including geometry uncertainty affect core choice?

The existing ablation already reveals the direction of this effect. At N/D=1024N/D=1024, the fixed 360-atom core yields final R2=0.046217R_2=0.046217, while the sampling-selected 450-atom core yields 0.0466240.046624: the smaller core is approximately 0.9% better on the full certified objective among these two evaluated candidates (Table 2). Increasing the core can reduce the sampling term while increasing the number of calibration categories and thus the geometry term. Revised Appendix A.2 now sets out how a geometry-aware design-stage objective could include both terms while keeping final calibration independent. This is evidence of the trade-off, not a claim that a new global core optimizer has already been implemented.

Novelty, tighter confidence bounds, runtime, and Q4

Novelty lies in the statistical unit and the valid end-to-end construction, not in claiming to invent Neyman allocation. Mixture methods reuse queries but retain random directional membership and importance weights inside each directional observation. KakeyaShare instead estimates one bounded mean per exact-membership atom, then propagates that mean into several targets using independently calibrated geometric coefficients. Budget-aware compression and exact joint allocation make this representation executable; Theorem 1 and Propositions 1–2 establish its coverage and finite-budget behavior.

The comparison includes Union-HT, DM-MIS, OptDM-MIS, and Multiplicity-Neyman, not just IMC (Table 1; Appendix C.2). We also take the tighter-bound question seriously: the revised Appendix A.2 explicitly reports that empirical-Bernstein IMC can yield narrower intervals than our Hoeffding-based certificate (Appendix D.5). This does not invalidate our certified comparison, but it precisely identifies the boundary of the claim: we establish an advantage for the stated simultaneous, range-based Hoeffding certificate, not dominance over every variance-adaptive method. The reported empirical-Bernstein offline radii have not been separately accompanied by a coverage experiment.

For efficiency, we do not equate fewer black-box calls with unconditional wall-clock speedup. Table 3 reports equal-query execution overhead; Appendix D.6 provides an explicit cost-amortization condition that includes geometry setup and rejection. Where model calls are expensive and canonical geometry is reusable, avoided evaluations can offset that work.

Finally, Figure 2 has been completely redrawn (p. 4) to present the core idea in three direct steps—find shared atoms, estimate a bounded atom mean, reuse it across directions—and the opening now explains an explicit risk-screening decision.

We believe the two newly proved propositions directly resolve the principal theoretical questions, while the revised figure and comparison discussion substantially strengthen the novelty and presentation. We respectfully ask the reviewer to reconsider the recommendation in light of these changes.

I appreciate the authors' clarifications and the additional allocation guarantee. However, my concern about the methodological contribution remains. The new guarantee assumes a fixed core, while the core selection still optimizes sampling error without accounting for geometry uncertainty in the final width, and the allocation scheme is closely related to the classical Neyman allocation. I remain unconvinced of the methodological advance, so I would prefer to retain my original rating.

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

The paper proposes a method for estimating a black-box model's average loss along several "directions" around a single input with confidence intervals. My best reading is that each direction corresponds to a tube around the input. And because the tubes overlap, one model query can be reused for several directions.

Critical strengths

None

Critical weaknesses

Overall my main concern is the paper presentation and practicality.

W1. The density of jargon prevented me from assessing the work reliably, and I expect the audience from the ML community would have the same difficulty. For example, the abstract and introduction rely heavily on unexplained terms such as "simultaneous auditor," "three-dimensional input chart," "intersection atom," "budget-feasible core," "finite-incidence bound," etc., mostly before these are introduced or defined. The diagram is also quite dense and hard for me to parse.

W2. Suppose I roughly got the main idea right, from a motivation standpoint, I could not find a concrete use case explaining why practically someone would need these particular directional averages, or what decision they would inform.

Questions for authors

None

1 comment
AuthorsOpenReview ↗

Response to Reviewer cGmV

We sincerely appreciate the reviewer's candid feedback. A central contribution is not useful if its purpose and mechanism are difficult to understand. We have therefore rewritten the abstract and introduction, defined the local chart in ordinary ML language, and replaced Figure 2. The changes are intended to make the problem and its solution clear before introducing the detailed statistics.

What would a practitioner actually use the directional averages for?

A concrete example: screening local failure directions of a credit-risk classifier. Consider a classifier and a labeled held-out applicant record. An evaluator wants to know whether small, joint changes in numerical features create directions in which the model's average loss is high. A single average over all nearby perturbations can conceal this variation. Testing each direction separately duplicates model calls when the perturbation regions overlap

The evaluator first specifies a local perturbation map (a chart): three coordinates encode joint changes in an otherwise high-dimensional input, for example using training-data PCA. Each narrow directional region (a tube) defines an explicit perturbation distribution. The target is simply average model loss under that distribution. The evaluator can ask:

Which predefined directions have average loss above a screening threshold, and which can be ruled out?

KakeyaShare returns a simultaneous interval [Lj,Uj][L_j,U_j] for every directional average μj\mu_j. For a threshold τ\tau:

If Lj≥τL_j\geq\tau, the average risk for direction jj is certified to be at least τ\tau.

If Uj<τU_j < \tau, that direction is screened out at the same confidence level

If the interval straddles τ\tau, the audit reports that the evidence is not decisive

Theorem 1 controls all of these decisions on a single simultaneous-coverage event; the threshold may be chosen after observing the intervals. It also supplies rigorous lower and upper bounds on how many directions exceed τ\tau. This is a decision-oriented average-risk audit, not a worst-case robustness certificate. The revised Section 2 and Appendix A.1 explicitly define what the perturbation map and anchor label mean; when label preservation is not justified, the loss 1−py1-p_y should be interpreted as sensitivity of confidence in the reference label

What exactly is the new mechanism?

The revised Figure 2 (p. 4) now makes the entire statistical idea visible:

Find shared atoms: group sampled locations by the exact set of directional regions containing them

Estimate atom means: obtain one bounded average loss from a pool of model evaluations in a shared region

Reuse across directions: multiply that mean by its direction-specific volume share and use the contribution in every direction containing the atom

The figure uses four illustrative evaluations to obtain a shared-region mean of 0.35; a volume share of 0.20 contributes 0.07 to each of three relevant directional averages. This is four calls to estimate that one shared mean rather than three independent four-call pools; it illustrates the reuse mechanism, not the overall audit savings. The algorithm also reserves budget for non-shared residual regions and independently calibrates the volume shares, preserving each directional target and the finite-sample guarantee

What is the substantive contribution beyond a picture of overlap?

The central advance is converting geometric overlap into statistically valid, reusable bounded observations. Conventional pooled or mixture observations retain random membership and importance weights. Exact-membership regions instead give one bounded scalar mean whose contribution to multiple directions is fixed by calibrated coefficients. This allows a joint allocation and a rigorously simultaneous confidence guarantee

The revised paper strengthens that guarantee further with two new formal results on p. 6: Proposition 1 gives an explicit sufficient condition under which the final calibrated RMS certificate beats same-confidence IMC–Hoeffding; Proposition 2 proves a 2\sqrt{2} approximation bound for allocating queries to minimize the final certified RMS radius within a fixed core. Complete proofs appear in Appendices B.8–B.9

On the main geometry, this results in approximately 33.5% fewer accepted model calls than IMC to reach the same certified RMS radius at 95% simultaneous confidence. Experiments involve 30 TabArena tasks and tabular, foundation-model, and vision predictors; synthetic functions are used separately to test coverage validity

Your presentation concern has led to concrete changes in the paper's first four pages, not merely a longer explanation in this response. We believe the revised problem statement, practical screening decision, and three-step mechanism now make both what KakeyaShare certifies and why the sharing matters accessible to an ML audience. We respectfully ask that the presentation and informativeness assessments be reconsidered on the basis of the revised manuscrip

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

The paper approaches local model risk through query grouping using geometric tubes rather than simple pooling. Their results show slight gains over an independent MC baseline, indicating query and certificate efficiency, as tube incidence supports query reuse. No competitive statistical methods for grouping queries are presented, and the tasks/models appear small without generalization to realistic settings.

Critical strengths

The paper brings together geometry and risk management.

Critical weaknesses

No competitive statistical methods for grouping queries are presented, and the tasks/models appear small without generalization to realistic settings.

Questions for authors

Why is Independent MC the most competitive baseline? Where are examples of overlap becoming useful through structured estimation in practice (beyond the synthetic losses and small setting)?

2 comments
AuthorsOpenReview ↗

Response to Reviewer ouGV (1&2)

We sincerely thank the reviewer for emphasizing competitive baselines and practical evidence. Both are central to the contribution. We believe two impressions in the review—that only independent MC is compared and that the evaluation is largely synthetic or limited to small models—can be resolved directly by the recorded experiments. We have also made this evidence much more visible in the revised paper.

  1. Independent MC is the reference, not the only statistical baseline

Table 1 compares six estimators in total, including five comparators to KakeyaShare. Four of those comparators already exploit shared or structured sampling:

Union-HT: sample from the tube union with volume correction.

DM-MIS: equal-mixture multiple importance sampling, reusing observations through balance weights.

OptDM-MIS: pilot-optimized mixture proposals; its reported adaptive radius is clearly nominal and excluded from certified query crossings.

Multiplicity-Neyman: strata based on the number of tubes covering a point, followed by variance-guided allocation.

Independent MC: a transparent no-sharing reference with direct simultaneous Hoeffding intervals and no estimated volume coefficients. Thus, our comparison already includes established statistical mechanisms for grouping and reusing queries (Section 5; Table 1; Appendix C.2). We do not assert that independent MC is universally the best numerical integrator or confidence procedure.

The conceptual distinction is precise. In mixture estimators, a shared query still carries a random membership indicator and importance weight for each direction. KakeyaShare constructs exact-membership strata instead: every sampled loss within a stratum estimates the same bounded mean, and calibrated geometric coefficients determine its contribution across directions. This change in the statistical unit enables the row-norm allocation and finite-sample simultaneous certificate.

  1. The measured improvement is substantial for the stated certification target

At the main geometry and N/D=512N/D=512, KakeyaShare's final certified RMS radius is 0.063860, compared with 0.077647 for independent MC at the same 95% simultaneous confidence: a 17.8% reduction in certificate radius. At the matched radius, the interpolated query equivalent falls from 512 to 340.5 accepted calls per direction, 33.5% fewer model evaluations (Appendix C.7). Independent reference evaluation also shows median dataset RMSE falling from 0.00619 to 0.00484, a 21.72% improvement. The matched-query saving is a main-geometry, confidence-matched result; repeated datasets support execution and estimation-error evidence, not independent repetitions of the geometry-level radius.

We also address the distinction between interval methods. The revised Appendix A.2 acknowledges that variance-adaptive empirical-Bernstein IMC can produce tighter bounds in the offline calculations (Appendix D.5). Our certified superiority claim is accordingly against the specified simultaneous Hoeffding-based comparator, not a claim that every interval method is dominated. The existing Sobol comparisons similarly separate point-estimation efficiency from finite-sample certificate efficiency.

AuthorsOpenReview ↗

Response to Reviewer ouGV (3&4)

  1. The study uses real datasets, diverse predictors, and extensive stress tests

The main experimental matrix covers 30 TabArena classification datasets, ranging from 748 to 150,000 observations and up to 1,776 numerical features. It evaluates LightGBM, logistic regression, RealMLP, and TabM, with additional execution studies on TabPFN-3, TabICLv2, CIFAR-10 ResNet20, and ViT-B/16. We report unavailable models and failed cells explicitly (Table 3; Appendix D.8).

Beyond the main matrix, the supplementary evidence includes:

8,064 paired stress-test cells across loss definitions, calibration, input scaling, missingness, label noise, shift, and OOD-like subsets (Table 4; Appendix D.7);

120 canonical tube geometries investigating how overlap changes ideal sharing opportunity and rejection cost (Figure 4; Appendix D.6); 14,000 synthetic repetitions, used for a separate, controlled validity check against analytical or high-precision references (Appendix D.1). These are real black-box predictor evaluations and heterogeneous input spaces, not a purely synthetic demonstration. The three-dimensional chart is the dimension of the local perturbation distribution, not a restriction to three input features. We also distinguish geometry-only query savings from measured wall-clock runtime; setup and rejection costs are explicitly analyzed in Appendix D.6.

  1. A concrete reason to audit overlapping regions

The revised Introduction now begins with an explicit application: screening local feature-variation directions around a labeled example to identify those with high average model loss. Theorem 1 allows the auditor to certify directions whose lower risk bound exceeds a chosen threshold, screen out those whose upper bound is below it, and bound the number of high-risk directions simultaneously. Independent per-direction auditing pays repeatedly for overlapping perturbation regions; exact-incidence sharing reuses bounded evidence without changing the target distribution.

The redrawn Figure 2 (p. 4) conveys the mechanism in three simple stages. The revised theory further establishes a sufficient condition for a narrower final certified radius and a 2\sqrt{2} approximation guarantee for fixed-core final-radius allocation (Propositions 1–2, p. 6; proofs in Appendices B.8–B.9).

The empirical comparison therefore includes multiple sharing baselines and substantial real-model evidence, and the new presentation makes the precise statistical contribution and its decision context explicit. We respectfully request a reassessment of novelty and empirical significance in view of these concrete results.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.