No More Free Lunch: Corpus Task Complexity Matters as Corpora Grow
Prasann Singhal, Amanda Bertsch, Jacob Steinhardt, Sewon Min
cs.CL · cs.AI
Quick verdict
Defines Corpus Task Complexity and a 22-task benchmark showing sparse/hybrid attention degrades on O(N²) tasks; convincing, but fine-tuned, ≤32k evidence only.
Summary
The paper introduces Corpus Task Complexity (CTC), characterizing corpus-reasoning tasks by how the number of oracle calls needed to solve them grows with corpus size N. The authors survey 12 widely used benchmarks (retrieval, QA, aggregation) and argue all are low-CTC, O(N). They add 10 new high-CTC tasks — contradiction search, cross-corpus absence, query-document matching, topic outlier/grouping, string matching, reordering, and an O(N³) triple-finding task — forming the 22-task CTC-BENCH, evaluated at 2k–32k tokens. Fine-tuning Qwen3.5-4B per task with in-distribution data, they find high-CTC performance drops 40% from 2k to 32k versus 13% for low-CTC. High-CTC results also reverse conclusions drawn from low-CTC evaluations: block-sparse attention matches full attention on low-CTC tasks but loses 26.9%→65.9% on high-CTC as context grows; OLMo-3's hybrid (3:1 GDN) trails its full-attention counterpart; and length generalization to 128k retains only 4–14% of 32k performance on high-CTC versus 28–100% on low-CTC. A mask-mixing curriculum improves block-sparse training. Smaller models degrade faster, and oracle-difficulty ordering predicts task-pair gaps. Limitations: evidence is restricted to fine-tuned 4B–7B models, corpus sizes cap at 32k (128k for generalization), tasks are largely synthetic with LLM-generated targets, and no variance estimates are reported.
Review complete
Assessment at a glance
5
risk flags identified
● high 0
● medium 3
● low 2
5 strengths · 5 weaknesses · 5 author questions
AI text signal = Binoculars zero-shot detector score over 20 sampled passages (Fast-DetectGPT co-reported) — absence does not prove human authorship, and a flag does not imply misconduct.
Levels reflect verification complexity — not a quality score. Evolve never rates your paper.
Key claims under review
- All 12 commonly used corpus-reasoning benchmark tasks are low-CTC (O(N)) in oracle-call complexity.
- With in-distribution fine-tuning, high-CTC task performance degrades far faster with corpus size than low-CTC (0.851→0.511, −40%, vs 0.910→0.788, −13%, from 2k to 32k).
- Block-sparse and hybrid attention match full attention on low-CTC tasks but suffer large, growing degradation on high-CTC tasks (block-sparse: −26.9% at 2k rising to −65.9% at 32k).
- Length generalization beyond the 32k training window largely fails on high-CTC tasks (4–14% retention at 128k vs 28–100% for low-CTC).
- Oracle-operation difficulty and CTC interact systematically: gaps between matched O(N)/O(N²) task pairs grow with context length ordered by oracle difficulty (§5.2).
Strengths
Principled, teachable formalization of task difficulty
CTC (§2.1) is defined as asymptotic growth of minimal oracle calls with corpus size N; the Figure 2 walkthrough (3 vs 4,950 calls at N=100) cleanly motivates why retrieval is O(N) and contradiction search O(N²), and §2.2 applies it uniformly to 12 established tasks.
Controlled task design that isolates the scaling variable
Paired controls are built in: NIAH-contra is an O(N) control sharing PubMed claim text with O(N²) Contradiction; Outlier has fixed-M (O(N)) vs scale-M (O(N^M)) variants; Strmatch strips all semantics so only the number of comparisons scales (§2.3, App. C).
In-distribution training cleanly targets architectural limits
Broad architectural coverage with a practical new trick
Strong reproducibility support and honest self-criticism
Weaknesses
All conclusions come from task-specialized fine-tuned models
CTC is a posited abstraction, not a proven link to model difficulty
No statistical rigor: single runs, no variance
Residual confounds in the architecture comparisons
Internal metric inconsistencies suggest reporting drift
Full Review Report
$1.99 · one-timeUnlock the complete preliminary analysis Evolve produced for this paper.
Report preview
Scope & Claims
The paper asks what makes corpus-reasoning tasks hard as corpora grow and answers with Corpus Task Complexity (CTC): the asymptotic growth in oracle calls (fixed-context judgments) needed to solve a task as corpus size N grows (§2.1). Surveying 12 established tasks — BEIR retrieval (SciFact, FiQA, MS MARCO), NQ/HotpotQA retrieval variants, MS MARCO rerank, OBLIQ, OOLONG, Amazon outlier detection, NIAH-contra, and Absence — it classifies all as low-CTC, O(N). It contributes 10 high-CTC tasks (§2.3): Contradiction, X-Absence, and QDmatch×3 (O(N²)); Outlier-wiki and Grouping (O(N^M)); Strmatch and Reorder (O(N²)); Textgroups (O(N³)); together forming the 22-task CTC-BENCH evaluated at 2k–32k tokens. Central claims: (1) high-CTC difficulty grows much faster with corpus size even under in-distribution fine-tuning; (2) modeling conclusions drawn from low-CTC evaluations — block-sparse ≈ full attention, hybrid ≈ full, short-context training generalizes — reverse on high-CTC tasks.
The remaining sections cover Methodology Assessment, Statistical Evidence, Results & Reproducibility, Limitations & Risks, and Verdict & Recommendations.
- All 5 strengths & 5 weaknesses, analyzed in detail
- 5 risk flags with severity, section & reviewer questions
- Methods & statistical evidence assessment
- 5 questions a peer reviewer would ask
- Full six-dimension evaluation report & recommendations
One-time purchase · this paper only
One-time purchase, this paper only. AI-generated preliminary analysis — not peer review.
Frequently asked questions
What is Corpus Task Complexity (CTC)?
CTC is a way of classifying corpus-reasoning tasks by how the minimum number of simple 'oracle' checks needed to solve them grows with the number of documents N. A factoid retrieval query needs roughly N checks (one pass, low CTC), while finding all contradictory claim pairs may need roughly N² pair comparisons (high CTC).
What is CTC-BENCH?
A 22-task benchmark suite introduced in this paper: 12 established low-CTC tasks (retrieval, QA, aggregation) plus 10 new high-CTC tasks (contradiction search, cross-corpus absence, query-document matching, topic outlier and grouping, string matching, reordering, and a triple-finding task), evaluated at corpus sizes from 2k to 32k tokens (up to 128k in length-generalization tests). Code and data are publicly released.
Why do efficient attention methods fail on high-CTC tasks?
Block-sparse and hybrid (linear-attention) architectures cut the quadratic cost of full attention and match it on standard retrieval/QA tasks, but the paper shows that on tasks requiring all-pairs or all-group comparisons their performance gap versus full attention grows with corpus size — up to a 65.9% relative loss for block-sparse at 32k tokens.
What are the main limitations of this study?
All evidence comes from task-specific fine-tuned models of 0.8B–7B scale; corpus sizes cap at 32k tokens (128k for length-generalization tests); most high-CTC tasks are synthetic with LLM-generated targets; and the paper reports no variance estimates or significance tests.
About this review
This is an AI-generated preliminary review by Evolve.Pub, produced from the openly available text of the paper. It is not peer review and does not represent the authors' views. The canonical record of the paper is at the publisher link above.
- Figures 1 and 3–7 are line plots; numeric values cited here come from in-text statements and captions, not visual inspection of the curves.
- The extraction includes appendices A–H and appears essentially complete, but some table cells (e.g., Table 3) are garbled; two metric inconsistencies (Grouping: pairwise-F1 in Table 3 vs Kendall-τ in §C.2.2; NIAH-contra: set-F1 vs gold-ID F1) could not be fully resolved from text alone.
- Single arXiv v1 preprint; no peer-review status information was available at review time.
Go deeper on this paper
Wrote a paper? Stress-test it before reviewers do.
Upload your manuscript for the same structured scrutiny — reasoning, statistics, evidence, figures, and reproducibility.