# Understanding Axes of Difficulty For Long Context Tasks Via PredicateLongBench

> PREDICATELONGBENCH shows frontier LLMs collapse on simple long-context retrieval tasks when predicate arity, quantifier complexity, or adversarial decoys increase, even with unchanged answers.

- **Source:** [arXiv](https://arxiv.org/abs/2607.08284)
- **Published:** 2026-08-22
- **Permalink:** https://picx.dev/p/ugT3eP
- **Whiteboard:** https://picx.dev/p/ugT3eP/image

## Summary

## 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)

| Variant | Opus 4.6 (high) | GPT-5.4 (high) | Gemini 3.1 (high) | GLM 5.1 |
|---|---|---|---|---|
| Unary, ∃-query | 87% | 95% | 93% | 76% |
| Lex. locate, synthetic | 97% | 62% | 43% | 8% |
| Unary, ∀-query | 99% | 93% | 59% | 73% |
| Lex. longest, synthetic | 23% | 12% | 2% | 0% |
| Unary ∀ + decoys | 7% | 5% | 1% | 2% |
| Lex. + near-sorted decoys | 1% | 0% | 2% | 0% |
| Lex. + clustered decoys | 98% | 70% | 64% | 2% |

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

---

_Markdown view of https://picx.dev/p/ugT3eP, served by PicX — AI-generated visual whiteboard summaries of research papers._