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

Introduction

Large Language Models (LLMs) are widely used for various text generation tasks (Radford et al., 2019; Brown et al., 2020; OpenAI, 2023b; Chowdhery et al., 2022; Touvron et al., 2023). It has also become common to employ them as evaluators of such LLM generations in order to assess, critique and improve the outputs (Zheng et al., 2023; Bai et al., 2022b). However, LLMs still struggle with tasks that have intricate requirements like satisfying a set of constraints or meeting objectives that 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 (Yao et al., 2023b; Bubeck et al., 2023). 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 (Bai et al., 2022b; Madaan et al., 2023; Ganguli et al., 2023; Yao et al., 2023c; Chen et al., 2023; Li et al., 2023; Huang et al., 2023).

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 (Schlag et al., 2023; Dohan et al., 2022) 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 sub-tasks, 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 sub-problems. 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 (Zheng et al., 2023). LLMs are now regularly used to perform automatic evaluation of model responses, e.g., to user queries (Dubois et al., 2023). Evaluating LLMs holistically is challenging because of their ability to generate long-form answers to arbitrary user questions (Zheng et al., 2023), the lack of reliability originating from many biases (Zheng et al., 2023; Wu & Aji, 2023; Wang et al., 2023b), and reliance on hand-designed evaluation plans that impact the method’s ability to generalize, introducing unintended human biases (Liu et al., 2023; Wu & Aji, 2023). BSM can be applied to this task by each branch assessing different aspects and criteria that require evaluation.Subsequently, we will refer to the task of ‘LLM Evaluation’ for short. In the scope of our experimental study, this will involve the pairwise evaluation of the response quality of two LLM outputs.

Constrained Text Generation. State-of-the-art LLMs struggle with constrained text generation tasks, for example the constraint of writing a story that should include several concepts. Models commonly either violate constraints, or else generate text that is incoherent in order to satisfy these constraints (Bubeck et al., 2023; Yao et al., 2023a). BSM can be applied to this task by each branch writing part of the story satisfying only some of the constraints, followed by a final merge.

We apply Branch-Solve-Merge to both these problems, see Figure 1 and Figure 3, and evaluate its effectiveness with multiple open-source and black-box LLMs of varying sizes and strengths including LLaMA-2-7B-chat (Touvron et al., 2023), Vicuna-33B (Chiang et al., 2023), LLaMA-2-70B-chat (Touvron et al., 2023), and GPT-4 (OpenAI, 2023b). BSM significantly improves both tasks, helping address the aforementioned limitations of LLM evaluation and generation:

BSM improves correctness of LLM evaluation. In particular, on the MT-Bench benchmark (Zheng et al., 2023), BSM improves LLM-human agreement for evaluating multi-turn questions belonging to different domains including writing, coding, reasoning, and mathematics. For example, compared to zero-shot prompting and self-consistency (Wang et al., 2022) baselines, BSM with LLaMA-2-70B-chat improves LLM-human agreement by up to absolute 26% and even matches or outperforms GPT-4 on many domains. BSM with GPT-4 improves agreement by a further 3% over GPT-4. Overall, these findings point to our method’s capability to evaluate LLM responses to arbitrary user questions from diverse domains and to improve any base LLM as an evaluator.

BSM also improves the consistency of LLM evaluation. It significantly reduces position, length, and self-enhancement biases of LLM-based evaluators. For instance, BSM with LLaMA-2-70B-chat reduces position bias and length bias by up to absolute 50%. Importantly, BSM with GPT-4 also improves GPT-4’s reliability as an evaluator when evaluating its own responses.

For the constrained text generation task of producing stories with several concepts, BSM generates more coherent stories, which are preferred by a GPT-4 judge a substantial 93% of the time compared to a zero-shot baseline. It also improves constraint satisfaction by an absolute 12%.

Overall, Branch-Solve-Merge provides a framework for planning and task decomposition for addressing challenging multi-faceted natural language generation and evaluation tasks. As the approach is framed as a generic LLM program, it can be applied to any underlying language model and potentially a wide range of tasks.

Related Work

