# Some upper bounds for 3-rainbow index of graphs

Tingting Liu, Yumei Hu111supported by NSFC No. 11001196.
Department of Mathematics, Tianjin University, Tianjin 300072, P. R. China
E-mails<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

A tree $T$, in an edge-colored graph $G$, is called a rainbow tree if no two
edges of $T$ are assigned the same color. A $k$-rainbow coloring of $G$ is an
edge coloring of $G$ having the property that for every set $S$ of $k$
vertices of $G$, there exists a rainbow tree $T$ in $G$ such that $S\subseteq
V(T)$. The minimum number of colors needed in a $k$-rainbow coloring of $G$ is
the $k$-rainbow index of $G$ , denoted by $rx_{k}(G)$. In this paper, we
consider $3$-rainbow index $rx_{3}(G)$ of $G$. We first show that for
connected graph $G$ with minimum degree $\delta(G)\geq 3$, the tight upper
bound of $rx_{3}(G)$ is $rx_{3}(G[D])+4$, where $D$ is the connected
$2$-dominating set of $G$. And then we determine a tight upper bound for
$K_{s,t}(3\leq s\leq t)$ and a better bound for $(P_{5},C_{5})$-free graphs.
Finally, we obtain a sharp bound for $3$-rainbow index of general graphs.

Keywords

: $3$-rainbow index; rainbow tree; connected $2$-dominating set.

##  1 Introduction

All graphs considered in this paper are simple, connected and undirected. We
follow the terminology and notation of Bondy and Murty [1]. An edge-colored
graph $G$ is rainbow connected  if any two vertices are connected by a path
whose edges have distinct colors. The rainbow connection number $rc(G)$ of
$G$, introduced by Chartrand et al. [6], is the minimum number of colors that
results in a rainbow connected graph $G$.

Later, another generalization of rainbow connection number was introduced by
Chartrand et al.[5] in 2009. A tree $T$ is a rainbow tree if no two edges of
$T$ are colored the same. Let $k$ be a fixed integer with $2\leq k\leq n$. An
edge coloring of $G$ is called a $k$-rainbow coloring if for every set $S$ of
$k$ vertices of $G$, there exists a rainbow tree in $G$ containing the
vertices of $S$. The $k$-rainbow index $rx_{k}(G)$ of $G$ is the minimum
number of colors needed in a $k$-rainbow coloring of $G$. It is obvious that
$rc(G)=rx_{2}(G)$.

Let $k$ be a positive integer. A subset $D\subseteq V(G)$ is a $k$-dominating
set of the graph $G$ if $|N_{G}(v)\cap D|\geq k$ for every $v\in V\setminus
D$. The $k$-domination number $\gamma_{k}(G)$ is the minimum cardinality among
the $k$-dominating sets of $G$. Note that the $1$-domination number
$\gamma_{1}(G)$ is the usual domination number $\gamma(G)$. A subset $S$ is a
connected $k$-dominating set if it is a $k$-dominating set and the graph
induced by $S$ is connected. The connected $k$-domination number
$\gamma_{k}^{c}(G)$ represents the cardinalities of a minimum connected
$k$-dominating set. For $k=1$, we write $\gamma_{c}$ instead of
$\gamma_{1}^{c}(G)$.

Chakraborty et al. [3] showed that computing the rainbow connection number of
a graph is NP-hard. So it is also NP-hard to compute $k$-rainbow index of an
arbitrary graph.

Chandran et al. [4] use a strengthened connected dominating set (connected
$2$-way dominating set) to prove $rc(G)\leq rc(G[D])+3$. This led us to the
investigation of what is strengthening of a connected dominating set which can
apply to consider $3$-rainbow index of a graph.

Recently, for $3$-rainbow index, Li et al. did some basic results and they
obtained the following theorem.

######  Theorem 1.1.

[7] Let $G$ be a $2$-connected graph of order $n$ $(n\geq 4)$. Then
$rx_{3}(G)\leq n-2$, with equality if and only if $G=C_{n}$ or $G$ is a
spanning subgraph of $3$-sun or $G$ is a spanning subgraph of $K_{5}\setminus
e$ or $G$ is a spanning subgraph of $K_{4}$.

Here, a $3$-sun is a graph $G$ which is defined from $C_{6}$ =
$v_{1}v_{2}\cdots v_{6}v_{1}$ by adding three edges $v_{2}v_{4}$, $v_{2}v_{6}$
and $v_{4}v_{6}$.

Chartrand et al. [6] obtained that for integers s and t with $2\leq s\leq t$,
$rc(K_{s,t})=min\\{\sqrt[s]{t},4\\}$. Thus, $rx_{2}(G)=rc(G)\leq 4$. Li et al.
[7] consider the regular complete bipartite graphs $K_{r,r}$. They show
$rx_{3}(K_{r,r})=3$ for integer $r$ with $r\geq 3$.

In this paper, we focus on $3$-rainbow index. In section $2$, we adopt
connected $2$-dominating set to study $3$-rainbow index. A coloring strategy
is obtained which uses only a constant number of extra colors outside the
dominating set. We prove that $rx_{3}(G)\leq rx_{3}(G[D])+4$, where $D$ is the
connected $2$-dominating set of $G$. In section $3$, We determine a sharp
bound of $3$-rainbow index for $K_{s,t}$ ( $3\leq s\leq t$) and an upper bound
for $(P_{5},C_{5})$-free. In section $4$, we investigate a sharp upper for
$rx_{3}(G)$ of general graphs by block decomposition and an upper bound for
graphs with $\delta(G)\geq 3$ by connected $2$-dominating set.

##  2 A sharp upper of $3$-rainbow index in terms of connected $2$-dominating
set

######  Theorem 2.1.

Let $G$ be a connected graph with minimal degree $\delta\geq 3$. If $D$ is a
connected $2$-dominating set of $G$, then $rx_{3}(G)\leq rx_{3}(G[D])+4$ and
the bound is tight.

###### Proof.

We prove the theorem by demonstrating that $G$ has a 3-rainbow coloring with
$rx_{3}(G[D])+4$ colors. For $x\in V(G)\setminus D$, its neighbors in $D$ will
be called foots of $x$, and the corresponding edges will be called legs of
$x$.

We give $G[D]$ a 3-rainbow coloring using colors
$1,2,\cdots,k~{}(k=rx_{3}(G[D]))$. Let $H:=G\setminus D$. Partition $V(H)$
into sets $X,Y,Z$ as follows. $Z$ is the set of all isolated vertices of $H$.
In every nonsingleton connected component of $H$, choose a spanning tree. So
we construct a forest on $W:=V(H)\setminus Z$ and choose $X$ and $Y$ as any
one of the bipartitions defined by this forest. Color every $X-D$ edge with
$k+1$ or $k+2$ where each of $k+1,k+2$ appears at least once, every $Y-D$ edge
with $k+1$ or $k+3$ where each of $k+1,~{}k+3$ appears at least once, every
edge between $X$ and $Y$ with $k+4$. Since $G$ has a minimal degree
$\delta\geq 3$, every vertex in $Z$ will have at least three neighbors in $D$.
Color two of them with $k+1$ and $k+3$ and all the others with $k+4$. Next, we
show that under such an edge coloring for any three vertices in $D$ there
exists a rainbow tree containing them.

For three vertices $(x,y,z)\in D\times D\times D$, there is already a rainbow
tree containing them in $G[D]$. For three vertices $(x,y,z)\in$ $D\times
D\times V(H)$ (or $D\times V(H)\times V(H)$), join any one leg of $z$ (or
$k+1$, $k+3$ ($k+2$) legs of $y$ and $z$ ) with a rainbow tree containing the
corresponding foot (or two foots), $x$ and $y$ (or $x$) in $G[D]$. Now we
consider the case three vertices $(x,y,z)\in$ $V(H)\times V(H)\times V(H)$.
For three vertices $(x,y,z)\in Z\times Z\times Z$, join three edges which
color $k+1,k+4$ and $k+3$ with a rainbow tree containing the corresponding
foots $(x^{\prime},y^{\prime},z^{\prime})$ in $D$. For two vertices $(x,y)\in
Z\times Z$, $z\in W$, join a $k+1$ leg of $z$ and $k+3,~{}k+4$ legs of
$x,~{}y$ with a rainbow tree containing the corresponding foots in $G[D]$.
Consider one vertex $x\in Z$, two vertices $(y,z)\in W\times W$. If $(y,z)\in
X\times X$, join a $k+4$ leg of $x$ and $k+1,k+2$ legs of $y$ and $z$ with a
rainbow tree containing the corresponding foots in $G[D]$. If $(y,z)\in
X\times Y$ or $(y,z)\in Y\times Y$, join a $k+4$ leg of $x$ and $k+1,k+3$ legs
of $y$ and $z$ with a rainbow tree containing the corresponding foots in
$G[D]$. Then consider three vertices $(x,y,z)\in W\times W\times W$. If
$(x,y,z)\in X\times X\times X$, we know, for $x\in X$, $x$ has a neighbor
$y(x)\in Y$. $x-y(x)$ edge (colored $k+4$) and $k+3$ leg of $y(x)$, join $k+1$
leg of $y$ and $k+2$ leg of $z$ with a rainbow tree containing the
corresponding foots in $G[D]$. Similarly, in other cases, we can find a
rainbow tree containing them. Hence, $G$ has a 3-rainbow coloring with
$rx_{3}(G[D])+4$ colors.

