.png)
October 9, 2024
Long-context language models (LCLMs), characterized by their extensive context window, are gaining increasing popularity. However, many long-context benchmarks pose challenging tasks that even the most advanced LCLMs struggle to solve. However, the underlying causes behind the diverse challenges posed by long contexts have rarely been explored. To bridge this gap, we conduct experiments demonstrating that their difficulty is primarily attributed to two fundamental issues: "multi-matching retrieval," requiring simultaneous retrieval of multiple elements, and "logic-based retrieval," necessitating logical judgments within retrieval criteria. These two issues, while seemingly simple at first glance, exceed the capabilities of LCLMs, as they are proven to be hyper-multi-step (i.e., their solutions require numerous steps). This finding could explain why LLMs struggle with more challenging long-context tasks, offering a more precise perspective for rethinking solutions to these tasks.
Over the past year, long-context language models (LCLMs) such as GPT-4o-128k and Gemini-1.5-1000k have surged in popularity, raising questions about their effectiveness in handling tasks with extended context. While various LCLMs have demonstrated proficiency in long-context information retrieval, passing the "needle in a haystack" test at a context length exceeding 100,000 words, benchmarks like Loogle and Loong have exposed their weaknesses in more complex tasks.
To better mimic real-world challenges, recent long-context benchmarks primarily aim to increase the difficulty of long-context tasks by requiring the comprehension of real-life scenarios and multi-step reasoning processes or increasing the amount of information that needs to be aggregated. This results in these tasks typically requiring multiple abilities from LLMs, such as world knowledge, advanced reasoning skills, and retrieval capabilities. Consequently, poor model performance is often vaguely attributed to insufficient comprehension, lack of reasoning abilities, and long-context retrieval capabilities, making it challenging to identify the specific factors causing the main difficulty.
To uncover the true cause of the challenges in long-context tasks, we conduct a detailed analysis of challenging tasks from previous long-context benchmarks and identify two common factors making these tasks difficult: multi-matching retrieval and logic-based retrieval. Multi-matching retrieval requires the simultaneous retrieval of multiple elements, and logic-based retrieval necessitates logical judgment within retrieval criteria. Although both are "basic" retrieval issues that have a simple form and cannot be explicitly decomposed into multiple steps (we will use examples to illustrate their differences from the traditional multi-step tasks that can be decomposed by CoT, hence referred to as "formally multi-step"), our experiments demonstrate that they are much more difficult than direct retrieval or formally multi-step retrieval for current LCLMs with increasing context length.
Instead of solely focusing on the superficial phenomena, we seek to explain why these seemingly simple problems pose significant challenges to LLMs. Through in-depth experiments, we show that they are inherently "hyper-multi-step," which distinguishes them significantly from ordinary retrieval problems. "Hyper-multi-step," the truth behind difficult long-context tasks, refers to a problem that appears indivisible in form but actually requires numerous independent steps, the number of which increases indefinitely with the length of the context, exceeding the ability of LLMs to process simultaneously. So far, none of the techniques like retrieval-augmented generation (RAG), chain-of-thought (CoT)-prompting, and LCLMs have properly addressed such problems.
With our studies, we do not aim to propose even more challenging benchmarks to further push optimizations on LCLMs. Instead, we reveal a harsh reality: while LCLMs are intended to process massive amounts of input data simultaneously, there are certain long-context tasks that will always be unattainable for LCLMs within one step. Therefore, future research should focus on addressing the challenges associated with numerous steps rather than merely expanding the context window of LLMs.
The emergence of long-context language models (LCLMs) aims to enable language models to process vast amounts of input information simultaneously. In recent years, closed-source LLMs have pioneered long-context modeling, with context windows expanding from 128k to 1000k tokens. Notable models include GPT-4o, Claude3.5-200k, and Gemini-1.5-1000k, which are capable of processing significantly longer texts. Meanwhile, open-source models such as phi-3.5-mini and Qwen2.5 utilize advanced RoPE (Rotary Position Embedding) interpolation techniques like Yarn and LongRope to achieve a context window of 128k. These open-source models are typically extended from a pretraining length of 4,000 words through long-context post-training with interpolated RoPE. However, it remains to be seen whether these models are truly capable of correctly and efficiently processing long contexts.
The field of long-context modeling is rapidly advancing, and benchmarks are becoming increasingly complex and diverse. Simple synthetic tasks like "needle-in-a-haystack" (NIAH) evaluate the retrieval ability of long-context language models. Early benchmarks such as Longbench, BAMBOO, and L-eval provide a multi-faceted evaluation of long-context understanding through various task forms, but the focus is not typically on difficulty. More recent benchmarks, including InfiniteBench, RULER, LOOGLE, and LOONG, incorporate more challenging tasks with varying levels of complexity and adjustable context lengths. LOFT, on the other hand, explores whether long-context models can act as retrieval systems like RAG and SQL. Despite these advancements, few studies have thoroughly investigated the underlying commonalities among these complicated long-context tasks, leaving a lack of understanding regarding the fundamental reasons for their challenges.
In this section, we conduct evaluations of current LCLMs to demonstrate that multi-matching and logic-based retrieval are indeed difficult, even nearly unsolvable for current LCLMs in long contexts. In contrast, normal retrieval or formally multi-step retrieval proves to be much easier.
To avoid data contamination, we create two completely synthetic datasets: key-value pair retrieval and student resume retrieval. These datasets allow us to easily make controlled changes to the input context size and problem types.
In key-value pair retrieval, the context is a JSON-formatted dictionary consisting of N randomly generated key-value pairs. The key is a 10-character string, and the value is a positive integer. The question is appended to the context and varies based on the task type. In multi-matching, the model needs to retrieve all keys associated with a specific value. In logic-based retrieval, the model needs to identify the key with the value within a certain range.
In the student resume retrieval task, all original resumes are fictitious and generated by GPT-4o. The context includes...
In conclusion, while long contexts are all the rage, tackling many long-context tasks remains highly challenging for current LCLMs. Instead of vaguely attributing the difficulty to insufficient comprehension, lack of reasoning ability, and retrieval capabilities, we have demonstrated through experiments that two specific issues, multi-matching retrieval and logic-based retrieval, are the primary contributors to the complexity of long-context tasks. Furthermore, through further investigation, we have found that these two problems are inherently hyper-multi-step, meaning they require a large number of independent steps that grow increasingly demanding with increasing context length. Therefore, they pose significant challenges to current LCLMs, which are designed to process information within one step. These findings suggest that future research should focus on addressing the challenges associated with numerous steps rather than merely expanding the context window of LLMs.
