Lost-in-Distance: Impact of Contextual Proximity on LLM Performance in Graph Tasks

## Abstract

Abstract Despite significant advancements, Large Language Models (LLMs) exhibit blind spots that impair their ability to retrieve and process relevant contextual data effectively. We demonstrate that LLM performance in graph tasks with complexities beyond the “needle-in-a-haystack” scenario—where solving the problem requires cross-referencing and reasoning across multiple subproblems jointly —is influenced by the proximity of relevant information within the context, a phenomenon we term “lost-in-distance”. We examine two fundamental graph tasks: identifying common connections between two nodes and assessing similarity among three nodes, and show that the model’s performance in these tasks significantly depends on the relative positioning of common edges. We evaluate three publicly available LLMs—Llama-3-8B, Llama-3-70B, and GPT-4—using various graph encoding techniques that represent graph structures for LLM input. We propose a formulation for the lost-in-distance phenomenon and demonstrate that lost-in-distance and lost-in-the middle phenomenas occur independently. Results indicate that model accuracy can decline by up to 6x as the distance between node connections increases, independent of graph encoding and model size.

## 1 Introduction

Large Language Models (LLMs) have attained an unprecedented level of generality by leveraging scale and attention-based architectures (Kaplan et al., ; Vaswani, ). These models exhibit remarkable, often superhuman, capabilities across a diverse range of tasks, including language translation, reading comprehension, and question answering (Costa-jussà et al., ; Sanh et al., ). Additionally, LLMs are increasingly serving as essential and flexible building blocks for various user-facing machine learning and artificial intelligence applications beyond traditional language processing domains, such as recommendation systems (Geng et al., ), graph-related tasks (Wang et al., ), knowledge bases (AlKhamissi et al., ; Petroni et al., ), and more. These applications highlight the versatility of LLMs but also expose new challenges in handling domain-specific data encoded as textual input.

Particularly, by leveraging the extensive common knowledge and powerful semantic comprehension abilities of LLMs, recent research has aimed to apply them to tasks related to graph structures (Wang et al., ). LLMs are increasingly being adopted for a variety of tasks that involve graph structures, such as planning in robotics (Andreas, ), knowledge extraction using knowledge graphs (Shen et al., ; Saxena et al., ), and multi-hop question answering (Creswell et al., ; Fang et al., ). For instance, they have been used to guide agents through structured graph-based environments (Huang et al., ). Building upon these applications, recent works by Sanford et al. (), Perozzi et al. (), and Agarwal et al. () have demonstrated that graph tasks can be encoded into textual formats that allow pre-trained LLMs to solve them as out-of-domain tasks. This innovative approach effectively transforms graph problems into a language that LLMs can understand and process.

While LLMs are being expanded in many applications, they suffer from certain blind spots that significantly affect their performance. In particular, how these models process information in their context and retrieve relevant data to solve the task at hand remains an active area of research (Kaddour et al., ). Understanding these limitations is crucial for extending context length (Gemini et al., ; Xu et al., ; Chen et al., ) and improving in-context learning (Zhou et al., ; Wei et al., ; An et al., ). Recent works have shown that the performance of LLMs depends on the location of information in their context. Primarily, Liu et al. () introduces the “lost-in-the-middle” phenomenon, where information placed in the middle of a prompt is less effectively utilized by the model compared to information at the beginning or end, resulting in significant performance degradation when the position of relevant information in the context changes.

Unlike these previous works which mainly focus on shortcomings of LLMs in NLP tasks, e.g. lost-in-the-middle, we focus on the deficiency of these models in tasks beyond natural language processing, specifically solving fundamental graph problems. This area is heavily under-explored and has wide practical applications (Perozzi et al., ; Colon-Hernandez et al., ; Xie et al., ). Since these tasks require understanding graph structure and relationship between objects, they provide us with great insights into model’s blind spots. Through our analysis, we provide insight that LLMs not only have blind spots regarding where information exists in the context, but their performance in solving complex tasks also depends on the *relative* position of information within the context.

Particularly, we look into Common Connection and Similarity tasks, which are the main algorithms used as the backbone of many applications such as molecular design (Tan et al., ; Xia et al., ), social network analysis (Gao et al., ), and recommendation systems (Li et al., ). For example, these tasks are the main algorithms in “user-user” and “user-item” recommendations in large industry recommendation products (Xie et al., ; Huang et al., ; Wu et al., ; Dai et al., ). These tasks not only require understanding of subgraph structures but also demand integration of information and reasoning across subgraphs. We demonstrate that strong, publicly available LLMs universally degrade in performance as when relevant pieces of information are distant from each other. Our analysis shows that this effect is present even when one controls for the effects absolute position of the relevant information in the context. To summarize

- •
For tasks that require cross-subgraph information lookup, such as identifying common connections or measuring similarity, model performance not only degrades due to the “lost-in-the-middle” effect based on the absolute positions but is also affected by the relative distance between pieces of information in the context—a phenomenon we term “lost-in-distance”. The further apart the information is, the more the model’s performance deteriorates.
- •
We demonstrate these shortcomings across different graph encoding algorithms and various publicly available LLMs such as Llama-3-8B, Llama-3-70B (Dubey et al., ) and GPT-4 (Achiam et al., ) indicating a universal limitation in current architectures.

Our findings suggest that current LLMs have inherent limitations in processing contextual information that is not sequentially localized or is widely dispersed within the input. This has significant implications for their application in domains that require complex reasoning over structured data, such as graph analysis.

### 1.1 Notations and Definitions

