Prefix-Balanced Decoding: Optimal Occupancy under Causal Coupling

Correlated autoregressive samples can improve coverage without changing each completed sample’s marginal. That guarantee need not survive inspection of the partial batch: other lanes may reveal shared randomness and distort a selected lane’s next-token law. We study couplings that preserve every named lane’s conditional given the full public history. Prefix-balanced decoding (PBD) meets this contract by refreshing a systematic categorical coupling within exact-prefix groups. We prove that one target-free process minimizes every individual prefix count in convex order, over all history-adapted admissible couplings. More strongly, local floor/ceiling counts characterize all such universal optimizers; minimizing one positive weighted sum of prefix-count variances is sufficient to identify this entire class. A Bellman gap identity, a conditional restart theorem, and two ordering results explain the mechanism: more balancing improves occupancy on a fixed tree, whereas exposing a finer factorization can worsen the causal optimum. On finite intent decoders induced by three real language models, PBD improves pass@8 by 1.116 percentage points, recovers 99.5% of the endpoint-aligned opportunity, and retains 98.7% of the gain with four balanced levels. Under a shared adaptive budget, full PBD also improves target-free pass by 1.09 percentage points. These results connect an exact characterization of sampling dependence to effective shallow coordination under an inspection-stable contract.