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

1 Introduction

• The motivating challenge is whether systems can answer cross-document questions, such as finding all contradictions in a large corpus.The introduction contrasts these with simple factoid queries.Source: §1 · pp. 1–2
• Corpus Task Complexity characterizes how task difficulty grows with corpus size; the paper introduces 10 tasks whose complexity grows quadratically or faster.Examples range from finding contradictory claims to identifying documents with the rarest topics.Source: §1 · p. 2
• High-CTC performance degrades faster as corpora grow, and block-sparse attention loses substantially to full attention there while nearly matching it on low-CTC tasks.The figure compares in-distribution trained Qwen3.5-4B models across corpus sizes.Source: §1 · p. 2, Figure 1 · p. 2
• Hybrid architectures and length generalization also show larger performance gaps or break down on high-CTC tasks, despite working on low-CTC tasks.Length generalization means fine-tuning on shorter contexts than the intended test context.Source: §1 · p. 2

2.1 Corpus Task Complexity

• CTC is the asymptotic growth in oracle calls needed to solve a task as corpus size N grows, using an oracle whose operation cost is constant in N.The definition focuses on the minimum-call algorithm, though in practice the paper classifies tasks using candidate best algorithms.Source: §2.1 · p. 3
• Factoid retrieval requires O(N) calls, while checking all candidate contradiction pairs can require O(N^2) calls.For 100 documents, exhaustive contradiction checking may require 4,950 calls.Source: §2.1 · p. 3

2.2 Existing Tasks Through the Lens of CTC

• The 12 surveyed retrieval, QA, reranking, aggregation, and aligned-absence tasks all fall into O(N) complexity.The authors describe them as a recent, diverse, representative sample of studied IR and LCLM benchmarks.Source: §2.2 · p. 4

2 Corpus Task Complexity & CTC-BENCH

• CTC-BENCH combines 12 low-CTC tasks with 10 high-CTC tasks; high-CTC tasks grow quadratically or faster with corpus size, whereas most existing benchmarks are low-CTC and grow linearly.The overview separates linear-time tasks from those requiring higher-order comparisons.Source: §2 · p. 3, Table 1 · p. 4, §2.3 · p. 5

2.3 CTC-BENCH and High CTC Tasks

• The new suite includes contradiction search, shuffled-corpus absence, and cross-corpus question-document matching tasks with quadratic pairwise comparisons.The question-document matching variants use FiQA, NaturalQuestions, and HotpotQA material.Source: §2.3 · p. 5
• Other high-CTC tasks include topic outliers and grouping, pairwise sequence matching and reordering, and triple-based Textgroups search.Outlier and grouping scale as O(NM); Textgroups searches over triples and is an O(N^3) example.Source: §2.3 · p. 5

3 Role of Task Complexity on Growing Corpora

• Qwen3.5-4B was trained and evaluated on all 22 CTC-BENCH tasks at context lengths from 2k to 32k.Source: §3 · p. 5
• Except for OBLIQ, the study used in-domain fine-tuning sets to isolate architectural limits from data and generalization.Source: §3 · p. 5
• Tasks used synthetic or semi-synthetic data for controllability and cleaner analysis while being designed to resemble realistic tasks.Source: §3 · p. 5
• High-CTC average performance fell 0.851 → 0.511 (40%) from 2k to 32k, versus low-CTC performance falling 0.910 → 0.788 (13%).Source: §3 · p. 6

4.1 Full vs Block-Sparse Attention

• Block-sparse attention prefills documents independently with limited global attention, and mask-mixing trains with full-attention masks before evaluation with block-sparse masks.Full-attention prefill has quadratic computational complexity.Source: §4.1 · p. 6
• Mask-mixing improves block-sparse performance, especially on many high-CTC tasks and cross-context aggregation such as OOLONG.It helps less on retrieval tasks such as FiQA and NQ; the authors suggest it may distill representations from full attention.Source: §4.1 · p. 6
• −26.9% (2k) to −65.9% (32k): average high-CTC degradation from using block-sparse attention grows with context length.The gap is negligible on low-CTC tasks, except where both approaches perform near zero.Source: §4.1 · pp. 6–7, Figure 3 · p. 7

