MANGO: A Benchmark for Evaluating Mapping and Navigation Abilities of Large Language Models

This paper propose a new benchmark for evaluating LLMs' mapping and navigation abilities (MANGO) by constructing 53 mazes (language-described walkthrough) from textgames and questions asking the LLMs to find a destination or infer a route. Extensive filtering and human examination are applied to ensure the data quality. Chain-of-Thoughts and prompt engineering are considered for LLMs. A range of latest LLMs including GPT-3.5-Turbo, GPT-4, Llama-2, and RWKV are evaluated accordingly to the success rate of the models in responding to the destination and route finding questions. Experiments show that GPT-3.5 and GPT-4 achieve the best results while still performing poorly on hard questions and occasionally hallucinate nonexistent locations or edges. Analysis also demonstrates that LLMs with better mapping and navigation capabilities can better solve relevant downstream tasks, suggesting potential in addressing other embodied navigation tasks.

This paper aims to evaluate the mapping and navigating abilities of large language models (LLMs) by proposing a new dataset called MANGO, which comprises 53 mazes taken from Zork-I. The LLMs are given a walkthrough as input and tasked with completing two types of tasks: destination-finding and route-finding. The study evaluates GPT-3.5, GPT-4, LLaMa, and RWKV models on this dataset and provides an analysis of the results for GPT models.

The paper introduces a new benchmark dataset for evaluating the mapping and navigation abilities of large language models. The authors construct 53 mazes from a suite of textgame. Given a walkthrough that visits every location in the maze, the LLM is tested with a suite of synthetically generated destination-finding and route-finding questions. The authors test with three families of LLMs, RWKV, LLAMA-2 and GPT, as well as LLMs of different sizes and notice clear performance gap in terms of model capabilities. They further conduct deep comparison between GPT 3.5 and GPT 4 on a range of controlled experiments which helps understand the factors that affect model performance, as well as the association with downstream tasks.

The paper presents a benchmark that evaluates the mapping and navigation abilities of LLMs. The proposed benchmark covers 53 mazes as well as evaluation strategies taken from text games dataset and modified to suit the requirement for the benchmark tasks. As base model performance is poor, hence it is claimed for future scope of research. Also, the authors promise to release the data and code. The authors claim their work as a first to measure the mapping and navigation abilities of LLMs. However, the novelty and hardness of the work done is not established. Suggestions: An experiment might be comparing trained human performance in similar task vs a data trained LLM.

[General Response - Have We Evaluated Strong Methods?]

R.14NH would like us to evaluate "vision language based models like CLIP".

As we explained in [General Response - Practicality and Impact], the MANGO benchmark is deliberately designed to be "text-only" and thus it is not within the scope of this paper to evaluate "vision language models like CLIP" (after all, there is no visual signals at all in a textgame). But we agree that it is a very interesting investigation that one could do in the future. Doing this investigation is non-trivial: one will need to build new datasets and evaluate a completely different set of models.

R.eNST suspects that "parse the walkthrough and draw the map first" will "have much better performance".

We appreciate this suggestion but genuinely disagree with this opinion. Below are 3 reasons (they have equal importance; we think "Third" is as important as "First" as a reason):

First, what we do is more than (quote R.eNST) "small amount of COT reasoning". Under our prompt, the COT reasoning given by an LLM is supposed to cover the necessary parts of the map that are actually relevant to the question. There is no guarantee that drawing the full map is helpful since it will introduce additional but non-relevant context (e.g., far-away locations). This issue of reduced signal-to-noise ratio will be severe when the map is large and the context becomes confusing to LLMs [1], which is likely to hurt the performance.

Second, some maps in MANGO have very simple scene descriptions such that the walkthrough already reads like a drawn map. In our experiments, an LLM still can not achieve a high success rate in such cases if the map or question itself is complex in some ways (e.g., size and implicit edges, as discussed in the paper).

Third, we evaluate some models in a simplified setting (see Sections 3.1 and B.1 in the paper), where the walkthrough mentions nothing but locations and their connections, such that the walkthrough indeed reads like a map. However, we didn't see an improvement in this setting (see Tab-1 in paper).

We think a map would only be useful if it was correct and it was used in a symbolic search algorithm. R.fKBg wonders whether the MANGO questions can be answered by "traditional search algorithms like depth-first-search or breadth-first-search". Yes, the questions would have become trivial using traditional search algorithms if a correct structured representation was built for a map. However, building such a representation---i.e., parsing a walkthrough into a map, is a very difficult task in the first place since it is generally a very challenging task to map unstructured text to structured forms [3]. Our case is particularly hard since the description of each step or location can be rich and many edges need imputation (see 2.2 in paper).

