UC Berkeley

This dissertation studies Large Language Model (LLM) inference through the lens of statistical decision-making theory, with the goal of advancing prevailing inference paradigms along two principal axes: scalability and provenance. In the domain of scalability, this dissertation investigates the efficiency of inference-time scaling paradigms and parallel decoding schemes. We formally characterize the sample complexity of self-consistency and best-of-n sampling methodologies, and demonstrate how self-correction can substantially expand the expressive power of Transformer architectures in multi-task settings. We analyze the information-theoretic bottlenecks associated with parallel sampling in diffusion language models, and introduce Explore-Then-Exploit, a scalable decoding strategy that improves inference throughput while preserving generation quality. In the domain of provenance, the dissertation develops theoretical foundations and practical schemes for statistical watermarking. We mathematically formalize statistical watermarking as a hypothesis-testing problem, providing a comprehensive characterization of the optimal Type II error, token efficiency, and robustness against perturbations. Guided by the theoretical insights, we propose SEAL, a semantic-aware watermarking scheme demonstrating strong detection efficiency and tamper resistance. We further generalize the statistical watermarking framework to support anytime-valid detection and derive the optimal e-value-based detection scheme. Collectively, our work connects theoretical insights with algorithmic innovations for understanding and improving the efficiency and responsible use of LLM inference.