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

Venue: colmweb_org_COLM_2024_Conference
Published: 2024-03-18 02:58:12

Abstract: Large language models such as ChatGPT and GPT-4 have recently achieved astonishing performance on a variety of natural language processing tasks. In this paper, we propose MANGO, a benchmark to evaluate their capabilities to perform text-based mapping and navigation. Our benchmark includes 53 mazes taken from a suite of textgames: each maze is paired with a walkthrough that visits every location but does not cover all possible paths. The task is question-answering: for each maze, a large language model reads the walkthrough and answers hundreds of mapping and navigation questions such as "How should you go to Attic from West of House?" and "Where are we if we go north and east from Cellar?". Although these questions are easy to humans, it turns out that even GPT-4, the best-to-date language model, performs poorly at answering them. Further, our experiments suggest that a strong mapping and navigation ability would benefit large language models in performing relevant downstream tasks, such as playing textgames. Our MANGO benchmark will facilitate future research on methods that improve the mapping and navigation capabilities of language models. We host our leaderboard, data, code, and evaluation program at https://mango.ttic.edu and https://github.com/oaklight/mango/.

Main paper: 
 introduction: 
 Mapping and navigation are fundamental abilities of human intelligence (Spiers & Maguire, 2006; Epstein et al., 2017) . Humans are able to construct maps-in their minds (Epstein et al., 2017) or on physical media like paper-as they explore unknown environments. Following these maps, humans can navigate through complex environments (Spiers & Maguire, 2006; Spiers & Gilbert, 2015; Javadi et al., 2017) , making informed decisions, and interact with their surroundings. Such abilities empower humans to explore, adapt, and thrive in diverse environments. An example is remote (e.g., deep-sea) exploration for which humans have drawn upon their intuition to develop algorithms that enable robots to autonomously navigate and map their surroundings based only on onboard sensing. Do large language models (LLMs) possess such abilities? In this paper, we investigate this research question by creating a benchmark and evaluating several widely used LLMs. Our MANGO benchmark is the first to measure the mapping and navigation abilities of language models. It includes 53 complex mazes, such as the one visualized in Figure 1 . It pairs each maze with hundreds of destination-finding questions (e.g., "Where will you be if you go north, north, and then up from Altar?") and routefinding questions (e.g., "How do you reach Dome Room from Altar?"). For each maze, the language model has to answer these questions after reading a walkthrough of the maze. Many questions involve possible routes that are not traced during the walkthrough, making the benchmark very challenging.In our experiments, GPT-4 only correctly answered half of the route-finding questions, performing disastrously on the difficult questions (e.g., those that involve long and unseen routes). MANGO will facilitate future research in improving the mapping and navigation abilities of LLMs.Another contribution of MANGO is to draw a novel connection between natural language processing and robotics. There has been significant interest in employing LLMs to endow intelligent agents (including robots) with complex reasoning (Yang et al., 2023) . Aligning with this interest, MANGO enables the investigation of the LLMs' capabilities in simultaneous localization and mapping (SLAM) within text-based worlds. Focusing on this aspect, our work stands out and complements previous SLAM-related research, which predominantly relies on richer sensory inputs (e.g., vision and LiDAR). Figure 1 : An example map for the maze of Zork-I. Arrows denote the direction of travel during the walkthrough, while the reverse direction is unseen but may be possible. Note that it is a 3D map projected onto a 2D plane so up may not point upward in the 2D visualization (e.g., Rocky Ledge to Canyon View). 
