Temperature as a Parallelism Dial for Many-Prototype Classifiers

A prototype classifier labels an input by its distance to a set of stored "typical points" for each class, instead of passing it through a learned linear layer. Using several prototypes per class fixes the main weakness of the single-average version: one mean vector cannot describe a class made of distinct sub-types. The cost is computational. With thousands of classes and tens of prototypes each, every training step must compare each input against hundreds of thousands of prototypes. This proposal makes one observation and tests it. When prototypes are trained with a softened nearest-prototype rule whose sharpness is gradually increased (an "annealed temperature"), each input's gradient touches fewer and fewer prototypes as training proceeds. The schedule that optimizes the classifier therefore also controls how much of the work can run independently.

We propose to measure this effect, bound it, and use it. Each input should be compared only against a neighborhood of prototypes whose size follows from the current temperature, with a stated bound on the ignored probability mass. Prototypes should be split across devices along the boundaries where they rarely interact, not at random. If the coupling between prototypes really does collapse as the temperature sharpens, a classifier with $10^5$ prototypes can be trained with mostly local computation and little cross-device traffic. It should match the accuracy of the dense computation, and a coarse version of the same schedule could be reused in later work.

Core Claim

Optimizing 1-Nearest Prototype Classifiers supplies the method we build on. That paper learns 15–50 discriminative prototypes per class by gradient descent on a soft version of the nearest-neighbor rule. A sharpness parameter $\gamma$ is raised over training: low $\gamma$ lets prototypes move freely, and high $\gamma$ approaches the hard decision rule. With this setup it reached 4.58% error on USPS, matching an RBF SVM. The authors treat the whole prototype set as one centralized optimization run in full-batch passes. We claim the soft assignment carries structure that this treatment ignores. Write the assignment weight of prototype $j$ for input $x$ as $p_\gamma(j \mid x) \propto \exp(-\gamma\, d(x, p_j))$, where $d$ is squared Euclidean distance and $p_j$ the prototype vector. Prototype $j$'s gradient from $x$ is proportional to this weight. Suppose we keep only a neighborhood $N(x)$ and $\Delta(x)$ is the gap between the nearest prototype's distance and the closest excluded one. The discarded mass is then bounded by

$$\varepsilon(x) \le (K - |N(x)|)\, e^{-\gamma \Delta(x)},$$

where $K$ is the total prototype count. The bound follows from bounding each excluded term's ratio to the top term. It gives a rule for choosing the neighborhood size at each temperature with a known gradient error. It also predicts that the "interaction graph," with edge weight $W_{ij} = \mathbb{E}_x[p_\gamma(i\mid x)\,p_\gamma(j\mid x)]$, becomes sparse as $\gamma$ grows. Once that graph is sparse, prototypes can be partitioned across workers by a minimum-cut split, so that most gradient interactions stay within one worker.

What is new is not that distance computations can run in parallel; dense GPU matrix products already handle that. The new claims are three. Annealing produces a measurable and predictable decay in coupling. That decay supports a certified truncation rule. And partitioning along the decayed graph reduces communication relative to random sharding at equal accuracy.

Positioning Against Prior Work

Two papers motivate the problem. The open-problems analysis in the research file lists scaling prototype search to many classes as a known bottleneck. The single-centroid assumption in Prototypical Networks for Few-shot Learning, which classifies by distance to one support-set mean per class, is the limitation that many prototypes per class address. Sparse Multi-Prototype Classification recasts multi-prototype learning as a convex-concave saddle point problem, smooths it with a soft-max, and solves it with sequential primal-dual updates on small tabular data. It shows the soft-max smoothing is principled, but it never asks how coupled the resulting updates are. We take the opposite route: we keep the non-convex annealed objective and exploit its sparsity.

The compressed-search line constrains the design. PQk-means clusters a billion vectors in compressed codes on one CPU, but it is unsupervised and its sparse-vote updates fit poorly on GPUs. Anisotropic Vector Quantization shows that quantization error along the query direction harms high-scoring retrievals most. The lesson for us is that an approximate neighbor search placed into training can corrupt exactly the top-scoring prototypes that carry the gradient. This is why we want a truncation rule with an explicit error bound rather than an off-the-shelf approximate index.

The parallel-systems line has a narrower role. Use and Misuse of Java 8 Streams found that about 90% of pipelines were side-effect-free, yet only 1.25% ran in parallel, and that naive parallelization often degraded performance. We read this as a warning that exposing independence is not enough without locality-aware partitioning. BitDP identifies gradient synchronization as the limit on data-parallel scaling. Our sharding aims to reduce what must be synchronized, not to compress it, and the two approaches could be combined.

Research Program

The work has three parts.

The first part is measurement. We train annealed multi-prototype classifiers on fixed encoder features and record, across the $\gamma$ schedule, three quantities: the interaction graph, the neighborhood size the bound requires for a target $\varepsilon$, and the fraction of $W$'s mass crossing a $P$-way minimum cut. This tests the core claim directly. If the cross-cut mass does not fall by at least an order of magnitude over the schedule, the parallelism argument fails and we report that.

The second part is the training algorithm. Each input is routed to the worker that owns its nearest prototype. Distances are computed only against that worker's prototypes plus a cached set of boundary prototypes from adjacent shards. The neighborhood is grown adaptively until the bound meets the target. Boundary caches refresh only when the graph partition is recomputed, which happens once per temperature stage. The encoder is frozen first. The end-to-end variant then trains the encoder data-parallel while prototypes stay sharded.