LLM programs such as Branch-Solve-Merge solve complex problems with the help of an algorithm that breaks the problem down into multiple steps and each step is then parameterized with a different prompt to an underlying LLM (Schlag et al., 2023; Dohan et al., 2022; Creswell & Shanahan, 2022). Complex tasks, in general, require task decomposition (Khot et al., 2022) and planning (Yao et al., 2022; Huang et al., 2022; Yao et al., 2023b; Ning et al., 2023). This has motivated a lot of recent work on advanced prompting methods across both vision and language domains. A few representative methods include decomposed prompting (Khot et al., 2022), least-to-most prompting (Zhou et al., 2022), plan and solve prompting (Wang et al., 2023a), successive prompting (Dua et al., 2022), decomposed summarization (Saha et al., 2022; 2023), text modular networks (Khot et al., 2021), and visual programming (Gupta & Kembhavi, 2023; Cho et al., 2023). However, most of these works typically focus on reasoning problems (like commonsense, symbolic, or mathematical reasoning) that benefit from sequential decompositions. We, on the other hand, study tasks that benefit from branching into parallel decompositions, in particular LLM Evaluation and constrained text generation. As well as being an LLM program, BSM can also be seen as an instance of Graph-of-Thoughts (GoT) prompting (Lei et al., 2023; Besta et al., 2023) because the execution trace of Branch-Solve-Merge takes the shape of a graph. GoT defines a wide array of LLM programs, including refining, backtracking and skipping graph nodes, which we do not consider here. Our work develops a specific fixed program, and applies it to the challenging tasks of evaluating or improving language models. Besta et al. (2023) consider tasks like sorting numbers, keyword counting or document merging, while Lei et al. (2023) consider Game of 24 and solving polynomial equations.

A fundamental challenge with the rapid progress of LLMs is evaluating their capabilities holistically (Chang et al., 2023; Liang et al., 2022). Human evaluation is difficult and expensive (Smith et al., 2022). On the other hand, LLMs, by virtue of being trained with RLHF, are shown to exhibit alignment with humans (Ouyang et al., 2022; Bai et al., 2022a). Hence, a standard procedure for comparing and evaluating LLM generations is by utilizing a strong LLM like GPT-4 (Bubeck et al., 2023; OpenAI, 2023a; Dubois et al., 2023; Zhou et al., 2023; Chiang & Lee, 2023; Wang et al., 2023c; Hada et al., 2023; Liu et al., 2023). This has also led to the development of a number of evaluation benchmarks (Zhong et al., 2023; Köpf et al., 2023; Zheng et al., 2023). Recent studies have shown that LLM-based evaluators are not fair evaluators (Wang et al., 2023b; Wu & Aji, 2023). In response, there have been proposals of using multi-agent debate frameworks (Chan et al., 2023) or developing wider and deeper LLMs (Zhang et al., 2023). In contrast, Branch-Solve-Merge improves LLM evaluation through an intuitive and general decomposition-based approach that can be applied on top of any LLM, and can be used to evaluate responses for a wide range of tasks.

LLMs are increasingly capable of generating coherent and fluent text. This has shifted the focus to evaluating LLMs for their capabilities in the more difficult setting of controllable and constrained text generation (Keskar et al., 2019; Dathathri et al., 2019; Lu et al., 2021; 2022; Lin et al., 2020; Li et al., 2022). Recent works have shown that GPT-4 struggles with constrained and planning-based text generation tasks (Bubeck et al., 2023; Madaan et al., 2023; Yao et al., 2023a). In this work, we experiment with such a constrained story generation task and show the promise of Branch-Solve-Merge in improving text generation capabilities.

Branch-Solve-Merge

We first introduce some notation to formally describe our method. Let $p_{\theta}$ denote an LLM with parameters $\theta$. We also denote $x=x_{1,\cdot\cdot\cdot,n}$ as a sequence of $n$ tokens, such that $p_{\theta}(x)=\prod_{i=1}^{n}p_{\theta}(x_{i}|x_{1,\cdot\cdot\cdot,i-1})$. Branch-Solve-Merge is an LLM program (Schlag et al., 2023; Dohan et al., 2022) that aims to solve complex planning-based tasks with three neural modules: a branch module, a solve module, and a merge module. Each module is parameterized with unique prompts to the LLM $p_{\theta}$. 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. Below, we describe each of these components in detail.

For a given task, Branch-Solve-Merge defines a controller in the form of an algorithm that lays out the transition logic between the modules. Let us denote the three modules with their functional forms: $\texttt{branch}(\cdot)$, $\texttt{solve}(\cdot)$, and $\texttt{merge}(\cdot)$. Then the program is defined as $\texttt{Prog}:(x,\texttt{branch}(\cdot),\texttt{solve}(\cdot),\texttt{merge}(\cdot))\rightarrow y$, taking as input a task instance $x$, along with the implementations of the modules and generating an output $y$.