We define a graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$, where $\mathcal{V}=\{v_{1},v_{2},\dots,v_{n}\}$ and $\mathcal{E}$ represent the sets of nodes and edges, respectively. If nodes $v_{i}$ and $v_{j}$ are directly connected, we denote the edge between them as $e_{ij}\in\mathcal{E}$. The neighbors of node $v_{i}$ are defined as $\mathcal{N}(v_{i})=\{v_{k}\in\mathcal{V}\mid e_{ik}\in\mathcal{E}\}$. A subgraph associated with node $v_{i}$ is defined as $\mathcal{G}_{v_{i}}=(\{v_{i}\}\cup\mathcal{N}(v_{i}),\mathcal{E}_{v_{i}})$, where $\mathcal{E}_{v_{i}}=\{e_{ij}\mid e_{ij}\in\mathcal{E},\ v_{j}\in\mathcal{N}(v_
{i})\}$.

We define the distance between a common node $v$ within two subgraphs $\mathcal{G}_{u}$ and $\mathcal{G}_{z}$ as the number of tokens separating the two occurrences of node $v$ in the context (i.e., the textual representation of the subgraphs). The overall distance between relevant information for common connections between the two subgraphs is defined as the median of all such distances computed for each common node. Throughout the paper, we use $p$ to indicate position and $d$ to indicate distance.

We use accuracy, as defined below, to measure the performance of an LLM model in solving a given task:

$$ $\mathrm{Accuracy}=\frac{1}{N}\sum_{i=1}^{N}\mathbf{1}_{\{y_{i}=\hat{y}_{i}\}} \times 100\%,$ (1) $$

where $N$ is the total number of samples in the task, and $y_{i}$ and $\hat{y}_{i}$ denote the true answer and the model’s answer for the $i$th sample, respectively. If the output of the LLM for sample $i$ is degenerate—such as not following instructions or hallucinating—we consider it an incorrect answer, i.e., $y_{i}\neq\hat{y}_{i}$.

## 2 Graph Encoding and Graph Tasks

### 2.1 Graph Encoding for LLM

Representing graph-structured data as text is an important step in enabling LLMs to understand graph structures and provide accurate answers to questions. Encoding graphs as text involves representing both nodes and edges. Different graph encodings can lead to varying performance of LLMs in graph reasoning tasks (Agarwal et al., ; Fatemi et al., ; Zhang et al., ). In this work, we encode nodes as integers, where each node is represented by a unique integer, such that $v_{i}\in\{0,1,\dots,n-1\}$.

We experiment with three encoding functions from Fatemi et al. () to encode edges in the graph, investigating whether patterns are consistently observed across different encoding functions.
More specifically, we consider the following edge encoding functions:

- •
Incident: Given a source node $v_{i}$, the edge information for node $v_{i}$ is encoded as an adjacency list in natural language.
For example, “node $v_{i}$ is connected to nodes $v_{j},v_{k}$”.
- •
Adjacency: Given a source node $v_{i}$ and a target node $v_{j}$, the edge is encoded as $(v_{i},v_{j})$.
- •
Expert: Given a source node $v_{i}$ and a target node $v_{j}$, the edge is encoded as $v_{i}\rightarrow v_{j}$.

Since the graph tasks considered in this paper only require access to the subgraph and the subgraph structure, we encode only the edge information for the nodes of interest. This is a common practice where a subgraph is extracted from a database before being processed by a compute engine (Shao et al., ).
Figure 1 shows an example about only including a subgraph with three encoding functions in the prompt.
In this example, node 0 0 and node $1$ are nodes of interest so we only encode their subgraph in the prompt.

Figure: Figure 1: Three graph encoding functions, with node 0 0 and node $1$ serving as the nodes of interest. The figure is inspired by Fatemi et al. ().
Refer to caption: x1.png

### 2.2 Graph Generation

In this paper, we build upon previous studies (Huang et al., ; Fatemi et al., ; Zhang et al., ) by conducting experiments on randomly generated graphs. We utilize the Erdős–Rényi (ER) graph generator (Erdős & Rényi, ) to create undirected graphs. We experiment with relatively large graphs comprising $n=1000$ nodes. The undirected edge $e_{ij}$ between nodes $v_{i}$ and $v_{j}$ is generated with probability $P(e_{ij}\in{\mathcal{E}})$. We set $P(e_{ij}\in{\mathcal{E}})=0.1$ throughout the main manuscript, and results for other values of $P(e_{ij}\in{\mathcal{E}})$ are presented in the Appendix for brevity.

### 2.3 Graph Tasks

We aim to analyze the performance of LLMs in three fundamental graph problems which require models to have thorough understanding of the input graph structure.

- 1.
Edge Existence: Given two nodes $v_{i}$ and $v_{j}$ sampled from a graph ${\mathcal{G}}$, node $v_{i}$ and node $v_{j}$ are directly connected if $e_{ij}\in{\mathcal{E}}$.
The edge existence task is to ask LLMs whether node $v_{i}$ and node $v_{j}$ are directly connected.
- 2.
Common Connection: Given two nodes $v_{i}$ and $v_{j}$ sampled from a graph ${\mathcal{G}}$, the common connection between two nodes are ${\mathcal{N}}(v_{i})\cap{\mathcal{N}}(v_{j})$.
For this task, we ask LLMs to find the number of common connections between node $v_{i}$ and node $v_{j}$, denoted as $|{\mathcal{N}}(v_{i})\cap{\mathcal{N}}(v_{j})|$.
- 3.
Similarity: Given three nodes $v_{i}$, $v_{j}$ and $v_{k}$ sampled from a graph ${\mathcal{G}}$, we let $v_{j}$ be the source node and $v_{i}$ and $v_{k}$ be the target nodes.
The task for LLMs is to compare the number of common connections $|{\mathcal{N}}(v_{i})\cap{\mathcal{N}}(v_{j})|$ and $|{\mathcal{N}}(v_{j})\cap{\mathcal{N}}(v_{k})|$.

