Needle Threading: Can LLMs Follow Threads Through Near-Million-Scale Haystacks?

Authors: Jonathan Roberts, Kai Han, Samuel Albanie
Primary area: other topics in machine learning (i.e., none of the above)
Keywords: LLMs, Long Context, Evaluation

Abstract:
As the context limits of Large Language Models (LLMs) increase, the range of
possible applications and downstream functions broadens. In many real-world
tasks, decisions depend on details scattered across collections of often disparate
documents containing mostly irrelevant information. Long-context LLMs appear
well-suited to this form of complex information retrieval and reasoning, which has
traditionally proven costly and time-consuming. However, although the development of longer context models has seen rapid gains in recent years, our understanding of how effectively LLMs use their context has not kept pace. To address
this, we conduct a set of retrieval experiments designed to evaluate the capabilities
of 17 leading LLMs, such as their ability to follow threads of information through
the context window. Strikingly, we find that many models are remarkably thread-
safe: capable of simultaneously following multiple threads without significant loss
in performance. Still, for many models, we find the effective context limit is significantly shorter than the supported context length, with accuracy decreasing as
the context window grows. Our study also highlights the important point that token counts from different tokenizers should not be directly compared—they often
correspond to substantially different numbers of written characters. We release
our code and long context experimental data.

Decision: accept (poster)
Reviewer scores: 6, 5, 6, 8

Reviews and discussion:
<thread>
creation date:
1729805039439

thread_type:
official_review

<thread_object>
creator: reviewer_wcwb

<content>
summary:
This paper executed a set of experiments to evaluate the capabilities of 17 LLMs to perform retrieval tasks with long contexts. It introduces challenging multi-step threading and multi-threading retrieval tasks to test the models' ability to track information through extended contexts. The results show that increased context length reduces retrieval performance, with accuracy generally decreasing as the context window grows. The authors also demonstrate that many leading LLMs are thread-safe. Additionally, they highlight significant differences in token counts across different tokenizers.

strengths:
(1) This paper studies an important aspect of LLMs -- their ability to manage long contexts -- which hasn't been fully explored yet.

(2) The paper is well-written.

(3) The task designs are comprehensive and insightful, especially the comparison between forward and backward threading.

(4) The experiments are extensive, and the results provide valuable insights into LLM performance with long contexts.

weaknesses:
(1) Code and data are not currently shared.

(2) The experiments in the paper rely on abstract retrieval tasks using synthetic data. These tasks can not reflect the complexity found in real-world, domain-specific applications. In practice, data often includes ambiguous language, diverse formats, and contextually relevant nuances. Moreover, the experiment design cannot test the model's ability to understand semantics.

questions:
Given that the experiments rely on synthetic, abstract tasks, how do you anticipate the performance trends observed in your study would translate to real-world, domain-specific applications with more complex and noisy data?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730361651219

thread_type:
official_review

<thread_object>
creator: reviewer_bszq

<content>
summary:
This paper investigates the ability of Large Language Models (LLMs) to handle complex information retrieval and reasoning tasks across long contexts. The authors conduct a series of retrieval experiments with 17 leading LLMs to assess their capability to follow information threads within extensive context windows, revealing that while many models can manage multiple threads without significant performance loss, their effective context limits are often shorter than their technical limits. The study also emphasizes the variability in token counts between different tokenizers, which affects model performance comparisons. A key contribution is the introduction of a task-specific effective context limit metric, which provides a more nuanced understanding of model capabilities in long-context scenarios.

strengths:
1. This paper provides an extensive evaluation of 17 leading LLMs across various long-context retrieval tasks, offering a thorough analysis of their performance in handling complex information retrieval and reasoning.

2. Through innovative needle threading and multi-threading experiments, the study creates scenarios where LLMs must follow chains of information across different parts of the context, effectively testing their limits in long-context understanding.

3. Analysis reveals significant differences in tokenization between models, crucial for understanding the discrepancies in reported context lengths and making accurate comparisons between LLMs.

