An Expression Tree Decoding Strategy for Mathematical Equation Generation
Authors: Wenqi Zhang
Yongliang Shen
Qingpeng Nong
Zeqi Tan
Yanna Ma
Weiming Lu
Venue: EMNLP 2023 Main (2023)
Keywords: Expression tree
Equation
Parallel Decoding
Math Word Problem

Abstract: Generating mathematical equations from natural language requires an accurate understanding of the relations among math expressions. Existing approaches can be broadly categorized into token-level and expression-level generation. The former treats equations as a mathematical language, sequentially generating math tokens. Expression-level methods generate each expression one by one. However, each expression represents a solving step, and there naturally exist parallel or dependent relations between these steps, which are ignored by current sequential methods. Therefore, we integrate tree structure into the expression-level generation and advocate an expression tree decoding strategy. To generate a tree with expression as its node, we employ a layer-wise parallel decoding strategy: we decode multiple independent expressions (leaf nodes) in parallel at each layer and repeat parallel decoding layer by layer to sequentially generate these parent node expressions  that depend on others. Besides, a bipartite matching algorithm is adopted to align multiple predictions with annotations for each layer. Experiments show our method outperforms other baselines, especially for these equations with complex structures.

An Expression Tree Decoding Strategy for Mathematical Equation Generation
Wenqi Zhang', Yongliang Shen't Qingpeng Nong", Zeqi Tan' Yanna Ma², Weiming Lu
CCollege of Computer Science and Technology, Zhejiang University
ZZongxing Telecommunication Equipment Corporationy
3 University of Shanghai for Science and Technology {zhangwenqi, luwm)@zju. edu. cn
Abstract
Question: Two cars are traveling from two places 10 km apart, the speed of the car 50kerhh speed second car 60kmmh, first drives S hours, the second car drives for hours, finally how far apart are the two cars?
Generating mathematical equations from natu- ral language requires an accurate understanding of the relations among math expressions. Ex- isting approaches can be broadly categorized into token-level and expression-level genera- tion. The former treats equations as mathe- matical language, sequentially generating math tokens. Expression-leve methods generate each expression by one. However, each expression represents solving step, and there naturally exist parallel or dependent relations between these steps, which are ignored by cur- rent sequential methods. Therefore, we inte- grate tree structure into the expression- level generation and advocate expression tree de- coding strategy. To generate a tree with ex- pression as its node, we employ a layer-wise parallel decoding strategy: we decode multiple independent expressions (leaf nodes) in paral- lel each layer and repeat parallel decoding layer by layer to sequentially generate these parent node expressions that depend on oth- Besides, bipartite matching algorithm is adopted to align multiple predictions with an- notations for each layer. Experiments show our method outperforms other baselines, especially for these equations with complex structures.
2eqq 13 Steps infix order (600)))(604))+-- 10
Seg Sxp: 4 Steps
Postfix order: 50
50 --X -+)
Stup1
Var
Step2
60 x 4 Vara
Step1 Step2
Step3
(Var3
Varl Ver2
Step4
Var3
Toleen-lvell
Exp-level
Tire:rre:: Steps
Expression Tree: Steps
Prefix orderst + x 50 60 4 10
Parallel Sequentiol
Stepl
Step2 Step9
Step3:
Var3
Step3
Step6
Step2:
Varl
Var2
Step4:0
Steep8
Stepl:
50 x 5
60 X
Step3
Step7
Tree
Figure 1: Four equation generation methods: Seq2Seq generates mathematical tokens one by one the token- level: Seq2Tree generates tokens using prefix order. In contrast, Seq2Exp generates expressions one by one at expression-leved Our expression tree decoding strategy predicts multiple math expressions in parallel and forms tree, with the minimum decoding steps.
2019) have considered mathematical symbols as special kind of language (i.e., mathematical lan- guage) and employ sequential generation for the equation. These methods belong the token-level sequential generation. Then great deal of work (Xie and Sun, 2019; Zhang et al.. 2020; Patel et al., 2021a; Li et al., 2020; Zhang et al., 2022c; Shen et al., 2022b) has proposed a tree-order decoding process (seq2tree in Figure 1) at the teken-level. This process considers it as an equation tree gener- ation and predicts pre-order tokens one by one.
1 Introduction
Generating corresponding mathematical equations and solutions from text is important for a range of tasks, such as dialogues, question answering, math word problem (MWP), etc. It necessitates an accurate comprehension of semantics and the complex relations between mathematical symbols.
Recently, some researchers have explored expression-level approaches for mathematical equa- tion generation, including (Kim et al., 2020; Cao et al., 2021; Jie al., 2022: Zhang and Moshfeghi. 2022: Zhang et al., 2022a). These approaches mostly place emphasis on generating a mathemati- cal expression step by step (seq2exp). rather than a token. These seq2exp methods belong to a sequen-
We investigate the existing approaches from two perspectives: the generation is the token-level or expression-level, and the order is based on se- quence or tree structure. Firstly, sequence-to- sequence methods (seq2seq in Figure 1) (Wang et al., 2017, 2018; Chiang and Chen, 2019; Li et al.,
*Corresponding author.

---

tial generation at expression-level.
Cao al. (2021) perform a bottom-up structure to extract multiple equations (c.g., x+y=3, y-2=4), whereas our method considers how to predict mul- tiple expressions in parallel for a complex equation at each step (e.g., output 50 x 5, 60 x simulta- neously for 50 x 5 + 60 x 4). Besides, Cao et al. (2021) enumerates all possible expression combi- nations but we first introduce bipartite matching to achieve parallel prediction. Our contributions are threefold:
However, it is imperative to recognize that each mathematical expression represents a problem- solving step, and there inherently exists a parallel or dependent relation among these steps. The ex- isting seq2exp approach may struggle to capture these relations since they only produce expressions in sequence. Therefore, there is a pressing need for versatile decoding strategy capable of simul- taneously generating independent expressions in parallel at one step, while sequentially producing expressions that depend on others step by step.
We introduce an expression tree decoding strategy by combining seq2exp with tree struc- ture. It considers the dependent or parallel relation among different expressions (solving steps). To the best of our knowledge, this is the first effort to integrate query-based object detection techniques with equation generation in the literature.
Based on this belief, we propose expression tree decoding strategy by combining the seq2exp with a tree structure the expression level. Dif- fering from the prior seq2tree, each node in this tree represents an expression, rather than a token. To construct an expression-level tree, we generate multiple expressions in parallel at each step. These expressions are independent to each other and act the leaf node in the expression tree. Those ex- pressions depend others, they act as parent nodes and are sequentially generated based their child nodes. As shown in Figure 1, the two expressions (50 5, 60 1) are completely independent and generated in parallel at Step 1. The third expression depends on the first two, forming an expression tree. It not only empowers the model to exploit the in- herent structure of the equation but also shortens its decoding path (the minimum steps in Figure 1). To achieve this, we design a layer-wise paral- lel decoding strategy. At each decoder's layer, it generate multiple independent expressions in parallel and then proceeds the next layer, and repeat parallel prediction layer by layer. This layer- wise parallel decoding process ensures that these independent expressions are produced in parallel, while these expressions depending on others are sequentially generated layer by layer, eventually constructing the entire expression tree.
We design a layer-wise parallel decoding pro- cess to construct an expression tree. It pre- dicts multiple independent expressions in par- allel and repeats parallel decoding layer by layer. Besides, employ bipartite matching align predicted expressions with labels.
To assess our method, we evaluate on MWP task and outperform prior baselines with higher accuracy and shorter steps.
By aligning the decoding process with the inher- ent structure of the equation, our approach paves the way for more intuitive, efficient equation gen- eration. Moreover, it provides insights that could be applicable to many other structured tasks.
Related work
In advancing toward general-purpose AI, depend- able reasoning remains imperative. The quest for human-equivalent reasoning has been rigorously explored in domains including NLP (Kojima et al., 2022), RL (Zhang et al., 2022b), and Robotics (Zhang et al., 2021). Recently, leveraging the plan- ning and reasoning capabilities of LLMs paves the way for the development of numerous intelligent applications (Wei et al., 2022; Shen et al., 2023; Zhang et al., 2023b). Accurate generation of math- ematical equations is important manifestation of reasoning abilities, which has been extensively investigated in plethora of NLP tasks, e.g., Math Word Problems (Wang et al., 2017: Ling et al., 2017; Xie and Sun, 2019; Wang et al., 2022a), Question Answering (Yu et al., 2018; Wu et al.,
Besides, to decode multiple expressions in par- allel, we take inspiration from query-based object detection (Carion et al., 2020; Jaegle et al., 2021; Li et al., 2023). Similar to detecting multiple visual objects by queries, we also utilize queries to iden- tify multiple mathematical relations for expression generation in parallel. Lastly, we adopt a bipartite matching algorithm for loss calculation between multiple predicted expressions and the label.
Cao et al. (2021) shares some similarities with us but the challenges and approaches are different.

---

2020b), Dialogue (Bocklisch al., 2017; Wu et al., 2022, 2023), etc. These tasks necessitate an accu- rate understanding of the semantics within the text as well as mathematical symbols.
3 Methodology
3.1
Overview
The task is to generate a complete equation based on the problem description. The generation process contains vocabularies: number and operator vo- cabulary (Vop=(+, -, ,..... }). The number is either from the original text or the math expression results from previous steps.
Token-level Generation Mathematical equation was treated as a translation task from human lan- guage into the mathematical token (symbol) (Wang et al., 2017: Chiang and Chen, 2019). Many seq2seq-baser based methods were proposed with an encoder-decoder framework. Li et al. (2019) in- troduced group attention to enhance seq2seq per- formance. Lan et al. (2021) utilized transformer model for equation generation. Except for seq2seq methods, some researchers (Liu et al.. 2019a; Xie and Sun, 2019; Zhang et al., 2020, 2022c) stud- ied the decoding structures and proposed a tree- based decoder using prefix sequence. Wu et al. (2020a, 2021); Qin et al. (2021); Yu et al. (2021) introduced mathematical knowledge to solve the complex math reasoning. Liang et al. (2021b) im- proved accuracy by knowledge distillation between the teacher and student. Li et al. (2021) proposed a prototype learning through contrasting different equations. Shen et al. (2022a); Liang et al. (2022) also used contrastive learning at the semantic and symbolic expression levels. Yang et al. (2022b) im- proved the interpretability by explicitly retrieving logical rules. These generative approaches were token-level generation in infix order or prefix order.
Similar to object detection, where queries are utilized to detect multiple objects, we also feed multiple learnable queries to identify possible math relations. As shown in Figure 2, standard decoder and multiple queries are adopted to generate didate expressions each layer. To construct expression tree, we must consider two structures simultaneously: parallel and sequential. For these expressions that have no dependent relations, we employ a parallel strategy to generate them. Con- versely, for these expressions that depend on others, we generate them layer by layer ($ 3.2). We also provide detailed cases in Figure A2 for decoding. When training, utilize bipartite matching al- gorithm to align the multiple predicted expressions with the label set for loss calculation ($ 3.3).
3.2 Layer-wise Parallel Decoding
We devise problem encoder, a decoder, and mul- tiple learnable queries, where the query is used to identify a specific mathematical relation and then produce a candidate expression at each layer.
Expression-level Generation Expression-level generation has opened up new perspective for math solving. Kim al. (2020) proposed an ex- pression pointer generation. Cao et al. (2021) in- troduced a DAG structure to extract two quantities from bottom to top. Jie et al. (2022); Wang and Lu (2023) further treated this task as an iterative rela- tion extraction to construct an expression at each step. Zhang and Moshfeghi (2022) treated expres- sion generation as program generation and exe- cution. Besides, Lee and Kim (2023); Zhang et al. (2023a); He- Yueya et al. (2023); Zhu et al. (2022) harness the capabilities of LLMs and prompt en- gineering to bolster mathematical reasoning under the shw-shot setting. These methods treat equation generation as a multi-step expression generation and achieve impressive performance. However, these methods generate only one expression per step using pre-defined order, which may potentially impede the model's acuity in accurately understand- ing mathematical logic. contrast, our method generates multiple expressions in parallel per step.
Problem Encoder Given a text description X with Nn number words, we adopt the pre-traine pre-trained language model (Devlin al., 2019; Liu et al., 2019b) to obtain the contextualized problem repre- sentations P. We obtain number vocabulary V, { from P. which denotes the embeddings of the N₂, number tokens from text. In addition, we randomly initialize the Icarnable embedding for each operator and a None label Vop ( 1- Learnable Query The decoder is designed for extracting all candidate expressions in parallel based on problem representation. Firstly, we de- sign learnable embeddings as query Q = [g:] where K means the number of the query. As shown in Figure 2, the K queries are firstly fed into the decoder and then utilized to predict K possible expressions at each layer.
No
Specifically, the decoder is the standard trans- former decoder which contains a stack of identical layers. At the 1-th layer, the problem embeddings pl-1 and the query embeddings Q' from the

---

Expression Tree Decoding
Decoder-Lane Layer 3
p2
varl + var2
Step2 Label set
Decoder-Layer
pl
50 None 4
50 +
60
5
50 + 4
Stepl Label set
Decoder- Layer
p0
Encoder
Multiple Query
Text
Label Set
Start with Leaf Node:
Stepl: Sct 50 x 5, 60 4, None, None, None, None Step2: Set (var++va22, None, None None, None, Nonc)
Label Equation: (50 (60 x 4)
Prefix Order:
+ x 50 x 60 4
50
5 60
4
Bipartite Matching For Step
Label Sct
x
60 x 4
None
None
None
None
Pred Sct
50 x
50 None 4
50 + 60
+ 4
60 x
50 +
Optimal Permutation Index: =0, 4, 1, 3,
We propose an expression tree decoding strategy by layer-wise parallel decoding. During training, we feed six queries into the decoder, where each decoder's layer generates six mathematical expressions. Then, we transform the original equation label into multiple label sets and employ a bipartite matching algorithm to align the label sets with the six predicted expressions loss calculation. Thereafter, we update problem representation using valid expressions and feed it into the next decoding layer. The whole process forms expression trec.
Figure 2:
previous layer are fed into the current decoder's layer as inputs, and then interact with each other by self-attention and cross-attention mechanism:
we predict three distributions as follows:
p!. ) Softmax (s) (s."" en), Ven E Vn
(3)
p.P Softmax(s," cop) Veop E Vap
(4)
Q' = Decoder-Layer' 1;p'-
p
(1)
where en and cop represent the number and opera- tor embedding in vocabulary respectively. (*)) P. (+), and (* denotes the three distributions for two operands and one operator. Lastly, we cal- culate the embedding for this i-th expression:
where Q' means K query embeddings 1-th layer. Parallel Decoding After obtaining K query vec- tors, we use them to predict K expressions in par- allel, each of which contains one operator and two operands (L, op, r). Firstly, we use query calcu- late the operator and operands embedding:
var; MLP" (Is" s/. 8/ 5 sf])
(5)
We totally predict K independent expressions from queries this layer. Then we continue the next layer for these expressions depending on previous results (e.g.varl + var2 Figure 2).
4/ S op MLP....p (L.p...o(qi)).. (q:), E Q!
where qi denotes the i-th query vectors in Q' Then,

---

Layer by Layer Prediction The K predicted expressions contain K1 valid expressions and K₂ invalid expressions. An invalid expression implies that the operator in (1, op. r) is predicted to None. We will discuss it in section ($ 3.3). First, we concat all valid expression embeddings with the problem representations pl-1 for the next layer:
Bipartite Match For each layer, K candidate mathematical expressions are predicted. We com- pute the function loss for the K predicted expres- sions based on the corresponding label set, which also contains K golden expressions. However, as the K expressions are unordered, it is difficult to calculate the loss directly. For instance, if the la- bel set is (50 x 5, 60 x 4}, and the prediction is {60 4, 50 x 5), the loss in this case should be O. To address this, we adopt a bipartite matching algo- rithm to align the two sets, i.e., align the K predic- tions with the K golden labels. As shown in Figure 2, six golden expressions align with six predicted expressions. Specifically, we denote the golden expression in the label set as [yI, D2: D2. J.). and the set of predicted expressions by ÿ = (ús) i=1- To find optimal matching, mutation (3 E Ok) of K elements with the lowest cost. As shown in Figure 2, the optimal permu- tation for predicted set is [No: D4, 21, 92, Ds, 0s). It can be formalized as:
P'=MLP" ([Pl vari war2..... Duark,)
(6)
where var ear2, ..., yark, means K1 new gen- erated expression embeddings in 1-th layer. + means the concatenation of the vectors. Besides, we also update the number embedding: Vi Vl 1 U vari warg.... U wark, using K new ex- pression embeddings as new number embeddings. As shown in Figure 2, we proceed to the next layer of decoding using p' and Q', as Equation 1:
search for per-
ql+1_
(7)
At layer 1 +- 1,, we still decode expressions in par- allel and continue to the next layer. If all predicted expressions are invalid, i.e., K operators are classi- fied as N None, it significs the equation generation is complete.
K Σ
8 = -arg min 9E0x
Smatch (Vis (3(1))
(8)
where Lmttch (Vi, (o(1)) is a pair matching cost be- tween the golden expression yi and the predicted expression ÿ with index (().. We use the Hun- garian algorithm (Kuhn, 1955) to compute this pair-matching cost. Each golden expression con- tains two operands and one operator, i.e. Yi (4,, op,, r:) and each predicted expression has three distributions, i.e. is = (*), PT (+).. We calculate Lmatch as follow:
3.3 Loss For Parallel Decoding
As mentioned before, each decoder's layer gener- ates multiple mathematical expressions. However, the annotations of equations in the dataset usu- ally serial (e.g., "50", "x"", "5", "+", "60", "x", "4"), and it crucial to design a method to utilize these annotations for training parallel decoding.
To this end, we first convert the original equation annotations into multiple label sets, each set com- prising K mathematical expressions. Then, bipar- tite matching is employed to align the K predicted expressions with the K mathematical expressions in the label set compute model loss.
Lmatch (yi, (p())) 11 (opr op
(P5(0) (op:)
PlR (4) + PB(( (r:)
(9)
After we get the optimal matching 3t, we calcu- late the final loss L(y, 9) as:
Label Set As shown in Figure 2, we initially convert the label equations from infix order to pre- fix order, thus forming an equation tree. Starting from the leaf nodes, we iterative gather two leaves and their parent node into a label set for each step, eventually producing multiple label sets (e.g. set = {50 x 5, 60 x 4}, set2 {varl> var2)). Each label set contains several non-dependent expres- sions that can be generated in parallel. Each label set is also padded with a specific label None to ensure all sets contain K elements. We provide two detailed cases for this process in Figure A2.
C(y.0) Σ t=1
log (1) (op:)
[ log logr's.co (4)
(10)
+ [onc)
- -logr (1) (ra))}
We calculate the predicted loss for each decoder layer after aligning two sets. A detailed match process is provided in Figure A3.

---

Model
Test Acc.
Model
Test
5-fold
GroupAttn(Li et al., 2019)
70.4
GroupAttn(2019)
69.5
66.9
GTS (Xic and Sun, 2019)
71.3
GTS (2019)
75.6
74.3
Seq2Seq l'rree
G2an al., 2020)
72.0
G2T(2020)
77.4
75.5
BERT-TTLLing al., 2021a)
73.8
mBEKTT2021)
75.1
mBERTTTan al., 2021)
77.1
(ymbol-Dec(2021)
75.7
Seq2Seq /'rre
T-DistLLiang al., 2021b)
73.1
BERTGen((021)
76.6
Prototype (Li al., 2021)
76.3
PLM-Gen (2021)
76.9
Textual-CLL?(Shen et al., 2022a)
78
H-Reusoner(2021)
83.9
82.2
Ana-CL (Liang al., 2022)
79.6
BERTTT((021a))
84.4
82.3
Rankf(2021)
85.4
E-pointeri et al., 2020)
73.5
Logic-Dee(2022h)
83.4
Scq2Exp
M- M-Tree al., 2022a)
76.5
T-Dis(2021b)
79.1
77.2
RE-Ext(Jie et ul., 2022)
78.6
Protolype (2021)
83.2
M- View et al., 2022a)
79.5
85.0
82.6f
Elastic * Zhang and Moshfeghi, 2022)
2022)
80.3
Ana-CL (2022)
85.6
83.2f
MWP-NASi(Bin et al., 2023)
79.2
E-Poinlerf(2020)
78.7
76.5
LLM
gp--3.5-turroo-(ppennAA 2022)
42.6
DAG (2021)
77.5
75.1
Self- Self-Consistenyy((Wngg et al., 2022b)
50.7
LLM Seq2Exp
M- M-Tre(22022a)
82.5
80.81
Ours
81.5 2.13
RE-Ext(2022)
85.4
83.3
Ours (Layer-Shared)
81.1 -023
(2View)((1122a)
85.6
83.1
(202))))(2022)
84.8
82.9
MWP-NAS(2023)
84.4
Table 1:
Results on MathQA. & means our reproduc- tion. O means we reproduce M- View using the stan- dard dataset without data Augmentation (their report). means Elastic use different data pre-processing method and operators, so we reproduce their method.
gpt-3.5-turboo(2222)
54.8
Sell-Consistenoy1120222
66.1
Ours
86.2 1:030
84.1 10:65
Ours (Layer-Shared)
85.6
83.4
Table 2: Testing and five-fold Acc. on Math23k.
3.4 Training and Inference
During training, we calculate the loss after employ- ing the bipartite match for each layer. Besides, also adopt the teacher forcing (Williams and Zipser, 1989) by using golden expressions for the next layer (Equation 5, 6). During inference, each layer predicts expressions parallel. Those expressions whose predicted operator None are filtered out before proceeding to the next layer gen- eration. The entire process is finished when all K expressions predicted to be None.
MathQA (Amini et al., 2019), Math23K (Wang et al., 2017), and MAWPS (Koncel- Kedziir-kdiio et al., 2016). We follow (Jie et al., 2022; Zhang al., 2022a) to preprocess datasets. The statistics of datasets are reported Appendix A.3.
Baselines We compare our method with three types of baselines: (1) Seq2Seq/Tree PLM-Gen (Lan et al., 3021), Rank (Shen et al., 2021), Symbol- Dec (Qin et al., 2021), H-Reasoner (Yu al., 2021), Logic-Dec (Yang et al., 2022b), Prototype (Li al., 2021), T-Dis (Liang al., 2021b), Textual-CL. (Shen et al., 2022a), Ana-CL (Liang et al., 2022) and several representative methods. (2) Seq2Exp: E-Pointer (Kim et al., 2020). DAG (Cao et al.. 2021), RE-Ext (Jic et al., 2022), M-View (Zhang et al., 2022a), ELASTIC(Zhang and Moshfeghi. 2022), M-Tree (Wang al., 2022a) and MWP- NAS (Bin et al., 2023). Besides, also com- pare with gpt-3.5-turbo (OpenAI, 2022) and Self- Consistency (Wang et al., 2022b) prompted by one demonstration through the OpenAl API. More de- tails are listed in Appendix A.1.
4 Experiments
Math Word Problem Task We first evaluate our expression tree decoding strategy on the Math Word Problem task (MWP). MWP represents challenging mathematical reasoning task where the model is required to comprehend the semantics of given problem and generate a complete equa- tion and the solution. Encompassing spectrum of topics, including engineering, arithmetic, geome- try, and commerce, MWP effectively evaluates the model's prowess in semantic understanding as well mathematical symbol generation. We use three standard MWP datasets across two languages:
Training Details Following most previous works (Zhang et al., 2022a; Jie et al., 2022), we port the average accuracy (five random seeds) with
'The criteria for the selection of the dataset: I. Dataset size. 2. Datasize label includes not just answers but also complete
equations. Extensively employed in prior research.