The third part tests whether the method generalizes. We ask whether the final sharding remains valid when new classes arrive. Each new class's prototypes are attached to the shard of its nearest existing prototypes. We also ask whether a cheap probe run predicts the coupling decay.

Baselines

The naive reference point is the dense computation. Every input is compared against every prototype with a single GPU matrix product, under the same annealing schedule, prototype count, data, and step budget as our method. This is the accuracy ceiling our approximation must match. It is also the throughput and memory point we must beat once $K$ is large. Beating it means matching its test accuracy within statistical noise across seeds while using less wall-clock time, less peak memory, or less cross-device traffic at $K \ge 10^4$.

For fidelity, we reimplement the original full-batch annealed optimizer of Optimizing 1-Nearest Prototype Classifiers on USPS and LETTER. That paper reports a 4.58% USPS error with 15–50 prototypes per class. Our truncated version must land within run-to-run variation of this number, or our implementation is not faithful.

The strongest scalable competitor is top-$k$ training with a periodically rebuilt approximate neighbor index over prototypes, combined with random sharding of prototypes across devices. This is the common practice for very large softmax layers; the research file contains no paper reporting it, so we cite none. It runs with the same $k$ budget, the same refresh frequency as our partition updates, and a tuning sweep of equal size over $k$ and refresh interval. Beating it means equal accuracy with lower cross-device traffic or, at equal traffic, higher accuracy. The gain must hold at the largest $K$, not only at small scale.

Two ablations isolate the ingredients. Fixed-$k$ truncation against bound-driven adaptive $k$ isolates the certified truncation rule. Random partitioning against minimum-cut partitioning at identical neighborhood rules isolates the locality partitioning.

Finally, single-prototype references fix the accuracy context. These are Prototypical Networks, nearest-centroid on whole-classification features as in Meta-Baseline, which reports 63.17% 5-way 1-shot on miniImageNet, and Hyperspherical Prototype Networks, which reports 63.0% on CIFAR-100 with 25 dimensions.

Why not just…?

Why not just use dense matrix products on GPUs, which are already parallel? At moderate $K$ this is the right answer, and we expect the dense computation to win below roughly $10^4$ prototypes. The case for our method rests on larger regimes. The full input-by-prototype matrix dominates memory there, and splitting prototypes across devices forces communication of all logits for every input. The scaling experiments sweep $K$ from $10^3$ to $10^5$ to locate the crossover. If no crossover appears, the computational claim fails and only the coupling analysis survives.

Why not just retrieve candidate prototypes with an approximate nearest-neighbor index? This is the most serious threat, since it achieves sparsity without our theory. Two pieces of evidence count against it. Anisotropic Vector Quantization shows standard approximate search distorts the highest-scoring items, which carry the gradient. And Meta-Baseline reports degradation when the evaluation metric departs from the training metric. Neither result is decisive for training, though. The fixed-$k$ index baseline with equal tuning settles the question. If it matches us on both accuracy and traffic, our contribution reduces to the measured coupling decay and the error bound, and we will say so.

Why not shard prototypes at random, as large-softmax systems do? Random sharding spreads each input's nearby prototypes across devices, so every step communicates. Our prediction is that minimum-cut sharding keeps most interaction mass local once $\gamma$ is moderate. The partition ablation measures cross-shard mass and traffic directly. Random sharding wins if the interaction graph fails to become sparse.

Why not just use one prototype per class and skip the scaling problem? If extra prototypes do not improve accuracy on deep features, the whole effort is unmotivated. Wohlhart et al. show gains on raw pixels, and Sparse Multi-Prototype Classification reports 95% on bankruptcy against baselines of 81–90%, but both results come from shallow inputs. We therefore run the accuracy-versus-prototypes-per-class curve first. If it is flat on pretrained features, we narrow the project to raw-feature and fine-grained settings where the curve rises.

Proposed Experiments

The fidelity stage uses USPS and LETTER, where we compare against the reported 4.58% USPS error. The deep-feature stage uses CIFAR-100, the 64 miniImageNet base classes with features from a whole-classification encoder, and ImageNet-scale features as in ILSVRC_1000C, with 1 to 100 prototypes per class. The largest ImageNet setting reaches $10^5$ prototypes. For multi-prototype classifiers on ILSVRC_1000C, no reported result was found on Lacuna, so the dense computation serves as the reference.

As a stress test of prototype count rather than of semantic accuracy, we build a labeled problem from a Deep1B subset. The labels are PQk-means cluster assignments, which gives $10^5$ classes, and the task is to learn several prototypes per class. This stress test is clearly synthetic and is reported separately.

The metrics are top-1 accuracy, wall-clock per epoch, peak memory, cross-device bytes per step, the measured truncation error against the bound, and cross-cut interaction mass as a function of $\gamma$. The decisive check is a single plot of cross-cut mass against temperature, overlaid with the accuracy gap to the dense computation. The claim holds if mass falls steeply while the gap stays near zero, and if at $K = 10^5$ our method beats the approximate-index baseline on traffic at equal accuracy. A flat mass curve or a tied baseline refutes it. A secondary check adds new classes to a trained, sharded model. Rerouting should keep accuracy within noise of retraining the partition from scratch.