4. The authors propose a task-specific and configurable metric independent of tokenization, enabling more precise assessment of models' reasoning capabilities over context.

weaknesses:
1. The study's exclusive use of synthetic data (UUID key-value pairs) may not accurately reflect performance on natural language tasks or domain-specific applications.

2. The paper may be limited in techinical contribution.

questions:
1. Have you considered conducting smaller-scale validation experiments with natural language data to verify if the findings generalize?

2. For the branched threading task, why was it only evaluated on a subset of models and smaller context sizes?
</content>
</thread_object>

</thread>
<thread>
creation date:
1731056806489

thread_type:
official_review

<thread_object>
creator: reviewer_n6xp

<content>
summary:
The paper evaluates the performance of Large Language Models (LLMs) as their context limits increase, focusing on their ability to handle complex information retrieval across multiple documents. Through experiments with 17 leading LLMs, the study finds that while many models effectively manage multiple threads of information, their actual efficient context range is often shorter than their maximum allowed, leading to reduced performance as the context window expands. The research also highlights inconsistencies in token counts across different tokenizers. Results and methodologies are made available for further study.

strengths:
Note: This is a review by an emergency reviewer. 

The paper addresses an intriguing and valuable research problem by exploring the utility of synthetic data for abstract tasks in the context of long-sequence processing.

Introducing multi-threading tasks as part of the experimental setup is particularly innovative. 

The findings of the paper offer practical insights that could inform both the academic and industry sectors about the design and tuning of language models for specific applications.

weaknesses:
Note: This is a review by an emergency reviewer. 

The major concern is that there's a gap between experimental design and real-world applications. The study employs highly abstract tasks using synthetic data with no natural language semantics, deviating considerably from the typical environments where large language models (LLMs) operate. The string-serialized JSON objects and UUIDs as key-value pairs fail to engage the models in natural language processing—core to their training and operational objectives. Consequently, the findings have limited applicability to real-world scenarios that demand comprehension, generation, and manipulation of actual linguistic content. This gap undermines the relevance of the research to practical applications of LLMs, which are primarily designed to interact with and generate coherent, contextually appropriate natural language.

The authors mention that they have released their code and experimental data for public use. However, the authors didn't upload supplemental materials to the open review nor include an anonymous link of their data and code. I would suggest sharing the code through an anonymous GitHub repository or similar platform. This would greatly aid other researchers and reviewers in replicating and understanding the research.

questions:
Please refer to the previous section
</content>
</thread_object>

</thread>
<thread>
creation date:
1731567417213

thread_type:
official_review

<thread_object>
creator: reviewer_q7cu

<content>
summary:
In this paper, the authors introduce simple single-needle retrieval, multiple-needle and conditional-needle retrieval and challenging needle threading and multithreading retrieval. Experiments on haystacks consisting of key-value pairs of UUIDs shows the retrieval precisions of 17 LLMs vary on different context lengths, multiple-needle and multiple threading conditions.

strengths:
The paper focuses on an interesting problem: how effectively LLMs use their context. 
The observations from the experiments are inspiring, for example, many models are remarkably thread-safe: capable of simultaneously following multiple threads without significant loss.

weaknesses:
Only one synthetic dataset is used for evaluation.

questions:
What is the time complexity (running/response time) of each LLM that is used for evaluation in different experiment settings?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732358444519

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Initial response to reviewers

comment:
We thank the reviewers for their insightful comments, positive responses, and time spent reviewing our paper. We are glad the reviewers found our paper to focus on an interesting (Q7CU) and intriguing (n6xp) problem with innovative experiments (bsZQ) and task designs that are comprehensive and insightful (wcWb).
 
Here, we address the weaknesses and questions raised in your reviews. **EDIT**: We have uploaded a Rebuttal Revision PDF of our paper with an additional ‘Rebuttal Figures’ section at the start of the Appendix (Page 14) containing some figures related to our rebuttal. Note, for the final version, we will incorporate any changes into the main paper and appendix, ensuring the total length is within the 10-page limit.



