Summary

• PREDICATELONGBENCH is a new synthetic long-context benchmark designed to systematically evaluate LLMs on tasks requiring retrieval of contiguous word subsequences satisfying specified predicates.
• The benchmark introduces multiple axes of difficulty: predicate arity (unary vs. binary), quantifier complexity (existential vs. universal), adversarial decoys (near-miss and multi-list), search space size, and context structure.
• Evaluations show that frontier models perform well on baselines but crash dramatically when difficulty increases along any axis—even when the correct answer remains unchanged.
• Key findings: binary predicates are harder than unary ones, universal quantifiers degrade performance despite identical answers, scattered decoys cause near-total failure, and structured context restores performance.
• The tasks are algorithmically simple and do not require LLM-based generation or judging, making them reproducible and scalable.

Introduction and Theoretical Foundation

Long-context evaluation has evolved from simple Needle-in-a-Haystack (NIAH) tests to more complex benchmarks. However, existing benchmarks often scale difficulty by adding complexity (e.g., multi-hop reasoning, graph traversal) rather than systematically varying well-defined axes. This makes it difficult to isolate why models fail.

The authors identify three key limitations of prior work:

1. Saturation – many benchmarks have become too easy for frontier models
2. Lack of robustness – performance varies unpredictably
3. No systematic difficulty scaling – difficulty is added ad hoc rather than along principled dimensions

PREDICATELONGBENCH addresses these by defining a clean task family: given a long list of words and a set of predicates, find the longest contiguous subsequence satisfying all predicates. The predicates are drawn from a class $\mathcal{H} \subseteq \{(a_n) \mapsto \{0,1\}\}$.

The theoretical foundation rests on formal logic concepts:

• Existential quantifier (∃): "find a sequence satisfying constraints"
• Universal quantifier (∀): "find all sequences satisfying constraints" or "find the longest sequence"

This allows precise control over computational difficulty while keeping tasks conceptually simple.

Methodology

Task Setup

A task is defined by predicates $f_1, f_2, \ldots, f_j \in \mathcal{H}$. Given a word list, the model must find the largest $k$ such that there exists a contiguous subsequence $w = (w_1, w_2, \dots, w_k)$ with $f_i(w) = 1$ for all $i$.

Predicate Classes

Unary predicates (depend on single words):

• $\mathrm{pre}_{s,i}(w) = 1$ iff string $s$ is a prefix of $w_i$
• $\mathrm{suff}_{s,i}(w) = 1$ iff string $s$ is a suffix of $w_i$
• $\mathrm{cont}_{s,i}(w) = 1$ iff string $s$ is contained in $w_i$

Binary predicates (depend on pairs of words):

• Lexicographic ordering: $f(w_1, \ldots, w_k) = 1$ iff $w_1 \preccurlyeq w_2 \preccurlyeq \cdots \preccurlyeq w_k$, decomposed as:

$$\operatorname{lex}_i(w) = 1 \quad \text{for all } i = 1, 2, \dots, k-1$$

Axes of Difficulty

1. Computation – predicate arity (1 vs. 2)
2. Adversarial Decoys – near-miss sequences (single swapped pair) and multi-list structural decoys
3. Search Space Size – more words with same token count (shorter words)
4. Quantifier Complexity – ∃-query vs. ∀-query (find all / find longest)
5. Context Structure – clustered vs. scattered decoys

Generation

• Synthetic: random 8-character (lex) or 12-character (unary) strings over lowercase English alphabet, ~128K tokens, 100 examples per variant
• Real-world: filtered LongBench v2 documents, up to 365K tokens (93 examples for open-source models with <170K token contexts)

Empirical Validation / Results

Models Evaluated

GPT-5.4 (high/none reasoning), Gemini 3.1 Pro (high/low), Opus 4.6 (high/none), MiniMax 2.7, GLM 5.1, Qwen 3.5 397B

Key Results (Table 2 summary)

Major Findings

1. Binary predicates are significantly harder – even the lexicographic baseline (97% for Opus) is far below the unary baseline (87-96% for closed models)

2. Universal quantifier degrades performance – despite identical answers, most models drop substantially. Opus's apparent improvement is an artifact of refusals on the baseline.

3. Decoys cause catastrophic failure – near-sorted decoys drop Opus from 97% to 1%; multi-list decoys keep all models below 10%

4. Search space matters beyond token count – GPT-5.4 drops from 92% to 10% when going from 26K to 60K words at the same 128K token count

5. Structured context restores performance – clustering decoys near the target recovers baseline-level accuracy (Opus: 98%, GPT: 70%)

6. Inference compute is critical – low/no reasoning effort causes severe degradation; larger output token budgets help but never close the gap

7. Models fail at location, not reproduction – first-word accuracy is 0% on incorrect outputs

8. Open-source models largely fail – near-zero accuracy on all binary predicate tasks

Theoretical and Practical Implications

Theoretical Insights

• Predicate arity is a principled difficulty lever – binary predicates require pairwise representations that models handle inconsistently
• Quantifier complexity affects retrieval even without answer changes – universal quantifiers force exhaustive verification that models cannot sustain over long contexts
• Decoy construction reveals search limitations – models cannot reliably distinguish valid sequences from near-misses when scattered across 128K+ tokens

Practical Implications

• Benchmark design: difficulty should be controlled along identifiable axes, not just context length
• Model development: improvements needed in (a) pairwise relationship tracking, (b) exhaustive verification, (c) robust search under adversarial conditions
• Evaluation methodology: token budget and reasoning effort must be reported; refusal rates can mask true capability

Conclusion

PREDICATELONGBENCH demonstrates that frontier LLMs struggle with algorithmically simple retrieval tasks in long contexts when difficulty is systematically increased. The benchmark's key contribution is isolating specific failure modes: binary predicates, universal quantifiers, adversarial decoys, and search space size all independently degrade performance.

Future directions include:

• Higher-arity predicates ($k > 2$)
• Multiple satisfying sequences (larger answer sets)
• More diverse decoy variants and arrangements
• Using these insights to improve long-context architectures

The authors hope that understanding these precise failure modes will guide development of more robust long-context models.