Given a task, the branch module generates multiple sub-tasks where each sub-task is represented by a unique branch. Branching into sub-problems allows the problem to be decomposed such that each part can be solved independently in parallel, at which point the partial solutions are combined. Formally, given a task input $x$, we define a ‘branch’ prompt $\texttt{prompt}_{\texttt{branch}}(x)$ that can be wrapped around $x$ with branching instructions and some demonstrations (if available). Conditioning on the prompt, the LLM $p_{\theta}$ generates a set of $k$ sub-problems $X=\{x^{(1)},x^{(2)},\cdot\cdot\cdot,x^{(k)}\}$, where $k$ is referred to as the branching factor. The sub-problems are generated auto-regressively as a sequence of tokens: $X\sim p_{\theta}(X|\texttt{prompt}_{\texttt{branch}}(x))$. Then the generated token sequence may additionally go through some post-processing to textually represent the sub-problems, e.g., split up into $k$ branch prompts and prepend extra input context to each. Importantly, the flexibility of our method comes from the fact that for a given problem, the LLM decides (generates) the sub-problems and the corresponding branching factor.

The solve module solves the task at hand by generating an output $y^{(i)}$ for a branch task input $x^{(i)}$. We define a ‘solve’ prompt $\texttt{prompt}_{\texttt{solve}}(x^{(i)})$ that wraps around the input $x^{(i)}$ with solving instructions and some input-output demonstrations (if available). For each branch, the LLM conditions on the solve prompt to generate a solution $y^{(i)}$ such that $y^{(i)}\sim p_{\theta}(y^{(i)}|\texttt{prompt}_{\texttt{solve}}(x^{(i)}))$.

The merge module fuses together the solutions to the sub-problems to generate a global solution to the top-level problem. Similar to the branch and solve prompts, we define a ‘merge’ prompt $\texttt{prompt}_{\texttt{merge}}(Y)$ that wraps around a set of sub-solutions $Y=\{y^{(1)},y^{(2)},\cdot\cdot\cdot,y^{(k)}\}$ with merging instructions and optional demonstrations. The language model conditions on it to generate a merged solution $y\sim p_{\theta}(y|\texttt{prompt}_{\texttt{merge}}(Y))$. Conceptually, the merge module learns an aggregator function that could aggregate a set of values (using an aggregation operator) or fuse pieces of text, depending on the task.

In the following two sub-sections, we motivate and conduct case studies of our method with two challenging NLP tasks, that of LLM evaluation and constrained generation. Each of the modules are implemented zero-shot for the purpose of this study. However, these could be additionally accompanied with few-shot in-context examples or could also be fine-tuned modules.

2 Branch-Solve-Merge: Case Study with LLM Evaluation

We consider the task of evaluating LLM-based chat assistants. Formally, given an open-ended question (that evaluates an LLM’s multi-turn conversational and instruction-following ability) and a pair of responses from two LLM agents, the task requires producing a preference judgement of which response is better or if it is a tie (see Figure 1 for an example). Evaluating LLM responses is challenging for multiple reasons:

Long-form answers to arbitrary questions. With the goal of providing a general-purpose assistant, the user asks arbitrary questions from any domain, and the LLM responds with long-form answers (Zheng et al., 2023). Based on the initial model response, the user can ask follow-up questions. Depending on the type of question, the evaluation process must consider the intent of the question, what is expected from an ideal response, and what criteria to evaluate the generated response against.

LLM evaluators are prone to biases. LLM-based evaluators are not reliable and are prone to different kinds of biases including (a) Position Bias: evaluation changes based on the encoding order of the responses, (b) Length Bias: tendency to favor longer responses, (c) Self-enhancement Bias: the LLM-evaluator favoring its own responses (Zheng et al., 2023; Wu & Aji, 2023; Wang et al., 2023b).

GPT-4 as evaluator is expensive. While API-based models like GPT-4 are fairly good evaluators (Liu et al., 2023; Zheng et al., 2023; Bubeck et al., 2023), these models are proprietary and charge users per token generated. Current open-source alternatives correlate less well with humans and are much more susceptible to the aforementioned biases (Zheng et al., 2023).

