ORCHARD: A Benchmark For Measuring Systematic Generalization of Multi-Hierarchical Reasoning

Bill Tuck Weng Pung, Alvin ChanarXiv 2021 · OpenReview

Abstract

The ability to reason with multiple hierarchical structures is an attractive and desirable property of sequential inductive biases for natural language processing. Do the state-of-the-art Transformers and LSTM architectures implicitly encode for these biases? To answer this, we propose ORCHARD, a diagnostic dataset for systematically evaluating hierarchical reasoning in state-of-the-art neural sequence models. While there have been prior evaluation frameworks such as ListOps or Logical Inference, our work presents a novel and more natural setting where our models learn to reason with multiple explicit hierarchical structures instead of only one, i.e., requiring the ability to do both long-term sequence memorizing, relational reasoning while reasoning with hierarchical structure. Consequently, backed by a set of rigorous experiments, we show that (1) Transformer and LSTM models surprisingly fail in systematic generalization, and (2) with increased references between hierarchies, Transformer performs no better than random.

Introduction: The Multi-Hierarchical Challenge

Natural language is not merely a flat sequence of words; it is a nested hierarchy where sentences form paragraphs and words within those sentences often refer back to previous entities. To truly master language, a model must perform multi-hierarchical reasoning: it must parse individual tree structures and understand the complex relationships between those trees.

While existing benchmarks like ListOps test a model's ability to parse a single tree, they fail to capture the relational reasoning required for real-world language. The central question addressed by the ORCHARD benchmark is whether current state-of-the-art models—Transformers and LSTMs—implicitly learn these hierarchical biases or merely exploit surface-level patterns.

Methods

The study evaluates two dominant NLP architectures:

  1. Transformer: A 44.3M parameter model relying entirely on self-attention.
  2. Bi-directional LSTM with Attention: A 6.2M parameter recurrent model.

Models were trained on a sequence-to-sequence task using the ORCHARD dataset. To measure systematic generalization, models were trained on "shallow" trees (depths 3 to 6) and evaluated on "deep" trees (up to depth 12). This tests whether models can apply learned rules to structures significantly more complex than those encountered during training.

The ORCHARD Dataset

The Operating Relational Cum-Hierarchical Arithmetic Reasoning Dataset (ORCHARD) introduces a novel challenge. Each input consists of two mathematical trees in Polish notation, separated by a delimiter.

Example of ORCHARD dataset structure showing cross-tree references via the COPY operator.

The dataset uses positional operators (FIRST, LAST), comparative operators (MIN, MAX), and a unique relational operator: COPY. The COPY operator in the second tree references a specific node's value from the first tree based on its position in a level-order traversal. This design forces the model to parse the first tree accurately and maintain its structure in memory to solve the second tree. Difficulty levels (Easy, Medium, Hard) are determined by the frequency of COPY operators.

Key Insights

  • The Relational Bottleneck: Models perform reasonably well on single trees but struggle significantly when required to use a value from one tree to solve another. This suggests a lack of robust internal hierarchical representation.
  • Recurrence vs. Attention: Surprisingly, the recurrent LSTM architecture generalized to deeper trees significantly better than the Transformer when evaluating the first tree. However, both architectures failed on the relational COPY task at greater depths.
  • Logical Complexity: Models found positional operators (FIRST/LAST) easier than comparative ones (MIN/MAX), indicating that identifying sequence positions is simpler than performing logical comparisons across nested structures.

Key Results

The experimental results highlight a stark failure in systematic generalization. While both models performed well within the training distribution (depths 3-6), accuracy plummeted beyond depth 7.

Systematic generalization performance of Transformer and LSTM models across varying tree depths and task difficulties.
  • Transformer Collapse: At a tree depth of 12, the Transformer’s accuracy on the "Hard" task dropped to approximately 10%, which is equivalent to random guessing among the 10 possible digit outputs.
  • LSTM Advantage: On the first tree at depth 12, the LSTM maintained 86-88% accuracy, whereas the Transformer struggled between 48-54%.
  • The Relational Trap: In the "Hard" variant, where the second tree depends entirely on the first via COPY, both models failed to generalize to deeper structures, identifying multi-hierarchical reasoning as a major blind spot for current architectures.

Conclusion and Future Work

ORCHARD serves as a rigorous diagnostic tool, revealing that even our most advanced models struggle with cross-hierarchical referencing. While the dataset uses synthetic mathematical structures, it isolates specific architectural failures that likely impact performance on complex natural language tasks. Future research should focus on developing architectural inductive biases specifically designed for cross-hierarchical referencing and investigating why recurrent structures like LSTMs appear to retain hierarchical "memory" better than attention-based Transformers during out-of-distribution generalization.

Summary updated

Abstract

The ability to reason with multiple hierarchical structures is an attractive and desirable property of sequential inductive biases for natural language processing. Do the state-of-the-art Transformers and LSTM architectures implicitly encode for these biases? To answer this, we propose ORCHARD, a diagnostic dataset for systematically evaluating hierarchical reasoning in state-of-the-art neural sequence models. While there have been prior evaluation frameworks such as ListOps or Logical Inference, our work presents a novel and more natural setting where our models learn to reason with multiple explicit hierarchical structures instead of only one, i.e., requiring the ability to do both long-term sequence memorizing, relational reasoning while reasoning with hierarchical structure. Consequently, backed by a set of rigorous experiments, we show that (1) Transformer and LSTM models surprisingly fail in systematic generalization, and (2) with increased references between hierarchies, Transformer performs no better than random.
BibTeX
@misc{pung2021orchard,
  author = {Bill Tuck Weng Pung and Alvin Chan},
  title = {{ORCHARD: A Benchmark For Measuring Systematic Generalization of Multi-Hierarchical Reasoning}},
  year = {2021},
  eprint = {2111.14034},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2111.14034},
}
Figure