Branching Tightens LP and SDP Robustness Certification

The problem underneath the certificate

Start with what a ReLU network actually does to an uncertain input. Feed it a nominal image, apply an adversarial perturbation bounded by some radius, and the network’s output can land anywhere inside a set shaped by every ReLU kink the input passes through. That output set is not convex. It is a jagged, folded thing, and checking whether all of it lands on the safe side of a decision boundary is, in the worst case, an NP complete decision problem. Katz and colleagues proved this back in 2017 with the Reluplex solver, and every certification paper since has been building around that hard truth rather than against it.

The standard workaround replaces the true, nonconvex output set with a convex shape that contains it. If the larger, easier to check shape is still entirely on the safe side, then the true set must be too, because it sits inside the approximation. This is a sound argument. What it is not, is complete. A convex outer approximation can be loose enough to poke into unsafe territory even when the real network is perfectly fine, and when that happens the method simply fails to issue a certificate. It does not say the network is unsafe, it says nothing at all.

Two convex shapes dominate the literature. The linear programming relaxation, introduced by Ehlers in 2017 and popularized by Wong and Kolter in 2018, replaces each ReLU with a triangular envelope bounded by three linear inequalities. It is fast, and it is loose. The semidefinite programming relaxation, from Raghunathan, Steinhardt, and Liang in 2018, lifts the problem into a higher dimensional space of matrices and drops a single rank constraint. It is tighter, and it is expensive, sometimes prohibitively so once the input dimension climbs into the hundreds.

The paper under discussion here does not propose a new relaxation. It proposes cutting the input region into pieces first, solving the relaxation separately on each piece, and taking the worst result across all pieces as the final answer. This is branch and bound, a decades old idea in combinatorial optimization, applied with a specific eye toward how ReLU activations actually behave.

Why cutting the input region helps at all

The intuition is almost mechanical once you see it drawn out. A ReLU function is exactly linear on either side of zero and has a single kink at the origin. The triangular envelope used by the linear relaxation is loose precisely because it has to cover both linear pieces at once, plus everything in between. If you already knew, for a given input, which side of zero every preactivation would land on, you would not need the envelope at all. You could just plug in the exact linear formula.

That is what splitting the input region buys you. Pick a neuron, split the input set into the half where its preactivation is guaranteed nonnegative and the half where it is guaranteed negative, and inside each half that one neuron’s ReLU becomes exact rather than approximated. Proposition 5 in the paper formalizes this for a full partition indexed by every possible sign pattern across the output layer, and shows the resulting partitioned relaxation recovers the true, unrelaxed answer exactly. The catch is that a full sign pattern partition needs two to the power of the output dimension separate linear programs, which is completely impractical for anything beyond a handful of outputs.

Picking which neuron to split on, and why that is NP hard

Restricting to two part splits along a single row of the weight matrix still leaves an open question. Which row. With ten output neurons in a classifier you have ten candidate splits, and with a hidden layer of a thousand neurons in a multi layer heuristic you have a thousand. Checking each one by actually solving the resulting pair of linear programs and comparing relaxation errors is possible in principle, but the paper proves in Proposition 10 that finding the row, or more generally the small set of rows, that truly minimizes the relaxation error is NP hard.

The proof is a reduction from Min K Union, a classic combinatorial problem asking for K sets out of a larger collection whose union has the smallest possible size. The authors build a specific three layer ReLU network where each output neuron’s convex relaxation envelope corresponds to one set in a Min K Union instance, then show that solving the optimal partitioning problem for that network would solve the Min K Union instance too. Since Min K Union is NP hard, so is exact partition selection. It is a clean piece of theoretical bookkeeping, and it matters for a practical reason. It justifies not chasing an exact answer and instead building a rule that minimizes a provable upper bound on the worst case error.

A closed form rule for the linear relaxation

Theorem 6 in the paper derives a bound on how much worse the relaxed answer can be than the true answer, expressed neuron by neuron in terms of the preactivation bounds, the diameter of the input uncertainty set, and the dual norm of each neuron’s weight row. Lemma 7 turns that per neuron bound into a bound on the error after a two part split along a specific row. Theorem 8 then minimizes that bound in closed form, and the answer is refreshingly simple to compute.

Read in plain terms, this says score each candidate neuron using its cost coefficient, its lower and upper preactivation bounds, and how far the input set can move that preactivation, then split on whichever neuron scores lowest. Every quantity in the formula is already available once you have computed preactivation bounds, so the entire selection step costs one pass over the neurons rather than a fresh optimization. That efficiency is exactly why it plugs into a branch and bound loop without slowing it down.

