PaperlayerView exact revision on arXiv

Source-linked AI summary

MS-TTRL: Breaking the Frequency Conflict in Multiple-Solution Test-Time Reinforcement Learning

Zhixia Zhang, Binqian Xu, Huaiyang Wang, Yikun Ban, Dianbo Liu

arXiv:2610.32234v1cs.LG

TL;DR

Multiple-solution reasoning can make exhaustive annotation costly, while generation frequency favors common outcomes for correctness and rare ones for diversity. MS-TTRL estimates correctness through outcome-level self-verification and reserves frequency for diversity, improving Recovery Rate over the best label-free baseline while approaching supervised IPS-GRPO.

  • Problem

    Multiple-solution problems can have many valid outcomes, making exhaustive annotation costly, while generation frequency gives conflicting signals for correctness estimation and outcome diversity.

    Source: §1 · pp. 1–2

  • Method

    MS-TTRL uses outcome-level self-verification for correctness and generation frequency for diversity, with a three-state cache and confidence-gated inverse-probability scaling.

    Source: §1 · pp. 2–3

  • Results

    Recovery Rate improves by an average of 19.13 percentage points over the best-performing label-free baseline, approaching supervised IPS-GRPO performance across the evaluated settings.

    Source: §1 · p. 3

  • Takeaways & Limitations

    Across four tasks and three backbones, decoupling correctness estimation from diversity preservation improves valid-outcome coverage without requiring complete solution annotations during training.

    Source: §6 · p. 9

    Across the three HypoSpace tasks, MS-TTRL requires approximately 23.2% more total training time than TTRL, with nearly unchanged peak GPU memory.

    Source: §5.2 · p. 6

Abstract

from arXiv · show

Scientific, engineering, and mathematical reasoning tasks can admit multiple valid solutions, while exhaustive annotation of the full solution set is often prohibitively costly. Test-time reinforcement learning (TTRL) applies reinforcement learning to unlabeled test instances, offering a label-free approach to multiple-solution reasoning. In this setting, generation frequency serves two opposing objectives: correctness estimation favors frequent outcomes, whereas outcome-level diversity preservation favors less frequent outcomes. We term this tension the \textbf{Frequency Conflict}. To resolve this conflict, we propose MS-TTRL, which obtains frequency-independent correctness estimates through Outcome-Level Self-Verification while reserving generation frequency solely for diversity preservation. Three-State Outcome Cache and the Candidate State support verification reuse across repeated observations and confidence-aware handling of ambiguous outcomes, while Confidence-Gated Inverse Probability Scaling selectively strengthens the learning signals of rare, reliably verified outcomes. Experiments across two benchmarks, four multiple-solution tasks, and three backbone models, each evaluated with five random seeds, show that MS-TTRL improves Recovery Rate by 19.13 percentage points on average over the best-performing label-free baseline and approaches the performance of the supervised IPS-GRPO.

1 INTRODUCTION

Multiple-solution reasoning makes exhaustive annotation costly, while generation frequency can favor common outcomes for correctness and rare outcomes for diversity. MS-TTRL separates these roles with self-verification and confidence-aware diversity weighting, improving Recovery Rate over label-free baselines.

1 INTRODUCTION

  • In multiple-solution reasoning, frequency favors common outcomes for correctness but rare outcomes for diversity, and rarity alone cannot distinguish valid alternatives from errors.The paper names this tension the Frequency Conflict.Source: §1 · pp. 2–3
  • Outcome-Level Self-Verification estimates correctness independently, leaving generation frequency to measure rarity and support diversity reweighting.Independent verification trials assess whether a candidate outcome is consistent with the problem's evidence, rules, and constraints.Source: §1 · pp. 2–3
  • MS-TTRL combines frequency-independent outcome verification, a cache with confidence-aware handling of ambiguous outcomes, and gated diversity reweighting.The Candidate State retains ambiguous outcomes, assigns soft rewards based on verification confidence, and re-verifies them when problems recur.Source: §1 · pp. 2–3
  • Recovery Rate improves by an average of 19.13 percentage points over the best label-free TTRL baseline, approaching supervised IPS-GRPO performance.Evaluations cover four multiple-solution tasks, two benchmarks, three backbone models, and five random seeds.Source: §1 · p. 3