Hand-designing evaluation plans is not scalable. A robust evaluator should generalize well, capable of evaluating responses to arbitrary questions and hence, hand-designing the evaluation plan for every task is not a desirable approach (Liu et al., 2023; Wu & Aji, 2023). For example, see Figure 1, where evaluating responses to a ‘writing’ question requires considering factors like ‘Relevance’, ‘Clarity’, etc whereas if the question is a ‘coding’ question (see Figure 2), one should evaluate for ‘Code Correctness’, ‘Code Readability’, etc.

Hence, given the multi-faceted nature of this evaluation task, we develop a version of Branch-Solve-Merge, as described below. For the purpose of this study, we focus on evaluating two-turn conversational questions although our method is generally applicable for any number of turns. Let us denote the first question as $q_{1}$ and the follow-up question as $q_{2}$. Let the responses from the two LLMs $A$ and $B$ be $r_{1}^{(A)}$ and $r_{1}^{(B)}$ for $q_{1}$, and $r_{2}^{(A)}$ and $r_{2}^{(B)}$ for $q_{2}$.

The branch module generates an evaluation plan. The plan is a set of evaluation criteria that the response will be evaluated against. To ensure that the plan is not biased by the model responses, the branch module only conditions on the input question. In particular, we define the branch module for turn-1 questions as branch($q_{1}$), while for turn-2 questions, it conditions on both turn-1 and turn-2 questions, represented as branch($q_{1},q_{2}$). The language model generates a set of evaluation criteria, $\texttt{branch}(q)\rightarrow\{c_{i}\}_{i=1}^{k}$, where each $c_{i}$ is the title of the criterion (e.g., ‘Relevance’) and a short description of how to evaluate for it (e.g., ‘Assess how well the response aligns with the user’s question and whether it provides relevant information about cultural experiences and must-see attractions in Hawaii.’). Figures 1 and 2 show examples of evaluation plans for different questions generated by the branch module with a LLaMA-2-70B-chat model, note that criteria are adapted for the question type. Refer to Figure 4 for the exact branch prompt we use.

The solve module compares and evaluates the responses based on a specific evaluation criterion. The output of the evaluation is a pair of scores (within a specified range, according to the solving instruction, e.g., 1-5) for each of the responses. Given an evaluation criterion $c$, we denote the solve module for a turn-1 question $q_{1}$ and turn-2 question $q_{2}$ as follows.

where $s_{1}^{(A)}$ and $s_{1}^{(B)}$ are the evaluation scores assigned to the two assistant responses for $q_{1}$ while $s_{2}^{(A)}$ and $s_{2}^{(B)}$ are those for $q_{2}$. Note that the solve module is not symmetric i.e., the order in which the two responses are encoded in the LLM is important due to its auto-regressive nature (and we address this below in our LLM program). The module additionally generates explanations along with the scores. Figure 1 shows example generations from the solve module with a LLaMA-2-70B-chat model. Refer to Figure 5 for the exact solve prompt we use.

We develop two variants of the merge module. A simple non-neural variant aggregates the scores across all branches by summing them up. We also develop a neural LLM variant that conditions on the individual evaluations and generates the final verdict with a model-decided aggregation strategy. We denote this with:

where the evaluation criteria $\{c_{i}\}_{i=1}^{k}$ are the outputs of the branch module and $s_{i}^{(A)}$ and $s_{i}^{(B)}$ are the criterion-wise evaluations (scores and explanations) of the two assistant responses generated from the solve module. The final verdict is $y\in\{A,B,tie\}$.

The overall LLM program pseudocode is given in Algorithm 1. If $q$ is a $t$-turn question, we assume that it encodes all the questions up to that turn in order. To account for position bias, the program executes two independent runs of BSM by swapping the encoding order of the responses in the ‘solve’ module. The final judgment is either ‘A’ or ‘B’ if and only if the judgement is consistent for both orders, otherwise it is a ‘tie’.

3 Branch-Solve-Merge: Case Study with Constrained Generation

Our next case study shows the general applicability of BSM by applying it to a completely different task, that of LLM generation. We consider a constrained story generation task – given a set of $N$ given concepts $l$, the task is to generate a coherent story $y$ by including all concepts in it. Figure 3 shows an example. Recent work has shown that constrained text generation poses significant challenges even for GPT-4 (Madaan et al., 2023; Yao et al., 2023a; Bubeck et al., 2023). When the number of concepts is large, LLMs tend to either leave out some concepts or generate text that is incoherent. The task requires composition incorporating the various constraints. When a standard model has already generated part of the text without including certain concepts, it is unable to roll back, in which case it tends to either miss some concepts completely or else include them in such a manner that the final generation is incoherent.