Our MANGO benchmark can be used to evaluate if an LLM can build such a structured representation internally (i.e., without consulting any external symbolic tools). According to our experiments, it seems that a more advanced LLM (e.g., GPT-4) tends to have a better ability to do so. An interesting future research direction is to investigate the internal representations of the LLMs and discover how such structures---if any---are formed and utilized. A concrete method to do this investigation is to probe for a "saliency map" like Li et al. 2023 [2]. Publishing our MANGO benchmark will enable not only us but also other researchers to conduct this and other important investigations in this area.

References:

[1] Liu, Nelson F., et al. arXiv preprint 2023. Lost in the middle: How language models use long contexts.

[2] Li et al. ICLR 2023. Emergent World Representations: Exploring a Sequence Model Trained on a Synthetic Task.

[3] Han et al. arXiv preprint 2022. FOLIO: Natural Language Reasoning with First-Order Logic.

[General Response - New Results]

We managed to finish a significant amount of new experiments. We present new results in this message, and hope that you like them!

However, we humbly remind the reviewers that our submitted version already has a rich set of results and analysis, a lot of which has to stay in the appendices due to page limit of the main paper. We understand that we haven't done everything; we really love the new experiments that the reviewers request; we would love to add new experiments during the discussion phase; we are committed to delivering an as good camera-ready version as possible. However, we also humbly request the reviewers to be mindful that this paper already has 24 pages and we have tried our best to establish the benchmark and appropriate baselines, which we believe is the primary goal of a data and benchmark paper. After all, what hasn't been done should not undermine the value and significance of what has already been done.

R.eNST requests more analysis on non-GPT models and wonders about the effects of "specific model designs, such as attention, position embedding, instruction tuning"; R.fKBg requests analysis on "additional LLMs" that are trained on code.

Per these requests, we present new results by evaluating more Llama-based models:

• code-llama-13B: Llama-2 continually pretrained on code data;
• code-llama-instruct-13B: code-llama-13B fine-tuned via instruction tuning.

We evaluated the models in both the original and simplified settings (see Sec 3.1 in paper). In each setting, for each maze, all the models read the walkthrough of the same length and thus were evaluated on the same set of test cases.

Here are the results:

Here are the takeaways from the new results:

• using code-tuned models significantly improved the success rates in most cases;
• instruction-tuning on top of code-tuned models is useful for RF questions, but doesn't seem to help much---if any---for DF questions.

The reason why code-tuning is helpful may be that such models are better at handling structured and semi-structured representations. Recall that our walkthrough and required output format follow a dict-like structure.

Please note that we can not practically experiment with certain variations of model designs such as attention or position embeddings while evaluating pretrained LLMs. This paper primarily focuses on evaluating them off-the-shelf. Publishing MANGO benchmark will enable future research that can afford other investigations.

[General Response - Novelty]

R.14NH is concerned with our work's "novelty and hardness" (which we interpret as "difficulty"); R.eNST asks us to explain how our work "differs from all other datasets".

Our MANGO benchmark is novel because it is the first to measure the mapping and navigation abilities of LLMs within text-based worlds. There has been significant research interest in leveraging LLMs to perform tasks (e.g., reading and generating executable actions in text). Our work aligns with this interest and provides a new benchmark to evaluate the text-based mapping and navigation abilities of LLMs, a dimension that has never been systematically explored in the literature. Thus, this benchmark is a unique contribution to the field.

Our benchmark is important for future research in this area because it can facilitate addressing the following fundamental questions:

• (1) what is the limit of the abilities of LLMs in text-based mapping and navigation?
• (2) what technical methods can help improve LLMs' text-based mapping and navigation abilities?

These questions can not be answered by working on the "other datasets" R.eNST suggests.

• SCAN [1] tests the execution of simple navigation commands (e.g., "dax twice" and "sing and dax") but our benchmark requires navigational reasoning. E.g., an LLM has to figure out a series of navigation commands for itself in order to answer "how can you go from A to B?", which is at a different level of difficulty than what SCAN tests.
• ALFRED [2] is similar to our MANGO but it has a different focus. It tests the models' abilities to understand and follow grounded instructions: the instructions are diverse; some are about navigation and the others are not (e.g., object detection and manipulation). Our MANGO focuses on mapping and navigation, and has a large diversity of map configurations (locations, connections, scenes, descriptions, etc). In addition, ALFRED has visual observations but MANGO is text-only; please see [General Response - Practicality and Impact] for why we design it to be text-only.