---

Model
5-fold Acc.
Math23K
Seq2Exp
Our
Seq2Seq
Seq2Tree
GroupAttn(2019)
76.1
Avg Step
2.4
1.92
7.01
5.62
GTS (2019)
82.6
Std Step
1.22
0.8
3.4
2.1
G2T(2020)
85.6
Max Step
9
8
27
19
Seq2Seq ''ree
Rank(2021)
BERTGen(2021)
84,0
86,9
MathQA
Seq
Our
Seq2Seq
Seq2Tree
PLM-Gen (2021)
88.4
Avg Step
4.33
3.2
16.74
9.87
PLM-GTS (2021a)
88.5
Std Step
2.26
1.6
11.03
5.51
PLM-G2T (2021a)
88.7
Max Step
11
8
109
55
H-Reaaoner(((211)
89.8
T-Dis(202Ib)
84.2
Table 4: The statistics for decoding steps between four types of methods.
Prototypef (2021)
89.6
Textual-CLf (2022a)
91.3
Am2CC)((0022)
91.8
E-Pointer (2020) M- 2ree(22
83,4
Seq2Exp
82.0
Variant
Acc.
RE-Ext(2022)
92.2
Bipartite Matching
81.5
M- M- (2022a)
92.1
Sequence Matching
78.8 1: 0.27
Elastic & (2022)
91.8
MWP-NAS(Bin et al., 2023)
88
Random Matching
20.1 +: 1,55
Operand None Loss
80.7 1: 0.36
gpt-3.5--urbo((2022)
91.5
w/o Operator None Loss
79.6 1: 0.21
Self Self-Coonsiteneyy1122222)
92.5
w/o Parallel decoding
79.9 1 0.31
Ours
92.3 0.41
Ours (Laycr-Shared)
92.2 + 0.28
Table 5: Ablation on MathQA about bipartite matching.
Table 3: Five-fold cross-validation results MAWPS.
(+0.8% on MathQA), with fewer parameters.
standard deviation for Math23K and MathQA, and 5-fold cross-valle validation for Math23K and MAWPS. The test-set accuracy is chosen by the best dev-set accuracy step. Since most of the math problems only require two or three mathematical expressions to be generated in parallel for each step, set the number of queries K to be 6, which is suffi- cient cover all cases. Except for using a standard decoder for layer-wise decoding (Our), we also explore an alternate variant (Our Layer-Shared), in which parallel decoding performed at every N transformer layer, but each decoding step shares the parameter of these N layers. This model is efficient with fewer parameters. Model details are reported in Figure Al.
From the view of three types of methods, our method is more stable and effective, with +1.9% and +1.2% gains against the best Seq2Tree base- line (Ana-CL) and best Seq2Exp baseline (Elas- tic) on MathQA. The Seq2Exp focuses on genera- tion at the sequence at the expression-level, while Seq2Tree absorbs the feature of a tree structure. In contrast, our expression tree decoding strategy, more than generating the expressions, also inte- grates the tree structure into the parallel decoding process, performing well for complex equations.
In addition to the accuracy comparison, we also analyze the difference in the number of decoding steps. We report the average decoding steps, step standard deviation, and maximum steps for the four types of methods (Seq2Seq: mBERT, Seq2Tree: Ana-CL, Seq2Exp: RE-Ext, and Expression tree: Ours) Table 4. We observe that the decoding steps of the token-level generation methods (e.g., Seq2Seq and Seq2Tree) are significantly higher than those of Expression-level methods (about four to five times). Compared to other methods, our parallel decoding method requires fewer decoding steps, especially on the more complex MathQA. We offer some intuitive examples in Figure A2. These results suggest that our parallel strategy not only offers superior accuracy but also reduces the number of decoding steps.
4.1 Results
As shown in Table 1, 2 and 3, our expression tree decoding strategy achieves SoTA performance on two large datasets, especially on the most difficult MathQA with +1.2% gains. Similarly, we gain +0.6% (test) and +0.8% (5-fold) improvements on Math23K and comparable performance on the MAWPS. Moreover, also notice that our perfor- mance still substantially outperforms LLMs in the case of complex mathematical equation generation (MathQA: +30.8% and Math23K: +20. 1%). Fur- thermore, our variant model (Our w/ Layer-Shared has also demonstrated comparable performance

---

Equation Type
Diagram
Example
Model
Single
Exp Chain
Exp Tree
Overall
Single
Esp
b
M- M-View
79.7
82.7
65.7
79.5
Expression Chain
Exp
Exp
Dip
(a bjxe-d
RE-Ext
77.4
82.5
64.7
78.6
Expression Tree
2
Esp
(a b)x (c -d) f
M-Tree
Ana-CL
79.9
75.2
80.2
82.8
64.5
67.8
79.6
76.5
Pep
Ours
80.1
82.0
75.2
81.5
4.2 Ablations
Table 6: categorize the structures of equations into
three types: Single, Chain and Tree, and evaluate the performance of five methods on three structures.
Bipartite matching is essential for our parallel strat- egy. Therefore, we study how works: I. Se- quence Matching. Firstly, we ablate bipartite matching and instead use simple matching strat- egy for multiple expressions: sequence matching. It means we align the first expression predicted by the first query with the first label, and then the sec- ond predicted expression aligns with the second label, and so on. II. Random Matching. Then random match the predicted expressions with the labels. III. Operand None Loss. As illustrated in Equation 10, for these labels padded with the None category, we only compute the loss for the operator. At this point, we add two operands' loss between None to analyze its effect. IV. Opera- tor None Loss. We remove the operator loss for the None category. V. Parallel Decoding. Lastly, we remove the whole parallel decoding, i.e., adopt only one query per layer. We provide a detailed visualization for these designs in Figure A3.
M--M222KK KudoA
--MMaEIKK Mutlo M.View
MartTKK BERT-T M--OOA MAURT
Prediction in
AEspression
4Expression MatiQQ
Figure Performance on the sample with the different number of expressions.
Equation Structure In Table 6, we categorize the structures of equations into three types: (1) Single expression, where the entire equation sists of only one expression; (2) Expression chain, where the equation is comprised of multiple ex- pressions forming a chain; (3) Expression Tree, which involves complex tree structures composed of multiple expressions. We evaluate the model's 's accuracy on three types of equation structures.
As shown in Table 5, when we replace with se- quence matching, there is notable degradation in accuracy (-2.7%). In this case, the performance is similar to the Seq2Exp (RE-Ext::8.69) 78.8%). undermines the advantages of expres- sion tree decoding since aligning process still intro- duces manually-amottal order. Secondly, we find random matching may lead to a training collapse. Then we observe disregarding None operator loss adding the None operands loss, both having negative impact (-0.9%. -0.8%). In the last ablation experiments, our performance drops from 81.5% 79.9% (-1.6%) when we remove the parallel de- coding from our system. More comparisons can be found in Appendix A.4.
Ablation:
As shown in Table 6, our expression tree de- coding strategy gains comparable performance other baselines the first two evaluations (Sin- gle Expression and Expression Chain). In contrast, in the Expression Tree evaluation, most of these instances in this type involve sophisticated equa- tion structures and complex solving processes. Our method significantly outperforms the other base- lines (2 +7.4%). Specifically, in comparison the seq2tree approach, we achieve +7.4% im- provement (Our:75.2% vs Ana-CL-67.88% and gain a more substantial advantage (+9.5% rela- tive to the seq2exp method. Under this case, our method outperforms seq2tree, and seq2tree turn outperforms seq2exp. This clearly demonstrates that introducing the structural feature of equations indeed contributes to the capable of handling equa- tions with complex structures.
4.3 Analysis
We investigate the efficacy of the expression tree decoding strategy in scenarios involving complex equation generation. We conduct the analysis along dimensions: the structure of the equation and the length of the equation. Besides, we also analyze the impact different query numbers on parallel decoding performance.
Equation Length An equation comprises mul- tiple mathematical expressions, with each expres-

---

sion representing reasoning step. Complex equa- tions usually contain more expressions. There- fore, we evaluate the performance on the instance Fig-
ples illustrate that our method is highly flexible and can adaptively predict expressions in parallel se- quentially based on the context, thereby composing an expression tree.
with different numbers of expressions. ure 3, as the number of expressions increases, the equation becomes more complex and the perfor- mance decreases rapidly. However, our method consistently maintains high accuracy (270% on MathQA) across all cases, especially complex cases. Compared with baselines, our advantage increases from +1.0% (#2) to +6.4% (#5). For the equation with the longest expressions (2#8), our strategy maintains an improvement by nearly +6%, showing expression tree decoding strategy is more stable for complex equations.
Conclusion
We devise an expression tree decoding strategy for generating mathematical equations layer by layer. Each layer produces multiple mathematical expressions in parallel which are non-dependent and order-free, achieving flexible decoding. During the training, we employ a bipartite matching algo- rithm to align the multiple generated expressions with the golden labels and compute the parallel prediction loss under the optimal matching scheme. Extensive experiments demonstrate that our expres- sion tree decoding strategy can effectively absorb the structural features of equations and enhance the capacity for generating complex equations for math reasoning.
Query Number We further analyze the impact the number of queries on parallel decoding per- formance. The number of queries is set from I to 30. As shown in Table A2, as the number of queries increases, the performance initially increases no- tably and then decreases. Specifically, when there is only one query per layer (# query 1), the par- allel decoding strategy is removed. Conversely, when we adopt too many queries (# query >= 10), the performance of parallel decoding drops rapidly. We speculate that this might be because most of the queries are redundant and are matched to the "None" label under this case. Too many queries may lead to instability in training. Apart from too many too few queries, the performance gains at- tributed to parallel decoding remain both stable and pronounced. For instance, as the number of queries fluctuates between 4 and 8, the improvement con- sistently remains within the range of +1.2% to +1.5%. It suggests that although the number of queries is hyperparameter, it does not need to be carefully tuned.
Limitations
Firstly, when faced with a mathematical problem that requires an extensive number of solving steps. we have to increase the number of decoder layers. It consequently leads to an increase in the model parameters. This is due to our layer-wise decoding strategy, where more complex equations require ad- ditional decoding layers. To address this, we have designed variant model with shared parameters (Layer-Sharee Figure A1), which achieves com- parable results without modifying layer number.
Secondly, some hyperparameters (e.g., the num- ber of queries and layer), need to be manually ad- justed according to the dataset. In the future, we will explore how to utilize our query-based, layer- wise expression tree decoding strategy to address a broader range of structured generation tasks.
4.4
Case Study and Visualization
We explore the role of learnable queries in the ex- pression tree decoding process. We first calculate the similarity between query vectors and problem representations for each layer and then visualize the results in Figure A4. As shown in the first case, the sixth query is activated twice through two steps, thus performing two division operations. In the second case. the first and second queries generate two valid expressions (14 + 6, + 6) in parallel in the first layer, and then the last query in the second layer outputs a division operation (Exp1* + Exp2) using two results from the first layer. These exam-
Acknowledgments
This work is supported by the Fundamental Re- search Funds for the Central Universities (No. 226- 2023-00060), Key Research and Development Pro- gram of Zhejiang Province (No. 2021C01013), National Key Research and Development Project of China (No. 201 2018AAA0101900), Joint Project DH-2022ZY0013 from Donghai Lab, and MOE Engineering Research Center of Digital Library.

---

References
Shifeng Huang, Jiawei Wang. Jiao Xu, Da Cao, and Ming Yang. 2021. Recall and learn: A memory- augmented solver for math word problems. arXiv preprint arXiv:2109 13/12.
Aida Amini, Saadia Gabriel, Shanchuan Lin, Rik Joncel-Kedziorske Yejin Choi, and Hannaneh Ha- jishirzi. 2019. MathQA: Towards interpretable math word problem solving with operation- baasdd for- malisms. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Tech- nologies, Volume 1 (Long and Short Papers), pages 2357-2367, Minneapolis, Minnesota. Association for Computational Linguistics.
Andrew Jaegle, Felix Gimeno, Andy Brock. Oriol Vinyals, Andrew Zisserman, and Joao Carreira. 2021. Perceiver: General perception with iterative atten- tion. In International conference on machine learn- ing, pages 4651-4664, PMLR.
Zhanming Jie, Jierui Li, and Wei Lu. 2022. Learning to reason deductively: Math word problem solving as complex relation extraction. In Proceedings of the 60th Annual Meeting of the Association for Compu- tational Linguistics (Volume 1: Long Papers), pages 5944-5955. Dublin, Ireland. Association for Compu- Lational Linguistics.
Yi Bin, Mengqun Han, Wenhao Shi, Lei Wang, Yang Yang, and Heng Tao Shen. 2023. Non-autoregressivve math word problem solver with unified tree structure. CoRR, abs/2305.0455
Tom Bocklisch, Joey Faulkner, Nick Pawlowski, and Alan Nichol. 2017. Rasa: Open source language understanding and dialogue management. arXiv preprint arXiv: 1712.0518.
Bugeun Kim, Kyung Seo Ki, Donggeon Lee, and Gah- gene Gweon. 2020. Point to the Expression: Soly- ing Algebraic Word Problems using the Expression- Pointer Transformer Model. Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages Online. Association for Computational Linguistics.
Yixuan Cao. Feng Hong, Hongwei Li, and Ping Luo. 2021. A bottom-up dag structure extraction model for math word problems. In Thirty-Fifth AAAI Con- ference on Artificial 2021, pages 39-46.
Nicolas Carion, Francisco Massa, Gabriel Synnaeve, Nicolas Usunier, Alexander Kirillov, and Sergey Zagoruyko. 2020. End-to-end object detection with transformers. Computer Vision-ECCV 2020: 16th European Conference, Glasgow, UK, August 23- 28, 2020, Proceedings, Part I 16, pages 213-229. Springer.
Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yu- taka Matsuo, and Yusuke Iwasawa. 2022. Large lan- guage models are zero-shot reasoners. arXiv preprint arXiv:2205.11911
Rik Koncel-Kedziorski Subhro Roy, Aida Amini, Nate Kushman, and Hannaneh Hajishirzi. 2016. Mawps: A math word problem repository. In Proceedings of the 2016 Conference of the North American Chap- ter of the Association for Computational Linguistics: Human Language Technologies, pages 1152-1157.
Ting-Rui Rui Chiang and Yun-Nung Chen. 2019. Semantically-aligned equation generation for solving and reasoning math word problems. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computa- fional Linguislics: Humun Language Technologies, Volume (Long and Short Papers), pages 2656- 2668, Minneapolis, Minnesota. Association for Computational Linguistics.
Harold W Kuhn. 1955. The hungarian method for the assignment problem. Naval research logistics quar- terly, 2(1-2):83-99
Yihuai Lan, Lei Wang. Qiyuan Zhang. Yunshi Lan. Bing Tian Dai, Yan Wang. Dongxiang Zhang, and Ec-Peng Lim. 2021. Mwptoolkit: An open-source framework for deep learning brased math word prob- lem solvers, arXiv preprint arXiv: 109, 109.0999..
Karl Cobbe, Vineet Kosaraju. Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reicchrr Nakano, et al. 2021. Training verifiers to solve math word problems. arXiv preprint arXiv:2110. 14168.
Yunshi Lan, Lei Wang, Jing Jiang, and Re-Peng Lim. 2022. Improving compositional generaliza- tion in math word problem solving. arXiv preprint arXiv:2209.01352
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. 2019. BERT: Pre-training of deep bidirectional transformers for language under- standing. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Tech- nologies, Volume I (Long and Short Papers), pages 4171-4186, Minneapolis, Minnesota. Association for Computational Linguistics.
Soochan Lee and Gunhee Kim. 2023. Recursion of thought: Divide and conquer reasoning with language models.
Jierui Li, Lei Wang, Jipeng Zhang, Yan Wang, Bing Tian Dai, and Dongxiang Zhang. 2019. Modeling intra- relation in math word problems with different func- tional multi-head attentions. In Proceedings of the 57th Annual Meeting of the Association for Computa- tional Linguisties, pages 6162 66-6767, Florence, Italy. Association for Computational Linguistics.
Joy He- Yueya, Gabriel Poesia, Rose E Wang, and Noah D Goodman. 2023. Solving math word prob- lems by combining language models with symbolic solvers. arXiv preprini 2xXiv:2304.001 09102.

---

Junnan Li. Dongxu Li. Silvio Savarese, and Steven Hoi. 2023. 2lip-2: Bootstrapping aanguae-immge pre- training with frozen image encoders and large lan- guage models. arXiv preprint ar arXiv:2301.12599
Arkil Patel, Satwik Bhattamishra, and Navin Goyal. 2021a. Are nlp models really able to solve simple math word problems? arXiv preprint arXiv:2103.07191
Shucheng Li, Lingfei Wu, Shiwei Feng. Fangli Xu, Fengyuan Xu, and Sheng Zhong. 2020. Graph-to- tree neural networks for learning structured input- output translation with applications to semantic pars- ing and math word problem. In Findings of the Asso- ciation for Computational Linguistics: EMNLP 2020, pages 2841 28122 Online. Association for Computa- tional Linguisties.
Arkil Patel, Satwik Bhattamishra, and Navin Goyal. 2021b. Are NLP models really able to solve simple math word problems? In Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, pages 2080-2094, Online. Association for Computational Linguistics.
Jinghui Qin, Xiaodan Liang, Yining Hong. Jianheng Tang, and Liang Lin. 2021. Neural-symbolic solver for math word problems with auxiliary tasks. In Proceedings of the 59th Annual Meeting of the Asso- ciation for Computational Linguistics and the 1 11th International Joint Conference on Natural Language Processing ( (Volume I: Long Papers), pages 5870- 5881, Online. Association for Computational Lin- guistics.
Zhongli Li, Wenxuan Zhang, Chao Yan, Qingyu Zhou, Chao Li, Hongzhi Liu, and Yunbo Cao. 2021. Seek- ing patterns, not just memorizing procedures: Con- trastive learning for solving math word problems. arXiv preprint arXiv:2110.0844
Zhenwen Liang, Jipeng Zhang, Jie Shao, and Xian- gliang Zhang. 2021a. Mwp-bert: A strong base- line for math word problems. arXiv preprint arXiv:2107.13435.
Jianhao Shen, Yichun Yin, Lin Li, Lifeng Shang, Xin Jiang, Ming Zhang, and Qun Liu. 2021. Generate & rank: multi-task framework for math word prob- lems. In Findings of the Association for Computa- tional Linguistics: EMNLP 2021, pages 2269-2279, Punta Cana, Dominican Republic. Association for Computational Linguistics.
Zhenwen Liang. Jipeng Zhang, and Xiangliang Zhang, 2022. Analogical math word problems solving with association. In Proceed- ings of the 2022 Conference on Empirical Methods in Natural Language Processing, pages 9454-9464, Abu Dhabi, United Arab Emirates. Association for Computational Linguistics.
enhanced
Yibin Shen, Qianying Liu, Zhuoyuan Mao, Fei Cheng, and Sadao Kurohashi. 2022a. Textual enhanced con- trastive learning for solving math word problems. arXiv preprint arxiv: 2211.16022
Zhenwen Liang et al. 202 Solving Math Word Prob- lems with Teacher Supervision. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21, pages 3522-3528. Interna- tional Joint Conferences on Artificial Intelligence Organization.
Yibin Shen, Qianying Liu, Zhuoyuan Mao, Zhen Wan, Fei Cheng, and Sadao Kurohashi. 2022b. Seeking diverse reasoning logic: Controlled equation expres- sion generation for solving math word problems. arXiv preprint arXiv:2209. 10310.
Wang Ling, Dani Yogatama, Chris Dyer, and Phil Blun- som. 2017. Program induction by rationale genera- tion: Learning to solve and explain algebraic word problems. In Proceedings of the 55th Annual Meet- ing of the Association for Computational Linguistics (Volume 1: Long Papers), pages 158-167, Vancouver, Canada, Association for Computational Linguisties.
Yongliang Shen, Kaitao Song, Xu Tan. Dongsheng Li, Weiming La, and Yueting Zhuang. 2023. Hugging- gpt: Solving ai tasks with chatgpt and its friends in huggingface. arXiv preprint 2303:22003.75800
Minghuan Tan, Lei Wang, Lingxiao Jiang, and Jing Jiang. 2021. Investigating math word problems using pretrained multilingual language models.
Qianying Liu, Wenyv Guan, Sujian Li, and Daisuke Kawahara. 2019a. Tree-structured decoding for soly- ing math word problems. In Proceedings of the 2019 Conference on Empirical Methods in Natu- ral Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP), pages 2370-2379, Hong Kong. China. Association for Computational Linguisties.
Shih-hung Tsai, Chao-Chun Liang, Hsin-Min Wang. and Keh- Yih Su. 2021. Sequence to general tree: Knowledge-guide geometry word problem solving. arXiv preprint 1rXiv:2106.00990
Bin Wang, Jiangzhou Ju, Yang Fan, Xin-W Yu Dai, Shujian Huang, and Jiajun Chen. 2022a. Structure-unified m-tree coding solver for mathword problem. arXiv preprint arXiv:2210. 12432..
Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Man- dar Joshi, Danqi Chen, Omer Levy, Mike Lewis,
Luke Zettlemoyer, and Veselin Stoyanov. 2019b. Roberta: A robustly optimized bert pretraining ap- proach. arXiv preprint 1rxiv:1907.11699
Lei Wang, Yan Wang, Deng Cai, Dongxiang Zhang, and Xiaojiang Liu. 2018. Translating a math word problem to an expression tree. arXiv preprint arXiv:1811.0566:
OpenAI. 2022. Chatgpt.

---

Tianduo Wang and Wei Lu. 2023. Learning multi-step reasoning by solving arithmetic tasks. In Proceed- ings of ACI.
In Proceedings of the 2022 Conference on Empiri- cal Methods in Natural Language Processing, pages 4787-4799.
Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc Le, Edd Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. 2022h. Sell-consistency improves chain of thought reasoning in language models. arXiv preprint arXiv: /1171.
Yiquan Wu, Weiming Lu, Yating Zhang. Adam Jatowt, Jun Feng. Changlong Sun, Fei Wu, and Kun Kuang. 2023. Focus-aware response generation in inquiry conversation. In Findings of the Association for Computational Linguistics: ACI. 2023, pages 12585- 12599.
Yan Wang, Xiaojiang Liu, and Shuming Shi. 2017. Deep neural solver for math word problems. In Pro- ceedings of the 2017 Conference Empirical Meth- ods in Natural Language Processing, pages 845-854.
Zhipeng Xie and Shichao Sun. 2019. A goal-driven tree-structured neural model for math word problems. In IJCAL, pages 5299-5305.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fd Chi, Quoe Le, and Denny Zhou. 2022. Chain of thought prompting elicits reasoning in large language models. arXiv preprint 2rXiv:2001.1100.
Jing Xiong, Zhongwei Wan, Xiping Hu, Min Yang. and Chengming Li. 2022. Self--onssstent reason- ing for solving math word problems. arXiv preprint arXiv:2210.15373.
Ronald J Williams and David Zipser. 1989. A learn- ing algorithm for continually running fully recurrent neural networks. Neural computation, 1(2):270-280.
Zhicheng Yang. Jinghui Qin, Jiaqi Chen, and Xiaodan Liang. 2022a. Unbiased math word problems bench- mark for mitigating solving bias. arXiv preprint M.Xiv2205.087000
Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pier- ric Cistac, Tim Rault, Remi Louf, Morgan Funtow- icz, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma. Yacine Jernite. Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, Mariama Drame, Quentin Lhoest, and Alexander Rush. 2020. Trans- formers: State-of of the-art natural language processing. In Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations, pages 38-45, Online, Association for Computational Linguistics.
Zhicheng Yang, Jinghui Qin, Jiaqi Chen, Liang Lin, and Xiaodan Liang. 2022b. Logicsolver: Towards interpretable math word problem solving with log- ical coompt-ennanced learning. arXiv preprint arXiv:2205.0822
Adams Wei Yu, David Dohan, Minh-Thang Thang Luong, Rui Zhao, Kai Chen, Mohammad Norouzi, and Quoc V Le. 2018. Qanet: Combining local convolution with global self-attention for reading comprehension. arXiv preprint 1rXiv:1804.09: 1804.09541.
Qinzhuo Wu, Qi Zhang, Jinlan Fu, and Xuan-Jing Huang. 2020a. A knowledge-award sequence-to- tree network for math word problem solving. In Proceed- ings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 7137-7146.
Weijiang Yu, Yingpeng Wen, Fudan Zheng, and Nong Xiao. 2021. Improving math word problems with pre-trained knowledge and hierarchical reasoning. In Proceedings of the 2021 Conference on Empiri- cal Methods in Natural Language Processing, pages 3394,,394, Online and Punta Cana, Dominican Re- public. Association for Computational Linguisties.
Qinzhuo Wu, Qi Zhang, Zhongyu Wei, and Xuanjing Huang. 2021. Math word problem solving with ex- plicit numerical values. In Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the I Itth International Joint Confer- ence on Natural Language Processing (Volume 1: Long Papers), pages 5859-5869, Online, Association for Computational Linguistics.
Jiaxin Zhang and Yasha Moshfeghi. 2022. Elastic: nu- merical reasoning with adaptive symbolic compiler. arXiv preprint arXiv: 10. 10105.
Jipeng Zhang. Lei Wang, Roy Ka-Wei Lee, Yi Bin, Yan Wang, Jie Shao, and Fe-Peng Lim. 2020. Graph-to- tree learning for solving math word problems. Asso- ciation for Computational Linguistics.
Yiquan Wu, Kun Kuang, Yating Zhang, Xiaozhong Liu, Changlong Sun, Jun Xiao, Yueting Zhuang, Luo Si, and Fei Wu. 2020b. De-biased court's view genera- tion with causality. In Proceedings of the 2020 Con- ference on Empirical Methods in Natural Language Processing (EMNLP), pages 763-780
Mengxue Zhang, Zichao Wang, Zhichao Yang. Weiqi Feng, and Andrew Lan. 2023a. Interpretable math word problem solution generation via step-by-step planning. arXiv preprint arXiv:2306.00784,
Yiquan WU, Yifei Liu, Weiming Lu, Yating Zhang, Jun Feng, Changlong Sun, Fei Wu, and Kun Kuang. 2022. Towards interactivity and interpretability: A rationale-based legal judgment prediction framework.
Wenqi Zhang, Yongliang Shen, Weiming Lu, and Yuet- ing Zhuang. 2023b. Data-copilot: Bridging bil- lions of data and humans with autonomous workflow. arXiv preprint arXiv:2306.07209.

---

Wenqi Zhang, Yongliang Shen, Yamna Ma, Xiaoxia Cheng, Zeqi Tan, Qingpeng Nong, and Weiming Lu. 2022a. Multi-view reasoning: Consistent contrastive learning for math word problem. In Findings of the Association for Computational Linguisties: EMNLP 2022, pages 103-1111,, Abu Dhabi, United Arab Emirates. Association for Computational Linguistics.
Wenqi Zhang, Kai Zhao, Peng Li, Xiao Zhu, Yongliang Shen, Yanna Ma, Yingfeng Chen, and Weiming Lu. 2022b. A closed-loop perception, decision-makee maaiing and reasoning mechanism for human-like naviga- tion. In Proceedings of the Thirty-Firsi International Joint Conference on Artificial Intelligence, IJCAI-22, pages 4717-4724. International Joint Conferences on Artificial Intelligence Organization. Main Track.
Wenqi Zhang, Kai Zhao, Peng Li, Xiaochun Zhu, Fap- ing Ye, Wei Jiang, Huiqiao Fu, and Tao Wang. 2021. Learning to navigate a vuca environment: Hierar- chical multi-expert approach. 2021 IEEE/RSJ Inter- national Conference on Intelligent Robots and Sys- tems (IROS), pages 9254-9261.
Zhang. Guangyou Zhou, Zhiwen Xie, and Jimmy Xi- angji Huang. 2022c. Hgen: Learning hierarchical het- erogeneous graph encoding for math word problem solving. IEEE/ACM Transactions on Audio, Speech, and Language Processing, 30:8 1-828.
Zihao Zhou, Maizhen Ning, Qiufeng Wang, Jie Yao, Wei Wang, Xiaowei Huang, and Kaizhu Huang. 2023. Learning by analogy: Diverse questions generation in math word problem. arXiv preprint arXiv:2306.09064.
Xinyu Zhu, Junjie Wang, Lin Zhang, Yuxiang Zhang, Ruyi Gan, Jiaxing Zhang, and Yujiu Yang. 2022. Solving math word problem via cooperative rea- soning induced language models. arXiv preprint arXiv:22 16257.

---

A Appendix
Two Variant Models
A.1 Baselines
Transformer Layer
In recent years, the MWP task has garnered widespread attention (Zhou et al., 2023; Xiong al., 2022; Lan et al., 2022; Yang et al., 2022a; Cobbe et al., 2021; Tsai et al., 2021; Huang
Transformer Layer
Transforner Layer
Transformer Layer
Transformer Layer
et al., 2021). We divide the prior baselines into two categories: Seq2Seq/Tree and Seq2Exp. In Seq2Seq/Tree, Li et al. (2019) (GroupAttn) ap- plied multi-head attention approach using seq2seq model. Xie and Sun (2019) proposed seq2tree generation (GTS). Zhang al. (2020) (G2T) introduced graph encoder. Patel et al. (2021b); Liang al. (2021a) added PLMs encoder GTS and G2T (PLM-GTS, BERT- T). Tan et al. (2021) proposed a multilingual model (mBERT). Lan et al. (2021) utilized Trans- former for generation (BERTGen). Shen et al. (2021) proposed multi-task method (Rank). Qin et al. (2021) introduced neural symbolic method (Symbol-Dec). Yu al. (2021) extracted hierarchi- cal features for encoder (HI-Reasoner). Yang et al. (2022b) designed logical rules to guide decoding (Logic-Dec). Li et al. (2021) proposed a prototype learning (Prototype). Liang et al. (2021b) adopted a teacher model for discrimination (T-Dis). Shen et al. (2022a) distinguished examples with similar semantics but different logics (Textual-CL). Liang et al. (2022) adopted analogy identification to improve the generalization (Ana-CL).
Exp. Expa
Exp,
Parameter Sharal
Transformer Layer
Transformer Layer N
Exp, Exps
Transformer Layer
Transformer Layer
Exp, Exp: Exps
Transformer Layer
Trameformer Layer
Mulriple Query
Multiple Query
Figure Al: Except for using a standard decoder for layer-wise decoding (Left), also explore alternate model (Right), in which parallel decoding is performed every N transformer layer, but each decoding step shares the parameter of these N layers. The left model more accurate, and the right has fewer parameters.
(Wolf et al., 2020) for multilingual datasets. We consider five mathematical operators, containing Addition, Subtraction, Multiplication, Division, Ex- ponentiation, and various constants ([ 1, .,.,.))) as previously. Our query decoder is a transformer decoder with multiple layers, each having 768 hid- den units. In our experiments, we perform parallel decoding once at each transformer layer. We use an Adam W optimizer with a 5e-5 learning rate, batch size of 32 for MathQA and 26 for Math23K. We set the maximum layer number 8. The other parameters
In Seq2Exp, Cao et al. (2021) used a bottom-up DAG construction method (DAG). Jie et al. (2022) introduced a relation extraction method (RE-Ext). Wang et al. (2022a) treated MWP as tagging an- notation by M-Tree coding (M-Tree). Bin et al. (2023) introduced a unified tree structure using non-autoregrressvve model (MWP-NAS). Zhang al. (2022a) aligned the representation of dif- ferent traversal order for consistency (M-View). ELASTIC (Zhang and Moshfeghi, 2022) designs a computer synthesis process to handle numerical reasoning. We also compare our results with the gpt-3.5-turbo in the few-shot setting. We design a prompt consisting of both directive instructions and demonstration to guide gpt-3.5 step-by-step reasoning.
previous works (Zhang al., 2022a; Jie al., 2022). All experiments were set up on an NVIDIA RTX A6000.
A.3
MWP Dataset Statistics
The statistics of the dataset are shown in Table A1.
#Avg. Token
#Avg. Exp
#Max. Exp
Dataset
#Train/WValdd/FTTe
MathQA
16191 226
39.6
4.17
12
Math23K
21162/1000/100
26.6
2.26
20
A.2 Training Details
MAWPS
1589/199/199
30.3
1.42
7
Following most previous works (Zhang et al., 2022a; Jie et al., 2022), we adopt Roberta-bart and Chinese-BERR as encoder from HuggingFace
Table A1: Statistics for three standard datasets.

---

Querr
6
15
30
Acc.(MathQA)
79.9
80.6
81.4
81.4
81.5
81.3
81.1
80.8
80.2
79.8
79.1
Compared to #1
0
+0.7
+1.5
+1.5
+1.6
+1.4
+1,2
+0.9
+0.3
-0.1
-0.8
Acc.(Math23K) %
85.2
85.8
86.2
86.0
86.2
85.9
85.6
85.2
84.8
83.5
83.3
Compared to #1
0
+0.6
+1
+0.8
+1
+0.7
+0.4
0
-0.4
-1.7
-1.9
Table A2: The impact of query number on our parallel decoding performance.
Method
MathQA
Math23K
w/ parallel decoding
81.5
86.2
w/o parallel decoding
79.9
85.2
E-pointer
73.5
78.7
M-View
79.5
85.6
RE-Ext
78.6
85.4
Elastic
80.3
84.8
Table A3: The ablation study on parallel decoding.
A.4 Ablating on Parallel Decoding
Parallel decoding is the key to constructing expres- sion trees. We provide a more detailed comparison of our parallel decoding strategy. The detailed re- sults shown in Table A3. When ablate parallel decoding from our framework, i.e., adopt only one query per layer, our performance drops from 81.5% to 79.9% (-1.6%) on MathQA. A sim- ilar trend is seen on Math23K (-1.0%). Besides, without the parallel decoding strategy, our perfor- mance is similar to the Seq2Exp baselines (c.g.. E-pointer, M-View, RE-Ext, Elastic, etc.), which generate one expression each step. Compared to them, parallel decoding brings noticeable and con- sistent improvements (E-pointer: +8%, M- MiView: +2%, Ex-Ext: +2.9%, Elastic: +1.2%).

---

Label Set
Expression Tree Decoding
Label Equation: (50 5) + 60 X(4 +
Prefix Order:
x 50 5 x 60 4
50
Layer
varl
Result
k2xch
varl
var3
60 var2
Layer
Stept: Set ( varl 50 x 5, var2
4+
Set 50 x 5, 4 7, None, None .....
Step2: Set ( vur3 60 x var2)
Set x var2, None, Nome .....)
Layer
Step3: (varl var3)
Padding
Set varl var3, None, None .....)
Label Equation: (10 + 4) 5 60 21 10 (10+7)
Prefix Order: + x 1045 x 60 10 = 10
Expression Tree Decoding
10
var3
Layer
60
10
varl
60
var
10
10
Layer 3
Result
aar
var?
var6
L1X5
60 x0
fo- Vi
var4
var5
Layer 2
Stepl:
Set varl var2 10 + var3 10 7, None....)
Step2: Set var4 - var5 60 var2, var6 + var3, None,...) ....)
10++
10+7
Step3: Set (var7 vard var5, None,
Layer
Step4; Sel (var7 var6, Nome, ....)
Figure A2: Two cases for Label Set and Expression Tree decoding processes.

---

Bipartite Matching Process
YO
Y1
Y2
Y3
Y4
Y5
Label Set
50 x
60
None
None
None
None
Predict Set
50 None
50 + 60
5
50 +
90
P1
92
93
94
85
Permutation
0
4
1
2
Index
Y0: 50 x 5
Y1: 60 x 4
Y2: None
t
Loss for operand
Loss for operator
Loss
Po: 50 5
94: x
91: 50 None
Loss Lossl + Loss2 + Lossó
Several Ablation Design
Bipartite Matching
Label Sct
50 x 5
60 x
None
None
None
None
Losse
Lossi
Loss2
Loss5
Lossó
Predict Sct
x0 5
50 None
+
+
4
50 4
Sequence Matching
Label Set
50 5
60 x
None
None
None
None
$
Loss
Loss2
Loss3
Loss4
Loss5
Lossó
+
Predict Set
50 5
50 None
50 + 60
5 +
60 4
Without Operator None Loss
Label Set
50 x
60 x 4
None
None
None
None
Loss 11
Loss2
Predict Set
50 None
50 +
4
50 +
With Operand None Loss
Label Set
50 x 5
60 x
None
None
None
None
ttt
Predict Set
50 x 5
50 None 4
50 +
5 +
60 x 4
50 + 4
Figure A3: Up: The process of the Bipartite Matching. Down: Several ablation designs.

---

if truck is traveling at constant rate of 180 kilometers per hour how many hours will it take the truck travel distance of 600 meters kilometer = 1000 meters)
Problem:
Label: 600 / 1000 / 180 Our Prediction: 600 1000 / 180
Layer 1: Expl= 600 + 1000 by # query 6
180 kilometers
truck
traveling
at
constant of
rate
per
how hour
seconds
will
take
truck
to travel
distance
600
meters
kilomet
1000
meters
R125
Queryy ld
Layer 2: Expl+
108 by # query 6
k kloomeee
traveling
constant
seconds
distance
meters
kilomet
meters
if
truck
at
180
per
hour
how
many
will
take
the
truck
to
of
G00
1000
</>>
Query
maxwell leaves his home and walks toward brad 's house one hour later, brad leaves his home and runs toward maxwell ss house if the distance between their homes is 14 kilometers, maxwell s walking speed is km/ h, and brad s running speed is 6 km h. what is the total time takes maxwell before he meets up with brad ? Label: (14+6) (4+6)
Problem:
Our Parallel Prediction:
(14+6 (4++)
Layer 1: Expl = 14 + 6 by # query
Exp2 = + by # query
oloometers
boward
House
sommes
Rallingg
Layer 2: Expl= + Exp2 by # query
Kllometters ters
110 Cavils
catre and
coward
house
covvss
and howard
house
Ghall zomes
Balkingg
maa
Figure A4: We visualize the expression tree decoding process at each layer. We calculate the cosine similarity between query vectors and problem representations for each layer. In the first case, the prediction expressions are output by query. In the second case, the first and second queries are activated for two expressions in parallel.


Reviews:
[{"review_id": "RIOVOCirKE", "reviewer": "Reviewer_GxCv", "summary": "", "questions": "A) The conclusion that 'Expression Tree Decoding' empowers the model to exploit the inherent structure of the equation does not seem to be well proven. Further ablation experiments (e.g. using only 1 query per layer) would be helpful. \n\nB) The section 'Learnable Query' may need clarification, it is not clear to me how these queries (which seem to be embedding vectors?) are learned and used to predict expressions of the given form (l, op, r) .\n\nC) According to Section A.2, your transformer has 8 layers, limiting the number of expressions. Are there examples in the datasets that are too complex for the model and how do you handle them? \n\nD) In the training /evaluation code, you define numerical constants (conf.use_constant in structured_decoding_main_math23k.py) based on the dataset used. I would expect this to affect the evaluation, but it is not mentioned in the paper. In which way do you use these constants and how do the results differ when no constants are used?  \n\nE) In Table 3, why do you report accuracy of your models in bold instead of Self-Consistency(2022b), which actually achieves the best result?", "limitations": "", "rating": 3, "confidence": 2, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "#### Reviewer GxCv\n\nThanks for your valuable comments. Below are our responses to your concerns:\n\n> ***Reject 1: The paper employs known strategies to a new problem which might limit the novelty.***\n\nThank you for taking the time and effort to review our work. We appreciate the opportunity to address the concerns regarding the novelty of our paper:\n\n+ **Innovation in Application:**  While the paper might employ known strategies, it creatively applies them to a novel domain, i.e., Equation Generation or Mathematical Word Problems (MWP). Specifically:\n    + We are the first to investigate existing methods from two orthogonal perspectives: token-level or expression-level generation, and sequential order or tree order (Figure 1). From two perspectives, we clearly observe the evolution between the different approaches and identify the weaknesses of the SoTA approach (Expression-Chain generation).\n    + We innovatively incorporate the tree structure of equations into a layer-wise decoding process, generalizing Expression-Chain to a more versatile Expression-Tree generation. \n    + The use of a multi-query parallel strategy and a bipartite matching algorithm in the context of equation generation is a pioneering method (mentioned by Reviewer Apu7). This method not only improves upon previous baselines (+1.2\\%, +0.8\\% in Table 1, 2) but also demonstrates superior performance in complex equation scenarios (+7.4\\% in Table 5, 6).\n\n+ **Potential for Broader Impact:** Our paper is more than just simply applying existing strategies to a new problem. Many structured prediction tasks (e.g., Parsing tasks) share similar challenges with equation generation, such as bottom-up or top-down prediction and the problem of optimal sub-structure search. Our approach, especially the multi-query parallel decoding and bipartite matching mechanisms we introduced, may provide insights for these structured prediction tasks. Similarly, as Reviewer 1r8v also mentioned, considering each equation generation method (Seq2Tree, Seq2Exp, Ours) from a Parsing task perspective can bring greater value. We hope our research can bring some inspiration to the community across different domains.\n\n> ***Question A: Ablation experiments about parallel decoding***\n\nThank you for your helpful suggestion. The crux of Expression-Tree strategy lies in parallel decoding utilizing multiple queries. So we analyze its practical effects from three distinct perspectives: \n\n+ **Ablating the whole parallel decoding**: Parallel decoding is the key to constructing expression trees. When we ablate parallel decoding from our framework, i.e., adopt only one query per layer, our performance drops from 81.5\\% to 79.9\\% (-1.6\\%) on MathQA. A similar trend is seen on Math23K (-1.0\\%). Besides, without the parallel decoding strategy, our performance is similar to the Seq2Exp baselines (e.g., E-pointer, M-View, RE-Ext, Elastic, etc.), which generate one expression at each step. Compared to them, parallel decoding brings noticeable and consistent improvements (E-pointer: +8\\%, M-View: +2\\%, RE-Ext: +2.9\\%, Elastic: +1.2\\%). The detailed results are as follows: \n| Method                | MathQA | Math23K |\n|-----------------------|--------|---------|\n| w/ parallel decoding  |  81.5  |   86.2  |\n| w/o parallel decoding |  79.9  |   85.2  |\n| E-pointer             |  73.5  |   78.7  |\n| M-View                |  79.5  |   85.6  |\n| RE-Ext                |  78.6  |   85.4  |\n| Elastic               |  80.3  |   84.8  |\n\n+ **Evaluating on complex structural equations**: We also analyzed the performance of our Expression-Tree decoding in comparison with Expression-Chain decoding (Seq2Exp baselines) in the context of complex equation scenarios. Table 5 showcases these results. In the first two simpler structures, Expression-Tree decoding did not lead to discernible differences. However, in the most complex third category of equations, our method (75.2\\%) significantly outperformed M-View (65.7\\%) and RE-Ext (64.7\\%).\n\n+ **Analyzing the impact of different query numbers**. We further analyze the impact of the number of queries on parallel decoding performance. The number of queries is set from 1 to 30. The results show as the number of queries increases, the performance initially increases notably and then decreases. Specifically, when there is only one query per layer (#query = 1), the parallel decoding strategy is removed. Conversely, when we adopt too many queries (#query >= 15), the performance of parallel decoding drops rapidly. We speculate that this might be because most of the queries are redundant and are matched to the \"None\" label under this case. Too many queries may lead to instability in training. Apart from these extreme cases (either too many or too few queries), the performance gains attributed to parallel decoding remain both stable and pronounced. For instance, as the number of queries fluctuates between 4 and 8, the improvement consistently remains within the range of +1.2\\% to +1.5\\%.\n|   # query         | 1   |   2   | 4   | 5   | 6   | 7   | 8   | 10  | 15  | 20  | 30  |\n|:----------------:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|\n| Acc.(MathQA) %    | 79.9| 80.6| 81.4| 81.4| **81.5**| 81.3| 81.1| 80.8| 80.2| 79.8| 79.1|\n| Comp to #1       | 0   | +0.7| +1.5| +1.5| **+1.6**| +1.4| +1.2| +0.9| +0.3| -0.1| -0.8|\n||||||||||||\n| Acc.( Math23K)   | 85.2| 85.8| **86.2**| 86.0| **86.2**| 85.9| 85.6| 85.2| 84.8| 83.5| 83.3|\n| Comp to #1       |  0  | +0.6| **+1**  | +0.8| **+1**| +0.7| +0.4|  0  | -0.4| -1.7| -1.9|\n\nThese results demonstrate that our parallel decoding can exploit the structure of equations to construct expression trees, proving to be more suitable for equation generation than Expression-Chain.\n\n\n> ***Question B: What is the learnable query? How do it learn? How to predict expression?***\n\nSorry for the confusion. We will make a clearer clarification regarding your concerns：\n\n+ **What is the learnable query:** Learnable queries are essentially embedding vectors. Instead of denoting tokens or words with specific meanings, these queries serve as trainable feature detectors and learn to detect mathematical patterns or relations by attention mechanism in the transformer. After training, these feature detectors can extract specific mathematical relations from the question text. For instance, we observe that the #6 query typically matches division relations (Figure A4). \n+ **How to predict:** The process of predicting the Left number, Right number, and Operator is carried out by feeding the learnable queries into three distinct classification heads. Each classification head is essentially a combination of an MLP (Multi-layer Perceptron) layer followed by a Softmax function. These heads output probabilities for each candidate value (l, op, r), and the one with the highest probability is chosen as the prediction (Equation 2-4).\n+ **How do it learn:**  Analogous to how word embeddings in a vocabulary are trained, our learnable queries learn to detect and symbolize mathematical patterns or relations. To give an analogy, consider these queries as \" band-pass filters\", which are gradually specialized into \"narrow-band filters\" to detect specific mathematical patterns as the training progresses. The whole training process can also be seen as a denoising and restoration process. We start with **a noise token** (the randomly initialized query) and through training, optimize it to **a mathematical token** that represents specific mathematical expressions or relations.\n\n\n> ***Question C: How to handle those complex samples only with 8 transformer layers***\n\n+ **Our parallel decoding mechanism can cover the vast majority of samples**. As each decoding layer can simultaneously output K expressions, our 8-layer model is capable of producing sufficiently complex expressions. According to our statistics, more than 94\\% of the samples can be processed by our 8-layer model. \n\n+ **To keep consistent with previous baselines**. Although increasing the decoding layers would allow our model to handle more samples, we also set the number of transformer layers to 8 to ensure a fair comparison with previous baselines (most Seq2Exp baselines set a maximum of 8-11 decoding steps).\n\n+ **Our Variant model for equations of any length**. We acknowledge that certain extremely complex equations might exceed the processing capabilities of our standard model. To address this, we designed a variant model as shown in Figure A1 (Right). Here, a shared transformer block is used at each step. By repetitively feeding the queries and the problem representation into this block for K parallel expressions, our model has the potential to handle equations of any length. This layer-shared mechanism not only resolves the issue of equation length but has also achieved promising results in our experiments (Table 1, 2, 3).\n\n\n> ***Question D: Why do you need constants? How are they used? Will they affect performance?***\n\nThank you for pointing out the use of numerical constants in our training and evaluation code. We'd like to clarify the rationale behind it and demonstrate its implications for assessment.\n\n+ **Why do we need a constant vocabulary:** MWP is to translate human language into mathematical language (i.e. a finite set of symbols). Therefore, it is more efficient to design a specialized output vocabulary, rather than using the original vocabulary of a pre-trained model. Like most previous MWP approaches (GTS, G2T, RE-Ext, M-view, etc.), we set up the same constant vocabularies (Line 984-988). For instance, on Math23K, we defined two constant numbers: {1, $\\pi$} as previous baselines. It is necessary to involve multiple mathematical operators and constant numbers in output vocabulary. The constant number is usually a common-sense number that doesn't appear in the question. For example, for a problem \"What is the area of a circle with radius 3?\". It cannot be solved without the constant \" $\\pi$\" in the output vocabulary. \n+ **How to use these constant numbers:** Each constant in the vocabulary is trained from scratch, i.e., First these constant embeddings are initialized randomly and are stored in the numerical vocabulary ($V_n$ in line 234), then are utilized for expression prediction (Equation 3) and subsequently updated during the training likes other parameters. Besides, we also experimented with initializing these constant vocabularies using the pre-trained embeddings from PLMs, but without any positive effect. \n\n+ **Impact of these constants on evaluation:**  The use of constants enhances the model's capability to solve a wider array of problems. Without these constants, the model may struggle with specific problems, like those requiring the value of $\\pi$. We remove the constant words and the corresponding samples and re-train the model, then test it on the entire test set. The accuracy of all methods dropped significantly:\n\n|               | Ours | Best Seq2tree (Ana-CL) | Best Seq2Exp (M-View) |\n|---------------|------|------------------------|-----------------------|\n| **w/ Constant**   | 86.2 | 85.6                   | 85.6                  |\n| **w/o Constant**  | 64.6 | 64.2                   | 61.9                  |\n| **Equation Case** |   (1/4 + 1) * 120 + 120   | Constant Number: 1  |  |\n\nQuestion Case: Given that a certain primary school has 120 male students and the number of female students is more than that of male students by (1/4), how many students are there in total in the school?   \n\n\n\n> ***Question E: Compared with Self-Consistency in Table 3***\n\nThank you for your thoughtful feedback. We will correct this mistake. Self-Consistency + GPT3.5 performs slightly better than our method on the MAWPS dataset (+0.2\\%), but on the other two large datasets, Self-Consistency performs considerably worse than ours (-30.8\\%, -20.1\\%).\n\t\n> ***Improvements: some mistakes and the paper has more than 8 pages***\n\nThank you for pointing out these grammatical mistakes. We will address these issues and add more diverse examples to demonstrate parallel decoding. \n\nAdditionally, according to the official guidelines of EMNLP, the main manuscript is limited to 8 pages, followed by Limitations, References, and Appendix, which are of unlimited length. Our main text is less than 8 pages.\n\n\n--------------------------------------------------------------------------------------------------------------------------------------------------------------\nThanks again for your valuable reviews above. If you have any further questions, please do not hesitate to let me know. I am more than happy to discuss with you (if the system allows).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "- The idea to adapt query-based detection combined with bipartite matching and layer-wise decoding to math word problems seems novel and appropriate.\n- The paper is well written and easy to follow.", "reasons_to_reject": "- The paper mainly employs known strategies to a new problem which might limit the novelty.", "questions_to_authors": "A) The conclusion that 'Expression Tree Decoding' empowers the model to exploit the inherent structure of the equation does not seem to be well proven. Further ablation experiments (e.g. using only 1 query per layer) would be helpful. \n\nB) The section 'Learnable Query' may need clarification, it is not clear to me how these queries (which seem to be embedding vectors?) are learned and used to predict expressions of the given form (l, op, r) .\n\nC) According to Section A.2, your transformer has 8 layers, limiting the number of expressions. Are there examples in the datasets that are too complex for the model and how do you handle them? \n\nD) In the training /evaluation code, you define numerical constants (conf.use_constant in structured_decoding_main_math23k.py) based on the dataset used. I would expect this to affect the evaluation, but it is not mentioned in the paper. In which way do you use these constants and how do the results differ when no constants are used?  \n\nE) In Table 3, why do you report accuracy of your models in bold instead of Self-Consistency(2022b), which actually achieves the best result?", "paper_topic_and_main_contributions": "The paper is about generating mathematical equations from natural language problem descriptions. The authors propose 'Expression Tree Decoding' as a novel approach that integrates tree structure into existing expression-level (seq2exp) approaches. To this end, they adapt ideas from query-based object detection, especially from [Carion et al., 2020] for math word problems. By using a bipartite matching loss for set prediction, the model is able to predict multiple independent expressions in parallel while dependent expressions are decoded sequentially. Here, a transformer model is used, where each layer performs one decoding step. This approach constructs an expression tree that aligns with the inherent structure of mathematical equations. The authors show their approach to outperform prior baselines on 3 common MWP tasks.", "excitement": 3, "reproducibility": 4, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {"Typos_Grammar_Style_and_Presentation_Improvements": "- l.294:  If all predicted expressions are invalid, i.e., K operators are classified as None, which signifies the equation generation is complete.\n- l. 355: we caculate ...\n- The example problems provided throughout the paper are very similar (all distance/time/speed related), it would be interesting to see more diverse examples\n- The paper has more than 8 pages"}}, {"review_id": "6npgC7o8il", "reviewer": "Reviewer_Apu7", "summary": "", "questions": "My first two questions are listed in the Reasons to Reject.\nC. The ablation study only ablates the bipartite matching method, is it possible to ablate other parts of the mode like parallel decoding?\n", "limitations": "", "rating": 4, "confidence": 4, "soundness": 3, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "#### Reviewer Apu7\n\nThanks for your valuable comments. Below are our responses to your concerns:\n\n> ***Question A: Introducing Seq2DAG and DETR is too brief***\n\nThank you for highlighting the importance of [1] and [2] in our work. In our revised paper, we will discuss both papers in detail.\n\nSeq2DAG [1] and DETR [2] are two profoundly significant works, which inspired us in many aspects. \nTo be specific, Seq2DAG's framework provided us with insights on the parallel extraction of multiple equations, and DETR's query-based detection mechanism served as a foundation for our method to predict sub-expression nodes for complex equations.\n\nIn the revised version, we will discuss more about [1-2] and delve into their methodologies, their main contributions, and how our work draws from these two pioneering studies.\n\n\n> ***Question B: Seq2DAG is also a parallel decoding method***\n\nSorry for the ambiguity in our statement. We will revise this statement and discuss their work further. Seq2DAG is the first to perform a bottom-up structure extraction, greatly inspiring the MWP community. There are some comparisons between Seq2DAG and our method:\n\n+ **Different Focus on Parallel Decoding:** Both methods involve parallel decoding, but they have different concerns. \nSeq2DAG extracts multiple equations in parallel, i.e., an annotated equation set (e.g., x+y=3, y-2=4), whereas our method considers how to predict multiple sub-expressions in parallel for a complex equation at each step. We need to craft a label set for the parallel expressions at each layer ourselves (Section 3.3). For instance in Figure A2, the equation (10 + 4) × 5 + 60 × (10 + 2) − 10 ÷ (10 + 7) is converted into four label sets: layer1= {10+4, 10+2, 10+7}, layer2={v1×5, 60×v2, 10÷v3}, layer3={v4+v5}, layer4={v6+v7}. This process is not mentioned in Seq2DAG.\n\n\n+ **Different Methodology:** Seq2DAG is an extraction framework, that enumerates all possible (l, op, r) combinations at each step, and then performs binary classification for each combination. This process is similar to iterative relation extraction [3]. In contrast, our query-based decoding method is a generative framework, that directly generates multiple possible expressions in parallel rather than enumerating all combinations. Then we align predicted expressions with the label set via bipartite matching loss, which is also different from Seq2DAG. \n\n[1] Yixuan Cao, Feng Hong, Hongwei Li, and Ping Luo. 2021. A bottom-up dag structure extraction model for math word problems. In AAAI. \n\n[2] Nicolas Carion, Francisco Massa, Gabriel Synnaeve, Nicolas Usunier, Alexander Kirillov, and Sergey Zagoruyko. 2020. End-to-end object detection with transformers. In ECCV.\n\n[3] Cao, Yixuan and Chen, Dian and Li, Hongwei and Luo, Ping. 2019. Nested relation extraction with iterative neural network. CIKM\n\n\n\n> ***Question C: The ablation study on parallel decoding***\n\nThank you for your helpful suggestion. We analyze the parallel decoding strategy from two distinct perspectives: \n\n+ **Ablating the whole parallel decoding**: Parallel decoding is the key to constructing expression trees. When we ablate parallel decoding from our framework, i.e., adopt only one query per layer, our performance drops from 81.5\\% to 79.9\\% (-1.6\\%) on MathQA. A similar trend is seen on Math23K (-1.0\\%). Besides, without the parallel decoding strategy, our performance is similar to the Seq2Exp baselines (e.g., E-pointer, M-View, RE-Ext, Elastic, etc.), which generate one expression at each step. Compared to them, parallel decoding brings noticeable and consistent improvements (E-pointer: +8\\%, M-View: +2\\%, RE-Ext: +2.9\\%, Elastic: +1.2\\%). The detailed results are as follows: \n| Method                | MathQA | Math23K |\n|-----------------------|--------|---------|\n| w/ parallel decoding  |  81.5  |   86.2  |\n| w/o parallel decoding |  79.9  |   85.2  |\n| E-pointer             |  73.5  |   78.7  |\n| M-View                |  79.5  |   85.6  |\n| RE-Ext                |  78.6  |   85.4  |\n| Elastic               |  80.3  |   84.8  |\n\n\n+ **Changing the number of parallel queries**: We further analyze the impact of the number of queries on parallel decoding performance. The number of queries is set from 1 to 30. The results show as the number of queries increases, the performance initially increases notably and then decreases. Specifically, when there is only one query per layer (#query = 1), the parallel decoding strategy is removed. Conversely, when we adopt too many queries (#query >= 15), the performance of parallel decoding drops rapidly. We speculate that this might be because most of the queries are redundant and are matched to the \"None\" label under this case. Too many queries may lead to instability in training. Apart from these extreme cases (either too many or too few queries), the performance gains attributed to parallel decoding remain both **stable** and **pronounced**. For instance, as the number of queries fluctuates between 4 and 8, the improvement consistently remains within the range of +1.2\\% to +1.5\\%.\n|   # query         | 1   |   2   | 4   | 5   | 6   | 7   | 8   | 10  | 15  | 20  | 30  |\n|:----------------:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|\n| Acc.(MathQA) %    | 79.9| 80.6| 81.4| 81.4| **81.5**| 81.3| 81.1| 80.8| 80.2| 79.8| 79.1|\n| Comp to #1       | 0   | +0.7| +1.5| +1.5| **+1.6**| +1.4| +1.2| +0.9| +0.3| -0.1| -0.8|\n||||||||||||\n| Acc.( Math23K)   | 85.2| 85.8| **86.2**| 86.0| **86.2**| 85.9| 85.6| 85.2| 84.8| 83.5| 83.3|\n| Comp to #1       |  0  | +0.6| **+1**  | +0.8| **+1**| +0.7| +0.4|  0  | -0.4| -1.7| -1.9|\n\n\n\n> ***Presentation Improvements***\n\nThanks for pointing out these issues. we will revise them.\n\n----------------\nThanks again for your valuable reviews above. If you have any further questions, please do not hesitate to let me know. I am more than happy to discuss with you (if the system allows).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "1. From my understanding, this paper combines the method from [1] and [2], where [1] constructs the tree in a bottom-up layer-wise fashion and [2] proposes a method to extract multiple objects in each layer in parallel. This combination is interesting since [2] is a paper on object detection tasks in CV.\n2. The experiment results are promising.\n\n[1] Yixuan Cao, Feng Hong, Hongwei Li, and Ping Luo. 2021. A bottom-up dag structure extraction model for math word problems. In AAAI.\n[2] Nicolas Carion, Francisco Massa, Gabriel Synnaeve, Nicolas Usunier, Alexander Kirillov, and Sergey Zagoruyko. 2020. End-to-end object detection with transformers. In ECCV.", "reasons_to_reject": "A. While from my understanding, [1] and [2] are the most important references for this paper, the authors have introduced them very briefly. \nB. The authors claim that ``To the best of our knowledge, this is the first effort to parallel decode expressions and form an expression tree for MWP.'' But [1] is a parallel decoding method, which has a similar decoding process to this paper.\n", "questions_to_authors": "My first two questions are listed in the Reasons to Reject.\nC. The ablation study only ablates the bipartite matching method, is it possible to ablate other parts of the mode like parallel decoding?\n", "paper_topic_and_main_contributions": "This paper proposes a method for math word problems. The proposed method partitions nodes in an expression tree by their layer (from left to root), and iteratively combines sub-expressions and variables to construct larger sub-expression. At each step, it generates all sub-expressions in the same layer in parallel, using a method similar to DETR (a multi-object detection framework).", "excitement": 4, "reproducibility": 4, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"Missing_References": "None"}, "extra_text": {"Typos_Grammar_Style_and_Presentation_Improvements": "     a. In line 256, \"K query embeddings\" should be \"K query hidden vectors\" to distinguish the embedding matrix and computed results.\n     b. In line 272, \"We totally predict K independent expressions from K query at this layer.\" "}}, {"review_id": "rC2ieFn9Bx", "reviewer": "Reviewer_1r8v", "summary": "", "questions": "An analysis of the number of steps required to generate the expressions would be interesting too.\nIn the examples given, your method takes slightly less steps than the postfix method. Providing an analysis of the expected number of steps for an expression between the different methods would be a nice add-on", "limitations": "", "rating": 3, "confidence": 3, "soundness": 4, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "#### The response to Reviewer 1r8v\n\nThanks for your valuable comments. Below are our responses to your concerns:\n\n> ***Reject1: The number of queries is a hyperparameter***.\n\nThank you for pointing out this limitation. We also discussed it in the Limitation Section. We found that, although the number of queries needs to be predefined, it doesn't require meticulous design:\n\n\n\n+ **Performance is stable with different number of queries**. We analyze the impact of the query number. We set the number of queries (K) from 1 to 30. We noticed that the performance is stable and satisfactory (+1.5\\%, +1.5\\%, +1.6\\%, +1.4\\%, +1.2\\%) when K is set between 4 and 8. This suggests that although the number of queries is a hyperparameter, it does not need to be carefully tuned. A moderate K can lead to a decent promotion.\n\n\n+ **The number of queries is easy to estimate**. \nContrary to being ad-hoc, the number of queries $K$ is quite intuitive to estimate. Our experimental results clearly demonstrate that extreme values (either too many or too few queries) are suboptimal. In real-world scenarios, most mathematical equations comprise only a handful of expressions that need parallel output. As a result, setting $K$ to a small integer (like within the range of 4 to 8) is not only empirical but also logical.\n\nThe detailed results for different query numbers:\n\n|   # query         | 1   |   2   | 4   | 5   | 6   | 7   | 8   | 10  | 15  | 20  | 30  |\n|:----------------:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|\n| Acc.(MathQA) %    | 79.9| 80.6| 81.4| 81.4| **81.5**| 81.3| 81.1| 80.8| 80.2| 79.8| 79.1|\n| Comp to #1       | 0   | +0.7| +1.5| +1.5| **+1.6**| +1.4| +1.2| +0.9| +0.3| -0.1| -0.8|\n\n\n|      # query        |  1  |  2  |  4  |  5  |  6  |  7  |  8  | 10  | 15  | 20  | 30  |\n|:----------------:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|\n| Acc.( Math23K)   | 85.2| 85.8| **86.2**| 86.0| **86.2**| 85.9| 85.6| 85.2| 84.8| 83.5| 83.3|\n| Comp to #1       |  0  | +0.6| **+1**  | +0.8| **+1**| +0.7| +0.4|  0  | -0.4| -1.7| -1.9|\n\n\n\n> ***Reject2: Establishing the association between different equation generation methods and parsing***\n\nThank you for your insightful suggestion.\n\nIt is quite intriguing to consider different equation generation methods from the perspective of parsing tasks. The Seq2Tree equation generation can be viewed as a shift-reduce strategy. Our approach also shares some similarities with the classic CKY algorithm. Firstly, both methods construct tree structures in a bottom-up manner, layer by layer. Secondly, while CKY employs dynamic programming to seek the optimal substructure, we use a bipartite matching (Hungarian algorithm) to find an optimal matching relation. We will add discussions about these parsing algorithms in our revised version.\n\n\n> ***Question: Analyse the number of decoding steps between different methods***\n\n\nWe calculate the average decoding steps, step standard deviation, and maximum decoding steps for the four types of methods (Seq2Seq: mBERT, Seq2Tree: Ana-CL, Seq2Exp: RE-Ext, and Expression-tree: Ours). We observed the following phenomena:\n\n+ Seq2Seq and Seq2Tree are token-level generation methods, so their decoding steps are significantly higher than those of Expression-level methods (about four to five times). \n\n\n+ Compared to Seq2Exp, our parallel decoding method requires fewer decoding steps (Math23K: -0.48, MathQA: -1.13) and Std, especially on the more complex MathQA. We offer some intuitive examples in Figure A2. These results suggest that our parallel decoding strategy not only offers superior accuracy but also reduces the number of decoding steps. \n\n\n|    Math23K      | Seq2Exp | Our | Seq2Seq | Seq2Tree |\n|----------|---------|-----|---------|----------|\n| Avg Step | 2.4     | **1.92**| 7.01    | 5.62     |\n| Std Step | 1.22    | **0.8** | 3.4     | 2.1      |\n| Max Step | 9       | **8**   | 27      | 19       |\n\n|  MathQA        | Seq2Exp | Our  | Seq2Seq | Seq2Tree |\n|----------|---------|------|---------|----------|\n| Avg Step | 4.33    | **3.2**  | 16.74   | 9.87     |\n| Std Step | 2.26    | **1.6** | 11.03   | 5.51     |\n| Max Step | 11      | **8**   | 109     | 55       |\n\n\n-----\nThanks again for your valuable reviews above. If you have any further questions, please do not hesitate to let me know. I am more than happy to discuss with you (if the system allows).", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "- The authors provide an original method for generating arithmetic expressions from problems stated in natural language\n- The results are good and the analysis highlights where the systems improves over the sota", "reasons_to_reject": "- The method is dependent on a ad-hoc constant: \nthere's is an hyper parameter constant K throughout the paper (the number of queries issued at each step) that is ad-hoc.\n- The paper would benefit from establishing a better relation to classical methods in parsing or generation.\nThe different tree construction scenarios investigated in the paper share striking similarities with parsing methods : top down, shift reduce, CKY... Relating the proposal with well known methods would add some substantial value to the paper. ", "questions_to_authors": "An analysis of the number of steps required to generate the expressions would be interesting too.\nIn the examples given, your method takes slightly less steps than the postfix method. Providing an analysis of the expected number of steps for an expression between the different methods would be a nice add-on", "paper_topic_and_main_contributions": "The authors describe a mathematical expression generator from natural language.\nThe context is to translate a mathematical problem expressed in natural language to an arithmetic expression\n\nIn the current research context, the solution builds upon transformers\nin a seq2expression framework: that is given an encoding of the natural language, generate the expression.\nHere the authors focus on generating the expression tree rather than generating directly the expression tokens sequentially.\n\nIn this case, several solutions are possible : prefix, infix, postfix encoding of the expression tree.\nThe authors observe that these orderings involve a large number of steps.\n\nThey introduce a new method that attempts to minimize the number of steps for generating the expression structure. The method builds the expression tree iteratively in bottom up order.\nAt each step the system issues K queries to the problem representation, each query generates a math expression\neach of these valid expressions are then added to the problem embedding and feed the next step.\nThe process stops when no valid expression is generated at some step\n\nThe authors also describe a method for constructing a loss in this setup relying on an alignment between the reference solution and the current state of the learner relying on bipartite matching method\n\nThe authors then provide experimental results on the Math Word Problem task (MWP) for 3 datasets where they get sota results. An analysis is provided where the relevance of the bipartite matching component is first highlighted.\nThen the experiments show that their method is well suited for long equations and equations with non trivial tree structure\n\n\n\n\n\n\n\n", "excitement": 3, "reproducibility": 4, "ethical_concerns": "No", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {}, "extra_text": {"Missing_References": "- The paper would benefit from establishing a better relation to classical methods in parsing or generation.\nThe different tree construction scenarios investigated in the paper share striking similarities with parsing methods : top down, shift reduce, CKY... Relating the proposal with well known methods would add some substantial value to the paper. "}}]

Author rebuttal:

Meta-review: Summary: The paper focuses on generating the expression tree rather than the expression tokens sequentially for math equation generation. The proposed method combines the method from Seq2DAG and DETR, where Seq2DAG constructs the tree in a bottom-up layer-wise fashion and DETR uses a method to extract multiple objects in each layer in parallel. The system minimizes the number of steps involved in generating the expression structure by building the expression tree iteratively in bottom-up order. The system issues multiple queries to the problem representation at each step, generating valid expressions that are added to the problem embedding for the next step. The process stops when no valid expression is generated. The experimental results on the MWP task demonstrate the effectiveness of their approach, particularly for long equations and equations with complex tree structures.

Strengths: All the reviewers unanimously agree that this is a solid contribution with interesting implications. The proposed method adapts query-based detection combined with layer-wise decoding to math word problems seems novel and appropriate. The comprehensive experimentation conducted in this study greatly contributed to understanding the mechanism of the proposed method.

Weaknesses: I don't think there are any major weaknesses -- some of the weaknesses have been addressed during the discussion phase. The authors should take the comments during the rebuttal into account when preparing for the final version of the paper.
Decision: Accept-Main