Composable Decoding on the Probability Simplex: Theory and Implementation

Xiaotong Ji; Ahmed Khaled Khamis; Rasul Tutunov; Matthieu Zimmer; Haitham Bou-Ammar

cs.LGSep 28, 2026

Composable Decoding on the Probability Simplex: Theory and Implementation

Authors: Xiaotong Ji, Ahmed Khaled Khamis, Rasul Tutunov, Matthieu Zimmer, Haitham Bou-Ammar

Organizations: Huawei Noah’s Ark Lab · UCL Centre for AI

Abstract

Decoding for large language models is typically treated as a collection of isolated sampling strategies, with limited theoretical understanding of the behaviours they induce and how their underlying objectives relate. We formulate decoding as an optimisation problem over next-token distributions on the probability simplex, balancing expected model score against regularisation under support constraints. This view recovers familiar decoding methods through choices of regularisers and support constraints; more importantly, it enables new decoders to be constructed by composing distributional preferences within a single optimisation problem without external rewards, learned critics, or model parameter updates. We introduce CompoSimplex, a library with configurable support rules, regularisation primitives, and simplex solvers for constructing and evaluating compositional decoders. We evaluate standard samplers, individual regularisers, and compositions across multiple models and reasoning tasks. Our results show that compositions can realise trade-offs between single-sample quality, multi-sample quality, and diversity that are not attained by individual decoding objectives.

Figures & tables

Appendix figures & tables8 assets

Supplementary material from the paper’s appendix.

Appendix

Method	$\tau$	Pass@1 $\uparrow$	Pass@4 $\uparrow$	Pass@16 $\uparrow$
Top- $k$ ( $k=200$ )	0.25	62.8	82.0	92.0
	0.5	59.8	81.2	90.0
	0.7	52.0	77.2	87.6
BoK (KL + Diversity)	0.25	65.2	84.0	92.0
	0.5	64.4	81.4	90.0
	0.7	60.4	77.8	88.6

Appendix

Table 1: Top-

k

sampling and BoK (KL + Diversity) at three different temperatures on MATH500 with Qwen2.5-7B. Both use Top-

k

support with

k=200

;

\tau

denotes temperature.

Qwen2.5-7B
Method	pass@1 $\uparrow$	pass@4 $\uparrow$	pass@16 $\uparrow$	SC@16 $\uparrow$	SemDiv $\uparrow$
Top-k	59.8	81.2	90.0	78.0	0.150
Single objective primitives
KL	64.4	80.6	88.4	76.8	0.132
JS	63.6	82.2	89.0	76.2	0.136
Entropy	59.8	81.2	90.0	78.0	0.150

Appendix

Table 2: MATH500 performance of Qwen2.5-7B under Top-

k

and Min-

p

support. Rows compare the standard sampler, individual regularisers, and compositions. Accuracy values are percentages.

Qwen3-4B-Base
Method	pass@1 $\uparrow$	pass@4 $\uparrow$	pass@16 $\uparrow$	SC@16 $\uparrow$	SemDiv $\uparrow$
Top-k	15.7	51.0	80.3	12.6	0.710
Single objective primitives
KL	21.2	50.0	78.3	24.7	0.564
JS	23.2	52.5	80.3	22.2	0.584
Entropy	15.7	51.0	80.3	12.6	0.710

Appendix

Table 3: GPQA Diamond performance of Qwen3-4B-Base under Top-

k

and typical support. Rows compare the standard sampler, individual regularisers, and compositions. Accuracy values are percentages.

LFM2.5-1.2B-Base
Method	pass@1 $\uparrow$	pass@4 $\uparrow$	pass@16 $\uparrow$	all-pass@16 $\uparrow$	SemDiv $\uparrow$
Top- $p$	52.1	70.2	80.0	21.8	0.284
Single objective primitives
KL	49.9	70.1	79.7	21.6	0.272
JS	51.4	67.8	79.5	20.9	0.274
Coverage	50.5	67.5	79.5	19.4	0.286

Appendix

Table 4: IFEval performance of LFM2.5-1.2B-Base under Top-

p

and

\eta

-sampling support. Success uses strict prompt-level grading, and success rates are percentages.

Gemma-4-26B-A4B-IT
Method	pass@1 $\uparrow$	pass@4 $\uparrow$	pass@16 $\uparrow$	all-pass@16 $\uparrow$	Hard pass@1 $\uparrow$
Top- $p$	56.6	63.4	69.7	41.7	25.0
Single objective primitives
KL	55.4	63.4	69.7	40.0	26.3
JS	57.1	65.7	69.1	38.9	27.5
Coverage	56.6	64.6	69.1	38.9	25.0

Appendix

Table 5: LiveCodeBench v6 performance of Gemma-4-26B-A4B-IT under Top-

p

and Min-

p

support. Hard pass@1 is measured on the 80 Hard problems. All reported success rates are percentages.