Note that these tasks are roughly ordered in terms of general complexity.
For example, solving the edge existence only depends on the model being able to retrieve the edge information from the representation. One step further, in finding the number of common connections, models needs to first identify the set of shared connections between two nodes and then calculate the size of that set. Finally, the similarity task is more complex than the common connection task, as it requires LLMs to consider *three* nodes and identify two sets of common connections and then compare their sizes.
As a result, these tasks are a good representative set to evaluate LLMs since they require LLMs to both retrieve and reason about the graph information. Furthermore, these tasks are also essential and the building blocks for solving practical problems in applications such as recommendation systems (Ying et al., ), protein folding (Strokach et al., ), bad actor detection (Papegnies et al., ) or any other task that requires graph understanding.

## 3 Lost-in-the-middle for Edge Existence

The edge existence task is analogous to the needle-in-a-haystack problem (Ivgi et al., ) and the document question-answering task (Liu et al., ), as it requires the LLM to retrieve the answer from the prompt without performing any computation. Building upon prior work in the literature by Liu et al. (), this study demonstrates the impact of the position of relevant information on the performance of LLMs. Specifically, it is shown that the accuracy in the edge existence task decreases when the information about the edge in question is placed in the middle of the prompt.

The prompt structure is constructed using the following procedure, which enables controlling the location of information within the prompt:

- 1.
Randomly sample two nodes from a graph along with their corresponding connections.
- 2.
Randomly select nine additional nodes as noise nodes and incorporate their textual subgraph encodings into the prompt. This step is necessary to examine the impact of the position of relevant information.
- 3.
Group the subgraph structures of the two nodes of interest and position them at the beginning, middle, or end of the input context.
- 4.
Query the model to determine whether an edge exists between the two nodes of interest.

An example of a prompt with different positions for the two nodes of interest is illustrated in Figure 2.

Figure: Figure 2: Example of the edge existence task, illustrating the placement of the nodes of interest subgraph (nodes $208$ and $358$) at (a) the beginning, (b) the middle, and (c) the end of the graph structure.
Refer to caption: x2.png

### 3.1 Experimental Results

Lost-in-the-middle can happen in the edge existence task.
To demonstrate the lost-in-the-middle phenomena in edge existence task, we experiment with the state of the art model as of writing this paper GPT-4. The experiment results are averaged over twenty randomly generated graph where from each graph we randomly select two nodes and form the edge existence prompt as described in previous section.

Figure 3 shows that all encodings can cause the LLM to lose the information in the middle of the prompt.
The best performance occurs when the relevant information is either at the beginning or the end of the entire subgraph structure.
Even for the incident encoding which has the best performance among all encodings, the LLM still has the worst performance when the answer is located in the middle of the prompt.

Figure: Figure 3: The effect of the position of the relevant information on the edge existence task.
Refer to caption: x3.png

## 4 Lost-in-Distance

Tasks such as the edge existence require LLMs to perform needle-in-a-haystack retrieval, which, as previously shown, suffers from the lost-in-the-middle phenomenon in long contexts. However, in many tasks, the model not only needs to look up relevant information in the context but also requires to perform cross-referencing between retrieved information. For example, tasks like the common connection require the model to retrieve connections that *jointly* appear in both subgraphs.

We hypothesize that for tasks requiring cross-referenced retrieval, the model’s performance is also impacted by the distance between relevant pieces of information, a phenomenon we term lost-in-distance. Specifically, for these tasks, the model’s performance is influenced by two compounding phenomena: lost-in-the-middle when retrieving relevant information and lost-in-distance when performing a join between retrieved information.

To explore this, we define $G(p)$ as the model’s performance when the relevant information is at position $p$. Similarly, we define $F(p_{1},p_{2})$ as the model’s performance when the relevant information is at positions $(p_{1},p_{2})$. The value of $F(p_{1},p_{2})$ is estimated based on the accuracy of model in a complex task that requires cross-referencing. We hypothesize that $F$ and $G$ have the following relationship:

$$ $F(p_{1},p_{2})=\gamma\,G(p_{1})\,G(p_{2})\,H(d),$ (2) $$

where $d=|p_{2}-p_{1}|$ represents the distance between relevant information in the prompt and $H(d)$ represents the effect of lost-in-distance.

In the experimental section, by studying LLM performance on common connection and similarity tasks, we first demonstrate that lost-in-the-middle alone cannot explain the model’s performance degradation in solving tasks that require joint reasoning across multiple subgraphs, and that it is affected by another factor, lost-in-distance. Then, by leveraging the experimental results, we measure the goodness of fit for Equation 2 in Section 6.

## 5 Experimentation

In our initial experiments, we focused on the common connection task. This task requires the model to determine the number of common connections between two nodes by joining information across two subgraphs. Our results demonstrate that the models’ performance degrades as the distance between the relevant pieces of information in the two subgraphs increases. Specifically, when the information about each node’s connections is placed further apart in the context, the models struggle to effectively retrieve and integrate this information to compute the correct number of common connections.

We then investigated how the lost-in-distance impacts tasks that require multiple cross-referencing steps, such as the similarity task. In the similarity task, the model needs to first identify the common connections between each of the two nodes and a reference node, and then compare these sets to determine the degree of similarity. Our findings reveal that performance degradation is even more pronounced in this case, as the task requires the model to perform multiple join operations over dispersed pieces of information within the context.

### 5.1 Experimental Setup

Leveraging in-context learning (Dong et al., ; Wei et al., ), we conducted experiments using both closed-source models (GPT-4) and open-source models (Llama-3-8B-Instruct and Llama-3-70B-Instruct). For all models, we set the decoding temperature to zero to ensure the generation of deterministic answers. In each sample, we randomly selected two or three nodes as the nodes of interest for the common connection and similarity tasks, respectively. We performed experiments on hundreds of thousands of randomly generated graphs to draw statistically significant conclusions regarding LLM behavior. The experimental results were then averaged across multiple samples.

### 5.2 Common Connection Task

In this section, we demonstrate the effect of increased distance on solving the common connection task. To create an input prompt for this task and to control the relative distance of relevant information (common neighbors), we use the following methodology:

