No More Free Lunch: Corpus Task Complexity Matters as Corpora Grow

Prasann Singhal; Amanda Bertsch; Jacob Steinhardt; Sewon Min

cs.CLSep 24, 2026

No More Free Lunch: Corpus Task Complexity Matters as Corpora Grow

Authors: Prasann Singhal, Amanda Bertsch, Jacob Steinhardt, Sewon Min

Organizations: UC Berkeley · Carnegie Mellon University · Allen Institute for AI

Abstract

Given a large corpus, the questions one might ask can vary -- from "When was the first human heart transplant?" to "What are all the contradictory claims in this literature?" -- but what makes some questions more challenging than others? In this work, we define a notion of Corpus Task Complexity (CTC) that characterizes tasks by how their difficulty grows with corpus size; for instance, a retrieval query only requires a single linear pass over a corpus, while finding contradictions requires checking a quadratically growing set of claim pairs. Observing that prior work has largely only studied tasks whose difficulty grows linearly with corpus size, which we call low CTC tasks, we introduce 10 new tasks belonging to a class of high CTC whose difficulty grows quadratically or more in corpus size. We find that high-CTC tasks not only grow much more challenging on average at longer contexts for LCLMs, they reverse many modeling conclusions drawn solely from low-CTC evaluations. For instance, efficient block-sparse and hybrid attention approaches consistently match full attention performance on low-CTC tasks, but degrade much more on high-CTC tasks. Large-corpus high-CTC reasoning thus remains an open challenge as full attention is too costly to scale, motivating future research on these tasks. We release our code, data, and 22-task suite (CTC-Bench), to facilitate future research in this area.

Figures & tables

Figure 1: Performance of in-distribution trained Qwen3.5-4B models on low- and high-CTC tasks. (Left) Performance degrades faster on high-CTC tasks than on low-CTC tasks as corpus size increases. (Right) Block-sparse attention causes almost no performance degradation relative to full attention on low-CTC tasks, but substantial degradation on high-CTC tasks.

Figure 2: Circles represent documents, with shaded circles for the gold documents. As corpus size

N=|C|

grows from 3 documents to 100 documents, a contradiction search task may in worst-case require many more oracle operations (4950) than factoid retrieval (100).

$\mathbf{O}(N)$ : Low Complexity Tasks		Higher-complexity tasks
Dataset	Description	Dataset	Description
NIAH-contra	Find the contradicting claim	Contradiction	Find all contradicting claim pairs
SciFact	Retrieve evidence for a scientific claim	X-Absence	Find unmatched docs across 2 shuffled, near-identical corpora
FiQA	Retrieve relevant financial opinions	QDmatch (HPQA)	Match questions to two documents
MS MARCO	Retrieve relevant web passages	QDmatch (NQ)	Match questions to documents
OBLIQ	Retrieve passages for subjective queries	QDmatch (FiQA)	Match financial queries to documents

Table 1: Overview of the 22 CTC-Bench Tasks. Linear-time tasks are shown on the left; tasks requiring higher-order comparisons are shown on the right (details, examples in Appendix H )

Figure 3: Scaling of full vs. block-sparse attention (mask mix) We show block-sparse vs full attention performance at different contexts on our full task suite. While both methods perform near-identically on low-CTC, high-CTC tasks correspond to growing gaps between them on larger corpora.

Figure 4: Hybrid vs Full Models We plot CTC-Bench -10 results for a full-attention (solid) version of OLMo-3-7B vs OLMo-3-Hybrid (dot-dashed). On low-CTC tasks both perform similarly, but on high-CTC tasks we observe consistent performance gaps.

Figure 5: (Left) Gain of curriculum mask-mixing over pure block-sparse training (no mixing) , averaged across 2k–32k contexts on CTC-Bench -10. Mask-mixing consistently improves block-sparse, especially on High-CTC tasks and tasks more dispersed across contexts (such as OOLONG). (Right) Length generalization (full attention). For 64k and 128k context eval sets (trained only to 32k), we plot percentage of 32k score. High-CTC tasks are harder for length generalization.

Figure 6: (Left) Model scale/family Percentage of full-attention performance lost to block-sparse attention at 4k, 8k and 16k context, for three Qwen3.5 scales and two other model families, on a low-CTC (HotpotQA,

O_{T}(N)

) and high-CTC (Contradiction,

O_{T}(N^{2})

) task. The gap is minimal on low-CTC and large and growing on high-CTC; within the Qwen3.5 family (shades of purple) smaller models degrade faster. (Right) Oracle Difficulty For 4 task pairs with matched oracle operations (block-sparse attention), ratio of

O_{T}(N)

O_{T}(N^{2})

task performance on the same corpus (pairs named in the legend). Tasks with harder base operations (darker) see the ratio grow faster.

Appendix figures & tables4 assets

Supplementary material from the paper’s appendix.

Appendix

