FACTOR: Factoring Complexity and Context Length in Long-Context Model Evaluation

Authors: Hongyi Liu, Zhuoming Chen, Yang Zhou, Beidi Chen
Primary area: datasets and benchmarks
Keywords: Long-context reasoning, Language models

Abstract:
Large language models (LLMs) with extended context windows have shown remarkable capabilities, especially with contexts up to 128K tokens. However, whether these resource-intensive LLMs genuinely surpass simpler Retrieval Augmented Generation (RAG) techniques remains debated. 
We precisely delineate differences between long-context LLMs and RAG methods, emphasizing the unique long-context reasoning abilities of LLMs that RAG cannot replicate. 
Existing benchmarks often focus on retrieval tasks and contain weak if not none complex reasoning tasks, hindering assessment of reasoning over extended contexts. We introduce the \textbf{FACTOR} benchmark (\textbf{F}actoring \textbf{A}nalysis of \textbf{C}omplexity and \textbf{T}extual \textbf{C}ontext in \textbf{R}easoning), which evaluates LLMs by independently varying task complexity and context length. A comprehensive list of LLMs are evaluated on FACTOR. 
Besides mere accuracy scores, we also model the relationship between accuracy and complexity given the context length. A simple but consistent log-linear model works surprisingly well across various models. Also, the modeling contains two explainable parameters, the slope or Complexity Decay Factor (CDF) and the y-intercept or Contextual Decay Offset (CDO) that are shown to offer separate and insightful measures of the models' complex reasoning and long context innate ability. 
Our findings highlight distinct failure modes linked to task complexity and context length, underscoring the unique reasoning capabilities of long-context LLMs unattainable by RAG methods.

Decision: reject
Reviewer scores: 3, 6, 3, 8

Reviews and discussion:
<thread>
creation date:
1730166760675

thread_type:
official_review

<thread_object>
creator: reviewer_zsab

<content>
summary:
This paper proposes FACTOR - a novel benchmark for evaluaition of long context reasoning in LLMs. Most importantly - it separates task complexity from context length. Then the paper evaulates several LLMs on this benchmark and shows that performance has a log linear relationship with complexity. Two metrics were then derived from this relationship - CDF and CDO. This is important to quantify the degradation in reasoning with complexity and length. Then the paper tests impact of pretraining and finetuning on these metrics, as well as the impact of more frequent sampling during inference.

strengths:
Originality - I believe that CDO and CDF are great metrics that fill a gap in LLM literature, and the FACTOR benchmark is very useful for this.

Quality - The methodology makes sense and the experiments are well structured. I found the log linear result to be very interesting.

Clarity - the paper is well written, easy to follow.

Significance - These results are an important addition to scaling laws, and important findings.

weaknesses:
Not much to say but - 

1. Task diversity is limited, which means maybe this is not as representative of real world scenarios.
2. FACTOR seems to be a very computationally expensive benchmark to run.

questions:
1. Would FACTOR be extended to further logical inference/ commonsense reasoning tasks?
2. How robust are CDO and CDF to randomness of seeds used in FACTOR generation? Are there any analyses on stability of these metrics?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730630606493

thread_type:
official_review

<thread_object>
creator: reviewer_alnr

<content>
summary:
This paper performs an experimental analysis of several language models for a particular reasoning task solving sets of simple equations when context windows increase and separate those equations. The results are fitted with simple linear equations (after logarithmic scale transformations) and two indicators are derived from the linear functions (the slope, Complexity Decay Factor, and the y-intercept, the Contextual Decay Offset). Some insights are extracted from that modelling.

strengths:
The paper is well written, and it is easy to follow.
There is more need to show how context windows affect some reasoning process and no appropriate benchmarks seem to exists, and previous analyses are confounded by other factors. So there's motivation for this paper.
Many models, including very recent ones, are covered. The experiments are quite exhaustive in that dimension.

weaknesses:
The kind of task is relatively narrow, and different results could be observed for other tasks. In particular, the task question is formulated as choosing those variables that meet the requirements. This can have elimination/random components that are specific to this task and do not generalise to other tasks, or even some other presentations of this task (asking for actual values, instead of affected variables). There's not sufficient analysis of shortcuts, even if the authors claim they ensure they not happen. The paths to the right answers may be short in some cases and this is intrinsic with the problem and not random.