**Use of abstract/synthetic data & applicability to real-world natural language scenarios (Q7CU, n6xp, bsZQ, wcWB):**

Thank you for raising this important point. As mentioned in our paper, focusing our evaluation on abstract and synthetically generated scenarios has benefits of enabling fine-grained control and high-quality noise-free generation without potentially expensive annotation. Additionally, the likelihood of data contamination is significantly reduced and we can be confident – especially given the unique nature of UUIDs – that our tasks cannot be performed via memorisation. 

However, we concur that there is a gap between our experimental design and real-world applications. To address this, we have carried out a series of natural-language experiments. We focus on the threading and multi-threading tasks as these arguably had the most interesting takeaways. Concretely, we took The History of the Decline and Fall of the Roman Empire book, by Edward Gibbon (see Fig. 1 of our paper) as our “distractor” text. We chose a sentence in the text as a proxy for a UUID pair in the abstract task. Then, we prompted OpenAI’s o1-preview model to provide a list of plausible yet fictional Roman events (that aren’t included in the text). Using these events, we constructed ‘threads’ in the form of linked sentences: 
Sentence 1: ‘Event A and then Event B.’,...
Sentence 2: ‘Event B and then Event C.’,... and so on. 
And replaced sentences in the text with these thread sentences.

Thus, we have a natural language text containing linked information that is *in distribution* with the rest of the text. This serves as a natural language proxy for our abstract threading tasks.

*Single Threading results:*

We repeated the threading task in this new setting by evaluating models on haystacks from 1k to 630k token context lengths with threads from 2-25 steps in length. Please refer to Fig. 14 in the rebuttal revision pdf for selected heatmaps for threads travelling in the forward and backward directions. As in the abstract setting (Fig. 10), following threads in the natural language text proves challenging for the models, with similar poorer performance observed at longer contexts. The preference towards forward travelling threads is clearly also apparent from the heatmaps in this setting. We will update the final paper with these observations.

*Multi-threading results:*

We conducted multi-threading experiments in the natural language setting using the same approach as the Single Threading experiments above (this time with additional simultaneous threads). We present results for the Thread-Safe experiments repeated in the natural language setting in Figs. 15 and 16 in the rebuttal revision pdf. Each point represents an average over 5 repeats retrieving threads with a length of 3 in 20k LLaMA 3.1 token haystacks. For Fig. 15, threads are randomly-directed whereas for Fig. 16 they are all forward-directed. Unlike the Single Threading experiments – for which the results and insights were largely the same across the abstract and natural text settings – the Multi-threading task in the natural language setting proved much more challenging for the models. Moreover, we find the task to be challenging when retrieving multiple threads that are all forward or all randomly directed. Similar results were obtained when repeating this experiment on smaller haystacks and chain lengths of 2. Thus, our study reveals that the multi-threading results are nuanced – with strong performance in the synthetic setting and weaker performance in the natural text setting. We’ll update the paper with these new insights, which we hope will be valuable for the research community.
</content>
</thread_object>

</thread>
<thread>
creation date:
1733284998181

thread_type:
official_comment

<thread_object>
creator: authors

<content>
comment:
We thank the reviewers again for their time, helpful comments and positive responses to our paper. In our rebuttal, we aimed to address all your concerns and consider our paper to be improved as a result.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper focuses on experimental validation and discussion of the context understanding capabilities of existing LLMs. The authors designed a series of retrieval experiments, including single needles, and multiple needles with random and clustered distributions. The experimental process is clearly presented and easy to understand, and most reviewers expressed their recognition of this work and gave positive scores. The main concern raised by the reviewers was that the authors only used synthetic datasets for testing, which the authors addressed in the rebuttal phase. I personally find this acceptable, especially since the authors conducted thorough experiments and provided a complete experimental process. Additionally, my suggestion is for the authors to avoid using different x-axis intervals (e.g., Gemini 1.5 Flash and GPT-4 Mini) in the same figure (e.g., Figure 5). To summarize, I recommend accepting this work.