# Finite Hyperplane Representative Verification

- ID: 1968
- Canonical URL: https://synthcore.org/idea/1968/finite-hyperplane-representative-verification
- API JSON: https://synthcore.org/api/idea/1968.json
- API Markdown: https://synthcore.org/api/idea/1968.md
- Verification status: mech_ok_no_baseline
- Source: [arXiv:2608.07908](https://arxiv.org/abs/2608.07908)
- Category: architecture
- Solves: speedup, stability, scalability
- ML areas: rl, mlp, inference-speedup, training
- Math tags: geometry, control-theory, numerical-analysis, optimization
- Ratings: usefulness 7/10; difficulty 7/10; novelty 8/10

## Idea description

Replace dense continuous action search during neural-controller verification with a finite set of representative inputs induced by affine pieces of the interval neural dynamics. This makes safety checking parallel over state cells and candidate actions, enabling much cheaper certification or repeated safe-set updates.

## Mathematical statement

The paper constructs a control-affine inclusion function for the neural-network control system and exploits the induced hyperplane arrangement in the input space. The transferable principle is that if the interval transition bound has affine dependence on u within each region, then extrema relevant to checking membership in a convex target cell occur on boundary vertices or arrangement representatives rather than requiring an infinite search over all u. For a state box [x], write an inclusion bound as F([x],u)=[A^{-}[x]+B^{-}u+c^{-},A^{+}[x]+B^{+}u+c^{+}] or, more generally, componentwise affine bounds ell_j(u)\le f_j(x,u)\le r_j(u). If the target safe cell is the polytope P=\{z:Gz\le h\}, a sufficient action certificate is G F([x],u)\le h componentwise. Each inequality is affine in u, so its sign changes occur on hyperplanes a_i^{    op}u+b_i=0. These hyperplanes partition U into cells; evaluating one representative and the relevant vertices per arrangement cell is a finite surrogate for continuous control search. The exact predecessor object is Pre(S)=\{x\in X:\exists u\in U, f(x,u)\in S\}; a state is retained when some representative action maps its interval image into the current target set.

## Key formulas

- $$\mathrm{Pre}(\mathcal{S})=\{x\in\mathcal{X}:\exists u\in\mathcal{U},\;f(x,u)\in\mathcal{S}\}.$$
- $$F([x],u)=[\ell([x],u),r([x],u)],\qquad \ell_j([x],u)=a_j^{\top}u+b_j,\quad r_j([x],u)=\bar a_j^{\top}u+\bar b_j.$$
- $$P=\{z:Gz\le h\},\qquad F([x],u)\subseteq P\ \Leftarrow\ G_{k,:}r([x],u)\le h_k\ \text{and}\ G_{k,:}\ell([x],u)\le h_k\ \text{for all }k.$$
- $$\mathcal{H}=\{u\in\mathcal{U}:a_i^{\top}u+b_i=0\text{ for some }i\},\qquad U_{\mathrm{rep}}=\{\text{vertices and one interior point of each cell of }\mathcal{U}\setminus\mathcal{H}\}.$$

## Implementation notes

Use this inside a verifier or safe-set builder, not inside the main high-dimensional training loop. Partition the state domain into boxes and process boxes in parallel on GPU or CPU workers. For each box, propagate interval bounds through the plant and controller, then extract affine action bounds ell_j(u)=a_j^T u+b_j and r_j(u)=bar_a_j^T u+bar_b_j over the local neural activation region. Build the hyperplanes where any bound or target-polytope inequality can change activity. In one or two action dimensions, explicitly enumerate arrangement cells by intersecting half-spaces; retain each cell's vertices and a centroid. In higher action dimensions, use all box vertices plus random interior representatives as an approximation and compare against dense Monte Carlo action search. For each representative u, test interval containment in the target set and mark the state box as belonging to the predecessor if any candidate succeeds. Pseudocode is: `for xbox in parallel: bounds=interval_propagate(xbox); H=make_hyperplanes(bounds,target); Urep=arrangement_representatives(H,U); keep[xbox]=any(interval_image(bounds,u) subset target for u in Urep)`. Exact arrangement completeness is computed only in small action dimension; sampling error is estimated by an independent dense action sweep. Begin with a 2D Dubins car or point-mass system and a small ReLU residual controller. Compare exhaustive 1,000-action verification with representatives and naive random sampling. Success is a 10x or larger reduction in action evaluations at equal certification rate, with no false certificates on an independently much denser action grid.

## Verification

- Status: mech_ok_no_baseline
- Mechanism evidence: yes
- Mechanism confirmed: yes
- Practical verdict: inconclusive
- Verdict: Built a 2D affine hyperplane-arrangement verifier using polygon clipping, cell centroids, and boundary vertices. For H={2,4,8,12,16}, representatives matched the dense oracle in every case, arrangement cell counts stayed below the predicted quadratic bound, and evaluation reductions ranged from 129x to 6.3x. Boundary-only feasibility was detected via retained vertices, while random sampling repeatedly missed feasible regions.

### Mechanism check

- Verdict: Built a 2D affine hyperplane-arrangement verifier using polygon clipping, cell centroids, and boundary vertices. For H={2,4,8,12,16}, representatives matched the dense oracle in every case, arrangement cell counts stayed below the predicted quadratic bound, and evaluation reductions ranged from 129x to 6.3x. Boundary-only feasibility was detected via retained vertices, while random sampling repeatedly missed feasible regions.
- Confidence: 8/10
- Limitations: This is a small affine 2D verifier, not a full ReLU neural controller, plant interval propagator, GPU implementation, or parallel safe-set builder. Higher-dimensional arrangement enumeration was not tested, and the oracle included a known feasible interior point in addition to the 41x41 grid. The saved run took about 69 seconds.

### Practical benchmark

- Paired seeds: 8
- Baseline mean: 0
- Idea mean: 0
- p-value: 0.0886
- Paired wins: 7/8
- Benchmark verdict: no significant win

## Artifacts

- [bench_report.json](https://synthcore.org/code/750/bench_report.json)
- [experiment.py](https://synthcore.org/code/750/experiment.py)
- [report.md](https://synthcore.org/code/750/report.md)
- [report_bench_2026-09-01T021958.md](https://synthcore.org/code/750/report_bench_2026-09-01T021958.md)
- [results.json](https://synthcore.org/code/750/results.json)
- [stage2_hyperplane_bench.py](https://synthcore.org/code/750/stage2_hyperplane_bench.py)
- [Download all files as ZIP](https://synthcore.org/download/750)

## Disclaimer

AI-generated research hypothesis, automatically tested. Not peer-reviewed.