cs.CLSep 27, 2026
SaveImproving the Diversity of LLM Outputs without a Trade-off
Organizations: National Institute of Informatics
Abstract
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.
Figures & tables
Figure 1: Comparison of i.i.d. and arithmetic sampling when generating samples. With i.i.d. sampling, all three may fall on the same token. Arithmetic sampling places the three random numbers exactly 120 degrees ( of a turn) apart, making them less likely to fall on the same token. Note that even with arithmetic sampling, each arm is sampled uniformly over 360 degrees.
Figure 2: Comparison of arithmetic sampling and our proposed method, DAST. LLM vocabularies generally have a disordered arrangement. Arms separated by 120 degrees are less likely to fall on exactly the same token ID, but may fall on similar tokens with different IDs. This is particularly likely in the next-token probability distribution, where irrelevant tokens have probabilities close to 0, while similar tokens that are plausible as the next token have large probabilities (areas). DAST uses WordTour to place tokens with similar meanings next to one another, making arms separated by 120 degrees more likely to fall on tokens with different meanings. Since this simply reassigns vocabulary IDs in advance, exactly the same inference program can produce exactly the same marginal distribution. When samples are generated simultaneously, the only difference is that the samples are more diverse.
| Model | SmolLM2-1.7B | Qwen2.5-1.5B | Qwen2.5-3B | Qwen2.5-7B |
|---|---|---|---|---|
| 49,152 | 151,936 | 151,936 | 152,064 |
Table 1: Vocabulary sizes of the models.
| One-time | Common | Sampling overhead | ||||
|---|---|---|---|---|---|---|
| Model | (Order construction) | (Forward pass, etc.) | i.i.d. | token ID | DAST | DAST i.i.d. |
| SmolLM2-1.7B | 21.3 s | 503 s | 8.6 s | 10.1 s | 10.5 s | 1.9 s |
| Qwen2.5-1.5B | 83.5 s | 530 s | 8.5 s | 9.9 s | 10.3 s | 1.8 s |
| Qwen2.5-3B | 105.6 s | 764 s | 8.6 s | 10.0 s | 10.6 s | 2.0 s |
| Qwen2.5-7B | 228.0 s | 1,215 s | 8.9 s | 10.4 s | 10.9 s | 2.0 s |
Table 2: The two types of overhead in DAST. “One-time” is the time required to construct the vocabulary order (nearest-neighbor search, tour construction, and 2-OPT combined), which can then be reused for all subsequent generations. The remaining columns show the time required to generate one token. “Common” denotes operations independent of the sampling method, such as the forward pass. DAST’s per-generation overhead relative to i.i.d. sampling is about 2 microseconds, less than 0.4% of the forward-pass time. Measurements were taken on an NVIDIA RTX PRO 6000 Blackwell GPU and an AMD EPYC 9534 CPU.
| Model | Standard vocabulary IDs | DAST | Held–Karp lower bound | DAST / lower bound |
|---|---|---|---|---|
| SmolLM2-1.7B | 212,363 | 151,905 | 148,736 | 2.13% |
| Qwen2.5-1.5B | 203,768 | 148,881 | 145,729 | 2.16% |
| Qwen2.5-3B | 223,011 | 163,290 | 159,730 | 2.23% |
| Qwen2.5-7B | 169,399 | 146,950 | 145,173 | 1.22% |
Table 3: Objective values ( 1 ) of the vocabulary orders (lower is better). The “Held–Karp lower bound” is a rigorous lower bound obtained from the dual problem; the true optimum is at least this value. Thus, the gap between DAST and the true optimum is bounded above by the “DAST / lower bound” column.
| Model | Standard ID | DAST |
|---|---|---|
| SmolLM2-1.7B | ␣Rim ␣equates ␣streaks ␣pharmacists "... Luck dialog jas ␣REG ␣Ngu ␣mixer ␣Jesuits | ␣exceedingly ␣extremely ␣incredibly ␣exceptionally ␣extraordinarily ␣extraordinary ␣remarkable ␣incredible ␣amazing ␣astounding ␣astonishing ␣startling |
| Qwen2.5-1.5B | .DB ␣popularity ␣gew ␣impr setValue FLAG max ␣bake wy ␣Economic ␣encontr ␣fname | ␣huge ␣enormous ␣immense ␣tremendous ␣tremendously ␣immensely ␣enormously ␣hugely ␣greatly ␣vastly ␣radically ␣drastically |
Table 4: The models’ standard token ID orders and the token orders produced by DAST. Only selected segments are shown. The standard orders are completely disordered, whereas WordTour places similar tokens in contiguous segments.
Figure 3: Quantitative results on ProtoQA. A positive orange bar on the left indicates that DAST outperforms i.i.d. sampling. A positive green bar in the middle indicates that arithmetic sampling outperforms i.i.d. sampling. An orange bar on the left that is higher than the green bar in the middle, as well as a positive blue bar on the right, indicates that DAST outperforms arithmetic sampling. Error bars show 95 percent confidence intervals.
Figure 4: Example answers from Qwen2.5-0.5B-Instruct, a smaller model used here for illustration, to the ProtoQA question “name a day of the year when most people call home.” The figure uses the actual token orders and arc lengths proportional to the output probabilities. In the standard token order, christmas and Christmas are far apart, and two arms of arithmetic sampling hit these two tokens, making the first tokens of the answers Christmas, christmas, Halloween. In DAST, the Christmas and christmas tokens are close together and are therefore not selected simultaneously; the first tokens of the outputs are christmas, Thanksgiving, Mother.