# Critical-Region LP Policy Layer

- ID: 2498
- Canonical URL: https://synthcore.org/idea/2498/critical-region-lp-policy-layer
- API JSON: https://synthcore.org/api/idea/2498.json
- API Markdown: https://synthcore.org/api/idea/2498.md
- Verification status: mech_ok_no_baseline
- Source: [arXiv:2608.18129](https://arxiv.org/abs/2608.18129)
- Category: architecture
- Solves: accuracy, speedup, stability
- ML areas: mlp, optimizer, training
- Math tags: optimization, linear-algebra, convex-analysis, dynamical-systems
- Ratings: usefulness 8/10; difficulty 5/10; novelty 5/10

## Idea description

Replace black-box differentiation through an embedded LP decision with an analytic Jacobian computed from the LP’s active basis. A neural policy emits LP coefficients or right-hand sides; the LP returns the decision, while the backward pass uses the basis inverse and dual sensitivity, avoiding solver unrolling and finite-difference noise.

## Mathematical statement

The paper’s LP is $a^*(s,\theta)=\arg\max_a c(s,\theta)^\top a$ subject to $Ga\le h(s,\theta)$ and $a\ge0$, with constant $G\in\mathbb{R}^{m\times n}$. Parametric-LP theory partitions $(s,\theta)$ into polyhedral critical regions $P_k$. On the interior of a region, the active basis $B_k$ is constant and the solution is $a^*(s,\theta)=B_k^{-1}h_k(s,\theta)$, where $h_k$ is the vector of right-hand sides of the active rows; the active-row dual is $\lambda_k^*=c_k^\top B_k^{-1}$. Therefore, when $G$ is constant, $\partial a^*/\partial x=B_k^{-1}\partial h_k/\partial x$ for any input $x$ entering the active right-hand side. More generally, if the active matrix depends on $x$, $\partial a^*/\partial x=B_k^{-1}(\partial h_k/\partial x-(\partial B_k/\partial x)a^*)$. The derivative is valid while the solution remains in the same critical-region interior; basis changes are the only nonsmooth events under the paper’s assumptions. For a recurrent system $s_{t+1}=\phi(s_t,a_t,\xi_t,\theta)$, define $S_t=\partial s_t/\partial\theta$ and $A_t=\partial a_t^*/\partial\theta$. Then $A_t=B_t^{-1}(h_{t,\theta}+h_{t,s}S_t)$ and $S_{t+1}=\phi_{s,t}S_t+\phi_{a,t}A_t+\phi_{\theta,t}$, with all partial derivatives evaluated along the sampled trajectory.

## Key formulas

- $$a^{*}_{i,t}=\arg\max_{a}\,c_{i}^{\top}a\quad\text{s.t.}\quad Ga\leq h_{i},\;a\geq 0,$$
- $$a^{*}(s,\theta)=B_{k}^{-1}h_{k}(s,\theta),\qquad \lambda^{*}_{k}=c_{k}^{\top}B_{k}^{-1},$$
- $$\frac{\partial a^*}{\partial x}=B_k^{-1}\frac{\partial h_k}{\partial x}\quad\text{(constant active matrix }B_k\text{)},$$
- $$A_t=B_t^{-1}(h_{t,\theta}+h_{t,s}S_t),\qquad S_{t+1}=\phi_{s,t}S_t+\phi_{a,t}A_t+\phi_{\theta,t}.$$

## Implementation notes

Integrate this as a custom differentiable optimization layer between a neural policy and the downstream loss. The policy network receives state $s_t$ and outputs LP parameters, for example $h_t=\operatorname{softplus}(g_\psi(s_t))+\epsilon$ and optionally $c_t=g^c_\psi(s_t)$. The forward pass solves the LP with a standard primal or primal-dual solver and records the active constraint indices, the basis matrix $B_t$, the primal action $a_t$, primal slacks, and dual variables. In the backward pass, first identify the $n$ active independent rows; solve linear systems with $B_t$ rather than explicitly forming $B_t^{-1}$. Compute $A_t=B_t^{-1}(h_{t,\theta}+h_{t,s}S_t)$ and propagate $S_{t+1}=\phi_sS_t+\phi_aA_t+\phi_\theta$. Backpropagate the final loss through $S_t$ into the neural parameters using ordinary autodiff. If the LP objective coefficients are learned, include the reduced-cost derivative using the recorded dual solution; if a parameter changes $G$, use the general term $-B_t^{-1}(B_{t,x}a_t)$. Mark a sample as unsafe when the smallest active slack margin, reduced-cost margin, or basis condition number is below a threshold; for unsafe samples, fall back to solver autodiff, a damped gradient, or a straight-through action while logging the event. The mathematical quantities are the basis sensitivity and recurrent chain rule; Jacobians of $\phi$ and the network are estimated by autodiff. First test a small inventory or transportation policy: a 2-layer MLP controlling a differentiable min-cost-flow LP on randomly generated demand. Compare analytic basis backpropagation against unrolled solver differentiation and finite differences at equal forward solves. Success means lower gradient variance, faster loss reduction at equal wall-clock time, and no degradation near—but not exactly on—basis boundaries.

## Verification

- Status: mech_ok_no_baseline
- Mechanism evidence: yes
- Mechanism confirmed: yes
- Practical verdict: harms
- Verdict: Built an active-basis LP sensitivity layer with a PyTorch autograd wrapper and numerical experiments. Interior analytic Jacobians matched finite differences to 1.4e-10, boundary-crossing finite differences showed a stable 0.1667 absolute error, and sensitivity norm scaled approximately as 1/epsilon with basis conditioning. The analytic method was 6.19x faster than coordinate finite differences over 80 two-variable LP samples.

### Mechanism check

- Verdict: Built an active-basis LP sensitivity layer with a PyTorch autograd wrapper and numerical experiments. Interior analytic Jacobians matched finite differences to 1.4e-10, boundary-crossing finite differences showed a stable 0.1667 absolute error, and sensitivity norm scaled approximately as 1/epsilon with basis conditioning. The analytic method was 6.19x faster than coordinate finite differences over 80 two-variable LP samples.
- Confidence: 9/10
- Limitations: The comparison uses finite differences rather than a full unrolled differentiable solver, and it is a small static two-variable LP rather than a recurrent neural policy or min-cost-flow task. The wrapper supports gradients with respect to h only; objective-coefficient, changing-matrix, unsafe-basis fallback, GPU, and learned-policy training were not tested.

### Practical benchmark

- Paired seeds: 8
- Baseline mean: 0
- Idea mean: 0
- p-value: 0.0338
- Paired wins: 1/8
- Benchmark verdict: idea worse (significant)

## Artifacts

- [bench_lp_policy.py](https://synthcore.org/code/850/bench_lp_policy.py)
- [bench_report.json](https://synthcore.org/code/850/bench_report.json)
- [critical_lp_experiment.py](https://synthcore.org/code/850/critical_lp_experiment.py)
- [report.md](https://synthcore.org/code/850/report.md)
- [report_bench_2026-09-01T122622.md](https://synthcore.org/code/850/report_bench_2026-09-01T122622.md)
- [results.json](https://synthcore.org/code/850/results.json)
- [Download all files as ZIP](https://synthcore.org/download/850)

## Disclaimer

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