- 1.
Sample two nodes from a given graph and extract their corresponding subgraphs.
- 2.
Within each subgraph, group the common connections.
- 3.
Within each subgraph, position the common connections at the beginning, middle, or end of the textual encoding of the subgraph.

The above recipe, specifically the grouping of relevant information into three positions—beginning, middle, and end (as illustrated in Figure 4 for adjacency encoding)—enables us to control the relative distance between common connections within the prompt. This allows us to investigate the effects on the model’s performance when the relative distance is small, medium, or large. We denote the positions of relevant information within the first and second subgraphs as $(p_{1},p_{2})$, where $p_{1}\in\{0,1,2\}$ and $p_{2}\in\{3,4,5\}$, respectively, for the sake of brevity.

Figure: Figure 4: An example illustrating the placement of relevant information, highlighted in blue and red, at different positions using the adjacency encoding function for the common connection task. Relevant information is grouped at positions 0 0, $1$, or $2$ within the first node’s (node $257$) subgraph and at positions $3$, $4$, or $5$ within the second node’s (node $462$) subgraph. The left plot depicts the smallest distance between relevant information, while the right plot shows the largest distance.
Refer to caption: x4.png

#### 5.2.1 Lost-in-Distance in Common Connection Task

The results presented in Figure 5 illustrate the impact of varying the positions of common edges within each subgraph (following the methodology outlined in the previous section) on the model’s performance in the common connection task. Unlike the edge existence task, the model’s performance is influenced not only by the lost-in-the-middle phenomenon but also by the relative distance between common connections.

With the position of relevant information fixed in one subgraph, we observe that the model’s performance degrades when the other subgraph is positioned closer to the middle of the prompt, influenced by the lost-in-the-middle phenomenon. For example, in adjacency encodings (Figure 5, middle plot), when the first node’s common connection is at position 0 0 (the beginning of the prompt), the model’s performance deteriorates from 40% to 20% as the second node’s common connection shifts from position $5$ (the end) to position $3$ (the middle). However, in contrast to the lost-in-the-middle phenomenon, Figure 5 demonstrates that across all three graph encodings, the model achieves optimal performance when relevant information is centrally located, with minimal distance between components at positions $(2,3)$. This illustrates the effect of lost-in-distance. Furthermore, when the first node’s common connection is at position $2$, the model’s accuracy drops by up to 50% as the second node’s common connection shifts from position $3$ (the middle of the prompt) to position $5$ (the end of the prompt), thereby increasing the distance between relevant information. These observations confirm that the lost-in-distance phenomenon and the lost-in-the-middle effect have independent, compounding effects on model performance, as hypothesized in Equation 2.

Figure: Figure 5: The effect of lost-in-distance on the common connection task. The number in each block is accuracy $\pm$ standard deviation.
Refer to caption: x5.png

### 5.3 Similarity Task

Solving the similarity between three nodes $v_{i}$, $v_{j}$, and $v_{k}$ requires the model to perform two common connection tasks, $|\mathcal{N}(v_{i})\cap\mathcal{N}(v_{j})|$ and $|\mathcal{N}(v_{j})\cap\mathcal{N}(v_{k})|$, and subsequently compare the results. As a result, the model needs to execute two cross-referencing operations between the subgraphs: one between $\mathcal{G}_{v_{i}}$ and $\mathcal{G}_{v_{j}}$, and the other between $\mathcal{G}_{v_{j}}$ and $\mathcal{G}_{v_{k}}$. Therefore, as we will demonstrate in this section, solving the similarity task inherently suffers from the lost-in-distance phenomenon.

To measure the effect of the lost-in-distance phenomenon, we select three nodes—$v_{i}$, $v_{j}$, and $v_{k}$—from a given graph and randomly shuffle the edges within each node’s subgraph. We designate $v_{j}$ as the source node for the similarity task, $v_{i}$ as the first target node, and $v_{k}$ as the second target node. In all scenarios, to mitigate the influence of the lost-in-the-middle effect and highlight the effect of lost-in-distance, the textual encoding of the source node $v_{j}$’s subgraph ($\mathcal{G}_{v_{j}}$) is positioned at the center of the prompt, while the subgraphs of the other two nodes are placed one before and one after it.

We quantify the lost-in-distance effect by calculating the median distance, measured in terms of tokens, between the common connections of the two subgraphs, specifically $|\mathcal{N}(v_{i})\cap\mathcal{N}(v_{j})|$ and $|\mathcal{N}(v_{j})\cap\mathcal{N}(v_{k})|$. The distance distribution is illustrated in Figure 6 for three different graph encodings. We utilize the thresholds presented in Table 1 to categorize the distances into small, medium, and large groups. Furthermore, in order to make sure more uniform coverage, we employ rejection sampling to ensure that each distance group contains one hundred samples with balanced responses.

**Table 1: Thresholds of each distance group for three graph encoding functions where distance is measured in number of tokens.**
| Graph Encoding | Small Distance | Medium Distance | Large Distance |
| --- | --- | --- | --- |
| Incident | $\leq 219$ | $219\sim 399$ | $>399$ |
| Adjacency | $\leq 425$ | $425\sim 785$ | $>785$ |
| Expert | $\leq 354$ | $354\sim 654$ | $>654$ |

Figure: Figure 6: The distribution of median distance, in number of tokens, for three graph encoding functions.
Refer to caption: x8.png

To eliminate potential biases, for the three subgraphs $\mathcal{G}_{v_{i}}$, $\mathcal{G}_{v_{j}}$, and $\mathcal{G}_{v_{k}}$, where $v_{j}$ is the source node for similarity, we generate questions randomly chosen from the following two templates:

- •
Is the number of common connections between node $\bm{v_{j}}$ and node $\bm{v_{k}}$ greater than the number of common connections between node $\bm{v_{i}}$ and node $\bm{v_{j}}$?
- •
Is the number of common connections between node $\bm{v_{i}}$ and node $\bm{v_{j}}$ greater than the number of common connections between node $\bm{v_{j}}$ and node $\bm{v_{k}}$?