2 RELATED WORK

The related work distinguishes trajectory diversity in single-solution reasoning from outcome diversity in multiple-solution reasoning. MS-TTRL addresses multiple-solution TTRL without ground-truth labels or a reliable external verifier by separating correctness estimation from frequency-based diversity preservation.

2 RELATED WORK

  • Prior TTRL methods primarily target single-solution reasoning, using self-generated supervision and sampled-response agreement to construct rewards.They improve pseudo-label reliability and balance exploration with exploitation.Source: §2 · p. 3
  • Trajectory-diversity methods promote alternative reasoning paths toward the same final answer, but do not by themselves ensure coverage of distinct valid outcomes.The related work describes Pass@K optimization and exploration-enhancing objectives as examples.Source: §2 · p. 3
  • Multiple-solution outcome-diversity methods promote distinct valid outcomes through inverse-probability scaling, distribution matching, or multi-answer objectives, relying on reliable correctness signals.MS-TTRL studies this setting without ground-truth labels or a reliable external verifier.Source: §2 · p. 3

3 FREQUENCY CONFLICT BETWEEN CORRECTNESS AND DIVERSITY

Frequency-based TTRL rewards the most frequent observed outcome as a correctness pseudo-label, while inverse-frequency weighting favors underrepresented outcomes for diversity. Because rarity alone cannot identify valid alternatives, the paper formalizes the conflict and motivates frequency-independent correctness estimates.

3 FREQUENCY CONFLICT BETWEEN CORRECTNESS AND DIVERSITY

  • The formulation considers each problem's valid-outcome set and the observed outcomes induced by mapping sampled responses to outcomes.The observed set is the basis for comparing frequency-based correctness and diversity scores.Source: §3 · p. 3
  • Frequency-based TTRL uses the most frequent outcome as a correctness pseudo-label, whereas inverse-frequency weighting favors underrepresented outcomes for diversity.The latter promotes coverage when applied to valid outcomes.Source: §3 · p. 3
  • The Frequency Conflict is present when a more frequent outcome receives at least as much correctness preference while a less frequent outcome receives at least as much diversity preference.The definition compares outcomes with different observed frequencies for the same problem.Source: §3 · p. 4
  • An observed outcome less frequent than the selected mode receives a zero correctness score but a higher diversity score, leaving rarity unable to distinguish valid alternatives from errors.The paper reports that extending pseudo-label selection to the top-k outcomes does not alleviate this conflict.Source: §3 · p. 4

4 METHOD

MS-TTRL separates correctness estimation from frequency-based diversity preservation. It verifies outcomes, reuses resolved judgments while buffering ambiguous ones, and selectively scales rewards for verified-correct rare outcomes.

4 METHOD

  • MS-TTRL separates correctness estimation through self-verification from frequency-based diversity reweighting.Figure 2 illustrates how the components interact; Algorithm 1 gives the complete training procedure.Source: §4 · p. 4, §4.1 · p. 4

4.1 OUTCOME-LEVEL SELF-VERIFICATION

  • Reverse reasoning checks each distinct final outcome against conditions implied by the task, and its verification pass rate estimates correctness.The same model acts as verifier and actor, evaluating outcomes rather than full responses or intermediate reasoning.Source: §4.1 · pp. 4–5

4.2 THREE-STATE OUTCOME CACHE

  • The persistent problem–outcome cache reuses resolved correct and wrong states, while candidates remain unresolved and are re-verified.Candidate outcomes retain soft rewards from their latest verification scores, buffering against premature acceptance or rejection.Source: §4.2 · p. 5

