Grow-by-Split Class Prototypes Under a Fixed Proxy Budget

Many image classifiers and retrieval models represent each class by one learned vector, a "prototype", and score an input by its similarity to that vector. When a class actually contains several distinct sub-types, such as birds photographed in flight and perched, one vector ends up averaging them and matches none well. Multi-prototype models fix this by giving each class several vectors. In practice they create two new problems. The vectors are randomly initialized, so they tend either to collapse onto one another or to sit in empty regions of feature space and never win an assignment. And every input must be compared against all classes times all prototypes, so the cost grows linearly with the total size of the prototype bank.

We propose to treat these as a single allocation problem. Every class starts with one prototype. During training, the model repeatedly takes the prototype whose assigned embeddings are most spread out and splits it in two along the direction that best separates that spread. The total number of prototypes is capped in advance, which caps compute. Because each new prototype is born from a real split of real data, both children start with assigned points: neither is dead, and they are not duplicates. The budget flows to classes with genuine sub-modes and away from tight classes. The splitting step is borrowed from fast unsupervised clustering. The new part is running it inside supervised training, on embeddings that keep moving, under a hard prototype budget.

Core Claim

Our central claim is about compute. At equal cost, measured as the total number of prototypes each input is scored against, a prototype bank grown by divisive splitting during training should beat the same budget spread uniformly across classes. It should also beat a large bank that is pruned down. On top of that, it should vary much less across random seeds. Prior work supplies the pieces but never this combination.

SoftTriple Loss keeps $K$ randomly initialized centers per class, scores with a smoothed maximum, and prunes redundant centers with a group-sparsity penalty. It works top-down: it pays for the full bank throughout training, and its starting points are unconstrained. The Multi-Proxy Wasserstein Classifier fixes $M=4$ proxies for every class and matches them to the feature map with optimal transport. Its authors flag two costs: proxy collapse, and a 17.7% wall-clock training overhead. ASGNet varies prototype count per support image in few-shot segmentation, but it re-clusters at inference time and depends on initial seed placement. That seed dependence is a limitation its authors acknowledge, and it motivates this proposal.

The splitting mechanism comes from k²-means. Its Greedy Divisive Initialization recursively splits the highest-energy cluster by projecting the cluster's points onto the line between two seeds and choosing the best cut. It runs once, on fixed unsupervised vectors. We run it repeatedly, per class, on embeddings that drift under gradient descent.

Research Program

The model is a backbone plus a bank of prototypes $\{p_{c,j}\}$. A sample is scored against each class $c$ by a smoothed maximum over that class's prototypes, as in SoftTriple, and trained with cross-entropy over classes. For each class we keep a small rolling buffer of recent embeddings, a few hundred at most, refreshed every epoch. This handles drift: split decisions use the current geometry rather than a stale one.

Each prototype $p$ has an energy $E(p)=\sum_{z \in A(p)} \lVert z-p \rVert^2$, where $A(p)$ is the set of buffered embeddings of its class that it currently wins. The energy measures how much intra-class spread this prototype is absorbing. At scheduled intervals we take the prototype with the largest potential reduction in energy and split it. The projective split proposes the cut, and the two children are initialized at the means of the two halves. Splitting continues until the global budget $K_{\text{total}}$ is spent, or until no split reduces energy by more than a relative threshold $\tau$.

The cost of a split is linear in one class's buffer, not in the dataset. Training cost per sample is $O(K_{\text{total}} d)$, where $d$ is the embedding dimension. That cost is fixed by design rather than growing as $C \cdot K$ for $C$ classes with $K$ prototypes each.

Splitting can create a known risk: a child prototype drifting toward a neighboring class. A second variant addresses this by accepting a split only if it lowers the classification loss on the buffer, not just the within-class energy. Comparing the two variants tests whether purely geometric splitting harms margins between classes.

We will also measure three diagnostics:

  • Proxy utilization: the fraction of prototypes that win at least a small share of their class's training samples.
  • Effective prototype count per class: how the budget actually gets distributed.
  • Seed sensitivity: the spread of accuracy and of the learned allocation across five seeds.

Baselines

