Multi-sample reasoning measures candidate coverage, the probability that at least one of K candidates is correct. However, minimizing the average loss of individual attempts does not directly optimize candidate coverage. We therefore formulate finite-K posterior learning, which trains a distribution over solver parameters to reduce the probability that all K independently generated candidates fail. To optimize this objective efficiently, we propose a Fenchel-Bregman (FB) approach that requires only one posterior draw per update, rather than the K used by direct Monte Carlo optimization. FB first uses an exact Fenchel reformulation to separate problem-specific weights from the posterior update, enabling one-draw posterior updates. It then applies a closed-form Bregman update to track these weights through an exponential running average of observed failures, reusing the same draw. We instantiate FB with IVON, a variational optimizer for Gaussian posteriors over solver parameters, yielding Fenchel-Bregman IVON (FBI). Across diverse recursive and autoregressive reasoning tasks, FBI improves candidate coverage. In a matched comparison, it achieves comparable Pass@10 using 12.3% of the direct Monte Carlo baseline's measured training time per update.
Figures & tables
Figure 1: Overview of finite- K posterior learning and FBI. Left: K independent posterior draws generate a candidate pool, and training targets the probability that all K candidates fail. Right: Fenchel reformulation enables a one-draw IVON posterior update with a fixed problem-specific weight, while Bregman tracking reuses the observed failure to update the weight for the next visit.
Figure 2: Candidate coverage across recursive and autoregressive models. (a) Pass@ K on 1,000 Maze-Hard test problems using TRM at depth 16. (b) Mean Pass@ K across five mathematical-reasoning benchmarks using Qwen3-4B-Base. FBI improves candidate coverage in both settings.
Figure 3: Performance across backbones and Bayesian methods. (a) Comparison across TRM and FPRM backbones. (b) Comparison of Bayesian methods with the TRM backbone. Bars show Pass@10, and dashed markers show selected accuracy. FB-based methods achieve higher Pass@10 than the corresponding baselines across the evaluated recursive backbones and variational optimizers.
Figure 4: Finite- K posterior learning and training efficiency. (a) The diagonal pattern shows that Ktrain=K attains the highest reported Pass@ K at each budget. Cells show Pass@ K (%); darker shades indicate higher within-column coverage. (b) Problem-specific weights outperform their minibatch-mean replacement at Ktrain=10 . (c) At Ktrain=10 , FBI achieves comparable coverage to Direct-10 using 12.3% of its measured training time per update. Resources are relative to Direct-10 (100%); FLOPs are in units of 1012 .
Figure 5: Recovery after first-candidate failures on Maze-Hard. Left: first-candidate failures are partitioned into three outcomes: only repeated initial outputs, different outputs with no exact solution, or at least one exact solution. Right: Pass@1 versus the exact-recovery rate among candidates 2–10 after each method’s first candidate fails. FBI has the highest conditional exact-recovery rate of 32.5%.
Appendix figures & tables6 assets
Supplementary material from the paper’s appendix.
Appendix
Setting
m
σ
W-PTRM, Sudoku-Extreme
0.30
0.00312003
W-PTRM, Maze-Hard
0.30
0.00202273
W-PTRM, ARC-AGI-1
0.30
0.00650025
W-PTRM, ARC-AGI-2
0.20
0.00453306
W-FPRM, Maze-Hard
0.05
0.000298018
Appendix
Table 3: Fixed-Gaussian weight-sampling controls. The variance of every sampled scalar is σ2 .
Sudoku-Extreme
Maze-Hard
Method
Acc. ↑
Pass@10 ↑
Acc. ↑
Pass@10 ↑
GRAM
98.48
98.49
87.30
87.30
FBI (Ours)
99.53
99.55
88.00
91.30
Appendix
Table 4: Additional recursive reasoning comparison. Acc. is selected accuracy, and Pass@10 is coverage among ten candidates. All values are percentages. FBI exceeds GRAM on both metrics and benchmarks.
Quantity
Value
Global batch size / GPUs
768 / 8
Dense learning rate
10−4
IVON effective sample size
100,000
IVON momentum / curvature EMA
0.9 / 0.999
IVON noise scale
1.0
Failure-score temperature / EMA coefficient
0.0625 / 0.95760
Appendix
Table 7: FPRM-based FBI training on Maze-Hard. The run uses bfloat16 forward computation, Ktrain=10 , and one posterior draw per update.
Quantity
FBI
Direct-10
Posterior draws per update
1
10
Training time/update (s)
0.0692
0.5614
Training FLOPs/update ( 1012 )
0.427
4.087
Peak allocated GPU memory (GB)
0.611
3.707
Appendix
Table 9: Matched one-GPU training-resource benchmark on Maze-Hard. Time and counted FLOPs are per update. FBI uses 12.3% of Direct-10’s time and 10.4% of its counted FLOPs.
Method
GPUs
Time/update
Memory (GB)
FLOPs/update
Pass@10
(ms)
Max/GPU
Sum
( 1012 )
(%)
FBI
1
72.4±4.6
0.611
0.611
0.427
91.3
Latent-space Direct-10
1
143.4±0.7
2.595
2.595
4.067
88.8
Appendix
Table 10: Latent-space direct-10: performance and one-GPU training resources. Pass@10 reports means over three independent training runs under the same Maze-Hard evaluation protocol. Performance is measured separately from the one-GPU resource benchmark, whose GPU count is reported in the GPUs column. Time reports the mean and sample standard deviation across three benchmark repetitions.
Figure 6: EMA and KL sensitivity of FBI on Maze-Hard. (a) varies the failure-EMA coefficient β at relative KL strength 2. (b) varies relative KL strength at β=0.9 while keeping the implied prior fixed. Selected accuracy uses the frozen prefix-Q selector, and Pass@10 measures coverage among ten posterior candidates on test set with one fixed seed. Both metrics are highest at β=0.9 in (a) and relative KL strength 2 in (b) among the tested settings.
Reinforcement Learning-based post-training of Large Language Models (LLM) has been successfully applied to improve their reasoning capabilities. Existing pipelines primarily finetune LLMs on a fixed pool of problems specified prior to training using the GRPO loss. This is fundamentally limiting, as learning signal arises only when policy rollouts mix successes and failures, causing the useful portion of any fixed pool to quickly become stale as the model improves. To address this, we propose frontier learning, an open-ended post-training approach in which procedural generators are used online to continually produce informative training problems. It treats the generator's task-specific parameters as a search space and uses a regret signal to prioritize and explore frontier difficulty levels in order to focus training at the edge of the model's evolving reasoning capabilities. Across several reasoning tasks and model families, our approach consistently achieves higher relative gains over fixed-pool baselines, demonstrating that effective post-training requires not only selecting useful problems, but continually generating them at the edge of capability.
Robin Faro, Shyam Sundhar Ramesh, Ilija Bogunovic +1
University College London London, UK · University of Basel Basel, Switzerland
Although large language models rely on chain-of-thought for complex reasoning, the overthinking phenomenon severely degrades inference efficiency. Existing reinforcement learning methods compress reasoning chains by designing elaborate reward functions, which renders high-quality samples extremely sparse in the exploration space and creates a sampling bottleneck for the prior policy. Inspired by cognitive science, we theoretically prove that a posterior distribution guided by reference answers achieves higher expected utility than the prior distribution, thus capable of breaking through the sampling bottleneck of high-quality samples. However, the posterior distribution is unavailable during inference. To this end, we formalize efficient reasoning as a variational inference problem and introduce an efficiency-aware evidence lower bound as the theoretical foundation. Based on this, we propose the VPG-EA framework. It adopts a parameter-shared dual-stream architecture to instantiate both the posterior distribution and the prior policy; after filtering out pseudo-efficient paths via cross-view evaluation, it unidirectionally transfers the posterior's efficient patterns to the prior policy through variational distillation. Experiments on DeepSeek-R1-Distill-Qwen-1.5B and 7B scales demonstrate that VPG-EA improves the comprehensive efficiency metric epsilon cubed by 8.73% and 12.37% over the strongest baselines on each model size, respectively.
Zizhao Chen, Yuying Li, Siting Lin +1
Guangdong University of Foreign Studies, Guangzhou, China.
Frontier reasoning models are produced by post-training base language models with reinforcement learning. Recent work has challenged this by showing that sampling from a sharpened version of the base model's distribution, a so-called power distribution, elicits comparable reasoning without additional training, curated datasets, or verifiers. However, making this method practical requires efficiently sampling from the power distribution. A sampler needs to "mix" to the power distribution, which necessitates moving between modes of the target distribution; intuitively, e.g., trying different reasoning strategies. The samplers proposed in prior works repeatedly select a "cut" position in the current reasoning trace uniformly at random and resample the suffix from that position onward. However, reasoning traces typically contain a few consequential decisions (e.g., the choice of proof strategy or algorithm), and we observe that a uniformly chosen cut tends to rewrite local details rather than revisit decision points. We introduce an algorithm (Entropy-Cut Metropolis-Hastings) that uses the base model's next-token entropy as a proxy to identify key decision points and resample from those positions. We empirically verify that entropy jumps are a useful proxy for decision points and, in a stylized model of reasoning, prove that our method's mixing time scales with the number of decisions in a trace rather than with the number of tokens, which can be much larger. Across MATH500, HumanEval, GPQA Diamond, and AIME26, our method consistently improves over baselines and RL-trained models, including best-of-N at the same token budget.