Pathology models that read whole-slide images, which are gigapixel scans of tissue, pay most of their cost at high magnification. Reading 20x or 40x patches multiplies the patch count by an order of magnitude or more, and every one of those patches must pass through a large image encoder. Current multi-scale systems decide where to zoom by heuristics: a low-resolution heatmap, an attention score, or a reinforcement-learning policy. None of these can say whether a skipped region could have changed the answer, and in metastasis detection the deciding evidence can be a few tens of microns of tumor. This note proposes a slide classifier that zooms in only where it must, and attaches a mathematical certificate to every skipped region. The certificate says the full-resolution model would have produced exactly the same trained weights during training and exactly the same slide prediction at test time.
The method combines two ingredients. The first is a containment-aware scoring rule. A high-magnification patch is scored as its low-magnification parent's score plus a bounded correction from the child's own embedding. Because the correction is bounded, the parent alone limits how high or low any of its children can score. The second is convex duality-gap monitoring, the classical way to certify how far an optimizer is from the optimum. Training the slide-level head as a convex problem over frozen features lets the duality gap control a "safe screening" rule in the style of GAP SAFE. Whole subtrees of children are certified irrelevant and are never extracted. The gap of the full problem, including the unextracted patches, can still be computed exactly.
Core Claim
Fix a frozen patch encoder whose embeddings are L2-normalized, so every embedding has norm at most one. For a parent patch $P$ at low magnification with embedding $h_P$, and a child $c$ inside it at high magnification with embedding $h_c$, define the instance score as
$$s_c(w) = w_P^\top h_P + w_C^\top h_c, \qquad |w_C^\top h_c| \le \|w_C\|,$$
where $w = (w_P, w_C)$ are the head's parent and child weights. We train $w$ with an L2-regularized hinge loss over instances, using the standard multiple-instance convention that every patch in a tumor-free slide is negative, with witness labels for positive slides handled by mi-SVM-style alternation. Each inner problem, with witness labels held fixed, is then strongly convex.
For any primal point $w$ with duality gap $\Delta$, strong convexity with modulus $\lambda$ places the optimum $w^*$ inside a ball of radius $r = \sqrt{2\Delta/\lambda}$ around $w$. This is the same geometric fact that GAP SAFE rules exploit in Mind the duality gap: safer rules for the Lasso. Every child of a negatively labeled parent then satisfies $y\, s_c(w^*) \ge -w_P^\top h_P - \|w_C\| - r\sqrt{2}$, where $y$ is the instance label. If this lower bound exceeds the hinge margin of 1, every child lies strictly outside the margin at the optimum. Each such child has zero dual weight, so the subtree can be dropped without extracting any of its patches.
Two consequences follow. The hinge loss on unextracted children is exactly zero, so the full-problem primal objective is known without touching them, and setting their dual variables to zero keeps the dual feasible. The duality gap of the complete multi-scale problem is therefore computable from the extracted patches alone. At inference with max pooling, the same bound lets us skip any parent whose best possible child score, $w_P^\top h_P + \|w_C\|$, cannot exceed the current slide maximum or the decision threshold. The resulting prediction equals what the model would output after reading every 20x patch.
The open empirical question is whether $\|w_C\|$ can be kept small enough for these bounds to bite while the head stays accurate. A larger penalty on $w_C$ than on $w_P$ encodes the prior "only zoom where the parent is ambiguous." The resulting trade-off between accuracy and the fraction of patches extracted is the main object of study.
Relation to Prior Work
The multi-scale pathology literature supplies the problem and also constrains the design. DAS-MIL in A Graph-Based Multi-Scale Approach With Knowledge Distillation for WSI Classification links 10x parents to nested 20x children in a two-tier graph network. PTree-Net in Diagnose Like A Pathologist builds a parent-child patch tree after a thumbnail heatmap discards regions. A Multi-scale Graph Network with Multi-head Attention uses explicit cross-scale edges. These papers motivate our use of containment rather than flat fusion, and Deep Learning for Visual Recognition of Environmental Enteropathy and Celiac Disease reports that naively combining zoom levels fails to beat single scale. That finding constrains us: our child term is a correction anchored to the parent, not an independent concatenated feature. None of these systems guarantees anything about the regions it never reads.
AdaptivePath in Agentic Visual Reasoning in Whole-Slide Pathology Images via Active Perception learns where to zoom with a reinforcement-learning navigator and leaves the decision of when evidence suffices to a language-model deliberator. We address the same "where to zoom" question deterministically, with an equivalence guarantee in place of a learned policy.
The optimization side supplies the method. GAP SAFE in Mind the duality gap: safer rules for the Lasso screens individual features of a Lasso using gap-shrinking dual balls. We transfer the idea to instances, which are dual coordinates in a hinge-loss problem. We also screen whole subtrees using a bound that needs only the parent, which is what turns screening into skipped encoder passes rather than skipped arithmetic. Primal-Dual Rates and Certificates shows that certificates can wrap generic solvers at the cost of about one extra data pass. That justifies running our inner problems with ordinary dual coordinate ascent and computing gaps periodically. The scheduling lesson from GAP SAFE, which evaluates the gap only every several passes, carries over. Inexact first-order primal-dual algorithms motivates using inner-problem gaps to decide when each alternation step has been solved accurately enough. CONESTA, in Continuation of Nesterov's Smoothing for Regression With Structured Sparsity in High-Dimensional Neuroimaging, is the closest medical-imaging precedent for gap-driven solvers, but it works on a dense 3D voxel grid with no scale hierarchy and no lazy data access.
Research Program
We will build a lazy, working-set trainer. It starts from parent embeddings only, at 5x or 10x. It repeatedly solves the restricted convex problem, computes the full-problem gap, and extracts children only for parents that the current safe radius cannot certify. Extraction stops when the full gap falls below a tolerance and no remaining uncertified parent has unextracted children. This is column generation in which the "pricing" step is the parent bound.
We extend the scheme recursively to three levels. A 40x grandchild bound adds a further $\|w_G\|$ term, where $w_G$ are the grandchild weights. We also derive the inference-time skip rule for max pooling, plus an ε-tolerant version for log-sum-exp pooling. In that version the bound caps how much skipped children can move the slide score.
The analysis has three parts. The first measures how the extraction fraction depends on the child-to-parent penalty ratio and on the encoder; we compare an ImageNet ResNet-50 against a self-supervised DINO ViT. The second measures how often the outer mi-SVM alternation changes witness labels. Each change resets which certificates are valid, and we must be honest that the guarantee is per inner problem, not global over the non-convex multiple-instance objective. The third tests whether a deep aggregator gated by the certified head keeps its accuracy.
Baselines
The naive reference point is a single-scale head and the same convex head given every 20x patch with no screening. The full-extraction convex head defines the exact predictions our screened model must reproduce. Any disagreement between the two is a bug, not a trade-off. It also gives the denominator for compute savings, measured as encoder forward passes and wall-clock time on identical hardware.
The strongest accuracy competitors are deep multi-scale aggregators run on all patches. On Camelyon16, DAS-MIL reports 94.5% accuracy and AUC 0.973, and TransMIL reports test AUC 93.09% (TransMIL). On TCGA lung subtyping, DAS-MIL reports AUC 0.965 and TransMIL 96.03%. We will rerun both on our exact splits with the same frozen encoder, the same patch grid, and an equal hyperparameter search budget, and quote the published figures only as context. Beating them outright is not the goal. Success means staying within roughly one AUC point of the stronger rerun while extracting a small fraction of the 20x patches.
The strongest efficiency competitor is heuristic pruning. We implement a PTree-Net-style thumbnail heatmap filter and an attention-score top-k filter, each tuned to the same extraction budget our method reaches. They are compared on AUC and on recall of annotated tumor regions. No reported result was found on Lacuna for PTree-Net's filter or AdaptivePath's navigator on Camelyon16, so these will be our own reimplementations.
Two ablations isolate the key ingredients. Removing the duality-gap radius, which means screening only after training to convergence, shows what the gap buys during training. Replacing the bounded child correction with an unconstrained concatenated child feature removes the parent-only bound and should collapse screening to near zero.
Why not just…?
Why not just prune with a thumbnail heatmap or attention scores? These filters can match our extraction budget cheaply, and on easy slides they may lose nothing. Their failure mode is silent loss of small foci. Detecting Cancer Metastases on Gigapixel Pathology Images shows how small and how easily missed metastatic regions are, with human exhaustive-search sensitivity of 73.2%. The decisive experiment uses Camelyon16's lesion annotations. At equal extraction budgets we count how many annotated micrometastases fall in regions each method skipped. Our method skips none that would have changed the full model's output, by construction. If the heuristic filters also miss none and match AUC, our contribution reduces to the guarantee itself, and we will say so.
Why not just run a deep aggregator such as DAS-MIL on everything? This is the real threat. A linear head over frozen features may simply be less accurate than a graph network, and compute may be cheap for well-funded labs. Our experiments report the accuracy gap directly. We also test a hybrid in which the certified head decides which children to extract and DAS-MIL runs on the retained set. That hybrid gives up exact equivalence for the deep model, but it shows whether the screening transfers. If the convex head trails by several AUC points and the hybrid degrades too, the proposal narrows to a certified triage tool rather than a classifier.
Why not just use validation early stopping instead of a duality gap? For accuracy alone, early stopping on the convex head would likely be fine. The gap is not there to choose a stopping epoch. It is what makes screening safe before convergence and what certifies the unextracted patches. The no-radius ablation measures exactly how much extraction the gap saves during training over "converge first, then screen."
Why not just bound children without any convex training? The inference-time skip rule indeed needs only the bounded scoring form. Duality matters at training time, when $w$ is still moving and children's influence on the optimum is unknown. Without a certified radius one must either extract everything or risk training on a biased subset.
Proposed Experiments
The primary benchmarks are Camelyon16 for binary metastasis detection with lesion annotations, TCGA-NSCLC for adenocarcinoma versus squamous cell carcinoma, and TCGA-RCC for the three-way renal subtyping task. All use 5x or 10x parents with 20x children, and Camelyon16 adds a three-level 40x run.
For each setting we report AUC and accuracy, the fraction of high-magnification patches extracted during training and at inference, total encoder wall-clock time, the final full-problem duality gap, and the agreement rate between screened and full-extraction predictions, which must be 100%. The trade-off curve over the child penalty ratio is the central figure.
The decisive check is whether some penalty setting on Camelyon16 extracts under about a quarter of the 20x patches while matching the full-extraction convex head exactly, staying within one AUC point of our TransMIL and DAS-MIL reruns, and missing zero annotated lesions that the heuristic filters miss at the same budget. If no such setting exists because $\|w_C\|$ must stay large for accuracy, the parent bound is too loose for real tissue, and we will report that negative result.
References
- Mind the duality gap: safer rules for the Lasso
- A Graph-Based Multi-Scale Approach With Knowledge Distillation for WSI Classification
- Diagnose Like A Pathologist: Weakly-Supervised Pathologist-Tree Network for Slide-Level Immunohistochemical Scoring
- A Multi-scale Graph Network with Multi-head Attention for Histopathology Image Diagnosisn
- Deep Learning for Visual Recognition of Environmental Enteropathy and Celiac Disease
- Agentic Visual Reasoning in Whole-Slide Pathology Images via Active Perception
- Primal-Dual Rates and Certificates
- Inexact first-order primal-dual algorithms
- Continuation of Nesterov's Smoothing for Regression With Structured Sparsity in High-Dimensional Neuroimaging
- TransMIL: Transformer based Correlated Multiple Instance Learning for Whole Slide Image Classification
- Detecting Cancer Metastases on Gigapixel Pathology Images