mango: a benchmark for text-based mapping and navigation: 
 Our MANGO benchmark measures the mapping and navigation capabilities of LLMs. It includes 53 complex mazes such as the one visualized in Figure 1 ; this particular maze is taken from Zork-I, the very first textgame in history. This figure was drawn according to the first 70 steps of the walkthrough of Zork-I, which can be found in Example 1. This map is imperfect: the annotator had to draw the only Kitchen twice to avoid a cluttered visualization; the Living Room was incorrectly placed outside the House. However, equipped with this map, one could correctly answer questions about any route in the maze such as "How do you reach Dome Room from Altar?" and "Where will you be if you go north, north, and up from Altar?". The walkthrough has not traced a route from Altar to Dome Room, but humans possess the remarkable capacity to plan a route by identifying the three individual steps-which the walkthrough has covered-from Dome Room to Altar and retracing those steps. MANGO tests whether a large language model can perform the same kind of reasoning.When evaluating a language model, we first let it read a walkthrough like Example 1 and then ask it questions like those in Examples 2 and 3. A question like Example 2 is a destination-finding (DF) question, and a question like Example 3 is a route-finding (RF) question. Users of MANGO have the flexibility to phrase the DF and RF questions in their own ways: as shown in Examples 4 and 5, we provide the skeletons of these questions, which users can plug into their own templates.Next, we introduce how we constructed this benchmark, including the data and evaluation program.Our mazes are taken from the textgames in the Jericho game suite (Hausknecht et al., 2020) . The main release of Jericho includes 57 popular textgames as well as a program that can generate walkthroughs for 56 of them. The original walkthrough of a game is a list of actions (such as east, north, and open door) that one could execute to efficiently complete the game. We enhanced each walkthrough by executing the sequence of actions and augmenting each step with the new observation (i.e., the text feedback that the game engine provides after the action is executed). Unless explicitly specified, the word "walkthrough" refers to the enhanced, but not original, walkthroughs (such as Example 1) throughout the paper. More details about walkthroughs can be found in Appendix A.1.In a walkthrough, not every action triggers a location change: it may update the inventory (such as take lamp and drop pen) or time (such as wait). For each game, we read the walkthrough, labeled the actions (such as east and up) that change the locations, and made note of the names of the locations (such as Temple and Altar). This annotation is nontrivial and can not be automated. We had to pay extra attention to appropriately handle the tricky cases including:• the name of a location may be mentioned in a rich, but distracting context. For example, the context may have ten paragraphs and hundreds of words with the name briefly mentioned in the middle. • a location may be visited multiple times, so we need to assign the same name to all its mentions.• different locations may be referred to with the same name in the textual feedback, so we need to rename them in a sensible way. The game of Night is an example: hallways on different floors are all referred to as Hall; we renamed each of them, e.g., with Hall (1st floor, north end).The location name resolution (see Appendix A.2 for a full procedure) results in a maze for each game. Three of the games have no location change, and so we left them out, resulting in 53 mazes. We store each maze as a directed graph: each node is a named location (e.g., Altar); each directed edge is a movement (e.g., north); and each node-edge-node combination is a location-changing step that was followed in the walkthrough. Note that a graph may be cyclic since the walkthrough may trace back-and-forth between locations (e.g., Temple and Egyptian Room in Figure 1 ).To generate DF and RF skeletons for a maze, a naive approach is to perform brute-force traversal. First, we collect all the possible S-P-D tuples, where S and D are locations and P is a simple path from S to D. A simple path is a directed path that does not visit any location more than once. This "simple" restriction ensures that we will have a finite number of S-P-D tuples. Example 6 is a simple path of 3 S-A-D edges from Altar to Dome Room. Each unique S-P-D tuple gives a unique DF skeleton: e.g., Example 4 is obtained from Example 6. Each unique S-P-D tuple gives an RF skeleton as well, such as Example 5 obtained from Example 6. However, the same RF skeleton may be obtained from other tuples since there may be multiple possible simple paths between the same pair of locations S and D.As a consequence, we may end up with fewer RF questions than DF questions for a given maze.The particular DF and RF questions in Examples 2 and 3 are challenging to large language models, since they involve actions-such as going north from Altar to Temple-that are not covered in the walkthrough. Answering such hard questions requires a deeper understanding of the spatial relationships between locations. However, also because these steps are not in the walkthrough, the skeletons in Examples 4 and 5 can not be obtained through a naive traversal of the directed graph in Figure 1 . That is, we have to traverse an extended graph that includes imputed edges. An imputed edge denotes a valid step that is not explicitly mentioned in the walkthrough, such as going north from Altar to Temple (i.e., Altar-north-Temple). Most mentioned edges involve directional moves (e.g., up, down, east, north), so reversing them is a straightforward way to impute new edges. We manually examined other edges: for some of them, we proposed intuitive reverses (such as exit for enter); for the others (e.g., pray), no reverse could be found. We then examined the imputed edges through real game play and discarded those that failed to cause the expected location changes. Appendix A.3 documents the full procedure of edge imputation and examination.After extending all the mazes in our benchmark, we collected 21046 DF skeletons and 14698 RF skeletons by traversing the extended graphs. While evaluating an LLM on a maze, the LLM may not be able to consume the entire walkthrough in its limited context window. That is, we may only feed it an appropriate prefix of the walkthrough (e.g., the first 70 steps for Zork-I as shown in Example 1), leaving some of the DF and RF skeletons unanswerable given that prefix. Therefore, our benchmark provides the ANSWERABLE label (an integer) for each skeleton such that this skeleton is only answerable if the maximum STEP NUM in that prefix (e.g., 70 in Example 1) is greater than or equal to its ANSWERABLE label. Furthermore, given a walkthrough prefix, an answerable skeleton may be easy or hard, depending on whether it involves edges that are not covered in the prefix. Precisely, a DF skeleton is considered to be easy if all the S-A-D edges in its corresponding simple path are covered in the walkthrough prefix; an RF skeleton is easy if the shortest simple path from its starting location to its destination only involves the S-A-D steps covered in the prefix. Overall, when a longer walkthrough prefix is used, more answerable questions tend to be easy. Therefore, our benchmark provides the EASY label (also an integer) for each skeleton: a skeleton is easy if the maximum STEP NUM in the walkthrough prefix is no smaller than its EASY label; otherwise, it is a hard skeleton. Table 3 in Appendix A documents the statistics of the full dataset, such as the number of locations and the number of skeletons. Tables 5 6 7 8 in Appendix B shows the information about the data on which each LLM was evaluated in our experiments.The evaluation program in our benchmark implements a range of evaluation and analysis methods.Reading the model-generated answers, it can return a set of evaluation scores together with rich analysis. In this section, we introduce the most important scores used in our main experiments. Other scores are discussed in Appendix A.6, with their related experiments presented in Appendix B.4.For DF questions, the most straightforward evaluation is the success rate: i.e., the fraction of questions that the language model answers correctly. What answers will be considered to be correct? A strict criteria is that the model answer is correct if and only if it exactly matches the ground-truth location name. However, due to the variability of natural language, a correct model answer may not exactly match the ground-truth. For example, the model may yield The House or That House when the ground-truth location name is just House. To account for such cases, we generalize the success rate to allow partial matches. Given a model answer Â and the ground-truth answer A, we compute their (character-level) edit-distance d and define a correctness score c def = 1 -d/ℓ where ℓ is the length of the longer answer. The score is ∈ [0, 1]: when the answer exactly matches the ground-truth, we have c = 1; if they have no character overlap at all, then c = 0. We then define the success rate to be the sum of the correctness scores over all the questions, divided by the number of questions.For RF questions, the main metric is still the success rate, but the definition of "success" is different from that for DF questions. Note that an answer to an RF question is a sequence of moves. We consider an answer to be correct if and only if it can reach the destination after our evaluation program executes it in the maze. A correct answer to an RF question may not be a good path: it doesn't have to be the shortest; it doesn't even have to be a simple path. It is possible that an LLM-generated move is meaningful but doesn't exactly match any valid move in the graph: e.g., the LLM may give walk south, which means the same as south. Therefore, when executing a model-generated move, our evaluation program will select the closest (i.e., smallest edit-distance) valid move. 
