acceptodds
Under review as a conference paper at ICLR 2027

Head-Tail Sampled Softmax for Scaling Vocabularies in Language Models

Abstract

Training a language model with softmax cross-entropy scores every vocabulary token at every position, though the loss needs them only for one normalizing sum. On a compact backbone with a large vocabulary, the output layer takes close to a third of a step's FLOPs, 28.9% in Qwen3.5-0.8B. Sampled softmax estimates that sum from a sample, but matches cross-entropy only if each draw is weighted by the inverse of how often it is drawn. Earlier language models trained with in-batch negatives are a sampled softmax without that weight, their scores deflated by token frequency, largely explaining why their direct readout reached 5× cross-entropy's perplexity. We propose head-tail sampled softmax (HTSS), which sums the K most frequent tokens exactly, where sampling is noisiest, and weights the sampled tail. The estimate of that sum stays unbiased at every K, so the loss and gradient consistently estimate those of cross-entropy. HTSS changes only the training loss, so the model and its inference are unchanged, while a step scores a third of the vocabulary. On GPT-2 (124M), weighting alone leaves a 2.1% gap to cross-entropy at matched steps, and at the same cost the exact head cuts it to 1.3%. At equal training compute, HTSS reaches 2.2–2.9% lower perplexity than cross-entropy, and overtakes it on a 304M multilingual backbone from V = 128K. At 256K it reaches 4.5% lower perplexity on 46% less peak training memory, never forming the logit matrix. Finetuning base Qwen3.5-0.8B and Llama 3.2 1B, HTSS lands within 0.34% of cross-entropy's perplexity on 12–20% fewer training FLOPs.

Primary area:
foundation or frontier models, including LLMs
Keywords:
sampled softmax, llm, language modeling, large vocabulary, importance sampling, efficient training, contrastive language models

Reviews

Among:
Shape:
1234this paper, Top 4%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.33 over 3 reviews, above 96% of the others.
Reviewer_9aNBOpenReview ↗
Rating
4(+1)
Confidence
2
Informativeness
3
Presentation
2
Soundness
3(+1)
Read review
Paper summary

This paper introduces a method named HTSS to speed up the softmax function in the language modeling head module of large language models. Specifically, HTSS first takes scores of target token, K most frequent tokens, and M sampled tokens from the last of vocabulary, then estimates the training loss based on their scores and frequency. Experimental results show that HTSS can achieve better results under the same computing with baseline methods while reducing the peak GPU memory usage.

Critical strengths
  • The proposed method achieves better performance while less GPU memory used compared to other baseline methods.
  • The effectiveness of HTSS is supported by theoretical analysis, and HTSS is well motivated.
Critical weaknesses
  • HTSS mainly focuses on improving the training speed of compact language models with large vocabulary where the forward of language modeling head composes nearly 30% of the overall computation.
  • The effectiveness of HTSS will reduce for larger language models and less vocabulary used. Therefore, large language models like LLaMA 70B may not benefit from this method.
Questions for authors
  • I find that most of improvement on the zero-shot downstream tasks is less than 1% (Table 4). Are these improvements statistically significant?
3 comments

Thank you for the review and for raising the question of significance. We have uploaded a revised version, with changes to the text marked in blue. The revision labels which end of Figure 3 holds the most frequent tokens, reports every seed in one table (Table 4, which renumbers the zero-shot table you refer to as Table 5), states both training budgets in the abstract, and adds the significance tests to the caption of Table 5.

Q1 (significance of the zero-shot gains). The gains on LAMBADA are significant, and on the multiple-choice tasks HTSS matches CE while training at a lower cost. In Table 5, HTSS-mc reduces its perplexity from 242.6 to 191.7 (tied) and from 218.9 to 162.1 (untied). Averaged over three seeds, HTSS-mc gains 3.0 accuracy points both tied and untied, and HTSS gains 2.2 and 2.0 at matched steps (Holm p≤1.6×10−15p \le 1.6 \times 10^{-15}; Table 6). Additionally, in Table 5, no multiple-choice difference from CE is significant. Every difference lies within 1.4 standard errors, below the 1.96 needed at the 5% level, and the largest is 2.1 accuracy points (HTSS on SciQ, tied). Paired per-item tests over three seeds are more sensitive. We compared each HTSS and HTSS-mc run with the CE run of the same seed (exact McNemar tests, Holm-corrected across the seven tasks; App. C.3, Table 6). Across the six multiple-choice tasks, only two differences are significant: both are small gains for HTSS-mc (ARC-c +1.5 points tied; HellaSwag +0.5 untied), and none favors CE. We also ran the evaluations on the 304M vocabulary sweep; in this setting, we get similar results: HTSS-mc is never significantly behind CE on any multiple-choice task under either accuracy score, and its LAMBADA gains are significant at every vocabulary size (App. D.3, Table 8).