An example of the prompt for the similarity task is presented in Appendix C.1. Since the similarity task inherently involves solving two common connection tasks and a comparison task, we adopt Chain-of-Thought prompting (Wei et al., ) to guide the model in solving the task step by step, thereby obtaining the most accurate answers. Detailed descriptions of the prompts and further analysis of the LLMs’ failure rates in following CoT instructions, along with examples of answer degeneration, are provided in Appendix A.2. GPT-4 and Llama-3-70B exhibit low failure rates, while Llama-3-8B demonstrates a high failure rate across all graph encodings, including a 69% failure rate in expert encodings.

#### 5.3.1 Lost-in-Distance in Similarity Task

For brevity, we present the results of one encoding for each model in Figure 7, with all results summarized in Appendix C.2. Our findings indicate that when both distances are minimal, GPT-4 and Llama-3-70B-Instruct exhibit the best performance. Llama-3-8B-Instruct, which has a high failure rate in following instructions as described in Appendix A.2, demonstrates the second-best performance, though it is not significantly different from the top performers.

Figure: Figure 7: The effect of lost-in-distance on the similarity task is illustrated. As the distance between target node 1 and target node 2 increases, the model’s performance degrades accordingly. The numbers in each block represent the accuracy $\pm$ standard deviation obtained through bootstrap sampling.
Refer to caption: x11.png

Specifically, performance at the largest distances is significantly worse compared to that at the smallest distances. As the distances increase (i.e., along the diagonal elements), the performance of all models deteriorates. In Llama-3-70B, we observe a 12% drop in model accuracy when the distance between common connections for both $|\mathcal{N}(v_{i})\cap\mathcal{N}(v_{j})|$ and $|\mathcal{N}(v_{j})\cap\mathcal{N}(v_{k})|$ increases, shifting from the $(\text{Small},\text{Small})$ index to the $(\text{Large},\text{Large})$ index in the heatmap plot. These results highlight that the lost-in-distance phenomenon adversely affects model performance in similarity tasks.

## 6 Goodness of Fit for Lost-in-Distance

In this section, we employ the Equation 2 function to capture the effects of the lost-in-distance phenomenon and to separate its impact from that of the lost-in-the-middle effect. To evaluate the goodness of fit for the lost-in-distance function defined in Equation 2, we compare it to a simpler function that accounts solely for the lost-in-the-middle effect as follows:

$$ $\mathbb{E}[F(p_{1},p_{2})|G(p_{1}),G(p_{2})]=\gamma G(p_{1})G(p_{2}),$ (3) $$

$$ $\mathbb{E}[F(p_{1},p_{2})|\gamma,G(p_{1}),G(p_{2})]=\gamma G(p_{1})G(p_{2})H(| p_{2}-p_{1}|),$ (4) $$

where $H(|p_{2}-p_{1}|))$ is the effect of lost-in-distance $d=|p_{2}-p_{1}|$.

To measure the goodness of fit we leverage results and output of common connection experiments but the result and findings here are extendable to similarity task as well. We randomly split samples into training and test sets of equal size. Using the training set, we first estimate $\hat{G}(\cdot)$ using interpolation based on the accuracy observed in the edge existence task. Then, we estimate $\gamma$ by regressing $F(p_{1},p_{2})$ onto $\hat{G}(p_{1})\hat{G}(p_{2})$. Finally, given the estimated $\hat{\gamma}$ and $\hat{G}(\cdot)$, we estimate $H(\cdot)$ using

$$ $\hat{H}(d)=\frac{1}{|{\mathcal{D}}_{d}|}\sum_{(p_{1},p_{2})\in{\mathcal{D}}_{d }}\frac{F(p_{1},p_{2})}{\hat{\gamma}\hat{G}(p_{1})\hat{G}(p_{2})},$ (5) $$

where ${\mathcal{D}}_{d}=\{(p_{1},p_{2})||p_{2}-p_{1}|=d\}$.

We evaluate the goodness of fit for both functions using the root mean squared error (RMSE) between the predicted and observed accuracy in the test set.

Table 2 shows that Equation 2 function, which includes the lost-in-distance effect, has a smaller RMSE compared to the lost-in-the-middle only function.
Moreover, $\hat{H}(\cdot)$ in Figure 8 indicates that smaller distance results in better performance, up to 3x, after accounting for the lost-in-the-middle effect.

Figure: Figure 8: The left plot is $\hat{G}(\cdot)$ and the right plot is $\hat{H}(\cdot)$. To better visualize the error bars in $\hat{H}(\cdot)$ estimation, we slightly shift the adjacency encoding to the left and the expert encoding to the right. Numbers in x-axis are normalized to the prompt length.
Refer to caption: x14.png

**Table 2: RMSE for lost-in-the-middle only and Equation 2 functions with three encodings.**
| Encoding | Model | RMSE (train) | RMSE (test) |
| --- | --- | --- | --- |
| Incident | Lost-in-the-middle only | 22.42 | 27.09 |
| Equation 2 | 10.04 | 14.50 |  |
| Adjacency | Lost-in-the-middle only | 21.43 | 22.36 |
| Equation 2 | 15.16 | 13.61 |  |
| Expert | Lost-in-the-middle only | 24.50 | 26.69 |
| Equation 2 | 12.84 | 17.42 |  |

## Appendix A Analysis

### A.1 Context Length

Table 3 summarizes the average context length (i.e., the number of tokens) for each task and each graph encoding. We use the tokenizer of Llama-3 to calculate the context length for Llama-3-8B-Instruct and Llama-3-70B-Instruct and use the tiktoken library (OpenAI, ) to calculate the context length for GPT-4 and GPT-4o. The incident encoding produces the shortest context length, while the adjacency encoding results in the longest context length.

