Beyond Truncation: Rethinking LLM Decoding as Ensemble Pruning Dunyao Xue1 , Chengshuo Du1 , Zhengbo Wang1 , Wenlin Dai1,2,† , Cheng Meng1,3,† 1
Institute of Statistics and Big Data, Renmin University of China, Beijing, China Big Data and Responsible Artificial Intelligence for National Governance, Renmin University of China, Beijing, China 3 Center for Applied Statistics, Institute of Statistics and Big Data, Renmin University of China, Beijing, China {xuedunyao1202,duchengshuo,zhengbowang,wenlin.dai,chengmeng}@ruc.edu.cn
Abstract We introduce Mahalanobis-Ensemble Decoding (ME-Decoding), a novel Large Language Model (LLM) decoding framework that frames candidate token selection as ensemble pruning. Existing selection strategies rely predominantly on scalar probabilities, ignoring geometric semantic relationships and causing candidate redundancy. Meanwhile, current geometry-aware methods often require complex optimization or directly reweighting the original token probabilities, leading to significant computational overhead or inference instability. To address this, we formulate decoding as a subset optimization problem using a Mahalanobis distancedriven objective to enhance semantic diversity while preserving high probabilities. Specifically, we dynamically discount redundant generation paths using a token similarity matrix, constructed via an adaptive-bandwidth kernel over token embeddings. We further devise an efficient greedy selection algorithm with nearlinear complexity in the candidate size under early stopping, while establishing its theoretical approximation guarantees. This renders MEDecoding a robust, plug-and-play module with negligible inference overhead. Extensive experiments across diverse reasoning and generation tasks demonstrate that our method consistently achieves strong performance.
arXiv:2609.18723v1 [cs.AI] 16 Sep 2026
2
1
Introduction
Large Language Models (LLMs) have demonstrated strong capabilities in mathematical reasoning, instruction following, and open-ended generation (Brown et al., 2020; Touvron et al., 2023; Chowdhery et al., 2023; OpenAI, 2023). Besides model scaling and post-training alignment, the inference-time decoding strategy also plays a crucial role in determining generation quality. At each step, an autoregressive LLM produces a next-token †
Corresponding authors.
distribution, from which the decoder selects or samples the next token. Deterministic methods such as greedy decoding and beam search (Holtzman et al., 2020) favor high-probability continuations but often produce repetitive or overly conservative outputs. Sampling-based methods introduce stochasticity and improve generation diversity, but they may also assign non-negligible probability to low-quality tokens, increasing inference uncertainty and potentially leading to illogical continuations or hallucinations. To control this quality–diversity trade-off, many decoding methods perform probability-based truncation and reshaping of the next-token distribution. Classical approaches such as Top-k and nucleus sampling restrict sampling to high-probability tokens (Fan et al., 2018; Holtzman et al., 2020), while later methods such as Min-p, entropy-aware sampling, and p-less adapt the truncation rule according to model confidence or distributional statistics (Hewitt et al., 2022; Nguyen et al., 2025; Tan et al., 2026). Despite their effectiveness, these methods mainly operate on token probabilities and treat candidates as independent categorical outcomes. As a result, they overlook the semantic geometry among tokens, which may retain redundant candidates and limit the effectiveness of the selected sampling support (Yang et al., 2026). Although recent geometry-aware methods incorporate token-space structure, they continue to face significant challenges. For example, Top-W formulates a Wasserstein-regularized distributionmatching problem (Davoodi et al., 2026), which requires approximating the Wasserstein objective and careful hyperparameter tuning, while not explicitly optimizing redundancy within the selected token support. Alternatively, CraEG penalizes tokens in crowded regions via a lightweight reweighting mechanism (Yang et al., 2026). However, the approach still relies on an auxiliary decoding method for post-processing, making its behavior dependent
Table 1: Comparison of different decoding methods. Method
Decoding Geometry Adaptive Redundancy Strategy Aware1 Selection Control2
Greedy Top-k Min-p p-less Top-W CraEG
Determin. Prob. Trunc. Prob. Trunc. Prob. Trunc. Dist. Match. Reweighting
✗ ✗ ✗ ✗ ✓ ✓
✗ ✗ ✗ ✓ ✓ ✗
✗ ✗ ✗ ✗ ✗ ✓
Ours
Ensemble
✓
✓
✓
mative candidate set while preserving token probabilities. • We devise an efficient greedy selection algorithm with candidate-linear complexity under early stopping, while establishing its trajectory unimodality and theoretical approximation guarantees. • Extensive experiments across diverse reasoning and generation tasks show that our method consistently outperforms strong existing baselines.
1
Embedding Geometry: Uses token embedding geometry in the decoding process. 2 Redundancy Control: Explicitly controls redundancy among candidate tokens.
on the properties of the downstream method. These limitations motivate our key question: How can we design a simple and efficient framework that selects a compact yet informative token set while preserving high-confidence candidates? In this work, we address this question from the perspective of ensemble pruning, a paradigm that entails selecting a compact subset of learners from a larger pool to optimize predictive outcomes. This paradigm closely mirrors the token selection problem in LLM decoding. Extensive research in ensemble learning shows that effective ensembles should balance individual accuracy with collective complementarity (Krogh and Vedelsby, 1994; Opitz and Maclin, 1999). Consequently, simply selecting the highest-scoring learners may introduce redundancy and hurt overall performance (Zhou et al., 2002; Li et al., 2012). Similarly, LLM decoding encounters an analogous challenge of token redundancy. Building on this insight, we introduce ME-Decoding, a novel framework that incorporates token geometry to reformulate decoding as a subset maximization problem driven by the Mahalanobis distance. By approximately solving this objective with an efficient greedy procedure, ME-Decoding mitigates redundancy within the selected token set during generation with negligible inference overhead, thereby improving token selection quality while maintaining reasoning performance. Our contributions are summarized as follows: • We reformulate LLM decoding through the novel lens of ensemble pruning. • We define a Mahalanobis distance-driven objective to adaptively select a compact, infor-
2
Motivation
2.1
Background of LLM Decoding
Large Language Models (LLMs) generate text autoregressively by predicting the next token from the preceding context. At each step, an LLM outputs a probability distribution P ∈ ∆|Ω|−1 over the full vocabulary Ω. To avoid sampling from the unreliable long tail, modern decoding methods usually first form a candidate pool Vt ⊆ Ω, then select a final subset S ⊆ Vt and sample from the renormalized distribution: pi 1{i ∈ S} pS (i) = P . j∈S pj This process can be viewed as a subset selection problem aiming to preserve the original distribution under a probability-based criterion: S ⋆ = arg min f (pS ), S⊆Vt
s.t.
S = {i : pi ≥ τ (P)},
where f (·) denotes a generalized decoding objective and τ (P) is a probability-based truncation threshold. Most prevailing decoding methods follow this probability-driven paradigm. Top-k and nucleus sampling truncate the distribution using fixed probability or cumulative-mass thresholds, while adaptive methods such as p-less and entropy-aware sampling adjust the threshold based on distributional statistics. Despite different truncation rules, these methods remain probability-centric and treat candidate tokens as independent outputs. They therefore overlook semantic dependencies among tokens, motivating us to incorporate inter-token semantics into the subset selection objective.
(a) Probability-based Truncation Renormalized Prob
p (token) 0.32 0.30 0.24
x1
(b) ME-Decoding
p (token)
MES Computation
0.32 0.30 0.24
x1
MES = 0.57 x1 x2 x3
0.07 0.04 0.01
Probability-based Threshold
p = 0.37
0.07
p = 0.35
⋮
x3
MES = 0.41 x1 x3
x2 x3 x4
0.04 0.01 x5 x6 ...
x2
p (token)
p = 0.28
x1
0.32 0.30
p = 0.51
0.24
MES = 0.62 x1 x3 x4
x1 x2 x3 x4 x5 x6 ...
Renormalized Prob
x3 0.07 x1
x2 x3
x4
0.04 0.01 x5 x6 ...
p = 0.38 x4 p = 0.11
Similarity Matrix K
Figure 1: Comparison between probability-based truncation methods (left) and our ME-Decoding framework (right). ME-Decoding extends standard probability-only token selection by incorporating embedding-based similarity into the MES score and selecting a compact geometry-aware subset for sampling.
2.2
Connection to Ensemble Pruning
Ensemble pruning aims to select a compact subensemble that preserves or improves the predictive performance of the full ensemble. Classical error analysis (Breiman, 2001) characterizes ensemble performance as a trade-off between individual accuracy and inter-model diversity. Following this idea, Zhang et al. (2006) formulate pruning as a quadratic subset-selection problem. Given a binary error indicator matrix E, they construct the error co-occurrence matrix C = E ⊤ E, where diagonal entries measure individual errors and off-diagonal entries measure shared failures. After normalization, the pruning objective can be written as b min s⊤ Cs s
s.t.
X
si = N, si ∈ {0, 1}. (1)
i
This objective selects a size-N sub-ensemble by jointly penalizing individual inaccuracy and pairwise redundancy. This paradigm naturally parallels token selection in LLM decoding. Candidate tokens can be viewed as ensemble members: their probabilities measure individual confidence, while their embeddingspace similarities measure semantic redundancy. Therefore, an ideal decoding subset should retain high-likelihood tokens while suppressing redundant candidates, mirroring the accuracy–diversity trade-off in ensemble pruning. 2.3
Generalizing Ensemble Pruning to LLM Decoding via Mahalanobis Distance
The quadratic objective in Eq. 1 leverages secondorder statistics to penalize redundant candidates. Motivated by this, we aim to extend this diversityaware framework to LLM decoding. To achieve
this, we observe that for any representation vector p and a symmetric positive definite matrix, this quadratic structure naturally corresponds to the Mahalanobis distance. In machine learning, the Mahalanobis distance is widely used to construct discriminative representations, such as in metric learning, out-of-distribution detection, and representation regularization (Weinberger and Saul, 2009; Lee et al., 2018; Wan et al., 2018; Kang et al., 2026). Formally, given two vectors x, y ∈ Rd and a symmetric positive definite matrix M ≻ 0, it is defined as q DM (x, y; M ) := (x − y)⊤ M −1 (x − y). In particular, setting y = 0 and letting M be the token similarity matrix K gives the Mahalanobis norm p ∥x∥K := x⊤ K −1 x. Mathematically, by explicitly incorporating the inverse matrix K −1 , the Mahalanobis norm inherently downweights correlated directions and separates information along non-redundant axes. This geometric property aligns perfectly with our overarching goal: to suppress repetitive generation paths and enhance token diversity during decoding.
3
Method: ME-Decoding
In this section, we propose Mahalanobis-Ensemble Decoding (ME-Decoding), a geometry-aware decoding framework inspired by ensemble pruning. ME-Decoding selects a compact token subset by optimizing a Mahalanobis-style objective that combines token probabilities with embedding-based similarities. The overall structure of ME-Decoding is illustrated on the right side of Figure 1.
3.1
3.2
Mahalanobis-Ensemble Score.
Inspired by ensemble pruning, we view the candidate tokens at each decoding step as a pool of weak semantic predictors. Instead of retaining a fixed number of high-probability tokens, our goal is to construct a compact token ensemble that preserves high-confidence candidates while reducing redundancy in the token embedding space. At each decoding step, ME-Decoding is applied to a probability-based candidate pool Vt ⊆ Ω; for simplicity, we omit t and write V hereafter. We first define the Mahalanobis-Ensemble Energy (MEE) for a selected token subset S ⊆ V as −1 MEE(S) = p⊤ S K S pS , where pS denotes the vector of token probabilities indexed by S, and K S is the token similarity matrix restricted to S. The inverse matrix K −1 S discounts redundant tokens and rewards subsets with high collective quality. However, unlike standard ensemble pruning, the optimal subset size in decoding is unknown a priori. This requires us to maximize the MEE of the selected tokens while avoiding unnecessarily large subsets, thereby filtering out redundant tokens that contribute only marginally to the overall MEE. To this end, we define the Mahalanobis-Ensemble Score (MES) as follows: MEE(S)
|S| , 1 + λH2T (p) P where H2T (p) = 1 − i∈V p2i is the order-2 Tsallis entropy measuring the uncertainty of the nexttoken distribution, and λ > 0 controls the entropydependent size penalty. Intuitively, the numerator rewards tokens with large non-redundant contributions, while the denominator discourages excessive subset expansion. When the distribution is flat, the unregularized MEE may keep increasing by accumulating weak marginal gains from many uncertain candidates. The entropy-dependent penalty raises the inclusion threshold, retaining only tokens with sufficiently large non-redundant contributions. Consequently, the decoding objective is given by: MESλ (S) =
S ⋆ = arg max MESλ (S). S⊆V
(2)
By optimizing the MES, we can effectively extract a highly representative token subset from the candidate distribution.
Construction of Similarity Matrix
To measure token similarity in the embedding space while maintaining numerical stability, we construct K using a Gaussian kernel on normalized token embeddings. Let ei ∈ Rd denote the normalized embedding of token i. We define Cij = 1 − e⊤ i ej ,
Kij = exp{−Cij /ϵ}. (3)
Here, Cij measures the semantic distance between tokens, and ϵ > 0 is a bandwidth parameter controlling the smoothness of the kernel. In our implementation, the bandwidth ϵ is chosen adaptively according to the probability-weighted semantic dispersion of the candidate tokens: ϵ=
1 X pi pj Cij , 2 i,j∈V
P where i,j∈V pi pj Cij is the expected pairwise semantic distance between tokens sampled from the candidate distribution. When the candidate tokens are semantically concentrated, the adaptive bandwidth becomes smaller, yielding a localized kernel and making the selection more probability-driven. Conversely, when the candidates are semantically dispersed, the bandwidth becomes larger, preserving semantic relations over a broader range and making the selection more geometry-aware. Thus, the adaptive bandwidth balances probability and semantic structure according to the local geometry of the decoding distribution. 3.3
Optimization Strategy
Directly solving the maximization problem formulated in Eq. 2 is an NP-hard combinatorial task. To maintain computational feasibility, we use a greedy forward-selection procedure and maintain the inverse Cholesky factor of K −1 S incrementally (Golub and Van Loan, 2013), which avoids repeated matrix inversions during subset construction. The greedy selection in Algorithm 1 is conceptually related to Orthogonal Matching Pursuit (OMP) (Pati et al., 1993). At each step, (pj − α⊤ j z) represents the conditional residual score of token j after accounting for its correlation with the selected tokens, while rj normalizes it by the corresponding conditional variance. The marginal contribution h i2 is therefore measured by rj (pj − α⊤ z) . The j algorithm selects the token with the largest contribution and accepts it only when the penalized MES
Algorithm 1 Greedy Algorithm for ME-Decoding Candidate token pool V with N = |V|; candidate token scores p ∈ RN ; normalized candidate token embeddings E = [e1 , . . . , eN ]⊤ ∈ RN ×d ; MES penalty λ. 2: Initialize S = ∅. 3: Set cλ ← 1 + λH2T (p). 4: Select the first token j1 = arg maxi pi and update S ← {j1 }. 5: Compute K S,S using Eq. 3. 1/2 z ← RpS . 6: R ← (K S,S )−1 , 1: Input:
|S|
7: MESg ← ∥z∥22 /cλ . 8: for t = 1 to N − 1 do 9: 10: 11: 12: 13: 14: 15: 16: 17: 18: 19: 20: 21: 22: 23:
for j ∈ {1, . . . , N } \ S do Compute β j ← [Kij ]i∈S using Eq. 3, and set bj ← K jj . αj ← Rβ j , rj ← (bj − ∥αj ∥22 )−1/2 . Compute the MEE after adding token j: h i2 cj ← ∥z∥22 + rj (pj − α⊤ z) . j end for ⋆ Select j⋆ = arg maxj ∈S / cj , let c = cj⋆ . Compute the candidate MES score: |S|+1 MESgcand ← c⋆ /cλ . if MESgcand ≤ MESg then break end if R ⊤ α j⋆ . γ ← −rj⋆ vj⋆ ← rj⋆ pj⋆ − α⊤ j⋆ z . Update R and z: R 0 z R← ⊤ , z← . v j⋆ γ rj⋆
Theorem 3.1 (Greedy Unimodality of Mahalanobis-Ensemble Decoding). Let |V| = N and MESgt = MESλ (St ), where {St }N t=0 is the greedy path generated by Algorithm 1. For any T ⊆ V, let K T = (Kij )i,j∈T and define κN (K) = (K T ) maxT ⊆V, |T |≤N λλmax . If κN (K) ≤ 1 + min (K T ) T λH2 (p), once for some t < N , MESgt+1 ≤ MESgt , then for all s ≥ t, MESgs+1 ≤ MESgs . Consequently, with τ = min{t : MESgt+1 ≤ MESgt }, we have MESgτ = max MESgr . 0≤r≤N
Theorem 3.1 justifies the early stopping rule in Algorithm 1: the greedy search can terminate once the MES score drops, without traversing all candidates. Appendix B.3 complements this sufficient-condition result by disabling early stopping and recording complete greedy trajectories on Qwen2.5-1.5B. All 512 trajectories on each of GSM8K and GPQA are unimodal, providing empirical support for the stopping behavior characterized by Theorem 3.1. The next theorem compares the stopped greedy value with the global optimum, showing that it provides an effective approximation to the optimal subset. Theorem 3.2 (Approximation Guarantee for Mahalanobis-Ensemble Decoding). Let MES⋆λ = max MESλ (S), S⊆V
24:
S ← S ∪ {j⋆ },
25: end for 26: Output: Selected token set S.
objective improves, favoring high-probability tokens while discounting redundant candidates. 3.4
|V| = N.
MESg ← MESgcand . Let {St }N t=0 be the greedy path generated by Algorithm 1, and let τ be the stopping time defined in Theorem 3.1. Under the assumptions of Theorem 3.1, we have MESgτ ≥ (1 − exp{−λmin (K, N )}) MES⋆λ ,
Theoretical Properties
Furthermore, to rigorously validate the effectiveness of our proposed strategy, we establish theoretical properties of the greedy algorithm, showing its unimodality along the search path and deriving an approximation bound to the global optimum. The following theorem states that, under a conditioning assumption on the token-similarity matrix, the greedy MES sequence cannot increase again once it stops increasing.
where λmin (K, r) ≜ minT ⊆V, |T |=r λmin (K T ) denotes the smallest eigenvalue among all r × r principal submatrices of K. Theorem 3.2 establishes the relation between the optimal greedy value and the globally optimal MES value. The approximation factor depends on the restricted minimum eigenvalue of K, which reflects the non-redundancy and conditioning of the selected token representations.
Qwen3-4B-Inst.
Phi-4-mini-Inst.
Mistral-7B-Inst.
Method
T = 1.0
T = 1.5
T = 2.0
T = 1.0
T = 1.5
T = 2.0
T = 1.0
T = 1.5
T = 2.0
Avg.
Min-p Top-p p-less Top-H Top-W Ours
70.74 68.01 78.92 76.80 77.71 80.67
62.02 55.19 72.71 67.17 76.65 79.76
54.06 21.00 63.15 58.53 74.98 80.06
79.68 80.06 84.05 81.65 82.64 84.08
70.81 11.75 83.09 73.77 83.24 84.23
30.86 0.30 69.52 34.65 82.18 82.41
48.67 48.90 54.06 52.01 53.98 55.34
36.32 23.05 50.80 46.78 53.15 53.45
17.97 0.45 46.47 22.52 51.02 53.90
52.35 34.30 66.97 57.10 70.62 72.66
Table 2: GSM8K accuracy (%) across different temperatures and decoding methods. The Avg. column reports the average accuracy over all models and temperatures. The best result is in bold and the second best is underlined. Qwen3-4B-Inst.
Phi-4-mini-Inst.
Mistral-7B-Inst.
Method
T = 1.0
T = 1.5
T = 2.0
T = 1.0
T = 1.5
T = 2.0
T = 1.0
T = 1.5
T = 2.0
Avg.
Min-p Top-p p-less Top-H Top-W Ours
34.38 34.60 35.27 34.38 34.82 35.49
32.59 35.49 34.82 33.93 36.83 35.49
35.04 30.58 35.49 34.15 35.27 35.71
27.01 31.25 33.26 34.38 31.70 34.38
29.02 27.01 33.26 33.93 29.46 36.16
26.56 15.40 27.90 29.91 31.47 33.93
26.12 25.89 27.68 28.12 27.23 28.35
28.12 26.41 27.01 27.23 29.02 28.79
25.22 14.06 24.78 23.88 28.23 28.35
29.34 26.74 31.08 31.10 31.56 32.96
Table 3: GPQA accuracy (%) across different temperatures and decoding methods. The Avg. column reports the average accuracy over all models and temperatures. The best result is in bold and the second best is underlined.
4
Experiments
4.1
Experimental Details
Models and Baselines. We evaluate MEDecoding on three instruction-tuned language models: Qwen3-4B-Instruct (Yang et al., 2025), Phi4-mini-Instruct (Abouelenin et al., 2025), and Mistral-7B-Instruct (Jiang et al., 2023). We compare our method with several representative decoding methods, including Min-p (Nguyen et al., 2025), Top-p (Holtzman et al., 2020), p-less (Tan et al., 2026), Top-H (Baghaei Potraghloo et al., 2025), and Top-W (Davoodi et al., 2026). For a fair comparison, all methods are evaluated under the same prompts, temperature settings, maximum generation length, and stopping criteria. Unless otherwise specified, we evaluate all methods at temperatures T ∈ {1.0, 1.5, 2.0}. All reported experiments use N = 512. We additionally implement CraEG (Yang et al., 2026) and combine its post-softmax reweighting with p-less, following its plug-in formulation. Repeated results for selected methods are reported in Appendix B.1. Benchmarks and Metrics. We consider two types of tasks. First, for reasoning benchmarks, we evaluate on GSM8K (Cobbe et al., 2021) and GPQA (Rein et al., 2024), where performance is measured by answer accuracy after extracting the final answer. These benchmarks test whether a de-
coding method can maintain reliable reasoning performance under different sampling temperatures. Second, for instruction-following and chat-style generation, we evaluate on AlpacaEval (Li et al., 2023) and MT-Bench (Zheng et al., 2023). For AlpacaEval, we report the candidate win-rate (%), and for MT-Bench, we report the average judge score. Since these tasks involve open-ended generation, we use DeepSeek-V4-Pro (DeepSeek-AI, 2026) as the judge to compare the generated responses under a fixed evaluation protocol. For reproducibility, AlpacaEval compares each response with a fixed reference for the same prompt, whereas MT-Bench independently scores each response on a 1–10 scale. Appendix B.7 reports an additional evaluation using GLM-5.2 as a second judge, together with paired prompt-level bootstrap confidence intervals. ME-Decoding Configuration. ME-Decoding selects a compact token subset by optimizing a Mahalanobis-style objective that balances token probability and embedding geometry. For TopW and ME-Decoding, both of which require an explicit candidate pool, we use the same top-N pool with N = 512. Except for the candidate-pool size, Top-W uses its default hyperparameters. Top-p, Min-p, and Top-H follow Davoodi et al. (2026), and p-less is evaluated under its original parameter-free rule. ME-
Decoding uses λ = 0.9 by default, following Appendix B. The official implementation is available at https://github.com/sapphirexdy/ME_decoding. Temperature Placement. At temperature T , every method operates on the same distribution pT = softmax(z/T ). ME-Decoding uses pT for candidate scoring and samples from the renormalized selected support, while each baseline applies its truncation or reweighting rule to the same temperatureadjusted distribution. 4.2
Main Results
Reasoning Benchmarks. We first evaluate MEDecoding on GSM8K and GPQA across three models and three temperatures. The results are reported in Tables 2 and 3. Overall, ME-Decoding achieves the best average performance across both datasets. Appendix B.1 reports three-seed repetitions as mean ± sample standard deviation and includes CraEG combined with p-less following its plug-in formulation. Figure 2 further shows the accuracy–temperature curves of different decoding methods. Compared with existing baselines, ME-Decoding maintains a more stable accuracy profile as the temperature increases. Higher temperatures enlarge the sampling space, making probability-only truncation methods more prone to noisy tokens. By incorporating token geometry, ME-Decoding better preserves high-confidence candidates while filtering out uninformative ones, leading to a better balance between exploration and reasoning reliability. Instruction-following and Chat. We further evaluate ME-Decoding on instruction-following and chat-style generation tasks using MT-Bench and AlpacaEval. Experiments are conducted on Qwen3-4B, Phi-4-mini, and Mistral-7B under T ∈ {1.0, 1.5, 2.0}. Figure 3 summarizes the results. The left and middle panels report the average AlpacaEval win rate and MT-Bench score over the three models at each temperature, while the right panel presents the overall average rank across all models, temperatures, and benchmarks. Detailed numerical results are provided in the Appendix. As shown in Figure 3, ME-Decoding achieves strong performance on both open-ended benchmarks. It obtains the best averaged AlpacaEval win rate and MT-Bench score. The overall rank comparison further shows that ME-Decoding attains the best average rank among all compared decoding methods, indicating its stable advantage across
models, temperatures, and benchmarks. These results suggest that ME-Decoding is not limited to accuracy-oriented reasoning tasks, but also improves open-ended generation by selecting a compact and informative token set. The same conclusion holds under a second automatic judge. Paired prompt-level bootstrap intervals against Top-W , pless, and Top-H are positive for both benchmarks and both judges, as reported in Appendix B.7. 4.3
Analysis
Complexity Analysis. We analyze the time complexity of ME-Decoding in Algorithm 1. Let N be the candidate-pool size, d the embedding dimension, and τ the number of selected tokens before early stopping. The kernel computation costs O(N τ d), and the greedy evaluation costs O(N τ 3 ), 2 leading to O N τ (d + τ ) . Since early stopping usually yields a small τ with τ ≪ N , the practical cost scales nearly linearly with N and approaches O(N d) when τ is treated as a small constant. A detailed analysis is provided in Appendix B.4. Efficiency Analysis. To compare inference-time efficiency, we use a CPU-only synthetic logits benchmark that isolates sampling and logitsprocessing overhead. We measure the average time for filtering logits and sampling one token under two settings: Medium with vocabulary size 32,000, embedding dimension 256, and top-N = 512; and Large with vocabulary size 128,000, embedding dimension 1024, and top-N = 2048. All experiments use batch size 1, one CPU thread, temperature 1.0, 50 warm-up steps, and 500 measured steps over 10 repeats. Results are reported in Table 4. As shown in Table 4, ME-Decoding introduces moderate overhead compared with purely probability-based methods due to its use of token embeddings, but remains highly efficient. It is about 2.7× faster than Top-W in the Medium setting and 7.4× faster in the Large setting. In the Large setting, its overhead is also comparable to Top-p and Top-H, demonstrating that MEDecoding can exploit token-geometry information with substantially lower cost than existing geometry-aware decoding methods. Appendix B.4 additionally reports end-to-end GPU latency and shows that model inference remains the dominant cost under the measured settings. Diversity Analysis. We analyze the accuracy– diversity trade-off on GSM8K with Qwen3-4B. For each method, we randomly sample 500 questions
GSM8K
GPQA 0.37
0.85 0.75
Accuracy
Accuracy
0.34 0.60 ME-Decoding p-less Top-W Top-H Min-p
0.45
0.30 0.5
0.75
0.30
ME-Decoding p-less Top-W Top-H Min-p
0.26 1.0
1.25
1.5
1.75
2.0
0.5
0.75
1.0
Temperature
1.25
1.5
1.75
2.0
Temperature
Figure 2: Accuracy vs. temperature curves of different decoding methods on GSM8K and GPQA. AlpacaEval
MT-Bench
10
7.06 7.20 7.09 7.01 7.06 7.18 6.60 6.97 7.04 7.00 7.08 7.14
8
1.94
6
5.34 6.40 6.50 6.81 7.10 7.20 6.34 6.86 6.88 6.94 7.08 7.17
Score
10.66 13.47 13.69 14.27 14.10 14.83 13.04 14.14 14.36 14.33 14.14 14.80
14.41 14.60 14.69 14.32 14.14 15.09 14.06 14.35 14.70 14.40 14.19 14.48
Win-Rate (%)
20
15
Average Rank
10
3.14 3.47 3.61
4
3.83
5
2 5.00
0
T=1
T=1.5
T=2
Top-p
Avg.
Min-p
0 Top-H
T=1
T=1.5
p-less
Top-W
T=2
Avg.
0.0
ME-Decoding
2.5
5.0
Figure 3: Open-ended generation performance and overall ranking comparison. The left and middle panels report AlpacaEval win rate and MT-Bench score across different temperatures, averaged over three models and aggregated over 3 runs. The right panel summarizes the average rank of each decoding method across all models, temperatures, and benchmarks, with bold numbers indicating the best overall rank.
Temp T=1.0 T=1.5 T=2.0
90
85
Accuracy
and generate 10 responses per question. Accuracy is computed over all generations, and diversity is measured by Distinct-1/2 (Li et al., 2016) and SelfBLEU (Zhu et al., 2018). We further average the min-max normalized Distinct-1, Distinct-2, and 1 − Self-BLEU within each temperature as an aggregated diversity score. Figure 4 shows a clear accuracy–diversity tradeoff. More exploratory methods, such as Top-p, achieve higher diversity, especially at high temperatures, but suffer from notable accuracy degradation. In contrast, ME-Decoding consistently achieves the highest accuracy and maintains stronger reasoning performance at comparable diversity levels. This suggests that the proposed Mahalanobis-Ensemble objective improves token selection reliability by constructing a compact and informative sampling support, rather than simply increasing output randomness. Detailed results are provided in Table 14. To further test whether ME-Decoding constructs an informative geometry-aware support rather than merely truncating more aggressively, we compare
80
75
Method Min-p p-less
70
Top-H Top-p Top-W
65
ME-Decoding(λ=0.9) ME-Decoding(λ=0.8) ME-Decoding(λ=0.7)
60 0.00
0.05
0.10
0.15
Diversity
0.20
0.25
Figure 4: Accuracy–diversity trade-off on GSM8K using Qwen3-4B. Each method generates 10 responses for 500 sampled questions under each temperature.
it with probability-only controls calibrated on independent prompts to match its average support size, post-pruning entropy, or support-level pairwise cosine. At each step with |S| ≥ 2, Cos. is the mean cosine over all unordered pairs of L2-
Top-p
Min-p
p-less
Top-H
Top-W
ME-Decoding
Setting
Statistic
Large
Mean s/token 0.01407 0.00196 0.00314 0.01493 0.13337 Standard Deviation 0.00006 0.00002 0.00000 0.00009 0.00098
0.01799 0.00560
Mean s/token 0.00335 0.00054 0.00080 0.00330 0.00487 Medium Standard Deviation 0.00003 0.00001 0.00001 0.00005 0.00003
0.00179 0.00010
Table 4: Average CPU sampling overhead per token on synthetic logits. Large: vocabulary size 128K, embedding dimension 1024, top-N = 2048. Medium: vocabulary size 32K, embedding dimension 256, top-N = 512.
normalized selected-token embeddings; we then average it across eligible steps. Table 5 reports results on Qwen2.5-1.5B at T = 1.0 over three generation seeds. Dataset Method
Acc. (%)
Avg. |S| Cos. MES
GSM8K
ME-Decoding 63.20 ± 0.57 Size-matched 61.79 ± 1.26 Entropy-matched 61.79 ± 0.99 Cosine-matched 62.70 ± 0.35
1.076 1.067 1.070 1.014
0.151 0.756 0.210 0.707 0.208 0.708 0.198 0.715
GPQA
ME-Decoding 32.66 ± 1.05 Size-matched 28.47 ± 1.17 Entropy-matched 28.47 ± 1.17 Cosine-matched 29.25 ± 0.91
1.134 1.106 1.106 1.084
0.243 0.589 0.289 0.558 0.289 0.558 0.259 0.537
Table 5: ME-Decoding and approximately matched probability-only controls on Qwen2.5-1.5B at T = 1.0. Accuracy is reported as mean ± sample standard deviation over three seeds.
Across both datasets, ME-Decoding achieves the highest accuracy and MES under approximately matched support size, entropy, or pairwise cosine. This result is consistent with our design goal of selecting a high-confidence support whose members provide complementary geometric information, and supports the effectiveness of directly optimizing MES. Appendix B.6 reports the complete diagnostics, including retained probability mass and entropy before pruning. Appendix B.2 further isolates the contribution of correctly aligned token geometry using identity- and permuted-kernel controls.
5
Conclusion
In this paper, we introduce ME-Decoding, a decoding framework that reformulates LLM token selection as ensemble pruning. ME-Decoding maximizes the Mahalanobis-Ensemble Score (MES) to select a compact token subset, combining token probabilities with an embedding-based similarity matrix to discount semantic redundancy. We further develop an efficient greedy algorithm with theoretical guarantees, including greedy-trajectory unimodality and an approximation bound. Exper-
iments on reasoning and open-ended generation tasks show that ME-Decoding improves over representative probability-based and geometry-aware baselines with low inference overhead. These results demonstrate the potential of ensemble pruning as a principled perspective for constructing compact, diverse, and reliable token candidate sets. Future work includes developing simpler and more effective objectives under this perspective, and extending ME-Decoding to broader scenarios such as long-form generation, multi-sample reasoning, and verification-augmented decoding.
Limitations Although ME-Decoding introduces an ensemblepruning perspective for LLM decoding and achieves strong performance on several tasks, it still has several limitations. First, its performance depends on the construction of the similarity matrix, which controls the trade-off between token confidence and redundancy. While we provide a practical geometry-based kernel, more effective and adaptive similarity designs may further improve performance. The current kernel uses static token embeddings as a soft redundancy signal and may not capture all context-dependent semantic distinctions. Contextualized or hidden-stateconditioned kernels are therefore a useful direction for future work. Second, although ME-Decoding consistently achieves higher accuracy than competing methods under comparable diversity levels, its output diversity is not always the highest among all decoding strategies. This suggests that the current kernel construction may still be conservative in promoting diverse generations. How to further improve generation diversity while preserving the accuracy gains of ME-Decoding remains an important direction for future work. Third, determining the optimal subset size remains challenging, as in existing truncation-based decoding methods. The proposed MES criterion provides a principled selection rule, but it may not be optimal for all token
distributions. Exploring adaptive subset-size rules and alternative objectives is another promising direction.
Ethical Considerations This work proposes ME-Decoding, a geometryaware decoding framework that reformulates candidate token selection from the perspective of ensemble pruning. By selecting compact yet informative token sets, ME-Decoding aims to improve generation quality and reasoning performance without modifying model parameters or requiring additional training. A potential positive impact is that such plug-and-play inference-time methods may improve the usability of existing language models with limited computational overhead, thereby reducing deployment costs and the need for repeated model retraining. At the same time, improved decoding and reasoning performance may also amplify downstream risks associated with generative systems. These risks include misinformation generation, hallucinated but plausible outputs, biased or harmful content, and the automation of low-quality or malicious text at scale. Since ME-Decoding operates at inference time and can be applied to a wide range of pretrained language models, its broader impact depends strongly on the deployment context, access control, and downstream use cases. We encourage practitioners to use ME-Decoding together with established responsible deployment practices, including safety evaluation, bias and toxicity assessment, hallucination analysis, usage policies, and rate limits in open-ended settings. For high-stakes applications such as medical, legal, financial, or educational decision-making, model outputs should be carefully verified by qualified human experts. In addition, when ME-Decoding is applied to models trained on copyrighted, private, or sensitive data, developers should follow appropriate data governance, documentation, and licensing practices. All datasets, models, and evaluation tools used in this work are publicly available. We follow their respective licenses and terms of use, and use them solely for research evaluation purposes. Our use of these artifacts is consistent with their intended use as benchmarks, pretrained models, and evaluation tools for research. We do not redistribute or repurpose any artifact beyond the scope allowed by its original access conditions, and we cite the original
creators of all benchmarks, models, and baseline methods used in our experiments. We do not collect any new user data or personally identifying information. The datasets used in our experiments are publicly available benchmarks released for research evaluation. We use them only under their standard evaluation settings and do not attempt to identify individuals or recover private information from any dataset.
Acknowledgments This work was supported by the Outstanding Innovative Talents Cultivation Funded Programs 2026 of Renmin University of China and the National Natural Science Foundation of China under Grant No. 12571301.
References Abdelrahman Abouelenin, Atabak Ashfaq, Adam Atkinson, Hany Awadalla, Nguyen Bach, Jianmin Bao, Alon Benhaim, Martin Cai, Vishrav Chaudhary, Congcong Chen, Dong Chen, Dongdong Chen, Junkun Chen, Weizhu Chen, Yen-Chun Chen, Yi-ling Chen, Qi Dai, Xiyang Dai, Ruchao Fan, and 55 others. 2025. Phi-4-mini technical report: Compact yet powerful multimodal language models via mixture-of-LoRAs. arXiv preprint arXiv:2503.01743. Erfan Baghaei Potraghloo, Seyedarmin Azizi, Souvik Kundu, and Massoud Pedram. 2025. Top-H decoding: Adapting the creativity and coherence with bounded entropy in text generation. In Advances in Neural Information Processing Systems, volume 38, pages 28482–28513. Leo Breiman. 2001. Random forests. Machine Learning, 45(1):5–32. Tom B. Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, Sandhini Agarwal, Ariel Herbert-Voss, Gretchen Krueger, Tom Henighan, Rewon Child, Aditya Ramesh, Daniel M. Ziegler, Jeffrey Wu, Clemens Winter, and 12 others. 2020. Language models are few-shot learners. In Advances in Neural Information Processing Systems, volume 33, pages 1877–1901. Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, Parker Schuh, Kensen Shi, Sasha Tsvyashchenko, Joshua Maynez, Abhishek Rao, Parker Barnes, Yi Tay, Noam Shazeer, Vinodkumar Prabhakaran, and 48 others. 2023. PaLM: Scaling language modeling with pathways. Journal of Machine Learning Research, 24(240):1–113.
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, Christopher Hesse, and John Schulman. 2021. Training verifiers to solve math word problems. arXiv preprint arXiv:2110.14168. Abhimanyu Das and David Kempe. 2018. Approximate submodularity and its applications: Subset selection, sparse approximation and dictionary selection. Journal of Machine Learning Research, 19(3):1–34. Arash Gholami Davoodi, Navid Rezazadeh, Seyed Pouyan Mousavi Davoudi, and Pouya Pezeshkpour. 2026. Geometry-aware decoding with Wassersteinregularized truncation and mass penalties for large language models. In Proceedings of the 43rd International Conference on Machine Learning. DeepSeek-AI. 2026. DeepSeek-V4: Towards highly efficient million-token context intelligence. https://huggingface.co/deepseek-ai/ DeepSeek-V4-Pro. Technical report. Angela Fan, Mike Lewis, and Yann Dauphin. 2018. Hierarchical neural story generation. In Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 889–898. Gene H Golub and Charles F Van Loan. 2013. Matrix Computations. JHU Press.
Kimin Lee, Kibok Lee, Honglak Lee, and Jinwoo Shin. 2018. A simple unified framework for detecting outof-distribution samples and adversarial attacks. In Advances in Neural Information Processing Systems, volume 31, pages 7167–7177. Jiwei Li, Michel Galley, Chris Brockett, Jianfeng Gao, and William B Dolan. 2016. A diversity-promoting objective function for neural conversation models. In Proceedings of the 2016 conference of the North American chapter of the association for computational linguistics: human language technologies, pages 110–119. Nan Li, Yang Yu, and Zhi-Hua Zhou. 2012. Diversity regularized ensemble pruning. In Joint European conference on machine learning and knowledge discovery in databases, pages 330–345. Springer. Xuechen Li, Tianyi Zhang, Yann Dubois, Rohan Taori, Ishaan Gulrajani, Carlos Guestrin, Percy Liang, and Tatsunori B. Hashimoto. 2023. Alpacaeval: An automatic evaluator of instruction-following models. https://github.com/tatsu-lab/alpaca_eval. Nhat Minh Nguyen, Andrew Baker, Clement Neo, Allen G. Roush, Andreas Kirsch, and Ravid ShwartzZiv. 2025. Turning up the heat: Min-p sampling for creative and coherent LLM outputs. In International Conference on Learning Representations. OpenAI. 2023. GPT-4 technical report. arXiv preprint arXiv:2303.08774.
John Hewitt, Christopher D Manning, and Percy Liang. 2022. Truncation sampling as language model desmoothing. In Findings of the Association for Computational Linguistics: EMNLP 2022, pages 3414– 3427.
David Opitz and Richard Maclin. 1999. Popular ensemble methods: An empirical study. Journal of artificial intelligence research, 11:169–198.
Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, and Yejin Choi. 2020. The curious case of neural text degeneration. In International Conference on Learning Representations.
Yagyensh Chandra Pati, Ramin Rezaiifar, and Perinkulam Sambamurthy Krishnaprasad. 1993. Orthogonal matching pursuit: Recursive function approximation with applications to wavelet decomposition. In Proceedings of 27th Asilomar conference on signals, systems and computers, pages 40–44. IEEE.
Albert Q. Jiang, Alexandre Sablayrolles, Arthur Mensch, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Florian Bressand, Gianna Lengyel, Guillaume Lample, Lucile Saulnier, Lélio Renard Lavaud, Marie-Anne Lachaux, Pierre Stock, Teven Le Scao, Thibaut Lavril, Thomas Wang, Timothée Lacroix, and William El Sayed. 2023. Mistral 7b. Preprint, arXiv:2310.06825.
David Rein, Betty Li Hou, Asa Cooper Stickland, Jackson Petty, Richard Yuanzhe Pang, Julien Dirani, Julian Michael, and Samuel R Bowman. 2024. GPQA: A graduate-level google-proof q&a benchmark. In Proceedings of the First Conference on Language Modeling.
Xinlai Kang, Dunyao Xue, Zhengbo Wang, Chengshuo Du, Xinghao Chen, Hang Zhou, Hanting Chen, and Cheng Meng. 2026. Breaking the echo chamber: A dynamic ensemble pruning perspective on MoE. In Proceedings of the 43rd International Conference on Machine Learning. Anders Krogh and Jesper Vedelsby. 1994. Neural network ensembles, cross validation, and active learning. In Advances in Neural Information Processing Systems, volume 7, pages 231–238.
Runyan Tan, Shuang Wu, and Phillip Howard. 2026. p-less sampling: A robust hyperparameter-free approach for LLM decoding. In International Conference on Learning Representations. Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, Aurelien Rodriguez, Armand Joulin, Edouard Grave, and Guillaume Lample. 2023. LLaMA: Open and efficient foundation language models. arXiv preprint arXiv:2302.13971.
Weitao Wan, Yuanyi Zhong, Tianpeng Li, and Jiansheng Chen. 2018. Rethinking feature distribution for loss functions in image classification. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 9117–9126. Kilian Q Weinberger and Lawrence K Saul. 2009. Distance metric learning for large margin nearest neighbor classification. Journal of Machine Learning Research, 10(9):207–244. An Yang, Anfeng Li, Baosong Yang, Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, Chang Gao, Chengen Huang, Chenxu Lv, Chujie Zheng, Dayiheng Liu, Fan Zhou, Fei Huang, Feng Hu, Hao Ge, Haoran Wei, Huan Lin, Jialong Tang, and 41 others. 2025. Qwen3 technical report. arXiv preprint arXiv:2505.09388. Yixin Yang, Qingxiu Dong, and Zhifang Sui. 2026. Decoding in geometry: Alleviating embedding-space crowding for complex reasoning. arXiv preprint arXiv:2601.22536. Aohan Zeng, Xin Lv, Zhenyu Hou, Zhengxiao Du, Qinkai Zheng, Bin Chen, Da Yin, Chendi Ge, Chenghua Huang, Chengxing Xie, et al. 2026. Glm5: from vibe coding to agentic engineering. arXiv preprint arXiv:2602.15763. Yi Zhang, Samuel Burer, and W. Nick Street. 2006. Ensemble pruning via semi-definite programming. Journal of Machine Learning Research, 7(48):1315– 1338. Lianmin Zheng, Wei-Lin Chiang, Ying Sheng, Siyuan Zhuang, Zhanghao Wu, Yonghao Zhuang, Zi Lin, Zhuohan Li, Dacheng Li, Eric Xing, Hao Zhang, Joseph Gonzalez, and Ion Stoica. 2023. Judging LLM-as-a-judge with mt-bench and chatbot arena. In Advances in Neural Information Processing Systems, volume 36, pages 46595–46623. Curran Associates, Inc. Zhi-Hua Zhou, Jianxin Wu, and Wei Tang. 2002. Ensembling neural networks: many could be better than all. Artificial intelligence, 137(1-2):239–263. Yaoming Zhu, Sidi Lu, Lei Zheng, Jiaxian Guo, Weinan Zhang, Jun Wang, and Yong Yu. 2018. Texygen: A benchmarking platform for text generation models. In The 41st international ACM SIGIR conference on research & development in information retrieval, pages 1097–1100.
A
Proofs of Theoretical Results
−1 T Proof of Theorem 3.1. Let MEE(S) = p⊤ S K S pS and cλ = 1 + λH2 (p). Write Ft = MEE(St ) and ∆t = MEE(St+1 ) − MEE(St ). Then the greedy objective is defined as MESgt = Fctt . λ We first show that the restricted condition number controls the conditional residual correlations. Fix any subset S ⊆ V and two indices i, k ∈ / S. Define the conditional residual covariance matrix of (i, k) given S as the Schur complement:
C {i,k}|S = K{i,k} − K {i,k},S K −1 S K S,{i,k} . Write
C {i,k}|S =
vi cki|S
cki|S , vk
−1 −1 where vi = Kii − K iS K −1 S K Si , vk = Kkk − K kS K S K Sk , and cki|S = Kki − K kS K S K Si . The corresponding conditional residual correlation is
cki|S ρki|S = √ . vi vk Since C {i,k}|S is the Schur complement of K S in K S∪{i,k} , its eigenvalues are bounded by those of K S∪{i,k} . More precisely, λmin (K S∪{i,k} ) ≤ λmax (C {i,k}|S ) ≤ λmax (K S∪{i,k} ). These inequalities follow from the variational characterization of eigenvalues and the Schur-complement residualization argument. Therefore, κ(C {i,k}|S ) ≤ κ(K S∪{i,k} ) ≤ κN (K). On the other hand, for any 2 × 2 positive definite matrix vi c C= , c vk with correlation ρ = √vci vk , we have: |ρ| ≤
κ(C) − 1 , κ(C) + 1
which gives κ(C) ≥
1 + |ρ| . 1 − |ρ|
Applying this to C {i,k}|S gives 1 + |ρki|S | ≤ κ(C {i,k}|S ) ≤ κN (K). 1 − |ρki|S | By the assumption κN (K) ≤ cλ , we obtain 1 + |ρki|S | ≤ cλ . 1 − |ρki|S |
(4)
Next, we prove the one-step growth control of greedy marginal gains. Fix a greedy step t, let S = St , and let i be the element added at step t, i.e., St+1 = St ∪ {i}. For any remaining token k ∈ / S ∪ {i}, define the standardized residual scores pi − K iS K −1 S pS zi = q , −1 Kii − K iS K S K Si
and define zk analogously. By the Schur-complement formula, ∆MEE(i | S) = zi2 and ∆MEE(k | S) = zk2 . Since i is selected greedily, zk2 ≤ zi2 . If zi = 0, then all remaining marginal gains are zero and the conclusion is immediate. Otherwise, define rk = zzki , where |rk | ≤ 1. After adding i, the marginal gain of k is (zk − ρki|S zi )2 ∆MEE(k | S ∪ {i}) = . 1 − ρ2ki|S Hence (1 + |ρki|S |)2 1 + |ρki|S | (rk − ρki|S )2 ∆MEE(k | S ∪ {i}) ≤ = = ≤ cλ , 2 2 ∆MEE(i | S) 1 − |ρki|S | 1 − ρki|S 1 − ρki|S
(5)
where the last inequality follows from (4). Taking the maximum over all remaining k gives ∆t+1 ≤ cλ ∆t .
(6)
Now suppose MESgt+1 ≤ MESgt . Since MESgt = Fctt , this is equivalent to λ
Ft+1 Ft t+1 ≤ ct . cλ λ t Using Ft+1 = Ft + ∆t , we get Ft + ∆t ≤ cλ Ft . Define Rt = ∆ Ft . Then
MESgt+1 ≤ MESgt
⇐⇒
Rt ≤ cλ − 1.
(7)
Using (6), we have ∆t+1 ∆t+1 = Ft+1 Ft + ∆t cλ ∆t cλ Rt ≤ = . Ft + ∆t 1 + Rt
Rt+1 =
cλ R The function h(R) = 1+R is increasing for R ≥ 0. Therefore, if Rt ≤ cλ − 1, then
Rt+1 ≤ h(Rt ) ≤ h(cλ − 1) = cλ − 1. By induction, Rs ≤ cλ − 1 for all s ≥ t. Using (7), we obtain MESgs+1 ≤ MESgs ,
∀s ≥ t.
Finally, define τ = min{t ∈ {0, . . . , N − 1} : MESgt+1 ≤ MESgt }, the sequence increases strictly before τ and is nonincreasing after τ . Hence MESgτ = max MESgr . 0≤r≤N
This completes the proof. Lemma A.1 (Approximation Guarantee for Greedy Selection). Let f : 2U → R≥0 be a normalized (f (∅) = 0), nonnegative, monotone set function, and let OPT = max|S|≤k f (S) denote the maximum value obtained by any set of size at most k. Let S be the set selected by the Greedy algorithm. Then, the solution satisfies the following approximation guarantee: f (S) ≥ 1 − e−γU,k · OPT, (8) where γU,k is the submodularity ratio of f . Formally, γU,k is defined as the minimum ratio of the marginal gain of a set to the marginal gain of its individual elements: P x∈A (f (L ∪ {x}) − f (L)) γU,k = min . (9) f (L ∪ A) − f (L) L⊆U, A:|A|≤k, L∩A=∅ The ratio is taken over pairs (L, A) such that f (L ∪ A) > f (L); if the denominator is zero, the ratio is defined as 1.
Proof. This is the standard approximation guarantee for greedy maximization of a nonnegative monotone set function with submodularity ratio γU,k . Proof can be found in Das and Kempe (2018). While Lemma A.1 offers a general guarantee, the ratio γV,k is typically intractable. We further provide a concrete bound for our Mahalanobis-Ensemble Energy (MEE) by considering the specific objective −1 f (S) = MEE(S) = p⊤ S K S pS .
The following lemma bounds γV,k via the restricted minimum eigenvalue of the kernel matrix K. Lemma A.2 (Schur Complement Preserves the Minimum Eigenvalue). Let K ∈ Rn×n be a symmetric positive definite matrix. Write K 11 s K= , K 11 ∈ R(n−1)×(n−1) , s ∈ R(n−1)×1 , Knn > 0. s⊤ Knn Define the Schur complement K ′ = K 11 −
1 ss⊤ . Knn
Then λmin (K) ≤ λmin (K ′ ). ′ ′ n−1 such that K ′ e′ = λ′ e′ . We Proof. Let λ′1 = λ min (K ), and choose a nonzero eigenvector e ∈ R 1 ′ e 1 ⊤ ′ construct e = , where en = − Knn s e . Using the block form of K, we have: en K 11 e′ + sen Ke = . s⊤ e′ + Knn en ⊤ ′ By the definition of en , the lower block becomes s e + Knn en = 0. For the upper block, we have K 11 e′ + sen = K 11 e′ − K1nn ss⊤ e′ = K 11 − K1nn ss⊤ e′ = K ′ e′ = λ′1 e′ . Therefore, ′ ′ λ1 e Ke = . 0 ⊤ ⊤ By the Rayleigh quotient, we know λmin (K) = minx̸=0 xx⊤Kx ≤ ee⊤Ke . Since e⊤ Ke = λ′1 ∥e′ ∥22 x e and e⊤ e = ∥e′ ∥22 + e2n ≥ ∥e′ ∥22 , we can bound the quotient as follows:
λmin (K) ≤
e⊤ Ke λ′1 ∥e′ ∥22 = ≤ λ′1 . e⊤ e ∥e′ ∥22 + e2n
Since K ′ ≻ 0, we have λ′1 > 0, which implies λ′1 = λmin (K ′ ). This proves the claim. Lemma A.3 (Spectral Bound on Submodularity Ratio). Assume that K ≻ 0 is a correlation ma−1 trix. For f (S) = p⊤ S K S pS and disjoint sets L, A, let K L∪A be partitioned naturally into blocks K L , K A , K LA , K AL . We define the residual statistics p̃ and K̃ (Schur complement) as: p̃ = pA − K AL K −1 L pL ,
K̃ = K A − K AL K −1 L K LA . ⊤
−1 p̃
K̃)] The submodularity ratio γV,k , which involves minimizing the term p̃ [diag( −1 ⊤ p̃ K̃
p̃
, is bounded from
below by the eigenvalues of K: γV,k ≥
min L⊆V, A⊆V\L |A|≤k
λmin (K, |L ∪ A|) ≥ λmin (K, N ),
where λmin (K, k) ≜ minS:|S|=k λmin (K S ) denotes the smallest eigenvalue among all k × k principal submatrices of K, and N = |V|.
Proof. Consider disjoint L and A. Using the block inverse formula for K −1 L∪A , one obtains the decomposition −1 ⊤ f (L ∪ A) = p⊤ L K L pL + p̃ K̃
−1
p̃,
hence f (L ∪ A) − f (L) = p̃⊤ K̃
−1
p̃.
For a singleton a ∈ A, the same calculation with |A| = 1 gives f (L ∪ {a}) − f (L) =
p̃2a . K̃aa
Therefore, for any L ⊆ V and A with |A| ≤ k and A ∩ L = ∅, the ratio appearing in the definition of the submodularity ratio becomes P
−1 p̃⊤ diag(K̃) p̃ f (L ∪ {a}) − f (L) = . −1 f (L ∪ A) − f (L) p̃⊤ K̃ p̃
a∈A
Then, let D = diag(K̃) and define the correlation matrix K̃ ρ = D −1/2 K̃D −1/2 . Let v = D −1/2 p̃. Then p̃⊤ D −1 p̃ = ∥v∥22 , Hence the ratio equals so
p̃⊤ K̃
−1
−1
p̃ = v ⊤ K̃ ρ v. −1
v⊤ v −1 v ⊤ K̃ ρ v
−1
. By Rayleigh–Ritz, v ⊤ K̃ ρ v ≤ λmax (K̃ ρ ) v ⊤ v = λ p̃⊤ D −1 p̃ p̃⊤ K̃
−1
1 min (K̃ ρ )
v ⊤ v,
≥ λmin (K̃ ρ ).
p̃
We can eliminate the elements of L one by one via residualization; each elimination replaces the current covariance by the covariance of residuals. By Lemma A.2, each such residualization step cannot decrease the smallest eigenvalue. After eliminating all of L, we obtain the Schur complement K̃ corresponding to conditioning on L, and thus λmin (K L∪A ) ≤ λmin (K̃). Finally, normalizing K̃ to unit variance gives K̃ ρ , and λmin (K̃) ≤ λmin (K̃ ρ ). Combining the last two displays: λmin (K̃ ρ ) ≥ λmin (K L∪A ) ≥ λmin (K, |L ∪ A|). By definition of γV,k , we conclude γV,k ≥
min L⊆V, A⊆V\L |A|≤k
λmin (K, |L ∪ A|).
Since K L∪A is a principal submatrix of K, Cauchy’s interlacing theorem gives λmin (K L∪A ) ≥ λmin (K). In our notation, λmin (K) = λmin (K, N ), which naturally completes the proof.
Lemma A.4 (Approximation Bound for Greedy MEE). Assume that K ≻ 0 is a correlation matrix defined on ground set V (|V| = N ). Let Sk be the greedy set after k steps. Then the approximation bound holds: f (Sk ) ≥ (1 − exp{−λmin (K, N )}) max f (S). S⊆V |S|≤k
Proof. Let OPT ≜ maxS⊆V, |S|≤k MEE(S). −1 First, since the Mahalanobis-Ensemble Energy objective MEE(S) = p⊤ S K S pS is a normalized, nonnegative, and monotone set function, we can apply the general greedy guarantee from Lemma A.1. This yields: MEE(Sk ) ≥ 1 − e−γV,k · OPT, where γV,k is the submodularity ratio of MEE on the ground set V. Next, we lower bound the submodularity ratio γV,k . By Lemma A.3, the submodularity ratio satisfies: γV,k ≥
min L⊆V, A⊆V\L |A|≤k
λmin (K, |L ∪ A|).
Since L ∪ A ⊆ V, we have |L ∪ A| ≤ N . By the interlacing theorem, every principal submatrix of K has a minimum eigenvalue at least λmin (K, N ). Hence: γV,k ≥ λmin (K, N ). Substituting this spectral lower bound back into the greedy approximation guarantee gives: MEE(Sk ) ≥ 1 − e−λmin (K,N ) · OPT. This completes the proof. −1 T Proof of Theorem 3.2. Let MEE(S) = p⊤ S K S pS and cλ = 1 + λH2 (p). The objective can be written . Define the greedy approximation factor as αN = 1 − exp{−λmin (K, N )}. as MESλ (S) = MEE(S) |S| cλ
By Lemma A.4, for every k = 1, . . . , N , the greedy set Sk satisfies: MEE(Sk ) ≥ αN
max
S⊆V |S|≤k
MEE(S).
(10)
Fix any k ∈ {1, . . . , N }. Dividing both sides of (10) by ckλ gives: MESλ (Sk ) =
maxS⊆V,|S|≤k MEE(S) MEE(Sk ) ≥ αN k cλ ckλ maxS⊆V,|S|=k MEE(S) ≥ αN ckλ MEE(S) = αN max = αN max MESλ (S). |S| S⊆V S⊆V c λ |S|=k |S|=k
Taking the maximum over all subset sizes k = 1, . . . , N on both sides, we obtain the global bound for the greedy trajectory: max MESλ (Sk ) ≥ αN max
1≤k≤N
max
1≤k≤N S⊆V |S|=k
MESλ (S).
(11)
By Theorem 3.1, the greedy saturation stopping point τ achieves the exact maximum of the entire greedy sequence, meaning MESgτ = max0≤r≤N MESgr . Since MESgr = MESλ (Sr ), we have:
MESgτ ≥ max MESλ (Sk ). 1≤k≤N
Combining this with (11) and substituting the definition of αN , we arrive at our final conclusion: MESgτ ≥ (1 − exp{−λmin (K, N )}) max MESλ (S). ∅̸=S⊆V
This completes the proof.
B
Additional Experiments
This section provides repeated evaluations, controlled ablations, diagnostic analyses, and efficiency measurements. All experiments in this work were conducted on a single NVIDIA GeForce RTX 4090 GPU. Unless stated otherwise, repeated generation results use three shared seeds and report the mean ± sample standard deviation.
B.1
Additional Results for Reasoning Benchmarks
Tables 6 and 7 repeat the reasoning evaluation over three seeds and report CraEG combined with p-less. This composition follows CraEG’s plug-in role as a post-softmax reweighting module rather than a standalone support-selection rule, while the tables use CraEG as the concise method name. Across the nine model–temperature settings, ME-Decoding achieves the highest average accuracy on both GSM8K and GPQA. It leads in eight of the nine settings on each benchmark, supporting stable improvements across seeds and temperatures.
B.2
Ablation Studies
Probability and Kernel Controls. We use Greedy decoding to test whether repeatedly selecting the locally most probable token is sufficient. At T = 1.0, ME-Decoding improves GSM8K accuracy from 61.41% to 63.20 ± 0.57% and GPQA accuracy from 32.37% to 32.66±1.05% on Qwen2.5-1.5B. Greedy is deterministic, whereas ME-Decoding results average three generation seeds. We then compare the semantic kernel with two controlled alternatives. The identity kernel K = I removes pairwise geometry, reducing the P MEE numerator to i∈S p2i . The permuted kernel Kperm = P Ktrue P ⊤ preserves the eigenvalues, condition number, entry multiset, and numerical scale of the semantic kernel while disrupting its alignment with token identities. All variants use the same prompts, probabilities, generation seeds, and pruning hyperparameters.
Dataset
True K
Permuted K
K=I
GSM8K GPQA
62.32 32.64
61.15 32.09
60.85 29.81
Table 8: Accuracy (%) averaged over T ∈ {1.0, 1.5, 2.0} in the Qwen2.5-1.5B kernel-control experiment. Both controls reduce accuracy relative to the correctly aligned semantic kernel.
The correctly aligned semantic kernel achieves the highest average accuracy on both datasets, while removing or permuting the geometry reduces performance. Component Ablations. We examine the contribution of the adaptive bandwidth ϵ and the kernel matrix K. Removing the adaptive bandwidth degrades performance, especially at higher temperatures, which indicates that an appropriately scaled kernel is important for robust optimization. Replacing K with the identity matrix removes the embedding-based similarity structure and also reduces accuracy.
Qwen3-4B-Instruct T = 1.5
Phi-4-mini-Instruct
T = 2.0
T = 1.0
T = 1.5
T = 2.0
Mistral-7B-Instruct
Method
T = 1.0
T = 1.0
T = 1.5
T = 2.0
p-less Top-W CraEG Ours
78.82±0.24 72.53±0.50 64.47±1.00 82.99±0.76 82.99±0.39 71.14±0.99 53.53±0.73 51.96±0.74 46.07±1.30 67.17 77.63±0.35 76.65±0.23 75.54±0.72 83.24±0.13 83.52±0.23 82.99±0.18 53.07±0.40 53.50±1.05 52.44±1.26 70.95 72.23±1.71 65.07±1.00 58.12±1.32 83.52±0.55 81.91±1.07 65.38±1.26 52.72±0.12 50.82±0.57 40.56±1.64 63.37 80.04±0.69 79.56±0.35 80.04±0.80 83.90±0.24 83.95±0.31 82.44±0.12 54.18±1.03 53.55±0.12 53.98±0.57 72.40
Avg.
Table 6: GSM8K flexible-extract accuracy (%) over three generation seeds. Subscripts report sample standard deviations, and the Avg. column averages the nine model–temperature means. Qwen3-4B-Instruct T = 1.5
Phi-4-mini-Instruct
T = 2.0
T = 1.0
T = 1.5
T = 2.0
Mistral-7B-Instruct
Method
T = 1.0
T = 1.0
T = 1.5
T = 2.0
p-less Top-W CraEG Ours
35.57±2.29 35.86±1.57 33.85±1.35 32.81±1.77 32.66±0.78 30.06±2.79 28.42±1.44 28.72±1.23 27.68±1.39 31.74 35.49±0.45 34.90±0.78 35.86±0.26 31.62±0.78 30.58±0.77 30.65±1.49 28.79±1.02 29.39±0.34 29.39±1.49 31.85 35.71±1.24 34.08±2.17 33.93±0.97 32.22±1.42 32.14±0.80 29.54±0.68 28.65±0.68 28.72±2.03 28.20±1.23 31.46 36.68±0.13 36.76±0.68 36.61±0.59 34.30±0.68 34.45±0.78 34.08±0.56 29.09±1.01 29.84±0.34 29.32±0.46 33.46
Avg.
Table 7: GPQA accuracy (%) over three generation seeds. Subscripts report sample standard deviations, and the Avg. column averages the nine model–temperature means.
Dataset
T
ME-Decoding
Without ϵ
K=I
submatrices.
GSM8K
1.0 1.5 2.0
84.08 84.23 82.41
−2.20 −4.62 −8.19
−0.15 −0.83 −1.36
B.4
GPQA
1.0 1.5 2.0
34.38 36.16 33.93
−0.22 −1.56 −0.22
−0.67 −2.90 −0.89
Table 9: Component ablations under different temperatures. The ME-Decoding column reports absolute accuracy, while the remaining columns report changes relative to ME-Decoding.
B.3
Empirical Validation of Theorem 3.1
The condition in Theorem 3.1 is sufficient rather than necessary for trajectory unimodality. To examine whether the predicted behavior occurs in practice, we disable early stopping and record the complete greedy MES trajectory for a 512-trajectory probe from each benchmark using Qwen2.5-1.5B at T = 1.0. Dataset
Unimodal Trajectories
Rate
GSM8K GPQA
512/512 512/512
100% 100%
Table 10: Empirical unimodality of complete greedy MES trajectories.
The observation supports the practical relevance of the stopping behavior without replacing the theorem’s sufficient-condition analysis. The approximation result has a separate scope and depends on restricted minimum eigenvalues of selected kernel
Efficiency and Complexity
We benchmark 200 GSM8K problems, generating 64 tokens per problem with T = 1.5, batch size 1, and N = 512. Each method therefore generates 12,800 tokens. ME-Decoding uses a custom Triton kernel, and all methods use identical filtering and sampling infrastructure.
Model
Method
Model Inference (s) Decoding and Sampling (s) Other (s) Total (s) ms/token
Top-p Min-p Qwen2.5-1.5B p-less Top-H ME-Decoding
233.20 233.19 233.23 233.56 242.85
4.29 2.17 2.17 4.68 5.64
0.99 0.57 0.63 1.00 1.03
238.48 235.93 236.03 239.25 249.52
18.63 18.43 18.44 18.69 19.49
Top-p Min-p p-less Top-H ME-Decoding
358.20 356.42 356.63 359.14 360.29
2.89 1.97 1.97 2.91 3.01
0.50 0.55 0.59 0.63 1.15
361.58 358.94 359.18 362.68 364.45
28.25 28.04 28.06 28.33 28.47
Qwen3-4B
Table 11: End-to-end GPU timing breakdown.
Table 11 shows that ME-Decoding increases total latency by approximately 5.8% on Qwen2.51.5B and 1.5% on Qwen3-4B relative to the fastest baseline, with model inference remaining the dominant cost. Detailed Complexity Analysis. Let N denote the size of the candidate token pool, d denote the token embedding dimension, and τ denote the number of tokens selected before the early stopping criterion is triggered. ME-Decoding does not explicitly construct the full N × N similarity matrix. The adaptive bandwidth can also be computed without any pairwise construction. Since we use normalized token embeddings and C ij = 1 − e⊤ i ej , we have 2 X 1 X 1 ϵ= pi pj C ij = 1− pi ei , 2 2 i,j∈V
i∈V
2
where p is normalized over the candidate pool. Therefore, computing ϵ only requires a probabilityweighted average of token embeddings, with complexity O(N d). After obtaining ϵ, kernel entries are dynamically computed according to Eq. 3. Whenever a new token is selected, the algorithm computes and caches its similarities to all candidate tokens, which costs O(N d) per selected token and therefore O(N τ d) in total. For the greedy selection stage, at the t-th step, the selected set has size t, and the algorithm evaluates at most N − t remaining candidates. For each candidate j, the dominant operation is computing αj = Rβ j , where R ∈ Rt×t and β j ∈ Rt , which costs O(t2 ). Hence, the total greedy evaluation cost before stopping is τ −1 X t=1
O (N − t)t
2
≤
τ −1 X t=1
2
3
O(N t ) = O(N τ ).
After each selected token, updating R and z through the block update costs O(t2 ) at step t, giving an additional O(τ 3 ) cost, which is dominated by O(N τ 3 ) since τ ≤ N . Therefore, the overall time complexity of ME-Decoding is O(N d + N τ d + N τ 3 ) = O N τ (d + τ 2 ) . The memory overhead is O(N τ ) for cached kernel entries and O(τ 2 ) for maintaining R. In contrast, explicitly constructing the full kernel matrix would require O(N 2 d) time and O(N 2 ) memory. Since the early stopping rule usually yields τ ≪ N , MEDecoding avoids the quadratic dependence on the candidate pool size and remains efficient in practice. B.5
Hyperparameter Analysis
We study the sensitivity of ME-Decoding to the hyperparameter λ, which controls the compactness of the selected token set. A larger λ imposes a stronger penalty on the subset size and therefore encourages a tighter candidate set, while a smaller λ allows more tokens to be retained. Table 12 reports the accuracy of ME-Decoding under different values of λ across three models, three temperatures, and two reasoning datasets. The results show that ME-Decoding is relatively stable over a range of λ values and consistently achieves strong performance under different settings. Among the tested values, λ = 0.9 obtains the best average accuracy on both GSM8K and GPQA. Therefore, unless otherwise specified, we use λ = 0.9 as the default setting in the main experiments. B.6
Diversity Analysis
Support-Level Diversity Diagnostics. Table 13 shows that ME-Decoding achieves the highest accuracy and MES on both datasets, while retaining a
Phi-4-mini-Inst.
Qwen3-4B-Inst.
λ
T = 1.0
T = 1.5
T = 2.0
T = 1.0
T = 1.5
Mistral-7B-Inst.
Avg.
T = 2.0
T = 1.0
T = 1.5
T = 2.0
82.03 82.41 81.65 82.11
52.84 55.34 55.19 53.45
52.77 53.45 53.45 54.51
53.45 53.90 53.53 53.75
72.39 72.66 72.50 72.37
35.71 33.93 34.15 33.93
27.90 28.35 27.90 27.90
28.79 28.79 25.67 29.24
27.23 28.35 27.68 26.34
32.64 32.96 32.42 32.12
GSM8K 1.0 0.9 0.8 0.7
81.20 80.67 80.44 79.68
81.35 79.76 80.06 80.14
79.76 80.06 80.44 79.98
83.78 84.08 83.70 84.15
84.38 84.23 84.08 83.55 GPQA
1.0 0.9 0.8 0.7
34.82 35.49 36.16 36.38
34.15 35.49 36.38 35.04
34.82 35.71 35.27 34.60
35.04 34.38 35.27 33.71
35.27 36.16 33.26 31.92
Table 12: Detailed hyperparameter selection results for ME-Decoding. Accuracy is reported in percentage. The highlighted row corresponds to the selected setting, λ=0.9, which achieves the best average performance on both GSM8K and GPQA.
compact support and comparable probability mass. None of the approximately matched probabilityonly controls reproduces both results, indicating that the gain is not explained solely by stronger truncation or one support statistic. Detailed Diversity Results. Table 14 reports the detailed numerical results corresponding to the diversity analysis in the main text. For each temperature, we report Acc, Distinct-1, Distinct-2, 1 − Self-BLEU, and the aggregated Diversity Avg. score. The diversity score is computed by minmax normalizing the three diversity metrics within each temperature and then taking their average. Although Top-p often obtains the highest diversity score, especially at high temperature, its accuracy drops substantially. In contrast, ME-Decoding maintains the strongest accuracy across temperatures, showing that it provides a better accuracy– diversity trade-off for reasoning-oriented generation. B.7
Additional Results for Open-Ended Generation
In the main text, we report the averaged instruction-following and chat performance over three instruction-tuned models. Here, we provide the corresponding per-model visualizations and detailed numerical results. Figure 5 shows the performance curves on MT-Bench and AlpacaEval across temperatures for each model. Figure 6 further summarizes the relative ranking of each decoding method under every model-temperature setting, averaged over MT-Bench and AlpacaEval. Lower ranks indicate better performance. The heatmap
shows that ME-Decoding obtains competitive ranks in multiple settings and achieves the best overall average rank, suggesting that its improvement is stable across models and temperatures. Tables 17 and 18 report the exact MT-Bench judge scores and AlpacaEval candidate win-rates, respectively. MEDecoding achieves the highest overall averages, with 7.17 on MT-Bench and 14.80% on AlpacaEval, although individual baselines lead in several settings. All results are evaluated using the same judge-based evaluation protocol as in the main text and aggregated over 3 runs. Evaluation Robustness. AlpacaEval-style evaluation compares each generated response with a fixed reference for the same prompt, while MTBench-style evaluation independently assigns a score from 1 to 10. All methods use matched samples at T ∈ {1.0, 1.5, 2.0} over three generation runs. We evaluate the same outputs with DeepSeekV4-Pro and GLM-5.2 (Zeng et al., 2026). Table 15 shows that ME-Decoding achieves the highest result under both judges and evaluation protocols. Table 16 further reports positive paired 95% confidence intervals against Top-W , p-less, and Top-H, supporting the consistency of the gains beyond aggregate means. Additional length, style, and refusal diagnostics indicate that the gains are not explained by verbosity or conservative refusal behavior.
Dataset
Method
Acc. (%)
Mass Cos. Avg. |S| Hbefore Hafter MES
ME-Decoding 63.20 ± 0.57 0.846 0.151 Top-W 61.64 ± 1.19 0.841 0.208 p-less 61.33 ± 0.23 0.842 0.179 61.16 ± 0.42 0.847 0.241 GSM8K Top-H Approx. size-matched 61.79 ± 1.26 0.850 0.210 Approx. entropy-matched 61.79 ± 0.99 0.851 0.208 Approx. cosine-matched 62.70 ± 0.35 0.840 0.198
1.076 1.093 1.164 2.240 1.067 1.070 1.014
0.614 0.692 0.659 0.736 0.615 0.614 0.598
0.052 0.057 0.075 0.191 0.044 0.045 0.010
0.756 0.688 0.689 0.660 0.707 0.708 0.715
ME-Decoding 32.66 ± 1.05 0.759 0.243 Top-W 27.69 ± 0.91 0.692 0.185 p-less 28.21 ± 1.05 0.770 0.192 Top-H 27.52 ± 0.66 0.778 0.184 Approx. size-matched 28.47 ± 1.17 0.760 0.289 Approx. entropy-matched 28.47 ± 1.17 0.760 0.289 Approx. cosine-matched 29.25 ± 0.91 0.737 0.259
1.134 1.213 1.265 2.877 1.106 1.106 1.084
0.983 1.454 1.002 1.277 0.947 0.947 1.018
0.091 0.124 0.144 0.431 0.069 0.069 0.055
0.589 0.498 0.553 0.475 0.558 0.558 0.537
GPQA
Table 13: Complete support diagnostics on Qwen2.5-1.5B at T = 1.0. Cosine similarity is computed within the selected support at each decoding step and then averaged across steps. The approximately matched Min-p controls are calibrated on independent prompts. Accuracy reports the mean ± sample standard deviation over three seeds. Table 14: Accuracy and diversity comparison under different temperatures. Diversity Avg. is computed by first min-max normalizing Distinct-1, Distinct-2, and 1 − Self-BLEU within each temperature, and then averaging the three normalized scores.
T
Method
Acc ↑
Distinct-1 ↑ Distinct-2 ↑ 1 − Self-BLEU ↑ Diversity Avg. ↑
Top-p Min-p p-less Top-H 1.0 Top-W ME-Decoding (λ = 0.9) ME-Decoding (λ = 0.8) ME-Decoding (λ = 0.7)
0.8484 0.8596 0.8906 0.8832 0.8996 0.9030 0.9008 0.9024
0.0050 0.0050 0.0046 0.0045 0.0049 0.0049 0.0049 0.0049
0.0695 0.0705 0.0445 0.0418 0.0480 0.0472 0.0504 0.0528
0.2570 0.2595 0.0607 0.0614 0.0686 0.0588 0.0813 0.1014
0.9842 1.0000 0.1012 0.0043 0.3550 0.3294 0.4039 0.4652
Top-p Min-p p-less Top-H 1.5 Top-W ME-Decoding (λ = 0.9) ME-Decoding (λ = 0.8) ME-Decoding (λ = 0.7)
0.6794 0.7802 0.8682 0.8224 0.8982 0.9026 0.9058 0.8996
0.0224 0.0054 0.0046 0.0047 0.0049 0.0052 0.0051 0.0053
0.1503 0.0849 0.0546 0.0585 0.0542 0.0526 0.0564 0.0592
0.4136 0.3421 0.1464 0.1974 0.1148 0.0735 0.1046 0.1268
1.0000 0.3884 0.0783 0.1434 0.0516 0.0112 0.0528 0.0879
Top-p Min-p p-less Top-H 2.0 Top-W ME-Decoding (λ = 0.9) ME-Decoding (λ = 0.8) ME-Decoding (λ = 0.7)
0.1886 0.6600 0.8128 0.7394 0.8906 0.9068 0.9036 0.9034
0.2494 0.0068 0.0049 0.0053 0.0047 0.0050 0.0051 0.0052
0.7750 0.1122 0.0659 0.0784 0.0543 0.0499 0.0553 0.0573
0.9054 0.4487 0.2454 0.3209 0.1397 0.0668 0.0959 0.1187
1.0000 0.1833 0.0786 0.1149 0.0310 0.0004 0.0146 0.0247
Judge
Method
AlpacaEval (%)
MT-Bench
DeepSeek-V4-Pro
Top-p Min-p Top-H p-less Top-W ME-Decoding
13.04 ± 2.07 14.14 ± 0.60 14.36 ± 0.58 14.33 ± 0.07 14.14 ± 0.04 14.80 ± 0.30
6.34 ± 0.89 6.86 ± 0.41 6.88 ± 0.33 6.94 ± 0.11 7.08 ± 0.02 7.17 ± 0.03
GLM-5.2
Top-H p-less Top-W ME-Decoding
9.48 ± 0.78 10.18 ± 0.24 10.11 ± 0.20 10.63 ± 0.16
5.42 ± 0.23 5.54 ± 0.05 5.58 ± 0.03 5.64 ± 0.01
Table 15: Open-ended evaluation under two automatic judges. Results average temperature-level aggregates over three generation runs.
Judge
Baseline
∆ AlpacaEval (pp)
95% CI
∆ MT-Bench
95% CI
DeepSeek-V4-Pro
Top-W p-less Top-H
+0.656 +0.469 +0.440
[0.320, 0.980] [0.115, 0.810] [0.076, 0.799]
+0.092 +0.234 +0.297
[0.018, 0.169] [0.158, 0.305] [0.221, 0.373]
GLM-5.2
Top-W p-less Top-H
+0.529 +0.456 +1.157
[0.239, 0.819] [0.138, 0.782] [0.824, 1.481]
+0.069 +0.107 +0.221
[0.018, 0.120] [0.052, 0.163] [0.162, 0.281]
Table 16: Paired-bootstrap gains of ME-Decoding. Resampling preserves prompt, model, temperature, and generation-run matching.
12
T=1.5
Score
T=1.5
T=2
0
T=2
Top-H
Top-W
0
Qwen3-4B-Inst.
T=1
T=1.5
T=1.5
6 4 2
T=2
0
Phi-4-mini-Inst. Top-p
Min-p
Top-H
p-less
8.78 8.47 8.05 8.22 8.43
T=1
4.82
8
8.49 9.13 8.84 8.59 7.95 8.20
1
Win-Rate (%)
2.73 2.90 2.73 2.73 2.61 2.90
2
10
8.43 9.17 8.49 8.30 7.56 8.36
T=2
ME-Decoding
12
4 3
p-less
Mistral-7B-Inst.
0.17
10
T=1.5
5.19 6.10 6.25 6.53 6.51 6.68
T=1
Min-p
Win-Rate (%)
27.00 29.80 30.45 32.09 31.76 33.42
31.28 31.21 32.23 31.68 32.05 31.93
32.08 31.72 32.85 31.93 32.26 34.00
Win-Rate (%)
20
T=1
T=1
4
Phi-4-mini-Inst. Top-p
30
6.27 6.55 6.70 6.47 6.55 6.72
0
T=2
1.82 2.15 2.65 2.32 2.65
T=1.5
2.40 2.69 3.02 2.94 2.57 3.31
T=1
6
2
Qwen3-4B-Inst.
0
6.16 6.05
2
2
40
8
6.63 6.69 6.59 6.42 6.44 6.78
4
0
4.61 4.63 5.15
4 2.37
6
4.85 5.63 5.79 5.91 5.96 5.94
8
6
5.79 6.19 5.97 5.91 6.12 5.93
8.47 8.51 8.62 8.75 8.64 8.87
8.69 8.73 8.65 8.62 8.72 8.76
8.76 8.71 8.70 8.70 8.62 8.84
8
Score
Score
10
Top-W
T=2
Mistral-7B-Inst. ME-Decoding
Figure 5: Detailed instruction-following and chat performance across temperatures. Top: MT-Bench judge scores. Bottom: AlpacaEval candidate win-rate. Results are reported for three instruction-tuned models and aggregated over 3 runs.
Qwen3-4B-Inst.
Phi-4-mini-Inst.
Mistral-7B-Inst.
Method
T = 1.0
T = 1.5
T = 2.0
T = 1.0
T = 1.5
T = 2.0
T = 1.0
T = 1.5
T = 2.0
Avg.
Min-p Top-p p-less Top-H Top-W Ours
8.71 8.76 8.70 8.70 8.62 8.84
8.73 8.69 8.62 8.65 8.72 8.76
8.51 8.47 8.75 8.62 8.64 8.87
6.19 5.79 5.91 5.97 6.12 5.93
5.63 4.85 5.91 5.79 5.96 5.94
4.61 2.37 5.15 4.63 6.16 6.05
6.69 6.63 6.42 6.59 6.44 6.78
6.55 6.27 6.47 6.70 6.55 6.72
6.10 5.19 6.53 6.25 6.51 6.68
6.86 6.34 6.94 6.88 7.08 7.17
Table 17: Detailed MT-Bench judge scores. Results are reported across three instruction-tuned models and three temperatures, aggregated over 3 runs. The Avg. column gives the unweighted average over all model-temperature combinations. Best results are shown in bold, and second-best results are underlined.
Qwen3-4B-Inst.
Phi-4-mini-Inst.
Mistral-7B-Inst.
Method
T = 1.0
T = 1.5
T = 2.0
T = 1.0
T = 1.5
T = 2.0
T = 1.0
T = 1.5
T = 2.0
Avg.
Min-p Top-p p-less Top-H Top-W Ours
31.72 32.08 31.93 32.85 32.26 34.00
31.21 31.28 31.68 32.23 32.05 31.93
29.80 27.00 32.09 30.45 31.76 33.42
2.90 2.73 2.73 2.73 2.61 2.90
2.69 2.40 2.94 3.02 2.57 3.31
1.82 0.17 2.65 2.15 2.32 2.65
9.17 8.43 8.30 8.49 7.56 8.36
9.13 8.49 8.59 8.84 7.95 8.20
8.78 4.82 8.05 8.47 8.22 8.43
14.14 13.04 14.33 14.36 14.14 14.80
Table 18: Detailed AlpacaEval candidate win-rate (%). Results are reported across three instruction-tuned models and three temperatures, aggregated over 3 runs. The Avg. column gives the unweighted average over all modeltemperature combinations. Best results are shown in bold, and second-best results are underlined.
Rank by Model and Temperature
6
Ours
1.0
2.0
1.0
2.8
1.5
1.8
2.5
3.0
2.0
Top-W
4.5
2.5
3.0
4.0
3.0
2.0
5.5
4.5
3.5
p-less
5.0
5.0
2.0
4.2
3.0
2.2
5.5
4.0
3.5
Top-H
3.0
3.0
4.0
3.2
3.0
4.0
3.0
2.0
3.0
Min-p
4.5
4.0
5.0
1.2
4.5
5.0
1.5
2.5
3.0
4
Rank
Method
5
3
2 Top-p
3.0
4.5
6.0
5.5
6.0
6.0
3.0
5.0
6.0
Qwen3-4B T=1
Qwen3-4B T=1.5
Qwen3-4B T=2
Phi-4-mini T=1
Phi-4-mini T=1.5
Phi-4-mini T=2
Mistral-7B T=1
Mistral-7B T=1.5
Mistral-7B T=2
1
Model and Temperature
Figure 6: Detailed average-rank comparison on open-ended generation benchmarks. The heatmap reports the rank of each decoding method under each model-temperature setting, averaged over AlpacaEval and MT-Bench.