Buying High-Resolution Looks at Brain Scans: Stochastic Programming for Lesion Search Under a Budget

Many segmentation systems for medical scans run in two steps. A cheap, coarse network first decides where to look, and an expensive, fine network then segments only those regions. This works well when the target is one large organ. It fails in a specific way when the target is dozens of scattered lesions a few voxels across, such as embolic stroke foci or white-matter hyperintensities (small bright spots on brain MRI linked to small-vessel disease). Once the first step decides not to look somewhere, a lesion there is lost for good. Every voxel-level loss also treats that tiny lesion as nearly worthless, because it covers almost none of the scan's volume. We propose to treat "where to look" as a two-stage stochastic program, a standard operations-research model in which a decision is committed now and a corrective ("recourse") decision is taken after the uncertainty resolves. The first stage picks which high-resolution patches to buy. The coarse network supplies not one probability map but a set of plausible lesion layouts, called scenarios. The second stage may buy extra patches after seeing what the fine network found. The cost counts missed lesions per lesion, not per voxel.

The claim is narrow and testable. At a fixed budget of fine-network compute, choosing patches by solving this program should find more small lesions than ranking patches by their average lesion probability. The advantage should be largest for the worst-served patients, whom we target with a risk measure (Conditional Value-at-Risk, CVaR: the average cost over the worst α-fraction of outcomes). Two features of the program produce the gain. Scenarios capture lesions that appear together, as embolic showers do. Recourse lets the system follow up near what it has already found. If a well-tuned greedy ranking matches the program, the formalism adds nothing, and the experiments are designed to show that outcome cleanly if it is true.

What exists and what is missing

The two-stage segmentation cascade is established. Automatic Liver and Lesion Segmentation in CT Using Cascaded Fully Convolutional Neural Networks and 3D Conditional Random Fields crops the liver with one network and segments lesions inside the crop with a second, raising liver Dice on 3DIRCADb from 72.9% (single U-Net) to 94.3%. This paper motivates our work: it shows that splitting the search pays off. It also exposes the gap, because the crop is a hard, one-shot commitment with no model of what the second stage will miss. Attention Gated Networks criticizes cascades for exactly this unrecoverable-error problem and replaces the crop with soft learned gates (pancreas Dice 0.814 to 0.840). Those gates are still deterministic activations. They carry no notion of uncertainty over where lesions are and offer no second chance.

The imbalance literature attacks the problem through the loss function. The generalized Dice loss reweights classes by inverse volume. Boundary loss for highly unbalanced segmentation adds a distance-to-contour term and reports Dice gains on ISLES (0.575 to 0.656) and WMH (0.727 to 0.748). Gradient-Aware for Class-Imbalanced Semi-supervised Medical Image Segmentation revives tail organs from 0% Dice with hard-example mining and dynamic class weights. These methods constrain our design more than they compete with it: we reuse them to train the fine network. They are all voxel-weighted, and the challenge evaluation in Standardized Assessment of Automatic Segmentation of White Matter Hyperintensities found that every method, including the top cluster, was weakest on lesion recall and F1 for small lesions. ISLES 2022 documents the same regime, with 0 to 126 disconnected lesions per patient. The failure is at the level of individual lesions, and our cost function works at that level.

The method comes from neural stochastic programming. Neur2SP trains a permutation-invariant network (DeepSets) that maps a first-stage decision and a set of scenarios to the expected recourse cost. It then embeds that network in a mixed-integer program (MIP), solving facility-location instances in under 1.66 s with gaps under 5%. A quantile neural network framework for two-stage stochastic optimization extends this to quantiles of the recourse cost, which enables CVaR objectives. Neur2RO does the analogous thing for robust optimization. All three were tested only on tabular operations-research problems. None has faced decisions that are sets of spatial patches, or scenarios that are sampled segmentation masks. We are not proposing a new surrogate. We are asking whether this machinery is the right tool for budgeted lesion search.

Core formulation

We split each scan into $P$ candidate patches, each with a fine-network cost $c_p$. A cheap stage-1 model is either a deep ensemble or a Monte Carlo dropout network: several copies, or several randomized passes, whose disagreement expresses uncertainty. It produces $S$ sampled lesion masks. Connected components turn each sample $\omega_s$ into a list of lesion instances. The first-stage choice is $x \in \{0,1\}^P$, the patches bought up front. The recourse choice $y$ is the extra patches bought after the fine network's output on $x$ is seen. The problem is

$$\min_{x}\; \lambda\, c^\top x + \mathrm{CVaR}_\alpha\big[Q(x,\omega)\big], \qquad Q(x,\omega) = \min_{y}\; \mu\, c^\top y + \sum_{\ell \in \omega} w_\ell \,\mathbb{1}[\ell \not\subseteq x \cup y],$$

where $\lambda$ and $\mu$ price up-front and follow-up compute ($\mu > \lambda$ reflects latency), $w_\ell$ is the penalty for missing lesion $\ell$, and $\alpha$ sets how much weight goes to bad cases. Setting $w_\ell = 1$ for every lesion is the direct answer to spatial imbalance: a three-voxel embolus costs as much to miss as a large infarct. We will also test $w_\ell$ that decreases mildly with size.

Textbook two-stage programs assume the recourse step sees the full scenario. Here it sees only the fine network's output inside $x$. We handle this in the usual lookahead way. We solve for $x$ with the two-stage model. At run time we reweight the scenarios by their agreement with the observed fine-network detections and re-solve the small recourse problem for $y$. This is an approximation, and we name it as one.