W1/2 (scale and vocabulary size). We agree with the point on scale, which §1 already stated as the paper's scope. Since HTSS can save at most as much as the output layer costs, its benefit diminishes as the backbone grows relative to the vocabulary size. On our 304M backbone, HTSS is behind CE at matched compute at 32K and 64K and ahead from 128K (Table 2). HTSS targets compact backbones with large vocabularies. The output layer takes 28.9% of a step in Qwen3.5-0.8B and 17.5% in Llama 3.2 1B, and HTSS-mc beat CE in fine-tuning on both. Because only active parameters count, MoEs such as Qwen3.5-35B-A3B (15.5%) and gpt-oss-20b (14.4%) reach shares close to Llama's, and our revised future work (§5) includes them.

Thank you for your responses, which address my concerns! I have modified my ratings, correspondingly, Good luck : )

Thank you! We are glad the significance analysis answered your question, and we appreciate your support and the updated score.

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

The authors propose a multiple division of to avoid forming the complete vocabulary when approximating the softmax sum denominator. Additionally they observe and recover the term log q that appear in CWT. The two mechanisms explain the gap between CWT and CE.

Critical strengths
  • The observation is valuable and has a potential application when suited.
  • Validation complete in limited to small models and includes pretrained models application.
Critical weaknesses
  • Research is very niche but valuable under those conditions
Questions for authors

In general, the authros make a good work, and I have very few concerns. Considering that the two elements in the article are the recovery of log q and the Head strategy, my main question concerns understanding better the head part.

  • How the size K effectively affect the head?
  • For the sake of discussion, what alternative methods could be used to reduce the overhead of selecting the head?
3 comments

Thank you. We have uploaded a revised version, with changes to the text marked in blue.

Q1 (how K affects the head). To isolate what K does, we held the number of scored candidates fixed at K + M = 18,432, so that every run has the same FLOPs and memory, and moved candidates between the exact head and the sampled tail, training GPT-2 with the recipe of Table 1 (App. C.5). Going from no head (K = 0) to K = 2,048 closes about 40% of the perplexity gap to CE, and going on to K = 8,192 closes only another 10%. The remaining gap falls on the most frequent tokens and persists at K = 8,192, where the head already sums the entire first-frequency decile exactly, so simply sampling those tokens does not fix it completely (§4.2; App. C.5 now gives the first-decile numbers for each K).

We use K = 2,048 for every model and vocabulary because the most frequent tokens account for most of the variance of the estimated softmax denominator. The 2,048 most frequent tokens constitute 4% of the GPT-2 vocabulary but account for 72% of tokens in FineWeb-Edu. Figure 4b shows that most of this variance comes from these frequent tokens (App. A.1), so summing them exactly removes most of it, which is consistent with a larger head adding little. Part of the head's gain may also come from scoring more distinct tokens. With replacement, 28% of the draws at K = 0 are repeats, against 14% at K = 8,192 (App. C.5).

Q2 (reducing the cost of selecting the head). Selecting the head costs nothing during training, because the head is the K most frequent tokens, counted once before training on a prefix of the training data, together with the tail distribution (§3.2–3.3). At a fixed candidate count, scoring a head column costs the same as scoring a sampled one, and drawing the tail takes at most 0.11% of a step in our measurements (App. C.6). Any alternative would trade some per-step cost for a better head or tail distribution, for example, the tokens the model scores highest at each position, or a tail distribution adapted during training. Either keeps the estimated denominator unbiased, since our unbiasedness result (Prop. 1) holds for any head and any tail distribution that assigns a known nonzero probability to every tail token. Each, however, needs a per-step search or a periodic refresh. Between refreshes, a model-aware proposal can become stale, and a single draw can then account for most of the estimated denominator (App. A.3). We kept the static head and tail distributions. Now, §5 lists both alternatives as future work, along with sampling frequent tokens within the head.

My questions are addressed. I ratify the score.

