Background Prototypes as Utility-Minus-Cost Selection in Few-Shot Segmentation

Few-shot segmentation asks a model to outline a new object category in a "query" image after seeing it in only one or a few labeled "support" images. Many methods quietly ignore the background, or summarize it crudely. That causes two typical errors. The model labels lookalike clutter as the object, and when the object resembles its surroundings (a red chair against a red wall), it either misses the object or swallows the wall along with it. Recent methods try to fix this by mining background examples ("prototypes", meaning representative feature vectors) directly from the unlabeled query image. They do so with fixed grids, similarity thresholds, or random token picks. None of these choices states what a good set of background examples is, and the known failures follow from that.

We propose to state the goal explicitly and then optimize it. A good set of background prototypes should cover the variety of the query's background while staying far from anything that looks like the target object. We write this as "coverage minus cost": a diminishing-returns coverage score minus a per-token penalty for resembling the support foreground. The most similar existing approaches resemble plain greedy selection on this kind of objective, and plain greedy is known to fail on it badly. It can be lured by tokens that cover a lot but cost a lot, which here means tokens that are actually object pixels. Distorted greedy with random candidate sampling is a selection algorithm built for exactly this objective. It is cheap enough to run per image at test time, it carries a guarantee with no loss on the cost term, and it decides on its own how many prototypes to keep.

Core Claim

The low-contrast failure of query-background mining is an instance of the "bad element trap" that Harshaw et al. identified for objectives of the form $g(S) - c(S)$. In that setting standard greedy can be as poor as $O(1/k)$. Their Stochastic Distorted Greedy fixes this by discounting coverage early in the selection, so early picks must be cheap, and by evaluating only a small random sample of candidates at each step. The algorithm guarantees $\mathbb{E}[g(S)-c(S)] \ge (1-e^{-\gamma}-\epsilon)\,g(OPT) - c(OPT)$, where $\gamma$ measures how close $g$ is to having strictly diminishing returns. The guarantee has no shrinking factor in front of the cost term, which is the property that matters when the cost stands for "this token is probably the object."

Concretely, let $V$ be the query feature tokens, $\mathrm{sim}_+$ the cosine similarity clipped at zero, $w_v$ the current background probability of token $v$ under the segmenter, and $\mathbf{p}_{fg}$ the support foreground prototype. We select background prototypes $S$ to maximize

$$f(S) = \underbrace{\sum_{v \in V} w_v \max_{u \in S} \mathrm{sim}_+(v,u)}_{g(S):\ \text{weighted background coverage}} \;-\; \underbrace{\lambda \sum_{u \in S} \mathrm{sim}_+(u, \mathbf{p}_{fg})}_{c(S):\ \text{foreground resemblance}}$$

Here $g$ is a monotone facility-location function, so $\gamma = 1$. The weight $\lambda$ is the only tuned parameter. We use the unconstrained variant, which stops adding prototypes once the distorted gain turns non-positive. The number of prototypes is therefore set per image, which is the choice that LPS-CE cites as the reason it avoided clustering.

The claim we will test is narrow. A soft, cost-aware, distorted selection beats both hard filtering and cost-blind coverage, and the advantage concentrates on images where foreground and background look alike.

Relation to Prior Work

The motivating evidence comes from few-shot segmentation methods that recognized background as a contrastive signal. Pyramid Graph Networks and SimPropNet argued that discarding support background removes the negative reference needed to reject lookalike regions. This idea goes back to the weakly supervised localization work that subtracts the features of a window's surroundings from the window itself (Cinbis et al.). Three methods mine background specifically, and each uses a heuristic we replace. CobNet pools query background over a fixed 4×4 grid and itself reports failure on the red-chair-red-wall case. LPS-CE thresholds cosine similarity at $\delta$ and reports strong sensitivity to that threshold. DCP splits only the support mask into foreground, boundary, background, and distractor proxies. CyCTR samples about 600 support tokens uniformly under the mask and then filters them with a cycle-consistency check that over-suppresses valid tokens. That over-suppression is a warning that hard filters on correspondence are brittle, and it is one reason our cost is soft.

The method comes from the stochastic greedy literature. We reuse Stochastic Distorted Greedy from Harshaw et al. without changing its theory. Sakaue shows that random candidate sampling extends to objectives that can decrease as items are added, at a 1/4 guarantee. We keep that algorithm as a variant to try if we later add redundancy penalties that make $g$ non-monotone. We do not expect it to matter for the core claim.

The closest use of submodular functions in few-shot vision is SMILe. It uses submodular mutual information as a continuous training loss over foreground class features in detection. It selects no tokens and models no spatial background. Our work does the opposite: discrete selection of background tokens at inference, with no change to training.

The host model is RePRI, whose code is available (mboudiaf/RePRI). RePRI fits a foreground/background linear classifier on frozen features at test time and constrains background only through a single scalar, the predicted foreground area proportion. We extend its background class to a mixture over the selected prototypes.

Research Program

We will build a training-free module that slots into RePRI's test-time loop. At a given iteration, RePRI's current predictions provide the weights $w_v$. Stochastic Distorted Greedy then selects $S$ from the query tokens, about 3,600 on a 60×60 map, with candidate sample size $s = O(\frac{n}{k\epsilon}\log\frac{1}{\epsilon})$. Each selected token becomes an extra background prototype in the classifier, the background score of a pixel becomes its maximum over these prototypes, and RePRI continues optimizing. Selection is redone once or twice as the weights sharpen. Because the module is training-free, any gain can be attributed to the selection itself rather than to retraining.

