Branch-Solve-Merge Improves Large Language Model Evaluation and Generation (2024)

Abstract: Large Language Models (LLMs) are frequently used for multi-faceted language generation and evaluation tasks that involve satisfying intricate user constraints or taking into account multiple aspects and criteria. However, their performance can fall short, due to the model’s lack of coherence and inability to plan and decompose the problem. We propose Branch-Solve-Merge (BSM), a Large Language Model program (Schlag et al., 2023) for tackling such challenging natural language tasks. It consists of branch, solve, and merge modules that are parameterized with specific prompts to the base LLM. These three modules plan a decomposition of the task into multiple parallel sub-tasks, independently solve them, and fuse the solutions to the sub-tasks. We apply our method to the tasks of LLM response evaluation and constrained text generation and evaluate its effectiveness with multiple LLMs, including Vicuna, LLaMA-2-chat, and GPT-4. BSM improves the evaluation correctness and consistency for each LLM by enhancing human-LLM agreement by up to 26%, reducing length and pairwise position biases by up to 50%, and allowing LLaMA-2-chat to match or outperform GPT-4 on most domains. On a constraint story generation task, BSM improves the coherence of stories while also improving constraint satisfaction by 12%.

## introduction large language models (llms) are widely used for various text generation tasks @xcite @xcite @xcite . it has also become common to employ them as evaluators of such llm generations in order to assess, critique and improve the outputs @xcite . however, llms still struggle with tasks that have intricate requirements like satisfying a set of constraints or meeting objectives that * work done during an internship at meta. are, in general, multi-dimensional (e.g., evaluating the quality of generated text against certain diverse criteria). this appears to primarily stem from the model's lack of self-consistency and inability to plan @xcite . recent research has tried to mitigate these limitations by developing iterative methods that involve eliciting reasoning, planning, and refinement, but so far they are still considered as open problems @xcite @xcite @xcite @xcite . in this work, we propose branch-solve-merge (bsm), a decomposition method for solving such multi-faceted natural language tasks. our approach is an instance of a large language model program @xcite and consists of three modules: branch, solve, and merge that are parameterized with specific prompts to an underlying llm. given an arbitrary user task, the 'branch' module generates a solution plan by decomposing the task into multiple parallel subtasks, where each sub-task is represented by a unique branch, representing different components required to solve the overall problem. the 'solve' module then solves each of these independent subproblems. finally, the 'merge' module fuses the solutions to these sub-problems to generate the overall solution. we apply our method to two challenging tasks where llms are commonly utilized but their performance still lags behind humans: • evaluation of llm outputs @xcite . llms are now regularly used to perform automatic evaluation of model responses, e.g., to user queries @xcite . evaluating llms holistically is challenging because of their ability to generate long-form answers to arbitrary user questions @xcite , the lack of reliability originating from many biases @xcite @xcite , and reliance on hand-designed evalua-compose an engaging travel blog post about a recent trip to hawaii, highlighting cultural experiences and must-see attractions. relevance: assess how well the response aligns with the user's question and whether it provides relevant information about cultural experiences and mustsee attractions in hawaii. clarity: evaluate how clear and concise the response is .... ## branch-solve-merge we first introduce some notation to formally describe bsm. let p θ denote an llm with parameters θ. we also denote @xmath0,•••,n as a sequence of n tokens, such that p θ (x) = n @xmath1,•••,i-1 ). bsm is an llm program that aims to solve complex planning-based tasks with three neural mod-ules: branch, solve, and merge. each module is parameterized with unique prompts to the llm p θ . the llm program further defines an algorithm on top of these modules, acting as a controller and invoking a module at each step of the algorithm. ## conclusion we presented bsm, an llm program for improving llm evaluation and generation. we conducted two case studies with different implementations of branch, solve, and merge modules, showcasing the effectiveness and generalizability of bsm.