The proof of tightness is given in the next section. ∎

##  3 Upper bounds for $3$-rainbow index of some special graphs

In this section, we consider two special graphs: complete bipartite graphs
$K_{s,t}$ and $(P_{5},C_{5})$-free graphs.

######  Theorem 3.1.

For any complete bipartite graphs $K_{s,t}$ with $3\leq s\leq t$,
$rx_{3}(K_{s,t})\leq min\\{6,s+t-3\\}$, and the bound is tight.

###### Proof.

Because $K_{s,t}$ with $3\leq s\leq t$ is a 2-connected graph, by Theorem 1.1,
we have, $rx_{3}(K_{s,t})\leq s+t-3$. The equality clearly holds for $s=t=3$
since $rx_{3}(K_{3,3})=3$. Thus, to complete the proof, it suffices to show
$rx_{3}(K_{s,t})\leq 6$, $3\leq s\leq t$. Let $U$ and $W$ be the two partite
sets of $K_{s,t}$, where $|U|=s$ and $|W|=t$. Suppose
$U=\\{u_{1},u_{2},\cdots,u_{s}\\},~{}W=\\{w_{1},w_{2},\cdots,w_{t}\\}$.

Clearly we can find a connected 2-dominating set
$D=\\{u_{1},u_{2},w_{1},w_{2}\\}$ of $K_{s,t}$. In addition, $K_{s,t}\setminus
D$ is connected, $Z=\emptyset$, by Theorem 2.1, $rx_{3}(K_{s,t})\leq
rx_{3}(G[D])+4=6$.

To prove the sharpness of the above upper bound, we derive the following
claim.

Claim. For any $s\geq 3$, $t\geq 2\times 6^{s}$, $rx_{3}(K_{s,t})=6$.

Firstly, we consider the graph $K_{3,t}$. We may assume that there exists a
3-rainbow coloring $c$ of $K_{3,t}$ with $k$ colors. Corresponding to this
3-rainbow coloring, for every vertex $w$ in $W$, there is a color code,
code($w$), assigned $a_{i}=c(u_{i}w)\in\\{1,2,\cdots,k\\}$, $1\leq i\leq 3$.
Observe that any three vertices have at least three distinct colors appeared
in their color codes. Thus, we know that at most two vertices have the common
code except possibly when $a_{1}\neq a_{2}\neq a_{3}$. Otherwise, there is no
rainbow tree containing these three vertices which have the same code and at
most two colors in color code. Therefore, when $t\geq 2k^{3}$, there must
exist three vertices $w^{\prime}$, $w^{\prime\prime}$,
$w^{\prime\prime\prime}$ such that code
($w^{\prime}$)=code($w^{\prime\prime}$)=code($w^{\prime\prime\prime}$)=$\\{a_{1},a_{2},a_{3}\\}$
and $a_{1}\neq a_{2}\neq a_{3}$. If a rainbow tree containing
$S=\\{w^{\prime},\ w^{\prime\prime},\ w^{\prime\prime\prime}\\}$, it must
contain $u_{1},u_{2},u_{3}$ and $w_{i}$ to guarantee its connectivity, where
$w_{i}$ belongs to $W$ and code($w_{i}$)=$\\{b_{1},b_{2},b_{3}\\}$, where
$a_{i}$, $b_{j}$ are different from each other, $i=1,2,3;\ j=1,2,3$. Thus
$k\geq 6$. So $rx_{3}(K_{3,t})=6$, when $t\geq 2\times 6^{3}$. Similarly, we
can prove $rx_{3}(K_{s,t})=6$, for $s\geq 4$, $t\geq 2\times 6^{s}$. Thus,
this claim also provides the tight proof of the Theorem 2.1. ∎

Here, we can simply check that the upper bound can not be generalized to the
graphs $K_{2,t}$. By the same method used in the above claim, We may assume
that there exists a 3-rainbow coloring $c$ of $K_{2,t}$ with $k$ colors.
Corresponding to this 3-rainbow coloring, there is a color code, code($w$),
assigned $a_{i}=c(u_{i}w)\in\\{1,2,\cdots,k\\}$ for $i=1,2$. Observe that at
most two vertices have the common code. It follows, $t\leq 2k^{2}$. Thus, $k$
is not less than a certain constant when $t$ is enough large.

To state next theorem, we need to make more definitions. A graph $G$ is called
a perfect connected dominant graph if $\gamma(X)=\gamma_{c}(X)$, for each
connected induced subgraph $X$ of $G$. If $G$ and $H$ are two graphs, we say
that $G$ is $H$-free if $H$ does not appear as an induced subgraph of $G$.
Furthermore, if $G$ is $H_{1}$-free and $H_{2}$-free, we say that $G$ is
$(H_{1},H_{2})$-free. Next, we determine the upper bound for $3$-rainbow index
of $(P_{5},C_{5})$-free graphs.

Zverovich has obtained the following result.

######  Theorem 3.2.

[14] A graph $G$ is a perfect connected-dominant graph if and only if $G$
contains no induced path $P_{5}$ and induced cycle $C_{5}$.

As shown in Theorem 2.1, in order to obtain a better bound of $3$-rainbow
index, we may turn to a smallest possible connected $2$-dominating set. For a
graph with minimal degree $\delta\geq 3$, B.Reed proved the following
conclusion in [13].

######  Theorem 3.3.

[13] If $G$ is connected graph with $\delta\geq 3$, then
$\gamma(G)\leq\frac{3n}{8}$.

For $(P_{5},C_{5})$-free graphs $\delta\geq 3$, we have
$\gamma_{c}(G)\leq\frac{3n}{8}$. Inspired by this result, the extension of the
idea of connected dominating set to connected $2$-dominating set is what gives
the following lemma.

######  Lemma 3.1.

Let $G$ be a connected graph of order $n$ with minimal degree $\delta\geq 2$.
If $D$ is a connected dominating set in a graph $G$, then there is a set of
vertices $D^{\prime}\supseteq D$ such that $D^{\prime}$ is a connected
2-dominating set and $|D^{\prime}|\leq\frac{1}{2}n+\frac{1}{2}|D|$.

###### Proof.

There are two types of the components of $G\setminus D$: singletons and
connected subgraphs. Let $P$ be the set of the singletons, and $Q$ be the set
of the connected components of $G\setminus D$. Note that $G\setminus D=P\cup
Q$. Since $\delta\geq 2$, for any vertex $v$ in $P$, it has at least two
neighbors in $D$. In every non-singleton connected component of $Q$, we choose
a spanning tree. This gives a spanning forest on $V(Q)$. Choose $X$ and $Y$ as
any one of the bipartitions defined by this forest. Without loss of
generality, we suppose that $|X|\leq|Y|$.

Stage $D^{\prime}=D$

while $\exists v\in V(Q)$ such that $|N(v)\bigcap D|=1$

$\\{$

If $v\in Y$

Pick a vertex $u\in N(v)\bigcap X$.

Let $D^{\prime}=D^{\prime}\bigcup\\{u\\}$

else

$D^{\prime}=D^{\prime}\bigcup\\{v\\}$

$\\}$

Clearly $D^{\prime}$ remains to be connected. Since stage ends only when any
vertex in $V(Q)$ has at least 2 neighbors in $D^{\prime}$. So the final
$D^{\prime}$ is a connected $2$-dominating set. Let $k$ be the number of
iterations executed. Since we add a vertex in $X$ to $D^{\prime}$, $|X|$
reduces by 1 in every iteration, $k\leq|X|\leq\frac{1}{2}(n-|D|)$, so
$|D^{\prime}|\leq|D|+k\leq|D|+\frac{1}{2}(n-|D|)=\frac{1}{2}n+\frac{1}{2}|D|$.
∎

For a connected $(P_{5},C_{5})$-free graph $G$ with $\delta\geq 3$, we can
derive the following result by Theorem 2.1, Theorem 3.2, Theorem 3.3 and Lemma
3.1.

######  Theorem 3.4.

For every connected $(P_{5},C_{5})$-free graphs $G$ with $\delta(G)\geq 3$,
$rx_{3}(G)\leq\frac{11}{16}n+3$.

###### Proof.