Apart from the use of only one problem, the major problem is the fitting. The authors calculate the logarithm of the y-axis on a bounded performance scale that goes between 0 and 1. But this can never give a linear relationship if we extend the complexity on the x-axis until we reach 0 accuracy (more variables or questions where choices or elimination make success by pseudochance very unlikely). The full response curves are actually sigmoid and the observed behaviour in this paper happens because collected data stops in a high-slope part of the sigmoid. Given the character of the y-axis, a logistic fit on the original scale would have made much more sense than a linear fit on a logarithmic scale.

In fact, extracting Effective Complexity using the linear model has the problem of possible extrapolation of a negative number of variables, something that wouldn't happen with a logistic model. With a logistic model, the effective complexity could simply be chosen when accuracy goes below a threshold of 90%.

The comparison with RAG appears in the abstract and the introduction, but then this disappears in the paper, so to me it's thrown as a red herring and deviates the motivation.

More justification is needed for repeated sampling as a proxy for increasing inference compute. Actually, there's no need to do experiments for this, as the tries are independent and it's a question of multiplying the failure probability of each of it. That's why figure 6 looks so linear.


Minor details:
- acronym in the abstract wrong
- the related work section has some expression and formatting issues (blank spaces missing before the references).

questions:
I couldn't find how scoring of answers is performed. For instance, if the ground truth is v3 and v5, what's the score if the model says only v3? Is it only totally right or otherwise wrong? This is very important to understand whether there are shortcuts or not.

About o1-mini, it is said that "inference-time strategies can significantly enhance performance across task complexities", but we don't know (or at least no source is provided) of whether o1 is using some other techniques that affect the context window, or it gives several passes or other strategies, since the details of the system have not been published. Do you have more details about o1 that are publicly available?

Can you explain why repeated sampling is a proxy for increasing inference compute?

Can you make a logistic fitting instead of a linear fitting?

Do you think the results will hold for other tasks?

Where's the discussion/comparison about RAG?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730696269264

thread_type:
official_review

<thread_object>
creator: reviewer_zehp

<content>
summary:
The paper presents FACTOR, a benchmark specifically developed to assess the performance of LLMs in handling complex reasoning tasks over long contexts. FACTOR generates synthetic problems that require models to understand and solve relationships between variables within long pieces of text. The authors also evaluate several models by evaluating them on varying tasks complexity and context length.

strengths:
They propose a task generation framework that can be used to generate tasks with various levels of difficulty and context lengths. 

They evaluate multiple models using their benchmarks, and show that by increasing the context length and difficulty of the problems, these models struggle to reason correctly on them.

weaknesses:
They don’t consider generating the filling text that is not random (e.g. is about math and reasoning) to make the task more difficult. 


They only focus on the tasks that have explicit assignment expressions in the text. As the LLMs get more advanced, we need the test cases where the information necessary for the reasoning is expressed in natural language and not explicitly specified with a special notation.

questions:
How many tasks are included in this benchmark for each experiment?

Could you present the results from Table 1 in a way that clearly highlights which models are performing better?

I am curious about how the o1 model would perform compared to the others (and o1 mini). 

Is the complexity of the problem only determined by the number of variables? How can you increase the complexity of the problem by changing the relationship of the variables and the nature of the problem (e.g. can some problems be unsolvable?)? 

What would happen if the filler text were meaningful rather than randomly generated?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730716278102

thread_type:
official_review

<thread_object>
creator: reviewer_wnwn

<content>
summary:
Authors introduce FACTOR, a benchmark to evaluate LLMs' long context complex reasoning ability. The goal was to distinguish between long-context LLMs and RAG and explore how LLMs reasoning abilities depend on context length and task complexity.

FACTOR manipulates two variables that control for task complexity and context length: the first one is the number of variables--the larger the number of variables the higher the complexity of the task; the second one is length of filler text--adding text to the necessary portion of logic arguments. The authors find log-linear relationship between accuracy and complexity. Filler text is randomly generated text.

Authors find that for some LLMs' performance is outlines by different performance zones. They also outline how different pertaining strategies can influence performance.

strengths:
I like that authors introduce task complexity and analyse performance as a function of this. The authors also show a nice analysis of this performance and divide it into performance phases.

weaknesses:
The main weakness of this paper is that it doesn't provide analysis or evidence for the claim it set out to explore at the outset: i.e. showing the 'unique reasoning capabilities of long-context LLMs unattainable by RAG methods'. They don't provide any analysis of LLMs using RAG to support this claim. Authors could've had a the models tested also use RAG to perform the same task. In particular, because their filler text is randomly generated, I suspect RAG wouldn't have issues finding the relevant text and which would then greatly simplify the task for an LLM.

