Decoding as Optimisation on the Probability Simplex: From Top-K to Top-P (Nucleus) to Best-of-K Samplers
Decoding sits between a language model and everything we do with it, yet it is still treated as a heuristic knob-tuning exercise. We argue decoding should be understood as a principled optimisation layer: at each token, we solve a regularised problem over the probability simplex that trades off model score against structural preferences and constraints. This single template recovers greedy decoding, Softmax sampling, Top-K, Top-P, and Sparsemax-style sparsity as special cases, and explains their common structure through optimality conditions. More importantly, the framework makes it easy to invent new decoders without folklore. We demonstrate this by designing Best-of-K (BoK), a KL-anchored coverage objective aimed at multi-sample pipelines (self-consistency, reranking, verifier selection). BoK targets the probability of covering good alternatives within a fixed K-sample budget and improves empirical performance. We show that such samples can improve accuracy by, for example, +18.6% for Qwen2.5-Math-7B on MATH500 at high sampling temperatures.
699c2a43f723198bd53a63cd
Xiaotong Ji
claimed_verified
2026-03-24T09:23:22.074Z
667b6e28a0e1bc140664e725
/avatars/2e4a69a0f98ce6de3f044b2831609ea4.svg
xiaotong
xtongji
user
xtongji
699c2a43f723198bd53a63ce
Rasul Tutunov
699c2a43f723198bd53a63cf
Matthieu Zimmer
699c2a43f723198bd53a63d0
Haitham Bou-Ammar
Decoding as Optimisation on the Probability Simplex: From Top-K to Top-P (Nucleus) to Best-of-K Samplers
Decoding sits between a language model and everything we do with it, yet it is still treated as a heuristic knob-tuning exercise. We argue decoding should be understood as a principled optimisation layer: at each token, we solve a regularised problem over the probability simplex that trades off model score against structural preferences and constraints. This single template recovers greedy decoding, Softmax sampling, Top-K, Top-P, and Sparsemax-style sparsity as special cases, and explains their common structure through optimality conditions. More importantly, the framework makes it easy to invent new decoders without folklore. We demonstrate this by designing Best-of-K (BoK), a KL-anchored coverage objective aimed at multi-sample pipelines (self-consistency, reranking, verifier selection). BoK targets the probability of covering good alternatives within a fixed K-sample budget and improves empirical performance. We show that such samples can improve accuracy by, for example, +18.6% for Qwen2.5-Math-7B on MATH500 at high sampling temperatures.
Decoding is reinterpreted as a principled optimization layer that balances model scores with structural preferences, recovering existing methods as special cases and enabling the creation of new decoders like Best-of-K that improve accuracy in mathematical reasoning tasks.
decoding probability simplex regularised problem structural preferences constraints greedy decoding Softmax sampling Top-K Top-P Sparsemax optimality conditions Best-of-K KL-anchored coverage objective self-consistency reranking verifier selection Qwen2.5-Math-7B MATH500