For every connected $(P_{5},C_{5})$-free graphs $G$ with $\delta(G)\geq 3$,
from the Theorem 3.2, $\gamma(G)=\gamma_{c}(G)$. And by the Theorem 3.3, we
have $\gamma(G)\leq\frac{3n}{8}$. Thus, $\gamma_{c}(G)\leq\frac{3n}{8}$.
Combining this with Lemma 3.1, the graph $G$ have a connected $2$-dominating
set $D$ with order less than $\frac{11}{16}n$. Observe that the connected
$2$-dominating set $D$ can get a 3-rainbow coloring using $|D|-1$ colors by
ensuring that every edge of some spanning tree gets distinct color. So the
upper bound follows immediately from Theorem 2.1. ∎

##  4 Upper bounds for $3$-rainbow index of general graphs

In this section, we derive a sharp bound for $3$-rainbow index of general
graphs by block decomposition. And we also show a better bound for $3$-rainbow
index of general graphs with $\delta(G)\geq 3$ by connected $2$-dominating
set.

Let $\mathcal{A}$ be the set of blocks of $G$, whose element is $K_{2}$; Let
$\mathcal{B}$ be the set of blocks of $G$, whose element is $K_{3}$; Let
$\mathcal{C}$ be the set of blocks of $G$, whose element $X$ is a cycle or a
block of order $4\leq|V(X)|\leq 6$; Let $\mathcal{D}$ be the set of blocks of
$G$, whose element $X$ is not a cycle and $|V(X)|\geq 7$.

######  Theorem 4.1.

Let $G$ be a connected graph of order $n~{}(n\geq 3)$. If $G$ has a block
decomposition $B_{1},B_{2},\cdots,B_{q}$, then $rx_{3}(G)\leq
n-|\mathcal{C}|-2|\mathcal{D}|-1$, and the upper bound is tight.

###### Proof.

Let $G$ be a connected graph of order $n$ with $q$ blocks in its block
decomposition. If $q=1$, then we have done by Theorem 1.1 and
$rx_{3}(K_{3})=2$, which satisfies the above bound. Thus, we suppose $q\geq
2$.

Note that $|\mathcal{A}\cup\mathcal{B}\cup\mathcal{C}\cup\mathcal{D}|=q$. From
the Theorem 1.1, we get $rx_{3}(X)\leq|X|-2$ for $X\in\mathcal{C}$ and
$rx_{3}(X)\leq|X|-3$ for $X\in\mathcal{D}$. Hence, it follows that

$\displaystyle rx_{3}(G)$ $\displaystyle\leq$
$\displaystyle\sum_{X\in\mathcal{A}}1+\sum_{X\in\mathcal{B}}2+\sum_{X\in\mathcal{C}}(|X|-2)+\sum_{X\in\mathcal{D}}(|X|-3)$
$\displaystyle=$ $\displaystyle n-|\mathcal{C}|-2|\mathcal{D}|-1.$

In order to prove that the upper bound is tight, we construct the graph $G$ of
order $n$, as shown in Figure 1, consisting of $(n-3r-7)$ $K_{2}$, $r$ cycles
of order 4 and one 7-length-cycle with a chord. It is clear that
$|\mathcal{C}|$=$r$, $|\mathcal{D}|=1$. We consider the size of a rainbow tree
$T$ contain the vertices $\\{u,v,w\\}$. $|E(T)|=n-4r-7+3r+4=n-r-3$ and
$rx_{3}(G)\leq n-|\mathcal{C}|-2|\mathcal{D}|-1=n-r-3$ by the above theorem.
we have $rx_{3}(G)=n-|\mathcal{C}|-2|\mathcal{D}|-1$.

Figure 1: Graph for Theorem 4.1

∎

We finish this section with general graphs with minimal degree at least $3$.
Here, we denote as $q_{max}(G)$ the maximum number of components of
$G\backslash u$ among all vertices $u\in V$. The following result is needed in
the sequel.

######  Theorem 4.2.

[9] Let G be a connected graph on $n$ vertices with minimum degree $\delta\geq
2$ and let $k$ be an integer with $1\leq k\leq\delta$. Then
$\gamma_{k}^{c}\leq n-q_{max}(G)(\delta-k+1)$

For general graphs with $\delta\geq 3$, we obtain an upper bound for
$3$-rainbow index from Theorem 2.1 and Theorem 4.2.

######  Theorem 4.3.

Let $G$ be a connected graph with minimal degree $\delta\geq 3$. Then
$rx_{3}(G)\leq n-q_{max}(\delta-1)+3$.

Note that the bound of $3$-rainbow index is better for the graphs with cut
vertices and larger minimal degree.

## References

  * [1] J. A. Bondy, U. S. R. Murty, Graph Theory, Springer, 2008.
  * [2] Y. Caro, A. Lev, Y. Roditty, Z. Tuza, R. Yuster, On rainbow connection, Electron. J. Combin 15(1), 2008, R57.
  * [3] S. Chakraborty, E. Fischer, A. Matsliah, R. Yuster, Hardness and algorithms for rainbow connection, J. Combin. Optim. 21, 2010, pp. 330-347.
  * [4] L. S. Chand, A. Das, D. Rajendraprasad, N. M. Varma, Rainbow connection number and connected dominating sets, Electronic Notes in Discrete Math. 38, 2011, pp. 239-244.
  * [5] G. Chartrand, F. Okamoto, P. Zhang, Rainbow trees in graphs and generalized connectivity, Networks, DOI, 2010.
  * [6] G. Chartrand, G. L. Johns, K. A. MeKeon, P. Zhang, Rainbow connection in graphs, Math. Bohem 133(1), 2008, pp. 85-98.
  * [7] L. Chen, X. Li, K. Yang, Y. Zhao, The 3-rainbow index of a graph. arXiv:1307.0079V3 [math.CO] (2013).
  * [8] X. Chen, X. Li, A solutuon to a conjecture on the rainbow connection number, Ars Combin., 104, 2012, pp. 193-196.
  * [9] Adriana Hansberg, Bounds on the connected $k$-domination number in graphs, Discrete Applied Mathematics 158, 2010, pp. 1506-1510.
  * [10] X. Li, S. Liu, Rainbow Connections number and the number of blocks, Graphs and Combin., in press.
  * [11] X. Li, Y. Shi, Y. Sun, Rainbow connections of graphs—A survey, Graphs and Combin 29, 2013, pp. 1-38.
  * [12] X. Li, Y. Sun, Rainbow connection numbers of line graphs, Ars Combin., 100, 2011, pp. 449-463.
  * [13] B. Reed, Paths, stars, and the number three, Combinatorics, Probability Computing 5(3),1996, pp. 277-295.
  * [14] I. E. Zverovich, Perfect connected-dominant graphs. Discuss. Math. Graph Theory 23, 2003, pp. 159-162.


#  LM2: A Simple Society of Language Models Solves Complex Reasoning

Gurusha Juneja
Microsoft Research, India
<EMAIL_ADDRESS>
&Subhabrata Dutta††footnotemark:
IIT Delhi, India
<EMAIL_ADDRESS>
&Tanmoy Chakraborty
IIT Delhi, India
<EMAIL_ADDRESS>Equal contribution

###### Abstract

