Branch-Solve-Merge Improves Large Language Model Evaluation and Generation

1 Introduction

• LLMs are used for both text generation and evaluation, but can struggle with intricate constraints and multi-dimensional quality criteria.The paper links these difficulties to lack of self-consistency and planning.Source: §1 · p. 1
• BSM uses branch, solve, and merge modules to divide tasks into parallel sub-tasks, solve them independently, and fuse their solutions.The modules are parameterized with prompts to an underlying LLM.Source: §1 · p. 1
• For constrained generation, BSM assigns branches parts of a story that satisfy subsets of constraints, then merges those parts.The paper contrasts this with models that omit concepts or produce incoherent text when handling many constraints.Source: §1 · p. 2
• The authors evaluate BSM on LLM response evaluation and constrained generation using open-source and black-box models, including LLaMA-2-chat, Vicuna, and GPT-4.The evaluation study focuses on pairwise response quality judgments.Source: §1 · p. 2
• BSM improves LLM-human agreement by up to absolute 26%, reduces position bias by up to absolute 50%, and improves story constraint satisfaction by 12%.Stories were preferred by a GPT-4 judge 93% of the time versus a zero-shot baseline; LLaMA-2-70B-chat matched or outperformed GPT-4 on many evaluation domains.Source: §1 · p. 3
• BSM is presented as a framework for planning and decomposition that can be applied to any underlying language model and potentially a wide range of tasks.The paper reports case studies using different implementations of its modules.Source: §1 · p. 3

LLM Programs and Decomposing Complex Tasks

• Prior LLM-program and decomposition work addresses complex tasks through multiple steps, while much advanced prompting focuses on sequential decomposition for reasoning problems.The paper positions BSM among LLM programs [Schlag et al., 2023; Dohan et al., 2022] and related task-decomposition work [Khot et al., 2022].Source: §2 · p. 3
• BSM instead studies parallel decompositions for LLM evaluation and constrained text generation, as a specific fixed program within Graph-of-Thoughts prompting.Unlike broader Graph-of-Thoughts programs, it does not consider refining, backtracking, or skipping graph nodes.Source: §2 · p. 3

LLM Evaluation

• LLM evaluation is used because human evaluation is difficult and expensive, but LLM evaluators can be unfair; BSM offers decomposition on top of any LLM.Prior work discusses human alignment [Ouyang et al., 2022; Bai et al., 2022a] and evaluator biases [Wang et al., 2023b; Wu and Aji, 2023].Source: §2 · p. 3

Constrained Text Generation

• Prior work finds that even GPT-4 struggles with constrained generation, and the paper tests BSM on a constrained story-generation task.The cited work discusses controllable and constrained generation [Keskar et al., 2019; Dathathri et al., 2019; Lu et al., 2021, 2022].Source: §2 · p. 3

3 BRANCH-SOLVE-MERGE

• BSM defines a controller that invokes prompted branch, solve, and merge modules to map a task instance to an output.The program is formalized as taking the task instance and module implementations as input and generating an output.Source: §3.1 · p. 4

3.1 Components of BRANCH-SOLVE-MERGE

• Branch generates multiple sub-tasks with an LLM-decided branching factor, solve independently produces a solution for each branch, and merge fuses those solutions.The merge prompt can aggregate values or combine text, depending on the task.Source: §3.1 · p. 4

3.2 BSM: Case Study with LLM Evaluation

• For pairwise response evaluation, the branch module generates criteria from the question, conditioning on both questions for turn-two cases.Each criterion includes a title and a short description of how to assess the responses.Source: §3.2 · p. 5
• The solve module evaluates both responses separately for each criterion, producing scores and explanations; the evaluation is sensitive to response order.The task compares two assistants’ answers to an open-ended question and returns a preference judgment or tie.Source: §3.2 · pp. 4–5
• The evaluation merge can sum scores across branches or use an LLM to aggregate criterion-wise evaluations into a final verdict.The program runs twice with response order swapped and returns a preference only when the judgments agree; otherwise it returns a tie.Source: §3.2 · p. 5

3.3 BSM: Case Study with Constrained Gen

• For constrained story generation, branching divides concepts into subsets and assigns a shared topic; solve writes a story per subset, and merge fuses the stories.The shared topic is intended to help the fused story remain coherent while including the concepts.Source: §3.3 · p. 5

4.1.1 Experimental Setup

• The MT-Bench evaluation compares zero-shot evaluators, Plan&Solve, and compute-matched Self-Consistency with zero-shot BSM modules using four evaluator metrics.The metrics are human agreement, position bias, length bias, and self-enhancement bias.Source: §4.1.1 · p. 6

