Research map / Large language models / Reasoning and chain of thought

Entropy-informed Decoding: Adaptive Information-Driven Branching

ICML 2026 · Large language models › Reasoning and chain of thought · approach: Routing, pruning and distillation for reasoning · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes EDEN, a decoding framework that sets beam branching factor proportional to normalized next-token entropy, achieving beam-search-level accuracy with fewer expansions on math, code, and science benchmarks.

Problem

Fixed-width beam search and sampling-based decoders either expend compute regardless of task complexity or commit to narrow paths; the paper seeks adaptive compute allocation during decoding.

Approach

Use the normalized entropy of the next-token distribution to set a per-step branching factor (monotone in entropy), expanding more candidates at uncertain steps and staying near greedy at confident steps, with a branch-and-bound pruning rule and theoretical regret/allocation arguments.

Key results

• On Llama-3.2-3B-Instruct, EDEN reaches 80.5% on GSM8K with 598 expansions versus 81.5% for beam search (3) with 1200 expansions, and best average Friedman rank 1.25 (p=0.012).
• EDEN achieves 32.8% on MATH500 and 31.3% on HumanEval, above beam search's 29.2% and 28.8%, with 840 and 965 expansions respectively.
• Bayesian analysis gives EDEN a 75% posterior probability of being the best method overall; vs beam search, P(EDEN > beam)=0.78.

Surprising findings

• Beam search achieves the highest GSM8K accuracy (81.5%) over EDEN (80.5%), so EDEN does not dominate on every benchmark.
• Top-k sampling underperforms greedy decoding on several benchmarks for Llama (e.g., MATH500 23.0% vs 27.4%).

Limitations

• Gains over beam search are not uniform; beam search is slightly better on GSM8K, and differences are often within confidence intervals.
• Heterogeneous branching complicates GPU parallelization.
• Closed-API setting uses only top-k log probs, giving a biased entropy estimate; the 7B Mistral evaluation is on only 100 GSM8K examples with 8-bit quantization.

Experimental setup

Datasets: GSM8K MATH500 HumanEval SciBench

Benchmarks: GSM8K MATH500 HumanEval SciBench

Metrics: accuracy (pass@1) average Friedman rank expansions count posterior probability from Bayesian hierarchical model

Baselines: Greedy decoding Top-k sampling Top-p sampling Top-H sampling Min-p sampling Best-of-n Majority voting Beam search Diverse beam search

Builds on: beam search top-k sampling nucleus sampling min-p sampling best-of-n

Closest papers by meaning

• Confidence-Based Decoding is Provably Efficient for Diffusion Language Models (NeurIPS 2026 · similarity 0.90)
• Improving Open-Ended Text Generation via Adaptive Decoding (ICML 2024 · similarity 0.89)
• Wider or Deeper? Scaling LLM Inference-Time Compute with Adaptive Branching Tree Search (NeurIPS 2025 · similarity 0.89)
• Hot or Cold? Adaptive Temperature Sampling for Code Generation with Large Language Models (AAAI 2024 · similarity 0.89)
• XTC: Head-Aware Sampling by Excluding Top Choices (NeurIPS 2026 · similarity 0.89)
• Optimized Multi-Token Joint Decoding With Auxiliary Model for LLM Inference (ICLR 2025 · similarity 0.88)