Despite demonstrating emergent reasoning abilities, Large Language Models
(LLMS) often lose track of complex, multi-step reasoning. Existing studies
show that providing guidance via decomposing the original question into
multiple subproblems elicits more robustness in LLM reasoning – a decomposer
generates the subproblems, and a solver solves each of these subproblems.
However, these techniques fail to accommodate coordination between the
decomposer and the solver modules (either in a single model or different
specialized ones) – the decomposer does not keep track of the ability of the
solver to follow the decomposed reasoning. In this paper, we propose LM2 to
address these challenges. LM2 modularizes the decomposition, solution, and
verification into three different language models. The decomposer module
identifies the key concepts necessary to solve the problem and generates step-
by-step subquestions according to the reasoning requirement. The solver model
generates the solution to the subproblems that are then checked by the
verifier module; depending upon the feedback from the verifier, the reasoning
context is constructed using the subproblems and the solutions. These models
are trained to coordinate using policy learning. Exhaustive experimentation
suggests the superiority of LM2 over existing methods on in- and out-domain
reasoning problems, outperforming the best baselines by 8.1% on MATH, 7.71% on
JEEBench, and 9.7% on MedQA problems (code available at
https://github.com/LCS2-IIITD/Language_Model_Multiplex).

LM2: A Simple Society of Language Models Solves Complex Reasoning

Gurusha Juneja††thanks: Equal contribution Microsoft Research, India
<EMAIL_ADDRESS>Subhabrata Dutta††footnotemark:  IIT Delhi, India
<EMAIL_ADDRESS>Tanmoy Chakraborty IIT Delhi, India<EMAIL_ADDRESS>

##  1 Introduction

Recent trends in solving complex reasoning tasks using Large Language Models
(LLMs) typically follow two different dominant approaches: (i) well-curated
prompting techniques (Zheng et al., 2023; Yao et al., 2024) on LLMs of
exorbitant size like GPT-4 (OpenAI, 2023), or (ii) finetuning a relatively
smaller LLM using domain-focused data (Shao et al., 2024; Toshniwal et al.,
2024; Dutta et al., 2024). Methods from the former category heavily rely on
the proprietary LLM being used and are prone to fail absolutely when employed
with less powerful models. The latter category, though cost-effective compared
to humongous LLMs, often loses in generalizability due to a narrow training
domain.

The chronicle of decomposed reasoning. A number of recent literature has
pointed out that LLMs tend to perform better on complex reasoning tasks when
the problem is decomposed into step-by-step subproblems (Zhou et al., 2023;
Khattab et al., 2022; Juneja et al., 2023). Earlier techniques demonstrated
the superiority by providing the model with examples containing the original
problem decomposed into multiple sub-problems along with their answers (Zhou
et al., 2023). However, Juneja et al. (2023) illustrated that decoupling the
decomposer from the solver by finetuning a separate decomposer language model
(LM) to coordinate with a larger solver LM is beneficial to simply prompting a
single monolithic LM to decompose and solve. Echoing their findings, Wu et al.
(2024) also found that distilling decomposition abilities from a larger LM to
a smaller LM is much more generalizable compared to decomposing the solver
abilities directly.

Figure 1: The inference procedure of LM2 on a question from the MATH dataset.
A question (in blue) is provided to the Solver LM that produces an incorrect
answer (in red). The question is then provided to the Decomposer LM that
generates the concepts and step-by-step subquestions (in lilac). Each
subquestion is answered by the Solver LM, and the sub-answer is verified by a
Verifier LM. If the Verifier LM approves the sub-answer, that subqustion-
subanswer pair is added to the context of reasoning steps; otherwise, a new
subquestion is generated. The question, concepts, subquestions, and subanswers
are provided in context to the Decomposer LM to generate the next subquestion.
Finally, the question, concepts, subquestions, and subanswers are provided to
the Solver LM to generate the final answer (in green).

Our contributions. However, a major bottleneck in existing methods of
decomposer finetuning is the lack of tightness between the decomposer-solver
interactions. Typically, the decomposition is done in a memoryless manner,
with or without the solver’s initial response; no strategy is employed to
track whether the solver can follow the decomposed chain of reasoning. Towards
this very end, we propose a novel multi-LLM coordination framework, Language
Model Multiplex (LM2). LM2 is built upon three separate LMs, each dedicated to
three different components of complex multistep reasoning – a solver LM is
responsible for answering questions; a verifier LM provides feedback on the
correctness of the output from the solver, and a decomposer LM identifies the
basic concepts required to solve the problem and generates step-by-step
subproblems by decomposing the original question (see Figure 1 for a working
example). Unlike prior approaches, the decomposer in LM2 generates each
subproblem depending on the solver’s answers to prior subproblems, along with
the verifier’s feedback on those answers. Furthermore, the decomposer
generates the conceptual requirements to solve the problem, which further
streamlines the solver LM. Irrespective of the complexity of the underlying
reasoning, the world knowledge required to answer any question is typically
better preserved in larger, proprietary LMs. Considering this, we use GPT-3.5
(text-davinci-003) as the solver without finetuning. For both the decomposer
and verifier, we implement parameter-efficient fine-tuning (Hu et al., 2022)
of LLaMA-2 (13 billion parameters) separately. First, these models are
finetuned separately towards the tasks of decomposition and verification using
datasets annotated by GPT-4. The decomposer is then taught to coordinate with
the solver and the verifier models in a policy learning setup. LM2 achieves
promising performance across a diverse set of reasoning tasks. On the MATH
dataset of mathematical reasoning, LM2 outperforms the best decomposer-tuning
baseline by a staggering margin 8.1% of absolute accuracy on average. Although
LM2 uses the training split of the MATH dataset for tuning the decomposer and
the solver, it seamlessly generalizes to out-of-distribution tasks in MedQA
and JEEBench, outperforming the best competitive baseline with 9.7 % and 7.71%
difference on absolute accuracy respectively.

Beyond the discourse of overall numbers, we perform in-depth ablation analyses
to identify the roles of each component of the model. We observe that (i) the
verifier LM and concept generated by the decomposer LM play a crucial role in
generalizing out-of-distribution reasoning tasks like MedQA, JEEBench
Chemistry, etc.; (ii) finetuning the decomposer is crucial for better concept
identification – finetuned LLaMA-2 7B generates more effective conceptual
requirements compared to even GPT-4; (iii) even while not using all the
modular components of LM2, the prompt template of structured reasoning boosts
the performance of GPT-4.

##  2 Related Work

The efficacy of explicitly generating intermediate reasoning steps over direct
generation of the required answer was first demonstrated by Nye et al. (2021).
Chain-of-thought prompting (Wei et al., 2022) generalized the scratchpad
learning of Nye et al. (2021) into an in-context learning regime using LLMs.
Chain-of-thought and its successors (Chen et al., 2022; Yao et al., 2024)
typically let the decomposition of a composite, multi-step reasoning problem
remain implicit in the LLM.

Zhou et al. (2023) demonstrated that instead, an explicit call to the LLM to
generate multiple smaller problems that are steps to answer the original query
achieves more robust reasoning. Their proposed method, Least-to-Most
prompting, uses these simpler subproblems and their answers as the context to
solve the original problem. Similarly, Khot et al. (2023) proposed a
prompting-based problem decomposition approach where the LLM is asked to
decompose a complex task using few-shot examples. However, this still burdens
a single language model in handling both decomposition and solution. Juneja et
al. (2023) circumvented this challenge by distilling the decomposition
abilities into a relatively smaller language model. Their proposed method,
DaSLaM, utilizes two separate language models that coordinate with each other
to solve complex reasoning problems. Their findings suggest that finetuning
the decomposer is more generalizable than finetuning the solver model. This
has been further supported by Wu et al. (2024) recently. Tarasov and Shridhar
(2024) explored the distillation of decomposition abilities via offline
reinforcement learning. Khattab et al. (2022) proposed a programmatic
retrieval augmentation framework, namely Demonstrate-Search-Predict (DSP), for
knowledge-intensive generation tasks. DSP relies on the coordination between a
generative LM and a retrieval model through sophisticated programs. Recent
attempts have been made to incorporate dense verifiers (typically, a
finetuned, bidirectional language model acting as a classifier) aiding a
generative model towards robust, verifiable problem solving and text
generation (Cobbe et al., 2021; Sun et al., 2023). Different techniques for
verification of LM-generated outputs have been proposed subsequently, such as
self-verification (Weng et al., 2023), majority voting (Li et al., 2023), etc.

##  3 Methodology

Our proposed method, LM2, is built upon the coordination of multiple LMs to
perform reasoning in a modular fashion. However, such coordination is not
implicit in the pertaining stage of a model; instead, we seek to inculcate
this ability via finetuning (parts of) the LM multiplex. To this end, LM2 is
built upon three functional components: a (preferably larger) solver model, a
decomposer model, and a verifier model.

For fine-grained control over the function of the different components of LM2,
we make use of a structured, step-by-step input-output framework (see Figure
1). The role of each of the modules in LM2 is described as follows.

###  3.1 Decomposer

The decomposer LM guides the solver LM to solve a multi-step reasoning
question in two ways. First, it provides the solver model with a set of
concepts required to solve the problem. Second, it tells the solver LM what is
the next sub-question required to solve given the previous sub-questions and
their answers. More specifically, the decomposer LM is a function that can be
defined as $D(q,\\{s_{i},sa_{i}\\},c):Q\times S\times SA\rightarrow\\{S,C\\}$,
where $q$ represents the initial question to be solved, $\\{s_{i},sa_{i}\\}$
denotes the set of previous sub-questions ($s_{i}$) and their corresponding
answers ($sa_{i}$), and ($c$) signifies whether the function needs to predict
the concept or the next sub-question. $Q$ is the space of all the questions,
$S$ is the space of all sub-questions, $SA$ is the space of all sub-answers,
and $C$ is the space of all concepts.

Supervised finetuning. The decomposer training is performed in two stages
similar to Juneja et al. (2023). The first stage is supervised finetuning,
where the language model is finetuned on a dataset prepared using GPT-4. To
create the dataset, we provided GPT-4 with a question and its gold reasoning.
It was then asked to first generate all the concepts required to solve the
question, followed by sub-questions and sub-answers. Only the questions that
were answered correctly were included in the dataset. Each sample in the
dataset can be expressed as a tuple
$\\{Q,c,\\{s_{i},sa_{i}\\}_{i=1}^{n},s_{n+1}\\}$, where $s_{n+1}$ is the next
sub-question given the previous sub-questions and answers. The decomposer was
then finetuned on the standard language modelling objective.

Policy optimization. With the supervised finetuning step, the decomposer LM is
conditioned to respond to reasoning problems with concepts and decomposed
subquestions. However, it is still not able to take the feedback from the
solver and the verifier models into account. To this end, we utilize Proximal
Policy Optimization (Schulman et al., 2017) with the decomposer as the policy
and the solver and the verifier model as a black-box environment. Precisely,
we compute different types of rewards utilizing the feedback from the verifier
model that takes the solver model’s response into account at each step and
provides the decomposer with necessary refinement signals.

###  3.2 Verifier

Given the complexity of multistep reasoning, we need the verifier to be able
to provide nuanced feedback to the decomposer on the possible mistakes made by
the solver; a binary correct/incorrect message as employed by prior works with
verifiers (Li et al., 2023; Weng et al., 2023) will limit the decomposer
model’s scope of vision. For fine-grained control, the verifier is finetuned
on a supervised dataset containing a question, an answer with an error made in
the correct answer, a classification for the type of error, and an explanation
for the classification. The verifier classifies the given input into nine
classes as follows: 1 Conceptual mistakes, 2 Computational mistakes, 3
Procedural mistakes, 4 Misunderstood question, 5 Mistake in the first step, 6
Mistake in first half, 7 Mistake in second half, 8 Mistake in last step, and 9
No mistake. The dataset was produced using GPT-4, asking it to generate an
explanation for the classification given the correct solution, wrong solution
and the classification. The verifier is finetuned to generate the explanation
and the classification (see Section 3.3 for examples of each type of error
message and explanation).

###  3.3 Training with Decomposer Feedback

The training dataset curated for the decomposer LM consists of only the
correct answers; hence, the decomposer is blind to the possible errors that
the language model can make. In order to make the decomposer generate
meaningful questions, we further finetune the decomposer while working in
synergy with the solver language model using Policy gradient methods.

Environment. The environment consists of a black-box solver model $\Theta$.
The model $\Theta$ generates an answer to the current question given the
concepts and previous questions and their answers.

Policy, action and state space. The decomposer language model $\phi$ comprises
the policy network. A state $s$ in the state space $S$ is defined by the
concatenation of the initial state $s_{0}$ and all the actions taken from the
initial state to the current state. The initial state $s_{0}$ is defined as
the initial question $Q$. The action space is defined as the token space of
the language model $\phi$. Hence, a state $s_{n}$ can be represented as
$(s_{0},\\{a_{i}\\}_{i=1}^{n})$, where $a_{i}$ is the action taken at the
$i_{th}$ time step.

Reward function. The reward is based on the feedback given by the verifier at
each sub-question produced by the decomposer. The reward structure is
intuitively designed to impose penalties for errors occurring in earlier sub-
questions relative to those occurring in later ones. This is because fixing an
early mistake can significantly increase the chances of the question being
correct. Further, the policy is penalised more for conceptual and procedural
mistakes as compared to computational mistakes. We construct the reward
function for the $k^{th}$ sub-question as follows:

$R=\gamma^{k}\sum_{i=1}^{9}{r_{i}}$ (1)

where $\gamma<1$ is the discount factor responsible for imposing more
penalties on the earlier generations. $r_{i}$ are the rewards for individual
feedback given by the verifier as defined below (for each type of reward, we
provide an example question asked by the decomposer, an erroneous answer to
that question by the solver, type of error identified and the explanation
generated by the verifier in red textboxes).

Conceptual correctness reward is defined as,

$r_{1}=-0.15I[V(s_{k},sa_{k})=1]$ (2)

where $I$ is the indicator function, $V$ is the verifier that takes in input
the $k^{th}$ sub-question ($s_{k}$) and its answer produced by the solver
($sa_{k}$) and outputs the category of mistake. This reward accounts for any
mistake made by the solver in understanding or while applying a concept
incorrectly.

$\mathbf{Q}$: What is $a$, $b$, $c$ in terms of common difference $d$?
$\mathbf{A:}$Since $a$, $b$, and $c$ form an arithmetic sequence, we can
express $c$ in terms of $a$ as $c=a+d$, where $d$ is the common difference.
$\mathbf{Verifier}$: Conceptual Mistakes: The student misunderstood the
concept of finding the possible values of the common difference in an
arithmetic sequence to form a triangle with a given perimeter.

Computational correctness reward is defined as,

$r_{2}=-0.05I[V(s_{k},sa_{k})=2]$ (3)

This reward accounts for cases where the model has made any mistakes in
calculation or formula application. These kinds of mistakes are weighted less
compared to all other types because an external tool can be easily used for
these mechanical tasks.

$\mathbf{Q}:$ What is the value of $a+c$? $\mathbf{A}:$ Since we are given
that $a$, $b$, and $c$ form an arithmetic sequence, we can express $b$ as the
average of $a$ and $c$. This gives us $b=\frac{a+c}{2}$. The perimeter of the
triangle is given by $P=a+b+c=a+\frac{a+c}{2}+c=\frac{3a+3c}{2}$. We are given
that the perimeter is 60 units, so we have $60=\frac{3a+3c}{2}$. Solving for
$a+c$, we get $a+c=20$ $\mathbf{Verifier:}$ Calculation Mistakes: The model
has made a calculation mistake while calculating the value of $a+c$. $a+c$
should be 40.

Procedural correctness reward is defined as,

$r_{3}=-0.15I[V(s_{k},sa_{k})=3]$ (4)

This encompasses any mistake made by the model while following a step-by-step
procedure whose information is already given in-context while solving the
problem.

$\mathbf{Q}:$ What are the possible values of $a,d$? $\mathbf{A}:$
Substituting this into the equation $a+c=20$, we get $a+(a+d)=20$, which
simplifies to $2a+d=20-a$. Since the side lengths must be integers, $a$ and
$d$ must be integers. We can then try different values of $a$ and $d$ that
satisfy the equation $2a+d=20-a$. After trying different values, we find that
the only solution that gives integer side lengths is $a=10$ and $d=20$.
$\mathbf{Verifier:}$ Procedural Mistakes: The student made a mistake in the
procedure of solving the problem by not accurately finding the possible values
of the common difference.

Question understanding reward is defined as,

$r_{4}=-0.2I[V(s_{k},sa_{k})=4]$ (5)

This reward accounts for the cases when the model has made a mistake in
understanding the sub-question. Either it has not answered the quantity asked
in the sub-question. This gives a signal that the sub-question was either
incoherent with the previous questions or was too complex for the model to
answer. This kind of mistake is important to address and, hence, is given a
higher weight.

$\mathbf{Q}:$ How many distinct values of $a,b,c$ are possible? $\mathbf{A}:$
This gives us the side lengths of the triangle as $a=10$, $b=15$, and $c=30$.
$\mathbf{Verifier:}$ Mistakes Understanding Question: The model has made a
mistake by not giving the number of distinct values.

Reward based on place of mistake. As discussed above, later mistakes are
penalised less than the earlier ones. Hence, if a mistake is made in the first
step, it is given a reward of $-0.2$. If the model makes a mistake in the
first half of the sub-answer, it is given a reward of $-0.12$. For a mistake
in the last half of the sub-answer, it is given a reward of $-0.08$. If the
mistake is made in the last step, it is given a reward of $-0.05$.

No-mistake rseward is the case when the model has not made any mistake in
answering the sub-question and is given a positive reward of $+1$.

###  3.4 Inference

During the inference, the decomposer, solver, and verifier models work
together to answer a given question (see working example in Figure 1). During
the inference, the decomposer first produces a list of concepts required to
solve the question. Then, given the question and concepts as context, the
decomposer produces a sub-question. The sub-question is answered by the
solver. Now, given the sub-question and sub-answer, the verifier provides
feedback in the form of a multi-class classification into the above-described
classes of mistakes. If the feedback provided by the verifier consists of
either a conceptual mistake, procedural mistake, mistake in understanding or
mistake in the first step, we again generate the sub-question.

##  4 Experiments

For all the experiments, LM2 uses the OpenAI text-davinci-003 model (hereafter
mentioned as GPT-3.5) as the solver and LLaMA-2 13B (Touvron et al., 2023) as
the base models for the decomposer and the verifier.

###  4.1 Training data curation

For the first stage of finetuning of the decomposer LM, we curated a dataset
of $15,396$ question, concept, sub-question, sub-answer tuples. The questions
were taken from the train split of the MATH dataset (Hendrycks et al., 2021).
The questions were taken from the MATH dataset. For verifier LM finetuning, a
dataset of $3,674$ question-answer-classification tuples was generated.
Details of the prompts used for each of these steps are provided in Appendix
A.

###  4.2 Training details

We finetune LLaMA2-13B for both the decomposer and verifier. We train for 8
epochs with a batch size of 128, learning rate 2e-5, warmup steps of 100, a
Lora r value of 4, LoRA Alpha of 16 and dropout of 0.05. The models were
trained in 8-bit quantization on an 80G A100 GPU.

For the second stage of fine-tuning, we finetuned the last 3 layers of LoRA
adapters, using a batch size of 16, gradient accumulation steps=4, init kl
coef=0.01, target=4. For inference, we used a temperature of 0 in all
experiments for consistency of results with a max output length of 2000.

###  4.3 Evaluation

We evaluate our method on hard reasoning datasets that require multi-step
reasoning. These datasets include MATH (Hendrycks et al., 2021) (test split),
JEEBench (Arora et al., 2023), and MedQA (Jin et al., 2020) (English
questions). The MATH dataset contains math questions from challenging math
competitions, since it was also used for training, this shows our performance
on in-domain questions. Next, we evaluate on the out-of-distribution datasets
like JEEBench which contains PCM questions extracted from the JEE Advanced
exam and MedQA which contains open-domain questions from professional medical
board exams. We only evaluate questions in the English language.

###  4.4 Baseline Details

We compare LM2 with five existing methods: Chain-of-thought prompting (CoT)
(Wei et al., 2022), Least-to-most prompting (L2M) (Zhou et al., 2023),
Progressive Hint Prompting (PHP) (Zheng et al., 2023), Demonstrate-Search-
Predict (DSP) (Khattab et al., 2022), and DaSLaM (Juneja et al., 2023). The
original setting of PHP requires an 8-shot prompting; however, since all other
methods including LM2 predict in the zero-shot setting, we use PHP in 1-shot
for a fairer comparison.

###  4.5 Ablation Study

In our investigation, we perform five types of ablation studies aimed at
comprehensively understanding the significance of each component within the
LM2 pipeline.

We start with investigating the relevance of the verifier by conducting an
experiment where we remove it entirely (LM2$\setminus$V). Here, we accept each
question generated by the decomposer during the inference process without any
verification. Then, we explore the role of concepts within the pipeline. Here,
we alter the approach by instructing the decomposer to directly generate sub-
questions, without providing the concepts to the Solver LM during the answer
generation phase (LM2$\setminus$C). Following this, we investigate the
incremental gains achieved through the second stage of finetuning via policy
learning. To accomplish this, we analyze the performance of the decomposer
checkpoint after the initial stage of fine-tuning, referred to as
(LM2$\setminus$RL).

To assess the impact of different types of rewards provided, we partition the
rewards into two distinct categories: i) based on the type of mistake, which
encompasses conceptual, computational, procedural, and question understanding
correctness, and ii) based on the position of mistake. Subsequently, we come
up with two ablation variants, finetuned using each category of rewards:
LM2-Type and LM2-Position.

