acceptodds
Under review as a conference paper at ICLR 2027

Vocabulary Pruning via Submodular Optimization

Abstract

Large language models generate text by scoring a distribution over the full vocabulary at each decoding step, making vocabulary size a significant latency and memory component, particularly in speculative decoding, early-exit inference, and edge deployment. Vocabulary pruning addresses this by retaining only a fixed subset of tokens, but existing approaches rely on frequency-based heuristics that optimize average token coverage and can leave minority languages or specialized domains catastrophically uncovered. Here, we formalize vocabulary pruning as a combinatorial optimization problem and propose maximizing the expected log retained probability mass, an objective equivalent to minimizing the expected reverse KL divergence to the teacher distribution. The objective is monotone submodular, yielding a greedy algorithm with a -approximation guarantee. Frequency pruning is its first-order approximation: it is optimal under a sufficient common-ranking condition and can be suboptimal when the condition fails. Our experiments show that vocabulary pruning reduces memory and latency, while the proposed support selection improves accepted length and throughput in speculative decoding at the same vocabulary budget.

Primary area:
generative models
Keywords:
vocabulary pruning, inference, language models

Reviews

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

This paper studies how to select a fixed output vocabulary offline while keeping the tokenizer unchanged. The method maximizes the expected log retained probability mass, which is equivalent to minimizing expected reverse KL from the restricted and renormalized teacher distribution to the original teacher. The authors show that the objective is monotone submodular and use a lazy greedy algorithm with a standard approximation guarantee. They also interpret frequency pruning as a first-order approximation, giving sufficient conditions for optimality and examples where it is suboptimal. Experiments cover synthetic mixtures, multilingual distributional fidelity and text continuation across several model families, and speculative decoding with EAGLE-2. The authors report improvements over frequency and magnitude pruning on a smoothed fidelity metric and continuation quality, as well as modest throughput gains over frequency pruning in several decoding settings.

Critical strengths
  1. The paper presents a theoretical analysis of static vocabulary pruning based on a reverse-KL formulation and submodularity. This helps explain when frequency-based selection can be suboptimal and motivates a selection rule that gives greater weight to poorly covered contexts.
Critical weaknesses

1.Although the paper compares with FR-Spec, comparisons with other relevant methods, such as VocabTrim and SpecVocab, are missing. The main throughput gains are reported on Arabic, while gains on other tested languages are smaller or tied. A controlled comparison with representative prior methods would help establish the practical value of the proposed selector.

Questions for authors

1.Could you compare your method with VocabTrim and representative dynamic vocabulary-selection methods, such as SpecVocab, NanoSpec, or DynaSpec(choose one), under matched experimental conditions? Please discuss the trade-offs in throughput, memory usage, training costs, etc to clarify when the proposed approach is preferable.

Reviewer_vrUGOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes a method for reducing the size of the vocabulary of a LLM. Reducing redundant tokens would save memory and speed up generation. This paper formulates vocabulary pruning as an optimization problem of selecting optimal vocabulary maximizing the log probability of token probabilities under a cardinality constraint, which corresponds to a monotone submodular function maximization problem. Therefore, a greedy algorithm can find a guaranteed approximate solution. The paper also shows that existing vocabulary pruning method based on frequency is a first-order approximation. Experimental results with multiple models show that the proposed method shows better than a frequency-based baseline.

Critical strengths
  • The experimental results show that the proposed method improves the scores of the frequency-based methods for multiple LLM models.

  • The paper provides a theoretical analysis on the relation between the proposed formulation and a frequency-based method.

Critical weaknesses
  • I have a few concerns on the proposed submodular maximization formulations.

    • The approach of formulating the vocabulary pruning problem as a submodular maximization already appears in [1]. Although there is a difference in input-side and output-side pruning, the novelty of the proposed approach seems limited.
    • The proposed objective compute scores based on pc(v)p_c(v), which is the next token probability given context cc. Since the next token probability changes drastically depending on context cc, the proposed empirical score (Eq.(6)) also strongly depends on the quality of sample contexts c1,…,cnc_1, \ldots, c_n. I think that the proposed method would require a huge number of samples contexts to retain globally rare yet locally indispensable tokens.
    • The authors say that the objective function is monotone submodular under the condition that pc(v)p_c(v) are fixed. However, pc(v)p_c(v) are computed with full vocabulary, and they should be changed depending on AA, especially when ∣A∣|A| is small. Therefore, I think the proposed objective is inherently not a monotone submodular.
  • Experimental results seems weak to support the superiority of the proposed approach.

    • the paper lacks the details of the datasets used in experiments. The explanations appearing in line 315 are insufficient. The paper should show statistics of the used dataset. As far as I can read, the number of datasets used in evaluation seems limited.
    • Most of the experiments are conducted for fixed K=1000K = 1000. Since vocabulary pruning is a method achieving a good trade-off in between vocabulary size and effectiveness, the results with other values should be reported.
    • As I've mentioned in above, the proposed method strongly depends on sampled contexts. c1,…,cnc_1, \ldots, c_n. The paper should show how many samples are needed to obtain good results for each dataset.
    • The paper must report the mean and variance of the realists, considering the above dependence on sample contexts.
    • Although speculative decoding is important, the effectiveness of the proposed method should be evaluated with muitiple downstream tasks.
    • The proposed method should be compared with more strong baseline methods.