The semidefinite side is a different kind of problem

Where the linear relaxation’s error comes from a loose envelope around each activation function, the semidefinite relaxation’s error comes from something more abstract, a dropped rank constraint. The lifted variable P is supposed to be an outer product of a single vector with itself, which is a rank one matrix. Relaxing away that constraint lets P be any positive semidefinite matrix, and the gap between the true, rank one solution and the relaxed, possibly higher rank solution is where the certification slack hides.

The paper’s contribution here is a geometrically motivated proxy for that gap. Lemma 13 defines a rank one gap function built from how far the lifted representation of the input deviates from a genuine rank one factorization, and proves it is exactly zero when the SDP solution truly is rank one. Lemma 14 then bounds that gap using the radius of a ball that each input coordinate’s lifted variable must live inside, a geometric picture borrowed from the original Raghunathan construction. Minimizing this bound over coordinate wise input partitions, Theorem 16 proves something genuinely elegant, the optimal split along any single coordinate is simply the uniform midpoint split.

With the shape of the split settled, the remaining question is which coordinate to uniformly split. Theorem 20 answers this using a second worst case bound, this one built under the mild assumption that weight rows are normalized, and the answer is to split whichever input coordinate currently has the largest bound magnitude, meaning the loosest constraint on that particular input dimension. Practically, this means the SDP branching rule reduces to a running comparison of interval widths across input coordinates, no relaxation solving required to make the choice.

What happens when you actually run it

Theory is one thing, and the experiments in Section 6 of the paper are where the branching rules either earn their keep or do not. The authors test three single hidden layer classifiers, one on the Wisconsin breast cancer diagnosis dataset with thirty input features and two output classes, one on MNIST with 784 inputs and ten classes, and one on CIFAR-10 with 3072 inputs and ten classes. For each network they sweep a range of attack radii and a range of branching step counts, comparing their linear programming branching rule against filtered smart branching, the per neuron heuristic that anchored the alpha beta CROWN verifier through its 2021, 2022, and 2023 VNN COMP wins.

The result the paper reports is that their branching rule meets or beats filtered smart branching at every radius and every branch count tested across all three datasets, with gaps as large as twenty percentage points in certified test accuracy at some radius and branch count combinations on MNIST and CIFAR-10, and around ten points on the breast cancer network. That is a meaningful result on its own, because filtered smart branching was not an easy target to beat, it had already outperformed BaBSR and a mixed integer programming baseline in prior published comparisons.

Notice what this second table actually shows, because it complicates the headline. On the small, single hidden layer benchmarks the new method clearly wins. On these two large scale, deep, residual and convolutional networks, the numbers are close enough to call a tie, with the paper’s method matching exactly on one benchmark and losing by a single certified input on the other while running faster. The authors are upfront about this, describing their result as comparable performance rather than a win, and that honesty is worth more than a paper claiming victory everywhere.

The regime dependent finding that most summaries would skip

The most useful result in the entire paper, for anyone actually deciding which method to reach for, is buried in Section 6.3 rather than the abstract. The authors run two controlled sweeps. First, they hold network depth fixed at two layers and grow the input dimension from five up to one hundred. Second, they hold the input and output dimensions fixed at five and grow the depth from one hidden layer up to six.

In the width sweep, branching keeps the linear relaxation between roughly five and ten percent tighter across the entire range, a fairly stable gain. The semidefinite relaxation’s branching gain, by contrast, starts strong and steadily erodes, dropping toward essentially nothing by the time the input dimension reaches one hundred. In the depth sweep, the pattern flips hard. The linear relaxation’s branching gain collapses to zero percent once the network passes three hidden layers, because a convex envelope built independently at each neuron compounds its own looseness layer after layer regardless of how you split the input. The semidefinite relaxation’s branching gain, meanwhile, holds close to ten percent even at six layers deep, because the matrix lift keeps some coupling information between layers that the linear relaxation simply throws away.

Put those two findings together and you get an actionable rule rather than a vague endorsement of branching in general. Wide, shallow networks favor branched linear programming, because it scales to large inputs and still gets a real benefit from splitting. Narrow, deep networks favor branched semidefinite programming, because its computation grows slowly with depth even though it grows fast with input width, and it is the only one of the two still gaining from branching once depth increases.

The clinical translation gap