Dataset | Method |
---|---|---
CoT | L2M | PHP | DSP | DaSLaM | LM2
PnC | $16.4$ | $16.0$ | $10.2$ | $16.2$ | $21.4$ | $\bf 30.0$
NT | $14.4$ | $11.0$ | $9.8$ | $20.3$ | $26.1$ | $\bf 41.0$
ALG | $27.6$ | $22.4$ | $24.0$ | $15.3$ | $33.4$ | $\bf 34.0$
I-ALG | $16.4$ | $16.8$ | $10.0$ | $17.0$ | $24.8$ | $\bf 27.8$
Calc. | $14.0$ | $14.58$ | $14.28$ | $18.8$ | $18.2$ | $\bf 34.0$
P-ALG | $32.3$ | $28.0$ | $26.5$ | $28.0$ | $44.0$ | $\bf 47.0$
Geom. | $14.2$ | $12.5$ | $14.0$ | $5.2$ | $21.4$ | $\bf 32.0$
MedQA | $50.3$ | $49.8$ | $47.5$ | $52.3$ | $50.1$ | $\bf 57.1$
Table 1: Performance comparison of LM2 with the baselines on MATH and MedQA datasets using GPT-3.5 as the solver LM. Method | Dataset |
---|---|---
Phy. MCQ |  Math. MCQ |  Phy. Multi. |  Math. Multi. |  Phy. Num. |  Math. Num. |  Phy. Int. |  Math. Int. |  Chem. Int. |  Chem. Num. |  Chem. Multi. |  Chem. MCQ
CoT | 33.33 | 21.9 | 6.25 | 12.0 | 3.03 | 1.69 | 12.5 | 10.8 | 17.3 | 11.6 | 11.6 | 40.0
PHP | 22.22 | 17.07 | 6.25 | 7.59 | 3.03 | 1.69 | 0* | 4.0 | 11.7 | 9.7 | 12.2 | 37.5
L2M | 22.22 | 21.9 | 6.25 | 12.5 | 3.03 | 3.38 | 10.0 | 10.8 | 13.0 | 9.7 | 10.0 | 20.0
DaSLaM | 55.5 | 29.5 | 18.7 | 16.0 | 6.06 | 10.1 | 15.7 | 11.7 | 14.2 | 9.2 | 11.6 | 14.6
GPT4 | 55.5 | 34.1 | 27.5 | 21.5 | 15.1 | 11.8 | 22.7 | 24.3 | 17.9 | 25.5 | 48.3 | 60.0
LM2 | 51.85 | 30.18 | 26.8 | 16.4 | 15.15 | 13.1 | 16.2 | 13.5 | 26.0 | 23.2 | 26.6 | 53.3
LM2$\setminus$V | 37.03 | 24.52 | 14.6 | 11.7 | 12.2 | 11.4 | 11.4 | 11.7 | 17.3 | 16.2 | 13.3 | 30.0
LM2$\setminus$C | 29.62 | 20.75 | 14.6 | 9.4 | 9.09 | 10.8 | 9.0 | 8.1 | 17.3 | 11.6 | 13.3 | 16.6
GPT4-C | 29.62 | 28.3 | 14.6 | 11.5 | 15.15 | 11.4 | 9.0 | 11.4 | 21.7 | 23.2 | 33.33 | 30.0
LM2$\setminus$RL | 33.33 | 21.9 | 18.7 | 12.7 | 12.2 | 10.1 | 10.0 | 8.1 | 17.3 | 12.4 | 13.3 | 27.3
LM2-Type | 46.1 | 28.0 | 20.3 | 14.0 | 13.4 | 11.4 | 15.0 | 13.5 | 24.0 | 23.2 | 23.6 | 45.4
LM2-Position | 38.4 | 24.52 | 16.0 | 12.9 | 12.2 | 11.4 | 15.0 | 10.8 | 24.0 | 20.6 | 20.3 | 33.0
GPT35-SP | 33.3 | 29.2 | 7.5 | 12.6 | 9.0 | 8.4 | 12.5 | 8.0 | 17.6 | 9.2 | 12.2 | 41.6
GPT4-SP | 61.1 | 36.5 | 30.0 | 26.5 | 30.0 | 14.2 | 43.75 | 32.0 | 17.6 | 36.5 | 49.1 | 66.6
Table 2: Performance of LM2 on JEEBench Dataset along with baselines and
ablation variants. (Top third) we highlight best and second best methods in
boldface and underline. LM2 generally outperforms all existing prompting
techniques with GPT-3.5 on different topics and different types of questions
(other than Physics MCQ questions). In 3/12 cases, LM2 outperforms GPT-4.
(Middle third) we observe a large drop in performance with each ablation
variant, pointing towards an efficient integration of these modules into LM2
(see Section 4.5 for the description of each variant). (Bottom third)
Performance of the structured answer generation employed in LM2, without
decomposer and verifier, using GPT-3.5 and GPT-4 as solvers.

