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.