4.1.2 Main Results

• BSM gains up to 12% absolute agreement over Plan&Solve, improves turn-2 agreement by up to 16%, and reduces position bias by up to 34%.The 12% comparison also indicates an advantage over Self-Consistency, which uses similar compute.Source: §4.1.2 · p. 7, Table 1 · p. 7
• BSM improves human agreement for all four tested base LLMs; on GPT-4 it adds 3%, while bias reductions do not hold for GPT-4.LLaMA-2-70B-chat with BSM is competitive with GPT-4 on turn-1 questions.Source: Table 3 · p. 7, §4.1.2 · p. 8
• In reference-based evaluation, BSM beats zero-shot by up to 14% agreement and improves coding position bias by 27%; on math, it beats GPT-4 on all metrics.The reference-based results cover coding, reasoning, and math categories.Source: §4.1.2 · p. 8, Table 4 · p. 8
• Tests extend beyond writing to roleplay, extraction, STEM, and humanities, where the authors report similar findings.The passage refers readers to Appendix A.2 for details.Source: §4.1.2 · p. 8
• One branch prompt generates domain-specific criteria without human intervention; branch names differ across writing and coding but overlap more within a domain.Examples include Clarity and Creativity for writing, and Efficiency and Code Readability for coding.Source: §4.1.2 · pp. 8–9

4.2.1 Experimental Setup

• The 100-sample task asks for concise stories from 10 concepts, scored for constraint coverage and GPT-4 pairwise quality with order-swapped consistency checks.Constraint coverage uses All Present and Missing Concepts metrics.Source: §4.2.1 · p. 9

4.2.2 Results and Analysis

• Both BSM variants beat constraint baselines, though 70B still omits a concept in 72% of samples; GPT-4 prefers its stories over zero-shot 93% of the time.The story preference comparison uses LLaMA-2-70B-chat with zero-shot prompting as the baseline.Source: §4.2.2 · p. 9, Table 6 · p. 9

5 Conclusion

• BSM is presented as an LLM program for improving LLM evaluation and generation.Source: §5 · p. 9
• Two case studies use different implementations of the branch, solve, and merge modules.Source: §5 · p. 9
• The case studies showcase BSM’s effectiveness and generalizability.Source: §5 · p. 9

• The paper does not evaluate safety, toxicity, or bias in LLM generations, despite their importance to holistic evaluation.Source: Limitations · p. 10
• Length bias is difficult to isolate because preference for longer responses may reflect other factors, and humans also tend to prefer them on open-ended questions.Source: Limitations · p. 10
• Recursive or multi-level BSM is left for future work because its additional base-LLM calls would increase computation cost.Source: Limitations · p. 10
• Although parallel decomposition may improve efficiency over sequential approaches, this work focuses on task performance instead.Source: Limitations · p. 10

• MT-Bench comprises 2,400 LLM responses and 3,000 expert judgments across 80 instructions in eight domains, with two turns per question.Source: §A.1 · p. 13
• Each question pairs responses from six LLMs, yielding 15 possible response pairs and 300 response-pair samples per category.Source: §A.1 · p. 13
• BSM uses greedy decoding, prompts its branch module for up to five evaluation criteria, and sums criterion-wise evaluations in a non-neural merge.Source: §A.1 · p. 13
• All methods address position bias by judging both response orders and assigning a tie when their verdicts disagree.Source: §A.1 · p. 13

• 26% absolute agreement improvement over the LLaMA-2-70B-chat baseline is reported on STEM; BSM matches GPT-4 and outperforms it on position and length biases.Source: §A.2 · p. 13
• 2% further reduction in position bias is reported for BSM+SC, while overall agreement scores do not improve further.Source: §A.2 · p. 13, Table 8 · p. 14
• Agreement is highest at branching factor 4 and mostly saturates afterward, while position bias continues to decrease as the branching factor increases.Source: §A.2 · p. 14
• Comparable agreement scores across 1–5 and 1–10 scoring scales indicate robustness to scale variation, though position bias rises slightly with the larger scale.Source: §A.2 · p. 14

• 72% of BSM stories had at least one missing concept; among those, 60% of cases were attributed to solve and 12% to merge.Source: B Additional Experiments: Constrained… · p. 14
• BSM’s branch module divides concepts and proposes a topic, solve creates an intermediate story per concept subset, and merge combines the stories while retaining concepts.Source: Figure 3 · p. 16
• The constrained-generation prompts condition branching on the concepts, solving on a concept subset and topic, and merging on intermediate stories and their concept sets.Source: Figure 6 · p. 19