4.3 CONFIDENCE-GATED INVERSE PROBABILITY SCALING

  • Inverse-probability scaling strengthens signals only for correct outcomes, while candidates retain soft rewards and wrong outcomes receive zero.The coefficient λ interpolates between full IPS (λ = 0) and the unscaled base reward (λ = 1); gating avoids amplifying low-frequency candidate verification noise.Source: §4.3 · p. 5

5 EXPERIMENTS

MS-TTRL is evaluated on four multiple-solution tasks, with comparisons to label-free baselines and a supervised reference. Results and analyses cover performance, component ablations, hyperparameter sensitivity, frequency-based pseudo-labeling, and learning signals for rare valid outcomes.

5.1 EXPERIMENTAL SETUP

  • The evaluation covers three HypoSpace tasks and MACE-Math, with complete solution sets reserved for evaluation and five-seed results across the specified backbones.IPS-GRPO receives ground-truth correctness labels as a supervised reference; label-free methods do not.Source: §5.1 · p. 6

5.2 MAIN RESULTS

  • Across HypoSpace tasks and backbones, MS-TTRL beats both label-free baselines in RR and ORR; on MACE-Math, it gains 9.87 percentage points in RR and 11.99 in ORR over the stronger baseline.Across three HypoSpace tasks, training takes approximately 23.2% longer than TTRL, with nearly unchanged peak GPU memory.Source: §5.2 · p. 6, Table 2 · p. 7
  • TTRL and TTRL-CoCoV can approach perfect accuracy on 3D while collapsing to a dominant outcome, and trajectory-level diversity alone does not prevent outcome-level collapse.TTRL-CoCoV is faster than MS-TTRL on Causal and 3D, and matches its reported Boolean runtime.Source: §5.2 · p. 7

5.3.1 ABLATION STUDY

  • The cache reduces self-verification samples by 75.9% overall and 96.1% in the final epoch across the three tasks.Reusing resolved outcome states reduces repeated self-verification and its additional inference cost.Source: §5.3.1 · p. 7, Figure 3 · p. 7
  • On Causal, retaining uncertain outcomes yields 93.75% accuracy and 45.89% RR, versus 74.80% accuracy and 41.79% RR with the midpoint threshold.Raising a fixed threshold improves accuracy but reduces coverage; lowering it has the opposite trade-off. Ungated inverse-frequency scaling reduces accuracy from 93.75% to 59.59%.Source: §5.3.1 · pp. 7–8, Table 4 · p. 8

5.3.2 HYPERPARAMETER SENSITIVITY ANALYSIS

  • Eight verification trials balance reliability and cost: Causal recovery improves from four to eight trials, while four trials already give near-optimal recovery on 3D.On 3D, moderate scaling with λ = 0.9 gives the best tested recovery; disabling IPS reduces Recovery Rate from 28.39% to 10.35%.Source: §5.3.2 · p. 8, Table 6 · p. 8, Table 7 · p. 9

5.4 EMPIRICAL ANALYSIS OF THE FREQUENCY CONFLICT

  • Expanding TTRL pseudo-labels to the top-k outcomes sharply degrades Causal and 3D accuracy without reliably improving coverage, while Boolean shows an accuracy–coverage trade-off.The Self-Verify variant improves coverage over TTRL while maintaining high accuracy, supporting separation of correctness estimation from frequency-based diversity weighting.Source: §5.4 · p. 9, Table 8 · p. 9

5.5 LEARNING SIGNALS FOR RARE VALID OUTCOMES

  • Across all three HypoSpace tasks, MS-TTRL maintains positive Mean Advantage and gives most rare valid outcomes positive advantages, whereas TTRL and TTRL-CoCoV tend to suppress them.Supervised IPS-GRPO also promotes rare valid outcomes.Source: §5.5 · p. 9

6 CONCLUSION

The paper concludes that MS-TTRL separates correctness estimation from diversity preservation and improves recovery over label-free baselines across its evaluated settings. Its algorithm reuses outcome states and updates the policy with GRPO.