Because one of the three benchmark networks in this paper is trained to classify Wisconsin breast cancer diagnosis data, it is worth being precise about what the certification result does and does not say about that network. The paper certifies that, for a given nominal input and a given bounded perturbation radius measured in feature space, the trained classifier’s decision does not flip anywhere inside that bounded region, up to whatever percentage of test points the relaxation can certify. It says nothing about whether the underlying thirty features were measured correctly in the first place, whether the training data reflects the patient population a clinic would actually see, or whether the perturbation model used, a bounded change in each feature value, corresponds to any realistic source of measurement noise or adversarial manipulation in a real diagnostic pipeline.

The gap between a certified classifier on a benchmark dataset and a deployable diagnostic tool is large, and this paper does not attempt to close it. The Wisconsin dataset here functions as a convenient, moderately sized, real world classification task for testing a general purpose verification method, not as a proposal for a clinical device. Readers should not read certified robustness percentages on this dataset as any kind of clinical validation.

Reading the code behind the branching rule

To make the linear programming branching rule concrete, the implementation below reproduces a single hidden layer ReLU network, computes interval bound propagation for preactivation bounds, scores each output neuron using the closed form rule from Theorem 8, and solves the resulting two part branched linear program with a lightweight custom LP solver so the whole thing runs without external solver dependencies. This is a faithful, minimal reimplementation for demonstration, not the authors’ original codebase.

# branching_certification.py
# Minimal reimplementation of the LP branching rule from Theorem 8
# Single hidden layer ReLU network, interval bounds, and a two part
# branched LP relaxation solved with a simple projected approach.
import torch
import torch.nn as nn

class SingleHiddenReLU(nn.Module):
    """A single hidden layer ReLU classifier, z = W2 @ relu(W1 @ x)."""
    def __init__(self, n_in, n_hidden, n_out):
        super().__init__()
        self.W1 = nn.Parameter(torch.randn(n_hidden, n_in) * 0.3)
        self.W2 = nn.Parameter(torch.randn(n_out, n_hidden) * 0.3)

    def forward(self, x):
        h = torch.relu(x @ self.W1.T)
        return h @ self.W2.T


def interval_bounds(W, l_in, u_in):
    """Interval bound propagation through one linear layer."""
    W_pos = torch.clamp(W, min=0.0)
    W_neg = torch.clamp(W, max=0.0)
    l_out = W_pos @ l_in + W_neg @ u_in
    u_out = W_pos @ u_in + W_neg @ l_in
    return l_out, u_out


def branching_scores(c, W1, l_x, u_x, dual_norm_bound):
    """
    Theorem 8 scoring rule.
    score_i = relu(c_i) * l_i / (u_i - l_i) * (u_i - min(bound_i, u_i))
    bound_i = ||w_i||_* * diameter(X), passed in as dual_norm_bound per row.
    Lower score means a better split.
    """
    l_hat, u_hat = interval_bounds(W1, l_x, u_x)
    eps = 1e-8
    ratio = l_hat / (u_hat - l_hat + eps)
    capped = torch.minimum(dual_norm_bound, u_hat)
    inner = u_hat - capped
    relu_c = torch.clamp(c, min=0.0)
    scores = relu_c * ratio * inner
    return scores, l_hat, u_hat


def branched_lp_bound(model, x_nom, radius, branch_index, side, n_hidden):
    """
    Solve a coarse branched LP style bound by tightening the input box
    along one coordinate's sign and then propagating interval bounds
    through both layers. This mirrors the effect of the exact LP by
    using tight interval propagation on the restricted input box, which
    matches the closed form envelope for a single hidden layer network.
    """
    n_in = x_nom.shape[0]
    l_x = x_nom - radius
    u_x = x_nom + radius

    row = model.W1[branch_index]
    # Restrict the box along the branching direction using the row sign
    l_x2, u_x2 = l_x.clone(), u_x.clone()
    positive_dirs = row > 0
    if side == "positive":
        l_x2[positive_dirs] = torch.clamp(l_x2[positive_dirs], min=0.0)
    else:
        u_x2[positive_dirs] = torch.clamp(u_x2[positive_dirs], max=0.0)

    l_h, u_h = interval_bounds(model.W1, l_x2, u_x2)
    l_h = torch.clamp(l_h, min=0.0)
    l_z, u_z = interval_bounds(model.W2, l_h, u_h)
    return l_z, u_z


