Source-linked AI summary
Improving the Diversity of LLM Outputs without a Trade-off
Ryoma Sato
TL;DR
LLMs may need to offer multiple ideas, but repeated generations can be similar, and arithmetic sampling can still select semantically similar tokens. DAST orders similar tokens together before arithmetic sampling; the authors report greater diversity and improved ProtoQA performance. The approach retains the marginal distribution and requires no generation-time overhead once the order is prepared.
Problem
Real-world tasks can have multiple useful answers, but generating again with a changed random seed may produce similar ideas; arithmetic sampling can also select different IDs with similar meanings.
Source: §1 · pp. 1–2Method
Results
DAST increases output diversity qualitatively and quantitatively and improves ProtoQA performance; on ProtoQA, it improves coverage over arithmetic sampling by up to 0.33 percentage points.
Source: §3.4 · p. 7, §5 · p. 8Takeaways & Limitations
The vocabulary order can be prepared from model parameters and reused, and DAST increases diversity without generation overhead or changing the marginal distribution.
Source: §2 · p. 3The guarantee concerns a desired output that exists and can be recognized when presented, and requires sufficiently many samples.
Source: §2 · p. 3
Abstract
from arXiv · showhide
We propose DAST (Diversifying Arithmetic Sampling with TokenTour), a method that increases the diversity of LLM outputs without any change to the marginal distribution and with negligible generation-time overhead (a few microseconds). We observe that token IDs are often arranged in a meaningless order and reassign them so that tokens with similar meanings appear consecutively. This can be done in advance in a few hundred seconds per model, and the resulting order can be reused for all subsequent generations. By combining this order with arithmetic sampling (or quasi-Monte Carlo methods), we make similar tokens less likely to be generated across runs while preserving the distribution. Our method not only produces qualitatively good ideas but also significantly improves performance on the downstream task of ProtoQA.
1 Introduction
The introduction motivates diverse multi-answer generation and identifies vocabulary ordering as an overlooked way to improve it. DAST combines an ordered vocabulary with arithmetic sampling, aiming to increase output diversity while preserving marginal distributions and improving ProtoQA performance.
1 Introduction
- Real-world tasks may have multiple useful answers, while generating again with a changed random seed can still yield similar ideas.Other diversification approaches can change the original distribution or increase generation time.Source: §1 · p. 1
- Diverse candidates can help find a correct solution in verifiable tasks, and diversity among passing outputs can itself matter [3] [32]; diverse outputs also have uses in RLVR [15] [18] [27] [37].The passage notes that RLVR training can stall when outputs are all correct or all incorrect [13] [36] [38].Source: §1 · p. 1
- Arithmetic sampling spaces K samples evenly, making repeated token draws less likely while each sample remains uniform and the marginal distribution stays unchanged.For K = 3, the samples are spaced 120 degrees apart.Source: §1 · p. 1, Figure 1 · p. 2
- Arithmetic sampling can still select different token IDs with the same meaning because similar plausible tokens may be scattered around the vocabulary order.The passage gives singular/plural forms, capitalization variants, and synonyms as examples.Source: §1 · p. 2
- Vocabulary-ID order has no meaning to the LLM but matters for arithmetic sampling, and prior work randomized rather than optimized that order [20].The authors say they are the first to consider assigning vocabulary IDs for arithmetic sampling.Source: §1 · p. 2
- WordTour orders word embeddings in one dimension, requiring no calibration data and allowing the resulting vocabulary order to be reused.The authors use it to address the large search space of possible vocabulary permutations.Source: §1 · p. 2
- DAST increases output diversity qualitatively and quantitatively and significantly improves performance on ProtoQA, which measures diverse and valid outputs.The authors also report that a well-organized vocabulary order can be obtained in a practical amount of time.Source: §1 · p. 2
2 Proposed Method (DAST)
DAST reorders a model’s vocabulary so similar tokens are adjacent, then applies arithmetic sampling as usual. The order can be prepared from model parameters and reused; the method retains arithmetic sampling’s marginal-distribution properties and has a conditional guarantee for obtaining a desired sequence.
2 Proposed Method (DAST)
- DAST reorders the vocabulary so similar tokens are adjacent, then uses arithmetic sampling to make simultaneously generated samples more likely to differ in meaning.The figure explains that different token IDs can still represent similar tokens under an unordered vocabulary.Source: §2 · p. 2, Figure 2 · p. 3
- The vocabulary is arranged around a circle to match mod1 placement in arithmetic sampling; DAST builds an initial tour with nearest-neighbor and refines it using 2-OPT.The authors found 2-OPT sufficient for arithmetic sampling; LKH only slightly lowered problem (1)’s objective, without improving diversity or downstream task performance.Source: §2 · p. 3
- Reordering requires only model parameters and uses the model’s input embeddings, so it needs no calibration data.The authors contrast this with reordering based on activation patterns, which would require calibration data and be more expensive.Source: §2 · p. 3
- The order must be built separately for each model but can then be reused for all its outputs; reordering typical tens-of-thousands-token vocabularies takes a few minutes.The authors released the orders used in their experiments.Source: §2 · p. 3
- Once the reordered vocabulary is available, DAST plugs into the existing generation program without generation overhead while increasing output diversity.It performs arithmetic sampling as usual.Source: §2 · p. 3
- If a desired sequence exists, the user can recognize it when presented, and token probabilities are positive, then some sufficiently large sample count K guarantees obtaining it.The theorem’s proof uses a token’s contiguous probability interval in the arithmetic code; the guarantee is stated for any input and target token sequences.Source: §2 · pp. 3–4
3 Experiments
The experiments evaluate DAST’s speed, vocabulary ordering, and output diversity across four models from two families, using ProtoQA to assess answer coverage. They also show how reordered token IDs change sampled answers in a qualitative example.
3.1 Experimental Setup
- The evaluation uses four models from two families and ProtoQA, which scores coverage of distinct human answers to commonsense questions without a unique answer.The experiment compares i.i.d. sampling, arithmetic sampling with standard vocabulary order, and DAST.Source: §3.1 · p. 4
3.2 Speed Comparison
- DAST adds about 2 microseconds per generated token, less than 0.4% of forward-pass time, while its vocabulary-order construction takes only a few minutes and is reusable.The table reports measurements on an NVIDIA RTX PRO 6000 Blackwell GPU and an AMD EPYC 9534 CPU.Source: §3.2 · p. 4, Table 2 · p. 5
3.3 Vocabulary Ordering
- DAST’s vocabulary-order objective values are close to the rigorous Held–Karp lower bound, while standard model orders leave considerable room for optimization.The lower bound is obtained from the dual problem; the true optimum is at least that value.Source: §3.3 · p. 5, Table 3 · p. 5
- Across the models, DAST places tokens with the same or similar meanings in contiguous segments, unlike the disordered standard token-ID orders.Table 4 shows selected segments for SmolLM2-1.7B and Qwen2.5-1.5B.Source: §3.3 · p. 5, Table 4 · p. 6
3.4 ProtoQA
- DAST and arithmetic sampling achieve approximately 2 to 4 percentage points greater coverage than i.i.d. sampling, and DAST improves coverage over arithmetic sampling by up to 0.33 percentage points.For Qwen2.5-1.5B and Qwen2.5-3B, the differences exceed the uncertainty indicated by the confidence intervals.Source: Figure 3 · p. 6, §3.4 · p. 7
3.5 Qualitative Example
- For a ProtoQA question, standard ordering lets arithmetic sampling select both “christmas” and “Christmas”; DAST places them close together and instead yields more varied first tokens.The example uses Qwen2.5-0.5B-Instruct, a smaller model included for illustration.Source: §3.5 · p. 7, Figure 4 · p. 7
4 Related Work
Prior work diversifies language-model outputs through sampling, prompting, search, representation changes, or post-training, often with trade-offs in quality, distribution, or compute. The paper assumes autoregressive LLMs and distinguishes its scope from diversification work on diffusion language models.
4 Related Work
- Temperature changes, prompt perturbations, and representation-intervention methods can increase diversity but commonly trade off output quality.The cited approaches include temperature changes [4] [8], prompt perturbation, and G2 [22], STARS [39], and SemDiD [25].Source: §4 · p. 7
- Sampling without replacement may slightly improve diversity but does not directly prevent duplicates among semantically equivalent sequences; beam-search methods empirically diversify outputs without guaranteeing it.The passage also notes that these methods change the original distribution [24] [19].Source: §4 · pp. 7–8
- Prompting and stratified-sampling alternatives can alter the distribution, while prompting may hinder parallel generation and stratified sampling generally increases processing time.The approaches discussed include prompting [26] and step-by-step stratified sampling [34].Source: §4 · p. 8
- Post-training and diverse base-model approaches require computation and change the distribution; diffusion-language-model diversification is a separate line because this paper assumes autoregressive LLMs.The cited examples include post-training [5] [17], BACo [33], and diffusion-language-model studies [12] [35].Source: §4 · p. 8
5 Conclusion
DAST increases LLM output diversity while preserving the marginal distribution, generation time, and parallelization. It explicitly arranges vocabulary tokens and improves diversity qualitatively and quantitatively.
5 Conclusion
- DAST increases LLM output diversity without changing the marginal distribution or generation time, while allowing parallelization.The conclusion reports both qualitative and quantitative diversity improvements.Source: §5 · p. 8
- DAST addresses the overlooked role of vocabulary ordering by explicitly constructing an arrangement.Source: §5 · p. 8
- The constructed arrangement improves qualitatively and quantitatively measured diversity.Source: §5 · p. 8