6 CONCLUSION

  • Across four tasks, three backbone models, and five random seeds, MS-TTRL consistently improves recovery over label-free baselines while approaching supervised IPS-GRPO.The paper concludes that decoupling correctness estimation from diversity preservation can improve valid-outcome coverage without complete solution annotations during training.Source: §6 · p. 9

A MS-TTRL ALGORITHM

  • Outcome caches persist across problem visits, and only newly observed outcomes and cached candidates are self-verified.The algorithm summary identifies stored verification states as a means of reusing prior results.Source: A MS-TTRL ALGORITHM · p. 14
  • Algorithm 1 takes an unlabeled problem set, rollout and verification budgets, outcome-state thresholds, an IPS coefficient, and an update budget.It samples responses, assigns rewards according to outcome state, then computes group-normalized advantages and updates the policy with GRPO.Source: A MS-TTRL ALGORITHM · p. 14

B DATASET DETAILS

The dataset section describes three HypoSpace tasks and the MACE mathematical reasoning subset, each with multiple valid outcomes. It also specifies that ground-truth labels are withheld from label-free methods during training.

HypoSpace: Causal Discovery

  • Causal Discovery tests recovery of multiple DAGs consistent with intervention observations; the finite admissible set is exhaustively enumerated for evaluation.The task uses 300 training problems and 92 evaluation problems.Source: B DATASET DETAILS · p. 14

HypoSpace: 3D Structure Reconstruction

  • 3D Structure Reconstruction asks for voxel structures consistent with a top-view projection and support constraint, with all valid assignments exhaustively enumerated.The task uses 100 training problems and 29 evaluation problems.Source: B DATASET DETAILS · p. 14

HypoSpace: Boolean Expression Discovery

  • Boolean Expression Discovery asks for expressions consistent with partial observations, using expressions up to depth two and canonical deduplication.The task uses 50 training problems and 28 evaluation problems.Source: B DATASET DETAILS · pp. 14–15

MACE: Mathematical Reasoning

  • MACE-Math questions ask for a number satisfying a specified property within an interval, and the benchmark provides the complete set of valid answers.Training uses 250 problems with exactly six valid answers; evaluation samples 100 problems from each group defined by valid-answer count.Source: B DATASET DETAILS · p. 15

Dataset protocol

  • All methods use the same training split, but ground-truth labels are available only to supervised IPS-GRPO and withheld from label-free methods.Evaluation uses a held-out test split.Source: B DATASET DETAILS · p. 15

C TRAINING AND EVALUATION DETAILS

The supplied passages cover shared training and evaluation settings, prior work on test-time reinforcement learning and diversity, and accuracy reporting. They frame MS-TTRL around preserving distinct valid outcomes while estimating correctness without relying on frequency.

C TRAINING AND EVALUATION DETAILS

  • Training uses eight sampled responses per prompt, while MS-TTRL uses eight verification samples for unresolved outcomes and gives candidates their verification pass rate as a soft reward.Evaluation reports trajectory-level accuracy, Recovery Rate, and Outcome Recovery Rate under a shared response budget.Source: C TRAINING AND EVALUATION DETAILS · p. 15

D.1 TEST-TIME REINFORCEMENT LEARNING

  • Most existing TTRL methods keep generation frequency central to pseudo-labeling or confidence estimation and mainly target single-solution reasoning.The paper distinguishes its multiple-solution setting, where correctness estimation must coexist with outcome-level diversity preservation.Source: §D.1 · pp. 15–16

D.2 TRAJECTORY-LEVEL DIVERSITY

  • Trajectory-level diversity methods broaden exploration among reasoning paths, but those paths can still converge to the same terminal outcome.The cited background distinguishes Pass@K-style coverage of reasoning trajectories from coverage of distinct final answers.Source: §D.2 · p. 16

