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

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 36 of its 45 references that are in the map.
- First posted on arXiv 24 Sep 2026.

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

- [Efficient Memory Management for Large Language Model Serving with PagedAttention](https://mlsanity.com/paper/2309.06180/) (2023)
- [Mamba: Linear-Time Sequence Modeling with Selective State Spaces](https://mlsanity.com/paper/2312.00752/) (2023)
- [Dense Passage Retrieval for Open-Domain Question Answering](https://mlsanity.com/paper/2004.04906/) (2020)
- [HotpotQA: A Dataset for Diverse, Explainable Multi-hop Question Answering](https://mlsanity.com/paper/1809.09600/) (2018)
- [Longformer: The Long-Document Transformer](https://mlsanity.com/paper/2004.05150/) (2020)
- [Transformers are RNNs: Fast Autoregressive Transformers with Linear Attention](https://mlsanity.com/paper/2006.16236/) (2020)
- [Big Bird: Transformers for Longer Sequences](https://mlsanity.com/paper/2007.14062/) (2020)
- [PubMedQA: A Dataset for Biomedical Research Question Answering](https://mlsanity.com/paper/1909.06146/) (2019)
- [BEIR: A Heterogenous Benchmark for Zero-shot Evaluation of Information Retrieval Models](https://mlsanity.com/paper/2104.08663/) (2021)
- [Leveraging Passage Retrieval with Generative Models for Open Domain Question Answering](https://mlsanity.com/paper/2007.01282/) (2020)
- [ColBERT: Efficient and Effective Passage Search via Contextualized Late Interaction over BERT](https://mlsanity.com/paper/2004.12832/) (2020)
- [Atlas: Few-shot Learning with Retrieval Augmented Language Models](https://mlsanity.com/paper/2208.03299/) (2022)
- [BrowseComp: A Simple Yet Challenging Benchmark for Browsing Agents](https://mlsanity.com/paper/2504.12516/) (2025)
- [YaRN: Efficient Context Window Extension of Large Language Models](https://mlsanity.com/paper/2309.00071/) (2023)
- [The NarrativeQA Reading Comprehension Challenge](https://mlsanity.com/paper/1712.07040/) (2017)
- [Gated Delta Networks: Improving Mamba2 with Delta Rule](https://mlsanity.com/paper/2412.06464/) (2024)
- [LongBench v2: Towards Deeper Understanding and Reasoning on Realistic Long-context Multitasks](https://mlsanity.com/paper/2412.15204/) (2024)
- [OpenAlex: A fully-open index of scholarly works, authors, venues, institutions, and concepts](https://mlsanity.com/paper/2205.01833/) (2022)
- [BRIGHT: A Realistic and Challenging Benchmark for Reasoning-Intensive Retrieval](https://mlsanity.com/paper/2407.12883/) (2024)
- [How to Train Long-Context Language Models (Effectively)](https://mlsanity.com/paper/2410.02660/) (2024)
- [HELMET: How to Evaluate Long-Context Language Models Effectively and Thoroughly](https://mlsanity.com/paper/2410.02694/) (2024)
- [On the Theoretical Limitations of Embedding-Based Retrieval](https://mlsanity.com/paper/2508.21038/) (2025)
- [Efficient Long-Text Understanding with Short-Text Models](https://mlsanity.com/paper/2208.00748/) (2022)
- [TurboRAG: Accelerating Retrieval-Augmented Generation with Precomputed KV Caches for Chunked Text](https://mlsanity.com/paper/2410.07590/) (2024)
- [DocETL: Agentic Query Rewriting and Evaluation for Complex Document Processing](https://mlsanity.com/paper/2410.12189/) (2024)
- [Oolong: Evaluating Long Context Reasoning and Aggregation Capabilities](https://mlsanity.com/paper/2511.02817/) (2025)
- [Is It Really Long Context if All You Need Is Retrieval? Towards Genuinely Difficult Long Context NLP](https://mlsanity.com/paper/2407.00402/) (2024)
- [Star Attention: Efficient LLM Inference over Long Sequences](https://mlsanity.com/paper/2411.17116/) (2024)
- [Olmo Hybrid: From Theory to Practice and Back](https://mlsanity.com/paper/2604.03444/) (2026)
- [LongBench Pro: A More Realistic and Comprehensive Bilingual Long-Context Evaluation Benchmark](https://mlsanity.com/paper/2601.02872/) (2026)

## Abstract (arXiv)

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.