Breaking the Linear Memory Scaling of Large Output Spaces

45 concepts44 papers2 proposals

In standard deep learning classification, the final layer is a dense linear projection that maps a hidden feature vector $h \in \mathbb{R}^d$ to a class score vector $y \in \mathbb{R}^C$, where $C$ is the number of target categories. This architecture relies on a weight matrix $W \in \mathbb{R}^{C \times d}$ whose size scales linearly with the number of classes.

While an $O(C)$ parameter footprint is negligible when dealing with dozens or hundreds of labels, it becomes a catastrophic bottleneck in two increasingly prominent domains: Extreme Classification (XC)—where models must choose from millions of items, products, or facial identities—and Class-Incremental Learning (CIL)—where the label space expands indefinitely over time.

To scale models to millions of classes or deploy continuous learning agents on edge devices, researchers must break this linear memory wall.


The Anatomy of the Memory Wall

To understand why the final layer becomes a bottleneck, we must look beyond the raw weight matrix. In modern deep learning, the true memory footprint of a layer during training is a function of its weights, its gradients, and the internal states tracked by adaptive optimizers like Adam.

$$\text{Memory} \propto C \times d \times \text{Optimizer Factors}$$

As highlighted by Medini et al. in Extreme Classification in Log Memory using Count-Min Sketch, a classification layer mapping to 50 million products can easily demand over 100 billion parameters. Babbar demonstrates in Towards Memory-Efficient Training for Extremely Large Output Spaces that because optimizers store additional historical states (such as momentum and variance) for every single parameter, the final layer quickly exhausts available GPU VRAM long before the rest of the network does.

This issue is exacerbated when fine-tuning massive architectures. As noted by Chang et al. in Taming Pretrained Transformers for Extreme Multi-label Text Classification, coupling large transformer backbones with millions of output labels causes standard architectures to hit an immediate memory wall, resulting in out-of-memory errors on standard hardware clusters. Work by Ullah et al. in Navigating Extremes: Dynamic Sparsity in Large Output Spaces and Zhang et al. in ELMO : Efficiency via Low-precision and Peak Memory Optimization in Large Output Spaces underscores that this linear scaling restricts end-to-end training of extreme classifiers to specialized, industrial-scale infrastructure.


The Linear Scaling Dilemma in Continual Learning

In Class-Incremental Learning, the memory wall manifests not as a massive static matrix, but as an accumulating storage tax. To prevent "catastrophic forgetting" when learning new classes without access to old data, models often allocate dedicated resources per category.

The authors of ILCOC: An Incremental Learning Framework Based on Contrastive One-Class Classifiers point out that architectures assigning independent parameters or models to each individual class face a strict linear increase in storage. This growth occurs across several common incremental strategies:


Strategy 1: Partial Evaluation and Parameter Sharing

To bypass the memory wall, researchers have developed techniques that avoid instantiating or updating the full classification layer at every training step.

Partial Fully Connected Layers

During any single forward pass, a training sample belongs to only one (or a few) positive classes. The remaining millions of classes serve purely as negative examples. The authors of Killing Two Birds with One Stone: Efficient and Robust Training of Face Recognition CNNs by Partial FC leverage this insight by randomly sampling only a small fraction of negative class centers during each iteration. By computing the softmax loss over this reduced subset, they dramatically lower the memory and computational burden on the hardware while maintaining classification accuracy.

Virtual Grouping

Instead of maintaining a strict 1:1 mapping between a unique identity and a weight vector, parameters can be shared. Li et al. introduce this concept in Virtual Fully-Connected Layer, where identities are clustered into shared parameter groups. By dynamically re-grouping these identities throughout training, the framework reduces the final layer's memory footprint by over 100x, enabling large-scale face recognition on limited hardware.

Standard FC Layer:
[Input h] ---> [ Matrix W: C x d ] ---> [ C Class Scores ]  (Scales linearly with C)

Partial / Virtual FC Layer:
[Input h] ---> [ Sampled/Grouped W: (C/k) x d ] ---> [ Subsampled Scores ] (Sub-linear active memory)

Strategy 2: Structural and Mathematical Compression

An alternative approach alters the geometry or routing of the output space entirely, substituting the flat $O(C)$ matrix with sub-linear mathematical structures.

Random Projections and Sketching

Instead of optimizing a massive weight matrix directly, the high-dimensional label space can be compressed using randomized algorithms. Yuan et al. demonstrate in Accelerating Deep Learning with Millions of Classes that a model can be trained in a compressed, randomly projected space and the full classifier can be mathematically recovered afterward. Similarly, Medini et al. utilize Count-Min Sketches—a probabilistic data structure—to log-compress the output layer, allowing extreme classification to occur within strict sub-linear memory bounds.

Hierarchical Routing

Rather than performing a massive matrix multiplication against every class simultaneously, inputs can be routed through a tree structure. The authors of Softmax Tree replace the flat softmax layer with a hierarchical tree of smaller classifiers. This structural shift changes both the inference speed and the active memory footprint from linear ($O(C)$) to logarithmic ($O(\log C)$), allowing models with hundreds of thousands of classes to fit onto resource-constrained edge devices.

Key Foundational Work

Class-Specific Simplex-Latent Dirichlet Allocation for Image Classification (2013) — contributed 1 concept elements to this direction.
Online multiclass learning by interclass hypothesis sharing (2006) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_linear_parameter_scaling_linear_memory_s_9c174b5b,
  title = {linear parameter scaling (linear memory scaling)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/linear-parameter-scaling-linear-memory-scaling/rdr_9c174b5beb514e32a702785faf900476},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_linear_parameter_scaling_linear_memory_s_9c174b5b_v1,
  title = {linear parameter scaling (linear memory scaling)},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/linear-parameter-scaling-linear-memory-scaling/rdr_9c174b5beb514e32a702785faf900476/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake