Stain Correction as a Patch Game: Bounded Test-Time Adaptation for Whole Slides

Pathology classifiers trained on slides from a few hospitals lose much of their accuracy on slides from a new hospital, mostly because dye chemistry and scanners change how tissue looks. The most accurate fix that runs at deployment time, without labels, uses a diffusion model to re-render each image tile in the training hospital's colors. A diffusion model is a generator that produces an image by repeatedly removing noise. Running hundreds of these denoising passes on each of the hundreds of thousands of tiles in a gigapixel slide is too slow for clinical use. We propose a cheaper alternative. Each tile chooses one stain correction from a small fixed menu of physically valid corrections. Tiles want corrections that make the frozen classifier confident and that agree with their spatial neighbors, so nearby tissue stays consistently colored. The resulting tile assignments form a game with a potential function: a single global score that rises whenever any one tile improves its own choice. Because of this, stable assignments always exist. The cost is a fixed K classifier passes per tile plus a cheap search over cached embeddings.

The game-theory literature tells us both what can go wrong and how to prevent it. When neighbor agreement is measured by an arbitrary, learned similarity, finding a stable assignment is the same kind of problem as finding a local maximum of a cut in a graph. That problem is PLS-complete, meaning no known method finds the answer in polynomial time, and greedy one-tile-at-a-time improvement can take exponentially many steps. A known coordinated schedule reaches an approximately stable state in a polynomial number of moves. The note asks three questions. Does this spatially coupled, discrete form of test-time adaptation add accuracy beyond simpler per-tile or per-slide corrections? Does the worst-case hardness actually show up on real slide graphs? And can the coordinated schedule give a guaranteed compute budget and a label-free stopping rule, which current test-time adaptation methods lack?

Core Claim

Treat each tile $i$ of a target slide as a player choosing a stain correction $s_i$ from a codebook of $K$ stain matrices.

The codebook is built from source hospitals using the Beer–Lambert separation of a tile into optical density, stain matrix, and stain concentrations. We borrow this physical parameterization directly from Test-Time Stain Adaptation with Diffusion Models for Histopathology Image Classification (TT-SaD). We keep their physics and drop their diffusion prior.

The slide-level potential is

$$\Phi(s) = \sum_i u_i(s_i) + \lambda \sum_{(i,j)\in E} w_{ij}(s_i, s_j),$$

where:

  • $u_i(s_i)$ is the negative prediction entropy of the frozen classifier on tile $i$ after correction $s_i$;
  • $E$ is the set of edges joining spatially adjacent tiles on the same slide;
  • $w_{ij}$ is the similarity between the corrected embeddings of tiles $i$ and $j$;
  • $\lambda$ trades confidence against coherence.

Each tile's own payoff is the part of $\Phi$ that involves it. Any single-tile improvement therefore raises $\Phi$, so the game is a potential game.

Keeping the coupling within one slide is a deliberate design choice. MixUp-MIL found that mixing features across slides hurt accuracy because it blended inconsistent preparation styles, while mixing within one slide helped. That result motivates our assumption that stain consistency is a within-slide property. It also argues against cross-slide coupling.

The claim has three parts.

First, on accuracy. On top of the strongest training-time recipe, this coupled discrete correction beats three simpler options: independent per-tile correction, one correction per slide, and spatial smoothing of predictions without any stain change.

Second, on complexity. The general embedding-similarity coupling makes stable-state search PLS-hard. This follows by the same Local Max-Cut reduction used for Discrete Preference Games. The only exception is when $w_{ij}$ is restricted to a metric such as the Potts penalty, which charges a fixed cost whenever two neighbors choose different corrections. In that case classical graph-cut moves already apply.

Third, on compute. The phased, block-partitioned schedule of Short Sequences of Improvement Moves Lead to Approximate Equilibria in Constraint Satisfaction Games bounds the number of moves.

Research Program

