When a radiologist's time is the scarce resource, an active learning system has to decide, one query at a time, which scan or slice the expert should label next. Benchmarks on 3D medical segmentation keep reporting the same uncomfortable result. Sophisticated selection rules, such as "label whatever the model is least sure about," rarely beat picking at random. Picking slices at fixed spatial intervals often does as well as anything else. Random picking, meanwhile, occasionally produces disastrously bad models. This note proposes to explain and fix that pattern with one idea borrowed from the theory of games on graphs: the amount of memory a strategy is allowed to keep. The idea is that the useful selection rules are the ones that remember, in a small and structured way, what they have already asked for. The best-known heuristics remember nothing.
The concrete claim is this. Query selection should be judged by a window guarantee: no region of the data the model handles badly may go unqueried for more than a fixed number of steps. This replaces the usual average-Dice-at-the-end criterion. Under that criterion, a policy that keeps one small counter per data cluster should match random sampling's average accuracy and remove random sampling's catastrophic runs. Larger memories, up to policies that condition on the full query history, should add little. When several anatomical structures must be covered jointly, the counters need to be joint rather than independent. Each part of this prediction transfers a specific result from graph games, and each can be tested with a controlled sweep over memory size on public benchmarks.
Why game memory is the right lens
In the formal-verification literature, a controller plays an infinite game against an environment on a graph. The central question there is how much history the controller must store to win. Several results bear directly on annotation.
Looking at Mean-Payoff and Total-Payoff through Windows replaces long-run averages with window objectives, which require a running balance to recover within $l$ steps. It shows three things: one-dimensional fixed windows are solvable in polynomial time with only linear memory, fixed windows in $k$ dimensions are EXPTIME-complete, and the required memory jumps to exponential. We reuse this as the method. "Every under-served cluster gets a query within $l$ steps" is a window objective, and the dimension count corresponds to the number of structures that must be covered simultaneously.
Energy Parity Games shows a memory asymmetry. The controller tracking a resource needs memory of order $n\cdot d\cdot W$, while the spoiler wins with a memoryless strategy, because it only needs to find one failure point. This motivates our evaluation choice. A worst-case auditor can be positional, so the evaluation should report worst-region and worst-volume Dice and not only the mean.
Infinite Separation between General and Chromatic Memory shows that memory updated only from observed labels ("chromatic") can need infinitely more states than memory that sees the full history. Here, chromatic memory corresponds to counters updated from cluster IDs. General memory corresponds to conditioning on the actual embeddings of past queries. Whether the separation shows up in practice is a direct experiment.
The non-elementary results play a constraining role. These are results where the required memory grows as a tower of exponentials: Games with a Weak Adversary, and Partial-Observation Stochastic Games: How to Win when Belief Fails, which shows that tracking nested beliefs explodes. They show that trying to model the expert's hidden intent, or keeping unbounded belief histories, is the wrong design target. We therefore restrict attention to small, explicitly bounded memory classes. We treat the unbounded-history learned policy only as an upper reference.
The empirical motivation comes from two benchmark studies. Less Is More: A Comparison of Active Learning Strategies for 3D Medical Image Segmentation found that random slice sampling matched uncertainty and representativeness sampling, and that strided sampling often matched or beat them. COLosSAL: A Benchmark for Cold-start Active Learning for 3D Medical Image Segmentation found that random selection is strong on average but yields low-performance outliers, and that TypiClust removes them in the one-shot cold-start round. Read through the memory lens, these findings line up:
- Uncertainty sampling is positional: it depends only on the current model's state, and it can collapse onto near-duplicate slices.
- Strided sampling is a one-counter finite-memory policy over spatial position, which is exactly why it covers anatomy.
- Random sampling is memoryless and randomized, so it has good expected coverage and no worst-case guarantee.
No existing work states or tests this reading. The bridge section of the research file confirms there is no prior connection between the two literatures.
Core Claim
Let the unlabeled pool be partitioned into $K$ clusters ("colors") by a frozen self-supervised encoder. Let $e_c(t)$ be an estimated error indicator for cluster $c$ at query step $t$, such as mean predicted entropy or disagreement between model checkpoints. Call cluster $c$ open while $e_c(t)$ exceeds a threshold $\tau$. A query policy satisfies the window objective with window $l$ if every cluster that stays open is queried at least once in every $l$ consecutive steps:
$$\forall c,\ \forall t:\quad \big(e_c(s)>\tau \text{ for all } s\in[t,t+l)\big)\ \Rightarrow\ \exists s\in[t,t+l) \text{ with a query drawn from } c.$$
This can be enforced with $K$ bounded counters. Inside the window constraint, the policy picks the most uncertain item from the most overdue open cluster. We make three predictions:
- Positional rules violate the window and produce the worst-case failures.
- $K$ counters, which is linear memory, recover nearly all achievable worst-case gains.
- For multi-structure targets, coupling the counters across structures beats independent per-structure counters, mirroring the jump from one to $k$ dimensions in window games.
We will also prove the abstract versions of predictions 1 and 2 in a stylized arena. There, the adversary chooses which cluster's error grows, and the result is a short adaptation of the known window-game constructions. These proofs illustrate the mechanism and are not the main contribution.
Research Program
The program has three parts.
A small theory piece. We model querying as a game. Cluster colors label the edges. The environment raises errors in clusters the policy neglects. The policy pays one unit of budget per query, as an energy cost. We show:
- every positional policy can be forced into an unbounded window violation;
- $K$ counters suffice for the single-structure window;
- in the $k$-structure version, no product of independent counters suffices on a constructed instance.
An empirical memory sweep. We hold the segmentation network, training schedule, budget, and encoder fixed, and vary only what the query policy remembers. The settings, in increasing memory, are:
- none (random; uncertainty);
- a spatial stride counter (strided);
- $K$ chromatic counters (the proposed policy);
- $K$ counters per structure, independent versus joint;
- general memory over embeddings of all past queries, implemented as a small recurrent selection network trained on held-out tasks, as an upper reference.
The chromatic-versus-general test. We ask whether replacing cluster-ID counters with history-embedding memory ever helps. That would be the empirical face of the Kozachinskiy separation.
Baselines
The naive reference is uniform random selection at slice and volume level. Less Is More reports that random sampling converges to approximately 0.89 Dice on MSD Heart after 50 iterations, matching the active heuristics. This is the mean-performance bar any method must at least tie.
The second baseline is strided slice selection from the same paper. It is the strongest existing low-memory competitor and the closest existing analogue of our counters. It consistently beat random on MSD Hippocampus, though no numerical value is reported. With interpolation on MSD Prostate it falls from 0.88 Dice at block size 5 to 0.81 at block size 15.
The third baseline is TypiClust as evaluated in COLosSAL. It is the strongest method for avoiding outliers in the cold-start round, but no reported result was found on Lacuna for its Dice values, since COLosSAL presents them as bar charts. We extend TypiClust to later rounds in two ways, by re-clustering each round and by following it with uncertainty sampling, so it competes across the whole budget.
Uncertainty sampling, using Monte Carlo dropout entropy, serves as the positional reference.
The key ablation is stratified round-robin sampling over the same $K$ clusters with random picks inside each cluster. This is our window policy minus the error indicator and minus the within-cluster uncertainty choice. It isolates whether the gain comes from the memory structure or from the uncertainty signal.
All methods share the same 2D U-Net (or nnU-Net configuration), the same frozen encoder and $K$, identical budgets, and the same number of hyperparameter trials (the window $l$ and threshold $\tau$ count against our budget). Every method is run with at least ten seeds.
We count "beating" the baselines as follows:
- mean Dice within the seed spread of random and strided sampling at every budget;
- worst-decile run Dice and worst-structure Dice significantly above random and uncertainty sampling;
- an outlier rate at least as low as TypiClust's.
Why not just…?
Why not just sample randomly or by stride? On average these are hard to beat, and we do not expect to beat them on mean Dice. The evidence that they fall short is about the tail. COLosSAL documents random selection's low-performance outliers. Striding encodes coverage of spatial position only, not coverage of appearance clusters, and it degrades at large gaps on prostate. If the window policy does not reduce worst-decile Dice failures relative to these two baselines, the core claim is false.
Why not just use TypiClust? TypiClust is a one-shot selector with no record of what later rounds queried. COLosSAL also reports that tumors in liver and pancreas resist both uncertainty-based and diversity-based selection. Our extension of TypiClust to sequential rounds tests directly whether memory across rounds matters beyond good initial coverage. If the extended TypiClust ties the window policy everywhere, the conclusion is that one-shot diversity suffices and memory is irrelevant. We would report that outcome.
Why not just do stratified random sampling over clusters? This is the real threat, because it already carries $K$-counter memory. That is why it appears as our central ablation and not as an afterthought. If it matches the full policy, the result still supports the memory hypothesis: linear chromatic memory is what matters and the uncertainty signal adds nothing. The proposal's practical recommendation would then reduce to "stratify and round-robin," which is a useful and cheap finding.
Why not just learn a query policy with full history, for example by reinforcement learning? The non-elementary memory results suggest that rich history-conditioned strategies are hard to obtain, and medical budgets are tiny. We include such a policy only as an upper reference. If it clearly beats bounded counters, that would be evidence for the general-versus-chromatic separation in practice and would redirect the work.
Proposed Experiments
The benchmarks are the five MSD tasks used by COLosSAL (Heart, Hippocampus, Spleen, Liver and Tumor, Pancreas and Tumor), the MSD Prostate setting from Less Is More, and ACDC cardiac MRI with its three structures. For ACDC, A Semi-Supervised Framework for Cardiac MRI Segmentation via Multi-Constraint Collaborative Self-Training reports 0.730 average DSC at a 5% label ratio and 0.891 under full supervision, which anchors the range at matched budgets.
We report the following metrics across seeds:
- mean Dice versus budget;
- area under that curve;
- worst-decile run Dice;
- worst-structure Dice;
- outlier rate below a fixed Dice threshold;
- the empirical number of window violations per run.
Three checks decide the outcome:
- Violations predict failures. Across all policies, the number of window violations should predict worst-structure Dice. If it does not, the window criterion is the wrong lens.
- Gains saturate at linear memory. The memory sweep should show worst-case gains saturating at $K$ counters on single-target tasks.
- Multi-structure tasks need joint memory. On tumor-bearing and multi-structure tasks (Liver and Tumor, Pancreas and Tumor, ACDC), joint counters should beat independent ones. Single-structure tasks should show no such gap.
A negative result on the third check would still be informative. It would say that the worst-case jump from one to $k$ dimensions in window games does not appear in realistic annotation, which bounds how far this theory transfers.
References
- Looking at mean-payoff and total-payoff through windows
- Energy Parity Games
- Infinite Separation between General and Chromatic Memory
- Games with a Weak Adversary
- Partial-Observation Stochastic Games: How to Win When Belief Fails
- Less Is More: A Comparison of Active Learning Strategies for 3D Medical Image Segmentation
- COLosSAL: A Benchmark for Cold-Start Active Learning for 3D Medical Image Segmentation
- A Semi-Supervised Framework for Cardiac MRI Segmentation via Multi-Constraint Collaborative Self-Training