LOGIT-PATH TRACING: EXACT GREEDY DECODING PARTITIONS OF LANGUAGE MODELS UNDER AFFINE LOGIT CONTROLS

Many language-model decoding methods expose continuous parameters, such as guidance scales and objective weights. We study settings in which token logits are affine in these parameters and ask which greedy outputs occur anywhere in the control domain. Finite sampling can detect observed outputs but cannot certify the absence of unobserved output cells. Under greedy decoding, affine token logits form an upper envelope whose intersections partition the parameter domain into regions with a constant next-token prediction. We introduce Logit-Path Tracing (LPT), which recursively constructs these regions and verifies their winners against the full vocabulary. Because pairwise logit gaps are affine, vertex verification certifies each polyhedral cell, yielding the complete greedy decoding partition under exact arithmetic. For finite-precision logits, we extend LPT with ε-robust certification, using a pairwise-gap error tolerance to separate certified and unresolved regions. We evaluate three base models on 200 test prompts over one- and two-dimensional control domains, with the pairwise-gap tolerance calibrated on a separate set of 100 prompts. LPT constructs the complete greedy decoding partition, with a mean of 5.23–10.36 output cells per prompt in one dimension and 18.82–68.30 in two dimensions. Using these complete partitions as reference, finite sampling observes only 45.0–87.9% of the output cells under matched execution time and 33.9–63.1% under matched model-evaluation budgets.