Thank you for reading our response and for confirming your positive assessment. If any further point would be useful to clarify, we would be glad to address it during the discussion period.

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

This paper addresses the cost of the output layer in language-model training with large vocabularies, where scoring every vocabulary token at every position can take close to a third of a training step (28.9% for Qwen3.5-0.8B). It diagnoses an earlier failure: contrastive weight tying (CWT) is a self-normalized sampled softmax whose proposal is the in-batch token distribution, and it omits the log q correction that sampled softmax requires, so its scores are deflated by token frequency. The proposed head-tail sampled softmax (HTSS) sums the K most frequent tokens exactly, importance-samples the rare tail with M draws from a static square-root tail proposal, and applies the log q correction only to sampled tail tokens, so the partition-function estimate stays unbiased at every K and the gradient consistently estimates the full-softmax gradient. Only the training loss changes; the model and inference are unchanged, and a step scores about a third of the vocabulary. Experiments include GPT-2 (124M), a 304M multilingual backbone across vocabulary sizes from 32K to 256K, and fine-tuning of Qwen3.5-0.8B and Llama 3.2 1B, compared with full cross-entropy, cross-entropy through a fused Cut Cross-Entropy kernel, CWT, and sampled softmax.

Critical strengths
  1. A sharp diagnosis that explains a known failure and directly motivates the method. The paper shows that omitting the log q correction accounts for about 80% of the loss gap between the CWT readout and cross-entropy, and then designs HTSS around exactly that correction, with an exact head to remove the variance contributed by frequent tokens. This is a clear, testable explanation, not just a new loss. 2. Matched-compute and memory gains that grow with vocabulary size. At equal training compute, HTSS reaches 2.2-2.9% lower perplexity than cross-entropy on GPT-2, and on the 304M backbone it overtakes cross-entropy from V = 128K, reaching 4.5% lower perplexity at V = 256K with 46% less peak training memory and without forming the logit matrix. Fine-tuning results are also encouraging: HTSS-mc is within 0.34% of cross-entropy perplexity on 12-20% fewer training FLOPs for Qwen3.5-0.8B and Llama 3.2 1B.
Critical weaknesses
  1. The advantage is a matched-compute advantage, not a matched-steps advantage, and it is demonstrated only at modest scale. At matched steps on GPT-2, HTSS is 1.3% behind cross-entropy in test perplexity (23.65 against 23.35 tied, and 22.35 against 22.05 untied), and the paper itself notes that the first-decile deficit for rare tokens persists at every exponent. Pretraining is at most 828M parameters and fine-tuning at most 1B, so the claim that the method will help at the scale where the output layer is most expensive is extrapolated rather than demonstrated. 2. Reliability and downstream breadth are limited. No multiple-seed error bars or significance analysis is reported for the small perplexity differences (for example, the 0.15% and 0.34% fine-tuning gaps at matched steps), the zero-shot downstream suite shows an exception on LAMBADA, and the fused-kernel implementation, which is central to the memory claim, is compared mainly with a Cut Cross-Entropy baseline that the paper notes has lower memory but retains dense FLOPs. A reader cannot yet tell how much of the practical benefit survives on other hardware, kernels, or downstream tasks.
Questions for authors
  1. Could the authors report multiple-seed means and error bars for the main perplexity comparisons, and clarify whether the 2.2-2.9% matched-compute gain on GPT-2 and the 4.5% gain at V = 256K are stable across seeds? 2. What happens to the rare-token (first-decile) deficit as K and M are varied, and is there a principled rule for choosing K and M for a new vocabulary and corpus, rather than the single coverage parameter described in the paper? 3. Could the authors provide a larger-scale or longer-training validation, or a downstream evaluation beyond the reported zero-shot suite and SmolTalk fine-tuning, to support the claim that HTSS will transfer to the large-backbone, large-vocabulary regime where the output layer dominates?
3 comments

We thank the reviewer. We have uploaded a revised version, with changes to the text marked in blue. Each point below indicates where to find them.

W1 (matched steps vs. matched compute). The perplexity advantage appears only at matched compute, which §4.1 declares the primary comparison for a method that makes each step cheaper. Figure 3 now states that decile 1 contains the most frequent tokens and decile 10 the rarest, which our original labeling left unclear. The first-decile deficit you mention concerns the most frequent tokens. At matched steps, HTSS is 1.8% behind CE in the first decile, which contains most of the token mass and thus determines the aggregate, and it equals or beats CE in the other nine deciles. At matched compute, HTSS-mc is ahead in all ten, by 2.2% on the most frequent and 23.5% on the rarest (§4.2).