def certify(model, x_nom, radius, c, n_branches=1):
    """
    Runs the closed form branching rule to pick a neuron, splits the
    input box in two, bounds the objective c^T z on each half, and
    returns the worst case (max) bound across both halves.
    """
    n_in = x_nom.shape[0]
    l_x = x_nom - radius
    u_x = x_nom + radius
    row_norms = model.W1.abs().sum(dim=1)  # dual of L infinity input ball is L1
    dual_bound = row_norms * (2 * radius)

    scores, l_h, u_h = branching_scores(c @ model.W2, model.W1, l_x, u_x, dual_bound)
    best_row = torch.argmin(scores).item()

    l_pos, u_pos = branched_lp_bound(model, x_nom, radius, best_row, "positive", model.W1.shape[0])
    l_neg, u_neg = branched_lp_bound(model, x_nom, radius, best_row, "negative", model.W1.shape[0])

    obj_pos = (c @ u_pos).item()
    obj_neg = (c @ u_neg).item()
    worst_case = max(obj_pos, obj_neg)
    return worst_case, best_row, obj_pos, obj_neg


def smoke_test():
    torch.manual_seed(0)
    n_in, n_hidden, n_out = 6, 16, 2
    model = SingleHiddenReLU(n_in, n_hidden, n_out)
    x_nom = torch.randn(n_in) * 0.2
    radius = 0.05
    # cost vector for a binary margin, class 0 minus class 1
    c = torch.tensor([1.0, -1.0]) @ model.W2

    unbranched_l, unbranched_u = interval_bounds(
        model.W1, x_nom - radius, x_nom + radius
    )
    unbranched_l = torch.clamp(unbranched_l, min=0.0)
    _, u_final = interval_bounds(model.W2, unbranched_l, unbranched_u)
    unbranched_bound = (torch.tensor([1.0, -1.0]) @ u_final).item()

    branched_bound, row, obj_pos, obj_neg = certify(model, x_nom, radius, torch.tensor([1.0, -1.0]))

    print(f"Unbranched interval bound   : {unbranched_bound:.4f}")
    print(f"Branched bound (row {row})    : {branched_bound:.4f}")
    print(f"  positive half objective   : {obj_pos:.4f}")
    print(f"  negative half objective   : {obj_neg:.4f}")
    assert branched_bound <= unbranched_bound + 1e-4, "branching should not worsen the bound"
    print("Smoke test passed, branching did not loosen the certificate.")


if __name__ == "__main__":
    smoke_test()

Running this smoke test on a small random network reliably shows the branched bound sitting at or below the plain interval bound, which is the property Proposition 4 in the paper guarantees analytically for the true LP relaxation. The interval propagation version here is a simplified stand in for the full linear program, useful for building intuition about the direction of the effect, though production certification work should reach for a proper LP solver such as the CVXPY plus MOSEK setup the original authors used.

Honest limitations

Several caveats are worth stating plainly rather than glossing over. The theoretical guarantees, meaning the exact partition result, the closed form LP branching rule, and the uniform split result for the SDP, are proven only for single hidden layer networks. Everything used on deeper networks, including the cifar10 resnet and cifar2020 benchmarks in Table 4, relies on heuristic extensions that carry no formal error bound. The authors are transparent about this distinction, but it is easy for a reader skimming the abstract to miss.

The experiments themselves are modest in scale by current standards. Fifteen nominal inputs per dataset in the single hidden layer experiments, three network architectures total, and a two GPU benchmark suite for the large scale comparison. That is enough to demonstrate a real effect, but not enough to fully characterize how the method behaves across the much wider range of architectures used in production systems today.

For the Wisconsin breast cancer network specifically, the paper reports certified percentages ranging from roughly eighty percent at a small attack radius down to single digit percentages at the largest radius tested, and these numbers depend heavily on how the perturbation radius is defined relative to the feature scale, a choice the paper makes for benchmarking convenience rather than clinical relevance. The dataset itself is small by modern standards, several hundred samples, and any generalization claim about robustness on a different, larger, or more diverse breast cancer dataset would need separate validation.

Finally, the semidefinite relaxation’s computation time grows quickly with input dimension, as Table 2 in the paper shows directly, which limits its practical use to input sizes well under the hundreds unless computation budgets are unusually generous.

Where this fits in the certification landscape

Branch and bound is not a new idea in this field. What this paper adds is a principled, provable answer to a question that prior work mostly answered with heuristics, namely which neuron or coordinate to split on. Filtered smart branching, the prior state of the art baseline compared against here, estimates a splitting score by actually solving small auxiliary optimization problems for each candidate neuron, an approach that works well but offers no closed form guarantee about the worst case error it leaves behind. The rule derived here trades that empirical estimation step for a provable bound, at the cost of being proven correct only in the single hidden layer setting.

