Existing decoding algorithms for large language models (LLMs) always rely on the information in the current step. We argue that future entropy is also essential for LLM decoding. However, this quantity is intractable for autoregressive LLMs, since it requires marginalizing over exponentially many continuations. We estimate it by computing the lower and upper bounds of it on a hidden Markov model (HMM), which is distilled as a surrogate of the LLM. By representing the HMM as probabilistic circuits, we make its latent-variable structure explicit and use it to derive an upper bound and a novel lower bound on the circuit entropy. On the HMM, these bounds yield efficient estimates of future entropy, which we leverage to implement entropy-guided decoding. On GSM8K and CSQA, this guidance improves math and logical reasoning over the decoding baselines in the Qwen2.5 and Mistral models, showing that estimated future entropy is effective for decoding.

@inproceedings{ChenTPM26,
  title     = {Entropy-Guided LLM Decoding via Probabilistic Circuits},
  author    = {Chen, Zhizhen and Israel, Daniel and Van den Broeck, Guy and Zeng, Zhe},
  booktitle = {Proceedings of the UAI Workshop on Tractable Probabilistic Modeling (TPM)},
  url       = "https://starai.cs.ucla.edu/papers/ChenTPM26.pdf",
  month     = 7,
  year      = {2026},
  keywords  = {workshop}
}