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

arXiv: https://arxiv.org/abs/2410.01985 · HTML: https://mlsanity.com/paper/2410.01985/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 37 of its 48 references that are in the map.
- First posted on arXiv 2 Oct 2024.

## Builds on (most cited first, 30 of 37)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [GPT-4 Technical Report](https://mlsanity.com/paper/2303.08774/) (2023)
- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [Chain-of-Thought Prompting Elicits Reasoning in Large Language Models](https://mlsanity.com/paper/2201.11903/) (2022)
- [Scaling Laws for Neural Language Models](https://mlsanity.com/paper/2001.08361/) (2020)
- [Lost in the Middle: How Language Models Use Long Contexts](https://mlsanity.com/paper/2307.03172/) (2023)
- [Language Models as Knowledge Bases?](https://mlsanity.com/paper/1909.01066/) (2019)
- [Multitask Prompted Training Enables Zero-Shot Task Generalization](https://mlsanity.com/paper/2110.08207/) (2021)
- [No Language Left Behind: Scaling Human-Centered Machine Translation](https://mlsanity.com/paper/2207.04672/) (2022)
- [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (2018)
- [Large Language Models Are Human-Level Prompt Engineers](https://mlsanity.com/paper/2211.01910/) (2022)
- [Language Models as Zero-Shot Planners: Extracting Actionable Knowledge for Embodied Agents](https://mlsanity.com/paper/2201.07207/) (2022)
- [Extending Context Window of Large Language Models via Positional Interpolation](https://mlsanity.com/paper/2306.15595/) (2023)
- [Graph Neural Networks in Recommender Systems: A Survey](https://mlsanity.com/paper/2011.02260/) (2020)
- [Recommendation as Language Processing (RLP): A Unified Pretrain, Personalized Prompt & Predict Paradigm (P5)](https://mlsanity.com/paper/2203.13366/) (2022)
- [Larger language models do in-context learning differently](https://mlsanity.com/paper/2303.03846/) (2023)
- [Selection-Inference: Exploiting Large Language Models for Interpretable Logical Reasoning](https://mlsanity.com/paper/2205.09712/) (2022)
- [Challenges and Applications of Large Language Models](https://mlsanity.com/paper/2307.10169/) (2023)
- [Can Language Models Solve Graph Problems in Natural Language?](https://mlsanity.com/paper/2305.10037/) (2023)
- [Talk like a Graph: Encoding Graphs for Large Language Models](https://mlsanity.com/paper/2310.04560/) (2023)
- [A Review on Language Models as Knowledge Bases](https://mlsanity.com/paper/2204.06031/) (2022)
- [Language Models as Agent Models](https://mlsanity.com/paper/2212.01681/) (2022)
- [Make Your LLM Fully Utilize the Context](https://mlsanity.com/paper/2404.16811/) (2024)
- [Let Your Graph Do the Talking: Encoding Structured Data for LLMs](https://mlsanity.com/paper/2402.05862/) (2024)
- [Retrieval meets Long Context Large Language Models](https://mlsanity.com/paper/2310.03025/) (2023)
- [Hierarchical Graph Network for Multi-hop Question Answering](https://mlsanity.com/paper/1911.03631/) (2019)
- [Efficient Long-Text Understanding with Short-Text Models](https://mlsanity.com/paper/2208.00748/) (2022)
- [Understanding Transformer Reasoning Capabilities via Graph Algorithms](https://mlsanity.com/paper/2405.18512/) (2024)
- [GraphTranslator: Aligning Graph Model to Large Language Model for Open-ended Tasks](https://mlsanity.com/paper/2402.07197/) (2024)
- [LLM4DyG: Can Large Language Models Solve Spatial-Temporal Problems on Dynamic Graphs?](https://mlsanity.com/paper/2310.17110/) (2023)

## Built on by (most cited first, 8 of 8)

- [PathRAG: Pruning Graph-based Retrieval Augmented Generation with Relational Paths](https://mlsanity.com/paper/2502.14902/) (2025)
- [GraphThought: Graph Combinatorial Optimization with Thought Generation](https://mlsanity.com/paper/2502.11607/) (2025)
- [Masks Can Be Distracting: On Context Comprehension in Diffusion Language Models](https://mlsanity.com/paper/2511.21338/) (2025)
- [Court of LLMs: Evidence-Augmented Generation via Multi-LLM Collaboration for Text-Attributed Graph Anomaly Detection](https://mlsanity.com/paper/2508.00507/) (2025)
- [Glance for Context: Learning When to Leverage LLMs for Node-Aware GNN-LLM Fusion](https://mlsanity.com/paper/2510.10849/) (2025)
- [NoteEx: Interactive Visual Context Manipulation for LLM-Assisted Exploratory Data Analysis in Computational Notebooks](https://mlsanity.com/paper/2511.07223/) (2025)
- [Formalizing and Mitigating Structural Distortion in LLM Attention for Graph Reasoning](https://mlsanity.com/paper/2606.15633/) (2026)
- [GTA: Graph Theory Agent and Benchmark for Algorithmic Graph Reasoning with LLMs](https://mlsanity.com/paper/2609.12265/) (2026)

## Abstract (arXiv)

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 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.