The naive reference is one prototype per class, a standard softmax classifier on the same backbone. On CUB-2011, SoftTriple reports this SoftMax baseline at 57.8% Recall@1. Any multi-prototype method must clear it by a margin that survives seed variance.

The strongest existing competitor is SoftTriple itself. It is the most direct multi-center classifier with learned cardinality, and it reports Recall@1 of 65.4% (512-dimensional) and 60.1% (64-dimensional) on CUB-2011, 78.6% (64-dimensional) on Cars196, and 78.3% (512-dimensional) on Stanford Online Products (SOP). We will rerun it with the same backbone, embedding size, augmentation, schedule, and hyperparameter search budget as our method. We will report it at its own best $K$, and also at the $K$ whose per-sample prototype count equals our $K_{\text{total}}/C$. Beating it means higher Recall@1 at equal per-sample prototype cost, or matching Recall@1 at clearly lower cost, with lower variance across seeds.

For image classification on CIFAR-100, the comparison point is the Multi-Proxy Wasserstein Classifier. It reports ResNet-110 improving from 73.25% to 75.27%. We will adopt its fixed $M=4$ setting and compare at matched total proxies.

Two ablations isolate our ingredients. The first keeps the same final per-class allocation that our method discovers, but re-initializes those prototypes randomly and trains from scratch. This separates the benefit of where the budget goes from the benefit of how prototypes are born. The second grows prototypes at uniform per-class rates instead of by energy. This separates allocation from the act of growing.

Why not just…?

Why not just run k-means on each class's features from a pretrained backbone and use those as initial prototypes? This is the most serious threat, and it may well close most of the gap. We will run it directly. Per-class k-means seeded with k-means++ on epoch-0 features gives a uniform-$K$ variant. A per-class $K$ variant chooses each class's count by within-class energy reduction under the same global budget, which is a one-shot version of our allocation. If one-shot allocation matches growth during training, our contribution reduces to an allocation rule, and we will say so. Our prediction is that it falls short, because pretrained features do not yet show the sub-modes that fine-tuning creates. The test is whether the gap grows on Cars196 and CUB-2011, where fine-tuning moves embeddings most.

Why not just use a large bank and let the group-sparsity penalty prune it, as SoftTriple does? Pruning pays the full $C \cdot K$ cost for most of training and adds a sensitive regularization weight, a limitation the research file attributes to SoftTriple. It also leaves randomly initialized centers free to start in empty regions. The matched-cost comparison above settles this. If pruned SoftTriple wins at equal per-sample cost, growth offers no advantage.

Why not just re-seed dead prototypes whenever they stop winning assignments? Resetting fixes dead prototypes but not duplicates, and it does not decide which classes deserve more capacity. We found no reported result on Lacuna for dead-prototype resetting in supervised multi-proxy classifiers. We will therefore implement it on uniform-$K$ SoftTriple as an extra baseline and compare utilization and Recall@1.

Why not just use a single prototype with a larger embedding? Increasing $d$ for a single-prototype softmax model is a cheap way to add capacity. We will match parameter count, so that any gain must come from modeling multiple modes rather than from more parameters.

Proposed Experiments

The first decisive check uses a setting with known ground-truth sub-modes. We train on CIFAR-100's 20 coarse superclasses, each of which contains five fine classes, and give the model only the coarse labels. A well-behaved method should spend roughly five prototypes per superclass. Its prototypes should recover the fine classes, measured by normalized mutual information between prototype assignment and fine label. The recovered structure should be stable across seeds. We will compare random multi-proxy initialization, k-means initialization, pruned SoftTriple, and grow-by-split. Low utilization or high seed variance in the random-initialization baselines would confirm the collapse and dead-prototype problem the file attributes to them.

The second check is the main metric-learning comparison on CUB-2011, Cars196, and SOP. We will report Recall@1 against the SoftTriple numbers above, along with per-sample prototype evaluations, wall-clock time, utilization, and seed standard deviation.

The third check tests a structural prediction. SOP has very few images per class, so the method should leave most classes with one prototype and match SoftTriple at a fraction of its prototype cost. CUB-2011 and Cars196 have pose and viewpoint variation, so the budget should concentrate there. If allocation instead stays near uniform on all three datasets, the energy criterion is not detecting intra-class structure, and the central claim fails.