The branch module $\texttt{branch}(l)\rightarrow(l_{1},l_{2},t)$ proposes a story generation plan, consisting of (1) two subsets of concepts $l_{1}$ and $l_{2}$ and (2) a story topic $t$. The two subsets represent sub-problems of the original story generation task with a smaller number of concepts. The story topic ensures that all sub-stories generated as part of BSM belong to the same topic. While we limit the branching factor to two for the purpose of this study, the concepts could be divided into an arbitrary number of subsets. See Figure 3 for examples of branches.

The solve module $\texttt{solve}(l_{i},t)\rightarrow y_{i}$ conditions on a subset of concepts $l_{i}$ and the story topic $t$ to generate a story $y_{i}$ on that topic, while also including all concepts in $l_{i}$. Intuitively, when the number of concepts is smaller, ‘solving’ the constrained generation task is easier.

The merge module $\texttt{merge}(y_{1},y_{2})\rightarrow y$ conditions on two intermediate stories (i.e., solutions to the two sub-problems) and fuses them together to generate the final story $y$. Since both intermediate stories belong to the same high-level topic, the fusion can lead to a final coherent story. For instance, Figure 3 shows that the final story contains all major parts of the two sub-stories, while undergoing some sentence restructuring and including phrases like ‘Meanwhile, outside’ to better connect the stories. Overall, BSM ensures better constraint satisfaction by solving sub-problems and maintains coherency through the use of a top-level plan that includes a story topic.

Experiments

We conduct experiments to evaluate Branch-Solve-Merge for both LLM Evaluation (in Section 4.1) and Constrained Text Generation (later in Section 4.2).

We experiment with the MT-Bench dataset, that evaluates LLMs as judges of other LLM’s responses when acting as helpful AI assistants in multi-turn conversations (Zheng et al., 2023). It consists of 2400 LLM responses and 3000 expert human judgements. LLM outputs are responses to 80 representative instructions from 8 diverse domains: writing, roleplay, extraction, reasoning, math, coding, knowledge \@slowromancapi@ (STEM), and knowledge \@slowromancapii@ (humanities/social science). Each question is a conversational question, consisting of two turns, in which the turn-2 question is a follow-up to the turn-1 question. For each question, the dataset consists of responses from 6 different LLMs (Alpaca-13B, Vicuna-13b, LLaMA-13B, Claude-v1, GPT-3.5-turbo, and GPT-4), resulting in 15 possible response pairs. Thus, the entire evaluation set consists of 300 response-pair samples per category.

We evaluate BSM (and baselines) using the following four metrics.

LLM-Human Agreement (Ag). Our primary metric of interest is LLM-human agreement. We report agreement scores $\in$ individually for turn-1 and turn-2 questions, as well as their combination. Each sample (question and two model responses) has a variable number of human judgments. Hence, following past work, we compute agreement by independently matching each human judgment for each sample with the model judgment (Zheng et al., 2023). Table 10 in the Appendix shows that even if the agreement is computed with a majority vote of the individual human judgments, our conclusions do not change.

Position Bias (PB). To evaluate whether BSM helps reduce the consistency problem with LLM-based evaluators, we report Position Bias. It refers to the fraction of samples where the judgment changes based on the encoding order of the pair of responses that are being compared.

Length Bias (LB). We measure length bias as the fraction of samples where humans prefer the shorter response but the evaluator model does not. Note that measuring length bias in isolation is challenging because knowing whether the model prefers the longer response because of its length (and not for another reason) is an interpretability question and humans also tend to prefer longer responses, especially for open-ended questions.

Self-enhancement Bias (SB). Self-enhancement bias refers to an evaluator model preferring its own responses. In order to quantitatively measure whether BSM helps reduce this bias, we consider the following setting. We use GPT-4 as the base judge model and consider the subset of samples from the MT-Bench benchmark where one of the responses is also generated by GPT-4. If BSM with GPT-4 improves agreement with humans for this subset of samples, it suggests that even in scenarios where a model A is judging its own outputs, BSM (with model A) leads to a better evaluator.