References:

[1] Lake, Brenden M. and Marco Baroni. ICML 2017. Generalization without Systematicity: On the Compositional Skills of Sequence-to-Sequence Recurrent Networks.

[2] Shridhar, Mohit et al. CVPR 2019. ALFRED: A Benchmark for Interpreting Grounded Instructions for Everyday Tasks.

[General Response - Presentation Improvements]

We will surely include all our new remarks, results, and analysis in the camera-ready version of the paper. Here are our proposed changes:

• in the Introduction, we will emphasize our novelty and contributions, as we have already discussed in [General Response - Novelty];
• in Section 2, we will explain why we chose text game environments, as we have already discussed in [General Response - Practicality and Impact];
• in Section 3, we will add all the new results of this rebuttal as well as relevant analysis, as we have shown in [General Response - New Results];
• we will add a new Limitations section to acknowledge the differences between our benchmark and more realistic settings, highlighting possible extensions that we could do in the future.

[General Response]

We thank all reviewers for their constructive feedback! We especially appreciate R.M8P4 for acknowledging the novelty, soundness, and usefulness of our work. Other reviewers have important concerns, but---as we will explain in this rebuttal---the causes of their concerns are our presentation but not the quality of the research.

In these to-all messages, we will clarify our technical contributions (e.g., novelty, soundness, practicality, etc) and propose presentation improvements. In addition, we ran new experiments within the past few days, and we present new results in this rebuttal. We hope that our rebuttal can set their minds on peace.

[General Response - Practicality and Impact]

R.fKBg worries that our benchmark is "too simplistic". But R.eNST seems to worry that our benchmark is not simple enough: R.eNST asks whether it is "necessary to derive the dataset from real text games" and whether it is better to use "pure synthetic data".

These are great questions and we carefully thought through them while designing this benchmark. In a nutshell,

• on one hand, we want the benchmark to be simple enough to conduct controlled experiments and comprehensive analysis;
• on the other hand, we want the benchmark to be realistically complex such that experiments on it can offer interesting findings and insights.

Text-games offer a sweet point to trade-off these two considerations:

• they are simplistic because the primitive actions are simple (e.g., east, north, up, down, etc);
• they are realistically complex because the environments are rich, covering diverse kinds of maps (small vs. big houses, long vs. short halls, verbose vs. concise scene descriptions, etc).

Moreover, textgames are deliberately designed by experts to challenge and entertain humans, and the 53 games in Jericho suite are the most popular and successful ones. Thus, they are supposed to challenge LLMs to an extent that interesting analysis can be done. Indeed, LLMs perform unsatisfactorily in our experiments and we have shown a lot of analysis.

We hope that readers like R.fKBg are mindful that research in synthetic worlds can have strong implications for realistic settings. E.g., the BLOCKS world is simplistic, but it enabled the development of SHRDLU [1], an early and influential natural language understanding computer program. Indeed, many good papers in 2023 still use the BLOCKS world as their testbed, e.g.,

• Valmeekam, Karthik, et al. NeurIPS23. On the Planning Abilities of Large Language Models--A Critical Investigation.
• Guan, Lin, et al. NeurIPS23. Leveraging Pre-trained Large Language Models to Construct and Utilize World Models for Model-based Task Planning.

In analogy, our MANGO is a repository of simple "BLOCKS worlds" for text-based mapping and navigation. There is a lot of interest in the robotics community in using language as a medium decomposing tasks into a sequence of subtasks that better match the primitives available to robots. We see mapping and navigation as one such example. Indeed, our results (like results in BLOCKS worlds) may not be immediately applicable to real-world embodied agents. However, as people in the robotics community increasingly rely on available LLMs for reasoning, there is merit in understanding the capabilities of these off-the-shelf models.

We can build our own synthetic maps as readers like R.eNST would like to see. But a purely symbolic map will be too simple to an LLM and too different from a realistic application setting. Designing a good synthetic map seems to be a step of designing a good textgame, so starting with existing text games prevents us from reinventing the wheels that we already have.

Why purely text-based worlds and text-based mapping and navigation?

Text is the ultimate interface of LLMs. Evaluating in a text-based world (quote from our Related Work) "enables us to conduct controlled experiments that investigate the capacity of language models to acquire knowledge about environments solely from textual inputs and answer navigation questions based on that knowledge. It complements the existing benchmark and methodological research in vision-language navigation." It will also facilitate the research in studying the emergence of maps within LLMs' learned representations.

