Beyond Truncation: Rethinking LLM Decoding as Ensemble Pruning
Dunyao Xue, Chengshuo Du, Zhengbo Wang, Wenlin Dai, Cheng Meng
EMNLP 2026 Main Conference
cs.AI, cs.LG
2026-09-16
ME-Decoding prunes redundant tokens with a Mahalanobis ensemble score. GSM8K avg 72.66 vs Top-W 70.62 on 3 models; Qwen3 stays at 80.06% at T=2 vs Top-p's 21%.
Which token you sample next decides whether generation stays coherent or drifts. Greedy search and beam search cling to high-probability continuations and tend to repeat themselves. Sampling spreads out, and it also gives weak tokens a real share of probability, which is how implausible continuations show up.
The usual fix is probability truncation: Top-k, nucleus (Top-p), Min-p, p-less. All of them keep confident-enough candidates and treat those candidates as independent categories. They ignore that near-synonyms sit on almost the same continuation in embedding space. The surviving support is fat and redundant; truncation budget is spent on semantic clones.
Geometry-aware methods try to close that gap. Top-W writes decoding as Wasserstein matching, which means approximating an expensive objective and tuning it. CraEG downweights crowded regions, then still has to ride on another decoder. This paper wants a narrower object: no weight updates, no retraining, a compact informative subset that keeps high-confidence tokens and discounts semantic duplicates.
ME-Decoding treats the current-step candidates as a pool of weak semantic predictors. Decoding becomes ensemble pruning: each member should be accurate, and they should not all fail the same way. Picking only the top-scoring tokens copies a mistake ensemble methods already know.
Four steps.
The similarity matrix is a Gaussian kernel on L2-normalized embeddings. Bandwidth is the probability-weighted mean pairwise semantic distance over the pool: concentrated candidates get a tight kernel and more probability-driven selection; spread-out candidates get a wider kernel.
Exact subset search is NP-hard. The implementation is greedy forward selection with an incremental Cholesky factor, so they never invert from scratch. At each step they measure residual contribution after partialing out correlation with tokens already chosen, and they stop when MES stops rising. Theorem 3.1: if the similarity matrix is reasonably conditioned, the greedy path is unimodal, so early stopping does not miss the peak on that path. Appendix B.3 reports 512 unimodal trajectories on each of GSM8K and GPQA with Qwen2.5-1.5B. Theorem 3.2 gives an approximation factor controlled by a restricted minimum eigenvalue. Cost is O(N τ (d+τ²)); after early stopping τ≪N, close to linear in the pool size.
Models: Qwen3-4B-Instruct, Phi-4-mini-Instruct, Mistral-7B-Instruct. Temperatures 1.0, 1.5, 2.0. Baselines: Min-p, Top-p, p-less, Top-H, Top-W. Reasoning is answer accuracy on GSM8K and GPQA. Open-ended scores are AlpacaEval win rate and MT-Bench, judged by DeepSeek-V4-Pro, with GLM-5.2 as a second judge in the appendix.
| Method | GSM8K avg | GPQA avg |
| Top-p | 34.30 | 26.74 |
| Min-p | 52.35 | 29.34 |
| Top-H | 57.10 | 31.10 |
| p-less | 66.97 | 31.08 |
| Top-W | 70.62 | 31.56 |
| ME-Decoding | 72.66 | 32.96 |
High temperature is where the gap opens. Qwen3-4B GSM8K at T=2.0: ME-Decoding 80.06, Top-W 74.98, p-less 63.15, Min-p 54.06, Top-p 21.00. Same cell on Phi-4-mini: 82.41 vs Top-W 82.18 and Top-p 0.30. Mistral-7B: 53.90 vs Top-p 0.45. GPQA barely moves: +1.4 over Top-W on average, and at Qwen3 T=1.5 Top-W wins 36.83 to 35.49.
Average rank across models, temperatures, and benchmarks is 1.94; the others sit between about 3.1 and 5.0. MT-Bench averages about 7.17 across the three temperatures; Top-p falls to 5.34 at T=2. Paired prompt-level bootstrap intervals vs Top-W, p-less, and Top-H are positive for both open-ended benches and both judges.
CPU synthetic-logits timing (filter plus sample only, no model forward): Medium (32K vocab, d=256, N=512) is 0.00179 s/token vs Top-W 0.00487, about 2.7×. Large (128K, d=1024, N=2048) is 0.01799 vs 0.13337, about 7.4×. Large is slightly slower than Top-p (0.01407) and Top-H (0.01493). End-to-end GPU cost is still dominated by the forward pass.
On Qwen2.5-1.5B at T=1.0, probability-only controls matched on support size, entropy, or pairwise cosine. GSM8K: 63.20±0.57 vs size-matched 61.79±1.26. GPQA: 32.66±1.05 vs 28.47±1.17. Mean |S| is only about 1.08, so most steps keep a single token.
Plug-in, no weight changes. Teams already running nucleus or Min-p who find Top-W too slow can treat this as a cheaper geometry-aware sampler, especially if they want T in 1.5-2.0 without math accuracy collapsing.
The accuracy lift over Top-W is incremental: about 2 points on GSM8K, thinner on GPQA. High-T stability is the more useful part, plus an order-of-magnitude cheaper sampling than Wasserstein matching.
Swapping the decoder will not turn a 7B instruct model into a frontier reasoner.
Default λ=0.9, pool size 512. Code is released with the paper.
The authors list three. The kernel uses static token embeddings and misses context-dependent distinctions; a hidden-state-conditioned kernel is future work. Accuracy is higher at matched diversity, but diversity itself is often not the highest, so the kernel may be conservative. Choosing subset size is still hard, and MES may not fit every next-token distribution.
The main tables only cover 4B-7B instruct models, no larger MoE, no closed APIs. GPQA is not a clean sweep; geometry helps little on hard science questions. Open-ended eval is entirely LLM-as-judge. Table 5's mean support size near 1 means the ensemble on the small model is closer to geometry-braked near-greedy decoding. N=512 is matched for geometry methods, but they never sweep pool size. CraEG appears only as an appendix plugin, not in the main tables.