MALT: Improving Reasoning with Multi-Agent LLM Training

• The approach targets the gap between multi-agent reasoning and role-specialized training, amid challenges from discrete outputs, scarce role-specific labels, and sparse-reward credit assignment.Source: §1 · p. 1
• MALT combines a Generator, Verifier, and Refiner in a generate-verify-refine pipeline and trains role-conditioned models using positive and negative reasoning trajectories.Source: §1 · pp. 1–2
• Value iteration attributes correct and incorrect reasoning traces to individual agents from search-tree outputs, enabling automatic post-training data creation without extra multi-agent data or an oracle policy.Source: §1 · p. 2
• 15.66%, 9.40%, and 7.42% relative boosts over a single-model baseline are reported on MATH, CSQA, and GSM8K, respectively.Source: §1 · p. 2

• Debate and orchestrated problem-solving add test-time deliberation, but prior approaches may lack role-specific training or dedicated post-trained verification (Du et al., 2024; Fourney et al., 2024).Source: §2 · p. 2
• Synthetic-data preference training has used correct and incorrect solutions (Setlur et al., 2024) and scalar-feedback filtering and fine-tuning (Singh et al., 2024) to improve reasoning.Source: §2 · pp. 2–3
• MALT unifies search, synthetic data generation, and preference-based post-training across a generator, verifier, and refinement model.Source: §2 · p. 3

• A standard chain of thought comprises natural-language reasoning steps followed by an answer, while complex solution processes can include latent iterative or corrective steps.Source: §3 · p. 3
• The multi-agent process factorizes reasoning into Generator output, Verifier feedback, and Refiner output, with the first two acting as latent meta-steps guiding the answer.Source: §3 · p. 3
• SFT uses positive demonstrations, whereas DPO learns from preferred and dispreferred outputs using a reference policy obtained through SFT and a reward-scaling hyperparameter.Source: §3 · p. 3
• Figure 1 maps training-time tree search and credit assignment to role-specific post-training, then shows three sequential test-time passes combined by majority voting.Source: §3 · p. 3, Figure 1 · p. 4

4 Method: Multi-Agent LLM Training

• Decentralized heterogeneous agents divide reasoning into sub-tasks, supporting targeted exploration and clearer credit assignment than a single joint action space.Source: §4 · p. 4

4.1 Multi-Agent Inference Setting

• The generator drafts an answer, the verifier critiques it, and the refiner combines both outputs to produce the final prediction.The final answer is extracted from the refiner output using a fixed deterministic function.Source: §4.1 · pp. 4–5

4.2 Collecting Reasoning Trajectories

• Branching-factor sampling creates n^3 generator-verifier-refiner trajectories per training example, with final refinements labeled against ground truth.The branching process yields diverse training samples and can be parallelized during inference.Source: §4.2 · p. 5
• Empirical means propagate expected correctness from downstream outputs to intermediate states, which are labeled correct above 0.5 and incorrect otherwise.The threshold prepares role outputs for SFT and DPO.Source: §4.2 · p. 6

4.3 MALT Post-training

• All three role models receive SFT, while DPO is applied only to verifier and refiner; the generator uses SFT alone because DPO did not improve performance.Training uses positive samples for SFT and correct-versus-incorrect pairs for preference updates.Source: §4.3 · p. 6

5.1 Experimental Details

• Experiments use Llama-3.1-8B-Instruct on MATH, GSM8K, and CSQA, comparing inference-only, STaR, and equal-inference debate baselines.MALT training samples 27 trajectories per question with branching factor n = 3, then applies role-specific SFT and DPO to labeled data.Source: §5.1 · p. 7

5.2 Experimental Results