4.2 Full vs Hybrid

• Hybrid attention often matches or exceeds full attention on low-CTC tasks but degrades substantially on high-CTC tasks.The gap varies by task, and the OLMo models are generally weaker than Qwen3.5.Source: §4.2 · pp. 7–8, Figure 4 · p. 8

4.3 Length Generalization

• At 128k, models trained through 32k retain 28%-100% of low-CTC performance but only 4%-14% of high-CTC performance.The 64k and 128k evaluations use full attention and report performance as a percentage of the 32k score.Source: Figure 5 · p. 8, §4.3 · pp. 8–9
• Across model families and scales, block-sparse attention degrades little on HotpotQA but substantially on Contradiction; smaller Qwen3.5 models degrade faster.The comparison covers three Qwen3.5 sizes and two other model families.Source: Figure 6 · p. 9
• For matched task pairs, the performance gap between OT (N²) and OT (N) grows with context, with larger gaps for harder oracle operations.The authors suggest shorter-context relative degradation may bound or predict degradation at longer contexts and higher CTC classes.Source: Figure 6 · p. 9

5.1 Role of Model Family and Scale

• Across all tested families and scales, block-sparse attention causes little degradation on HotpotQA but substantial degradation on Contradiction.Among Qwen3.5 models, smaller models degrade faster on larger input corpora.Source: §5.1 · p. 9

5.2 Oracle Operation Difficulty

• The analysis pairs four linear-operation tasks with corresponding quadratic-operation tasks to test whether oracle difficulty affects performance differently across CTC classes.CTC measures how oracle-call counts scale with corpus size, not the difficulty of each call.Source: §5.2 · pp. 9–10
• The performance gap between matched quadratic- and linear-operation tasks grows with context length, and its ordering follows oracle difficulty.The authors suggest shorter-context degradation may bound or predict degradation at longer contexts and higher CTC classes.Source: §5.2 · p. 10

6 Related Work

• Corpus reasoning spans longstanding work on information retrieval [Craswell et al., 2025], event ordering, exploratory data analysis, and document interrelatedness [Tillett, 1991].The paper notes that Zhang et al. [2025] studied exhaustive pair generation and that the authors are not the first to propose tasks classifiable as high-CTC.Source: §6 · p. 10
• The paper presents CTC as a unified account of difficulty within complexity classes and connects task complexity to architectural choices.It describes its testbed as the most comprehensive for studying how high-CTC task difficulty grows at scale.Source: §6 · p. 10
• Corpus methods include retrieval-plus-LLM agentic scaffolds and architectures that ingest full corpora, often using more efficient attention.The paper says agentic systems face retrieval challenges and high per-query costs, while architecture methods have mainly been developed on low-CTC tasks.Source: §6 · p. 10

7 Conclusion

• The paper encourages avoiding over-reliance on low-CTC evaluations and treating high-CTC tasks as an impactful long-term open problem.Its investigation also helps explain the success of cheaper linear-cost methods.Source: §7 · p. 10

A Limitations

• Compute limits the in-domain analysis to 32k tokens and length-generalization experiments to 128k tokens, leaving larger corpus-scale settings unexamined.The authors note that many high-CTC tasks already degrade greatly by 32k tokens and show trends of further degradation.Source: A Limitations · p. 14
• The 12-task suite aims to represent previously explored settings but may omit other low-CTC and high-CTC tasks.The authors encourage future work to examine additional tasks and reproduce the findings.Source: A Limitations · p. 14
• The work takes initial steps toward defining and understanding high-CTC tasks but does not solve them.Source: A Limitations · p. 14

B Discussion of Real High CTC Tasks