experiments: 
 In this section, we present the results our evaluation of several widely used LLMs.The evaluated models are: GPT-3.5-turbo (Brown et al., 2020; Stiennon et al., 2020; Gao et al., 2022) , GPT-4 (OpenAI, 2023) , Llama-2 with 13B parameters (Touvron et al., 2023b) , and RWKV with 14B parameters (Peng et al., 2023) . For GPT-3.5 and GPT-4, we used the prompt templates in Examples 7 and 8, converting the DF and RF skeletons like Examples 4 and 5 into LLM-friendly questions like Examples 2 and 3. The templates were carefully designed and examined through pilot experiments, in order to ensure that we do not underestimate the models on our benchmark. In our templates, each question starts with a list of legal actions, followed by a list of reachable locations. The presence of these two lists discourages a language model from hallucinating nonexistent moves or locations, thus improving the success rate of the model. The templates ask the model to spell out the entire trajectory including all the intermediate locations. This design is inspired by Chain-of-Thought prompting (Wei et al., 2022) : eliciting an LLM to give its entire reasoning process tends to improve its overall performance on downstream tasks. In addition, it allows us to conduct a deeper evaluation and analysis, such as the reasoning accuracies of the models (see Appendices A.6 and B.4 ). Note that our templates request the model to form its answer as a list of Python dictionaries with specific key names. We found that this restriction encourages the model to generate structured answers-which are easy to parse and analyze-as well as improves its performance. For Llama-2 and RWKV, we made moderate revisions to the prompts in order to generate well-structured answers (that are easy to parse and analyze) as well as optimize for their performance.For GPT-3.5, we experimented with the 4K version, which can consume 4096 tokens in its context window. This context limit restricts the length of the walkthrough that it can read, and the number of DF and RF questions that it can answer. Table 5 shows the statistics about the walkthrough prefix and questions that GPT-3.5 used for each maze. For GPT-4, we used the same walkthrough prefixes and questions as GPT-3.5 for a fair comparison. Llama-2 has a 4096 context window as well. But its tokenizer is different from GPTs' so we evaluated it on a slightly different set of questions. RWKV is capable of handling infinite context. For each maze, we experimented it with the 70-step prefix of the walkthrough so that its set of answerable questions includes all the questions answered by all the other models. We also evaluated Llama-2 and RWKV in a simplified setting, where the observation at each step of the walkthrough only includes the location name but nothing else. For example, at STEP 1 of the simplified Example 1, OBSERVATION only has South of House and everything else (i.e., Your are...) is omitted. We refer to Llama-2 and RWKV with the simplified walkthroughs as Llama-2-S and RWKV-S, respectively. More details about the experiment setup are in Appendix B.1.Figure 2 presents the success rates of all models. For each kind of question (i.e., DF or RF), we show the results on easy and hard questions separately. As we can see, GPT-4 significantly outperforms all the other models on all kinds of questions. However, it only correctly answers half of the RF questions, far worse than what a human could do: in our experiments, humans perfectly answered a randomly sampled set of questions. Note that each model was evaluated on its specific set of questions determined by the length and format of the walkthrough it read. To be fair, we also (b) Pairwise comparison on easy (lower left) and hard (higher right) RF questions.Table 1 : Success rates on DF and RF questions broken down into pairwise comparisons. In each table, the cell of row-A and col-B contains the success rates of the models-in the format of A | B-on the intersection of the questions that A and B answered individually. The lower left triangle of the table displays the results on easy questions, while the upper right triangle shows the results on hard questions. compared each pair of models on the intersection of the questions that they answered. The results are presented in Table 1 : as we can see, GPT-4 and GPT-3.5 consistently outperform the other models and GPT-4 significantly outperforms GPT-3.5.More results are in Appendix B.4, including results on other evaluation metrics and comparison between Llama-2 with Llama-1 and Llama-2-chat.Now, we focus our analysis on the best models, namely GPT-3.5 and GPT-4. We aim to understand the improvements of GPT-4 over GPT-3.5 as well as the current bottlenecks for GPT-4, shedding light on opportunities for future improvements.By analyzing the errors of GPT-3.5 and GPT-4, we discovered that these models occasionally hallucinate nonexistent locations or edges. Once they made such a mistake at any step of reasoning, they would be misled and deviate from the correct path towards the correct answer. Furthermore, we found that the mazes are not equally difficult for the models. Figure 3 displays the success rates of the GPT models broken down into their per-game results.In each figure of Figure 3 , each dot is a maze: the x-axis coefficient is the performance of GPT-3.5 on this maze while the y-axis is that of GPT-4. As we can see, the success rates of the models vary across different mazes as well as across different kinds of questions. GPT-4 consistently outperforms GPT-3.5 across nearly all the mazes. The only exception is Seastalker: there are too few hard DF questions for this maze, and thus it is a noisy outlier. Apparently, both GPTs tend to work better on easy questions than on hard questions. However, some mazes seem to be particularly challenging to GPT-4, such as Zenon and OMNIQuest.To answer this question, we collected some important statistics about the mazes and analyzed their correlation with the success rates of the models. To understand the success rates on the easy questions, it is interesting to investigate:• number of locations (# locations) and number of explicit edges (# exp edges). These quantities directly measure the size of a maze, which may be a key indicator of its difficulty. • number of potentially confusingly named locations (# conf locations). Recall from section 2.1 that different locations may have similar or related names, which may confuse a language model. To quantify the number of confusingly named locations, we compute a confusion score for each location, and then sum the scores across all the locations. For a location name A, the confusion score is defined to be the maximum word-level edit distance between A and any other location name in the maze, divided by the maximum word-level length of the pair of location names being compared. Technically, it is max B (edit-distance(A, B)/ max(len(A), len(B))), and it is ∈ [0, 1]. • average length of the easy simple paths (avg len easy), i.e., the simple paths that do not include any imputed edges. A longer path may tend to be more difficult for models. • average number of words in the scene descriptions (avg len scene). The walkthroughs exhibit very diverse styles: for some of them, the text description for each scene is very concise and the name of each location is appropriately highlighted; for others, each description may be verbose (e.g., ten paragraphs and hundreds of words) and the location names are often not obvious from the contexts. It is useful to analyze whether a long scene description poses a challenge for the models.In order to understand the models' performance on hard questions, we analyze the effects of the variables above (except avg len easy) as well as the following:• number of imputed edges (# imp edges).• average length of the hard simple paths (avg len hard), i.e., the simple paths with imputed edges.• average number of imputed edges in the hard simple paths (avg # imp in hard).We use regression analysis to understand the effects of the aforementioned variables on model performance. In particular, for each model (GPT-3.5 or GPT-4) on each type of question (DF or RF, easy or hard), we ran single-variable linear regression to understand how the success rate varies with each of the variables of interest. Table 2 displays the regression results. As we can see,• on easy questions, GPT-3.5 and GPT-4 are influenced by the size of the maze, the confusion level of location name, and the path length. The effects are significant with extremely small p-values. • on easy questions, the average length of the scene descriptions does not have a significant effect on the performance of GPT-3.5, but interestingly has a significant positive effect on GPT-4's performance. It is perhaps because GPT-4 possesses a strong capability to understand texts and can leverage the rich contexts in each description. This allows it to better distinguish confusingly named locations and establish a better internal representation of the map. However, this richness seems to confuse GPT-3.5 and impede its ability to create a good internal representation of the maze, possibly due to GPT-3.5's weaker overall language understanding capabilities. • on hard questions, the variables do not seem to significantly affect the performance of GPT-3.5.Note that GPT-3.5 yields very low success rates when answering the hard DF and RF questions.It seems that GPT-3.5 struggles when it has to reason about a path with any number of imputed edges, making the effect of other factors less important to its performance. • on hard questions, GPT-4 exhibits a stronger ability to handle paths with imputed edges, compared to GPT-3.5. However, it will experience difficulties when the challenge of inferring imputed edges is amplified by other factors such as the size of the maze or the length of the path. As a result, nearly all the variables have significant effects on GPT-4.The results of our regression analysis are consistent with the plots in Figure 3 . For example, both Zenon and OMNIQuest stay at the lower-left corners of the hard-question plots in Figure 3 since their mazes are particularly challenging to both GPT-3.5 and GPT-4: they both have substantially larger numbers of imputed edges than the other mazes; OMNIQuest also has more locations. Wishbringer and Lost Pig have several imputed edges, but their paths are short, so they fall in the upper-left corners of the hard-question plots in Figure 3 .In our pilot experiments, we ran a multivariate regression analysis that used the aforementioned variables jointly. However, the results of this regression are misleading: due to colinearity among the explanatory variables, the estimated coefficients are unreliable and the p-values are inflated. We also tried principled component regression, but the first principle component has nearly equal loadings across all the variables, making it inconvenient to interpret the results.Now we present a case study showing that a strong mapping and navigation ability of an LLM would benefit it in downstream tasks. In particular, we selected 284 minigames in the Jericho game suite, and investigated how the map knowledge may improve the performance of an LLM in playing these minigames. Each minigame is a selected step from one of 53 textgames; the selection criterion is that the best action to take at this step is a movement. Through evaluating an LLM on a minigame, we synthesize a scenario in which the LLM has to figure out the best action to take given its previous actions and observations (i.e., the prefix of walkthrough up to the current step). Note that this task is different and more challenging than answering the DF and RF questions: the LLM is not explicitly given a route (as in DF questions) or a destination (as in RF questions), but has to spontaneously figure out which action may contribute to its long-term goal.For this task, we evaluated GPT-3.5 and GPT-4. For each model, we tried two settings: the first is to condition the LLM on the walkthrough like Example 1; the second is to include in the prompt the information about the nearby locations, and an example of the full prompt is given in Example 9. The information about nearby locations is the ground-truth information that the LLM, in principle, should have learned from the walkthrough prefix. If the LLM had a perfect mapping and navigation ability, it would be able to perfectly spell it out and use that information to guide its decision making.Figure 4 presents the results of this experiment. GPT-4 significantly outperforms GPT-3.5 in playing these minigames, consistent with their relative performance when answering the DF and RF questions of our MANGO benchmark. For each of the GPT models, having access to nearby location information significantly improves its performance, demonstrating that a strong mapping and navigation ability is essential to succeeding at relevant downstream tasks. 
related work: 
 Over the past few years, the field of natural language processing has experienced remarkable advancements with the emergence of large language models. This progress has spurred a multitude of research endeavors that propose benchmarks challenging the limits of these models. Those benchmarks assess the capacities of LLMs in linguistics (Wang et al., 2018; 2019) , reading comprehension (Richardson et al., 2013; Lai et al., 2017) , commonsense reasoning (Zellers et al., 2019; Bisk et al., 2020; Huang et al., 2019; Talmor et al., 2019) , arithmetic reasoning (Miao et al., 2020; Cobbe et al., 2021; Patel et al., 2021) , and knowledge memorization and understanding (Clark et al., 2018; Mihaylov et al., 2018; Khot et al., 2020; Clark et al., 2020; Hendrycks et al., 2021; Srivastava et al., 2022) . Recent models have achieved remarkable performance not only on these benchmarks, but also across a diversity of human-oriented academic and professional exams (OpenAI, 2023) as well as general tasks (Bubeck et al., 2023) . Our benchmark presents a unique challenge to large language models, evaluating their capacity to acquire spatial knowledge about new environments and answering complex navigation questions; it is a dimension orthogonal to the aforementioned reasoning abilities.The advances of LLMs have sparked a recent wave of endeavors that integrate these models into embodied agents (Huang et al., 2022c; Yang et al., 2023; Vemprala et al., 2023; Wang et al., 2023a) . Generally, they utilize language models as a means to understand human instructions and plan executable actions (Driess et al., 2023; Liang et al., 2022; Huang et al., 2022b; Ichter et al., 2023) . This includes instructions related to object manipulation and tool operation (Wang et al., 2023b; Ren et al., 2023) as well as localization and navigation (Majumdar et al., 2020; Gadre et al., 2023; Shah et al., 2023; Huang et al., 2022a) . Our MANGO benchmark aligns with the growing trend to deploy LLMs in embodied agents and provides a comprehensive investigation of their capacities in mapping and navigation. Our benchmark operates in text-based environments, distinguishing itself from previous benchmarks (Puig et al., 2018; Shridhar et al., 2020; Fan et al., 2022) that allow agents to utilize visual signals. This "text-only" design 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 (Duvallet et al., 2014; Mei et al., 2016; Anderson et al., 2017; Fried et al., 2018; Zhu et al., 2020; Min et al., 2021) . Our work is related to recent studies that demonstrate the emergence of maps with learned neural representations as a consequence of navigation (Huynh et al., 2020; Wijmans et al., 2023) with the key distinction that our agents are provided with textual descriptions of their environments.Given our focus on mapping and navigation, it is worth noting the work on simultaneous localization and mapping (SLAM), a classic problem in which a mobile agent (e.g., a robot or hand-held camera) is tasked with mapping an a priori unknown environment while concurrently using its estimated map to localize itself in the environment (Mur-Artal et al., 2015; Cadena et al., 2016) . Particularly relevant are the methods that maintain spatial-semantic maps of the environments based on natural language descriptions (Walter et al., 2013; Hemachandra & Walter, 2015) , however they rely on non-linguistic observations (e.g., vision) to ground these descriptions. 
conclusion: 
 We present MANGO, a benchmark that evaluates the mapping and navigation abilities of large language models. Our benchmark covers a diversity of 53 mazes as well as a variety of evaluation and analysis programs, offering a comprehensive testbed in a great breadth and depth. In our experiments, the current best model still performs poorly on the benchmark, with a sharp degradation on the more difficult questions. We release our benchmark-along with the source code for data generation and evaluation-to track the advances of the mapping and navigation capabilities of future large language models as well as to facilitate future research in related areas. 
 
 Appendix: Our data and program is released at https://anonymous_for_now. In the data folder, each game has a folder that contains multiple JSON files. The most important files are the DF and RF skeletons (where X is the game name such as zork or detective):• X.df: it contains the DF skeletons like Example 4.• X.rf: it contains the RF skeletons like Example 5.As introduced in section 2.2, each skeleton is paired with an ANSWERABLE label and an EASY label: given a prefix of the walkthrough, the ANSWERABLE label indicates whether this skeleton is answerable, and the EASY label will decide whether this skeleton is easy or hard given this walkthrough prefix. Table 3 displays some important statistics of the full dataset broken down into each individual maze, including the number of DF and RF skeletons. In addition, we also provide the following data files for easy reference:• X.walkthrough: it contains the full walkthrough of the game. See Appendix A.1 for details.• X.locations: it lists all the locations. Details about annotating these locations can be found in Appendix A.2.• X.moves: it lists all the moves that may change the location.• X.all_pairs: it contains all the pairs of distinct locations.• X.all2all: it contains all the simple paths between any pair of distinct locations.In the following subsections, we will explain the details about collecting this data.In this section, we document the technical details about walkthroughs.The only game that doesn't have a walkthrough is Leather Goddesses of Phobos (LGoP).There may be multiple correct ways to complete a game with the same level of efficiency. So the program has some randomness. In our experiments, we fixed the random seed for better reproducibility.Each action in the program-generated walkthroughs is a highly abbreviated symbol such as E for East and NW for Northwest. For a better readability, we use the full words in our enhanced walkthrough such as Example 1.For each maze, our human annotator read the walkthrough and annotated all the locations. In most cases, the surrounding description given by the game engine includes the name of the location, and the annotator needs to manually extract it from the text; this process is difficult to automate because the text is often unstructured and an automatic extractor is hard to build. What makes this annotation tricky is• a location may be visited more than once in the walkthrough but we should avoid assigning multiple names to it.• distinct locations may be referred to in the same way by the game engine but we should distinguish them.We solved the problems above by hacking into the source code of the game engines and conducting multiple rounds of human verification. First, for each maze, we checked the source code of the game provided by the Jericho game suite (Hausknecht et al., 2020) and found the unique ID for each location. Matching IDs with human annotations allows us to perform the following post processing:• when a location is given multiple names, our human annotators work together to select the most proper unique name that they all agree on. The selection principles are: it is descriptive; whenever this location is visited in the walkthrough, the name has an intuitive match with the surrounding description given by the game engine. When counting the easy and hard skeletons, we assume that the full walkthrough will be used. For the statistics of the data used in our experiments, please see Tables 5 6 7 8 .• when multiple locations share a name, our human annotators work together to distinguish them by adding descriptive marks. An example is the Halls mentioned in section 2.1: we renamed them to be Hall (1st floor, north end of north/south hall), Hall (1st floor, middle of north/south hall), and Hall (2nd floor, middle of north/south hall). There are rare cases in which all the annotators agreed that no marks could be added and the location names had to be kept fuzzy (i.e., a name corresponds to multiple different locations). The rationale is: if a human may confuse with these locations, then it is reasonable for a model to have the same confusion. Then allowing them to share the name is essentially to apply a looser evaluation to the models: e.g., if the name Forest is overloaded, then when the model answers "how to reach Forest from House", any path that ends at any of the Forests will be considered to be correct. This treatment is equivalent to merging the locations with the same human-annotated name.In our repository, there is a data-intermediate folder that tracks such intermediate annotations.In the folder of each game, the JSON files anno2code and code2anno track the mapping between machine IDs and human-annotated location names.Why don't we just use the unique IDs as the location names? Because the IDs are often not intuitive or descriptive and they are often just strings of digits. Such IDs may not match any content in the walkthrough so a human or model may be confused when asked about the path between "loc12" and "loc5" after reading the very descriptive walkthrough.During human annotation, we labeled all the moves that change the locations. Like in Appendix A.2, we used the source code of the game engine to verify the human annotations. This annotation led to a map for each game-like what's shown in Figure 1 -but this map is incomplete since there exist implicit moves between locations. For example, south is a movement that can end up at Altar if we start from Temple; see Figure 1 . It means that north is also a possible move from Altar and it leads to Temple; but this edge has never explicitly shown up in the walkthrough. We would like our questions to cover such implicit edges, so we examined every possible implicit edge and inserted the valid ones into our map (though Figure 1 only displays the explicit edges).The examination was carried out through real game playing by our human annotators. For each directional move (e.g., south), we tested if its reverse directional move (e.g., north for south, down for up) could lead to the previous location. Not every move is directional: e.g., in Zork-I, you may enter and exit the House; pray moves the player from Altar to Forest. We had such edges examined by human annotators: for some (e.g., enter), we could find intuitive reverse moves and verify them; for the others (e.g., pray), we didn't propose any reverse. Usually, the list of moves we ended up for a game includes eight possible directional moves as well as a few special moves.Once we have figured out all the locations and moves for a game, we will end up with a map. We collected all the unique pairs of distinct locations in the map and stored them in the all_pairs file: for each pair of locations A and B, we could ask a route finding question that aims to reach B from A.Note that A,B and B,A are different pairs.For each pair of the starting point A and destination B, we collected all the simple paths P that connects from A to B. Each (A,B,P) tuple defines a destination finding question about where one will be if they go through path P from A.A.5 PROGRAM DETAILS Our graph and path operations (e.g., finding simple paths) are handled by the networkx package.Its documentation is at https://networkx.org/. Particularly, the program that finds all the simple paths for a pair of graph nodes is at https://networkx.org/documentation/ stable/reference/algorithms/generated/networkx.algorithms.simple_paths. all_simple_paths.html.Another important-yet more strict-evaluation is the reasoning accuracy. This evaluation requires the language model to spell out its planned trajectories of moves when answering questions (like requested in our Examples 7 and 8). For an RF question, the reasoning process is correct if and only if the model-generated trajectory is a valid path from the starting position S to the destination D : the first step starts from S; each step starts from where it ended up in the last step; the final step reaches D. For a DF question, the model-generated trajectory has to be a valid path from S to the model-generated destination D; in addition, the sequence of moves in the trajectory has to match the given list of actions A. Like we explained in section 2.3, the "match" here is not an exact match: if the closest valid move is the correct move, then it is counted as a "match".In this section, we present our experiment details for reproducing the results.The specific GPTs used in our experiments are GPT-4-0314 and for GPT-3.5-turbo-0301. For 14B RWKV model, the specific model version we are using is "RWKV-4-Pile-14B-20230313-ctx8192-test1050". For Llama-2, we used the ckeckpoint officially released by Meta.For all the models, we set the temperature of the LLMs to be 0 for reproducibility.For GPTs, our prompts are the concatenation of walkthrough like in Example 1 and the questions like in Examples 2 and 3; the questions are obtained by filling the templates in Examples 7 and 8. When calling OpenAI API, we set the "role" to be "user" and the "content" to be the prompt. After receiving the response from the API call, we processed the output string by fetching the content from the structured output (recall that we request the models to return Python lists of Python dictionaries).What prompts are to LLMs are like what hyperparameters are to classifical deep neural nets. To ensure that we could obtain the optimal results of RWKV and Llamas, we tuned the prompts-more precisely, experimented with variants of the prompts of GPTs-and ended up with a set of new prompts that are mostly the same but exhibit some prose differences. For example, at the beginning of the prompts, we added "Here is a walkthrough of a text game."It is worth noting that, even though we carefully tuned the prompts, the non-GPT models still suffer a high chance of failing to return well-structured answers. Table 4 shows the average number of answered questions as well as how many of them received ill-formatted answers. As we could see, GPT-3.5 and GPT-4 could generate well-structured answers for a large portion of the DF and RF questions, but the other models often gave ill-structured answers. As a result, we could only evaluate the non-GPT models on the questions to which the answers were well-structured and thus could be parsed. We also experimented with the function-calling interface of GPTs, but it didn't lead to an increased amount of well-structured answers compared to our prompt design. In this section, we present the results of each LLM measured by reasoning accuracy, the metric introduced in Appendix A.6. Results are shown in Figure 5 , with their pair-wise comparison shown in Table 9 . As we can see, the trend measured by this metric is similar to what's shown in section 3: GPT-4 is the best among all the evaluated models but still suffers a low accuracy. Figure 6 shows the reasoning accuracies of GPT-3.5 vs.GPT-4 broken down into individual games, showing similar patterns with Figure 3 . R W K V R W K V -S L 


Decision: The paper introduces MANGO, a benchmark to evaluate large language models' (LLMs) abilities in text-based mapping and navigation. It uses 53 mazes from text games, each with a walkthrough covering all locations but not all possible paths. 

Pros:
1. The paper effectively operationalizes the known difficulty of text-only spatial reasoning for LLMs, proposing a concrete assessment method.
2. Significant effort and attention to detail were invested in creating and verifying the benchmark, including manual work and verification. The evaluation includes multiple models and demonstrates the task's difficulty, reinforcing the benchmark's relevance.
3. The dataset has diverse 53 mazes and are mapped to a large number of DF and RF questions.
4. More details, which are answering all questions on the human evaluation are provided in the rebuttal.

Cons:
1. As the minigames are the trajectories sampled from the prefixes, it is unclear how they are different downstream tasks compared to the benchmark itself. Reviewer 1xds raises the same concern. It is advisable if the authors conduct downstream task experiments to validate this.
2. Human evaluations included a study on sketching maps during the rebuttal. It is unclear how this map-sketching is mapped to model performance.

Neutral comment: Model performance analysis on the categories of the failures would make the analysis strong. The authors presented some categories of failures, which if can be made more systematic would be helpful for future directions. As the reviewers pointed out this direction, the authors seemed keen on performing model representation analysis which would be a standalone paper as they responded. However, atleast discussing the categories or types of failures beyond easy hard questions would provide better insight into the benchmark. 

Originality: The paper is clear in its presentation of the benchmark and its importance, though some sections are dense. The originality lies in the novel benchmark for assessing text-based mapping and navigation, which addresses a previously underexplored area in LLM capabilities particularly in the framing of the maze equivalent itself for text spatial reasoning.

Significance: The work is significant as it identifies a critical gap in current LLM performance and provides a structured way to evaluate and improve text-based spatial reasoning, which could enhance performance in related downstream tasks.

Reviews: review: paper_summary: paper_summary: The authors propose a benchmark to test LLM's ability on text-based spatial reasoning (mapping and navigation). The benchmark uses mazes that are paired with walkthroughs which cover all the location but not necessarily all the paths. Evaluation results show that current best models still struggle on this task. The authors also provide tests to showcase how the mapping capability can improve the text-game playing ability.
strength_weakness: strength_weakness: - The text is a bit dense which makes it hard to follow at times (eg., 2.1, 2.2, 2.3; especially 2.2); might be better to split up the sections when it comes to introducing new ideas (e.g., That is, we have to traverse an extended graph that includes imputed edges. An imputed edge denotes [...]).
- The authors showcase the usefulness of having the mapping capability added to the model for downstream tasks. However, this is done by sampling from the minigames from the same suite; it might help if the authors can provide some quantification on how different is the downstream task to the walkthrough to really understand its usefulness.
paper_summary: paper_summary: The paper introduces a benchmark to test the ability of large language models for text-based mapping and navigation. The benchmark includes several maps paired with a walkthrough, along with a large number of destination-finding and route-finding questions and answers. Through evaluations on multiple open source and close source, large language models, the authors demonstrate that this task is very challenging  even for the most advanced models.
strength_weakness: strength_weakness: Two aspects where l I believe the paper could be improved:

1. The comparison to the human performance is hand wavy at best. The authors mention that humans answered a random number of selected questions, and based on that the performance of the models was deemed below that of human performance. Given that this is a benchmark, I believe it is important to have a strong human reference. I would like to see significant details included on this aspect of the evaluation, including among others: how many questions were evaluated by humans; what is the agreement between them; what is the performance on easy versus hard questions; etc. 

2. It would be useful to include information on how the prompt robustness was tested. Just as an example, considering the prompt shown in Example 9: how would a change in this prompt affect the model? For instance, if the prompt is ordered differently; or if a paraphrase used; or if there are additional irrelevant details included; etc

Consider including the actual walkthrough used (even if only partial) for the example in Fig 1, to give a better sense of what is seen by the models. 


Minor: acronyms are not consistently used, Eg, see the captions for Examples 2-5; the use of LLM (or not), etc
questions: questions: Please see items 1 and 2 under “reasons to reject”
paper_summary: paper_summary: The paper introduces MANGO, a benchmark for assessing large language models' mapping and navigation abilities (LLMs). The benchmark comprises 53 mazes from text-based games paired with walkthroughs, mapping, and navigation questions. The authors evaluate the performance of several LLMs, including GPT-4, on this benchmark. They find that even GPT-4 struggles with the tasks, particularly on challenging questions involving unseen paths. The paper demonstrates that strong mapping and navigation abilities can benefit LLMs in downstream tasks like playing text-based games.
The paper is well-structured, with a detailed description of the benchmark creation process and comprehensive experiments. The methodology is clearly described, and the results are presented in an organized manner with supporting statistical analyses and visualizations.
The MANGO benchmark is novel in its focus on evaluating LLMs' mapping and navigation abilities, addressing an aspect that has received limited attention in prior research. The findings have implications for applications such as embodied agents and robotics.
However, the benchmark's current scope may be limited, as it focuses on text-based game environments. The paper lacks a comprehensive comparison with existing methods for mapping and navigation tasks and does not provide a deep analysis of the underlying mechanisms contributing to the LLMs' performance.
Overall, the paper makes a contribution by introducing a new benchmark and evaluating LLMs' mapping and navigation abilities, but there is room for improvement in terms of scope, comparison with existing methods, and analysis of underlying mechanisms.
strength_weakness: strength_weakness: 1. Limited scope of the benchmark:
While the MANGO benchmark introduces a novel approach to evaluating the mapping and navigation abilities of LLMs, the current scope of the benchmark may be limited. The benchmark consists of 53 mazes derived from text-based games representing a specific environment type. It is unclear whether the performance of LLMs on this benchmark would generalize to other types of environments or real-world scenarios. The authors could consider expanding the benchmark to include a more diverse set of environments or discussing the limitations and potential challenges in generalizing the findings to other contexts to strengthen the paper.

2. Lack of comparison with existing methods:
The paper focuses on evaluating the performance of LLMs on the MANGO benchmark but does not provide a comprehensive comparison with existing methods for mapping and navigation tasks. While the authors mention that their work complements previous research on vision-language navigation, they do not directly compare the performance of LLMs with state-of-the-art approaches in this domain. Including a comparative analysis with existing methods could help contextualize the performance of LLMs and provide a clearer understanding of their strengths and limitations in mapping and navigation tasks.

3. Insufficient analysis of the underlying mechanisms:
Although the paper thoroughly evaluates LLMs' performance on the MANGO benchmark, there is limited analysis of the underlying mechanisms that contribute to their successes and failures. The authors provide some insights into the factors that influence the performance of LLMs, such as the maze size and the path length but do not delve deeper into the specific aspects of the models' architectures or training that may impact their mapping and navigation abilities. A more detailed analysis of the models' internal representations and decision-making processes could provide valuable insights for future research and developing more effective LLMs for spatial reasoning tasks.
questions: questions: 1. Generalizability of the benchmark: The current MANGO benchmark comprises 53 mazes derived from text-based games. How well do you expect the performance of LLMs on this benchmark to generalize to other types of environments or real-world scenarios? Are there any plans to expand the benchmark to include a more diverse set of environments, and what challenges do you anticipate in doing so?

2. Comparison with existing methods: The paper focuses on evaluating the performance of LLMs on the MANGO benchmark but does not provide a comprehensive comparison with existing methods for mapping and navigation tasks, particularly in the domain of vision-language navigation. Could you discuss how the performance of LLMs on the MANGO benchmark compares to state-of-the-art approaches in related domains? What insights can be gained from such a comparison, and how might it inform future research in this area?

3. Analysis of underlying mechanisms: The paper thoroughly evaluates LLMs' performance on the MANGO benchmark but offers limited analysis of the underlying mechanisms that contribute to their successes and failures. Can you provide more insight into how the specific aspects of the models' architectures or training might impact their mapping and navigation abilities? What additional experiments or analyses could be conducted to better understand LLMs' internal representations and decision-making processes in the context of spatial reasoning tasks?
paper_summary: paper_summary: The paper introduces a new benchmark called MANGO, which focuses on evaluating the mapping and navigation abilities of large language models. The benchmark consists of a set of mazes paired with textual walkthroughs, challenging models to navigate through the mazes based on the provided instructions. The paper discusses the motivation behind creating the benchmark, the design of the mazes and walkthroughs, and the evaluation of models, including GPT-4, on the benchmark tasks.
strength_weakness: strength_weakness: The paper presents a benchmark with 53 mazes, which could be seen as limited in scale. Moreover, it's unclear how to enable LLM models to comprehend complex mazes, as it may require instructions with more tokens than the LLM window can accommodate.

The paper briefly mentions the poor performance of GPT-4 on certain questions but does not delve deeply into the specific limitations or challenges faced by the model in mapping and navigation tasks. A more detailed analysis of model weaknesses could offer valuable insights for future improvements.

Comments: comment: Thank you for the response!

The detailed human evaluation is summarized below. 31 RF questions and 30 DF questions were evaluated. Success rate (loose) is the main metric used in the paper, which allows partial string matching using edit-distance (discussed in Sec 2.3). The strict version requires exact string matching and is provided as a reference. The reasoning accuracy metric is discussed in Appendix A.6.

Humans generally achieve near-perfect success rates with no significant difference between easy and hard questions. The distinction between easy and hard questions lies in the need to reason about reversed edges (e.g., inferring "b->west->a" from "a->east->b"), which is challenging for LLMs but straightforward for humans.

Imperfections in reasoning accuracy scores are due to: 1) the requirement for exact string matching, and 2) human errors in typing location names with special symbols.