While multiple past works have highlighted the importance of these biases (Zheng et al., 2023; Wang et al., 2023b; Wu & Aji, 2023), we measure all of them with concrete metrics within the same evaluation framework. Conceptually, the human agreement metric evaluates correctness while position bias for example evaluates consistency of LLM-based evaluators. Note that these are complementary aspects and an ideal evaluator should perform well in all metrics (i.e., high agreement scores and low biases) for it to be reliably used.

We develop BSM on top of multiple state-of-the-art open-source and API-based LLMs of varying scales and capabilities: LLaMA-2-7B-chat (Touvron et al., 2023), Vicuna-33B (Chiang et al., 2023), LLaMA-2-70B-chat (Touvron et al., 2023), and GPT-4 (OpenAI, 2023b). We implement all modules zero-shot, providing only module-specific instructions and assuming no access to demonstrations of how to branch, solve, or merge. For better reproducibility, all modules generate text using greedy decoding. For the branch module, the LLM is prompted to generate a plan consisting of a maximum of five evaluation criteria (which we found it adheres to in experiments). For the merge module, we find that the non-neural merge of summing up the criterion-wise evaluations is simple and works well in practice, hence all our experimental results are reported with that method. Refer to our prompts in the Appendix for additional implementation details.

We compare our method, BSM, to zero-shot prompting with the same LLM, using the same evaluation prompt as used in prior work (Zheng et al., 2023). We also compare with Self-Consistency (Wang et al., 2022), which samples multiple evaluations from the prompted LLM (with temperature $0.7$) and chooses the majority vote as the final judgment. All methods, including BSM, account for position bias in the same manner, generating a verdict for both encoding orders and choosing the final verdict based on the individual verdicts (assigning a tie if the two encoding orders disagree). In particular, Self-Consistency computes majority vote independently for each encoding order. To ensure fair comparisons, Self-Consistency samples the same number of generations as the branching factor in BSM (five, in our experiments). We also note that Self-Consistency is a simple special case of BSM, where the branch module spawns multiple instances of the same underlying problem (instead of sub-problems), solves them by sampling different solutions, and the merging operator is a majority vote.

1.2 Main Results

Table 1 evaluates the efficacy of Branch-Solve-Merge, specifically focusing on the ‘writing’ category of questions from the MT-Bench benchmark. We report our main findings below.

Overall agreement. We find that BSM improves LLM-human agreement for both turn-1 and turn-2 questions, when applied to all three base LLMs. For LLaMA-2, compared to the zero-shot baseline, BSM obtains an overall absolute improvement of 12% in agreement score, making LLaMA-2-70B-chat competitive with GPT-4 for turn-1 (but still lags behind for turn-2). Even though zero-shot GPT-4 is the state-of-the-art LLM-based evaluator, applying BSM obtains a further improvement of 3%.For fair comparison with BSM, the baseline zero-shot GPT-4 results are our reproduction of prior work (Zheng et al., 2023), who also report same agreement score of 0.59. Observing no significant difference, we thus directly use their GPT-4 predictions for the results in Tables 4 and 5.

Turn-1 versus Turn-2 questions. Evaluating turn-2 (follow-up) questions is harder because it requires additional contextualization of the responses for the turn-1 question. This is also reflected in all zero-shot models exhibiting lower turn-2 agreement scores (e.g., LLaMA-2-70B-chat results drop from 0.53 in turn-1 to 0.34 in turn-2). BSM shows that a decomposition approach which generates an evaluation plan is particularly helpful for evaluating long context questions, resulting in more improvements for turn-2 questions (e.g., a 16% improvement with LLaMA-2). An illustration of this is shown in Figure 2, in which for the turn-2 question, the model generates ‘Adherence to Instructions’ as the first criterion to evaluate.

Self-Consistency versus BSM. BSM also outperforms Self-Consistency (e.g., by up to 5% with Vicuna). As noted earlier, Self-Consistency is a special case of BSM. Moreover, Self-Consistency with comparatively weaker models like Vicuna may not always be effective because of the model’s inability to generate vastly different solutions (Wang et al., 2022). BSM, on the other hand, works well across all models. This result is also noteworthy because both approaches leverage similar amounts of compute in generating multiple solutions – but branching and solving the differing sub-problems provides superior results to solving the same problem multiple times.

Position and Length Bias Reduction. On top of improving LLM-human agreement, BSM helps reduce critical biases with LLM-based evaluators. Weaker models exhibit biases more frequently e.g., LLaMA-2 suffers from position bias almost half the time. However, BSM obtains a significant 34% reduction in position bias, matching that of GPT-4. We also observe a significant reduction in length bias. BSM with GPT-4 does not impact position bias much (despite improving its LLM-Human Agreement). Nevertheless, BSM opens up the possibility of using weaker open-source models also as evaluators, closing the gap to GPT-4.