• MALT achieves relative improvements of 15.66% on MATH, 9.40% on CSQA, and 7.42% on GSM8K over the untrained generator, outperforming all baselines, including equal-inference debate.The reported results use Llama-3.1-8B-Instruct; MALT also significantly outperforms the debate baseline across all three benchmarks.Source: §5.2 · p. 8, Table 1 · p. 8, Table 2 · p. 8
• On GSM-Symbolic-P1, GSM8K-trained MALT reaches 84.75 ± 3.30% accuracy, outperforming all baselines and approaching Llama-3.1-70B at 88.25 ± 2.95%.This evaluates whether the GSM8K-based setup generalizes to a more difficult benchmark.Source: §5.2 · p. 8, Table 3 · p. 8
• With majority voting, MALT’s self-consistency yields a 9.57% relative improvement on MATH, while correcting prior errors more often than it introduces mistakes.Without voting, performance remained close to the multi-agent inference-only setting.Source: §5.2 · p. 9, Figure 2 · p. 9
• On MATH, accuracy rises across MALT’s turns: 53.50% after the Generator, 55.75% after the Verifier, and 57.25% after the Refiner.The paper reports similar turn-wise increases on GSM8K and CSQA.Source: §5.2 · p. 9, Figure 3 · p. 9

5.3 Ablation studies

• Replacing any one trained agent with an untrained baseline degrades performance across all three benchmarks.For example, an untrained generator yields mean accuracies of 54.25% on MATH, 87.00% on GSM8K, and 78.75% on CSQA.Source: §5.3 · p. 9, Table 4 · p. 10
• Both two-agent variants underperform the full pipeline: generate-refine omits the Verifier, while generate-verify omits the Refiner.The paper describes the three-model pipeline as a modular entry point rather than a fixed limit on MALT’s usability.Source: §5.3 · pp. 9–10, Table 5 · p. 10
• DPO improves beyond SFT alone, while positive-only rationales can introduce spurious correlations and degrade SFT performance.The paper attributes DPO’s advantage to contrastive training on negative data that helps identify high-advantage reasoning steps.Source: §5.3 · p. 10

6 Discussion and Conclusion

• MALT bridges multi-agent inference and trained multi-agent systems by generating role-specific data through tree-based sampling and credit assignment.Negative synthetic data is used to identify and correct flawed reasoning steps during post-training.Source: §6 · p. 10
• Experiments did not expand to significantly larger models because of compute limitations.The authors also describe the three-role setup as extendable to automatically learned roles, repeated refinement, online RL, and larger branching factors.Source: §6 · p. 10
• The authors propose trusted small MALT-trained models and trained verifiers as potential tools for oversight and safety criticism.They suggest these verifiers could improve solution legibility.Source: §6 · p. 10

A.1 Algorithm

• MALT runs a Generator, Verifier, and Refiner for each question and expands their outputs into a multi-agent search tree.The algorithm takes an initial dataset, the three models, and a branching factor as inputs.Source: §A.1 · p. 14
• Value-iteration credit assignment labels branches as correct or incorrect from outcome rewards, producing role-specific training data.The algorithm records refiner rewards and binarizes verifier and generator values for their datasets.Source: §A.1 · p. 14
• The collected data trains the Generator with supervised fine-tuning and the Verifier and Refiner with preference optimization.The algorithm specifies DPO for verifier and refiner training; its stated goal is trained models G′, V′, and R′.Source: §A.1 · p. 14

A.2 Experiments with GSM-Symbolic

• GSM-Symbolic P1 adds a clause to each GSM8K-style question to test multi-step reasoning beyond the original training distribution.The evaluated MALT model was trained on the GSM8K training set.Source: §A.2 · pp. 14–15
• MALT on Llama 3.1 8B Instruct outperforms Llama 3.1 70B Instruct on GSM-Symbolic P1.The table reports results over four seeds on a random subset of GSM-Symbolic P1.Source: Table 6 · p. 15, §A.2 · p. 15

A.3 Multi-Agent Debate Baseline

• MALT significantly outperforms the equal-inference-spend multi-agent debate baseline across all three benchmarks.Table 7 presents the comparison.Source: §A.3 · p. 15, Table 7 · p. 15
• The debate baseline follows Du et al. (2024) and uses three agents debating over three rounds to match inference spend.Source: §A.3 · p. 15
• Table 7 compares MALT with a multi-agent debate baseline at equal inference spend.Source: Table 7 · p. 15

Qualitative Examples

