Viewing LLM Inference as Statistical Decision-Making: Theory, Algorithms, and Experiments

1. Problem Statement: LLM Inference Is No Longer a Static Function

Modern LLM systems generate long reasoning chains, sample multiple candidates, use validators, perform self‑correction, and adapt strategies through tool use, which classic machine‑learning theory cannot adequately describe.

2. Test‑Time Scaling: Self‑Consistency, Best‑of‑n, and Self‑Correction

The thesis studies two fundamental questions: how many samples are needed for repeated‑sampling methods, and whether Transformers can truly improve ability through test‑time self‑correction. For mathematical reasoning tasks, self‑consistency samples multiple reasoning paths and selects the most frequent answer, while Best‑of‑n samples candidates and uses a validator to pick the highest‑scoring answer. The authors prove a sample‑complexity separation: if the probability gap between the correct answer and the second‑best answer is gap, self‑consistency requires roughly 1/gap² samples, whereas Best‑of‑n needs only 1/gap samples. Self‑correction is shown to give a Transformer the ability to perform online learning with a verifier, enabling it to identify suitable experts for a task without knowing the task identity.

Experiments on AIME 2024/2025 math reasoning show that Best‑of‑n with four samples outperforms self‑consistency with sixty‑four samples, and self‑correction raises Qwen3‑1.7B accuracy from 58.33 % to 79.29 %.

3. Diffusion Language Model Decoding: Bits‑to‑Rounds

Diffusion language models (DLMs) can generate many tokens in parallel via mask/unmask, but parallel sampling makes tokens conditionally independent, causing a mismatch with the true joint distribution. Existing methods prioritize high‑confidence tokens, which can create an information‑theoretic bottleneck because each round contributes little information.

The authors introduce a bits‑to‑rounds perspective: the number of decoding rounds is bounded by the total information divided by the information gained per round. Based on this theory they propose the Explore‑Then‑Exploit (ETE) algorithm. ETE first expands the decodable region with fast block diffusion, then strategically explores high‑information tokens (e.g., using shared KV‑cache beam search) before exploiting high‑confidence tokens in parallel.

Experiments on GSM8K, HumanEval, MATH, and MMLU‑Pro show that ETE improves the speed‑accuracy frontier, achieving up to a 70 % throughput increase at the same accuracy and sometimes higher peak accuracy.

4. Statistical Watermarking: Hypothesis‑Testing Formulation

The second half of the thesis addresses provenance: determining whether a text originates from a specific LLM. Statistical watermarks embed a signal during generation; a detector with a secret key tests whether the text falls into a random rejection region R. The framework controls Type I error (false alarm) and Type II error (missed detection).

The authors derive optimal Type II error under a Type I constraint, characterize minimax optimal model‑agnostic watermarks, and show that the token complexity needed to achieve a fixed error rate is approximately log(1/h)/h, where h is the average token entropy. Higher‑entropy (more random) text is easier to watermark and detect.

5. SEAL: Semantic‑Aware Speculative Sampling

SEAL (Semantic‑awarE speculAtive sampLing) uses a public proposal LLM to extract semantic information from the most recent K tokens, hashes it to obtain a random‑seed distribution, and then performs speculative sampling that maximally couples this distribution with the target LLM’s next‑token distribution. This embeds a statistical signal while preserving output quality.

On the MarkMyWords benchmark, SEAL outperforms baselines such as Exponential, Inverse Transform, Binary, and Distribution Shift in text quality, detection token count, and robustness to paraphrase attacks.

6. Anchored E‑Watermarking: Anytime‑Valid Detection

Traditional watermark detection waits for a fixed text length before computing a p‑value, which is unsuitable for streaming outputs. Anchored E‑Watermarking employs e‑values and sequential hypothesis testing, allowing the detector to stop early once sufficient evidence accumulates while still controlling Type I error.

The authors prove a minimax‑optimal logarithmic growth rate for evidence and give tight bounds on expected detection time. Experiments on the MarkMyWords sequential setting show that the e‑value watermark reduces required tokens to 72.0, a ~15 % improvement over SEAL’s 84.5 and nearly a 2× gain over non‑anchored baselines.

7. Unified View: Inference as Statistical Decision

The thesis emphasizes that test‑time scaling, parallel decoding, and watermark detection are all instances of statistical decision‑making under uncertainty. This explains why Best‑of‑n is more sample‑efficient than self‑consistency (verification turns probability estimation into candidate identification), why high‑confidence‑first parallel decoding can be slow (insufficient per‑round information gain), and why semantic watermarks resist paraphrase attacks (semantic information yields tighter coupling with the generation process).

8. Implications for Research and Applications

Future work should analyze the trade‑offs between sample budgets, verifier feedback, and statistical efficiency for test‑time scaling; develop feedback mechanisms that enable online‑learning‑style self‑correction; design information‑aware scheduling for diffusion decoding; and create watermark schemes that balance statistical guarantees with practical concerns such as token efficiency, text quality, model‑agnosticism, robustness to attacks, and streaming detection.