Theory. We will write each round of the game as a boolean decision: each tile either switches to a candidate correction $\alpha$ or keeps its current one. Any two-variable payoff function can be written, after a constant shift, as a sum of nonnegative weighted pairwise constraints. Each round is then a $P_2$-FLIP game in the sense of Caragiannis et al. For these games, block partitioning by utility scale and freezing high-utility blocks phase by phase yields a $(3+\epsilon)$-approximate stable state in $\text{poly}(n, 1/\epsilon)$ moves, using their $k+1+\epsilon$ bound with $k=2$.

We will state one caveat explicitly. The guarantee is multiplicative on the shifted potential. Its practical meaning therefore depends on the size of the shift, and we will report that size. We will also prove the PLS-hardness of the general coupled game and identify the metric-coupling special case that is easy.

System. For each target tile, we precompute classifier embeddings under all $K$ corrections. With $K$ between 8 and 16, this costs K forward passes per tile. All game dynamics then run on cached vectors, at negligible cost relative to the network. Two outputs follow from the schedule:

  • a per-slide compute bound that is known before inference starts;
  • a stopping certificate: the run ends when no tile in the active blocks can improve by more than the threshold.

This certificate is a label-free stopping rule. Extending the WILDS Benchmark for Unsupervised Adaptation identifies the absence of such a rule as a central obstacle for unsupervised adaptation. $\lambda$ is the one remaining hyperparameter, and it is tuned only on the WILDS out-of-distribution validation hospital.

Empirical complexity study. We will measure how long uncoordinated best-response paths are on real slide graphs as $\lambda$ grows. Larger $\lambda$ increases frustration, meaning more neighboring tiles whose preferences conflict. We will also compare the potential reached by each schedule against a strong reference optimizer. This tests whether the worst-case hardness matters in practice or is only a theoretical warning.

Relation to prior game-framed adaptation. Two prior works describe domain adaptation as a game. Domain Adversarial Training: A Game Perspective treats adversarial domain training as a three-player continuous game and stabilizes it with Runge–Kutta solvers. Patch-Mix Transformer builds an adversarial cross-domain patch mixer. Both are training-time, continuous, gradient-based games over network weights. Neither analyzes how hard their equilibrium is to compute. Neither has been tested on pathology. The patch mixer also mixes across domains, which conflicts with the MixUp-MIL evidence. Our game differs on each point: it runs at test time, its players are discrete physical corrections, all coupling stays within one slide, and its move count is bounded.

The Communication Complexity of Local Search shows that decentralized local search can need exponential communication. That result constrains our design: we keep a single coordinator per slide, which costs nothing because one inference process sees the whole slide.

Baselines

Naive reference. The do-nothing point is the classifier applied without adaptation. We run both an empirical risk minimization (ERM) classifier and the same classifier trained with targeted H&E jitter. WILDS 2.0 reports 70.8% out-of-distribution accuracy for ERM on Camelyon17-WILDS. We will rerun ERM ourselves so that every method shares one protocol, backbone, and patch set.

Strongest training-time competitor. This is targeted stain augmentation from Out-of-Distribution Robustness via Targeted Augmentations. It reports 90.5% out-of-distribution average accuracy on Camelyon17-WILDS, up from 75.3%. It is the strongest competitor because it already removes much of the stain shortcut at training time and costs nothing at inference. We will reproduce it with the same backbone. Our method only counts as useful if, applied on top of that classifier, it raises out-of-distribution accuracy by more than the seed-to-seed spread over at least five seeds.

Strongest test-time competitor. This is TT-SaD. It reports 81.54% accuracy on unseen Camelyon17 hospitals. In the same paper, the unadapted baseline reaches 58.71% and RandStainNA reaches 75.23%. That baseline differs from the WILDS ERM figure, so the two protocols are not comparable. We will therefore run TT-SaD's released configuration on our split and backbone where feasible. We will report accuracy together with network passes per tile and wall-clock time per slide. Beating it means matching its accuracy within one point at a small fraction of its cost, or exceeding its accuracy at equal cost.