**Table 3: Input and output context length in each encoding and each task.**
| Graph Task | Graph Encoding | Average Input Length | Average Output Length |  |  |
| --- | --- | --- | --- | --- | --- |
| GPT-4/4o | Llama-3-8B-Instruct | Llama-3-70B-Instruct |  |  |  |
| Edge Existence | Incident | 3409.50 | 13 | 8 | 7 |
| Adjacency | 6598.10 | 13 | 8 | 7 |  |
| Expert | 5514.75 | 13 | 8 | 7 |  |
| Common Connection | Incident | 662.55 | 13 | 8 | 7 |
| Adjacency | 1261.10 | 13 | 8 | 7 |  |
| Expert | 1068.25 | 13 | 8 | 7 |  |
| Similarity | Incident | 1263.37 | 153.46 | 695.31 | 91.76 |
| Adjacency | 2164.75 | 142.32 | 1126.30 | 106.86 |  |
| Expert | 1869.29 | 140.34 | 1453.97 | 97.73 |  |

### A.2 Answer degeneration

LLMs sometimes fail to follow instructions and generate responses that do not adhere to the expected output template. We classify these degenerate responses as incorrect answers, i.e., $y_{i}\neq\hat{y}_{i}$ for accuracy calculation in Equation 1. Llama-3-8B-Instruct is less likely to generate a final answer compared to GPT-4o and Llama-3-70B-Instruct, which explains why it has lowest accuracy in Figure 7. Table 4 summarizes the percentage of samples in which models fail to follow instructions. Generally, the most common patterns of degenerate answers are as follows:

- •
Repetition: LLMs sometimes repeat the same context until they reach the maximum number of output tokens, thereby failing to generate a final answer.
- •
Self-contradiction: In CoT prompting, LLMs are asked to answer the main question based on their responses to subquestions. However, we find that LLMs sometimes provide an incorrect final conclusion. For example, as shown in Figure 9 where we ask the LLM “is the number of common connections between node 658 and node 535 greater than the number of common connections between node 535 and node 807?”, the LLM determines that the number of common connections between node $658$ and node $535$ is $6$, and between node $535$ and node $807$ is $4$, but the final answer is “no” when it should be “yes”.

**Table 4: Percentage of samples where each model generates degenerated answer.**
| Graph Encoding | Percentage of not generating the answer |  |  |
| --- | --- | --- | --- |
| GPT-4o | Llama-3-8B-Instruct | Llama-3-70B-Instruct |  |
| Incident | $0.78$% | $18.78$% | $0.11$% |
| Adjacency | $4.11$% | $61.11$% | $0.22$% |
| Expert | $4.44$% | $69.00$% | $0.22$% |

Figure: Figure 9: Example where the answer is self-contradictory. The question in this example is that “is the number of common connections between node 658 and node 535 greater than the number of common connections between node 535 and node 807?”.
Refer to caption: x15.png

## Appendix B Common Connection: More result

Figure 10 illustrates the impact of the lost-in-distance phenomenon on the GPT-4o model (OpenAI, ) in solving the common connection task. Although the accuracy metrics slightly differ from those in Figure 5 for GPT-4, the pattern of the lost-in-distance effect remains consistent.

Figure: Figure 10: The effect of the position of the relevant information on the GPT-4o model solving the common connection task.
Refer to caption: x16.png

## Appendix C Similarity Task

### C.1 Prompt Example

Figure 11 illustrates an example of the similarity task prompt, as described in Section 5.3, along with GPT-4o’s answer for solving the similarity task using incident graph encoding.

Figure: Figure 11: Example of the CoT prompting for the similarity task.
Refer to caption: x19.png

### C.2 All results

Figure 12 presents the results of the similarity task at a density of 0.1 across three models (GPT-4o, Llama-8B, Llama-70B) and three different graph encodings. For all models utilizing the graph encoding functions, we observe the typical lost-in-distance pattern, where performance at the $(\mathrm{Small},\mathrm{Small})$ index is better than at the $(\mathrm{Large},\mathrm{Large})$ index.

Figure: Figure 12: All results in the similarity task with density = 0.1.
Refer to caption: x20.png

## Appendix D Effect of Graph Density

The lost-in-distance effect remains consistent across different graph densities, i.e., different values of $P(e_{ij}\in{\mathcal{E}})$ in Erdős–Rényi (ER) randomly generated graphs. Graph density affects the input sequence length in a linear manner; higher densities result in proportionally longer input sequences, as demonstrated in Table 5.

Figure 13 illustrates that increasing the context length by raising graph density follows the same pattern of the lost-in-distance effect in similarity tasks. Specifically, accuracy declines progressively from top to bottom and left to right as the distances between common edges within each subgraph increase. Additionally, the figure demonstrates that for smaller context lengths, corresponding to graphs with low density, the results are noisier and the effect of lost-in-distance diminishes.

**Table 5: Average Token Length from different Graph Density, $P(e_{ij}\in{\mathcal{E}})$, for ER graphs using expert encoding**
| Graph Density | Average Token Length |
| --- | --- |
| 0.05 | 1145 |
| 0.10 | 1869 |
| 0.15 | 2633 |

Figure: Figure 13: Results from similarity tasks with three different density values, $P(e_{ij}\in{\mathcal{E}})$, (left) 0.05 , (middle) 0.1, and (right) 0.15.
Refer to caption: x29.png

## Peer Reviews

