# Fast and Expressive Multi-Byte Prediction with Probabilistic Circuits

arXiv: https://arxiv.org/abs/2511.11346 · HTML: https://mlsanity.com/paper/2511.11346/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 40 of its 65 references that are in the map.
- First posted on arXiv 14 Nov 2025.

## Builds on (most cited first, 30 of 40)

- [Fast Inference from Transformers via Speculative Decoding](https://mlsanity.com/paper/2211.17192/) (2022)
- [Tulu 3: Pushing Frontiers in Open Language Model Post-Training](https://mlsanity.com/paper/2411.15124/) (2024)
- [Accelerating Large Language Model Decoding with Speculative Sampling](https://mlsanity.com/paper/2302.01318/) (2023)
- [Sequence-Level Knowledge Distillation](https://mlsanity.com/paper/1606.07947/) (2016)
- [EAGLE: Speculative Sampling Requires Rethinking Feature Uncertainty](https://mlsanity.com/paper/2401.15077/) (2024)
- [Better & Faster Large Language Models via Multi-token Prediction](https://mlsanity.com/paper/2404.19737/) (2024)
- [Blockwise Parallel Decoding for Deep Autoregressive Models](https://mlsanity.com/paper/1811.03115/) (2018)
- [Unlocking Efficiency in Large Language Model Inference: A Comprehensive Survey of Speculative Decoding](https://mlsanity.com/paper/2401.07851/) (2024)
- [Deterministic Non-Autoregressive Neural Sequence Modeling by Iterative Refinement](https://mlsanity.com/paper/1802.06901/) (2018)
- [Do All Languages Cost the Same? Tokenization in the Era of Commercial Language Models](https://mlsanity.com/paper/2305.13707/) (2023)
- [MEGABYTE: Predicting Million-byte Sequences with Multiscale Transformers](https://mlsanity.com/paper/2305.07185/) (2023)
- [Breaking the Softmax Bottleneck: A High-Rank RNN Language Model](https://mlsanity.com/paper/1711.03953/) (2017)
- [Byte Latent Transformer: Patches Scale Better Than Tokens](https://mlsanity.com/paper/2412.09871/) (2024)
- [SpecTr: Fast Speculative Decoding via Optimal Transport](https://mlsanity.com/paper/2310.15141/) (2023)
- [Hydra: Sequentially-Dependent Draft Heads for Medusa Decoding](https://mlsanity.com/paper/2402.05109/) (2024)
- [Dynamic Memory Compression: Retrofitting LLMs for Accelerated Inference](https://mlsanity.com/paper/2403.09636/) (2024)
- [Einsum Networks: Fast and Scalable Learning of Tractable Probabilistic Circuits](https://mlsanity.com/paper/2004.06231/) (2020)
- [Semantic Probabilistic Layers for Neuro-Symbolic Learning](https://mlsanity.com/paper/2206.00426/) (2022)
- [A Differential Approach to Inference in Bayesian Networks](https://mlsanity.com/paper/1301.3847/) (2013)
- [Coercing LLMs to do and reveal (almost) anything](https://mlsanity.com/paper/2402.14020/) (2024)
- [Efficient Transformers with Dynamic Token Pooling](https://mlsanity.com/paper/2211.09761/) (2022)
- [Getting the most out of your tokenizer for pre-training and domain adaptation](https://mlsanity.com/paper/2402.01035/) (2024)
- [Tractable Control for Autoregressive Language Generation](https://mlsanity.com/paper/2304.07438/) (2023)
- [Tree Tensor Networks for Generative Modeling](https://mlsanity.com/paper/1901.02217/) (2019)
- [Universal Cross-Tokenizer Distillation via Approximate Likelihood Matching](https://mlsanity.com/paper/2503.20083/) (2025)
- [Subtractive Mixture Models via Squaring: Representation and Learning](https://mlsanity.com/paper/2310.00724/) (2023)
- [Adaptable Logical Control for Large Language Models](https://mlsanity.com/paper/2406.13892/) (2024)
- [Inference-Time Hyper-Scaling with KV Cache Compression](https://mlsanity.com/paper/2506.05345/) (2025)
- [Conditional Sum-Product Networks: Imposing Structure on Deep Probabilistic Architectures](https://mlsanity.com/paper/1905.08550/) (2019)
- [Scaling Tractable Probabilistic Circuits: A Systems Perspective](https://mlsanity.com/paper/2406.00766/) (2024)

## Built on by (most cited first, 9 of 9)

- [Bolmo: Byteifying the Next Generation of Language Models](https://mlsanity.com/paper/2512.15586/) (2025)
- [Self-Distillation for Multi-Token Prediction](https://mlsanity.com/paper/2603.23911/) (2026)
- [Proxy Compression for Language Modeling](https://mlsanity.com/paper/2602.04289/) (2026)
- [A Sobering Look at Tabular Data Generation via Probabilistic Circuits](https://mlsanity.com/paper/2603.23016/) (2026)
- [MIXAR: Scaling Autoregressive Pixel-based Language Models to Multiple Languages and Scripts](https://mlsanity.com/paper/2604.11575/) (2026)
- [Scratchpad Patching: Decoupling Compute from Patch Size in Byte-Level Language Models](https://mlsanity.com/paper/2605.09630/) (2026)
- [DBLAST: Dependent Block Drafting for Stochastic Speculative Decoding](https://mlsanity.com/paper/2608.05448/) (2026)
- [Tractable Hierarchical Control of Autoregressive Language Models](https://mlsanity.com/paper/2607.20483/) (2026)
- [Dynamic Multi-Byte Prediction With Hierarchical Language Models](https://mlsanity.com/paper/2608.15454/) (2026)

## Abstract (arXiv)

Multi-token prediction (MTP) is a prominent strategy to significantly speed up generation in large language models (LLMs), especially in byte-level LLMs, which are tokeniser-free but prohibitively slow. However, many existing MTP methods either assume independence between future tokens, sacrificing expressiveness, or generate tokens one at a time within the window, increasing latency. In this work, we investigate the trade-off between expressiveness and latency in MTP within the framework of probabilistic circuits (PCs). Our framework, MTPC, allows one to explore different ways to encode the joint distributions over future tokens by selecting circuit architectures, generalising classical models such as (hierarchical) mixture models, hidden Markov models, and tensor networks. We show the efficacy of MTPC by retrofitting existing byte-level LLMs, such as EvaByte, and byte-fied subword models, such as Llama3.2 3B. Our experiments show that, when combined with speculative decoding, MTPC substantially speeds up generation compared to MTP with independence assumptions, while guaranteeing to retain the performance of the original verifier LLM. We also rigorously study the optimal trade-off between expressiveness and latency when exploring the possible parameterisations of MTPC, such as PC architectures and partial layer sharing between the verifier and draft LLMs.