W1/Q3 (scale). HTSS can save at most η\eta, the output layer's share of a training step's FLOPs, which increases with vocabulary size and decreases as the backbone grows. On our 304M backbone, raising V from 32K to 256K raises η\eta from 7.5% to 39.4%, and HTSS-mc improves w.r.t. CE in test bpb from 128K (see Table 2). In fine-tuning, it outperforms Qwen3.5-0.8B (η\eta = 28.9%) and Llama 3.2 1B (η\eta = 17.5%) (§3.4, §4.4). HTSS thus suits small language models, and we expect the same for MoE models, where each token activates only a few experts: counting active parameters, η\eta is 15.5% in Qwen3.5-35B-A3B and 14.4% in gpt-oss-20b, close to Llama 3.2 1B.

During the discussion period, we spent our compute on additional seeds (see W2/Q1), since larger pretraining runs take days per run. The revised Limitations (§5) states our pretraining scale (at most 828M parameters, 20 tokens per parameter), notes that longer and 1B-scale pretraining remain untested, and lists MoE as future work.

W2 (hardware and kernels). Our cost columns were measured on A100 GPUs (GPT-2 and the vocabulary sweep) and H100 GPUs (fine-tuning). Fused HTSS reaches the peak memory of CCE, the memory-efficient CE kernel (28.1 GB on tied GPT-2), and runs 1.25$\times$ faster, because it also removes most of the output layer's FLOPs, which CCE keeps (§4.2, App. C.6). Against CE with materialized logits, it cuts peak training memory by up to 46% at 256K (§4.3). The added GPT-2 and fine-tuning seeds were run on a different GPU type than the original runs, and their differences from CE have the same sign and similar magnitude (App. B.5, Table 4).

Q2 (K, M and the first decile). On GPT-2, HTSS-mc is 2.2% better than CE on the first decile at matched compute (§4.2). At matched steps, HTSS is about 2% behind CE on that decile at every head size we tried, including K = 8,192, where the head sums the whole decile exactly, so the deficit does not arise from sampling (App. C.5). Along M, it tracks aggregate perplexity.

We fix K = 2,048, since a larger head adds little (App. C.5), and set M to one coverage value, ρ=K+MV≈0.3\rho = \frac{K+M}{V} \approx 0.3, which we chose for GPT-2 (§3.4) and reused unchanged across all other models. Eq. (5) predicts, before training, whether HTSS-mc will beat CE, which it did whenever the step multiplier gg was above about 1.2, and in fine-tuning, already at 1.14.

W2/Q1 (seeds). We report three seeds for every GPT-2 and fine-tuning comparison and two at V = 128K (App. B.5, Table 4). In every seed, HTSS wins over CE at matched compute but loses at matched steps. The 2.2–2.9% you quote comes from seed 0 (Table 1 and §4.2). Now, the revised abstract quotes the three-seed means (1.9–2.6%), with tied GPT-2 going from 2.9% to 2.6% and untied from 2.2% to 1.9%.

Unfortunately, for the 4.5% at 256K, we have one seed, since a second would cost about 450 A100-hours (outside the allocated discussion time). We added a second seed at V = 128K instead, where HTSS-mc is slightly ahead of CE, so a sign change was most likely.

Each new seed changes the tail draws, the data order and, in pretraining, the initialization. Within a seed, CE, HTSS, and HTSS-mc run on the same GPU type. The following table shows this effect, where entries are changes relative to CE (negative = HTSS better).

SettingHTSS, matched steps (mean ± SD)HTSS, per seedHTSS-mc, matched compute (mean ± SD)HTSS-mc, per seed
GPT-2 tied, test ppl+1.57 ± 0.23%+1.30, +1.72, +1.69-2.63 ± 0.21%-2.87, -2.48, -2.53
GPT-2 untied, test ppl+1.59 ± 0.19%+1.39, +1.77, +1.62-1.92 ± 0.32%-2.19, -1.56, -2.01
Fine-tune, Qwen3.5-0.8B, test ppl+0.142 ± 0.009%+0.147, +0.132, +0.147-0.829 ± 0.019%-0.824, -0.850, -0.812
Fine-tune, Llama 3.2 1B, test ppl+0.328 ± 0.015%+0.341, +0.330, +0.312-0.330 ± 0.027%-0.307, -0.324, -0.360
304M, V = 128K, test bpb+1.37 ± 0.18%+1.24, +1.50-0.30 ± 0.19%-0.43, -0.16