• Global contradiction and redundancy detection could support systematic synthesis of scientific evidence, fact-checking, and tracking redundancy in long texts.The discussion contrasts this with local keyword searches and describes global analysis as OT(N^2).Source: B Discussion of Real High CTC Tasks · p. 15
• Finding rare or harmful events in large-scale LLM generations is framed as OT(NM), where M is the number of possible phenomena.The discussion says M may be large in long-tail settings, making high-fidelity analysis challenging.Source: B Discussion of Real High CTC Tasks · p. 15
• Reorganizing corpora by importance or semantic structure, including reflecting new trends, may require OT(NM) or OT(N^2).Source: B Discussion of Real High CTC Tasks · p. 15
• Cross-corpus comparisons can examine changes between overlapping corpora or connections between unrelated fields, and often require OT(N^2).Source: B Discussion of Real High CTC Tasks · p. 15
• The authors identify scalable methods and realistic benchmarks for high-CTC tasks as valuable future directions, noting that current approaches can require manual work and heuristics.Source: B Discussion of Real High CTC Tasks · p. 15

C.1 Data Construction

• Evaluations extend to 128k tokens, typically use 500 queries per task, expand distractors across lengths, and keep train and evaluation documents and queries disjoint by default.Source: §C.1 · p. 15
• Training generally uses one epoch over 20,000 examples split evenly across five context budgets, with task-generated examples or established dataset splits.OBLIQ is the exception: its training data is synthesized because it lacks a usable training split.Source: §C.1 · p. 16

C.2.1 OT (N) tasks: one pass over the corpus

• One-pass retrieval tasks include NaturalQuestions, HotpotQA, SciFact, FiQA, MS MARCO, and OBLIQ, with task-specific corpora, golds, and distractors.HotpotQA requires two retrieval steps; OBLIQ uses subjective queries and multiple relevant tweets.Source: §C.2.1 · pp. 16–17
• OBLIQ training examples are synthesized from seed documents using generated oblique queries and an overlap filter; evaluation uses only the benchmark’s Twitter subset.The authors describe this dataset as initial and say better training data may be possible.Source: §C.2.1 · p. 17
• Other OT(N) constructions include classification aggregation, positional absence detection, rating or category outliers, and a single-needle contradiction control.Oolong classifies items before aggregation; Absence aligns two ordered corpus copies, while the contradiction control isolates all-pairs search from claim-text effects.Source: §C.2.1 · pp. 17–18

C.2.2 OT (NM) tasks: categorization

• Categorization tasks include finding the least-represented Wikipedia source article, with both growing-M and fixed-M variants, and grouping OpenAlex abstracts at sampled hierarchy levels.For grouping, the sampled level sets category granularity, and M naturally grows with corpus size under the construction.Source: §C.2.2 · p. 18

C.2.3 OT (N 2) tasks: all-pairs search

• All-pairs tasks include matching sparse question-document pairs among N × N combinations and finding unmatched documents across near-identical PubMed corpora.The matching variants draw on NaturalQuestions, HotpotQA bridge, and FiQA; the cross-corpus absence task uses exact-copy twins.Source: §C.2.3 · p. 18
• PubMed contradiction search plants three hidden pairs, one sentence per pair LLM-written, but subtle annotation artifacts may make it easier than realistic contradiction search.Source: §C.2.3 · p. 18
• String matching tests contiguous word-run pairs, while book-segment reordering requires comparisons between arbitrary pairs rather than relying on a global positional prior.Source: §C.2.3 · p. 18

C.2.4 Beyond OT (N 2)

• Textgroups asks for triples whose feature values sum to a target; its nontrivial per-document counting operation makes its CTC greater than quadratic.The construction plants exactly K triples and verifies by brute force that no others exist.Source: §C.2.4 · p. 19

