Martingale Foresight Sampling: A Principled Approach to Inference-Time LLM Decoding

Huayu Li, Zhengxiao He, Siyuan Tian, Jinghao Wen, Ao Li

TL;DR

This paper introduces Martingale Foresight Sampling (MFS), a new LLM decoding framework that replaces ad-hoc heuristics with principled probability theory. MFS models reasoning paths as stochastic processes, using Martingale theory to guide step valuation, path pruning, and early stopping, leading to improved accuracy and efficiency on reasoning tasks.

What Problem Does This Paper Address?

Large Language Models (LLMs) often struggle with complex reasoning because their standard autoregressive decoding is "short-sighted." They generate text token by token, making locally optimal choices without a clear understanding of long-term consequences. This can lead to suboptimal reasoning paths, even if they seem promising initially. While existing "foresight sampling" methods try to look ahead by simulating future steps, they rely on heuristic rules for deciding which paths are good and which to discard. This ad-hoc approach limits their robustness and theoretical grounding, making it hard to understand why they work or how to systematically improve them. The paper aims to bridge this gap by developing a principled, theoretically sound framework for inference-time LLM decoding.

Methods

MFS reframes LLM decoding not as a search problem to be solved with heuristics, but as the challenge of identifying an optimal stochastic process. The core idea is to model the "quality" of a reasoning path over time as a stochastic process and leverage Martingale theory.

Here's how MFS achieves this:

  • Principled Step Valuation (Doob Decomposition Theorem): Instead of heuristic scores, MFS uses the Doob Decomposition Theorem to measure a path's "predictable advantage." This score quantifies the expected increase in the path's quality, providing a theoretically grounded way to value each step.
  • Optimal Path Pruning (Optional Stopping Theory): MFS employs Optional Stopping Theory to decide when to prune suboptimal paths during beam search. This ensures computational resources are focused on promising candidates by leveraging the properties of martingales at stopping times.
  • Adaptive Stopping Rule (Martingale Convergence Theorem): The framework uses an adaptive stopping rule based on the Martingale Convergence Theorem. This rule terminates the expensive foresight process as soon as a path's quality is provably converged, preventing wasted computation.
  • Martingale Foresight Sampling (MFS) Algorithm: The paper presents a concrete algorithm that implements these principled concepts, integrating them into a coherent decoding strategy.

Datasets

The paper evaluates MFS on six reasoning benchmarks:

  • GSM8K (mathematical word problems)
  • MATH-500 (competition-level mathematics)
  • GPQA (graduate-level factual reasoning)
  • ReClor (logical reasoning)
  • LogiQA (logical reasoning)
  • ARC-Challenge (common-sense multiple-choice evaluation)

No new benchmarks were introduced.

Key Insights and Ideas

  • Martingales as a Framework for Reasoning: The core insight is that reasoning paths can be modeled as favorable games (submartingales) where quality is expected to increase. This probabilistic framing provides a powerful lens for understanding and optimizing LLM decoding.
  • Theory Over Heuristics: The paper demonstrates that fundamental probability theorems (Doob Decomposition, Optional Stopping, Martingale Convergence) can directly replace ad-hoc heuristics in LLM decoding, leading to more robust and interpretable algorithms.
  • Predictable Advantage as a Unified Metric: Using the Doob Decomposition to derive a single "predictable advantage" score elegantly replaces the combined heuristic scores (like Advantage + Alignment) used in prior work, simplifying and grounding the valuation process.
  • Early Stopping is Crucial for Efficiency and Accuracy: The adaptive stopping rule, derived from Martingale Convergence, not only saves computation but also actively prevents "overthinking," which can introduce noise and degrade accuracy.

Key Results

MFS consistently outperforms state-of-the-art methods on six reasoning benchmarks, achieving higher accuracy while significantly improving computational efficiency.

  • Accuracy: On LLaMA3.1-8B-Instruct, MFS achieved an average accuracy of 60.21, a 34.1% relative improvement over Auto-Regressive (CoT). It also surpassed the previous state-of-the-art, φ-Decoding.
  • Efficiency: MFS required 4.38 × 10¹⁷ FLOPS on LLaMA3.1-8B-Instruct, making it 31.9% more efficient than φ-Decoding and over 35% more efficient than MCTS.
  • Generalization: MFS showed strong performance on the Qwen2.5-3B-Instruct model, improving ReClor by +10.18 and ARC-c by +7.58 over the baseline, demonstrating robustness across different architectures.
  • Ablation Studies: Removing the martingale-based early stopping or optional path selection significantly increased FLOPS (by 36.8% or more) and, in some cases, degraded accuracy, highlighting the importance of these principled components.

Limitations and Future Work

  • Convergent Reasoning Focus: MFS's theoretical foundation relies on the Martingale Convergence Theorem, which guarantees stabilization towards a correct answer. This makes it ideal for tasks like mathematics and symbolic logic but less suitable for open-ended or creative generation where diversity and stylistic quality are paramount.
  • Inherent Foresight Cost: While MFS is more efficient than many search-based methods, it still incurs overhead from simulating future rollouts. The adaptive stopping rule mitigates this, but the foresight cost remains a constraint.
  • Dependence on Base Model Foresight: The effectiveness of MFS hinges on the quality of the base LLM's foresight probability estimates. If the LLM is poorly calibrated or generates weak signals, the advantage estimation and pruning decisions may be compromised. Improving foresight calibration is a key future direction.
  • Long-Form, Multi-Turn Tasks: The current empirical evaluation focuses on structured reasoning benchmarks. The behavior of MFS on long-form, multi-turn tasks remains unexplored.

Summary updated

Abstract

Standard autoregressive decoding in large language models (LLMs) is inherently short-sighted, often failing to find globally optimal reasoning paths due to its token-by-token generation process. While inference-time strategies like foresight sampling attempt to mitigate this by simulating future steps, they typically rely on ad-hoc heuristics for valuing paths and pruning the search space. This paper introduces Martingale Foresight Sampling (MFS), a principled framework that reformulates LLM decoding as a problem of identifying an optimal stochastic process. By modeling the quality of a reasoning path as a stochastic process, we leverage Martingale theory to design a theoretically-grounded algorithm. Our approach replaces heuristic mechanisms with principles from probability theory: step valuation is derived from the Doob Decomposition Theorem to measure a path’s predictable advantage, path selection uses Optional Stopping Theory for principled pruning of suboptimal candidates, and an adaptive stopping rule based on the Martingale Convergence Theorem terminates exploration once a path’s quality has provably converged. Experiments on six reasoning benchmarks demonstrate that MFS surpasses state-of-the-art methods in accuracy while significantly improving computational efficiency. Code will be released at https://github.com/miraclehetech/EACL2026-Martingale-Foresight-Sampling.
BibTeX
@inproceedings{li2026martingale,
  author = {Huayu Li and Zhengxiao He and Siyuan Tian and Jinghao Wen and Ao Li},
  title = {{Martingale Foresight Sampling: A Principled Approach to Inference-Time LLM Decoding}},
  booktitle = {EACL (Volume 1: Long Papers)},
  year = {2026},
  url = {https://openreview.net/forum?id=egejd2N4Wi},
}
Figure