免费午餐终结：语料库任务复杂度随规模增长而关键

# Corpus Task Complexity Matters as Corpora Grow
Source: [https://arxiv.org/html/2609.29245](https://arxiv.org/html/2609.29245)
## No More Free Lunch: Corpus Task Complexity Matters as Corpora Grow

Amanda Bertschγ\\gammaβ\\betaJacob Steinhardtα\\alphaSewon Minα\\alphaβ\\betaAffiliation:αUC BerkeleyβAllen Institute for AIγCarnegie Mellon UniversityEmail:[prasann@berkeley\.edu](mailto:)

###### 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 ofCorpus 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\.

## 1Introduction

Computational tools enable us to conduct search over large digital corpora—from scientific literature to the internet—but is it yet possible to develop systems that could, for example,*find all contradictions*in a large corpus? Given the wealth of valuable information contained in large corpora, researchers have built diverse systems to extract and analyze this information, from work in information retrieval\([Craswell et al\., 2025](https://arxiv.org/html/2609.29245#bib.bib2);[Hou et al\., 2025](https://arxiv.org/html/2609.29245#bib.bib3)\)to summarization\([Kociský et al\., 2017](https://arxiv.org/html/2609.29245#bib.bib15)\)\. We refer to these collectively as*corpus reasoning*tasks, but they can vary substantially in their complexity over the corpus, ranging from simple factoid queries like “When was Ralph Lauren founded?”, to tasks requiring extensive cross\-document interaction, such as “Find all contradicting claims in this biology literature” or “What are the outliers in the LLM agent trace corpus?”\.

Long\-context language models \(LCLMs\) trained to process large inputs \(e\.g\., 32K tokens or more\) are promising for corpus tasks—with softmax attention enabling direct retrieval and reasoning across parts of the conditioned corpus\. Modern LCLMs achieve strong performance on many existing synthetic long\-context benchmarks\([Yen et al\., 2024](https://arxiv.org/html/2609.29245#bib.bib14);[Bai et al\., 2024](https://arxiv.org/html/2609.29245#bib.bib21);[Chen et al\., 2026](https://arxiv.org/html/2609.29245#bib.bib20)\), even with various efficient approaches used to reduce their computational cost\([Yang et al\., 2024](https://arxiv.org/html/2609.29245#bib.bib28);[Beltagy et al\., 2020](https://arxiv.org/html/2609.29245#bib.bib9)\)\. But given the lack of clear characterization of what makes corpus reasoning tasks difficult on large corpora, it remains unclear whether these successes apply to all corpus reasoning tasks, particularly more complex tasks\.

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\.We begin by defining*corpus task complexity*\(CTC\), which characterizes a task by how the number of operations required to solve it scales with corpus size\. For example, the number of local operations required to retrieve a fact usually grows linearly with corpus size, since each document need only be checked once to find where the fact is located\. In contrast, a task such as “Find all contradicting claims in the literature” involves comparing all pairs of claims, resulting in quadratic growth\. Through this lens, we survey 12 diverse corpus reasoning tasks commonly used to evaluate LCLMs and find them to all grow linearly in difficulty with corpus size \(which we call*low\-CTC*\)\. We then introduce 10 diverse tasks whose complexity grows quadratically or faster \(*high\-CTC*tasks\), ranging from identifying all contradictory claims in a corpus to finding documents with the rarest topics\.

Using this benchmark suite,CTC\-Bench, we evaluate a range of LCLMs across corpus sizes from 2K to 32K tokens\. We first find that with increasing corpus size, performance degrades faster on average on high\-CTC tasks than on low\-CTC tasks \(Figure[1](https://arxiv.org/html/2609.29245#S1.F1)\(a\)\)\. More importantly, however,we find that high\-CTC task results frequently reverse modeling conclusionsdrawn solely from low\-CTC evaluations\. For example, block\-sparse attention—an efficient attention variant often used for corpus reasoning\([Xiao et al\., 2025](https://arxiv.org/html/2609.29245#bib.bib13)\)—shows minimal degradation on low\-CTC tasks, yet on high\-CTC tasks it sees large performance drops relative to full attention \(Figure[1](https://arxiv.org/html/2609.29245#S1.F1)\(b\)\)\. Similar discrepancies occur for other modeling decisions: hybrid architectures that alternate linear and full attention exhibit larger performance gaps on high\-CTC tasks; and length generalization—fine\-tuning a long\-context model on shorter contexts than the intended context length at test time\([Gao et al\., 2024](https://arxiv.org/html/2609.29245#bib.bib46)\)—can work for low\-CTC tasks but breaks down on high\-CTC tasks\.

To summarize, our results show that evaluations including high\-CTC tasks reveal hidden costs to many common modeling choices, and that there is no free lunch: full attention becomes quadratically intractable on large corpora, but efficient attention mechanisms that appear lossless under existing low\-CTC evaluations can lead to substantial degradation on high\-CTC tasks\. Solving high\-CTC tasks on large corpora is a challenging long\-term problem, and we encourage more research into scalable architectures that can handle both low*and*high\-CTC tasks\. To support this effort, we releaseCTC\-Bench, along with our code and data\.

## 2Corpus Task Complexity &CTC\-Bench

Figure 2:Circles represent documents, with shaded circles for the gold documents\. As corpus sizeN=\|C\|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\)\.What most strongly determines corpus task difficulty? We propose*Corpus Task Complexity \(CTC\)*, a definition of task difficulty based on how a task’s difficulty scales with corpus size \(§[2\.1](https://arxiv.org/html/2609.29245#S2.SS1)\), which we walk through with two tasks \(shown in Figure[2](https://arxiv.org/html/2609.29245#S2.F2)\)\. We find that most existing benchmarks are low CTC—their complexity grows linearly with corpus size \(§[2\.2](https://arxiv.org/html/2609.29245#S2.SS2)\)—then introduce a new class of high CTC tasks, whose complexity grows quadratically or faster \(§[2\.3](https://arxiv.org/html/2609.29245#S2.SS3)\)\.

### 2\.1Corpus Task Complexity

Define a corpusCCto be an unstructured set ofNNdocuments\{d1,…,dN\}\\\{d\_\{1\},\\ldots,d\_\{N\}\\\}, where eachdid\_\{i\}is a sequence of tokens\. A corpus reasoning taskTTis a set of same\-type corpus\-question\-answer samples\(Ci,qi,ai\)∈T\(C\_\{i\},q\_\{i\},a\_\{i\}\)\\in T\. For instance a factoid retrieval task sample could be \(Ci=C\_\{i\}=Wikipedia,qi=q\_\{i\}=*“When was Ralph Lauren founded?”*,aia\_\{i\}=*“1967”*\), and a contradiction task sample could be \(Ci=C\_\{i\}=CommonCrawl,qi=q\_\{i\}=*“Find all contradictions”*,ai=a\_\{i\}=list of contradicting pairs withinCiC\_\{i\}\)\.

To understanding corpus reasoning tasks, we define a notion of complexity called*corpus task complexity \(CTC\)*\. Imagine that we can call anoracle\(e\.g\. an LM\-judge\) that can answer questions over small contexts with O\(1\)\-length in corpus size\. CTC is the asymptotic growth in oracle calls needed to solve tasks as a function of corpus size N\.

Specifically, letATA\_\{T\}be an algorithm composed of oracle calls that solvesall\(Ci,qi,ai\)∈T\(C\_\{i\},q\_\{i\},a\_\{i\}\)\\in T, wherefAT​\(Ci,qi\)f\_\{A\_\{T\}\}\(C\_\{i\},q\_\{i\}\)indicates oracle call count, and we constrainATA\_\{T\}to be the algorithm with lowest possible call count across samples\. TaskTTisOT​\(g​\(N\)\)O\_\{T\}\(g\(N\)\)if there exists some constantα\\alphasuch thatfAT​\(Ci,qi\)≤α​g​\(N\)f\_\{A\_\{T\}\}\(C\_\{i\},q\_\{i\}\)\\leq\\alpha g\(N\)for all\(Ci,qi,ai\)∈T\(C\_\{i\},q\_\{i\},a\_\{i\}\)\\in T\. In practice, as proving the optimalATA\_\{T\}can be challenging, we classify CTC with*candidate*best algorithms for tasks given unstructured corpora\.

Example 1:\(Figure[2](https://arxiv.org/html/2609.29245#S2.F2), blue\) To solve factoid retrieval queries likeq=q=*“When was Ralph Lauren founded?”*with oracle calls,ATA\_\{T\}may be to runoracle⁡\(isrelevant,di,q\)\\mathrm\{oracle\}\(\\mathrm\{isrelevant\},d\_\{i\},q\)individually on alldi∈Cd\_\{i\}\\in C\. SincefAT​\(Ci,qi\)f\_\{A\_\{T\}\}\(C\_\{i\},q\_\{i\}\)is justNN, and less operations aren’t possible, this task isOT​\(N\)O\_\{T\}\(N\)\.111CTC should*not*be confused with individual online or offline cost, which combine to become overall cost\. For example, nearest neighbors search often hasO⁡\(l​o​g​\(N\)\)O\(log\(N\)\)*query\-time*complexity, but still requiresO⁡\(N​l​o​g​\(N\)\)O\(Nlog\(N\)\)*build\-time*cost\.

Example 2:\(Figure[2](https://arxiv.org/html/2609.29245#S2.F2), orange\) To*“Find all contradicting claim pairs\.”*with oracle calls,ATA\_\{T\}may be to runoracle⁡\(contradicts,di,dj\)\\mathrm\{oracle\}\(\\mathrm\{contradicts\},d\_\{i\},d\_\{j\}\)on all viable document pairs\. While priors or corpus structure could lower this, exhaustively checking*all*possible pairs will generally require quadratic oracle calls in corpus size \(e\.g\. 4,950 calls for 100 documents\)—making the taskOT​\(N2\)O\_\{T\}\(N^\{2\}\)\.

Since CTC corresponds to minimal computation*necessary*to solve tasks with growingNN, we posit that it will correspond to empirical trends for even black\-box methods applied to corpus tasks \(e\.g\. LCLMs, dense retrievers\)\. Similar methods may work for tasks within the same CTC, and on larger corpora anOT​\(N2\)O\_\{T\}\(N^\{2\}\)task may demand methods with greater inference computation\.

Not all same\-CTC tasks are identical—retrieval queries with oracle calls involving exact word matches are harder in a constant sense than ones involving abstract relationships, and such differences may even multiply at higher CTC\. But by defining task CTC we can better explain what underlies a task’s difficulty, and make better modeling decisions to solve it\.

### 2\.2Existing Tasks Through the Lens of CTC

Table 1:Overview of the 22CTC\-BenchTasks\.Linear\-time tasks are shown on the left; tasks requiring higher\-order comparisons are shown on the right \(details, examples in Appendix[H](https://arxiv.org/html/2609.29245#A8)\)Which CTC categories do existing corpus reasoning tasks belong to? To answer this, we examine a range of 12 well\-established existing tasks\. We introduce tasks in the order shown in Table[1](https://arxiv.org/html/2609.29245#S2.T1)\(left\):

Information retrieval is arguably the best\-studied corpus reasoning task\. Within it we examine a synthetic recall*NIAH\-contra*task, standard*SciFact, FiQA, and MS\-MARCO*tasks taken from BEIR\([Thakur et al\., 2021](https://arxiv.org/html/2609.29245#bib.bib38)\), and the twitter set of the modern*OBLIQ*\([Tchuindjo et al\., 2026](https://arxiv.org/html/2609.29245#bib.bib39)\)benchmark\. While ranging in difficulty, as discussed in our earlier factoid example these tasks areOT​\(N\)O\_\{T\}\(N\)\.

We include retrieval variants of two factoid QA datasets: NaturalQuestions \(*NQ*\)\([Kwiatkowski et al\., 2019](https://arxiv.org/html/2609.29245#bib.bib40)\), a single\-hop task, and HotpotQA\([Yang et al\., 2018](https://arxiv.org/html/2609.29245#bib.bib17)\), a multi\-hop task\. Both calloracle⁡\(hasanswer,q,di\)\\mathrm\{oracle\}\(\\mathrm\{hasanswer\},q,d\_\{i\}\)\. Since, even in the multi\-hop case requiring multiple retrieval steps, only a constant number of passes are required—one retrieval step to find the first hop, and one retrieval step to find the second hop—we classify these also asOT​\(N\)O\_\{T\}\(N\)\. Likewise, MSMARCO rerank, which involves finding top\-10 most relevant documents to a query, given a small k, is at most a constant number of retrieval passes, and thus is alsoOT​\(N\)O\_\{T\}\(N\)\.

We include several corpus aggregation tasks\.OOLONG\([Bertsch et al\., 2025](https://arxiv.org/html/2609.29245#bib.bib19)\)involves distributional or counting questions about class labels of documents\.Outlier \(Amazon\)involves finding the least common star or product category in a set of reviews\. Given a fixed set of class labels, a single pass oforacle⁡\(classify,di\)\\mathrm\{oracle\}\(\\mathrm\{classify\},d\_\{i\}\)\(e\.g\. 2\-stars, 4\-stars\) calls with lightweight aggregation is typically sufficient for these tasks, making themOT​\(N\)O\_\{T\}\(N\)\. Lastly, we include a 2\-corpusAbsencetask based on AbsenceBench\([Fu et al\., 2025](https://arxiv.org/html/2609.29245#bib.bib37)\)—searching for deletions in near\-identical Project Gutenberg passages\. Since positions are aligned, the oracle isoracle⁡\(matches,di,di−N\)\\mathrm\{oracle\}\(\\mathrm\{matches\},d\_\{i\},d\_\{i\-N\}\), whereNNis individual corpus size\. Only a single pass over the second corpus is needed here, so this is*also*OT​\(N\)O\_\{T\}\(N\)\.

The above tasks constitute a recent, diverse, and representative sample of the most studied IR and LCLM benchmark tasks, yetthey all fall intoOT​\(N\)O\_\{T\}\(N\)\.

### 2\.3CTC\-Benchand High CTC Tasks

Our definition of CTC suggests that a variety of useful tasks fall into higher complexity classes, yet such tasks, while explored at small scale \(e\.g\. event re\-ordering[Chambers et al\. \(2014\)](https://arxiv.org/html/2609.29245#bib.bib41)\), are understudied for larger corpora, especially in the context of LCLMs\. We thus, to enable our analysis, construct a diverse suite of 10 high\-CTC tasks \(Table[1](https://arxiv.org/html/2609.29245#S2.T1), right\)\. We call these—along with the 12 low\-CTC tasks—CTC\-Bench222We often include synthetic / semi\-synthetic tasks for controllability and cleaner analysis, though we design allCTC\-Benchtasks to structurally resemble realistic tasks \(see Appendix[B](https://arxiv.org/html/2609.29245#A2)\):

\(a\)*Contradiction*qi=q\_\{i\}=*“Find all the contradicting claim pairs in the corpus\.”*,aia\_\{i\}is a list of 3 contradicting claim pair IDs\. It uses LLM\-generated contradictions to pubmed abstract claims\([Jin et al\., 2019](https://arxiv.org/html/2609.29245#bib.bib34)\), and is as discussed earlierOT​\(N2\)O\_\{T\}\(N^\{2\}\)\(Section[2\.1](https://arxiv.org/html/2609.29245#S2.SS1)\) \.

\(b\)*X\-Absence*qi=q\_\{i\}=*“Given near\-identical corpus A and B with shuffled chunks, find chunks that are only in one corpus”*,aia\_\{i\}is a list of chunks only in one of either A or B\. Alldid\_\{i\}are chunks of a Project Gutenberg passage\.CAC\_\{A\}andCBC\_\{B\}\(NNchunks each\) are shuffled to prevent positional bias \(unlike Absence which is ordered\), so totaloracle⁡\(matches,di,dj\)\\mathrm\{oracle\}\(\\mathrm\{matches\},d\_\{i\},d\_\{j\}\)calls areOT​\(N2\)O\_\{T\}\(N^\{2\}\)\.

\(c\-e\)*\(QDmatch\)\-FiQA, NQ, HotpotQA*qiq\_\{i\}=*“Given corpus A with single\-sentence questions and B with documents, find \(question, document\) pairs where documents answer questions”*,aia\_\{i\}is a list of 3 matching pair IDs\. We use 3 such settings, using retrieval questions and documents from the FiQA, NQ, and HotpotQA tasks to construct this task\. SinceCAC\_\{A\}andCBC\_\{B\}are sizeNNeach, cross checking all pairs withoracle⁡\(isrelevant,di,dj\)\\mathrm\{oracle\}\(\\mathrm\{isrelevant\},d\_\{i\},d\_\{j\}\)isOT​\(N2\)O\_\{T\}\(N^\{2\}\)\.

\(f\)*Outlier \(wiki\)*qiq\_\{i\}=*“Given the corpus with chunks discussing different topics, identify chunks belonging to the least common topic”*,aia\_\{i\}is a list of minority topic chunk IDs\. We source chunks \(did\_\{i\}\) fromMMWikipedia pages, where the “topic” is the page source \(e\.g\. “Horses”\)\. Unlike OOLONG, which has fixed classes, page topics are diverse and don’t repeat across corpora\. Givenoracle⁡\(samecategory,di,dj\)\\mathrm\{oracle\}\(\\mathrm\{samecategory\},d\_\{i\},d\_\{j\}\), since each new document only needs to check one document per category, this isOT​\(N​M\)O\_\{T\}\(NM\)\. To test this we include an Outlier \(fixMM\) setting whereMMstays constant \(OT​\(N\)O\_\{T\}\(N\)\) and Outlier \(scaleMM\) whereMMgrows proportional toNN\(OT​\(N2\)O\_\{T\}\(N^\{2\}\)\)\.

\(g\)*Grouping*,qiq\_\{i\}=*“Group the following scientific abstracts intokkgroups”*,aia\_\{i\}is a dictionary which must havekkkeys and put abstracts in the same topic group together \(notekkincreases naturally withNN\)\. Abstracts \(did\_\{i\}\) and true topic labels \(e\.g\. Biology, Plant Biology\) are mined from OpenAlex\([Priem et al\., 2022](https://arxiv.org/html/2609.29245#bib.bib33)\)\. This has the the same structure as Outlier \(wiki\) and isOT​\(N​M\)O\_\{T\}\(NM\)\.

\(h\)*Strmatch*,qiq\_\{i\}=*“Find word sequences with at least k words in common”*,aia\_\{i\}= 3 pair IDs that match\.did\_\{i\}are random noun sequences\. Callingoracle⁡\(hascommonk,di,dj\)\\mathrm\{oracle\}\(\\mathrm\{hascommonk\},d\_\{i\},d\_\{j\}\), the task requires searching overOT​\(N2\)O\_\{T\}\(N^\{2\}\)pairs\. This task serves as a synthetic control for other pairwise tasks\.

\(i\)*Reorder*\([Bai et al\. \(2024\)](https://arxiv.org/html/2609.29245#bib.bib21)\),qiq\_\{i\}=*“Given the passage \(chunks have been randomly shuffled\), output the original ordering\.”*,aia\_\{i\}is an ID list of lengthNNwith true ordering, anddid\_\{i\}are sentences from a Project Gutenberg passage\. If we useoracle⁡\(directlyneighbors,di,dj\)\\mathrm\{oracle\}\(\\mathrm\{directlyneighbors\},d\_\{i\},d\_\{j\}\), this requires brute\-force checking all pairs to recover the order \(OT​\(N2\)O\_\{T\}\(N^\{2\}\)\)\.

\(j\)*Textgroups*,qiq\_\{i\}=*“Find groups of 3 passages whose adjective count add ups to t\.”*given Project Gutenberg chunks, where property and countttvary \(e\.g\. 67 nouns\)\. With calls tooracle⁡\(propertysum,di,dj,dk\)\\mathrm\{oracle\}\(\\mathrm\{propertysum\},d\_\{i\},d\_\{j\},d\_\{k\}\)searching over all triples, we include it as anOT​\(N3\)O\_\{T\}\(N^\{3\}\)exemplar\.

## 3Role of Task Complexity on Growing Corpora

Having established CTC andCTC\-Bench, we now evaluate a range of models to understand how well they perform on these tasks\. In particular, we focus on performance as a function of corpus size:*How challenging do high\-CTC tasks become as corpus size grows?*

Experimental SetupWe train Qwen3\.5\-4B individually for all 22CTC\-Benchtasks, ranging from 2k to 32k context length in training and evaluation\. For all tasks except OBLIQ \(where we use synthetic data, Appendix[C](https://arxiv.org/html/2609.29245#A3)\), we use existing or generated in\-domain fine\-tuning sets to isolate architectural limits independent of data and generalization\.

We always train for 1 epoch on 20k datapoints per task \(except for OBLIQ and SciFact\), with evenly split examples across context lengths \(matching the corpus sizes we evaluate on\)\. We train with full fine\-tuning, with a learning rate of5×10−55\\times 10^\{\-5\}\. All tasks use this prompt format:

\[Initial\]1:\[Doc 1 content\] …N:\[Doc N content\]\[Query\]\[Answer\]

Result: High\-CTC Task Performance Drops More Rapidly Than Low\-CTC\.We plot in Figure[1](https://arxiv.org/html/2609.29245#S1.F1)\(left\)averages across tasksof full attention performance for all High\-CTC \(orange\) and Low\-CTC \(blue\) tasks acrossCTC\-Bench\(task\-individual plots in Figure[3](https://arxiv.org/html/2609.29245#S4.F3)\)\. Average performance drops0\.910→0\.7880\.910\\rightarrow 0\.788\(13%\) from 2k to 32k on low\-CTC \(10 out of 12 tasks degrade less than0\.10\.1in performance\) but on high\-CTC tasks average performance drops0\.851→0\.5110\.851\\rightarrow 0\.511\(40%\) from 2k to 32k \(7 of 10 tasks drop over0\.10\.1in performance\)\. In aggregate, even with in\-distribution training, high complexity task difficulty grows much faster on larger corpora\.

## 4Rethinking Free Lunches With CTC

In the previous section, we show that high\-CTC tasks often degrade at larger corpus sizes much faster than more commonly studied low\-CTC tasks—suggesting that even costly full attention models are insufficient at scale for high\-CTC tasks\. But how does this relate to the large body of prior LCLM work that has predominantly focused on*reducing*LCLM computation? We revisit 3 common modern LCLM choices from the lens of CTC: block\-sparse attention \(§[4\.1](https://arxiv.org/html/2609.29245#S4.SS1)\), hybrid architectures \(§[4\.2](https://arxiv.org/html/2609.29245#S4.SS2)\), and length generalization from short train contexts \(§[4\.3](https://arxiv.org/html/2609.29245#S4.SS3)\)\.

### 4\.1Full vs Block\-Sparse Attention

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\.In a regular Transformer model \(full attention\), pre\-filling a corpus has quadratic computational complexity\. Motivated by the fact that in corpus reasoning, the input is a collection of independent documents, much prior work has tried\([Beltagy et al\., 2020](https://arxiv.org/html/2609.29245#bib.bib9);[Zaheer et al\., 2020](https://arxiv.org/html/2609.29245#bib.bib25);[Gollapudi et al\., 2026](https://arxiv.org/html/2609.29245#bib.bib48);[Xiao et al\., 2025](https://arxiv.org/html/2609.29245#bib.bib13)\)block\-sparse attention: pre\-filling each document independently so that they attend to tokens within the same document only, with only a small number of query and answer tokens attending globally\. These approaches have been shown effective, though often limited to evaluation onOT​\(N\)O\_\{T\}\(N\)settings like QA, retrieval, and in\-context learning\.

We investigate several decisions reducing computation from full attention, but what if we instead apply*more*computation to cheap methods? Our block\-sparse attention implementation follows that of\([Xiao et al\., 2025](https://arxiv.org/html/2609.29245#bib.bib13)\)333Qwen3\.5 models use 75% gated delta\-net layers \(already linear\), so we only apply block\-sparse to remaining 25%, but we additionally propose a new*mask\-mixing*technique: during block\-sparse attention training, with probabilityppa training batch uses the full\-attention mask instead of the block\-sparse one, wherep=0p=0indicates original block\-sparse attention, andp=1p=1indicates full attention \(we anneal on a curriculum fromp=0\.8p=0\.8top=0p=0during training\)\. During evaluation, block\-sparse attention is used for all inputs\.

Mask\-Mixing Frequently Improves Block\-Sparse\.We evaluate mask\-mixing on a 10 task subset that we callCTC\-Bench\-10, that we select to cover diverse task structures and difficulties across CTC classes inCTC\-Bench\(results in Figure[5](https://arxiv.org/html/2609.29245#S4.F5), Left\)\. We find mask\-mixing greatly improves block\-sparse attention, and*consequently apply it to all block\-sparse experiments*\. Specifically, while it helps less on retrieval settings like FiQA and NQ, we find that on many High\-CTC tasks and tasks requiring aggregation across context like OOLONG, mask\-mixing improves block\-sparse performance—potentially by distilling representations for tasks from the more computationally expressive full attention\.

Full vs Block\-Sparse Gap Grows Faster in High\-CTC\.Figure[3](https://arxiv.org/html/2609.29245#S4.F3)shows degradation and comparisons between full and block\-sparse attention for the fullCTC\-Bench\. On low\-CTC tasks, the gap between full and block\-sparse attention is negligible*for all tasks*—reproducing much prior work\([Beltagy et al\., 2020](https://arxiv.org/html/2609.29245#bib.bib9);[Gollapudi et al\., 2026](https://arxiv.org/html/2609.29245#bib.bib48)\), we find that block\-sparse gives a free lunch of comparable performance \(sometimes even better\) while being much cheaper\. However, across all high\-CTC tasks, choosing block\-sparse attention over full attention leads to worse performance, despite our own improvements through mask\-mixing\. Unless the task is so difficult that both approach zero \(e\.g\. Textgroups, Reorder\), this gap monotonically grows at longer contexts\. Averaged across tasks, the performance degradation from using block\-sparse on high\-CTC is−26\.9%\-26\.9\\%\(2k\),−33\.0%\-33\.0\\%\(4k\),−43\.7%\-43\.7\\%\(8k\),−57\.4%\-57\.4\\%\(16k\) and−65\.9%\-65\.9\\%\(32k\)\. This supports a central theme—decisions that did not matter for low\-CTC matter greatly on high complexity tasks\.

Figure 4:*Hybrid vs Full Models*We plotCTC\-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\.
### 4\.2Full vs Hybrid

Beyond block\-sparse attention, alternative architectures such as state\-space\-models \(SSMs\)\([Katharopoulos et al\., 2020](https://arxiv.org/html/2609.29245#bib.bib26);[Gu and Dao, 2023](https://arxiv.org/html/2609.29245#bib.bib27)\)and adjacent approaches like*gated delta net \(GDN\)*\([Yang et al\., 2024](https://arxiv.org/html/2609.29245#bib.bib28)\)have also enabled attention to reduce computational complexity\. Specifically, these methods replace all\-to\-all token interactions with a recurrent state update, giving linear computation and constant memory\. While this has shown promise, pure\-GDN has, even at low\-CTC, proven insufficient—language models like Qwen3\.5\([Qwen Team, 2026](https://arxiv.org/html/2609.29245#bib.bib32)\)have mixed GDN with full attention rather than replacing it\.

Strong performance of Qwen3\.5 on long\-context benchmarks[Bai et al\. \(2024\)](https://arxiv.org/html/2609.29245#bib.bib21)\) and prior comparisons of full vs hybrid architectures\([Merrill et al\., 2026](https://arxiv.org/html/2609.29245#bib.bib47)\)have suggested hybrid architectures to be comparable or even better than full attention, but does this free lunch apply to high\-CTC tasks? To do a controlled test of this question, we compare OLMo\-3\-7B\([Ettinger et al\., 2025](https://arxiv.org/html/2609.29245#bib.bib44)\)vs OLMo\-3\-7B\-Hybrid\([Merrill et al\., 2026](https://arxiv.org/html/2609.29245#bib.bib47)\), the closest open\-weight comparison between hybrid and full architectures\. Note that since Olmo3 by default uses sliding window attention, we adapt it to a full\-attention version with a 100M\-token continued\-pretraining phase on Dolma3\-Longmino data \(0\.1% of its mid\-training budget\)\. OLMo\-3\-7B\-Hybrid is already mid\-trained natively on this data\.

Hybrid Underperforms Full Attention on High\-CTC Tasks\.We plot individual task results on the 10CTC\-Bench\-10 tasks in Figure[4](https://arxiv.org/html/2609.29245#S4.F4)\. Similar to block\-sparse attention, hybrid attention often leads to no degradation compared to full attention on low\-CTC tasks \(in fact doing better at 32k\), but leads to large degradation on high\-CTC\. Note that these numbers are affected by OLMo models being generally weaker than Qwen3\.5, and while overall trends are consistent, the gap varies by task, e\.g\. QDmatch \(NQ\) vs Outlier \(wiki, ScaleMM\)\.

Figure 5:\(Left\)*Gain of curriculum mask\-mixing over pure block\-sparse training \(no mixing\)*, averaged across 2k–32k contexts onCTC\-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\.
### 4\.3Length Generalization

Our work shows that even up to the relatively small scale of 32k tokens, high\-CTC tasks already degrade greatly—scaling data sufficiently, especially for larger corpora, becomes increasingly important\. But LCLM training is costly\. Given these prohibitive costs, much work has sought to use short\-context data to generalize to longer contexts \(training only on short versions of tasks or short instruction\-tuning data\)\. Such work has successfully shown generalization on a variety of tasks past lengths used in fine\-tuning\([Gao et al\., 2024](https://arxiv.org/html/2609.29245#bib.bib46);[Peng et al\., 2023](https://arxiv.org/html/2609.29245#bib.bib42);[Mehta et al\., 2026](https://arxiv.org/html/2609.29245#bib.bib43)\)\. However, these results have predominantly been demonstrated only on low\-CTC settings\.

High\-CTC Tasks May Generalize Worse to Longer Contexts\.We evaluate 2k\-32k\-trained models at 64k and 128k onCTC\-Bench\-10\. Note this does not require context extension as Qwen3\.5\-4B’s native context is 2̃56K tokens\. We plot results in Figure[5](https://arxiv.org/html/2609.29245#S4.F5)\(right\) with full attention, showing percentage of 32k performance retained on the y\-axis to increase comparability\. At 128k context low\-CTC ranges from 28%\-100% while high\-CTC ranges from 4%\-14%—all high\-CTC points fall below low\-CTC points\. We find these trends at only 128k tokens, and it’s likely that this issue may become even more pronounced at larger corpus scales \(e\.g\. 1 million\+ tokens\)\. Taken together with our prior results, this poses a conundrum: full attention is too costly to scale to large corpora, but many modeling decisions that make LCLMs tractable for larger corpora cause degradation on high\-CTC tasks\.

## 5Analyses: Model Scale, Operation Difficulty

We so far show that high\-CTC often translates to tasks becoming much harder on larger corpora and how various “free lunches” that have been demonstrated on common tasks don’t apply on high\-CTC tasks\. In this final section, we analyze how factors beyond complexity, both modeling \(model family, model scale, §[5\.1](https://arxiv.org/html/2609.29245#S5.SS1)\) and task\-specific \(oracle difficulty, §[5\.2](https://arxiv.org/html/2609.29245#S5.SS2)\) interplay with our previous findings\.

### 5\.1Role of Model Family and Scale

Are our findings robust to different model scales and families? To answer this question, we sample two tasks: HotpotQA retrieval, one of the most commonly evaluated low\-CTC tasks inCTC\-Bench, and Contradiction, a representative high\-CTC task\. We train with three model families \(OLMo\-3\-7B, Qwen3\.5\-4B, and Llama3\.2\-3B\)\([Team, 2024](https://arxiv.org/html/2609.29245#bib.bib45);[Ettinger et al\., 2025](https://arxiv.org/html/2609.29245#bib.bib44)\), as well as different model scales within Qwen3\.5\. We compare full vs block\-sparse attention performance to see whether the trends align with our earlier finding\.

Block\-Sparse Result Holds Across Model Families\.We report the performance gap between full and block\-sparse attention across three sizes of Qwen 3\.5, Llama, and OLMo in Figure[6](https://arxiv.org/html/2609.29245#S5.F6)\(Left\); individual results are reported in Figure[8](https://arxiv.org/html/2609.29245#A5.F8)of Appendix[E](https://arxiv.org/html/2609.29245#A5)\. Across all families and scales, block\-sparse attention causes little degradation on HotpotQA but substantial degradation on Contradiction\. Comparing degrees of degration across three model sizes of Qwen\-3\.5 \(0\.8B, 2B, 4B\) additionally reveal the pattern that smaller models degrades faster on larger input corpora\. This confirms our earlier finding that replacing full with block\-sparse attention has a larger impact on high\-CTC than low\-CTC tasks\.

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,OT​\(N\)O\_\{T\}\(N\)\) and high\-CTC \(Contradiction,OT​\(N2\)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 ofOT​\(N\)O\_\{T\}\(N\)toOT​\(N2\)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\.
### 5\.2Oracle Operation Difficulty

CTC focuses on how the number of oracle calls required to solve a task scales with corpus size, rather than the difficulty of each oracle call itself\. A natural question to ask is: How does oracle operation difficulty affect model performance on low\- and high\-CTC tasks?

To study this, we consider fourOT​\(N\)O\_\{T\}\(N\)tasks, Contra\-NIAH\-Contra, HotpotQA, NQ, and FiQA, and rank them by relative difficulty, measured empirically by Qwen3\.5\-4B performance averaged across all evaluated context lengths\. We pair each task with its correspondingOT​\(N2\)O\_\{T\}\(N^\{2\}\)tasks—Contradiction, QDMatch HotpotQA, QDMatch NQ, QDMatch FiQA—and measure how much harder theOT​\(N2\)O\_\{T\}\(N^\{2\}\)version is relative to its matchedOT​\(N\)O\_\{T\}\(N\)task, i\.e\., the ratio of their performance at aech context length, under block\-sparse attention\.

CTC Magnifies Difficulty Gaps Between Tasks\.Figure[6](https://arxiv.org/html/2609.29245#S5.F6)\(Right\) shows that the performance gap between eachOT​\(N2\)O\_\{T\}\(N^\{2\}\)task and its matchingOT​\(N\)O\_\{T\}\(N\)tasks grows with context length\. Importantly, the ordering of these gaps follows the ordering of oracle difficulty: tasks with harder oracle operations exhibit larger gaps as context length increases\. This suggests that oracle difficulty and CTC interact systematically, and that relative degradation between tasks at shorter contexts may provide bounds on, or even predict degradation at longer contexts and higher CTC classes\.

## 6Related Work

##### Prior Corpus Reasoning Tasks

Corpus reasoning tasks \(including examples with possibly high\-CTC\) have been studied for decades in computer science, from various low\-CTC tasks in our suite \(e\.g\. IR[Craswell et al\. \(2025\)](https://arxiv.org/html/2609.29245#bib.bib2)\), to others like event ordering\([Chambers et al\., 2014](https://arxiv.org/html/2609.29245#bib.bib41)\)\. Fields like Exploratory Data Analysis\([Tukey, 1962](https://arxiv.org/html/2609.29245#bib.bib31)\)\(which studies visualization and understanding of large data\), though often focused on structured data, have explored engineering specialized pipelines to understand unstructured data\([Shankar et al\., 2024](https://arxiv.org/html/2609.29245#bib.bib30)\)\. Work in library sciences has also developed theories of interrelatedness between documents, most famously in the taxonomy of[Tillett \(1991\)](https://arxiv.org/html/2609.29245#bib.bib1)\. More recently[Zhang et al\. \(2025\)](https://arxiv.org/html/2609.29245#bib.bib22)—which informally mentions a notion of task complexity related to CTC—includes an exhaustive pair generation task they find to be more challenging at scale for closed\-source LLMs\. Overall, while we assemble a large and new set of high\-CTC tasks, we are not the first to propose tasks classifiable as high\-CTC\. That said, beyond existing notions\([Goldman et al\., 2024](https://arxiv.org/html/2609.29245#bib.bib36)\), we develop a new unified understanding of difficulty within CTC classes\. To our knowledge this work is the first to identify LCLMs as uniquely suitable for high CTC tasks, and to connect task complexity to architectural decisions\. ThroughCTC\-Bench, our work also provides the most comprehensive testbed for how high\-CTC task difficulty grows at scale\.

##### Scalable Corpus Methods

Work applying language models to corpora has taken several directions\. One path is to develop agentic scaffolds that combine efficient tools like dense retrievers[Khattab and Zaharia \(2020\)](https://arxiv.org/html/2609.29245#bib.bib6);[Karpukhin et al\. \(2020\)](https://arxiv.org/html/2609.29245#bib.bib7)with LLMs\. These are often hampered by fundamental challenges in retrieval\([Weller et al\., 2025](https://arxiv.org/html/2609.29245#bib.bib8);[Su et al\., 2024](https://arxiv.org/html/2609.29245#bib.bib4);[Wei et al\., 2025](https://arxiv.org/html/2609.29245#bib.bib29)\), but as shown by[Zhang et al\. \(2025\)](https://arxiv.org/html/2609.29245#bib.bib22)can be promising given the right scaffold and sufficient inference compute\. Note that the slowness of auto\-regression \(and the high per\-query online cost,[Zhang et al\. \(2025\)](https://arxiv.org/html/2609.29245#bib.bib22)\) make agentic systems intractable for high\-complexity tasks—finding subtle contradictions via enumeration acrossNNdocuments may require generating on the order ofN2N^\{2\}tokens per query\. Consequently, a complementary line of work—which we focus on in this work—seeks to develop architectures capable of ingesting full corpora end\-to\-end, often by making attention more efficient\([Acharya et al\., 2024](https://arxiv.org/html/2609.29245#bib.bib10);[Beltagy et al\., 2020](https://arxiv.org/html/2609.29245#bib.bib9);[Ivgi et al\., 2022](https://arxiv.org/html/2609.29245#bib.bib11);[Lu et al\., 2024](https://arxiv.org/html/2609.29245#bib.bib12);[Xiao et al\., 2025](https://arxiv.org/html/2609.29245#bib.bib13);[Izacard and Grave, 2020](https://arxiv.org/html/2609.29245#bib.bib24);[Zaheer et al\., 2020](https://arxiv.org/html/2609.29245#bib.bib25);[Katharopoulos et al\., 2020](https://arxiv.org/html/2609.29245#bib.bib26);[Yang et al\., 2024](https://arxiv.org/html/2609.29245#bib.bib28)\)\. Context extension[Peng et al\. \(2023\)](https://arxiv.org/html/2609.29245#bib.bib42), and length generalization[Mehta et al\. \(2026\)](https://arxiv.org/html/2609.29245#bib.bib43)also fall into these efforts\. Our work helps develop a unified understanding of what these can / cannot achieve as a function of their computation\. Importantly, our findings qualify this line of work, and reveal limitations obscured by the fact that these methods have primarily been developed on low\-CTC tasks\.

## 7Conclusion

Our work focuses on clearly defining the challenges around high\-CTC settings, and identifying the relationship between architecture design and CTC\. While helping explain the success of cheaper linear cost methods, our investigation in particular encourages the community to avoid over\-reliance on low\-CTC evaluations and pay greater attention to high CTC tasks, which represent an interesting and impactful long\-term open problem\.

## Acknowledgment

We thank Ryan Wang, Karim Abdel Sadek, Jongho Park, Diane Tchuindjo, Omar Khattab, Suhas Kotha, Rhys Gould, Yaowen Ye, Yichuan Wang and other members of Jacob Steinhardt, Sewon Min, and Berkeley AI Research groups for discussion and feedback\. This research was supported in part by ONR \(N00014\-26\-1\-2233\), the NVIDIA Academic Grant Program, and gifts from Ai2 and Apple\. This material is based upon work supported by the National Science Foundation Graduate Research Fellowship Program under Grant Numbers DGE2146752, DGE2637800, DGE2140739\. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author\(s\) and do not necessarily reflect the views of the National Science Foundation\. This project was also supported generously by compute from VESSL AI\.

## References

- Acharyaet al\.\(2024\)S\. Acharya, F\. Jia, and B\. GinsburgStar attention: efficient llm inference over long sequences\.ArXivabs/2411\.17116\.External Links:[Link](https://api.semanticscholar.org/CorpusID:274280741)Cited by:[§6](https://arxiv.org/html/2609.29245#S6.SS0.SSS0.Px2.p1.1)\.
- Baiet al\.\(2024\)Y\. Bai, S\. Tu, J\. Zhang, H\. Peng, X\. Wang, X\. Lv, S\. Cao, J\. Xu, L\. Hou, Y\. Dong, J\. Tang, and J\. LiLongBench v2: towards deeper understanding and reasoning on realistic long\-context multitasks\.ArXivabs/2412\.15204\.External Links:[Link](https://api.semanticscholar.org/CorpusID:274859535)Cited by:[§1](https://arxiv.org/html/2609.29245#S1.p2.1),[§2\.3](https://arxiv.org/html/2609.29245#S2.SS3.p8.1),[§4\.2](https://arxiv.org/html/2609.29245#S4.SS2.p2.1)\.
- Beltagyet al\.\(2020\)I\. Beltagy, M\. E\. Peters, and A\. CohanLongformer: the long\-document transformer\.ArXivabs/2004\.05150\.External Links:[Link](https://api.semanticscholar.org/CorpusID:215737171)Cited by:[§1](https://arxiv.org/html/2609.29245#S1.p2.1),[§4\.1](https://arxiv.org/html/2609.29245#S4.SS1.p1.1),[§4\.1](https://arxiv.org/html/2609.29245#S4.SS1.p4.1),[§6](https://arxiv.org/html/2609.29245#S6.SS0.SSS0.Px2.p1.1)\.
- Bertschet al\.\(2025\)A\. Bertsch, A\. Pratapa, T\. Mitamura, G\. Neubig, and M\. R\. GormleyOolong: evaluating long context reasoning and aggregation capabilities\.ArXivabs/2511\.02817\.External Links:[Link](https://api.semanticscholar.org/CorpusID:282749185)Cited by:[§C\.2\.1](https://arxiv.org/html/2609.29245#A3.SS2.SSS1.p10.1),[§2\.2](https://arxiv.org/html/2609.29245#S2.SS2.p4.1.1)\.
- Chamberset al\.\(2014\)N\. Chambers, T\. Cassidy, B\. McDowell, and S\. BethardDense event ordering with a multi\-pass architecture\.Transactions of the Association for Computational Linguistics2,pp\. 273–284\.External Links:[Link](https://api.semanticscholar.org/CorpusID:1564278)Cited by:[§2\.3](https://arxiv.org/html/2609.29245#S2.SS3.p1.1),[§6](https://arxiv.org/html/2609.29245#S6.SS0.SSS0.Px1.p1.1)\.
- Chenet al\.\(2026\)Z\. Chen, X\. Wu, J\. Jia, C\. Gao, Q\. Fu, D\. Zhang, and S\. HuLongBench pro: a more realistic and comprehensive bilingual long\-context evaluation benchmark\.ArXivabs/2601\.02872\.External Links:[Link](https://api.semanticscholar.org/CorpusID:284512608)Cited by:[§1](https://arxiv.org/html/2609.29245#S1.p2.1)\.
- Craswellet al\.\(2025\)N\. Craswell, B\. Mitra, E\. Yilmaz, D\. F\. Campos, and J\. J\. LinOverview of the trec 2021 deep learning track\.ArXivabs/2507\.08191\.External Links:[Link](https://api.semanticscholar.org/CorpusID:261242374)Cited by:[§1](https://arxiv.org/html/2609.29245#S1.p1.1),[§6](https://arxiv.org/html/2609.29245#S6.SS0.SSS0.Px1.p1.1)\.
- Ettingeret al\.\(2025\)A\. Ettinger, A\. Bertsch, B\. Kuehl, D\. W\. Graham, D\. Heineman, D\. Groeneveld, F\. Brahman, F\. Timbers, H\. Ivison, J\. D\. Morrison, J\. Poznanski, K\. Lo, L\. Soldaini, M\. Jordan, M\. F\. Chen, M\. Noukhovitch, N\. Lambert, P\. Walsh, P\. Dasigi, R\. Berry, S\. Malik, S\. Shah, S\. Geng, S\. Arora, S\. Gupta, T\. Anderson, T\. Xiao, T\. C\. Murray, T\. Romero, V\. Graf, A\. Asai, A\. Bhagia, A\. Wettig, A\. Liu, A\. Rangapur, C\. Anastasiades, C\. Huang, D\. Schwenk, H\. M\. Trivedi, I\. Magnusson, J\. Lochner, J\. Liu, L\. J\. V\. Miranda, M\. Sap, M\. Morgan, M\. Schmitz, M\. Guerquin, M\. Wilson, R\. Huff, R\. L\. Bras, R\. Xin, R\. Shao, S\. Skjonsberg, S\. Z\. Shen, S\. S\. Li, T\. Wilde, V\. Pyatkin, W\. Merrill, Y\. Chang, Y\. Gu, Z\. Zeng, A\. Sabharwal, L\. Zettlemoyer, P\. W\. Koh, A\. Farhadi, N\. A\. Smith, and H\. HajishirziOlmo 3\.ArXiv\.External Links:[Link](https://api.semanticscholar.org/CorpusID:283908770)Cited by:[§4\.2](https://arxiv.org/html/2609.29245#S4.SS2.p2.1),[§5\.1](https://arxiv.org/html/2609.29245#S5.SS1.p1.1)\.
- Fuet al\.\(2025\)H\. Y\. Fu, A\. Shrivastava, J\. Moore, P\. West, C\. Tan, and A\. HoltzmanAbsenceBench: language models can’t tell what’s missing\.ArXivabs/2506\.11440\.External Links:[Link](https://api.semanticscholar.org/CorpusID:279391603)Cited by:[§C\.2\.1](https://arxiv.org/html/2609.29245#A3.SS2.SSS1.p11.1),[§2\.2](https://arxiv.org/html/2609.29245#S2.SS2.p4.1)\.
- Gaoet al\.\(2024\)T\. Gao, A\. Wettig, H\. Yen, and D\. ChenHow to train long\-context language models \(effectively\)\.InAnnual Meeting of the Association for Computational Linguistics,External Links:[Link](https://api.semanticscholar.org/CorpusID:273098476)Cited by:[§1](https://arxiv.org/html/2609.29245#S1.p4.1),[§4\.3](https://arxiv.org/html/2609.29245#S4.SS3.p1.1)\.
- Goldmanet al\.\(2024\)O\. Goldman, A\. Jacovi, A\. Slobodkin, A\. Maimon, I\. Dagan, and R\. TsarfatyIs it really long context if all you need is retrieval? towards genuinely difficult long context nlp\.ArXivabs/2407\.00402\.External Links:[Link](https://api.semanticscholar.org/CorpusID:270870356)Cited by:[§6](https://arxiv.org/html/2609.29245#S6.SS0.SSS0.Px1.p1.1)\.
- Gollapudiet al\.\(2026\)S\. Gollapudi, N\. Gupta, P\. Singhal, and S\. MinCan language models actually retrieve in\-context? drowning in documents at million token scale\.ArXiv\.External Links:[Link](https://api.semanticscholar.org/CorpusID:289749122)Cited by:[§4\.1](https://arxiv.org/html/2609.29245#S4.SS1.p1.1),[§4\.1](https://arxiv.org/html/2609.29245#S4.SS1.p4.1)\.
- Gu and Dao \(2023\)A\. Gu and T\. DaoMamba: linear\-time sequence modeling with selective state spaces\.ArXivabs/2312\.00752\.External Links:[Link](https://api.semanticscholar.org/CorpusID:265551773)Cited by:[§4\.2](https://arxiv.org/html/2609.29245#S4.SS2.p1.1)\.
- Houet al\.\(2025\)A\. B\. Hou, O\. Weller, G\. Qin, E\. Yang, D\. J\. Lawrie, N\. Holzenberger, A\. Blair\-Stanek, and B\. V\. DurmeCLERC: a dataset for u\. s\. legal case retrieval and retrieval\-augmented analysis generation\.InNorth American Chapter of the Association for Computational Linguistics,External Links:[Link](https://api.semanticscholar.org/CorpusID:278664835)Cited by:[§1](https://arxiv.org/html/2609.29245#S1.p1.1)\.
- Houet al\.\(2024\)Y\. Hou, J\. Li, Z\. He, A\. Yan, X\. Chen, and J\. McAuleyBridging language and items for retrieval and recommendation\.ArXivabs/2403\.03952\.External Links:[Link](https://api.semanticscholar.org/CorpusID:287635730)Cited by:[§C\.2\.1](https://arxiv.org/html/2609.29245#A3.SS2.SSS1.p12.1)\.
- Ivgiet al\.\(2022\)M\. Ivgi, U\. Shaham, and J\. BerantEfficient long\-text understanding with short\-text models\.Transactions of the Association for Computational Linguistics11,pp\. 284–299\.External Links:[Link](https://api.semanticscholar.org/CorpusID:251224058)Cited by:[§6](https://arxiv.org/html/2609.29245#S6.SS0.SSS0.Px2.p1.1)\.
- Izacard and Grave \(2020\)G\. Izacard and E\. GraveLeveraging passage retrieval with generative models for open domain question answering\.ArXivabs/2007\.01282\.External Links:[Link](https://api.semanticscholar.org/CorpusID:220302360)Cited by:[§6](https://arxiv.org/html/2609.29245#S6.SS0.SSS0.Px2.p1.1)\.
- Izacardet al\.\(2022\)G\. Izacard, P\. Lewis, M\. Lomeli, L\. Hosseini, F\. Petroni, T\. Schick, J\. A\. Yu, A\. Joulin, S\. Riedel, and E\. GraveFew\-shot learning with retrieval augmented language models\.J\. Mach\. Learn\. Res\.24,pp\. 251:1–251:43\.External Links:[Link](https://api.semanticscholar.org/CorpusID:251371732)Cited by:[§C\.2\.1](https://arxiv.org/html/2609.29245#A3.SS2.SSS1.p1.1)\.
- Jinet al\.\(2019\)Q\. Jin, B\. Dhingra, Z\. Liu, W\. W\. Cohen, and X\. LuPubMedQA: a dataset for biomedical research question answering\.ArXivabs/1909\.06146\.External Links:[Link](https://api.semanticscholar.org/CorpusID:202572622)Cited by:[§C\.2\.3](https://arxiv.org/html/2609.29245#A3.SS2.SSS3.p3.1),[§2\.3](https://arxiv.org/html/2609.29245#S2.SS3.p2.1)\.
- Karpukhinet al\.\(2020\)V\. Karpukhin, B\. Oğuz, S\. Min, P\. Lewis, L\. Y\. Wu, S\. Edunov, D\. Chen, and W\. YihDense passage retrieval for open\-domain question answering\.ArXivabs/2004\.04906\.External Links:[Link](https://api.semanticscholar.org/CorpusID:215737187)Cited by:[§C\.2\.1](https://arxiv.org/html/2609.29245#A3.SS2.SSS1.p1.1),[§6](https://arxiv.org/html/2609.29245#S6.SS0.SSS0.Px2.p1.1)\.
- Katharopouloset al\.\(2020\)A\. Katharopoulos, A\. Vyas, N\. Pappas, and F\. FleuretTransformers are rnns: fast autoregressive transformers with linear attention\.InInternational Conference on Machine Learning,External Links:[Link](https://api.semanticscholar.org/CorpusID:220250819)Cited by:[§4\.2](https://arxiv.org/html/2609.29245#S4.SS2.p1.1),[§6](https://arxiv.org/html/2609.29245#S6.SS0.SSS0.Px2.p1.1)\.
- Khattab and Zaharia \(2020\)O\. Khattab and M\. A\. ZahariaColBERT: efficient and effective passage search via contextualized late interaction over bert\.Proceedings of the 43rd International ACM SIGIR Conference on Research and Development in Information Retrieval\.External Links:[Link](https://api.semanticscholar.org/CorpusID:216553223)Cited by:[§6](https://arxiv.org/html/2609.29245#S6.SS0.SSS0.Px2.p1.1)\.
- Kociskýet al\.\(2017\)T\. Kociský, J\. Schwarz, P\. Blunsom, C\. Dyer, K\. M\. Hermann, G\. Melis, and E\. GrefenstetteThe narrativeqa reading comprehension challenge\.Transactions of the Association for Computational Linguistics6,pp\. 317–328\.External Links:[Link](https://api.semanticscholar.org/CorpusID:2593903)Cited by:[§1](https://arxiv.org/html/2609.29245#S1.p1.1)\.
- Kwiatkowskiet al\.\(2019\)T\. Kwiatkowski, J\. Palomaki, O\. Redfield, M\. Collins, A\. P\. Parikh, C\. Alberti, D\. Epstein, I\. Polosukhin, J\. Devlin, K\. Lee, K\. Toutanova, L\. Jones, M\. Kelcey, M\. Chang, A\. M\. Dai, J\. Uszkoreit, Q\. V\. Le, and S\. PetrovNatural questions: a benchmark for question answering research\.Transactions of the Association for Computational Linguistics7,pp\. 453–466\.External Links:[Link](https://api.semanticscholar.org/CorpusID:86611921)Cited by:[§2\.2](https://arxiv.org/html/2609.29245#S2.SS2.p3.1)\.
- Kwonet al\.\(2023\)W\. Kwon, Z\. Li, S\. Zhuang, Y\. Sheng, L\. Zheng, C\. H\. Yu, J\. E\. Gonzalez, H\. Zhang, and I\. StoicaEfficient memory management for large language model serving with pagedattention\.InProceedings of the ACM SIGOPS 29th Symposium on Operating Systems Principles,Cited by:[Appendix D](https://arxiv.org/html/2609.29245#A4.p2.1)\.
- Linet al\.\(2021\)J\. J\. Lin, X\. Ma, S\. Lin, J\. Yang, R\. Pradeep, R\. Nogueira, and D\. R\. CheritonPyserini: a python toolkit for reproducible information retrieval research with sparse and dense representations\.Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval\.External Links:[Link](https://api.semanticscholar.org/CorpusID:235366815)Cited by:[§C\.2\.1](https://arxiv.org/html/2609.29245#A3.SS2.SSS1.p1.1)\.
- Luet al\.\(2024\)S\. Lu, H\. Wang, Y\. Rong, Z\. Chen, and Y\. TangTurboRAG: accelerating retrieval\-augmented generation with precomputed kv caches for chunked text\.InConference on Empirical Methods in Natural Language Processing,External Links:[Link](https://api.semanticscholar.org/CorpusID:273233795)Cited by:[§6](https://arxiv.org/html/2609.29245#S6.SS0.SSS0.Px2.p1.1)\.
- Mehtaet al\.\(2026\)M\. Mehta, F\. Yin, and G\. DurrettRandomized yarn improves length generalization for long\-context reasoning\.ArXivabs/2606\.23687\.External Links:[Link](https://api.semanticscholar.org/CorpusID:289629978)Cited by:[§4\.3](https://arxiv.org/html/2609.29245#S4.SS3.p1.1),[§6](https://arxiv.org/html/2609.29245#S6.SS0.SSS0.Px2.p1.1)\.
- Merrillet al\.\(2026\)W\. Merrill, Y\. Li, T\. Romero, A\. Svete, C\. Costello, P\. Dasigi, D\. Groeneveld, D\. Heineman, B\. Kuehl, N\. Lambert, J\. Morrison, L\. Soldaini, F\. Timbers, P\. Walsh, N\. A\. Smith, H\. Hajishirzi, and A\. SabharwalOlmo hybrid: from theory to practice and back\.ArXivabs/2604\.03444\.External Links:[Link](https://api.semanticscholar.org/CorpusID:287199770)Cited by:[§4\.2](https://arxiv.org/html/2609.29245#S4.SS2.p2.1)\.
- Penget al\.\(2023\)B\. Peng, J\. Quesnelle, H\. Fan, and E\. ShippoleYaRN: efficient context window extension of large language models\.ArXivabs/2309\.00071\.External Links:[Link](https://api.semanticscholar.org/CorpusID:261493986)Cited by:[§4\.3](https://arxiv.org/html/2609.29245#S4.SS3.p1.1),[§6](https://arxiv.org/html/2609.29245#S6.SS0.SSS0.Px2.p1.1)\.
- Priemet al\.\(2022\)J\. Priem, H\. A\. Piwowar, and R\. OrrOpenAlex: a fully\-open index of scholarly works, authors, venues, institutions, and concepts\.ArXivabs/2205\.01833\.External Links:[Link](https://api.semanticscholar.org/CorpusID:248512771)Cited by:[§C\.2\.2](https://arxiv.org/html/2609.29245#A3.SS2.SSS2.p2.1),[§2\.3](https://arxiv.org/html/2609.29245#S2.SS3.p6.1)\.
- Qwen Team \(2026\)Qwen TeamQwen3\.5: towards native multimodal agents\.External Links:[Link](https://qwen.ai/blog?id=qwen3.5)Cited by:[§4\.2](https://arxiv.org/html/2609.29245#S4.SS2.p1.1)\.
- Robertson and Jones \(1976\)S\. E\. Robertson and K\. S\. JonesRelevance weighting of search terms\.J\. Am\. Soc\. Inf\. Sci\.27,pp\. 129–146\.External Links:[Link](https://api.semanticscholar.org/CorpusID:45186038)Cited by:[§C\.2\.1](https://arxiv.org/html/2609.29245#A3.SS2.SSS1.p1.1)\.
- Shankaret al\.\(2024\)S\. Shankar, A\. G\. Parameswaran, and E\. WuDocETL: agentic query rewriting and evaluation for complex document processing\.ArXivabs/2410\.12189\.External Links:[Link](https://api.semanticscholar.org/CorpusID:273374845)Cited by:[§6](https://arxiv.org/html/2609.29245#S6.SS0.SSS0.Px1.p1.1)\.
- Suet al\.\(2024\)H\. Su, H\. Yen, M\. Xia, W\. Shi, N\. Muennighoff, H\. Wang, H\. Liu, Q\. Shi, Z\. S\. Siegel, M\. Tang, R\. Sun, J\. Yoon, S\. Ö\. Arik, D\. Chen, and T\. YuBRIGHT: a realistic and challenging benchmark for reasoning\-intensive retrieval\.ArXivabs/2407\.12883\.External Links:[Link](https://api.semanticscholar.org/CorpusID:271270735)Cited by:[§6](https://arxiv.org/html/2609.29245#S6.SS0.SSS0.Px2.p1.1)\.
- Tchuindjoet al\.\(2026\)D\. Tchuindjo, D\. Shah, and O\. KhattabOBLIQ\-bench: exposing overlooked bottlenecks in modern retrievers with latent and implicit queries\.ArXivabs/2605\.06235\.External Links:[Link](https://api.semanticscholar.org/CorpusID:288014448)Cited by:[§2\.2](https://arxiv.org/html/2609.29245#S2.SS2.p2.1)\.
- Team \(2024\)L\. TeamThe llama 3 herd of models\.External Links:2407\.21783Cited by:[§5\.1](https://arxiv.org/html/2609.29245#S5.SS1.p1.1)\.
- Thakuret al\.\(2021\)N\. Thakur, N\. Reimers, A\. Ruckl’e, A\. Srivastava, and I\. GurevychBEIR: a heterogenous benchmark for zero\-shot evaluation of information retrieval models\.ArXivabs/2104\.08663\.External Links:[Link](https://api.semanticscholar.org/CorpusID:233296016)Cited by:[§C\.2\.1](https://arxiv.org/html/2609.29245#A3.SS2.SSS1.p3.1),[§2\.2](https://arxiv.org/html/2609.29245#S2.SS2.p2.1)\.
- Tillett \(1991\)B\. B\. TillettA taxonomy of bibliographic relationships\.Library Resources & Technical Services35,pp\. 150–158\.External Links:[Link](https://api.semanticscholar.org/CorpusID:59748210)Cited by:[§6](https://arxiv.org/html/2609.29245#S6.SS0.SSS0.Px1.p1.1)\.
- Tukey \(1962\)J\. W\. TukeyThe future of data analysis\.Annals of Mathematical Statistics33,pp\. 1–67\.External Links:[Link](https://api.semanticscholar.org/CorpusID:122864799)Cited by:[§6](https://arxiv.org/html/2609.29245#S6.SS0.SSS0.Px1.p1.1)\.
- Weiet al\.\(2025\)J\. Wei, Z\. Sun, S\. Papay, S\. McKinney, J\. Han, I\. Fulford, H\. W\. Chung, A\. Passos, W\. Fedus, and A\. GlaeseBrowseComp: a simple yet challenging benchmark for browsing agents\.ArXivabs/2504\.12516\.External Links:[Link](https://api.semanticscholar.org/CorpusID:277857238)Cited by:[§6](https://arxiv.org/html/2609.29245#S6.SS0.SSS0.Px2.p1.1)\.
- Welleret al\.\(2025\)O\. Weller, M\. Boratko, I\. Naim, and J\. LeeOn the theoretical limitations of embedding\-based retrieval\.ArXivabs/2508\.21038\.External Links:[Link](https://api.semanticscholar.org/CorpusID:280949957)Cited by:[§6](https://arxiv.org/html/2609.29245#S6.SS0.SSS0.Px2.p1.1)\.
- Xiaoet al\.\(2025\)E\. Xiao, C\. Li, Y\. Zhang, G\. Neubig, and A\. BertschEfficient many\-shot in\-context learning with dynamic block\-sparse attention\.ArXivabs/2503\.08640\.External Links:[Link](https://api.semanticscholar.org/CorpusID:276928367)Cited by:[§1](https://arxiv.org/html/2609.29245#S1.p4.1),[§4\.1](https://arxiv.org/html/2609.29245#S4.SS1.p1.1),[§4\.1](https://arxiv.org/html/2609.29245#S4.SS1.p2.1),[§6](https://arxiv.org/html/2609.29245#S6.SS0.SSS0.Px2.p1.1)\.
- Yanget al\.\(2024\)S\. Yang, J\. Kautz, and A\. HatamizadehGated delta networks: improving mamba2 with delta rule\.ArXivabs/2412\.06464\.External Links:[Link](https://api.semanticscholar.org/CorpusID:274598177)Cited by:[§1](https://arxiv.org/html/2609.29245#S1.p2.1),[§4\.2](https://arxiv.org/html/2609.29245#S4.SS2.p1.1),[§6](https://arxiv.org/html/2609.29245#S6.SS0.SSS0.Px2.p1.1)\.
- Yanget al\.\(2018\)Z\. Yang, P\. Qi, S\. Zhang, Y\. Bengio, W\. W\. Cohen, R\. Salakhutdinov, and C\. D\. ManningHotpotQA: a dataset for diverse, explainable multi\-hop question answering\.InConference on Empirical Methods in Natural Language Processing,External Links:[Link](https://api.semanticscholar.org/CorpusID:52822214)Cited by:[§C\.2\.1](https://arxiv.org/html/2609.29245#A3.SS2.SSS1.p2.1),[§2\.2](https://arxiv.org/html/2609.29245#S2.SS2.p3.1)\.
- Yenet al\.\(2024\)H\. Yen, T\. Gao, M\. Hou, K\. Ding, D\. Fleischer, P\. Izsak, M\. Wasserblat, and D\. ChenHELMET: how to evaluate long\-context language models effectively and thoroughly\.ArXivabs/2410\.02694\.External Links:[Link](https://api.semanticscholar.org/CorpusID:273098808)Cited by:[§1](https://arxiv.org/html/2609.29245#S1.p2.1)\.
- Zaheeret al\.\(2020\)M\. Zaheer, G\. Guruganesh, K\. A\. Dubey, J\. Ainslie, C\. Alberti, S\. Ontañón, P\. Pham, A\. Ravula, Q\. Wang, L\. Yang, and A\. AhmedBig bird: transformers for longer sequences\.ArXivabs/2007\.14062\.External Links:[Link](https://api.semanticscholar.org/CorpusID:220831004)Cited by:[§4\.1](https://arxiv.org/html/2609.29245#S4.SS1.p1.1),[§6](https://arxiv.org/html/2609.29245#S6.SS0.SSS0.Px2.p1.1)\.
- Zhanget al\.\(2025\)A\. L\. Zhang, T\. Kraska, and O\. KhattabRecursive language models\.ArXivabs/2512\.24601\.External Links:[Link](https://api.semanticscholar.org/CorpusID:284350669)Cited by:[§6](https://arxiv.org/html/2609.29245#S6.SS0.SSS0.Px1.p1.1),[§6](https://arxiv.org/html/2609.29245#S6.SS0.SSS0.Px2.p1.1)\.

## Appendix ALimitations

While this work shows initial evidence for challenging properties of CTC tasks, there is still room for future work to expand on our analysis\. Our paper, while supporting our hypotheses up to 32k tokens in\-domain \(128k tokens in our length generalization experiments\) due to compute limitations does not examine larger corpus\-scale settings beyond 128k tokens—note that for many high\-CTC tasks performance already degrades greatly by 32k tokens and shows clear trends of degrading further\. While we aim to get a comprehensive set \(including 12 tasks representative of previously explored settings\), there are still likely several low\-CTC and high\-CTC tasks our suite misses, and that we encourage future work to examine and reproduce our findings on\. While this work helps define and understand high\-CTC tasks, it only take initial steps towards solving them, and we are excited to see future work make further progress on high\-CTC tasks\.

## Appendix BDiscussion of Real High CTC Tasks

A key message of this work is to encourage more work onOT​\(N2\)O\_\{T\}\(N^\{2\}\)andOT​\(N​M\)O\_\{T\}\(NM\)tasks, which represent very different architectural challenges at scale\. While our investigation focuses largely on the technical and architectural aspects of this problem, we emphasize that while these tasks are under\-explored, they*are*realistic, and systems that can do such tasks over large corpora may open up various new valuable applications not previously possible, inspiring our current task suite\. We below detail just a few applications and potential ideas for future work to investigate that could benefit from such systems at scale, connected to tasks from our suite:

Contradiction / Redundancy Detection\(high\-CTC tasks a\) Motivating example: scientific literature\. Given a large and growing body of scientific literature, a key and evolving question in determining new research and experiments is always*what information does the community have?*Often, one will examine a specific research area at a local level, and given specific ideas may, with keyword search and other tools, try to determine what’s been explored and not, or what’s been verified or not, which isOT​\(N\)O\_\{T\}\(N\)\. To determine the state of an entire field at a global level \(e\.g\. all claims with the most contradictory evidence, claims with the most redundant evidence\), allowing for systematic synthesis and resolution of such evidence, isOT​\(N2\)O\_\{T\}\(N^\{2\}\), and not currently tractable\. Better corpus reasoning systems could allow such systematic analysis end\-to\-end for scientific literature, fact\-checking, minimizing / tracking redundancy in long\-text like books, and many other applications\.

Discovering long\-tail categories / phenomena\(high\-CTC tasks f, g\) Motivating example: Monitoring LLM Generations\. Language models can generate text at rapid scale, and for an LLM provider or other larger\-scale user, every day a new corpus may get generated\. For such instances, being able to faithfully look for the long tail of the least common events with harmful or other properties may be important to the safe deployment of such systems \(e\.g\.*What are the weirdest questions today?*\)\. Doing so however isOT​\(N​M\)O\_\{T\}\(NM\)whereMMis the number of possible phenomena \(which in the long\-tail case will be quite large\), and so doing such a task at high\-fidelity may currently be very challenging\. Similar analyses could be applied for finding under\-explored research areas / methodologies\.

Structured Re\-Organization of Large Corpora\(high\-CTC task i\) Corpora are often unstructured and, aside from some metadata, relatively unorganized\. Being able to do analyses like sorting passages in a book by importance, or hierarchically re\-organizing and grouping a corpus into a fashion reflecting the overall semantic structure \(e\.g\. to reflect new trends in the corpus\) can all beOT​\(N​M\)O\_\{T\}\(NM\)orOT​\(N2\)O\_\{T\}\(N^\{2\}\), and potentially provide valuable analyses or new ways of interacting with corpora\.

Cross\-Corpus Comparison\(high\-CTC tasks b, c, d, e\) Often corpora don’t exist as monoliths in isolation\. We may be interested in understanding how corpora evolve over time from largely similar distributions with high overlap \(e\.g\. historical records, internet text, internal LLM agent traces from different live model checkpoints\), or we may be interested in finding connections between unrelated corpora \(for example two unrelated fields of science\)\. These tasks are versatile, and in large part often end up beingOT​\(N2\)O\_\{T\}\(N^\{2\}\)as a function of the corpora being compared\.

We believe that if systems which can handle such tasks become more scalable, given that the above are often difficult \(or intractable\) and may rely on a lot of manual work and heuristics with current systems, a large variety of applications may emerge from new methods here\. Work towards building realistic benchmarks for these, as well as new architectures that can handle them, are valuable future directions\.

## Appendix CTask Suite Data Details

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](https://arxiv.org/html/2609.29245#A8)shows each example in full, with the task instruction, the surrounding corpus and the distractor types\.### C\.1Data Construction

##### Evaluation Set Construction

We evaluate at lengths up to 128k tokens \(our code supports up to 10M tokens for several tasks\)\. For each task we typically fix a canonical query set \(usually 500 examples per set\), and then will across different length evaluation sets within the task expand the distractor set\. The documents and queries between train and eval sets are by default kept completely disjoint to avoid any sort of contamination\.

##### Training Data Construction

Unless stated otherwise, each task is trained for one epoch on 20,000 examples split evenly across five context budgets \(so 4,000 examples for 2k, 4k, 8k, 16k and 32k respectively, so the training distribution matches the evaluation uniformly\. Training examples are drawn from the same generator as the evaluation examples for that task, and for the tasks with a published split \(e\.g\. NQ, etc\.\), we use existing train/test divisions\. OBLIQ is the sole exception: it has no usable training split and its training data is synthesized, though for evaluation we use its existing evaluation set with BM25 mined hard negatives\.

### C\.2Tasks: Overview

#### C\.2\.1OT​\(N\)O\_\{T\}\(N\)tasks: one pass over the corpus

Factoid QA \(NQ\)\.*Gold\-ID F1\.*We use NaturalQuestions\-Open \(sourcing train and eval from existing train / eval set\)\[[Izacard et al\., 2022](https://arxiv.org/html/2609.29245#bib.bib16)\], with all documents — gold, hard negative and filler — drawn from the 100\-word Wikipedia DPR corpus\[[Karpukhin et al\., 2020](https://arxiv.org/html/2609.29245#bib.bib7)\]served by pyserini\[[Lin et al\., 2021](https://arxiv.org/html/2609.29245#bib.bib18)\], so every document shares one surface format\. For each question we BM25\-search\[[Robertson and Jones, 1976](https://arxiv.org/html/2609.29245#bib.bib5)\]for a passage containing an answer string \(that becomes the gold\), take top BM25 hits that do*not*contain the answer as hard negatives, and fill the remaining slots with random wiki\-DPR passages\. By default we hold hard negatives to∼\\sim10% of the pool\.

Multi\-hop QA \(HotpotQA\)\.*Gold\-ID F1\.*The bridge subset of HotpotQA\[[Yang et al\., 2018](https://arxiv.org/html/2609.29245#bib.bib17)\], where answering requires composing two gold passages; the corpus is again wikipedia\-100w with BM25 hard negatives\. Because the answer needs a fixed \(two\) number of retrieval steps, this remainsOT​\(N\)O\_\{T\}\(N\)\. We source train examples from the standard train set and test examples from the validation set\. We usecross\-encoder/ms\-marco\-MiniLM\-L\-6\-v2with a CE filter of 3 as well to remove false positives\. And similar to NQ we hold hard negatives to∼\\sim10% of the pool\.

BEIR SciFact / FiQA\.*Set\-F1\.*We use two BEIR[Thakur et al\. \[2021\]](https://arxiv.org/html/2609.29245#bib.bib38)tasks: SciFact \(scientific claim→\\toabstract, single\-gold\) and FiQA \(financial opinion QA, median 2 golds/query\)\. Both mine distractors by BM25 from the dataset’s own corpus\. FiQA is sparsely judged, so plain BM25 distractors to filter unlabeled positives we score \(query, candidate\) pairs with a cross\-encoder and keep a candidate only if it scores at least a margin below the gold, then fill the rest of the pool with random real corpus documents\. FiQA’s train\-set is too small \(5,500 examples\) so we re\-use queries across context lengths to get to 20,000\. SciFact’s existing train set was too small \(809\) to go to 20,000 total, so it has a smaller train set \(4045 examples, each query used once per length\)\. For SciFact the eval set is only 299 examples so our set doesn’t go up to 500\. We use the same CE filter pipeline as HotpotQA to remove false positives\.

MS MARCO retrieval and reranking\.*Set\-F1; MRR@10 for docs with positive CE score*Passages come from themsmarco\-v1\-passageindex\. Hard negatives are taken from SentenceTransformers’ precomputed BM25\+dense mining and filtered by a margin on precomputed cross\-encoder scores \(same as above\), so we don’t re\-run cross\-encoder here; random fill is sampled as random pids from the 8\.8M collection, which are byte\-identical in format to gold and hard passages\. The rerank variant reuses the identical pool but asks for the documents in ranked order based on cross\-encoder score\.

Needle contradiction \(NIAH\-contra\)\.*Set\-F1\.*AnOT​\(N\)O\_\{T\}\(N\)control derived from theOT​\(N2\)O\_\{T\}\(N^\{2\}\)contradiction task: one member of a gold contradiction pair is promoted to the query \(“*find the document that contradicts this claim*”\) and the other stays in the corpus as the needle\. Every other claim, including the other gold pairs, is a distractor\. Comparing this against contradiction isolates the effect of all\-pairs search from the effect of PubMed claim text\.

OBLIQ retrieval\.*Set\-F1\.*OBLIQ\-Bench \(dianetc/OBLIQ\-Bench\) poses subjective, long\-form queries over its own corpora; we port it in\-context by forcing all qrel positives into the example and filling with BM25\-mined distractors from the same subset\. Specifically, we use the twitter subset of the benchmark \(“*find tweets where users are implicitly insinuating that great powers quietly profit from sustained turmoil*…”\), satisfied by a*set*of documents: median 5 golds per example, mean 9\. The documents themselves are single tweets — a median of 257 characters\.

*Synthetic training data\.*As OBLIQ has no usable training split: the benchmark has only a few hundred real queries per subset\. We thus generate data as follows\. For each seed documentDD\(taken from corpus\):

1. 1\.An LLM \(Qwen3\-14B\-Instruct\) writes an oblique queryQQthatDDsatisfies, few\-shot primed with real \(document, query\) pairs \(held out from final eval set\)\.
2. 2\.An*obliqueness*filter rejects anyQQwith word\-Jaccard overlap againstDDabove a per\-subset cap \(0\.55 for the writing subset, 0\.35 elsewhere\), so a keyword shortcut cannot separate the golds — matching real OBLIQ, whose queries are deliberately non\-lexical\.
3. 3\.BM25 retrieves candidate documents forQQfrom the same subset\.
4. 4\.A*multi\-gold judge*\(also using Qwen3\-8B\) asks, for each top candidate, whether it*also*satisfiesQQ\. These either become additional golds or hard negatives\.

Only training data is synthetic— the held\-out evaluation set is the twitter subset of the benchmark \(we use all subsets for generation of the training data\)\. Our data is very initial and it’s likely that much better data could be generated for this task\.

Oolong\.*Partial\-credit score\.*A port of OOLONG\[[Bertsch et al\., 2025](https://arxiv.org/html/2609.29245#bib.bib19)\]: a long context of labeled classification items, each tagged with a date and a user id, and a distributional question — most/least common label, most frequent user, when label A overtook label B\. We use the*unlabeled*context variant, so the model must classify each item and then aggregate\. Because the label set is fixed and each item is judged independently before a single aggregation step, this isOT​\(N\)O\_\{T\}\(N\)\.

Absence\.*Set\-F1 over removed IDs\.*Following AbsenceBench\[[Fu et al\., 2025](https://arxiv.org/html/2609.29245#bib.bib37)\]: the model sees a full numbered corpus, then a second copy with some elements deleted, and must name what is missing\. We construct data with random Project Gutenberg passages, with sentence\-level chunks: each document is deleted independently with probabilitypp\. Because the second copy preserves the original order, the two corpora are positionally aligned\.

Outlier detection \(Amazon Reviews\)\.*Set\-F1\.*Each corpus contains customer reviews from the Amazon Reviews 2023 corpus\[[Hou et al\., 2024](https://arxiv.org/html/2609.29245#bib.bib23)\], shown as review title and body only\. Examples are mixed 50/50 between two variants\. In the*rating*variant a majority of reviews share one star rating and 3 outliers carry a different one \(*“find the outliers with the least common rating”*\); in the*category*variant the majority share one product category and 3 outliers come from another \(*“find the outliers from the least common category”*\), with categories taken from the corpus’s own product\-category labels\.

#### C\.2\.2OT​\(N​M\)O\_\{T\}\(NM\)tasks: categorization

Outlier detection \(Wikipedia\)\.*Set\-F1\.*Each context is filled with 100\-word chunks from a handful of Wikipedia articles with imbalanced counts; the answer is the ID list of chunks belonging to the article with the fewest chunks\. We run two variants:*scale\-MM*, where the number of source articles grows withNN\(M=N/5M=N/5on average\), and a*fixed\-MM*control where the article count stays constant \(at a value of 3\) asNNgrow\.

Grouping \(OpenAlex\)\.*Kendall Tau with true order labels*GivenNNscientific abstracts, partition them intoMMgroups\. Gold partitions come from the OpenAlex\[[Priem et al\., 2022](https://arxiv.org/html/2609.29245#bib.bib33)\]concept hierarchy: we sample only papers annotated down to level L3 \(lower levels indicate more specific categories\), then per example pick a levelL∈\{L​0,…,L​3\}L\\in\\\{L0,\\ldots,L3\\\}and sampleMMdistinct concept values at that level\. The level sets the granularity—L0 gives coarse groups to L3 fine ones—and the model must infer from the corpus andMMwhat granularity is being asked for\. Note thatMMwill naturally be larger for larger corpora with these heuristics\.

#### C\.2\.3OT​\(N2\)O\_\{T\}\(N^\{2\}\)tasks: all\-pairs search

Cross\-corpus absence \(xabsence\)\.*Set\-F1\.*Two corporaAAandBBshare near identical document sets\. Almost every document in one has a twin in the other; exactlykkare unmatched, and the model names these\. The suite uses anexact\-copyvariant: a twin is an identical copy of its partner, and documents are full PubMed abstracts rather than single sentences, but this task could be made more challenging with paraphrasing or other variants\.

Query\-document matching \(qdmatch\)\.*Pair set\-F1\.*The retrieval analogue of contradiction for 3 retrieval tasks\. Pools are drawn so that relevant questions, distractor questions \(gold withheld\) and distractor documents \(questions withheld\) are disjoint such that only three pairs of \(question, document\) are in the corpus\. The model must find the sparse gold pairs amongN×NN\\times Ncombinations\. We build three versions from three retrieval sources—NQ \(1 gold/question\), HotpotQA bridge \(2 golds/question\), and FiQA \(median 2 golds/question\)—so difficulty from the underlying retrieval problem varies while the search structure is fixed\. Note that there are no hard negatives here, but the process to get train data and sources are the same as the original retrieval sets described above\.

Contradiction search \(PubMed\)\.*Pair set\-F1*Each document is a single claim sentence from a PubMed abstract\[[Jin et al\., 2019](https://arxiv.org/html/2609.29245#bib.bib34)\]\. AmongNNdocuments,K=3K\{=\}3gold pairs\(d,d′\)\(d,d^\{\\prime\}\)are hidden:ddis a real PubMed sentence andd′d^\{\\prime\}is a sentence, written by Qwen3\-14B\-Instruct, reporting what a*different*study might have found such that the two cannot both be true \(and prompted with the style of other claim pairs\)\. A word\-overlap threshold \(Jaccard≤0\.5\{\\leq\}0\.5\) drops any near\-duplicates\. Only one sentence per pair is LLM\-written\. Candidate sentences are filtered via regex to be self\-contained and claim sentences, and fillers come from abstracts disjoint from every gold\-source abstract in that example\. While we manually inspect 100 examples for obvious artifacts, subtle LLM\-generated annotation artifacts likely make this version of the task much easier than more realistic versions of contradiction search, which we encourage future work to investigate\.

String matching \(strmatch\)\.*Pair set\-F1\.*NNstrings ofLLwords drawn from a Wikipedia vocabulary, and the task is to find every pair sharing a contiguous run of≥k\\geq kwords\. Gold pairs share exactly onekk\-word run; hard negatives share a\(k−1\)\(k\{\-\}1\)\-word run\. This task has no semantic content at all, so the only thing that scales is the number of comparisons\.

Reordering\.*Kendall\-τ\\tau\.*NNconsecutive sentence segments of a single Project Gutenberg book, presented in random order, with the task of recovering the original ordering as a list of document IDs\. Because sorting requires comparisons between arbitrary pairs of segments, we label itOT​\(N2\)O\_\{T\}\(N^\{2\}\)\(unlike number sorting we can’t assume a strict global positional prior\)\.

#### C\.2\.4BeyondOT​\(N2\)O\_\{T\}\(N^\{2\}\)

Textgroups\.*Group set\-F1\.*NNchunks \(sourced from Project Gutenberg\), each carrying a feature \(how many nouns / verbs / adjectives it contains, or how often a chosen connective appears\), and the task is to find every triple whose feature values sum to a targetTT\. BecauseG=3G\{=\}3, the construction can both plant exactlyKKtriples and verify by brute force that no others exist\. This is the one task in the suite where the per\-document oracle operation is itself nontrivial \(counting\)*and*the CTC is greater than quadratic\. We include it as an example of tasks that can go beyondOT​\(N2\)O\_\{T\}\(N^\{2\}\)\.

## Appendix DData Statistics / Evaluation

Table[3](https://arxiv.org/html/2609.29245#A4.T3)lists, for every task in the suite, the corpus it is built from, its CTC class, the number of documents present at each context rung, and the number of examples it is evaluated on\. Each example carriesdocuments\(a list of \{title, text\}\),queries,answers, andgold\_doc\_indices\. Document counts are measured from the evaluation files\. Document length is given in characters\.

EvaluationWe typically serve everything with vLLM[Kwon et al\. \[2023\]](https://arxiv.org/html/2609.29245#bib.bib35)\(we use a modified version for block\-sparse inference\), where block\-sparse attention is implemented by masking with respect to marker tokens\. For generation we use greedy decoding\.

Table 3:Corpus statistics for every task in the evaluation suiteColumn 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\.
## Appendix EAdditional Experiments

### E\.1Model Scale

We include a more detailed plot with some different dense and block\-sparse attention values for our model scale comparison \(Figure[7](https://arxiv.org/html/2609.29245#A5.F7)\)\. This includes dense attention model scale results on Reordering and QDMatch \(NQ\), where we find a trend of smaller model scales sometimes being unable to learn challenging high CTC tasks\.

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\.
### E\.2Model Family

We in Figure[8](https://arxiv.org/html/2609.29245#A5.F8)show a few exact model family performance numbers with both block\-sparse and full attention\. Note that block\-sparse struggles greatly on contradiction across model families\.

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

## Appendix FTraining Hyperparameters

All CTC Suite results are full\-parameter fine\-tunes of a base checkpoint, trained witholmo\-core\. Every arm of a comparison — full attention, block\-sparse, and block\-sparse with mask mixing — is trained from the same base with the same recipe, so the only difference between arms is the attention mask used during training\. Defaults shared across all settings:

Optimizer:AdamW with skip\-step \(a step whose loss or gradient norm is a large outlier is skipped rather than applied\), lr×10−55\\\!\\times\\\!10^\{\-5\},β=\(0\.9,0\.95\)\\beta=\(0\.9,0\.95\), weight decay 0, gradient clipping at global norm 1\.0\.Schedule:linear warmup over the first 3% of steps, then linear decay to 0\.Epochs / batch:1 epoch, global batch 8 sequences, 1 instance per micro\-batch\.Precision:bf16 parameters with fp32 gradient reduction, FSDP for data parallelism, activation checkpointing on\.Packing:examples are*not*packed; one example per sequence, so per\-example sequence lengths are stable across runs and document boundaries stay aligned with chunk boundaries\.

##### Mask mixing\.

We apply mask\-mixing as a*curriculum*from0\.80\.8to00rather than a fixedpp, finding this to work well empirically\. Evaluation always uses the block\-sparse mask with no mixing, so a mask\-mixing result reflects pure block\-sparse inference and differs from the pure\-block\-sparse arm only in how it was trained\.

## Appendix GGPU Resources / Compute

The experiments for our investigation involved roughly 3k A100 hours and 1k H200 hours \(32 CPU cores, 300GB RAM\)\. We expect that with 8xH100 GPUs, the results in the paper Figure[3](https://arxiv.org/html/2609.29245#S4.F3)would take under 500 hours to reproduce\.

## Appendix HTask Examples

We show one real example for every task in the suite \(Table[1](https://arxiv.org/html/2609.29245#S2.T1)\), we omit full corpus text omitted for readability\.

### H\.1OT​\(N\)O\_\{T\}\(N\)tasks

#### H\.1\.1NQ \(factoid retrieval\)

Instruction:*“Use the given documents to identify which document is most relevant to answering the question\. Write your answer in the following format: Relevant Document: \[id\]”* Query:*“who sold out jesus for 30 pieces of silver”* Context \(3 of 20 documents shown\):

> \[1\]*\(gold\)*“Thirty pieces of silver was the price for which Judas Iscariot betrayed Jesus, according to an account in the Gospel of Matthew 26:15…\\dots” \[2\]*\(BM25 hard negative\)*“Butuan Silver Paleograph\. The Butuan Silver Palaeograph, also known as the ‘Butuan Silver Strip’, is a piece of metal with inscriptions…\\dots” \[3\]*\(BM25 hard negative\)*“Phantom Stranger…\\dotsof betraying him\. As the Spectre is about to attack the Stranger, a Mysterious Voice sends him off…\\dotsAs payment for what occurred…\\dots” \[⋅\\cdot17 more documents omitted\]

Gold doc ID:1Answer string \(not the target\):*“Judas Iscariot”*

#### H\.1\.2HotpotQA \(bridge, multi\-hop retrieval\)

Instruction:*“…\\dotsidentify which documents are relevant…\\dotsRelevant Documents: \[id1\], \[id2\]”* Query:*“What company did Rex Maughan aquire?”**\(question text verbatim, including the source typo\)* Context \(4 of 20 documents shown\):

> \[8\]*\(gold\-1\)*“Forever Living Products International, Inc\. \(FLPI\) is an American privately\-held multi\-level marketing \(MLM\) company based in Scottsdale, Arizona…\\dots” \[9\]*\(gold\-2\)*“Rex G\. Maughan is an American businessman\. He is the founder, president, and chief executive officer of Forever Living Products…\\dots” \[1\]*\(hard negative — name collision\)*“Alex Maughan \(born April 24, 1995\) is an American rugby union player who plays in the front row for the United States men’s national team…\\dots” \[2\]*\(hard negative — same article, wrong chunk\)*“Ruth graduated from BYU with a degree in elementary education, she and Rex moved to Arizona…\\dots” \[⋅\\cdot16 more documents omitted\]

Gold doc IDs:\[8, 9\]Answer string:*“Aloe Vera of America”*

#### H\.1\.3NIAH\-contradiction \(OT​\(N\)O\_\{T\}\(N\)control for contradiction\)

Instruction:*single\-document retrieval, as in NQ\.* Query:*“Find the document that directly contradicts the following claim: The National Lung Screening Trial, performed mainly in academic medical centers, showed that cancer mortality can be reduced with computed tomography \(CT\) screening compared with chest radiography in high\-risk patients\.”* Context \(4 of 40 documents shown; the 2k rung\):

> \[23\]*\(needle\)*“A large\-scale randomized trial indicated that, for individuals at elevated risk, chest X\-rays were more effective than CT scans in lowering cancer\-related deaths\.” \[1\]*\(filler\)*“Thirteen focus group discussions involving a total of 97 informants were conducted\.” \[2\]*\(filler\)*“TRIM47 expression levels were found to be significantly increased in PC compared to benign tissues by both immunohistochemistry and qRT\-PCR…\\dots” \[3\]*\(filler\)*“Free cortisol was significantly elevated at 8:00 to 8:30 hours in the high job strain group but not at later times of the day or evening\.” \[⋅\\cdot36 more documents omitted, drawn from PubMed abstracts disjoint from the needle’s source abstract\]

Gold doc ID:23\.

#### H\.1\.4BEIR SciFact

Instruction:*single/multi\-document retrieval\.* Query \(a scientific claim\):*“0\-dimensional biomaterials show inductive properties\.”* Context \(3 of 22 abstracts shown\):

> \[1\]*\(gold\)*“New opportunities: the use of nanotechnologies to manipulate and track stem cells\. Nanotechnologies are emerging platforms that could be useful in measuring, understanding, and manipulating…\\dots” \[2\]*\(BM25 negative\)*“The spectrum of retinopathy in adults with Plasmodium falciparum malaria…\\dots” \[3\]*\(BM25 negative\)*“Inheritance of coronary artery disease in men: an analysis of the role of the Y chromosome…\\dots” \[⋅\\cdot19 more documents omitted\]

Gold doc ID:1

#### H\.1\.5BEIR FiQA \(cross\-encoder–cleaned negatives\)

Instruction:*multi\-document retrieval\.* Query:*“Where should I park my rainy\-day / emergency fund?”* Context \(3 of 20 documents shown; 5 golds in this example\):

> \[2\]*\(gold\)*“I would suggest your local credit union or local bank for security and liquidity\. Liquidity is probably the most important issue for a emergency fund\.” \[8\]*\(gold\)*“This is probably a good time to note that credit is not a liquid asset, and not an emergency fund\. Credit can be revoked or denied at any time…\\dots” \[10\]*\(gold\)*“First off, you generally want to park your emergency fund somewhere that is ‘safe’, meaning something that is not subject to market fluctuations…\\dots” \[⋅\\cdot17 more documents omitted: cross\-encoder\-surviving hard negatives \(∼\\sim10% of slots\) plus random real corpus documents\]

Gold doc IDs:\[2, 8, 10, 12, 19\]\. FiQA is sparsely judged, so candidates scoring close to the gold under the cross\-encoder are dropped rather than used as negatives — they are likely unlabeled positives\.

#### H\.1\.6MS MARCO \(retrieval\)

Instruction:*single\-document retrieval\.* Query:*“what is the difference between fables and folktales? for kids”* Context \(3 of 20 passages shown\):

> \[2\]*\(gold\)*“Folktale vs Fable\. Folktales and fables can be understood as two different types of stories that show a difference between them…\\dots” \[1\]*\(hard negative\)*“Your job is to make sense of the fact or example in the context of the overall main idea that is being conveyed…\\dots” \[3\]*\(random fill\)*“Cascamite is a waterproof glue and is probably the must effective glue of all…\\dots” \[⋅\\cdot17 more documents omitted\]

Gold doc ID:2\. Hard and random passages are drawn from the same index, so they are format\-identical: there is no stylistic cue distinguishing a mined negative from a random one\.

#### H\.1\.7MS MARCO reranking

Instruction:*“Rank the documents by how relevant each is to the question, from most to least relevant\. Output the document IDs in ranked order\. Write your answer in the following format: Ranking: \[id1\], \[id2\], \[id3\], …”* Query:*“what is the difference between fables and folktales? for kids”* Context \(5 of 23 passages shown; the 2k rung\. Cross\-encoder scores not in the actual prompt\):

> \[3\]*\(CE\+8\.04\+8\.04; also the MS MARCO qrel positive\)*“Folktale vs Fable\. Folktales and fables can be understood as two different types of stories that show a difference between them\. Mostly, folktales and fables are passed on from one generation to another orally…\\dots” \[17\]*\(CE\+4\.60\+4\.60\)*“A fable differs from a parable in that the latter excludes animals, plants, inanimate objects, and forces of nature as actors that assume speech…\\dots” \[12\]*\(CE\+4\.40\+4\.40\)*“A fable is a moral tale that often features animal characters\. We often associate fables with the master of them all, Aesop…\\dots” \[9\]*\(CE−9\.79\-9\.79\)*“A mood disorder is a mental health class that health professionals use to broadly describe all types of depression and bipolar disorders…\\dots” \[19\]*\(CE−11\.30\-11\.30, the lowest in the pool\)*“Geology 1003 with Weaver at University of Oklahoma…\\dots” \[⋅\\cdot18 more passages omitted\]

Target \(top\-10\):Ranking: \[3\], \[17\], \[1\], \[12\], \[9\], \[22\], \[13\], \[16\], \[14\], \[5\]

#### H\.1\.8OBLIQ \(subjective retrieval, twitter subset\)

Instruction:*multi\-document retrieval\.* Query:*“Find tweets where users are implicitly insinuating that great powers quietly profit from sustained turmoil in West Asia, suggesting that disruptions at key maritime chokepoints and damage to energy facilities maintain elevated fuel costs and tilt market share toward them, while questioning which actors truly profit from an extended standoff\.”* Context \(3 of 33 documents shown; 2k rung\):

> \[19\]*\(gold\)*“Yes… So what happens if all of that Middle Eastern infrastructure gets destroyed over the next year or so including Iran’s? Who benefits in terms of oil sales? Mostly the US and Russia\.” \[27\]*\(gold\)*“Who stands to gain and who stands to lose if the Strait of Hormuz stays closed?” \[3\]*\(distractor\)*“Strong conviction on the spike\! Brent’s holding near $103 spot right now with Hormuz disruptions from the Iran strikes\. Jumping to $119 today or $140 by Monday would demand major sustained…” \[⋅\\cdot30 more documents omitted, BM25\-mined from the twitter subset’s 500\-document pool\]

Gold doc IDs:\[4, 19, 27, 30, 32\]

#### H\.1\.9OOLONG \(aggregation over labeled items\)

Instruction:*“Read the data below and answer the question\. Compute the exact answer by analyzing every item; do not guess or approximate\.”* Context \(rendered verbatim as one stream, not as numbered documents; 2k rung, 59 items, one per line\):

> “The following lines contain 59 general\-knowledge questions, one per line\. Each question has an answer that can be described as one of 6 categories: ‘abbreviation’, ‘entity’, ‘human being’, ‘numeric value’, ‘location’, ‘description and abstract concept’\. You will be asked to answer questions about the aggregate label statistics across all 59 examples in this dataset\. Do not try to guess, estimate, or approximate the result\. Calculate the exact answer given these datapoints\. Date: Oct 24, 2022 \|\| User: 34487 \|\| Instance:*Where is Inoco based ?* Date: Jul 14, 2022 \|\| User: 11784 \|\| Instance:*Where did the term “ 86 ” come from ?* Date: Feb 23, 2023 \|\| User: 57329 \|\| Instance:*What international sport was originally called hurley ?* Date: Feb 09, 2024 \|\| User: 24838 \|\| Instance:*What is SVHS ?* Date: Apr 17, 2025 \|\| User: 60511 \|\| Instance:*What is HDLC ?* *\[⋅\\cdot54 more items omitted\]*”

Query:*“For the following question, only consider the subset of instances that occur in April of any year\. Among instances occuring in April, which of the labels is the most common? Give your final answer in the form ‘Label: answer’…\\dots”* Answer:abbreviation

#### H\.1\.10Outlier \(Amazon Reviews\)

Instruction:*“You are given a list of product reviews\. Most share a common attribute \(star rating or product category\); a few are outliers with a different value\. First state what the majority attribute is and what the outlier attribute is, then list the 1\-indexed document IDs of the outliers…\\dotsOutliers: \[id1\], \[id2\], …”* Query:*“Can you find outliers with the least common rating in this data?”* Context \(3 of 20 reviews shown; ratings and categories are withheld from the model — only title and body are rendered\):

> \[4\]*\(outlier, 5\-star\)**“Works great, no errors on memtest”*— “This RAM comes in 2 sticks of 4gb…\\dotsand works perfectly in my old PC\. Ran memtest with 0 errors…\\dots” \[11\]*\(outlier, 5\-star\)**“Great Case at a Fantastic Price”*— “I never realized Amazon had their own line of products, AmazonBasics\!…\\dotsThe case is the perfect size for my new Canon Powershot Camera…\\dots” \[1\]*\(majority, 4\-star\)**“Light”*— “Works well\. Can be kind of heavy depending on the size of your camera\. Easy to install and use…\\dots” \[17 more reviews omitted\]

Target:*“Most reviews are 4\-star ratings and the outliers are 5\-star reviews\.”*followed byOutliers: \[4\], \[7\], \[11\], \[17\]\. Ground truth comes from structured metadata only \(the star\-rating field\), never from an LLM label\. The attribute set is small and fixed — five star ratings, or a closed category list — which is what keeps this variantOT​\(N\)O\_\{T\}\(N\): there is no category to discover\.

#### H\.1\.11Outlier \(Wikipedia, fixed M\)

TheOT​\(N\)O\_\{T\}\(N\)control for the scale\-kkoutlier task: identical format and generator, but the number of source articlesMMis pinned asNNgrows instead of scaling with it\. Query:*“Can you find passages that are about a different topic than the rest of these passages?”* Context \(3 of 14 chunks shown at the 2k rung; article titles are withheld\):

> \[2\]*\(outlier\)*“1987, and 1989\. Several notable players played for Sheppard in the 1980s: John Morris, Tony DeFrancesco, Pat Pacillo, Rich Scheid, Craig Biggio…\\dots” \[14\]*\(outlier\)*“Future major leaguers Rick Cerone and Dan Morogiello played for Sheppard during the 1970s\. Seton Hall appeared in the NCAA Tournament three more times…\\dots” \[1\]*\(majority\)*“…\\dotsaccount of black immigration to the United States from the Caribbean dates back to 1619, when a small group of voluntary indentured workers arrived in Jamestown…\\dots” \[⋅\\cdot11 more chunks omitted\]

Article distribution \(M=3M\{=\}3, pinned\):Privy Council of Sweden: 6,Trinidadian and Tobagonian Americans: 5,Mike Sheppard \(baseball\):3\(outlier\)\.Target:Outliers: \[2\], \[11\], \[14\]\. HoldingMMfixed whileNNgrows is what separatesOT​\(N\)O\_\{T\}\(N\)from theOT​\(N​M\)O\_\{T\}\(NM\)scale\-kkrow: with a constant article count, one exemplar per topic suffices and no group discovery is needed\.

#### H\.1\.12Absence \(Gutenberg text\-diff\)

Instruction:*“Above are two versions of the same passage\. Version B is identical to Version A except that some whole sentences have been removed\. Identify every sentence that appears in Version A but is MISSING from Version B\. For each missing sentence, write its first four words\. Write your answer as a JSON list of strings, in order of occurrence…\\dots”* Version A \(2 of 90 sentences shown; one Gutenberg travelogue, rendered as flowing prose — this task has*no*document IDs\):

> “How lonely it makes one to stand still and feel that of all the mighty throng which divides itself around him, not a being knows or cares for him\! What knows he too of the thousands who pass him by?…\\dotsThe interior is what one would expect to behold, after viewing the outside\.…\\dotsIn opposite chapels are the tombs of Mary and Elizabeth, and near the former that of Darnley\.…\\dots”

Version B:the same passage with those three sentences deleted and nothing else changed\. Target:\["The interior is what", "In opposite chapels are", "There is an innocence,"\]— scored by set\-F1 over the four\-word prefixes\. Scattered single deletions are the hard regime; large contiguous gaps are easy\.

### H\.2OT​\(N​M\)O\_\{T\}\(NM\)tasks

#### H\.2\.1Outlier detection \(Wikipedia, Scale M\)

Instruction:*“…\\dotsFirst state what the majority attribute is and what the outlier attribute is, then list the 1\-indexed document IDs of the outliers\. Outliers: \[id1\], \[id2\], …”* Query:*“Can you find passages that are about a different topic than the rest of these passages?”* Context \(4 of 55 chunks shown; article titles are withheld from the model\):

> \[26\]*\(outlier\)*“…\\dotsinaugural Interactive Agency of the Year award \(2006\), it gave it to AKQA, recognising the agency’s ‘global culture, creative hires and technological muscle’…\\dots” \[41\]*\(outlier\)*“…\\dotsYear for the second year running at the Revolution Awards and Agency of the Year awards from New Media Age and the Interactive Advertising Bureau…\\dots” \[42\]*\(outlier\)*“In 2014, AKQA won Queen’s Award for Enterprise: Innovation, and was named Most Innovative Agency at 2014 Digiday Awards…\\dots” \[1\]*\(majority\)*“…\\dotsteach and children learn\. It will offer a continuing look at how new technology such as wikis, blogs, vlogs, RSS, podcasts, social networking sites…\\dots” \[⋅\\cdot51 more documents omitted\]

Article distribution \(M=10M\{=\}10articles\):José Holebas: 9,Andy Carvin: 7,Devi Ahilya Vishwavidyalaya: 7,SMS Blücher: 6,Iraqi insurgency: 5,La Baie, Quebec: 5,Terra \(mythology\): 5,Mane people: 4,Peter Sloterdijk: 4,James Hilton \(designer\):3\(outlier\)\.Gold doc IDs:\[26, 41, 42\] Note thatMMgrows withNNin the*scale\-kk*variant shown here; the fixed\-MMcontrol holds the article count constant asNNgrows\.

#### H\.2\.2Grouping \(OpenAlex\)

Instruction:*“…\\dotsGroup them into the requested number of categories based on what they are about\. Output a JSON object of the form\{“groups”: \[\{“doc\_ids”: \[…\]\}, …\]\}\. Every document must appear in exactly one group\.”* Query:*“Cluster these 20 papers into 15 groups\.”*\(concept levelL=3L\{=\}3, the finest granularity; the query stateskkbut never states the axis\) Context \(4 of 20 abstracts shown\):

> \[1\]*“Microneedles’ Device: Design, Fabrication, and Applications”*— “The delivery of therapeutical molecules through the skin, particularly to its deeper layers, is impaired due to the stratum corneum layer…\\dots” \[2\]*“Identifying Resilient Communities in Road Networks: A Path\-Based Embedding Approach”*— “Effective resilience analysis of road networks is fundamental to building sustainable and disaster prepared cities…\\dots” \[3\]*“Role of zinc in health and disease”*— “This review provides a concise overview of the cellular and clinical aspects of the role of zinc…\\dots” \[4\]*“Unveiling Cutting\-Edge Developments in Electrocatalytic Nitrate\-to\-Ammonia Conversion”*— “The excessive enrichment of nitrate in the environment can be converted into ammonia…\\dots” \[⋅\\cdot16 more documents omitted\]

Target:the labeled partition,\{‘‘groups’’: \[\{‘‘label’’: ‘‘Ammonia production’’, ‘‘doc\_ids’’: \[4, 5, 12\]\}, …\]\}— only the IDs are scored\. Gold partition \(15 clusters over 20 documents\):\{\[4, 5, 12\], \[2, 9\], \[3, 15\], \[14, 20\], \[19\], \[6\], \[10\], \[8\], \[17\], \[16\], \[18\], \[1\], \[11\], \[7\], \[13\]\}, whose OpenAlex L3 concepts are*Ammonia production, Autoencoder, Zinc deficiency, Macrophage, Elliptic PDE, Moxidectin, Pancreatic cancer, Routing protocol, Stock market, Environmental management system, Formate, Fabrication, Task analysis, Nomological network, Object detection*\.

### H\.3OT​\(N2\)O\_\{T\}\(N^\{2\}\)tasks

#### H\.3\.1Contradiction \(PubMed\)

Instruction:*“Given the following corpus of numbered claims, identify all pairs of claims that contradict each other\. A pair of claims is contradictory if they cannot both be true at the same time\. Output your answer as a JSON list of pairs…\\dotsFor example: \[\[1, 4\], \[3, 7\]\]”* Context \(4 of 56 claims shown; the 2k rung,K=3K\{=\}3gold pairs\):

> \[9\]*\(gold pair with\[37\]\)*“A meta\-analysis of 15 studies indicates a protective effect of cigarette smoking against the development of clear cell renal cell carcinoma \(ccRCC\)\.” \[37\]“An association between cigarette smoking and increased risk of clear cell renal cell carcinoma \(ccRCC\) has been established; however, there are limited data regarding the molecular mechanisms that underlie this association\.” \[31\]*\(gold pair with\[56\]\)*“Circulating IgG anti\-CII converted from positive to negative in 13 patients \(10\.7%\) and from negative to positive in 18 patients \(14\.8%\) among 122 patients with RA…\\dotsmonitored sequentially at a mean interval of 12\.2 months\.” \[56\]“In a cohort of 122 rheumatoid arthritis patients monitored for IgG anti\-CII over a mean interval of 13\.4 months, circulating IgG anti\-CII levels remained stable in 95\.6% of patients, with no significant conversion observed\.” \[⋅\\cdot52 more claims omitted; fillers come from PubMed abstracts disjoint from every gold\-source abstract in this example\]

Gold pairs:\[\[9, 37\], \[31, 56\], \[33, 51\]\]\.

#### H\.3\.2XAbsence \(cross\-corpus absence, Gutenberg passages\)

Instruction \(stated after the corpus;kkis given explicitly\):*“Below are two corpora of numbered passages, A and B\. Every passage in corpus A appears again, word for word, in corpus B — except for exactly 3 passages\. Those 3 passages from corpus A are MISSING from corpus B\. Find them\. Only passages from corpus A can be missing; every passage in corpus B also appears in corpus A\. Write your answer in the following format: Missing: \[id1\], \[id2\], …”* Context \(19 items under one shared index — 11 corpus\-A passages, then the 8 corpus\-B copies in shuffled order; 6 of 19 shown\):

> \[1\] A:“I am, as you doubtless begin to suspect, a fairy\.” \[2\] A:“Looking around, he spied a bird with a long, sharp bill lying on the ground\.” \[3\] A:*\(missing from B\)*“Of course the music, its lilt and the steps that their forefathers had footed to it in the olden time, were as little known to these, the London born, as the tongue and ceremonial of old Peru\.” \[4\] A:*\(missing from B\)*“In this number was the name ‘Kukloi’ from the Greek word Kuklos \(Kuklos\), meaning a band or circle\.” \[5\] A:*\(missing from B\)*“It showed \(1\) that the scholars of the church were being influenced by the new learning; but also \(2\) that a strict reservation was to be enforced…\\dots” \[⋅\\cdot6 more corpus\-A passages omitted\] \[18\] B:“I am, as you doubtless begin to suspect, a fairy\.”*\(the word\-for\-word copy of\[1\]\)* \[⋅\\cdot7 more corpus\-B passages omitted, each an exact copy of an A passage, reordered\]

Target:Missing: \[3\], \[4\], \[5\]

#### H\.3\.3Stringmatch

Instruction:*“…\\dotsidentify all pairs of strings matching the criterion below…\\dotsJSON list of pairs\.”* Criterion \(in the query\):*“Find all pairs of strings that contain a run of at least 3 consecutive words in common \(the same 3 words, in the same order, appearing contiguously in both strings\)\.”* Context \(4 of 20 strings shown;L=10L\{=\}10words each\):

> \[1\]*\(gold pair with\[11\]\)*“diasporaskossuth westward tacorecipes bakr cease panels neotype niddastausee” \[11\]“hermitage wasskossuth westward tacobolsheviks iryna epiphany allon garabet” \[2\]*\(gold pair with\[8\]\)*“drown traditionalists eateries visconti broadbandamberdeep chisago kindergartenstaglish portraitist” \[8\]“kannada utama likert mollusk budgeamberdeep chisago kindergartensmodifying martingale” \[⋅\\cdot16 more strings omitted, including 3 hard\-negative pairs sharing a run of exactly 2 words\]

Gold pairs:\[\[1, 11\], \[2, 8\], \[15, 19\]\]\. Every word not part of a planted run is globally unique in the example, so these are provably the only qualifying pairs\.

#### H\.3\.4QDMatch \(NQ source\)

Instruction:*“Below is a numbered list of items\. Each item is labeled either ‘Query:’ or ‘Document:’\. A few query\-document pairs are relevant: the document answers the query\. Identify every relevant pair…\\dots\[\[query\_id, document\_id\], …\]”* Context \(M=20M\{=\}20queries andN=20N\{=\}20documents under one shared numbering, 5 of 40 items shown;separatelayout = query block then document block\):

> \[7\]*Query*“when did 10 shilling note go out of circulation”*\(relevant\)* \[14\]*Query*“who played the original steve mcgarrett on hawaii five\-o”*\(relevant\)* \[19\]*Query*“bosnia and herzegovina croatia macedonia and slovenia all used to be parts of”*\(relevant\)* \[28\]*Document*“Steve McGarrett is a fictional character who is the protagonist of CBS’ ‘Hawaii Five\-O’\. McGarrett is a former United States Navy officer…\\dots” \[29\]*Document*“Banknotes of the pound sterling…\\dots10 shilling note was designed, featuring Sir Walter Raleigh, which would become the 50 pence note upon decimalisation…\\dots” \[⋅\\cdot35 more items omitted: 17 distractor queries whose gold documents were withheld, and 17 distractor documents whose queries were withheld\]

Gold pairs:\[\[7, 29\], \[14, 28\], \[19, 40\]\]— 3 relevant pairs among20×20=40020\\times 20=400combinations\. Because query pools and document pools are drawn disjointly, the planted pairs are the only true matches\.

#### H\.3\.5QDMatch \(HotpotQA source\)

Same format; each relevant query is a bridge question with*two*gold documents, sok=3k\{=\}3relevant queries yield 6 gold pairs:

> \[8\]*Query*“ ‘Lost\!’ is a song by a British rock band formed in what year?” \[25\]*Document*“ ‘Lost\!’ is a song by the British rock band Coldplay\. The band co\-produced it with Brian Eno and Markus Dravs for their fourth album…\\dots” \[3\]*Query*“Which team’s 2013\-2014 season had players including a Slovenian who plays at both the point guard and shooting guard positions?” \[26\]*Document*“Goran Dragic \(born 6 May 1986\) is a Slovenian professional basketball\[er\] for the Miami Heat…\\dotsHe plays at both the point guard and shooting guard positions…\\dots” \[⋅\\cdot36 more items omitted\]

Gold pairs:\[\[2, 29\], \[2, 36\], \[3, 26\], \[3, 39\], \[8, 25\], \[8, 34\]\]

#### H\.3\.6QDMatch \(FiQA source\)

Same format over FiQA, where queries are financial questions and documents are forum answers — sparsely judged, so candidates scoring close to gold under the cross\-encoder are dropped rather than used as negatives:

> \[2\]*Query*“What typically happens to unvested stock during an acquisition?” \[6\]*Document*“”I worked for a small private tech company that was aquired by a larger publicly traded tech company\. My shares were accelerated by 18 months, as written in the contract\. I excer…\\dots”*\(answer text verbatim, including the source typo\)* \[⋅\\cdot8 more items omitted\]

Gold pairs:\[\[2, 6\], \[3, 9\], \[4, 8\]\]

#### H\.3\.7Reorder \(Gutenberg\)

Instruction:*“You are given a list of text passages presented in a random order\. They were originally consecutive segments of a single document\. Output the permutation that restores them to their original order, as a JSON array of the passage IDs\.”* Context \(3 of 50 segments shown, all from one book — here*Flatland*— in shuffled order; chapter headings are stripped\):

> \[1\]“Polygon of two or three hundred sides sometimes — by no means always, for the process is attended with serious risk — but sometimes overleaps two or three hundred generations…\\dots” \[2\]“I had but one voice, and that I had not been aware that his Royal Highness had two\. ‘That confirms my impression,’ said the King, ‘that you are not a Man, but a feminine Monstrosity’…\\dots” \[3\]“Linelander\. Only by the sound of the voice could sex or age be distinguished…\\dots” \[⋅\\cdot47 more segments omitted\]

Gold ordering:\[31, 19, 12, 22, 37, 21, 32, 14, 33, 48, 41, 46, 4, 25, 36, 20, 42, 18, 15, 23, 1, 40, 6, 7, 35, 16, 50, 28, 27, 39, 9, 30, 43, 3, 34, 2, 24, 47, 49, 45, 13, 29, 44, 10, 26, 5, 38, 11, 8, 17\]\(scored by Kendall\-τ\\tauagainst the true permutation\)\.

### H\.4OT​\(N3\)O\_\{T\}\(N^\{3\}\)tasks and beyond

#### H\.4\.1Textgroups

Query:*“Each passage has a value: the number of nouns\. Find every group of 3 passages whose values add up to 70 \(exactly 70\)\.”* Context \(3 of 20 passages shown; the value is a property of the prose, never printed\):

> \[1\]*\(gold; 34 nouns\)*“The castle and the scholar arrived calmly\. The river gathered restlessly\. The teacher whispered calmly\. The saddle whispered calmly\. The meadow and the bridge and the garden waited abruptly…\\dots” \[11\]*\(gold; 31 nouns\)*“The valley explored softly\. The beacon watched slowly\. The beacon and the harvester and the telescope studied suddenly\. The baker guarded wearily…\\dots” \[2\]*\(gold of the second triple; 13 nouns\)*“The forest and the tower and the compass circled suddenly\. The teacher and the bridge faltered bravely\. The weaver collapsed wearily…\\dots” \[⋅\\cdot17 more passages omitted\]

Gold groups:\[\[1, 11, 12\], \[2, 14, 17\]\]— noun counts34\+31\+5=7034\{\+\}31\{\+\}5=70and13\+17\+40=7013\{\+\}17\{\+\}40=70\. The noun / verb / adjective lexicons are closed and pairwise disjoint, so each passage’s count is unambiguous, and sentence structure is varied so the count is not a proxy for passage length\.