Chain-of-thought prompting improves mathematical reasoning, but generated reasoning chains can appear locally plausible while being globally inconsistent. Later steps may derive equations inconsistent with claims asserted earlier. We propose SAGE, a training-free decoding approach that treats symbolic consistency as probabilistic conditioning over mathematical claims, conditioning each new claim on the symbolic state accumulated from earlier steps. SAGE approximates this conditional distribution online by resampling at mathematical span boundaries: candidate continuations are parsed into formal claims and selected according to satisfiability with the accumulated symbolic state. This statement-level decoding avoids intractable token-level constrained decoding while still using solver feedback online, before a complete solution has been generated. Across MATH-500, Gaokao, and Minerva, SAGE improves LLaMA, DeepSeek, and Qwen models over temperature sampling. On MATH-500, it improves accuracy by up to 6.3% and by 3.1% on average across four models. On Gaokao and Minerva datasets, SAGE yields consistent gains across models, improving Gaokao and Minerva pass@3 by up to 2% and 3%, respectively. We release our code at https://github.com/tamannahossainkay/sage

Large Language Models (LLMs) are typically shipped with tokenizers that deterministically encode text into so-called canonical token sequences, to which the LLMs assign probability values.One common assumption is that the probability of a piece of text is the probability of its canonical token sequence.However, the tokenization of a string is not unique: e.g., the Llama2 tokenizer encodes ‘Tokens‘ as ‘[Tok,ens]‘, but ‘[Tok,en,s]‘ also represents the same text.In this paper, we study non-canonical tokenizations.We prove that, given a string, it is computationally hard to find the most likely tokenization for an autoregressive LLM, as well as to compute the marginal probability over all possible tokenizations.We then show how the marginal is, in most cases, indistinguishable from the canonical probability.Surprisingly, we then empirically demonstrate the existence of a significant amount of signal hidden within tokenization space.Notably, by simply aggregating the probabilities of non-canonical tokenizations, we achieve improvements across a range of LLM evaluation benchmarks for a variety of architectures, including transformers and state space models.