| Difficulty          | Total Tasks | Success Rate (Loose) | Success Rate (Strict) | Reasoning Accuracy |
|---------------------|-------------|----------------------|-----------------------|--------------------|
| **Route Finding**   |             |                      |                       |                    |
| All                 | 31          | 0.8211               | 0.8065                | 0.6129             |
| Easy                | 20          | 0.7727               | 0.75                  | 0.55               |
| Hard                | 11          | 0.9091               | 0.9091                | 0.7273             |
| **Destination Finding** |        |                      |                       |                    |
| All                 | 30          | 1.0                  | 1.0                   | 0.5667             |
| Easy                | 21          | 1.0                  | 1.0                   | 0.6667             |
| Hard                | 9           | 1.0                  | 1.0                   | 0.3333             |



Previously, different experts evaluated different questions, so a human agreement score wasn't available. Due to time constraints, a subset of the previously evaluated questions (10 RF, including 2 HARD, and 10 DF, including 3 HARD) were re-evaluated by different experts. Since DF and RF questions can have multiple valid solutions, the answers were not directly compared for agreement. Instead, the mean squared error (MSE) was computed for each metric across tasks and difficulty levels. For each file evaluated in both rounds, the squared error was calculated as (x₁ - x₂)² and then averaged by task type, difficulty, and metric type, as shown below. In general, MSE was low for both RF and DF questions in terms of our main metric.

|                    | All                |                |                | Easy               |                |                | Hard               |                |                |
|--------------------|--------------------|----------------|----------------|--------------------|----------------|----------------|--------------------|----------------|----------------|
|                    | Loose   MSE        | Strict  MSE    | Reasoning MSE  | Loose MSE          | Strict MSE     | Reasoning MSE  | Loose MSE          | Strict MSE     | Reasoning MSE  |
| Route Finding      | 0.1442             | 0.2222         | 0.3333         | 0.0425             | 0.1429         | 0.1429         | 0.5                | 0.5            | 1.0            |
| Destination Finding| 0.0                | 0.0            | 0.6            | 0.0                | 0.0            | 0.5714         | 0.0                | 0.0            | 0.6667         |
Thank you for your answers, and the additional evaluation.

To follow up on the human evaluation -- some questions I had in my original review that still feel unanswered: 
"how many questions were evaluated by humans; what is the agreement between them; what is the performance on easy versus hard questions; etc."