Self-enhancement Bias reduction. Table 2 evaluates self-enhancement bias by comparing BSM (with zero-shot GPT-4) for the fraction of samples where one of the responses is also generated by GPT-4. We observe a 3% better correlation with humans, suggesting that BSM leads to a better evaluator even when the LLM is judging its own outputs.

BSM with comparatively smaller models. We also investigate whether smaller models like LLaMA-2-7B-chat can benefit from BSM. Table 3 shows that smaller models are, in general, weak evaluators. Even then, BSM leads to a moderate 2% improvement in agreement scores, while self-consistency proves to be ineffective. More encouragingly, BSM reduces the position bias by a significant 14%. Although the underlying model is weak and may not be best suited for LLM evaluation, the BSM decomposition-based approach makes its evaluations much more consistent.

In summary, our results suggest that BSM is a generic method that can be applied to any LLM for evaluating generations from language models. It improves both correctness (by improving human agreement) and consistency (by reducing biases) of LLM-based evaluators.

In Table 4, we evaluate BSM’s ability to evaluate generations for questions in the categories of ‘Roleplay’, ‘Extraction’, ‘Stem’, and ‘Humanities’. We find that BSM is robust and performs well across domains in terms of improvement over the LLaMa-2-70B-chat baseline, and approaches GPT-4 performance on several of the domains. In particular, on the Stem domain, it is able to improve agreement scores over the baseline by up to 26% (absolute), match GPT-4, and even outperform it in terms of position and length biases.

So far, we have applied BSM in reference-free evaluations for comparatively open-ended questions like writing, roleplay, etc. However, LLMs generally struggle with complex tasks like in math, reasoning, and coding (Cobbe et al., 2021; Chen et al., 2021; Wei et al., 2022). More so, even when LLMs are able to successfully answer these questions, they may not be able to evaluate them correctly. Zheng et al. (2023) suggest alleviating this issue by first generating an answer using GPT-4 and then appending it to the evaluation prompt, which is our baseline in this experiment. For BSM, we then follow a similar recipe for grading these categories of questions by conditioning the ‘solve’ module on the GPT-4 generated answers. The key assumption here is that these answers are curated once and have limited variations unlike answers for open-ended questions, thus allowing us to evaluate BSM in reference-based settings. Table 5 shows the results. BSM significantly outperforms LLaMA-2-70B-chat in all categories (by up to 14% better agreement scores and 27% better position bias in coding questions). On Math, it even outperforms the state-of-the-art GPT-4 evaluator, outperforming on all metrics.

1.3 Analysis and Ablations of Branch-Solve-Merge

BSM generates a single solution for each sub-problem (each branch). A possible enhancement is combining BSM with self-consistency i.e., sampling multiple solutions for each sub-problem. In particular, we implement BSM+SC by sampling five evaluations per branch (with temperature $0.7$) and then the score for each sub-evaluation in that branch is given by the average score. We compare BSM with BSM+SC in Table 6. While agreement scores do not improve further, we observe a 2% reduction in position bias. This points to two conclusions. First, BSM, through its decomposition approach, already constructs sub-problems that are granular enough and hence, the variance reduction that one obtains through self-consistency within each sub-problem is limited. However, the moderate reduction in position bias still reflects its usefulness, which is a direct effect of making evaluations more consistent.

BSM has the benefit of relying on the underlying LLM for deciding what sub-problems to branch to, while the prompt controls the maximum branching factor (see the phrase ‘list of up to five factors’ in the branch prompt in Fig. 4). We vary this maximum branching factor from 2 to 5 and study its effect on 100 samples from the ‘writing’ category of questions. Table 7 reports our findings. We observe highest agreement at a branching factor of 4, after which the result mostly saturates. In general, the optimal branching factor should depend on the specific question under consideration and unlike past work where users specify what factors to evaluate on (Liu et al., 2023; Zheng et al., 2023), BSM generates that plan on its own. Position bias continues to decrease with increasing branching factor, where more branches helps reduce variance in the final judgment.

