PaperlayerView exact revision on arXiv

Source-linked AI summary

StepGame: A New Benchmark for Robust Multi-Hop Spatial Reasoning in Texts

Zhengxiang Shi, Qiang Zhang, Aldo Lipani

arXiv:2204.08292v1cs.CLcs.AI

TL;DR

Few datasets evaluate inference over spatial information in text, and bAbI’s spatial tasks have limitations in leakage, diversity, and reasoning depth. The paper introduces StepGame and TP-MANN; existing models struggle on StepGame, while TP-MANN achieves state-of-the-art performance on both datasets.

  • Problem

    Few existing datasets evaluate models’ inference over spatial information in text, while bAbI tasks 17 and 19 have leakage, fixed entities and relations, shallow reasoning, and synthetic descriptions.

    Source: §1 · pp. 1–2

  • Method

    The paper introduces StepGame, built from crowdsourced descriptions of spatial relations, and TP-MANN, which uses tensor-product representations in recurrent memory for inferred entity relations.

    Source: §1 · p. 2

  • Results

    Existing models fail to match their bAbI performance on StepGame and drop as reasoning steps increase, while TP-MANN achieves state-of-the-art performance on both datasets.

    Source: §1 · p. 2, §6 · p. 7

  • Takeaways & Limitations

    StepGame evaluates robust multi-hop spatial reasoning that bAbI’s tasks do not require, and the paper’s analysis finds recurrent memory important for multi-hop reasoning.

    Source: §1 · p. 2, §6 · p. 7

    The bAbI spatial tasks use fixed entities and limited relations, require only shallow reasoning, and use synthetic descriptions, limiting what they reveal about textual spatial understanding.

    Source: §1 · pp. 1–2

Abstract

from arXiv · show

Inferring spatial relations in natural language is a crucial ability an intelligent system should possess. The bAbI dataset tries to capture tasks relevant to this domain (task 17 and 19). However, these tasks have several limitations. Most importantly, they are limited to fixed expressions, they are limited in the number of reasoning steps required to solve them, and they fail to test the robustness of models to input that contains irrelevant or redundant information. In this paper, we present a new Question-Answering dataset called StepGame for robust multi-hop spatial reasoning in texts. Our experiments demonstrate that state-of-the-art models on the bAbI dataset struggle on the StepGame dataset. Moreover, we propose a Tensor-Product based Memory-Augmented Neural Network (TP-MANN) specialized for spatial reasoning tasks. Experimental results on both datasets show that our model outperforms all the baselines with superior generalization and robustness performance.

1 Introduction

Spatial inference in text matters for communication and navigation, yet few datasets evaluate it; this paper introduces StepGame and TP-MANN to address bAbI’s limitations and multi-hop reasoning needs.

1 Introduction

  • Spatial reasoning in text is relevant to navigation, situated dialog, and robotic manipulation, but remains challenging for conversational systems.The paper frames spatial-language understanding as important for following instructions and understanding spatial descriptions.Source: §1 · p. 1
  • bAbI tasks 17 and 19 have train–test leakage, fixed entities and limited relations, shallow reasoning requirements, and synthetic descriptions.The paper notes that most test samples appear in training, and that the tasks can be solved in a single step.Source: §1 · pp. 1–2
  • Existing models fail to match bAbI performance on StepGame and drop sharply as reasoning steps increase, while TP-MANN achieves state-of-the-art performance on both datasets.TP-MANN also demonstrates better generalization to more complex stories.Source: §1 · p. 2
  • StepGame uses crowdsourced templates for eight spatial relations, many named entities, and multi-hop questions, with combinatorial story growth reducing leakage risk.Crowdworkers diversified the templates to cover natural ways of describing relations between two entities.Source: §1 · p. 2
  • TP-MANN uses tensor-product representations in recurrent memory to store, update, or delete inferred entity relations.The recurrent architecture supports inference from memory and multi-hop reasoning, is described as robust to noise, and keeps parameter count unchanged as recurrent layers increase.Source: §1 · p. 2

2 Related Work and Background

Prior work offers few datasets for evaluating spatial inference in text, while existing multi-hop QA datasets generally require fewer reasoning steps than StepGame. The background introduces tensor-product representations as a way to encode and retrieve symbolic structure.

2.1 Related Work

  • Few existing datasets evaluate spatial reasoning over text, and SpartQA requires less multi-hop reasoning than StepGame.bAbI tasks 17 and 19 evaluate positional reasoning and path finding, but have data leakage, fixed entities and expressions, and little need for multi-hop reasoning.Source: §2.1 · p. 2
  • StepGame can require up to 10 reasoning steps, while common multi-hop QA datasets usually require no more than two.The paper distinguishes StepGame by its focus on inferring spatial relations among described entities.Source: §2.1 · p. 2
  • Transformers and other reasoning architectures have been studied for spatial and relational reasoning, but prior analyses report persistent difficulty on bAbI’s spatial tasks.The related work describes memory-augmented networks, graph neural networks, and transformer-based networks.Source: §2.1 · p. 2
  • Prior TPR-RNN and STM models store symbolic structures in memory, but do not process paragraphs or allow later information updates as TP-MANN does.STM achieves state-of-the-art bAbI performance but takes longer to converge in practice.Source: §2.1 · p. 3

2.2 Background

  • Tensor Product Representation encodes symbolic structure in vector spaces by binding role-filler pairs with outer products and retrieving a filler through an unbinding role.The background calls the resulting representation a memory and notes that recovery is perfect when role vectors are orthogonal.Source: §2.2 · p. 3

3 The StepGame Dataset