##  5 Results

We summarize the performance of LM2 along with the baseline methods on the
MATH and MedQA datasets in Table 1 and on the JEEBench dataset in Table 2.
Across all the datasets, LM2 improves upon existing methods (using GPT-3.5
solver) by a huge margin. It demonstrates an average $8\%$ improvement on the
MATH dataset and an average $2.5\%$ improvement on the JEEBench dataset as
compared to the best-performing baseline DaSLaM.

Can it improve on out-of-domain tasks? In both DaSLaM and LM2, the solver
model is kept frozen with the hope of retaining generalizability. However, the
decomposer model in both methods (and the verifier in LM2) are finetuned using
mathematical reasoning problems. This raises the question of the
generalizability of these finetuned components over problems other than
mathematical reasoning. One of the most significant challenges with DaSLaM is
that it is not able to perform well on out-of-domain tasks like JEEBench
Chemistry. We find that our method can surpass this limitation as can be seen
in Tables 1 (MedQA) and 2 (JEEBench Chemistry). While DaSLaM degrades the
performance over CoT on MedQA, LM2 achieves an absolute accuracy gain of $6.8$
percentage points.

How important is the verifier? Next, we seek to investigate the relative
importance of each component in our pipeline. We observe that the accuracy
decreases substantially upon removing the verifier model (LM2$\setminus$V in
the middle third of Table 2). We can see that there is a drop of $13.0\%$ in
Chemistry versus $10.08\%$ in Physics and $3.4\%$ in Math subsets. The
relative drop in accuracy with the ablation of the verifier is sharper with
multi-answer, numeric, and integer answer questions. This makes sense given
the computational reasoning requirement is higher in these problems and the
verifier plays a crucial role in guiding the decomposer and the solver along
the correct reasoning path.