Another smaller issues pertains to the interpretation of the context decay offset (i.e. CDO) which is the intersect of the fitted log performance line and captures 'the baseline performance level influenced by context length'. I don't think this would be a correct interpretation of the intercept, for a simple reason that these intercepts of log performance can be higher 0 (and many times are as seem from Table 1), meaning that that this baseline performance can be higher than 100%, which doesn't make sense. In the context of the paper, these intercepts have no interpretation in terms of performance.

questions:
Why no experiments were done comparing LLMs that use long-context windows and those that use RAG?

Why was the filler text decided to be a completely random text? Why not some meaningful filler text?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732482592662

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Response to all reviewers

comment:
We thank all reviewers [`R1 (wnwN)`, `R2 (ZEhP)`, `R3 (ALNr)`, `R4 (zsAb)`] for their attention and interest in reading FACTOR and for your constructive and supportive comments. We are glad to find that people think that this benchmark has strong significance `R3 (ALNr)`, and we are also pleased to see people appreciate our methodology to do fine-grained op control when benchmarking `R1 (wnwN)` and `R2 (ZEhP)`. 

We want to assure the reviewers that we take their suggestions and criticism seriously. Therefore, we substantially rewrote the paper submitted based on the valuable feedback. The differences can be summarized in the following bullet points: 

 - **Bring FACTOR’s Spirit to Common Sense Reasoning and Fusing General Language Context into the Problem Generation** [`R2 (ZEhP)`, `R3 (ALNr)`, `R4 (szAb)`] To increase the diversity of our current dataset, we introduce an entire common-sense reasoning benchmark suite. This suite follows the core spirit of FACTOR to generate text problems from curated computational graphs. To increase the diversity of the machine-generated dataset, we curated three different real-world scenarios as the context template and evaluated models to run on it with both forward and backward logic. The result is that we can use this problem generation system to generate infinite GSM-8K-like problems while also fine-grainedly controlling and easily scaling up the problem’s difficulty. Together with the previous symbolic benchmark suite, we now have the full machine-generated benchmark decoupling context and logic difficulty and easy to scale up in difficulty. Details about the implementation of graph generation and text attachment can be found in the revised paper $\text{\textcolor{blue}{Section 4.2 - 4.4, page 6 - 7}}$. 
 
 - **Present Detailed RAG Experiments to Show that RAG Cannot Perform Well on Complex Long-Context Reasoning Task** [`R1(wnwN)` and `R2 (ZEhP)`] 
We added extensive comparisons and studies to contrast RAG’s performance and long-context LLM on our tasks. We first build up a RAG system baseline using Llama 3.1 8B Instruct as the decoder. We test it across various popular and open-sourced long context benchmarks. For VT from RULER, the RAG achieves 86.4% accuracy with the full LLM achieving 99.2%. However, the RAG accuracy on our commonsense reasoning suite drops to zero when the number of operations (op) > 3. We further enable iterative prefilling of the RAG system so that it can achieve 100% on VT, but it still has near 0 accuracy when op > 3, despite the full LLM scoring >20% consistently. The same phenomenon holds true even when we use Llama 3.1 70B Instruct as the RAG system’s decoder, signifying our dataset has a high-quality design of noise. More details can be found in $\text{\textcolor{blue}{Section 3, page 3 - 5}}$ RAG vs Long Context Benchmarks. 

 - **Refined Description of the Methods and Evaluation Metrics** [`R2 (ZEhP)`, `R3 (ALNr)`] 
To present FACTOR in a more discerning and open way, besides presenting intensive details on the implementation of the dataset generator, we also elaborate on more details about noise addition design together with the evaluation prompt, template, and parsing in $\text{\textcolor{blue}{Section 4, page 5 - 8}}$. We believe that providing these details is conducive to a more in-depth evaluation of the significance of the dataset.
</content>
</thread_object>

</thread>
<thread>
creation date:
1733207035504

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
A Call for AC's Discretion

comment:
Dear Area Chair, 

We genuinely appreciate all four reviewers' time and effort in reviewing and raising valuable suggestions about FACTOR. On the other hand, it is unfortunate and disheartening to see that despite our significant efforts and major paper revision to carefully and comprehensively clarify in our responses, only one further feedback is received during the entire rebuttal. We believe that the lack of engagement during the rebuttal made it unfair and extremely difficult for us to further communicate and bolster the value of our work. Therefore, we sincerely request AC's discretion on our work. To make it easier for AC's navigation through the long and detailed reviews and responses, here we provide a one-stop summary for all the major contributions of FACTOR and our responses to related concerns. 