[1] Jia Peng Lim, Shawn Tan, Davin Choo, and Hady W Lauw. A Partition Cover Approach to Tokenization. In Proc. 39th Conf. on Neural Information Processing Systems (NeurIPS), 2025.

Questions for authors

I think K=1000K = 1000 is very small for LLMs. Why are the models works better with such a small model size? Why do you report results for K=1000K=1000? What happens if we change KK?

Could you please provide detailed statistics of datasets used in experiments?

How can we decide the number of sufficient samples for specific tasks?

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

The paper studies output-side vocabulary pruning, where a frozen language model score only a fixed subset of output tokens. The paper proposes choosing subset by maximizing the expected log retained probability mass over a calibration distribution of contexts. The objective is monotone submodular, so lazy greedy selection inherits the classical approximation guarantee, and frequency pruning emerges as its first-order linearization that is optimal only when contexts share a common token ranking. Experiments on Qwen, Gemma, and Llama models, mostly on multilingual FLORES data, show lower smoothed divergence and slightly higher chrF than frequency and magnitude pruning at a budget of 1000 tokens, with larger gaps under skewed calibration. In FR-Spec with EAGLE-2 drafters, the method gives modest accepted-length and throughput gains over frequency selection on minority-language evaluation.

Critical strengths
  • The framing is clean and gives a useful lens on a widely used heuristic. The exact reverse-KL interpretation, the result that frequency pruning is the linearized objective, and the common-ranking condition together explain when frequency-based vocabularies such as FR-Spec should work and when they should fail. The heterogeneity and calibration-skew sweeps are consistent with this prediction.

  • The method is simple and cheap, requiring only an offline lazy greedy pass over calibration distributions with no change to the model or tokenizer, so it can be dropped into existing static-vocabulary pipelines.

Critical weaknesses
  • The objective does not match the main application metric. The paper’s own appendix notes that speculative decoding acceptance probability equals retained mass, which is linear, so frequency selection maximizes expected acceptance when calibration matches deployment. Consistent with this, the sample-based acceptance study shows no gain or a small loss on the Latin-5 and script-5 mixtures, and reweighting the high-skew result to the actual 99 to 1 deployment gives a negative estimate.

  • The reported gains rely on a deliberate mismatch between calibration and evaluation. The FR-Spec results calibrate on 99 percent English but evaluate only on the minority language, so the method mainly acts as a robustness correction. Simple baselines for that goal are missing, such as frequency with per-language reweighting, per-language quotas, or a union of per-language top tokens.

  • The theoretical contribution is largely standard. Submodularity of a concave function of a modular function, the reverse-KL projection result, and the greedy guarantee are textbook facts, and the hardness statements apply to general monotone submodular maximization rather than to this specific problem.

  • Effect sizes are small and sometimes inconsistent. chrF differences are often a fraction of a point, for example 1.92 versus 1.98 on Gemma-2-2B, throughput gains over frequency are about 1 to 6 percent, and on Llama-3.2-1B frequency is better on Latin-5 at 4,000 tokens while the divergence score and chrF disagree on Multi-script-5.

  • The gains appear only at very small budgets. At 1,000 tokens, all pruned models lose a large share of quality, with macro chrF dropping from 10.0 to about 5, while at the practically used budget of 16,000 tokens the paper reports greedy and frequency within one percent of each other.

  • The main quality metric is a smoothed top-8,192 surrogate rather than the exact reverse KL analyzed by the theory, and the authors state that the method ordering under exact KL is not guaranteed, which weakens the link between theory and experiments.

  • The efficiency claims are presented in a misleading way. The 41 to 92 times speedups in the headline figure and the efficiency table come from an isolated projection-and-softmax benchmark rather than end-to-end inference, the hardware for these timings is not specified, and latency at 1,000 tokens is almost identical across models, which suggests overhead-dominated measurements.

  • The experimental scope is narrow. All models are 0.5B to 7B and evaluation is almost entirely multilingual sentence continuation, even though the motivation highlights code and domain-specific tokens, and there is no comparison with other drafter-vocabulary methods such as VocabTrim or SpecVocab.

  • The large Hindi regression in sample-based acceptance, about 12 points, is left unexplained.

Questions for authors

see problems listed in weakness

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.