Research Program

The work has four parts. First, we build scenario generation and check its calibration. A scenario set is useful only if real lesions fall inside it at the claimed rate, so we measure the fraction of ground-truth lesions covered by at least one scenario as a function of $S$. Second, we solve the program two ways: exactly, by writing out every scenario and its recourse variables in one MIP (sample average approximation, SAA, in extensive form), and with a Neur2SP-style set-based surrogate embedded in the MIP. This tells us whether the surrogate is needed at realistic sizes, roughly $P$ in the low hundreds and $S$ around 50, or whether exact SAA already runs in seconds. We will report whichever is true. Third, we swap the expected-cost objective for CVaR using the incremental quantile network. Fourth, we analyze when recourse and scenario correlation matter by stratifying patients by lesion count and by how clustered their lesions are. Throughout, the fine network is fixed and shared by every method. It is trained with the generalized Dice loss plus boundary loss on uniformly sampled patches, so that differences come only from where it is pointed.

Baselines

The naive reference is full sliding-window inference with the fine network over the whole scan. It is the recall ceiling at 100% budget and marks the point where any budgeted method must converge. The standard cascade is the approach of the cascaded FCN work: threshold the stage-1 probability map, dilate by a margin, and process the result. We tune the threshold and the margin jointly on validation data at each budget, so the cascade gets the same tuning effort as our method.

The strongest competitor is greedy marginal top-k. It ranks patches by the expected number of lesions they contain, averaged over the same $S$ scenarios, and buys the top patches until the budget runs out. It also gets a greedy second round that ranks the remaining patches after reweighting on the fine network's output. This baseline uses the same stage-1 model, the same scenarios, the same budget and the same second round. The only thing it lacks is joint optimization over correlated scenarios and a risk measure. It is therefore also the ablation that isolates our key ingredient.

Two further ablations remove recourse (the whole budget spent up front) and replace CVaR with expectation. The end-to-end reference is an attention-gated U-Net and a boundary-loss U-Net run on the full volume. For boundary loss, Kervadec et al. report Dice 0.656 on ISLES and 0.748 on WMH with GDL plus boundary loss. The file has no reported lesion-wise recall for these methods: no reported result found on Lacuna for small-lesion recall on ISLES 2022 or WMH for any listed method. We will measure it ourselves.

Beating the strongest baseline means one of two things, each holding across five seeds with paired bootstrap intervals over patients excluding zero. The first is higher lesion-wise recall for lesions under 10 voxels at budgets of 10–30% of the volume, with no loss in voxel Dice. The second is higher recall in the worst-decile patients.

Why not just…?

Why not just use a better loss, such as boundary or gradient-aware loss, on the full volume? These losses improve Dice, but the WMH challenge found small-lesion recall to be the weak point across all methods (Standardized Assessment…). Dice barely registers tiny lesions. We keep the best loss inside our fine network, so this is not an either/or. If compute is not constrained, full-volume inference with that loss is our 100%-budget ceiling. The proposal matters only where the fine model cannot afford the whole scan: native-resolution 3D, heavy test-time augmentation, or large models. We will show budget–recall curves rather than a single point.

Why not just lower the cascade threshold and widen the margin? This is a real threat, and we give it a full joint tuning sweep. Our expectation is that a single threshold must trade coverage of faint, scattered foci against spending budget on large confident regions. The program can instead spend budget where scenarios disagree. The per-budget comparison will settle it.

Why not just rank patches greedily by expected lesion count? This is the most serious alternative. Buying patches to cover lesions is a coverage problem, and greedy methods are often near-optimal for coverage. The program can win only through correlated scenarios, where lesions tend to appear together, and through risk aversion. We expect the gap to appear mainly in high-lesion-count, clustered ISLES 2022 cases and in worst-decile recall. If greedy matches the program within confidence intervals, we will report that the stochastic-programming machinery is unnecessary here and keep only the lesion-level scenario and cost modeling.

Why not just solve the exact SAA program and skip neural surrogates? At moderate $P$ and $S$ this may be fast enough, so it is a planned comparison rather than an assumption. The surrogate earns its place only if the exact solve exceeds per-scan latency limits, as it did for order fulfillment, where solve times averaged 6.063 s and reached up to 88.56 s (Deep Learning-Driven Contextual Stochastic Optimization).

Proposed Experiments

The primary benchmarks are ISLES 2022 (250 training and 150 test cases across three centers, 0 to 126 lesions per patient) and the WMH challenge (60 training and 110 test images across five scanners). Their small, scattered lesions are the case the method targets. The WMH split lets us check whether patch selection holds up when the stage-1 model faces an unseen scanner. We also run a sanity check on 3DIRCADb hepatic tumors, where the cascade baseline originated.

Metrics are lesion-wise recall and F1 stratified by lesion size, voxel Dice, 95th-percentile Hausdorff distance, worst-decile patient recall, fraction of volume processed at high resolution, and wall-clock time including the solve.

The experiments that decide the question are three. The first is the budget–recall curve against tuned greedy top-k with a second round. The second is the no-recourse and expectation-only ablations, which show which ingredient carries any gain. The third is a scenario-calibration study: we deliberately degrade the stage-1 ensemble, for example by shrinking it to two members, to test whether the program's advantage disappears as scenarios lose coverage. If it does not, the gain is coming from somewhere other than the uncertainty model.