Method	pass@1	pass@4	pass@16	SC@16	SemDiv ( $\times 10^{-3}$ )
Top- $k$	0.70	0.12	0.81	0.92	2.63
KL	0.31	1.13	0.42	0.53	3.99
JS	0.12	0.83	0.42	0.31	3.64
Coverage	0.83	0.71	0.71	0.83	2.56
Diversity	1.33	0.12	1.27	0.71	3.64
KL + Diversity	0.72	0.71	1.11	0.31	3.42

Appendix

Table 6: Sample standard deviations across seeds 0, 42, and 1234 on MATH500 with Qwen2.5-7B and Top-

k

support. Deviations for pass@

k

and SC@16 are in percentage points; SemDiv deviations are shown in units of

10^{-3}

Method	MATH500	GPQA	IFEval	LiveCodeBench
	Top- $k$	Top- $k$	Top- $p$	Top- $p$
Baseline	2.258	3.093	1.833	18.560
KL	2.238	3.068	1.838	18.308
JS	4.329	5.266	3.924	21.255
Coverage	5.004	5.910	4.399	20.954
Diversity	5.751	6.273	4.624	21.245

Appendix

Table 7: Generation cost in milliseconds per output token for selected objectives. Columns use the model–benchmark pair and support rule indicated in the table. The baseline uses the base support rule without an added regulariser.

KL + Coverage
Method	$\bm{\lambda}$	pass@1 $\uparrow$	pass@4 $\uparrow$	pass@16 $\uparrow$	SC@16 $\uparrow$	SemDiv $\uparrow$	KL $\downarrow$	Coverage $\uparrow$
KL	0.5	65.8	82.0	88.0	73.4	0.111	0.0501	0.1498
	1	64.4	80.6	88.4	76.8	0.132	0.0380	0.1564
	2	59.8	81.2	90.0	78.0	0.150	0.0240	0.1663
Coverage	0.5	64.4	82.4	89.4	76.8	0.142	0.0310	0.1622
	1	63.4	82.8	89.4	78.4	0.157	0.0225	0.1729

Appendix

Table 8: Effect of regularisation strength

\lambda\in\{0.5,1,2\}

on KL–Coverage, KL–Diversity, JS–Coverage, and JS–Diversity on MATH500 with Qwen2.5-7B and Top-

k

support. Each family reports task performance, semantic diversity, the indicated divergence, and its coverage or diversity utility.

Explore similar work

Entropy-informed Decoding: Adaptive Information-Driven Branching
May 10, 2026Benjamin Patrick Evans, Sumitra Ganesh, Leo ArdonConstrained Decoding Token-Level Entropy
JP Morgan AI Research, London, UK · JP Morgan AI Research, New York, USA
Grammar-Aligned Decoding
May 31, 2024Kanghee Park, Jiayu Wang, Taylor Berg-Kirkpatrick +2Constrained Decoding Large Language Model Generation
University of Wisconsin-Madison · University of California San Diego
Beyond Truncation: Rethinking LLM Decoding as Ensemble Pruning
Sep 16, 2026Dunyao Xue, Chengshuo Du, Zhengbo Wang +2Large Language Model Decoding Decoding
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 · Center for Applied Statistics, Institute of Statistics and Big Data, Renmin University of China, Beijing, China

May 10, 2026, cs.LGJ/K move · Enter open · S save

Entropy-informed Decoding: Adaptive Information-Driven Branching

Benjamin Patrick Evans, Sumitra Ganesh, Leo Ardon

JP Morgan AI Research, London, UK · JP Morgan AI Research, New York, USA

Constrained Decoding Token-Level Entropy Decoding Beam Search

Open paper AskPDF arXiv

Large language models (LLMs) achieve remarkable generative performance, yet their output quality is dependent on the decoding strategy. While sampling-based methods (e.g., top-k, nucleus) and search-and-select based methods (e.g., beam search, best-of-n, majority voting) can improve upon greedy decoding, both approaches suffer from limitations: sampling generally commits to a single path, while search often expends excessive computation regardless of task complexity. To address these, we introduce Entropy-informed decoding (EDEN), a plug-and-play, model-agnostic decoding framework that adaptively allocates computation based on the model's own uncertainty, approximating higher-width beam search with fewer expansions. At each generation step, EDEN estimates the entropy of the output token distribution and adjusts the branching factor monotonically with the entropy, expanding more candidates in high-entropy regions and following a greedier path in low-entropy regions, improving token efficiency. Experiments across complex tasks, including mathematical reasoning, code generation, and scientific questions, demonstrate that EDEN consistently improves output quality over existing decoding strategies, achieving better accuracy-expansion trade-offs than fixed-width beam search. By treating next-token selection as a noisy maximisation problem, we prove that branching factors monotone in entropy are guaranteed to find better (i.e. more probable) continuations than any fixed branching factor within the same total expansion budget, and derive explicit regret rates characterising the benefit of the adaptive allocation.

Abstract

Explore similar work

Entropy-informed Decoding: Adaptive Information-Driven Branching

Grammar-Aligned Decoding

Beyond Truncation: Rethinking LLM Decoding as Ensemble Pruning