W2/Q3 (LAMBADA and downstream evaluation). The LAMBADA difference is a gain for HTSS, as §4.2 now states. Of the seven zero-shot tasks, LAMBADA is the only one scored against the full vocabulary, and 62% of its target tokens fall outside the first frequency decile, against 18% of FineWeb-Edu tokens. HTSS-mc gains most on these rarer deciles (W1). On tied GPT-2, it lowers LAMBADA perplexity from 242.6 to 191.7. Paired tests over three seeds (App. C.3, Table 6) find significant LAMBADA accuracy gains for HTSS and HTSS-mc on tied and untied GPT-2, in every seed (pooled Holm p≤1.6×10−15p \le 1.6 \times 10^{-15}). On the multiple-choice tasks, three small gains for HTSS-mc and one loss for HTSS (PIQA, tied) are significant under only one of the two accuracy scores, none under both, and HTSS-mc is never significantly behind CE, so we claim parity on those.

We also evaluate the 304M backbone models of the vocabulary sweep, plus a second seed at 128K, on the same seven tasks (App. D.3, Table 8). Entries are differences from CE, computed from unrounded accuracies, and * marks a significant difference (Holm-corrected; App. D.3).

32K64K128K256K128K, second seed
HTSS, LAMBADA accuracy (points)+1.0+2.7*+4.3*+3.4*+5.1*
HTSS-mc, LAMBADA accuracy (points)+3.1*+3.0*+5.5*+5.8*+5.0*
HTSS-mc, LAMBADA perplexity-17%-20%-32%-35%-25%

Matched-steps HTSS gains significantly on LAMBADA from 64K on, even though its bpb is higher than CE's at every vocabulary size. The second seed at 128K (in the last column) reproduces both gains. On the multiple-choice tasks, a few differences are significant under one of the two standard accuracy scores (with and without length normalization), mostly gains for HTSS-mc and one loss for matched-steps HTSS (SciQ, second 128K seed, marked † in Table 8). None is significant under both scores, and HTSS-mc is never significantly behind CE, so we claim parity. The new downstream evidence uses the same seven tasks, now on the 304M models, with paired significance tests across three GPT-2 seeds.

The fine-tuning evaluation on IFEval and GSM8K is in App. E, Table 10. All comparisons with CE that have a standard error are within 0.98 of it, and at matched steps HTSS is slightly below CE on all eight metrics, each within noise (§5).

Q3 (multilingual downstream evaluation). Since our previous reply, we have been able to run the additional downstream evaluation you asked for. The 304M sweep models train on English and 28 other languages, but the downstream tasks are all in English. We have now evaluated them, including the second 128K seed, on machine-translated LAMBADA in German, Spanish, French and Italian. Entries are differences from CE at the same V and seed, averaged over the four languages (positive accuracy and negative perplexity favor HTSS). In parentheses is the number of languages with a significant accuracy gain (exact McNemar, Holm-corrected over the four languages). Bold marks a difference that is significant in all four languages, for perplexity by a 95% paired-bootstrap interval.

32K64K128K128K, second seed256K
HTSS, accuracy (points)+0.21 (1/4)+0.76 (1/4)+2.07 (4/4)+1.17 (2/4)+1.82 (4/4)
HTSS, perplexity+9.6%-0.8%-11.3%-0.1%-11.4%
HTSS-mc, accuracy (points)+0.76 (2/4)+1.19 (4/4)+2.44 (4/4)+1.76 (4/4)+3.46 (4/4)
HTSS-mc, perplexity-4.1%-8.2%-18.2%-12.5%-30.0%

No accuracy difference significantly favors CE, and CE has significantly lower perplexity only in a few languages at 32K and 64K. From 64K on, HTSS-mc's accuracy gain is significant in every language, and at 128K (first seed) and 256K both methods are significantly better than CE in every language, in accuracy and perplexity.

We have added these results to App. D.3 (Table 9). They complement the additional seeds and downstream evaluations in our earlier replies on the points raised in W2, Q1 and Q3. We would be glad to clarify anything else before the discussion period ends.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.