• The section presents a synthetic example for SFT and DPO, a trained-versus-untrained verifier comparison, and a backtracking cycle that reaches a correct answer.The pump example illustrates the cycle: the generator answers “service station,” the verifier reconsiders what the pumps extract, and refinement gives “ground.”Source: §A.4 · pp. 15, 17
• The Marco-card refinement example rejects an output of 125 new cards and accepts 25, matching the stated ground-truth answer.The accepted solution calculates 125 duplicates and trades one-fifth, or 25, for new cards.Source: §A.4 · pp. 15–17
• The verifier corrects the generator’s sibling-count error, changing the answer from 3 sodas per sibling to 2.The generator treats 2 sisters as x and incorrectly concludes there are 4 siblings; the verifier identifies 4 brothers plus 2 sisters, or 6 siblings.Source: §A.4 · pp. 17–18

Reasoning and Improvement Sequence

• The generator chooses E, “service station,” by interpreting the pumps as located at a place where oil is dispensed.The answer is wrong: the ground-truth answer is D, “ground.”Source: A Complete Reasoning and Improvement… · pp. 18–19
• The verifier catches that “out of” asks for the source of the oil, shifting its interpretation from pump location to extraction source.It identifies the ground as the likely source of oil.Source: A Complete Reasoning and Improvement… · pp. 18–19
• The refiner uses the verifier’s interpretation to change the answer to D, “ground,” which matches the ground truth.The reasoning points to oil being extracted from the ground.Source: A Complete Reasoning and Improvement… · p. 19

A.5 Detailed Discussion

• DPO was chosen over PPO for offline, single-iteration training because the authors describe it as more stable and lower-overhead; tree sampling was efficient at limited depth, while MCTS remains an open choice.Handling new out-of-distribution data would require iterative rollout and post-training.Source: §A.5 · p. 19

A.6.1 Credit Assignment Strategy

• MALT models generation, verification, and refinement as a sampled three-step process, assigns binary rewards to final answers, and propagates values backward to guide role-specific SFT and DPO updates.The offline credit-assignment threshold is 0.5, which the authors describe as balancing sample efficiency and noise for a single iteration.Source: §A.6.1 · pp. 20–21

A.6.2 Policy optimizing the DPO objective is identical to Optimal RL Policy

• The authors state that optimizing DPO with binarized preferences yields the optimal RL policy under their theorem’s setup, with higher-value actions favored relative to the reference policy.They characterize this as supporting approximate monotonic improvement.Source: §A.6.2 · pp. 21–22

A.7 Additional Related Work

• MALT combines ideas from inference-time sampling, refinement, SFT, and synthetic-data preference training in an offline pipeline with separately post-trained generator, verifier, and refiner roles.The discussion contrasts this role-specialized post-training with multi-turn RL and same-model refinement approaches.Source: §A.7 · p. 22

A.8.1 Improving Multi-Agent Systems

• Online PPO, additional attribution and branching strategies, prompt tuning, and alternative roles are identified as future directions beyond this paper’s goal of introducing the methodology and demonstrating empirical performance.The authors also describe expanding beyond the Generate-Verify-Refine paradigm through orchestration and deeper search as beyond scope.Source: §A.8.1 · pp. 22–23

A.8.2 Relation to DeepSeek R1 and LLM Mid-training

• MALT is presented as complementary to single-model reasoning work: its search trajectories could supply cold-start data for instruction tuning before reinforcement learning, or its credit assignment could be used with online PPO.The online PPO option is framed as viable when more training and inference compute is available.Source: §A.8.2 · p. 23

A.9 Additional Information

• 52.25% on MATH with SFT versus 51.25% with SFT+DPO is reported for the generator; the authors attribute the decrease as likely related to overfitting on a distribution similar to prior DPO training.The experiments use zero-shot CoT prompts and an initial question-answer training set; hyperparameter exploration is left for future work.Source: §A.9 · p. 23

A.10 Limitations and Ethics Statement

• Benchmark performance can vary substantially even at low temperatures, so evaluations used random test-set subsets across four seeds; the authors also note CommonsenseQA’s potentially biased or incorrect labels.They used CommonsenseQA consistently with prior work.Source: §A.10 · p. 24