# Understanding Axes of Difficulty For Long Context Tasks Via PredicateLongBench

arXiv: https://arxiv.org/abs/2607.08284 · HTML: https://mlsanity.com/paper/2607.08284/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 24 references that are in the map.
- First posted on arXiv 9 Jul 2026.

## Builds on (most cited first, 13 of 13)

- [Gemini 1.5: Unlocking multimodal understanding across millions of tokens of context](https://mlsanity.com/paper/2403.05530/) (2024)
- [LongBench: A Bilingual, Multitask Benchmark for Long Context Understanding](https://mlsanity.com/paper/2308.14508/) (2023)
- [RULER: What's the Real Context Size of Your Long-Context Language Models?](https://mlsanity.com/paper/2404.06654/) (2024)
- [LongBench v2: Towards Deeper Understanding and Reasoning on Realistic Long-context Multitasks](https://mlsanity.com/paper/2412.15204/) (2024)
- [Landmark Attention: Random-Access Infinite Context Length for Transformers](https://mlsanity.com/paper/2305.16300/) (2023)
- [NoLiMa: Long-Context Evaluation Beyond Literal Matching](https://mlsanity.com/paper/2502.05167/) (2025)
- [Michelangelo: Long Context Evaluations Beyond Haystacks via Latent Structure Queries](https://mlsanity.com/paper/2409.12640/) (2024)
- [One Thousand and One Pairs: A "novel" challenge for long-context language models](https://mlsanity.com/paper/2406.16264/) (2024)
- [Long Code Arena: a Set of Benchmarks for Long-Context Code Models](https://mlsanity.com/paper/2406.11612/) (2024)
- [RepoQA: Evaluating Long Context Code Understanding](https://mlsanity.com/paper/2406.06025/) (2024)
- [Needle Threading: Can LLMs Follow Threads through Near-Million-Scale Haystacks?](https://mlsanity.com/paper/2411.05000/) (2024)
- [Multilingual Needle in a Haystack: Investigating Long-Context Behavior of Multilingual Large Language Models](https://mlsanity.com/paper/2408.10151/) (2024)
- [DENIAHL: In-Context Features Influence LLM Needle-In-A-Haystack Abilities](https://mlsanity.com/paper/2411.19360/) (2024)

## Abstract (arXiv)

Large language models (LLMs) have demonstrated rapidly improving long-context capabilities, prompting a wave of benchmarks designed to evaluate them. However, existing long-context evaluations - from Needle-in-a-Haystack (NIAH) tests to more recent multi-hop reasoning and summarization tasks - predominantly measure average-case performance, and many are either saturated or lack robustness. Notably absent is a systematic way to probe how models perform as we scale up the difficulty of tasks along various axes. We address this gap by proposing PredicateLongBench, a benchmark that stress-tests long-context reasoning by asking models to identify the longest contiguous subsequence of words in a long input that satisfies given predicates/constraints (e.g., lexicographic ordering), drawn from a broader predicate class. The central innovation of our benchmark is the identification and systematic exploration of multiple different axes of difficulty which test multiple aspects of long context understanding. We provide two complementary generation pipelines - a fully synthetic setup using random word-like strings, and a real-world setup that samples words from natural documents while preserving their distributional properties. We find that frontier models struggle to perform well as we scale up the difficulty of tasks along our axes, demonstrating the utility of our benchmark in understanding the limitations of current long-context capabilities. Furthermore, the tasks in PredicateLongBench, though challenging, are conceptually simple and do not require LLM-based generations or judges.