A Bottom-Up DAG Structure Extraction Model for Math Word Problems

Yixuan Cao, Feng Hong, Hongwei Li, Ping Luo

Abstract

Automatically solving Math Word Problems (MWPs) requires translating natural language into solvable mathematical equations. Traditional Sequence-to-Sequence (Seq2Seq) and Sequence-to-Tree (Seq2Tree) models often struggle with the structural complexity of algebraic systems and ignore fundamental mathematical properties. This paper presents Seq2DAG, a novel bottom-up approach that represents equation sets as Directed Acyclic Graphs (DAGs). By iteratively building expressions and explicitly incorporating commutativity into the architecture, Seq2DAG achieves state-of-the-art results on major benchmarks, including a 13.4% accuracy improvement on the complex DRAW1K dataset.

1. Introduction

Translating a word problem—such as "Tom and his father's ages are in a 1:5 ratio..."—into a system of equations is a significant challenge for AI. While recent deep learning models have made progress, they face three primary limitations. First, Seq2Seq models often lack structural awareness, leading to mathematically invalid outputs. Second, Seq2Tree models are typically restricted to univariate arithmetic and fail to handle systems of equations where variables are reused. Finally, most models ignore mathematical symmetries, such as the commutative law ($a + b = b + a$), requiring the network to learn these patterns from data alone.

Figure 1: Comparison of standard Equation Trees and the proposed Aligned DAG representation for a system of equations.

To address these issues, we propose representing equation sets as DAGs. While a single equation can be viewed as a tree, a system of equations is more naturally represented as a DAG because intermediate results and variables are frequently shared across different equations.

2. Methodology: The Seq2DAG Model

The Seq2DAG model extracts equation sets using a bottom-up strategy, mimicking the human process of identifying sub-expressions before solving the entire problem.

2.1 Bottom-Up Strategy and DAG Decoder

The model begins with "leaf" nodes—quantities and variables identified in the text. It then iteratively searches for valid triplets consisting of an operator and two operands. When a triplet is classified as a valid sub-expression, it is added as a new node in the DAG, becoming available as an operand for subsequent layers.

Figure 2: The DAG Decoder architecture illustrating the layer-by-layer bottom-up construction process.

2.2 DAG-LSTM and Mathematical Properties

The core of the decoder is a specialized DAG-LSTM designed to handle mathematical properties:

  • Non-Commutative Cells: Used for subtraction and division, where operand order is critical. These utilize an N-ary Tree-LSTM structure.
  • Commutative Cells: Used for addition, multiplication, and equality. These employ a Child-Sum structure, ensuring the hidden representation remains identical regardless of operand order (e.g., $x+y$ vs $y+x$).

This architectural choice hard-codes mathematical laws into the network, reducing the search space and increasing robustness.

3. Experiments and Results

The model was evaluated on two primary benchmarks: DRAW1K (1,000 complex algebra problems with multiple equations) and Math23K (over 23,000 arithmetic problems).

3.1 Performance Metrics

Seq2DAG demonstrated significant performance gains over previous baselines:

  • DRAW1K: The model achieved 44.4% accuracy, representing a massive 13.4% absolute improvement over the previous deep learning baseline (DNS).
  • Math23K: It reached 77.1% accuracy, outperforming the previous state-of-the-art Graph2Tree model (75.5%).
  • Ablation Study: Removing the commutative law design resulted in a 2.5% drop in performance, validating the importance of incorporating mathematical rules into the architecture.

3.2 Efficiency

Despite the iterative nature of checking candidate triplets, the model remains efficient. The average inference time is approximately 53ms per problem, making it suitable for real-time applications.

4. Conclusion and Future Work

Seq2DAG provides a robust framework for solving complex MWPs by leveraging the structural advantages of DAGs and the efficiency of bottom-up extraction. However, the model still faces challenges with coreference resolution—distinguishing between different entities (e.g., "apple trees" vs "pear trees") when linguistic context is subtle. Future research will focus on incorporating additional mathematical properties, such as the associative law, and improving text encoders with graph-based representations to better capture entity relationships.

Summary updated

Abstract

Research on automatically solving mathematical word problems (MWP) has a long history. Most recent works adopt Seq2Seq approach to predict the result equations as a sequence of quantities and operators. Although result equations can be written as a sequence, it is essentially a structure. More precisely, it is a Direct Acyclic Graph (DAG) whose leaf nodes are the quantities, and internal and root nodes are arithmetic or comparison operators. In this paper, we propose a novel Seq2DAG approach to extract the equation set directly as a DAG structure. It is extracted in a bottom-up fashion by aggregating quantities and sub-expressions layer by layer iteratively. The advantages of our approach approach are three-fold: it is intrinsically suitable to solve multivariate problems, it always outputs valid structure, and its computation satisfies commutative law for +, x and =. Experimental results on Math23K and DRAW1K demonstrate that our model outperforms state-of-the-art deep learning methods. We also conduct detailed analysis on the results to show the strengths and limitations of our approach.
BibTeX
@inproceedings{cao2021bottom,
  author = {Yixuan Cao and Feng Hong and Hongwei Li and Ping Luo},
  title = {{A Bottom-Up DAG Structure Extraction Model for Math Word Problems}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.1609/aaai.v35i1.16075},
}
Figure