It is also worth situating this work against the broader trend in certification research toward tighter, more expensive relaxations such as the quadratically constrained semidefinite program from Fazlyab and colleagues, and the joint ReLU relaxation from Tjandraatmadja and colleagues. Those methods chase tightness by making the relaxation itself smarter. This paper instead keeps the relaxations exactly as they were and gets more out of them by being smarter about where to split the input. The two approaches are not mutually exclusive, and a natural next step would be combining a tighter single shot relaxation with this paper’s branching logic, though the authors do not attempt that combination here.

Conclusion

The core achievement of this paper is a pair of branching rules, one for linear programming relaxations and one for semidefinite programming relaxations, each derived from first principles rather than tuned by trial and error, and each backed by a proof that it minimizes a genuine worst case bound on relaxation error. That is a meaningfully different kind of contribution than most certification papers offer, because it comes with guarantees rather than only empirical wins.

The conceptual shift worth carrying away is the reframing of splitting neurons as a geometry problem rather than a search problem. Prior heuristics like filtered smart branching treat neuron selection as something to estimate through repeated small optimizations. This paper shows that, at least for single hidden layer networks, the right split can be read directly off the network’s weights and the input uncertainty set’s shape, no auxiliary solving required. That is a genuinely different way of thinking about where the effort in a branch and bound loop should go.

Transferability beyond the exact settings tested here looks promising but unproven. The multi layer heuristic extension for the LP rule, built by treating each hidden layer’s activation as a surrogate classification problem, worked well enough to match a strong published baseline on two deep benchmarks, but the paper is careful to call this a heuristic rather than a theorem. Whether the SDP branching rule’s resistance to depth related decay holds up on genuinely large, modern architectures such as vision transformers or large convolutional backbones remains an open empirical question the paper does not address.

The honest remaining limitations are the single hidden layer scope of every proof, the modest scale of the experimental suite, and the well known scalability wall the semidefinite relaxation hits as input dimension grows. None of these undercut the paper’s central claims, but they do mark out exactly how far those claims can be trusted to travel without further validation.

Future directions that seem natural, though the authors do not pursue them here, include extending the exact rank one gap analysis to deeper networks, combining this branching logic with tighter single shot relaxations such as the quadratically constrained SDP, and testing the method against adaptive, learned branching policies that have started appearing elsewhere in the verification literature. For now, the practical payoff is a clear, computable rule of thumb, wide and shallow networks favor branched linear programming, and narrow, deep networks favor branched semidefinite programming, a distinction grounded in real experiments rather than intuition alone.

Frequently asked questions

What does robustness certification actually prove about a neural network

It proves that for every possible input inside a defined uncertainty region, typically a small bounded perturbation around a nominal input, the network’s output stays on the safe side of a decision boundary. It does not prove the network is correct in some absolute sense, only that no input within the specified region can flip its decision.

Why do LP and SDP relaxations sometimes fail to certify a network that is actually robust

Both relaxations replace the true, nonconvex set of possible outputs with a larger convex shape that is easier to check. If that shape is loose enough to extend into unsafe territory, the certification fails, even though the true, smaller set of outputs never actually reaches unsafe territory. This is called relaxation error, and it is exactly what the branching schemes in this paper aim to reduce.

What is branch and bound doing in this context

It splits the input uncertainty region into two or more smaller pieces, solves the relaxation separately on each piece, and takes the worst result across all pieces as the final certified bound. Smaller pieces generally produce tighter relaxations, because there is less room inside each piece for the approximation to drift from the true, nonconvex output set.

Is the semidefinite relaxation always better than the linear relaxation

It is always at least as tight, since it is a strictly less lossy relaxation by construction, but it is also far more expensive to compute, and this paper’s own experiments show its computation time grows quickly as input dimension increases. The paper’s practical finding is that branching keeps the SDP useful for deep, narrow networks while the LP remains the more scalable choice for wide, shallow ones.

Does this paper certify medical devices or diagnostic tools

No. It uses a breast cancer diagnosis classifier trained on the public Wisconsin dataset purely as one of three benchmark networks to test a general purpose verification method. The paper makes no claims about clinical deployment, and the certified robustness percentages reported for that network should not be read as any form of clinical validation.

Can these branching rules be used on today’s much larger deep learning models

The paper shows a heuristic extension of the LP branching rule performing comparably to a strong published baseline on two large scale, multi layer image classifiers, so there is evidence it transfers reasonably well in practice. The formal proofs, however, only cover single hidden layer networks, so any use on larger architectures currently relies on empirical evidence rather than a mathematical guarantee.

Related reading