StepGame is a contextual question-answering dataset for inferring relative positions from natural-language stories. It combines crowdsourced relation descriptions with multi-hop chains and distracting noise, and its possible sample space grows exponentially with chain length.

3 The StepGame Dataset

  • StepGame tests spatial inference from natural-language stories and questions, including robustness to distracting noise.Each question asks for the relative position of two entities described in the story.Source: §3 · p. 3

3.1 Template Collection

  • Crowdworkers supplied diverse natural-language templates for describing positional relations, with 23 templates for left/right, 27 for top/down, and 26 for diagonal relations.Templates were collected iteratively, with previously accepted answers shown as examples to encourage new descriptions.Source: §3.1 · p. 3

3.2 Data Generation

  • Each sample forms a chain of k relations among k + 1 entities; the question selects two entities, and their edge distance determines the required number of hops.Answers use nine relative-position labels, including overlap.Source: §3.2 · p. 4
  • Generation samples a chain and its relations, selects two entities for the question, then translates and shuffles relation descriptions using crowdsourced templates.The answer is inferred from the generated chain and selected entities.Source: §3.2 · p. 4
  • With |E| = 26, the possible sample space grows exponentially: k = 1 yields 10,400 samples and k = 2 yields more than 23 million.The paper states that increasing sample complexity diminishes the probability of train-test sample leakage; including templates would increase the number of variations further.Source: §3.2 · p. 4

3.3 Distracting Noise

  • Test examples add disconnected, irrelevant, or supporting noise, which does not change the correct answer; Figure 2 marks the noise additions in green.Supporting noise is added only to chains with more than two entities.Source: §3.3 · p. 4, Figure 2 · p. 4

4 The TP-MANN Model

TP-MANN combines a story-and-question encoder, recurrent memory module, and relation decoder to infer spatial relations. Its memory stores and updates entity–relation representations, allowing episodes to interact without increasing trainable parameters as recurrent layers are added.

4 The TP-MANN Model

  • TP-MANN has a story-and-question encoder, a recurrent memory module, and a relation decoder that uses stored information to infer the queried spatial relation.The encoder represents entities and relations in story sentences; the memory stores and updates those representations.Source: §4 · p. 4
  • The encoder applies positional encoding to word embeddings, averages them into sentence and question vectors, then uses feed-forward networks to form entity and relation representations.The resulting search keys are used to manipulate memory and retrieve potential existing associations for entity–relation pairs.Source: §4 · p. 5
  • Adding recurrent layers lets stored episodes interact with new inferences without increasing the number of trainable parameters.The memory module updates a TPR-like memory representation across T recurrent layers.Source: §4 · p. 5
  • At the first memory layer, story sentences are stored as episodes; later layers use pseudo-entities to connect episodes and identify old episodes for updating or removal.New episodes are then added to memory, which is updated by removing old episodes and adding new ones.Source: §4 · pp. 5–6
  • The decoder retrieves information from the final memory recurrently using question-derived unbinding vectors, then maps the result to a vocabulary probability distribution.The output uses a linear projection and softmax.Source: §4 · p. 6

5 Experiments and Results

The experiments compare TP-MANN with baselines on bAbI and StepGame, examining data leakage, spatial inference, generalization to larger k, and the effect of recurrent-layer count.

5.1 Material and Baselines

  • Experiments use bAbI tasks 17 and 19 and StepGame, with StepGame training on k = 1–5 and testing on k = 1–10 with distracting noise.Five baselines are compared, with each model trained and validated independently on each dataset.Source: §5.1 · p. 6, §5 · p. 6

5.2 Training-Test Leakage

  • Test-set overlap is 23.2% for bAbI task 17 and 80.2% for task 19 sentence-question pairs, compared with 1.09% for StepGame pairs before noise and template use.Removing StepGame examples with k = 1 reduces its reported overlap to 0%.Source: §5.2 · p. 6

5.3 Spatial Inference

  • On bAbI tasks 17 and 19, TP-MANN is slightly better than the best baseline, but these results do not firmly answer the spatial-inference question.The authors cite bAbI dataset issues as the reason for this qualification.Source: §5.3 · p. 6, Table 1 · p. 6
  • TP-MANN outperforms all baselines on noisy StepGame test data, where baseline accuracy decreases as the required inference hops increase.The table reports average performance across k; the training set is noise-free, while the test set includes distracting noise.Source: Table 2 · p. 7, §5.3 · p. 7

5.4 Systematic Generalization

  • TP-MANN outperforms baseline models by a large margin on larger-k StepGame tests, while RN, RRN, UT, and SAM fail to generalize to higher k.Models are trained on k values 1–5 and evaluated on larger values; performance degrades as k increases.Source: Table 3 · p. 7, §5.4 · p. 7

5.5 Inference Analysis

  • Higher-k test sets benefit more from additional recurrent layers, and performance on k values beyond training improves as T increases.The number of trainable parameters remains unchanged as T increases; the authors note that fewer recurrent layers than story length may suffice, suggesting inference may occur in parallel.Source: §5.5 · p. 7, Figure 4 · p. 7

6 Conclusion

The paper introduces StepGame for robust multi-hop spatial reasoning and TP-MANN, which achieves state-of-the-art performance on both datasets.

6 Conclusion

  • StepGame targets robust multi-hop spatial reasoning and mitigates bAbI’s issues, while TP-MANN achieves state-of-the-art performance on both datasets.Further analysis indicates the importance of a recurrent memory module for multi-hop reasoning.Source: §6 · p. 7

Related papers

Loading 2204.08292v1…