acceptodds
Under review as a conference paper at ICLR 2027

Encoding The LLM Vocabulary Bottleneck

Abstract

Large Language Models (LLMs) have achieved strong performance across a wide range of natural language processing tasks, but their increasing scale raises significant challenges in computational and memory efficiency. One of the major contributors to these costs is the decision layer (referred to as the Softmax layer), a fully connected projection followed by a Softmax activation. Its learned parameter count and associated optimizer-state count grow linearly with vocabulary size and can account for a substantial fraction of a smaller model's trainable state. In this work, we propose a framework based on Error Correcting Output Coding (ECOC), in which the standard Softmax layer is recovered as a special case corresponding to the identity coding, while more compact decision-boundary encodings are obtained by replacing this identity structure with alternative ECOC encodings, yielding an ECOC-Softmax decision layer. Experiments spanning three architectures and vocabularies of up to 114K tokens show that, with binary codewords of length 200, ECOC-Softmax keeps top-1 accuracy within around 2 percentage points of the best Softmax baseline while reducing the trainable output-layer parameter count by up to 571 times, total trainable parameters by 18–23%, and output-layer FLOPs per predicted token by 3.8–4.4 times. Extending this, ECOC-Tying reduces total trainable parameters and associated optimizer state by 22–29% relative to tied Softmax.

Primary area:
foundation or frontier models, including LLMs
Keywords:
Large Language Models (LLMs), Softmax, Error Correcting Output Codes (ECOC), pretraining, distillation, scalability

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_eEKJOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes using error correcting output coding (ECOC) to calculate an approximate softmax score. The main application the paper targets is the unembedding (LM head) layer, which can be very expensive for very small models.

Critical strengths

The ECOC-Softmax method is pretty interesting as an approximation for softmax. The writing explains the concept well.

Critical weaknesses

My main concern with this paper is that the targeted problem (making the unembedding faster) is generally not a real problem at large model scales. The only models for which the unembedding is a large cost are very small models with a few billion active parameters. For example, in Kimi K3, a large MoE, there are 104B active parameters and only 7168*160000 = 1.1B parameters in the unembedding. Furthermore, since the unembedding is a dense matmul, the unembedding will generally have higher MFU than other ops, making it relatively cheap. If the concern is the memory of softmax, one can use a tiled online softmax kernel (we only need to store the probability of the correct token for training) or write a fast top-k kernel for sampling. Even if we want full sampling we can also use online gumbel sampling, which has the same marginal probabilities. The test setup in this model (slow GPU, 256 sequence length, not fused/well optimized kernels for baseline softmax) also makes it unclear if the proposed method can be implemented efficiently.

Questions for authors

Are there other uses (e.g. in attention, which is the other key use of softmax) of ECOC-Softmax? I like the idea and its pretty cool, but it just doesn't seem very practical or useful in the proposed setup since the targeted problem isn't a problem at scale.

Reviewer_kLNoOpenReview ↗
Rating
2
Confidence
2
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

In LLMs, the decision layer (lm_head) uses a linear projection to map hidden states to vocabulary-sized logits, followed by Softmax to obtain next-token probabilities. As the vocabulary size grows, the parameters of this layer increase substantially, creating a major memory and compute bottleneck, especially for smaller models where the output layer accounts for a large fraction of the total parameters. To address this inefficiency, the authors propose ECOC-Softmax (and its weight-tied variant, ECOC-Tying) based on Error Correcting Output Coding (ECOC). Instead of projecting directly to the vocabulary size, the proposed method projects hidden states to a much smaller code length and decodes token probabilities using a fixed binary code matrix, demonstrating reductions in trainable parameters and output-layer compute with a modest drop in top-1 accuracy.

Critical strengths
  • Well-motivated problem While most LLM efficiency research focuses on the transformer backbone, this paper highlights an important and often overlooked bottleneck: the linear growth of the decision layer (lm_head) with vocabulary size, which is particularly costly for smaller models.
  • Broad architectural validation and system-level profiling The authors validate ECOC-Softmax by pre-training from scratch across three distinct model families (OPT, Qwen2, and Mistral) on TinyStories, demonstrating applicability across different architectures and hidden dimensions in this setting. In addition, the paper provides detailed hardware-level profiling.
  • Clear presentation The paper is well-structured and easy to follow. Interpreting standard Softmax decision boundaries through identity codes and illustrating the architecture via clear diagrams (Figures 1 and 2) make the proposed formulation intuitive.
Critical weaknesses

W1. Equivalence to a 2-Layer Bottleneck and Missing Baselines Since the L1 distance to a binary codeword is affine in u~\tilde{u}, ECOC-Softmax is essentially a d→L→Vd \rightarrow L \rightarrow V bottleneck with a sigmoid activation and fixed decoding weights and codeword-dependent biases (Section 3, Appendix B.1). The most natural baselines are therefore missing. These include (a) a fully trainable sigmoid bottleneck, (b) a linear low-rank output head, and (c) a frozen continuous random projection, all with the same bottleneck dimension LL. A trainable sigmoid bottleneck would have the same dominant forward GEMM cost and similar dense inference storage at the same precision as ECOC (Table 4, Appendix A.3). Freezing the V×LV \times L decoder saves its gradients and optimizer states, as well as decoder-weight-gradient and optimizer-update computation (Appendix B.2). It remains unclear whether these additional training-time savings justify the accuracy loss.