Evaluation tasks, in general, require defining a scale for scoring the responses. In Table 8, we compare the performance of BSM by varying this evaluation scale, specified in the ‘solve’ prompt (see Fig 5), either scoring 1-5 (used in the main experiments) or 1-10. We observe that BSM is fairly robust to such variations, obtaining comparable agreement scores. The position bias, however, increases slightly with a larger scale.

2 Constrained Text Generation

This section describes our experimental setup and findings for the constrained story generation task.

The constrained story generation task we consider is a more challenging variant of a generative commonsense reasoning task, CommonGen (Lin et al., 2020). While the original task requires generating a single coherent sentence from 3 or 4 concepts, we increase the complexity of the task by having the model generate a concise story consisting of 10 concepts (Madaan et al., 2023). We experiment with 100 samples for the purpose of this study.The dataset is available at https://github.com/madaan/self-refine/blob/main/data/prompt/commongen/commongen_hard.jsonl.

We evaluate the generated stories along two axes:constraints satisfaction and overall story quality. For constraints satisfaction, we report two metrics: (a) All Present: fraction of samples where all constraints are satisfied i.e., there are no missing concepts, and (b) Missing Concepts: average percentage of missing concepts. Higher ‘all present’ and lower ‘missing concepts’ are preferable. We identify a missing concept if it does not appear in the story in any word form. For evaluating overall story quality, we conduct a pairwise evaluation with GPT-4. The evaluation prompt is provided in Figure 7. To account for position bias in this pairwise comparison, we follow our findings from the LLM Evaluation task and conduct each evaluation twice, by swapping the order of the stories and preferring one story over the other only if the evaluations are consistent.

We evaluate BSM using LLaMA-2-7B-chat and LLaMA-2-70B-chat. All modules generate text using greedy decoding. For the branch module, the LLM is prompted to divide the concepts into two groups. Refer to our prompts in Figure 6 in the Appendix for additional implementation details.

We compare BSM to zero-shot prompting with the same LLM. The zero-shot prompt is similar to the ‘solve’ prompt in BSM, with the exception that it first proposes a story topic and then generates a story on that topic. This not only makes the comparison with BSM fair but we also find that first proposing a topic generally makes the story more coherent.

2.2 Results and Analysis

Table 9 shows the results. We observe that BSM with both LLaMA-2-7B-chat and LLaMA-2-70B-chat leads to a significant improvement in constraint satisfaction metrics. In particular, it increases the fraction of samples where no constraints are violated (‘All Present’) by 7-10%. Despite this improvement, it is important to note that this is a still a challenging task even for a stronger LLaMA-2-70B-chat model and the scale of the model has little impact on constraint satisfaction. For example, even BSM with LLaMA-2-70B-chat omits at least one concept for 72% of the samples, echoing the findings from prior work that constrained text generation is hard even for state-of-the-art LLMs (Bubeck et al., 2023; Yao et al., 2023a).

BSM not only satisfies more constraints but almost always generates a more coherent story. We find that in a head-to-head comparison with the zero-shot prompting baseline (with LLaMA-2-70B-chat), stories generated by BSM are preferred a substantial 93% of the time by GPT-4. This can be attributed to two aspects of BSM. First, in each of the branches, the model conditions on a lesser number of concepts and thus generates intermediate stories that by themselves are more coherent. Second, in the merging step, the model is able to condition on these two intermediate stories and generate a final story that further improves the coherence.

The source of missing concepts in BSM can be attributed to one of the following two categories: (a) the ‘solve’ module, i.e., the model omits concepts even when generating an intermediate story in a branch subproblem with a lesser number of concepts; or (b) the ‘merge’ module, i.e., the intermediate stories include their respective concepts but the fusion process omits some of these. We observe that out of 72% of the BSM stories (with LLaMA-2-70B-chat) where at least one concept is missing, a significant 60% of these belong to the first category (i.e., concept omission in the ‘solve’ module) versus only 12% belong to the second category (i.e., concept omission during ‘merging’). This suggests that constraint satisfaction can be further improved via a ‘recursive’ BSM method involving iterative branching to even more granular sub-problems. However, recursive BSM would be significantly more expensive because of many more calls to the base LLM. We leave this exploration as part of future work.

Conclusion

We presented Branch-Solve-Merge (BSM), a Large Language Model 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. On the LLM evaluation task, BSM substantially improves correctness and consistency of evaluation by demonstrating better LLM-human agreement and reducing position bias respectively. BSM also improves a constrained text generation task, enhancing its coherency and satisfying more constraints.

References

Appendix A Appendix