This paper has been received by the EMNLP 2026 Main Conference. The first author of the paper is Dr. Dong Yao, PhD student at the Institute of Statistics and Big Data of the People's University of China.
In a single decoding step, the big language model faces not the only answer, but a set of candidate tokens with different probabilities. In order to enhance decoding diversity, existing methods often do not follow a greedy selection strategy but instead predict the next step from probability distribution sampling. To avoid sampling to extremely small probability tokens, common methods such as Top-p, Min-p, are used to cut candidate sets based on probability and then sample from the remainder.
These methods are simply effective, but one problem is ignored: high-probability tokens do not necessarily bring new information to the candidate set. Multiple high-probability tokens may be highly similar in meaning, but only different expressions of the same generating path. They are retained at the same time if selected only by probability; while a slightly lower probability, but offering different semantic directions, tokens may instead be pre-intercepted.
Mahalanobis-Ensemble Decoding (ME-Decoding), proposed by a team of researchers at the Chinese People's University of Davenport and a team of researchers at the People's University of China, transcribes the selection of candidate tokens in decoding as a dynamic set optimization problem. The method simultaneously reads model probabilities and token embedding, looking for higher confidence at each generation step, lower internal redundancy sampling support. In the three models measured, the results of the three temperature settings, ME-Decoding achieved the best average performance in the method compared to the logic open generation tasks; in end-to-end GPU testing, the comparatively fastest probability cut-off baseline delay increased by only about 3% overall.
Left: Probability interrupts are decided based solely on individual tokens. Right:ME-Decoding simultaneously uses token probability and embedding similarities to select a subset of candidates with higher overall information.
Beyond Truncation: Rethinking LLM Decoding as Ensemble Pruning
Address of the paper:https://arxiv.org/abs/2609.18723
The code address is:https://github.com/sapphirexdy/ME_decoding
What is ME-Decoding?
ME-Decoding looks at candidate tokens as an integrated member that needs to be cut: both focusing on the probability of an individual candidate and examining its semantic relationships with other candidates. The method can be broadly generalized into three steps.
Step 1: Use the Mahalanobis-Ensemble Score to measure both probability and redundancy
The candidate subset is
The corresponding probability vector is
The similarity matrix of tokens is
The paper first defines Mahalanobis-Ensemble Energy:
MEE incorporates candidate probability and semantic relationships into the same set of scores: probability reflects the model's confidence in the candidate, and the similarity matrix reacts to the semantic relationship between the candidate. Intuitively, the candidate we want to retain is both more likely to add to the information that the current set has not yet covered.
In order to decide how many candidates to retain at the same time, the paper further introduces the scale of punishment that changes with the current distribution uncertainty, given the Mahalanobis-Ensemble Score:
Molecules measure the combined contributions of a candidate set, and the dividend constrains the size of the set. MES is only improved when the gains from new candidates are sufficient to offset the scale punishment. Therefore, ME-Decoding assesses the quality of the entire subset and decides whether to continue to expand the candidate set accordingly.
Step 2: Draw local semantic structures with a custom kernel
ME-Decoding uses consolidated token embedding to construct a Gaussian resemblance core:
Among them,
Measuring the semantic distance and bandwidth of two tokens
It determines how far the candidate will remain relevant. ME-Decoding calculates this bandwidth according to the degree of probability-weighted semantic dissociation of the current candidate distribution.
The more centralized the semantic distribution of the candidate, the smaller the bandwidth, the more localized the range of focus of the nuclear function; the more distributed the distribution, the larger the bandwidth, and the more distant the semantic relationships will also be incorporated into the score. Thus, each step of the candidate selection can use a semantic scale that corresponds to the current distribution.
Step 3: Gradually expand the candidate pool and automatically determine the size of the pool
Combined searches across all token subsets are difficult to use for decoding each token. Therefore, ME-Decoding starts with the highest probability token and each round of selection results in the candidate with the largest marginal MEE gain; if the MES continues to rise after joining, the set is expanded or immediately stopped and retains the current set. Once the candidate is identified, the original probability of the token within the set is reconciled and a token is taken from it.
This process does not require a predetermined number of retained tokens, but automatically determines the size of the set based on each step's probability distribution and semantic relationship. In actual decoding, the final set is usually small; combined with prior stops, the calculation is nearly linear to the size of the candidate pool.
Test results and analysis
The paper evaluates reasoning and open generation on Qwen3-4B, Phi-4-mini and Mistral-7B, and compares it with methods such as Min-p, p-less, Top-H, Top-W.
Reasoning task: stability at different temperatures
On GSM8K and GPQA, the paper compared the three models to reasoning accuracy at T = 1.0, 1.5, and 2.0.
It's the first time I've ever been in a situation like this.
ME-Decoding has an average accuracy of 72.66% and 32.96% respectively for the two datasets, the highest value in the comparison method. Particularly in the high-temperature setting of GSM8K, some of the probability interception methods have significantly degraded, while ME-Decoding still maintains a higher accuracy rate, reflecting cross-model, cross-temperature reasoning stability.
Open generation: instructions to follow and dialogue
Under the evaluation of DeepSeek-V4-Pro as a review model, ME-Decoding achieved the highest average win rate and average scores on the AlpacaEval and MT-Bench respectively. This suggests that candidate selection based on aggregate quality can also improve the quality of instructions followed in open generation with multi-round conversations.
On the left, the average AlpacaEval win rate and MT-Bench score for three models at different temperatures, respectively; on the right, the lower the numerical value, the better the overall average ranking for all models, temperatures and tasks.
Further analysis: Is the performance improvement only due to changes in candidate cluster size or sample size?
The paper matches the probability method with ME-Decoding's average support set size, cross-sectional resemblance and resemblance of the two strings within the support set, respectively, and compares the rational performance of these conditions with the aggregate score when they are approximately consistent.
After matching, ME-Decoding still achieved the highest accuracy on GSM8K and GPQA, while maintaining the highest MES and lowest semantic similarity. This result supports its advantage from MES's joint assessment of probability and semantic redundancy, rather than merely reducing the support set, reducing the sample size, or reducing the resemblance of the mean string.
Theoretical behaviour and actual costs
The paper provides sufficient conditions and approximate assurances for the ambitious MES trajectory single peak. In the early shutdown mechanism experiments, both the GSM8K and GPQA logical trajectories were single peaked, supporting the actual performance of this stop rule in the measured settings.
In terms of efficiency, ME-Decoding is about 3 to 7 times faster than Top-W in synthetic CPU benchmarks; in end-to-end GPU testing, the total latency for the fastest baseline relative to probability-based intercepts increases by only about 3%, accounting for only a fraction of the model's forward-looking costs.
Summary
ME-Decoding offers a different perspective from traditional decoding: LLM decoding can be understood as a dynamic set optimization problem in addition to marking thresholds on the probability distribution. Overall, the work has three characteristics:
First, redefine the token selection problem. It looks at the candidate token as an integrated member to be cut, and extends the single-point probability selection to the collective-level joint selection.
Second, the combined use of confidence and semantic geometry. While maintaining the high-probability candidate, MES contributes to the semantic direction of the adjustment that has been covered by the current collection to obtain more compact, more informative sampling support.
Third, efficiently adapt to the current distribution. The bandwidth of the semantic kernel changes with each step in the candidate distribution, greedy searches stop automatically when the MES is no longer upgraded, and controls the size and computational expenses of the candidate collection.
At the heart of ME-Decoding is: when selecting a candidate token, it takes into account both the probability of a single candidate and the semantic redundancy between the candidates to decide which candidates to retain from a collective level. Experiments show that this view improves the average performance of the measured task and remains stable at different temperatures.