Figure 2: Comparison of token generation cost. We depict the average number of
tokens generated by the solver model using different methods to solve the
given question averaged over 50 questions from the JEEBench dataset. Figure 3:
Comparison of GPT-4, DaSLaM and LM2 on an example from MATH dataset.

How important are the concepts? As can be seen from Table 2, removing concepts
decreases the accuracy of Physics subset by $11.6\%$, Maths subset by
$6.03\%$, and Chemistry subset by $17.5\%$. This shows that concepts also play
a very important role in improving the performance on out-of-domain datasets
like Physics and Chemistry. Typically, LM2$\setminus$C fares worse than the
rest of the ablation variants, demonstrating that the concepts are the most
important component in LM2.

GPT-4 as concept generator? We also check how our decomposer compares to GPT-4
while generating concepts. To compare this, we prompt GPT-4 to generate
concepts given the question. We observe that there is an average decrease of
$9.13\%$ when generating concepts using GPT-4 when compared to the Decomposer
model, indicating the higher quality of concepts generated as a result of
feedback-based fine-tuning.

What is the effect of feedback-based finetuning? The effect of feedback-based
fine-tuning is evident when comparing the performance of the decomposer
without the second stage of fine-tuning alongside the verifier to that of LM2.
On average, we observe a notable decrease of $9.6\%$ in performance when the
second stage of fine-tuning is omitted. This finding highlights the
significance of fine-tuning as a crucial step in optimizing model performance.
However, the importance of concepts and the verifier appears to outweigh that
of fine-tuning. This suggests that while fine-tuning contributes to improved
model performance, the incorporation of concepts and a verifier into the model
architecture yields more substantial enhancements.

How does the structured answering template contribute? Recall that in LM2, we
introduce a novel, structured answering template for controllable coordination
between the three models. It is imperative to investigate the role of such a
template alone behind the performance boost. We make use of the template with
two different solver models, GPT-3.5 and GPT-4. As we can see in the bottom
third of Table 2 (coined as modelname-SP), both models improve upon their base
performance with our structured template. However, the stronger GPT-4 model is
able to utilize the template much more efficiently, with an average gain of
$7.8\%$ across the JEEBench problems. Typically, improvement on Physics
problems is higher than the Math problems, indicating that language models are
not very good at retrieving physics concepts and solving the problem when
using chain-of-thought prompting. It should noted that while the structured
answering template alone is a powerful boost, it is much weaker alone without
the complete coordination in LM2.

Does guided reasoning help limit token usage? An important challenge with
iteratively interacting with an LLM is the increased token usage that will
translate to expenses in either computational or monetary terms. In Figure 2,
we plot the average token usage (per problem) incurred by the solver model
(GPT-3.5) while using LM2 and DaSLaM against that of base chain-of-thought
generation. Note that we only show the token usage corresponding to the
modified responses while using LM2 and DaSLaM. Both these methods originally
use base CoT to generate the initial response and therefore, their total token
usage will always be higher than that of CoT. However, the added structure and
guided reasoning significantly reduce the token usage in the modified
response. LM2 prevails in this aspect too. A major reason behind this is the
step-by-step synergy between the decomposer, the solver, and the verifier in
LM2. Since the decomposer generates the subquestion depending upon the
response from the solver to the previous subquestion, the chances of redundant
generation decrease, as opposed to DaSLaM where the subquestions are generated
all at once.

Example analysis. To further understand the nuances of LM2, we perform an
analysis of the generated output on an example from the MATH dataset (see
Figure 3). We compare between LM2, DaSLaM and GPT-4 with CoT. As we can see,
GPT-4 makes an incorrect interpretation of the question itself. It assumes
that the total journey after delay takes 10 hours, leading to an incorrect
choice of option. The subquestions produced by DaSLaM do not adhere to the
order of reasoning required to solve the problem and generate redundant
questions. It starts with asking What is the total distance to be covered?
However, in the second question, it asks for the speed of the train which is
already given in the question itself. The 3rd subquestion generated by DaSLaM
is actually the original question, and the solver makes a numerical mistake by
simplifying the fraction $\frac{\frac{3d}{4}}{75}$ to $\frac{d}{300}$ instead
of $\frac{d}{100}$. Without a verifier, this erroneous response is integrated
into the reasoning context of the solver. In the next questions, the same
problem is asked to be solved and the solver continues to make incorrect
responses. With LM2, we observe a much more well-defined, crisp line of
questioning by the decomposer model; the solver is able to reach the correct
answer option without regenerating the same information or drawing incorrect
subanswers.

##  6 Conclusion

In this paper, we present LM2, a cooperative cohort of generative language
models working together to solve complex reasoning problems. LM2 utilizes a
frozen solver model that is guided to solve reasoning problems by
incrementally answering questions framed by a decomposer model and checked by
the verifier model that is trained to coordinate with each other. We find that
LM2 proves its supremacy over existing methods over a variety of reasoning
tasks, both in-domain and out-domain. We find that despite being trained using
mathematical reasoning examples, our proposed structured response scheme along
with the fine-grained verification strategy plays a crucial role in
generalizing LM2 to heavily out-of-distribution tasks like medical question
answering and chemistry.

Limitations. Despite promising results, LM2 bears some inherent limitations.
Compared to purely prompting-based methods, it requires a certain
computational overhead for the two-staged training. With proprietary LLM-based
solvers, LM2 incurs extra token usage over single-pass solutions like chain-
of-thought. Implicit limitations of the solver model, like lack of length
generalization, arbitrary digit manipulation, etc. are expected to be
inherited in LM2 as well. A possible future work can be towards incorporating
deterministic solvers and tools into the multiplex.