D.3 OUTCOME-LEVEL DIVERSITY

  • In the paper's setting, frequency simultaneously indicates likely correctness and outcome underrepresentation, although training has neither ground-truth solutions nor a reliable external verifier.Prior outcome-diversity approaches share an assumption that reliable correctness signals are available before diversity is promoted.Source: §D.3 · p. 16

E.1 ACCURACY REPORT

E.2 TRAINING DYNAMICS

On Causal, 3D, and Boolean, TTRL and TTRL-CoCoV improve accuracy while RR and ORR decline later in training. The evaluation metrics capture complementary views of valid-solution coverage.

E.2 TRAINING DYNAMICS

  • TTRL and TTRL-CoCoV improve accuracy but show later declines in Recovery Rate and Outcome Recovery Rate across Causal, 3D, and Boolean.The training-dynamics figure plots accuracy, recovery rate, and outcome recovery rate for these three tasks.Source: §E.2 · p. 17, Figure 5 · p. 18

F.1 EVALUATION METRICS

  • Recovery Rate averages each problem’s fraction of valid solutions recovered, giving every problem equal weight.Evaluation sampling budgets are matched across methods and based on the maximum number of valid solutions admitted by a problem.Source: §F.1 · p. 17
  • Outcome Recovery Rate aggregates recovered valid solutions across the dataset, weighting problems with larger solution sets more heavily.The two metrics typically show similar trends while emphasizing per-problem and aggregate solution-space coverage, respectively.Source: §F.1 · pp. 17–18

F.2 MAIN RESULTS AND EFFICIENCY

MS-TTRL improves valid-outcome coverage over label-free baselines across HypoSpace tasks and also improves results on MACE-Math. Its gains persist across models and seeds, with moderate additional training time.

F.2 MAIN RESULTS AND EFFICIENCY

  • MS-TTRL substantially outperforms TTRL and TTRL-CoCoV on both RR and ORR across all three HypoSpace tasks, and improves both metrics on MACE-Math.The MACE-Math result indicates generalization beyond HypoSpace to an independent multiple-solution reasoning benchmark.Source: §F.2 · p. 18
  • The gains persist across Qwen3-1.7B and Qwen3-8B, Qwen and Phi model families, and five random seeds.The study emphasizes valid-outcome coverage, reporting RR and ORR in the main table and using accuracy mainly for diagnostic analyses.Source: §F.2 · p. 18
  • MS-TTRL adds approximately 23.2% wall-clock training time over TTRL, while peak GPU memory remains nearly unchanged.It is faster than TTRL-CoCoV on Causal and 3D and matches its reported runtime on Boolean; cache reuse amortizes repeated verification.Source: §F.2 · p. 18
  • TTRL and TTRL-CoCoV can achieve near-perfect trajectory-level accuracy while producing only a small subset of valid outcomes.On 3D Structure Reconstruction, specified model-method configurations effectively produce a single dominant outcome despite correct answers.Source: §F.2 · pp. 18–19
  • TTRL-CoCoV’s trajectory exploration yields limited RR and ORR gains over TTRL in most model-task configurations.Diversifying reasoning paths that converge to the same answer does not necessarily broaden coverage of distinct valid outcomes.Source: §F.2 · p. 19
  • MS-TTRL remains competitive with supervised IPS-GRPO and occasionally achieves higher recovery without ground-truth solutions during training.The authors suggest exact correctness labels may add limited recovery benefit on tractable tasks where preserving diversity is the main challenge; soft rewards for uncertain outcomes can also introduce noise.Source: §F.2 · p. 19

F.3 COMPONENT ABLATIONS

The ablations support verification reuse, uncertainty retention, and confidence-gated scaling, while sensitivity analyses show that verification and scaling require balanced settings.