Unlabeled-data competitor. Noisy Student self-training reaches 86.7% on Camelyon17-WILDS in WILDS 2.0. We will include it under the same tuning budget, with $\lambda$ and its hyperparameters each given the same number of validation-hospital trials.

Ablations that isolate the coupling. Four ablations isolate what the coupling and the schedule contribute:

  • unary only: $\lambda=0$, so each tile picks its most confident correction independently;
  • global: one correction shared by the whole slide;
  • Potts coupling solved by graph-cut expansion moves;
  • uncoordinated best response versus the phased schedule, both run on the same potential.

Why not just…?

Why not just use one stain normalization per slide? If stain is roughly constant within a slide, a single correction captures almost all of the benefit, and the game is unnecessary. This is a real threat. We have no in-file evidence that within-slide stain variation matters for classification. The global ablation settles it directly. If the global ablation matches the coupled game on Camelyon17-WILDS and the multi-scanner data, we will report that per-tile coupling is unnecessary and the contribution reduces to cheap codebook test-time adaptation.

Why not just pick each tile's most confident correction independently? Minimizing entropy tile by tile is the obvious cheap rule. It can also choose a correction that makes the classifier confidently wrong, and nothing stops neighboring tiles from receiving incompatible colorings. The unary-only ablation measures this directly. The coupling earns its place only if it improves accuracy at matched cost.

Why not just smooth predictions spatially, or use a standard MRF solver instead of game dynamics? Here MRF means Markov random field, the standard pixel- or tile-labeling model with unary and pairwise terms. Smoothing predicted probabilities over the tile graph uses spatial context without touching stain at all. With Potts coupling, graph-cut expansion moves already give approximation guarantees, so the game-theoretic schedule only matters for non-metric embedding couplings. We therefore run both as baselines. If Potts with graph cuts matches the embedding coupling, the PLS analysis remains a correct theoretical observation, but the practical recommendation becomes the simpler solver.

Why not just rely on TT-SaD or HistAuGAN? TT-SaD's authors identify inference latency as its barrier. HistAuGAN is a GAN that separates tissue structure from stain color, used as a training-time augmenter. It raised hospital mixing on Camelyon17 from 0.20 to 0.85 mean local diversity, a measure of how well hospitals intermix in the learned features. It cannot react to a new hospital at deployment time. Neither concern means our method is more accurate. The compute-matched comparison against TT-SaD decides that.

Proposed Experiments

Main benchmark. We use Camelyon17-WILDS with the official hospital split. The tile graph is built from patch coordinates in the dataset metadata where they are available, and from k-nearest neighbors over embeddings within each slide otherwise. We report out-of-distribution accuracy, network passes per tile, and wall-clock time per slide.

Scanner stress test. The Multi-Scanner Canine Cutaneous Squamous Cell Carcinoma dataset supports a leave-one-scanner-out segmentation test, scored by mean intersection-over-union. Its authors report in-domain scores of 0.82–0.86 and cross-scanner drops of up to 0.38. We expect a stain codebook to fail on the Pannoramic 1000's background whitening. To probe this, we will add a background-handling transform to the menu of corrections. Either outcome bounds what discrete physical corrections can fix.

Decisive checks. Three checks decide the outcome.

The first is accuracy. The coupled game must beat the unary, global, and prediction-smoothing ablations on top of the targeted-augmentation classifier. If it does not, the core claim fails.

The second is hardness in practice. We plot uncoordinated best-response path lengths against $\lambda$ on real slides. We expect paths to be short at moderate $\lambda$, in which case the phased schedule's value is its guarantee rather than its speed. We expect paths to grow as frustration increases, and we will report whichever outcome appears.

The third is the stopping rule. The certified stopping point must reach within a stated fraction of the reference optimizer's potential while using fewer moves, with no target labels involved.