Indeed, it is a debate whether using language as the ultimate interface is better than other options (e.g., vision language multimodal LLMs). But this question is orthogonal to our contribution and our benchmark will actually facilitate future research in answering this question.

In addition, there are indeed some settings where language has to be used as the ultimate interface. Some settings include HCI scenarios where humans communicate with robots (e.g., describe scenes and ask for navigational advice) in language, robots assisting visually impaired humans, and operating in low-visibility environments.

References:

[1] Winograd, Terry. Cognitive Psychology 1972. Procedures as a Representation for Data in a Computer Program for Understanding Natural Language.

[General Response - New Results of Symbolic Graph]

Per requests of R.eNST and R.fKBg, we ran new experiments (with GPT-3.5) to show the difficulty of converting walkthroughs to symbolic graphs.

We ran 2 distinct experiment settings:

• Experiment setting 1: Each demonstration is a single S-A-D triplet and we do 5-shot prompting. For each walkthrough, we use the first 5 steps as our demonstrations and evaluate on the remaining steps.
• Experiment setting 2: The prompt includes the entire walkthrough, without demonstrations. Then an LLM has to generate a sequence of S-A-D triplets which in principle can be used to construct graphs.

Note that the reviewers refer to a triplet as S-P-D which is incorrect. According to our notation,

• S-P-D is a starting location, a path of possibly multiple steps, and a destination.
• S-A-D is a starting location, an action (i.e., a single step), and a destination.

For each setting, we ran experiments on 6 mazes: Zork1, Night, Partyfoul, Plundered, Spirit, and Temple.

In both experiments, GPT-3.5 yields a low success rate (i.e., accuracy of the triplet completion) that is far from perfect, which indicates the difficulty of translating natural language into symbols/maps:

• In experiment setting 1, the average success rate is 70.5%. A LLM extraction is considered to be a success if it matches our human-annotated location name.
• In experiment setting 2, the average success rate is 6.3%. Definition is the same as setting 1. Since triplets are generated in a row, any mistake will cause all subsequent steps to be incorrect; that is why the overall accuracy is so low.

Some LLM mistakes and our error analysis can be found at this anonymized URL: https://hackmd.io/@anonymous123123123/BJJvjGhVT

The LLM errors in Experiment 1 are diverse and it will be very difficult to recover a correct graph from these LLM-generated triplets. Errors include:

• it extracts None. E.g., in Zork1, "Altar" was extracted as "None".
• location names are not even sensible names. E.g., "==>LOCATION: None" in Zork1.
• location names are sensible but incorrect in the contexts. E.g., in Night, "Hall (1st floor)" was named as "Hall (3rd floor)" by LLM, which is a fatal mistake.
• distinct locations are assigned the same name, so that the LLM-generated graph structure will be different from the ground-truth graph structure. E.g., in Temple, multiple "Road"s that are obviously different from descriptions are all labeled as "Road".
• the same location is assigned multiple different names (since it is visited and described at multiple steps) so that the LLM-generated graph structure is different from the ground-truth graph structure. E.g., in Night, "Hall (1st floor, north end)" is visited multiple times and receives a different name at each time.

This set of results verifies our claim that it is difficult to parse the walkthrough into useful structured formats, thus demonstrating the value of our MANGO benchmark (esp., compared to purely synthetic data).

[General Response - Why NOT Generated Graphs or Synthetic Data]

Now the main concerns of R.eNST and R.fKBg boil down to

• MANGO questions are easy to answer if the walkthrough is converted to a symbolic graph.
• why not use synthetic data and what is the additional value of textgames?

It seems convenient to address them in this general response.

Conversion to symbolic graph

We ran new experiments and the results verified our claim that this conversion is not as easy as reviewers thought. Please see [General Response - New Results of Symbolic Graph].

We hope that these new results can finally resolve the concerns.

Meanwhile, we would still like to emphasize that this paper is not about whether a symbolic approach can do better than LLM-off-the-shelf approaches. Rather, it is more about how well an LLM-off-the-shelf approach can do in mapping and navigation, which is an interesting question since many LLM+robotics systems indeed use LLMs that way. This investigation aligns with the significant interest in using LLMs as off-the-shelf problem solvers. For example, [1] investigates how well an LLM can do multi-digit multiplication by itself, without using a calculator. Of course, parsing the formula into calculator-readable format and then using a calculator may get a better result, but it is off the primary goal of that work. Similar remarks apply to our MANGO paper.

Why not synthetic data