Dataset	Example
$\mathbf{O}(N)$ : One-pass tasks
NQ	“who sold out jesus for 30 pieces of silver” $\rightarrow$ [1]
HotpotQA (bridge)	“What company did Rex Maughan aquire?” $\rightarrow$ [8, 9]
NIAH-contra	“ $\dots$ a hypertonic solution of 14.4% has an ir reversible ciliostatic effect” $\rightarrow$ [20] , the one claim saying reversible
BEIR SciFact	“0-dimensional biomaterials show inductive properties.” $\rightarrow$ [1]
BEIR FiQA	“Where should I park my rainy-day / emergency fund?” $\rightarrow$ [2, 8, 10, 12, 19]

Appendix

Table 2: One real example per task. All content is verbatim from the evaluation sets, elided with … where a passage is too long to show; document IDs are 1-indexed exactly as the model sees them. Appendix H shows each example in full, with the task instruction, the surrounding corpus and the distractor types.

Task	Source corpus	CTC	Metric	2k	4k	8k	16k	32k	Chars/doc	Eval
				Documents per example ( $N$ )
NQ	Wikipedia 100w (DPR)	$O_{T}(N)$	gold-ID F1	11	23	48	104	208	636	500
HotpotQA (bridge)	Wikipedia 100w (DPR)	$O_{T}(N)$	gold-ID F1	17	36	72	144	296	432	500
NIAH-contra	PubMed claims	$O_{T}(N)$	gold-ID F1	40	86	180	365	740	60	500
BEIR SciFact	SciFact abstracts	$O_{T}(N)$	gold-ID F1	5	10	21	43	88	1517	300
BEIR FiQA	FiQA-2018 posts	$O_{T}(N)$	gold-ID F1	8	19	40	82	166	835	500

Appendix

Table 3: Corpus statistics for every task in the evaluation suite Column headings 2k–32k are approximate token targets per task; the entries are the median number of documents actually present in an example of that rung, measured from the evaluation files the reported results were graded on. Chars/doc is the median document length in characters at the deepest available rung.

Figure 7: Full model performance on several tasks and Qwen3.5 model scales. Some high-CTC tasks have minimum model scales necessary to learn effectively.

Figure 8: Full vs block-sparse attention with a few different model families.

Explore similar work

MixRea: Benchmarking Explicit-Implicit Reasoning in Large Language Models
May 19, 2026Yuanqing Cai, Ziyi Huang, Minhao Liu +3LLM Reasoning Strategies Progressive Reasoning
Shenzhen Institute for Advanced Study, University of Electronic Science and Technology of China
Oolong: Evaluating Long Context Reasoning and Aggregation Capabilities
Nov 4, 2025Amanda Bertsch, Adithya Pratapa, Teruko Mitamura +2Question-Answering Benchmarks
Carnegie Mellon University, Language Technologies Institute
Scaling Multi-Hop Training Data via Graph-Constrained Path Selection
May 29, 2026Pengyu Chen, Yonggang Zhang, Mingming Chen +3Multi-Hop Reasoning Reasoning Paths
The Hong Kong University of Science and Technology · Hong Kong Generative AI Research and Development Center · Hong Kong Baptist University

May 19, 2026, cs.CLJ/K move · Enter open · S save

MixRea: Benchmarking Explicit-Implicit Reasoning in Large Language Models

Yuanqing Cai, Ziyi Huang, Minhao Liu, Lixin Duan+2

Shenzhen Institute for Advanced Study, University of Electronic Science and Technology of China

LLM Reasoning Strategies Progressive Reasoning Cognitive Science

Open paper AskPDF arXiv

Large language models (LLMs) are increasingly integrated into high-stakes decision-making. Inspired by the theory of \emph{inattentional blindness} in human cognition, we investigate whether LLMs, trained on human-preferred corpora that embed attentional biases, exhibit a similar limitation: \emph{failing to attend to subtle yet important contextual cues under explicit task instructions}. To evaluate this, we introduce the task of \textbf{explicit-implicit reasoning} and present \textbf{MixRea}, a benchmark of 2,246 multiple-choice questions across 9 reasoning types with varying distributions of explicit and implicit information. Evaluation of 21 advanced LLMs shows that even the best-performing reasoning model (Gemini 2.5 Pro) achieves only 42.8% consistency, revealing widespread inattentional blindness. To mitigate this, we propose \textbf{Potential Relation Completion Prompting (PRCP)}, a prompting method that improves reasoning by recovering overlooked causal relations. Further analysis shows that this limitation persists across diverse multi-source reasoning tasks, highlighting the need for more cognitively aligned models.

Abstract

Explore similar work

MixRea: Benchmarking Explicit-Implicit Reasoning in Large Language Models

Oolong: Evaluating Long Context Reasoning and Aggregation Capabilities

Scaling Multi-Hop Training Data via Graph-Constrained Path Selection