To check whether a neural network is safe, it is not enough to know that some inputs give safe outputs. Engineers want a map of all the inputs that do, called the network's preimage of the safe output set. Computing this map exactly is #P-hard. A recent alternative, RF-ProVe, fits a random forest to sampled input–output pairs. It reads the tree leaves, which are axis-aligned boxes (regions defined by an independent lower and upper bound on each input coordinate), as candidate safe regions. It then certifies each box statistically by drawing extra random samples inside it (On the Probabilistic Learnability of Compact Neural Network Preimage Bounds). Every one of those extra samples lands inside a box. None is spent finding out where the box should actually end. The edges of the map come from wherever the forest happened to split, so a true safe region is often cut into many small boxes, or covered by a box that is smaller than it needs to be.
We propose to spend network queries on the edges instead. Each candidate box is treated as a small active learning problem over the class of axis-aligned rectangles. The algorithm keeps the set of all boxes still consistent with the labeled points and queries only inputs on which those boxes disagree. This is the classical disagreement-based scheme of Cohn, Atlas and Ladner (CAL). For rectangles, the disagreement test reduces to a closed-form check of cost $O(d)$ per labeled point. Rigorous statistical certification is applied only after the box edges have settled.
The setting has a second, less obvious advantage. Active learning theory gives near-optimal label complexity for rectangles only when the input distribution is a product distribution, meaning the coordinates are independent (A Compression Technique for Analyzing Disagreement-Based Active Learning). Usually that assumption is unrealistic. In verification it holds by design, because the verifier chooses the sampling distribution, and uniform sampling over the input box is a product distribution. This is one of the few practical settings where that theory applies without approximation.
Core Claim
Our claim concerns the three axis-aligned benchmarks RF-ProVe uses: VCAS, DubinsRejoin and LunarLander. On these, replacing interior-only resampling with disagreement-region queries, followed by a held-out statistical certificate, should do one of two things at the same impurity level. It should reach the same preimage coverage with fewer network evaluations and fewer boxes, or it should reach higher coverage at the same budget.
The mechanism is specific. Let $P$ be the labeled safe points and $N$ the labeled unsafe points assigned to a candidate box. Let $B_{\mathrm{in}}$ be the smallest axis-aligned box containing $P$, and let $\mathrm{hull}(\cdot)$ denote the smallest axis-aligned box containing a set. The version space is every box that contains all of $P$ and none of $N$. Its disagreement region, the set of inputs whose label the consistent boxes disagree on, is then
$$ \mathrm{DIS} = \{\, x \notin B_{\mathrm{in}} \;:\; \mathrm{hull}(B_{\mathrm{in}} \cup \{x\}) \cap N = \emptyset \,\}. $$
Testing whether a candidate input is in this region therefore costs $O(|N|\,d)$ with coordinate-wise min and max operations. The coordinate-wise structure that makes boxes cheap to intersect also makes the version space cheap to query, and this is what ties box geometry to label efficiency.
A Compression Technique for Analyzing Disagreement-Based Active Learning proves that CAL on rectangles in $k$ dimensions under product densities has label complexity whose dependence on dimension is $\Theta(k \log^2 k)$, improved from $\Theta(k^3 \log^2 k)$. It also extends the analysis to noisy settings through RobustCAL. That paper supplies our method and our expectation of scaling. It offers no algorithm for real systems and no experiments, and we supply both.
Research Program
The pipeline begins as in RF-ProVe: uniform samples over the input domain, a random forest, and candidate leaf boxes predicted safe. For each candidate, we set a local window, the leaf enlarged by a fixed factor per coordinate. We seed $P$ and $N$ with the existing samples in that window.
We then run a robust variant of CAL. We draw uniform candidates from the window, discard those outside $\mathrm{DIS}$ without evaluating the network, and evaluate the network on the rest. The true preimage is generally not a single box, so a strict consistent version space would collapse. We use RobustCAL's tolerance instead. A box remains in the version space if it contains at most a fraction $1-R$ of the unsafe points it would cover, where $R$ is the same target purity RF-ProVe certifies. Membership in $\mathrm{DIS}$ is then computed with a small per-face sorted index of unsafe points.
When the disagreement region's estimated volume falls below a threshold, we fix the box. It is the largest consistent box found by greedy face-by-face expansion. Overlapping fixed boxes are merged as in RF-ProVe.
Only after this step do we certify. We draw a fresh independent and identically distributed (i.i.d.) sample inside each final box, sized by Wilks' tolerance-limit argument exactly as in On the Probabilistic Learnability of Compact Neural Network Preimage Bounds. Using a fresh sample keeps the guarantee valid even though the box was chosen adaptively.
The analysis has two parts. The first measures empirically how network queries scale with input dimension and compares the curve against the $k \log^2 k$ form. The second measures what we call the axis-alignment tax. When the true safe region has an oblique edge, the box version space must approximate it with a staircase of boxes. CAL should then concentrate its queries in a thin layer along that staircase rather than spreading them over box interiors. That gives a predicted relationship between the angle of the edge and the extra queries needed, which we test directly.
Baselines
The naive reference point is passive uniform sampling with the same total number of network evaluations. All samples go into training the forest, followed by the same Wilks certification. This shows what the extra structure buys over simply sampling more.
The strongest existing method is RF-ProVe with its interior active resampling, run with the authors' settings ($R = 99.5\%$, confidence $99.9\%$). The file reports the following results for it:
- on DubinsRejoin, it reaches the coverage target in 66 seconds with 136 boxes;
- on VCAS, it runs 20 times faster than provable methods while keeping impurity below 0.1%;
- on LunarLander, active resampling cuts the box count from 190 to 42 and the error from above 3% to below 0.5%.
All three numbers come from On the Probabilistic Learnability of Compact Neural Network Preimage Bounds. The file gives no reported coverage-versus-network-query curve for RF-ProVe, so we will regenerate RF-ProVe on identical hardware, networks and evaluation budgets. Beating it means either fewer boxes and fewer network evaluations at equal certified impurity and coverage, or higher coverage at equal budget. In both cases certified impurity must stay below the stated targets. Merely matching 136 boxes on DubinsRejoin with fewer queries would count.
The exact solver PREMAP serves as the provable upper reference. It is reported to fail to reach coverage on DubinsRejoin or to produce more than 1,000 fragmented polytopes. It indicates the scale problem but is not a fair competitor on time.
Two ablations isolate the key ingredient. The first replaces the disagreement-region filter with uncertainty sampling on the forest's vote margin, which queries where the trees split their vote. This tests whether the version space adds anything beyond ordinary model uncertainty. The second couples vote-margin uncertainty with a furthest-from-centroid diversity rule in the style of O-MedAL: Online active deep learning for medical image analysis. That paper pairs predictive entropy with this rule to avoid redundant queries clustered in one area. All methods share the same initial sample, forest hyperparameters, certification step and query budget, and each acquisition rule gets the same small tuning sweep over its single threshold.
Why not just…?
Why not just give RF-ProVe more random samples? That is the uniform-sampling baseline. The LunarLander ablation in On the Probabilistic Learnability of Compact Neural Network Preimage Bounds already shows that where samples go matters more than how many there are: targeted resampling, not more data, cut 190 boxes to 42. Uniform samples land mostly in box interiors whose label is already settled. Our query-count curves at equal budgets will show whether disagreement queries widen that gap.
Why not just query where the forest's trees disagree? This is the real threat, since tree vote disagreement is a cheap stand-in for version-space disagreement. It has two weaknesses. The trees can agree confidently, and wrongly, in regions where no point has ever been labeled. Pure uncertainty sampling is also known to keep querying near-identical points along one narrow stretch of the decision edge, as noted in the O-MedAL line of work. If the vote-margin ablation matches our method, the honest conclusion is that the forest already approximates the version space well enough. We would report that, and the contribution would shrink to the certification ordering.
Why not drop axis alignment and fit oblique or general polytope regions? For tilted edges this could win on box count. However, exact general-polytope preimages are #P-hard, and PREMAP fragments into more than 1,000 polytopes on DubinsRejoin. Rectangles also keep containment and intersection checks at $O(d)$, as box methods such as Dual Box Embeddings for the Description Logic EL++ rely on. The synthetic rotation experiment below is designed to find the edge angle beyond which an oblique-tree variant beats active rectangles. We will report that crossover rather than assume it does not exist.
Proposed Experiments
The main experiment uses the VCAS, DubinsRejoin and LunarLander networks from RF-ProVe. It plots certified coverage against the number of network evaluations for all methods, at the paper's impurity and confidence settings. We report box count, wall-clock time, and impurity measured independently on a large held-out sample. Each configuration runs over ten seeds.
A controlled synthetic study plants a known safe region in $d$ dimensions, with $d$ ranging from 2 to 20. The region is either an axis-aligned box or the same box rotated by angle $\theta$. On aligned regions, query counts should grow roughly as $d \log^2 d$, following the CAL bound for rectangles under product densities. On rotated regions, the extra queries should concentrate in a thin layer along the boundary, and the box count should grow with $\theta$. That growth would put a number on the axis-alignment tax.
Three results would be decisive against the idea. The first is if the vote-margin ablation matches our method at every budget on the real benchmarks. The second is if fresh-sample certification rejects our expanded boxes noticeably more often than RF-ProVe's, which would mean face expansion is overreaching. The third is if aligned synthetic regions show query growth clearly faster than near-linear in $d$, which would mean the robust version space has lost the structure that the theory exploits.