F.3 COMPONENT ABLATIONS

  • The cache reduces self-verification samples by 75.9% across three tasks and by 96.1% in the final epoch.Reusing stored verification states avoids redundant checks of previously resolved outcomes.Source: §F.3 · p. 19
  • Without the Candidate Set, a single binary threshold forces an accuracy–coverage trade-off: higher thresholds reduce RR and ORR, while lower thresholds reduce accuracy.The uncertainty buffer retains ambiguous outcomes until further verification evidence is available, avoiding forced immediate classification.Source: §F.3 · p. 19
  • Removing the Gated IPS condition sharply reduces Causal accuracy because vanilla IPS can amplify positive rewards assigned to low-frequency incorrect outcomes.Gated IPS restricts amplification to outcomes verified with sufficiently high confidence.Source: §F.3 · p. 19

F.4 HYPERPARAMETER SENSITIVITY

  • On Causal Discovery, increasing verification trials from 4 to 8 improves RR and ORR, with a smaller additional RR gain at 16 trials; four trials nearly suffice on 3D reconstruction.Marginal benefit diminishes after a sufficient budget, and verification incurs inference cost.Source: §F.4 · pp. 19–20
  • Increasing τlow to 0.625 noticeably reduces both recovery metrics, while decreasing it to 0.375 causes little degradation; τhigh variation has minor effects.Prematurely assigning uncertain valid outcomes to the Wrong Set can suppress their generation probability when cached states and zero rewards are reused.Source: §F.4 · p. 20
  • Setting the Gated IPS coefficient λ to 1.0 substantially reduces RR and ORR, while overly aggressive scaling also deteriorates performance.The authors report that λ around 0.9 best balances reliable correctness signals and promotion of underrepresented valid outcomes.Source: §F.4 · p. 20

F.5 FREQUENCY CONFLICT ANALYSIS

Expanding frequency-based pseudo-labels shifts rather than resolves the tension between correctness and coverage. MS-TTRL instead separates self-verification from frequency-based diversity signals, and its prompts illustrate candidate generation and checking.

F.5 FREQUENCY CONFLICT ANALYSIS

  • Expanding the positive pseudo-label set does not reliably preserve both correctness and coverage, producing optimization collapse on Causal and 3D and an accuracy–coverage trade-off on Boolean.On Causal and 3D, accuracy falls as k increases; on Boolean, larger k improves coverage while increasing the chance of rewarding low-frequency invalid outcomes.Source: §F.5 · p. 20
  • Changing k shifts the boundary between excluding rare valid outcomes and admitting rare invalid ones; self-verification supplies an independent correctness signal while frequency is reserved for diversity.A minimal version using n independent verification trials per outcome improves coverage while maintaining high accuracy.Source: §F.5 · p. 20

F.6 LEARNING SIGNALS FOR RARE VALID OUTCOMES

  • Across Causal, 3D, and Boolean, MS-TTRL gives rare valid outcomes positive Mean Advantage and gives most of them positive advantages.TTRL and TTRL-CoCoV instead show a suppressive effect; supervised IPS-GRPO also consistently promotes these outcomes and serves as a reference upper bound.Source: §F.6 · p. 21

G.1 CAUSAL TASK INPUT PROMPT

  • The Causal Discovery prompt asks the policy model to produce a DAG from perturbation observations under node, cycle, and edge-count constraints.The appendix provides task and verifier prompts plus a representative verifier response to make the procedure concrete.Source: G PROMPT TEMPLATES AND… · p. 21, §G.1 · p. 21

G.2 SELF-VERIFICATION PROMPT

  • The verifier prompt checks one candidate graph against perturbation observations, while explicitly allowing that multiple candidates may be valid.It asks for reasoning through reachability and a final True-or-False verification result.Source: §G.2 · p. 22

G.3 REPRESENTATIVE SELF-VERIFICATION OUTPUT

  • In the example, the verifier finds the candidate graph inconsistent with the observations, including for perturbations of B, C, and D.The response compares predicted descendant values with the observed values for each perturbation.Source: §G.3 · p. 23

Related papers

Loading 2610.32234v1…