A second, conditional stage would replace CobNet's grid-pooled background module with the same selection inside a trained network. We will pursue it only if the training-free results clear the decisive check described below.

We will analyze three things. First, how the per-image prototype count varies with background complexity. Second, the variance across random seeds, which the stochastic greedy literature flags as a risk when few items are selected. We will test whether averaging predictions over a few independent draws removes this variance. Third, wall-clock time compared with exhaustive greedy.

Baselines

The naive reference is unmodified RePRI with its single background class, run with the authors' code, backbone, and test-time iteration count. The file has no RePRI 1-shot PASCAL-5i absolute number; it reports a 63.2% mIoU for RePRI in the COCO→PASCAL 1-shot cross-domain setting, and gains of about 5% at 5-shot and 6% at 10-shot over earlier methods. We will reproduce our own RePRI numbers and report against them.

The strongest existing query-background miners are CobNet, at 61.4% mIoU 1-shot on PASCAL-5i and 37.8% on COCO-20i, and LPS-CE, which reports gains of up to 5.3% (1-shot) and up to 8.5% (COCO 1-shot) when added to PFENet. We cannot fairly compare against their full trained networks, because those differ from RePRI in architecture and training. Instead we reimplement each method's mining rule inside the same RePRI loop: CobNet-style 4×4 grid pooling of predicted-background tokens, and LPS-style cosine thresholding with $\delta$ tuned on a held-out fold. Every method gets the same frozen features, the same number of test-time iterations, and the same tuning budget: a grid of eight settings for its one key parameter ($\lambda$, $\delta$, or cluster count), selected on fold 0 and applied unchanged to the other folds. We also list CyCTR's published 5-shot results (66.6% PASCAL-5i, 45.6% COCO-20i) to show where trained transformers sit. Beating them is not our goal.

The ablations isolate the key ingredient. One removes the distortion and runs plain stochastic greedy on $g - c$. One removes the cost and runs facility location only. One removes the randomness and runs exhaustive distorted greedy. One fixes $k$ instead of stopping adaptively. The proposal counts as beating the field if full selection improves mean mIoU over the best tuned mining rule by a margin larger than the spread across seeds. It must do so on all four folds, with the gain at least doubling on the low-contrast tercile described below.

Why not just…?

Why not just filter out foreground-like tokens with a threshold and run k-means++ on what remains? This is the most serious threat. k-means++ seeding is itself a randomized, greedy coverage procedure, so a filter followed by clustering could capture most of the benefit. Our argument against it is specific to the low-contrast regime. A hard filter makes the same choice LPS-CE makes, and LPS-CE's own results show that choice is fragile: a low threshold lets object pixels into the background, and a high threshold deletes the background that sits next to the object, which is exactly what is needed to separate them. A soft cost lets a token that covers a lot and resembles the object only slightly enter late, while a strongly object-like token never enters. We will run filter-plus-k-means++ with its threshold and cluster count jointly tuned under the same budget. If it matches us on the low-contrast tercile, our contribution reduces to "query background prototypes help RePRI," and we will report it that way.

Why not just sample background tokens uniformly, as CyCTR does? Uniform sampling has no notion of coverage, so small distractors such as a lookalike object in a corner are missed with high probability. CyCTR needed both many samples and a secondary filter to compensate. The comparison with uniform sampling at equal prototype count settles this directly, and the expected gap should appear on cluttered COCO-20i more than on PASCAL-5i.

Why not just run exhaustive greedy on the same objective? Two reasons, one practical and one about quality. Exhaustive greedy costs $O(nk)$ evaluations per image, while random candidate sampling reduces that to near-linear in $n$, and Sakaue reports 10–100× fewer evaluations at equal objective value. Without distortion, exhaustive greedy also falls into the bad-element trap. The exhaustive-distorted ablation separates the two effects. If it matches stochastic distorted greedy in mIoU, the randomness is purely a speed device, which is an acceptable outcome. If plain greedy on $g - c$ matches the distorted version, the theory-motivated part of the claim fails.

Decisive Experiments

We evaluate on PASCAL-5i and COCO-20i at 1-shot and 5-shot across all four folds, reporting mIoU. We also evaluate the cross-domain transfer from PASCAL to ISIC2018, Chest X-ray, Deepglobe, and FSS-1000. In those domains the foreground often resembles the background; DMTNet reports a 59.74% 1-shot average there, which we cite as a reference rather than a target.

The decisive check uses a low-contrast stratification. For each test episode we compute, from the ground truth after the fact, the similarity between the mean foreground and mean background features. We then split episodes into terciles. The hypothesis predicts that distortion and the soft cost help most in the highest-similarity tercile, and that their advantage over filter-plus-k-means++ vanishes in the lowest. A flat gain across terciles would mean the mechanism is generic background coverage, not escape from the bad-element trap.

We will also report how often each method's selected prototypes fall inside the ground-truth foreground. This is a direct measure of the trap that should track the mIoU differences. Finally, we report seed variance and wall-clock time per episode.