**Problem and FACTOR**

Despite a plethora of popular long-context benchmarks of LLM, we first show that these popular long-context tasks can be satisfactorily solved by a simple-to-build RAG system. Therefore, we believe that the tremendous cost of training the long-context LLM isn't justified by the existing benchmarks. To solve the problem, we developed FACTOR, a synthetic long-context benchmark that aims to evaluate the complex reasoning of LLMs with various context-length settings. Because of the problem curation and the noise design, the RAG system completely cannot solve the task, while LLM delivers a reasonable range of performance. We further study the LLM performance degradation with higher difficulty as well as with longer context length, and we report that a comprehensive list of LLMs we tested generally displayed a exponential decaying performance-to-difficulty relationship that can be neatly modeled by a fitted curve. This observation offers new insight into LLM's reasoning ability and its long-context ability. 

**Main Concerns We Faced** 

*Lack of diversity in the benchmark* (`ZEhP`, `ALNr`, `zsAB`) 

In the initial version of FACTOR we submitted, the task is focused on variable assignments without any semantics in the problem context. In rebuttal, we incorporate real-world context in our newly added Medium and Hard subsets of FACTOR. The addition is based on a new observation: LLM performance naturally degrades when the problem involves more hierarchical relationships in the problem set. We now generate controlled commonsense reasoning problems that contain hidden operations through semantics. More interestingly, we show that the exponentially decaying trend observed on the simple variable assignment subset holds on the new commonsense subsets. 

*Lack of RAG experiments and the use of not random noise* (`wnwN`, `ZEhP`, `ALNr`) 

During the rebuttal, we generate noise directly by the same problem generator. Then, we present RAG experiments on our newly added medium and hard subsets with the new noise. We first test a conventional setup using an LLM as the decoder but with context retrieved by a sentence transformer. We show that even though under a generous setting of 8K context length with a 2K budget, the RAG performance is near zero for reasonable operation counts. Then, to make the case even more convincing, we enable iterative prefilling for every token. The RAG still gives near 0 performance, showing a significant gap to the full context LLM. 

*Computational Expensive* (`zsAb`) 

Admittedly, a sweep of all the operation counts from 0 to 20 (medium and hard) or 40 (easy) is costly. However, since FACTOR uses the fitted curve and its parameters to cross-compare different models, we show that only evaluating once every three or four operation numbers can fit the landscape nicely, reducing the total testing compute by 3-4x. Also, since we newly added the hard subsets where LLM performance degrades the fastest, measuring smaller number of operations would give complete landscape. 

*The fitted curve is closer to logistic regression, not exponential decay* (`ALNr`) 

We observe that there are two phases of the general trend of LLM performance degradation with respect to problem difficulty. First, it remains flat for easy problems, and as the difficulty increases, the performance drops sharply. Intuitively, using the logistic regression is a natural way to describe this relationship. However, through comprehensive experiments with high precision and costs, we show that the trend is closer to a step-wise function where the beginning is a constant, followed by an exponential decaying function across various models and FACTOR subsets. 

-----
We hope the post provides a concise summary of the entire paper and rebuttal. With the advent of ChatGPT-O1 and similar models, the reasoning ability of LLM is becoming stronger. The community is in desperate need of a fine-grainedly controllable dataset that is easily scalable in both difficulty and context length. FACTOR is a pioneering work in this direction and would be filling the dire need of the community. 

Sincerely, 

Paper 7490 Authors
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper introduces the FACTOR benchmark (Factoring Analysis of Complexity and Textual Context in Reasoning). Factor evaluates LLMs by independently varying task complexity and context length. The results are fitted with log-linear model, and three indicators are extracted from it. The reviews acknowledge that there is a significant effort in this paper, and the line of research is important. Unfortunately, two reviewers raised concerns about the contribution and the justification for some choices, and I fully agree. As the discussion between the authors and the reviewers indicates, this needs to be clarified and will be a major rewrite, as a lot of changes and new ideas and arguments have been presented in the discussion. Moreover, the evaluation should involve some significant analysis of the log-linear model fits as well as of the predictive performance. Please note that the overall judgment should not be taken as a statement regarding the usefulness of your research.