Our main arguments are already in [General Response - Practicality and Impact]. Here, we would like to emphasize again:

Our key contribution is to take an initiative to evaluate mapping and navigation abilities of LLMs.

This contribution is orthogonal to how we generated data, as long as our data and experiments serve the research goal and support our claims. For synthetic data vs. textgames:

• synthetic data is easy to control but too dissimilar from realistic settings;
• textgame maps can not be changed but they are more realistic.

People like R.eNST and R.fKBg prefer the former; but there are surely other people preferring the latter. E.g., R.M8P4 hopes that our data is more realistic.

We believe that the community should have both kinds of benchmarks: they all function to evaluate the intelligent property of mapping and navigation; each benchmark has its own characteristics and focuses. That way, each benchmark fulfills needs of a certain kind of readers, and all the benchmarks collectively satisfy diverse tastes across the entire community.

R.eNST asks "most language navigation and embodied AI benchmarks are generated programmatically, what are the things that work for them, but not in the case here?" and "what is the advantage of using real textgames with extra processing?"

Note that we have explained the advantages of using textgames in [General Response - Practicality and Impact].

In addition, we could similarly ask questions like "there are good benchmarks that are not generated programmatically, so what are the things that work for them but not in the case here?" and "what is the advantage of using synthetic data but not real games?" To only name a few "not programmatically generated data":

• Room-to-Room. CVPR 2018.
• Vision-and-dialog navigation. CVPR 2020.
• ALFRED. CVPR 2020.

With this argument, we aim to make the point clear that benchmarks of different styles are all and equally useful; we choose to establish one of them, while someone else can do the others.

Dilemma about "synthetic data" and "symbolic search"

In the end, we would like to humbly point to a dilemma that has been overlooked in our previous discussion. That is, for synthetic data, a symbolic search approach can surely solve it, even without involving LLMs. Therefore, all the "symbolic search" arguments that reviewers use to challenge our MANGO data can apply to the "synthetic data" that they have been advocating, leading to a conclusion like "your synthetic data is bad because DFS or BFS can already solve it".

What can resolve this dilemma? The key is that such a benchmark is meant to measure and track the mapping and navigation abilities of using LLMs off-the-self, without leveraging any external tools. That ability is closer to the kind of intelligence that we would like LLMs to have, isn't it? Indeed, humans can map and navigate better with an external tool (e.g., a paper and a pen). But humans can also do it without an external tool, purely relying on their neural representations in the brains. This paper sets up where each modern LLM stands on this leaderboard. Then an interesting future direction is to investigate why each LLM stands where it is and how their internal representations may or may not capture the structures of the maps.

[1] Dziri, Nouha et al. NeurIPS 2023. Faith and Fate: Limits of Transformers on Compositionality.

The reviewers and the AC appreciate the detailed response from the authors, and there’s general agreement the benchmark is well constructed and the paper is well written.

The reviewers repeatedly raise concerns about the potential impact of the dataset and how what it studies extends to more realistic problems. Naturally, this is not to say all “toy” or closed-world experimental platforms are not useful. There are many such environments and tasks that have done much to promote research. In their response, the authors point to SHRDLU. While SHRDLU has received much attention for being first (to some degree), one could argue its impact has been debatable. The same applies to many block environments, although the AC agrees these can be impactful depending on how they are designed, and what research questions they aim to study. Indeed the authors provide some potential examples in their response.

The author directly address this question in their response. For example, the authors write:

Moreover, textgames are deliberately designed by experts to challenge and entertain humans, and the 53 games in Jericho suite are the most popular and successful ones. Thus, they are supposed to challenge LLMs to an extent that interesting analysis can be done. Indeed, LLMs perform unsatisfactorily in our experiments and we have shown a lot of analysis. This does not answer the broader utility question, unless the target is emulate the entertainment dispositions of people, which is not what the authors seem to aim. The authors also discuss relevance to the robotics community, but it’s not clear there’s evidence in the past for tight connections between text games and robotics.

Adding to the discussion below, using popular text games also raises issues of data contamination in the pre-training data. Depending on the research question, this might not be a problem. For example, the Voyager paper relies on this issue of the pre-training data containing information about Minecraft. However, this seems like it would hurt the study of the research question MANGO aims to study. I do understand the benefit of using data from existing games, which provide richness of design (tested through decades of use) that researchers would have a very hard time to re-create. But one must also consider pre-training contamination and how it may impact what the benchmark measures.

The AC generally agrees that the reviewers could have been more consistent and direct in their feedback. This has been taken into account.

Reject