confidence: 5
contribution: 2
initial_rating: 3
presentation: 2
questions: 1. Given the identified “lost-in-distance” phenomenon, are there any potential strategies the authors would recommend for mitigating this effect?
2. The study uses multiple graph encoding techniques but does not deeply analyze the role of each encoding in mitigating or amplifying the “lost-in-distance” effect.  Could the authors elaborate on whether certain encoding styles are more effective in handling context separation?
soundness: 2
strengths: 1.	The paper introduces the novel concept of "lost-in-distance," highlighting a previously unexamined limitation of LLMs in handling graph-structured information when relevant context is distributed over greater distances. 
2.	By identifying the limitations of LLMs in processing complex, dispersed contextual information, the findings have broad implications for future LLM deployment in structured data scenarios.
summary: The paper investigates the limitations of large language models (LLMs) in processing graph-structured information when relevant context is distributed over larger distances within input sequences. The authors introduce the “lost-in-distance” phenomenon, demonstrating that LLM accuracy in graph tasks such as identifying common connections or assessing similarity between nodes declines significantly as the contextual distance between relevant nodes increases. Evaluations across LLMs reveal a universal decline in performance, independent of model size and graph encoding techniques, indicating inherent limitations in current LLM architectures for complex graph reasoning.
weaknesses: 1.	I believe the contributions of this work are limited.  The authors explore the impact of contextual positioning on LLMs within graph tasks.  However, numerous studies have already shown how context position and order affect LLMs' general generative capabilities in in-context learning (ICL).  The findings observed in this work appear consistent with these prior studies, simply applied to a specific task, and lack innovative setups or contributions.
2.	Furthermore, the authors focus on tasks like identifying common connections or assessing similarity between nodes, which limits the generality of the findings. A broader range of tasks should be considered. It’s worth noting that the effects of more general graph descriptive order on graph tasks have already been explored [1]. In contrast, this paper feels more like an experimental report on the impact of a specific descriptive order within a narrowly defined set of tasks in the graph domain.
[1] Ge Y et al. Can Graph Descriptive Order Affect Solving Graph Problems with LLMs?

---

confidence: 5
contribution: 2
initial_rating: 3
presentation: 1
questions: - Does the calculation of the accuracies reported using Llama 3 8B take into account the high failure rate?
- Why did the authors choose to explore “lost-in-distance” only within the context of graphs?
- For each experiment, how many graphs did you evaluate on? How were the accuracies that the authors reported calculated?
- Why did the authors choose to define CoT prompting as decomposing the problem into subquestions instead of how CoT prompting is originally defined in Wei et al, 2022.? 
- What was the baseline level of performance on the Similarity task without the use of subquestions?
- How often did both the Repetition and Self-Contradiction patterns occur?
soundness: 1
strengths: - The concept of lost-in-distance is interesting, and is a significant-enough phenomenon worth exploring within the context of evaluating the reasoning abilities of LLMs.
summary: The paper’s central claim is that LLMs’ performance on graph tasks that involves cross-referencing is influenced not only by absolute positioning of relevant information in the context (“lost-in-the-middle”), but by the relative distance between relevant information within the prompt. The authors term this phenomenon “lost-in-distance”. The authors first validate the lost-in-the-middle phenomenon in the graph setting using the Edge Existence task, and show that model performance decreases when relevant information is close to the middle of the prompt. The authors then address lost-in-distance using two more graph tasks: Common Connection and Similarity. The authors claim that results on the Common Connection task demonstrate models’ performance degradation as the distance between the relevant pieces of information in the two subgraphs increases. The authors also claim that a similar pattern of performance degradation can be seen in the Similarity task, where the model must compare connections across three nodes. Finally, the authors capture the effects of lost-in-distance by evaluating the goodness of fit of two proposed functions, comparing their ability to explain observed performance degradation.
weaknesses: === Related Work and Conclusion === 
- The paper is incomplete due to the absence of related work and conclusion sections, which significantly limits the depth of analysis and hinders reader understanding. Without a related works section, readers are unable to properly contextualize the contributions of this paper relative to any prior work. The lack of a conclusion prevents readers from grasping the overall implications and the scope of potential future research directions.

=== Methodology & Analysis ===
- The crucial concept behind lost-in-distance is that model performance on cross-referencing tasks is impacted by the relative distance between relevant information in the prompt. However, this could apply to many other settings beyond graphs. If the authors show similar patterns in non-graph contexts, like in previously studied “needle-in-a-haystack” papers, it’ll strengthen their claims’ generalizability and impact.
- The authors mention that they “performed experiments on hundreds of thousands of randomly generated graphs to draw statistically significant conclusions regarding LLM behavior”. However, the exact number of graphs used in each experiment is unclear. The results in Figure 5 suggest that the number of graphs used in the Common Connection task is very small, raising concerns about the transparency and robustness of the results.
- For the Similarity task, the authors mention that their “findings indicate that when both distances are minimal, GPT4 and Llama-3-70B-Instruct exhibit the best performance.” However, Figure 12 contradicts this: in four out of six experiments, optimal performance was achieved at non-minimal distances (Small-Small). Therefore, this claim appears inconsistent with their results, and a direct comment/explanation on this from the authors would highly advisable.
- The authors demonstrate the high failure rate of Llama 3 8B, and therefore the analysis of these results, as well as the comparison of them to GPT-4 and Llama 3 70B, is highly limited. Including more SOTA LLMs that have lower failure rates, potentially including models in the Llama 3.1 family, would make the claims made by this paper, as well as inter-model comparison, stronger.
- The authors point out the limitations of models on these tasks, but do not attempt/suggest any potential improvements, such as in-context learning. On the subject of in-context learning, the authors mention that they “adopt Chain-of-Thought prompting (Wei et al., 2022) to guide the model in solving the task step by step”. According to Wei et al., 2022, CoT prompting involves placing in-context examples in the prompt with guided solutions. However, in Figure 11, the authors define CoT prompting as breaking the problem into subquestions. Why did the authors choose to define CoT prompting in this way? In addition, what was the baseline level of performance on the Similarity task without the use of subquestions?
- In Section A.2, the authors mention Repetition and Self-Contradiction as the two “most common patterns of degenerate answers”. It would be helpful to report how often both patterns occur, similarly to Table 4, as this would add clarity on the prevalence of these errors.

---