• Each example contains documents, queries, answers, and gold document indices; document counts come from evaluation files and document length is measured in characters.Source: D Data Statistics / Evaluation · p. 19
• Evaluation typically uses vLLM, with a modified version for block-sparse inference, and generation uses greedy decoding.Source: D Data Statistics / Evaluation · p. 19
• Table 3 reports median document counts for each task at approximate 2k–32k token targets and median document length at the deepest available rung.Source: Table 3 · p. 19

E.1 Model Scale

• Smaller model scales sometimes cannot learn challenging high-CTC tasks, including Reordering and QDMatch (NQ).Figure 7 compares dense and block-sparse attention across model scales and includes full-model performance on Qwen3.5 scales.Source: §E.1 · p. 19, Figure 7 · p. 20

E.2 Model Family

• Block-sparse attention struggles greatly on contradiction across model families; Figure 8 compares full and block-sparse attention for several families.Source: §E.2 · p. 19, Figure 8 · p. 20

F Training Hyperparameters

• Training comparisons use full-parameter fine-tunes from the same base checkpoint and recipe, varying the attention mask; mask mixing is trained with a curriculum from p=0.8 to 0 and evaluated with pure block-sparse attention.The stated defaults include AdamW, learning rate 5×10−5, one epoch, global batch 8, and linear warmup then decay.Source: F Training Hyperparameters · p. 20

G GPU Resources / Compute

• The investigation used roughly 3k A100 hours and 1k H200 hours; the authors estimate Figure 3 could be reproduced in under 500 hours with 8×H100 GPUs.Source: G GPU Resources / Compute · p. 20

H.1.1 NQ (factoid retrieval)

• Retrieval examples span factoid and bridge questions, contradiction search, scientific-claim retrieval, financial advice, and passage retrieval.The examples include a single relevant document, multiple bridge documents, and multi-document retrieval.Source: §H.1.1 · p. 21, §H.1.2 · p. 21, §H.1.3 · p. 21

H.1.7 MS MARCO reranking

• Reranking asks for an ordered relevance ranking, while OBLIQ asks for tweets matching a subjective, multi-clause description.The examples show a target top-10 ranking and five gold tweet IDs, respectively.Source: §H.1.7 · pp. 22–23, §H.1.8 · p. 23

H.2.2 Grouping (OpenAlex)

• The larger-scale examples include identifying passages on a different topic among a 55-chunk set (four shown) and clustering 20 OpenAlex papers into 15 groups at concept level L=3.The grouping target was a labeled partition, but only document IDs were scored.Source: §H.2.1 · p. 25, §H.2.2 · p. 25

H.3.1 Contradiction (PubMed)

• H.3 examples ask models to identify contradictory claim pairs, passages missing across two corpora, and string pairs sharing a contiguous three-word run.The supplied examples give three gold contradiction pairs, three missing passage IDs, and three qualifying string pairs.Source: §H.3.1 · p. 26, §H.3.2 · p. 26, §H.3.3 · pp. 26–27

H.3.4 QDMatch (NQ source)

• QDMatch asks for every relevant query-document pair, using NQ, bridge-question HotpotQA, and financial-question FiQA examples.The NQ example has three relevant pairs among 20 queries by 20 documents; the HotpotQA variant gives each relevant query two gold documents, and FiQA uses cross-encoder-cleaned negatives for sparse judgments.Source: §H.3.4 · p. 27, §H.3.5 · p. 27, §H.3.6 · pp. 27–28

H.3.7 Reorder (Gutenberg)

• The Reorder example asks for the permutation that restores shuffled segments from one book to their original order.The 50-segment ordering is scored by Kendall-τ against the true permutation.Source: §H.3.7 · p. 28

H.4.1 Textgroups

• The task is to find every group of three passages whose hidden noun counts total exactly 70; the gold groups are [1, 11, 12] and [2, 14, 17].Their counts are 34+31+5 and 13+17+40, respectively.Source: §H.4.1 · p. 28
• Closed, pairwise-disjoint noun, verb, and adjective lexicons make each passage’s noun count unambiguous, while varied sentence structures keep count from proxying for passage length.Source: §H.4.1 · p. 28