W2. Limited Validation of ECOC-Tying Most small LMs, including the models that motivate this study (Lines 014–015, 042–043), use weight tying by default. Relative to Tied Softmax, ECOC-Softmax gives no reduction in trainable parameters (Table 3), so the practical benefit depends on ECOC-Tying. However, ECOC-Tying restricts all input embeddings to a subspace of dimension at most LL built from a semantics-agnostic code matrix (Eq. 3), and its accuracy is missing from Table 1 and only partially reported in Table 2. Whether it holds up across settings remains unverified.

Additional concerns

W3. Perplexity Gap Apart from a single near-tie (Table 14), ECOC-Softmax trails Softmax in top-1 and top-5 accuracy, and its perplexity is substantially worse (Table 15), as the authors acknowledge (Lines 369–371). Since perplexity is closely tied to generation quality, this gap is a concern.

W4. No Downstream Evaluation All quantitative results are next-token metrics on pre-training corpora. Whether the compressed token interface preserves performance on standard downstream tasks is not evaluated (acknowledged in Lines 480–481).

Questions for authors

Q1. Comparison with 2-Layer MLP / Low-Rank Baselines Have you considered comparing ECOC-Softmax against a fully trainable sigmoid bottleneck, a linear low-rank output head, or a frozen continuous random projection of the same bottleneck dimension LL? How does freezing the second layer (V×LV \times L) as a binary code matrix compare to training it in terms of the accuracy-efficiency trade-off?

Q2. Perplexity and Zero-Shot Downstream Performance Could you report the Perplexity (PPL) on the main open-domain datasets (C4 and WikiText-103, including for ECOC-Tying), as well as the models' zero-shot language understanding performance on standard downstream benchmarks?

Q3. Scaling Token Budgets and Training Stability for ECOC-Tying Applying ECOC-Tying to small models appears particularly relevant for reducing trainable parameters beyond standard weight tying. However, the C4 experiment with Qwen2-0.5B uses only 650M training tokens (Appendix A.1, Table 6). Could you provide learning curves or a longer-budget comparison of ECOC-Tying and Tied Softmax to determine whether their accuracy gap persists as training progresses and whether ECOC-Tying remains stable without early saturation? Furthermore, how does its downstream benchmark performance compare to standard Tied Softmax at scale?

Reviewer_vLY9OpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The vocabulary-sized output layer can account for a large share of a smaller language model’s parameters and training state. This paper proposes ECOC-Softmax, which replaces the large learned output matrix with a compact projection and fixed binary token codes. ECOC-Tying also derives input embeddings from the shared compact representation. Experiments cover three architectures on TinyStories, with additional C4 and WikiText-103 studies using larger vocabularies. The method substantially reduces trainable parameters and output-layer computation while keeping token prediction accuracy fairly close to Softmax.

Critical strengths
  1. The paper addresses a useful compression problem beyond the transformer backbone. It reports measured memory and timing results and distinguishes trainable parameter savings from codebook storage.
  2. The experiments vary vocabulary size and code length and include tied, adaptive, and hierarchical Softmax baselines. These comparisons give a useful picture of the accuracy-cost trade-off.
Critical weaknesses
  1. A learned low-rank output layer with a matched parameter budget is missing. This is a direct baseline for testing whether fixed binary codes offer an advantage over simply reducing the output-layer dimension. The current comparisons do not isolate the value of the coding design.
  2. The quality evaluation relies heavily on top-1 and top-5 token accuracy despite a substantial perplexity gap. For example, Mistral’s full-vocabulary TinyStories perplexity rises from 3.53 to 6.52 with 200-bit codes. There is no systematic downstream or generation evaluation, and no common validation-based temperature calibration to assess how much of this gap can be recovered.
  3. The training and efficiency settings limit the conclusions. Models are trained from scratch, with the C4 model receiving about 650M tokens and the 7B study mainly using TinyStories. Results at these budgets may not reflect fully trained language models. Efficiency also depends on implementation: the appendix shows that fused cross-entropy reduces the peak-memory advantage substantially. The paper should give more emphasis to optimized comparisons and include broader training-budget checks.
Questions for authors

See weakness above.

Comments on the paper

1 comment
~Itay_Evron1OpenReview ↗

Connections to extreme classification

Dear authors,
Thank you for the interesting manuscript.

I think the manuscript would benefit from discussing connections to the extreme classification field, which studies classification problems with very large label spaces.

For example, Jasinska and Karampatziakis (2016) and Evron et al. (2018) developed compact, graph-based output representations and efficient decoding methods, with the latter explicitly connecting these representations to ECOC. These approaches represent large label spaces using a logarithmic number of learned scoring functions and explore trade-offs between accuracy, model size, and prediction time.

Additionally, in Evron et al. (2023), we showed that codeword-to-class assignments can substantially affect ECOC performance. In particular, assigning similar codewords to similar classes can make the induced binary subproblems easier and improve generalization, while preserving the codebook’s other important properties. This suggests a potential extension to the binary-index-based assignment with random-bit augmentation described in your Section 4.1: exploring assignments that reflect token similarity. It would be interesting to discuss this connection, perhaps as a direction for future work.

It is important to note that all the aforementioned papers did not utilize ECOC for the softmax layer of neural networks like the manuscript suggests, but were rather limited to basic (mostly linear) models.

Good luck with your submission!

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.