confidence: 3
contribution: 2
initial_rating: 3
presentation: 2
questions: My primary concerns have been addressed in the **"Weaknesses"** section.  Minor questions:

* The most common representations of graphs are linked lists or adjacency dictionaries. I am confused about the "expert" encoding shown in Figure 1 and the partial explanation of this encoding in Line 131.

* What is the exact number of samples tested in Section 5.1? The authors only mention "hundreds of thousands of randomly generated graphs" in Line 311.
soundness: 2
strengths: This paper **studies an important yet unexplored research question**: How does LLMs' performance change when relevant information is given in different positions within the query? 

Personally, I believe understanding this problem can reveal insights into LLMs' reasoning mechanism for graph tasks, unlocking their potentials to tackle graph-related tasks more intelligently.
summary: Motivated by the prevalent phenomenon "lost-in-the-middle" of LLMs solving general tasks, this paper investigates how LLM performance changes for graph tasks when relevant information is positioned differently ("lost-in-middle"), and when pieces of relevant information are provided at varying distances ("lost-in-distance"). Focusing on Edge Existence, Common Connection, and Similarity tasks, the empirical findings demonstrate that LLMs do exhibit the lost-in-distance, and that changing the position of relevant information can significantly enhance performance.
weaknesses: This paper is more like an experimental report than a research paper. I will elaborate on my opinion as follows:

1. The primary focus of this paper is to reveal that LLMs' performance on graph tasks is significantly influenced by the positioning of relevant information in the query and the distance between relevant pieces of information. However, **some conclusions are weakened by limited empirical investigations**:
   * (a) The experimented LLMs are limited, e.g., for showing "lost-in-the-middle" effect, only GPT-4 is considered. 
   * (b) The number of tested samples is limited, e.g., only 20 cases for "lost-in-the-middle", and an unspecified number for remaining experiments.
   * (c) Lack of evaluation on existing graph reasoning benchmarks [1, 2], and the synthesized data is overly simplistic, e.g., only 9 additional noisy nodes for "lost-in-the-middle".

2. The authors primarily present preliminary empirical findings **without providing more in-depth research**, such as theoretical analysis or effective methods for LLMs to address these shortcomings (e.g., how to overcome inconsistent performance and improve accuracy when relevant information is presented at a long distance).

3. Lack of discussion about preliminary research on LLMs' inconsistent performance related to graph representation [3].

4. The considered graph tasks are also limited. While the authors claim that Common Connection and Similarity are fundamental graph tasks, I struggle to identify direct application scenarios for these tasks. Additionally, existing research on LLMs solving basic graph reasoning tasks [1, 2] does not include these types, focusing instead on tasks like the shortest path. I believe that the shortest path is a type of graph task that requires specific pieces of information, i.e., the source and target nodes. Enriching this type of task could further highlight the inherent limitations of LLMs in solving graph problems.

--- 

[1] Chen, Nuo et al. "GraphWiz: An Instruction-Following Language Model for Graph Problems." In KDD, 2024.

[2] Luo, Zihan, et al. "GraphInstruct: Empowering Large Language Models with Graph Understanding and Reasoning Capability." In arXiv preprint, 2024.

[3] Ge, Yuyao, et al. "Can Graph Descriptive Order Affect Solving Graph Problems with LLMs?" In arXiv preprint, 2024.

---

confidence: 4
contribution: 1
initial_rating: 3
presentation: 2
questions: Does the "lost-in-distance" phenomenon appear in real-world application scenarios, such as knowledge graph question answering or recommender systems? Are there any experiments that provide evidence for this?
soundness: 2
strengths: 1. The problem in this paper is novel, introducing the concept of "lost-in-distance" in the context of LLMs working on complex graph tasks. This perspective offers an innovative angle on understanding LLM performance.
2. The study includes experiments on both closed-source and open-source models, enhancing the robustness of the findings. The authors utilize three different encoding functions to transform graph data into text formats suitable for LLM processing, showcasing a comprehensive approach to graph encoding.
summary: This paper explores a notable phenomenon in LLMs regarding their performance on complex graph tasks, specifically how effectiveness decreases as the distance between relevant contextual information increases. The authors introduce the concept of "lost-in-distance," investigating two fundamental graph tasks: identifying common connections between two nodes and assessing similarity among three nodes. The study conducts experiments on three publicly available LLMs, utilizing various graph encoding techniques to represent graph structures.
weaknesses: 1. The problem investigated in this paper may not be a critical aspect of LLM reasoning processes. There are already several methods that can significantly enhance LLMs' reasoning capabilities for complex graph-related problems; however, the authors do not discuss these important related works, such as methods for improving LLMs' inference capabilities on knowledge graphs [1] and Graph Retrieval-Augmented Generation [2].
2. The authors do not provide an in-depth theoretical analysis of why LLMs exhibit the lost-in-distance phenomenon in complex graph tasks. 
3. The paper identifies a pertinent issue but does not provide corresponding solutions or model innovations. It lacks a discussion of potential measures or strategies to address this phenomenon, which could have significantly enhanced the overall contribution of the research.
4. I do not believe this paper is complete; it lacks a thorough discussion of related work and does not provide a conclusion section. 

[1] Sun J, Xu C, Tang L, et al. Think-on-graph: Deep and responsible reasoning of large language model with knowledge graph[J]. arXiv preprint arXiv:2307.07697, 2023.
[2] Edge D, Trinh H, Cheng N, et al. From local to global: A graph rag approach to query-focused summarization[J]. arXiv preprint arXiv:2404.16130, 2024.

Meta-review: Reviewers generally agree that the paper studies an important and novel problem, where the concept of 'lost-in-distance' provides useful insights in examining the limitations of LLMs. 

However, the paper appears to be incomplete: lacking a thorough review of related work; no conclusion section; empirical results are limited to a narrowly defined set of tasks; the paper only presents the phenomenon, but lacks a discussion of potential measures or strategies to address it.

Decision: Reject