## References

  * Arora et al. (2023) Daman Arora, Himanshu Gaurav Singh, and Mausam. 2023.  Have llms advanced enough? a challenging problem solving benchmark for large language models.
  * Chen et al. (2022) Wenhu Chen, Xueguang Ma, Xinyi Wang, and William W Cohen. 2022.  Program of thoughts prompting: Disentangling computation from reasoning for numerical reasoning tasks.  _arXiv preprint arXiv:2211.12588_.
  * Cobbe et al. (2021) Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, Christopher Hesse, and John Schulman. 2021.  Training verifiers to solve math word problems.
  * Dutta et al. (2024) Subhabrata Dutta, Ishan Pandey, Joykirat Singh, Sunny Manchanda, Soumen Chakrabarti, and Tanmoy Chakraborty. 2024.  Frugal lms trained to invoke symbolic solvers achieve parameter-efficient arithmetic reasoning.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 38, pages 17951–17959.
  * Hendrycks et al. (2021) Dan Hendrycks, Collin Burns, Saurav Kadavath, Akul Arora, Steven Basart, Eric Tang, Dawn Song, and Jacob Steinhardt. 2021.  Measuring mathematical problem solving with the math dataset.  _NeurIPS_.
  * Hu et al. (2022) Edward J Hu, yelong shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, and Weizhu Chen. 2022.  LoRA: Low-rank adaptation of large language models.  In _International Conference on Learning Representations_.
  * Jin et al. (2020) Di Jin, Eileen Pan, Nassim Oufattole, Wei-Hung Weng, Hanyi Fang, and Peter Szolovits. 2020.  What disease does this patient have? a large-scale open domain question answering dataset from medical exams.
  * Juneja et al. (2023) Gurusha Juneja, Subhabrata Dutta, Soumen Chakrabarti, Sunny Manchanda, and Tanmoy Chakraborty. 2023.  Small language models fine-tuned to coordinate larger language models improve complex reasoning.  In _Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing_ , pages 3675–3691, Singapore. Association for Computational Linguistics.
  * Khattab et al. (2022) Omar Khattab, Keshav Santhanam, Xiang Lisa Li, David Hall, Percy Liang, Christopher Potts, and Matei Zaharia. 2022.  Demonstrate-search-predict: Composing retrieval and language models for knowledge-intensive nlp.  _arXiv preprint arXiv:2212.14024_.
  * Khot et al. (2023) Tushar Khot, Harsh Trivedi, Matthew Finlayson, Yao Fu, Kyle Richardson, Peter Clark, and Ashish Sabharwal. 2023.  Decomposed prompting: A modular approach for solving complex tasks.  In _The Eleventh International Conference on Learning Representations_.
  * Li et al. (2023) Yifei Li, Zeqi Lin, Shizhuo Zhang, Qiang Fu, Bei Chen, Jian-Guang Lou, and Weizhu Chen. 2023.  Making large language models better reasoners with step-aware verifier.
  * Nye et al. (2021) Maxwell Nye, Anders Johan Andreassen, Guy Gur-Ari, Henryk Michalewski, Jacob Austin, David Bieber, David Dohan, Aitor Lewkowycz, Maarten Bosma, David Luan, et al. 2021.  Show your work: Scratchpads for intermediate computation with language models.  _arXiv preprint arXiv:2112.00114_.
  * OpenAI (2023) OpenAI. 2023.  Gpt-4 technical report.
  * Schulman et al. (2017) John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. 2017.  Proximal policy optimization algorithms.  _CoRR_ , abs/1707.06347.
  * Shao et al. (2024) Zhihong Shao, Peiyi Wang, Qihao Zhu, Runxin Xu, Junxiao Song, Mingchuan Zhang, YK Li, Y Wu, and Daya Guo. 2024.  Deepseekmath: Pushing the limits of mathematical reasoning in open language models.  _arXiv preprint arXiv:2402.03300_.
  * Sun et al. (2023) Hao Sun, Hengyi Cai, Bo Wang, Yingyan Hou, Xiaochi Wei, Shuaiqiang Wang, Yan Zhang, and Dawei Yin. 2023.  Towards verifiable text generation with evolving memory and self-reflection.  _arXiv preprint arXiv:2312.09075_.
  * Tarasov and Shridhar (2024) Denis Tarasov and Kumar Shridhar. 2024.  Distilling llms’ decomposition abilities into compact language models.
  * Toshniwal et al. (2024) Shubham Toshniwal, Ivan Moshkov, Sean Narenthiran, Daria Gitman, Fei Jia, and Igor Gitman. 2024.  Openmathinstruct-1: A 1.8 million math instruction tuning dataset.  _arXiv preprint arXiv:2402.10176_.
  * Touvron et al. (2023) Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, Aurelien Rodriguez, Armand Joulin, Edouard Grave, and Guillaume Lample. 2023.  Llama: Open and efficient foundation language models.
  * Wei et al. (2022) Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, brian ichter, Fei Xia, Ed H. Chi, Quoc V Le, and Denny Zhou. 2022.  Chain of thought prompting elicits reasoning in large language models.  In _Advances in Neural Information Processing Systems_.
  * Weng et al. (2023) Yixuan Weng, Minjun Zhu, Fei Xia, Bin Li, Shizhu He, Shengping Liu, Bin Sun, Kang Liu, and Jun Zhao. 2023.  Large language models are better reasoners with self-verification.
  * Wu et al. (2024) Zhuofeng Wu, He Bai, Aonan Zhang, Jiatao Gu, VG Vinod Vydiswaran, Navdeep Jaitly, and Yizhe Zhang. 2024.  Divide-or-conquer? which part should you distill your llm?
  * Yao et al. (2024) Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Tom Griffiths, Yuan Cao, and Karthik Narasimhan. 2024.  Tree of thoughts: Deliberate problem solving with large language models.  _Advances in Neural Information Processing Systems_ , 36.
  * Zheng et al. (2023) Chuanyang Zheng, Zhengying Liu, Enze Xie, Zhenguo Li, and Yu Li. 2023.  Progressive-hint prompting improves reasoning in large language models.
  * Zhou et al. (2023) Denny Zhou, Nathanael Schärli, Le Hou, Jason Wei, Nathan Scales, Xuezhi Wang, Dale Schuurmans, Claire Cui, Olivier Bousquet, Quoc V Le, and Ed H. Chi. 2023.  Least-to-most prompting enables complex reasoning in large language models.  In _The Eleventh International Conference on Learning Representations_.

##  Appendix A Training Data Creation

The data was generated using GPT-4. A temperature of 0.7 is used to ensure
diversity in the generated data. We only stored the sub-question, sub-answer
dataset if the number of sub-questions generated was more than three, this was
done to ensure high data quality so that the model is able to decompose longer
and more difficult questions effectively. First, we generate all the concepts,
then the sub-questions given the question and the gold chain of thought.
Finally, we generate the sub-answer given the question, a gold chain of
thought and the sub-question to be answered. for the verifier, we first ask
the LLM to answer the given question using standard COT prompting. Then based
on the correctness of the answer, we take the solution chain of thought
produced by the LLM and the gold answer and ask the LLM to classify the
produced solution based on the mistake made. If the answer is correct, we
store it separately and include it to make up to 10% of the dataset with the
label as ’No Mistake’. Prompts for the data curation are given below.

###  A.1 Verifier Data Creation

####  A.1.1 Prompt

You are a teacher, and you are grading a student’s answer to a question. The
student’s answer is as follows: {COT_LLM} The correct answer is as follows:
{COT_gold} Please provide feedback to the students on the mistakes they have
made. You need to fill out a rubric and classify the mistakes into the
following categories:

1\. Conceptual Mistakes: The student has misunderstood the concept or has
applied the wrong concept.
2\. Computational Mistakes: The student has made a mistake in the
calculations.
3\. Procedural Mistakes: The student has made a mistake in the procedure of
solving the problem.
4\. Mistake in understanding the question: The student has made a mistake in
understanding the question.
5\. Mistake in the first step: The student has made a mistake in the first
step of the solution.
6\. Mistake in the first half: The student has made a mistake in the first
half of the solution.
7\. Mistake in the second half: The student has made a mistake in the second
half of the solution.
8\. Mistake in the last step: The student has made a mistake in the last step
of the solution.
9\. No mistake: The student has not made any mistake.

Please first provide feedback then fill the rubric and then finally tell your
feedback to the student in between <feedback> and </feedback> tags as shown
below:
For example, if you want to tell the student that they have made a mistake in
the first step and a conceptual mistake, then you need to write the following:
<feedback> 1,4 </feedback> Do not write anything else in between <feedback>
and </feedback> tags except the numbers.

Now, please provide feedback to the student on the mistakes they have made.

###  A.2 Decomposer Data Creation

####  A.2.1 Concepts data creation

I have a question’s solution, tell me all the specific concepts, theorems and
formulas (separated by a comma,) used in it. An example is given below.
Question: How many primes are in the row of Pascal’s Triangle that starts with
a $1$ followed by a $6$?
Answer: If the row contains a $1$, then a $6$, then the binomial coefficients
must be $\binom{6}{0}$ and $\binom{6}{1}$. All we need to check now are
$\binom{6}{2}$ and $\binom{6}{3}$, since $\binom{6}{0}=\binom{6}{6}$,
$\binom{6}{1}=\binom{6}{5}$ , and $\binom{6}{2}=\binom{6}{4}$.
$\binom{6}{2}=\frac{6!}{4!\times 2!}=15$, and $\binom{6}{3}=\frac{6!}{3!\times
3!}=20$. None of those is prime, so there are $\boxed{0}$ prime numbers in the
given row.
Concepts: Coefficients in Pascal’s Triangle, Binomial Coefficients Formula,
Prime Numbers
Question: question
Answer: answer
Concepts:

####  A.2.2 Sub-question data creation

I have a question, it’s a solution and a sub-question.
Your task is to break the question into sub-questions based on the steps in
the answer.
Keep the following tips in mind:
1\. Make sure not to break the question into trivial sub-questions, the sub-
questions should be informative.
2\. The sub-questions should not require multiple steps to answer, something
like 2-3 steps to solve is ideal.
3\. One way to break the question could be to identify what all quantities are
required in the question by observing it’s answer and then try to frame sub-
questions based on the unknown entities.
4\. Make sure to put each question in the question tag like $ question(What is
the acceleration of the car as a function of time?)$
One example is given below.
Question: How many primes are in the row of Pascal’s Triangle that starts with
a $1$ followed by a $6$?
Answer: If the row contains a $1$, then a $6$, then the binomial coefficients
must be $\binom{6}{0}$ and $\binom{6}{1}$. All we need to check now are
$\binom{6}{2}$ and $\binom{6}{3}$, since $\binom{6}{0}=\binom{6}{6}$,
$\binom{6}{1}=\binom{6}{5}$ , and $\binom{6}{2}=\binom{6}{4}$.
$\binom{6}{2}=\frac{6!}{4!\times 2!}=15$, and $\binom{6}{3}=\frac{6!}{3!\times
3!}=20$. None of those is prime, so there are $\boxed{0}$ prime numbers in the
given row.
Sub-questions:
$ question(How can the first two numbers be represented in form of binomial
coefficients?)$, $ question(What are the values of all the coefficients in the
row?)$, $ question(How many of the above numbers are prime?)$
Question: question
Answer: answer
Sub-questions:

###  A.3 Sub-answer data generation

I have a question, it’s solution and a sub-question.
I want you to answer the subquestion along with an explanation.
Make sure to put the sub-answer in the answer tag like $sub-answer(The
acceleration of the car at time t = 2 seconds is speed / time = 2m/s/2s =
$1m/s^{2}$)$
Think step by step.
Question: question
Answer: answer
Sub-question: sub-question-array[i]
Sub-Answer: