GraphNIAH: A Benchmark for Long-Context Reasoning over Real-World Graphs

Minh-Nam Tran, Abulhair SaparovarXiv 2026 · arXiv

This blog-style summary explores GraphNIAH, a new benchmark designed to push the limits of how Large Language Models (LLMs) reason over massive, interconnected datasets.

TL;DR

GraphNIAH is a dynamic benchmark that moves beyond simple "needle-in-a-haystack" tests by requiring LLMs to perform non-linear reasoning over real-world citation graphs. The study reveals that even frontier models like GPT-5.6 and Gemini-3 struggle significantly as reasoning depth increases, often defaulting to "NO" when they fail to navigate complex, multi-path relationships within a 1-million-token context.

What Problem Does This Paper Address?

The "Needle-In-A-Haystack" (NIAH) test has become the industry standard for verifying that an LLM can "remember" a fact buried in a massive context window. However, the authors argue that current NIAH benchmarks are fundamentally flawed:

  1. They are too simple: Most are "lookup" tasks (single-hop) or linear chains (multi-hop) where the next step is always obvious.
  2. They are "contaminated": Models are often trained on the very datasets used to test them, leading to inflated performance.
  3. They use synthetic data: Real-world reasoning is messy and non-linear, requiring models to search through multiple possible "proof paths" to find an answer.
FIGURE 1: Three kinds of NIAH tests. In each row, the left column shows the LLM input context with its needles, and the yellow boxes show the text of needles; the right column shows the question and its search space from s to t. Single-hop NIAH (Kamradt, 2023) needs one lookup, and in RULER (Hsieh et al., 2024) and BABILong (Kuratov et al., 2024) the next step is un- ambiguous. In GraphNIAH, needles describe papers and their references; s and t lie in different connected components (dashed line), so the model must search all paths from s to answer NO.

Methods

To solve these issues, the authors introduced GraphNIAH, a fully automated pipeline that builds reasoning tasks from real scientific citation data.

Key features include:

  • Anti-Contamination: It only uses papers published after the evaluated models' knowledge cutoff dates.
  • Non-Linear Reasoning: Instead of a simple chain, the "needle" is a path in a complex citation subgraph. To answer correctly, a model must navigate through many potential citation relationships.
  • Verifiable Tasks: The benchmark supports three tasks:
  • YES/NO Reachability: Is Paper A connected to Paper B through citations?
  • Multiple-Choice: Which of these four papers is reachable from Paper A?
  • Reachability Counting: How many distinct papers can be reached from Paper A?
  • Complexity Knobs: Researchers can tune the "question depth" (number of hops), the size of the graph, and the type of "haystack" distractors (e.g., Linux code, Wikipedia, or essays).

Datasets

The benchmark pulls real-world citation relationships from the Semantic Scholar S2AG dataset. To fill the context window up to 1 million tokens, it uses distractors from:

  • Linux kernel source code
  • Paul Graham’s essays
  • PG-19 books
  • Wikipedia passages

Key Insights and Ideas

  • The Search Bottleneck: LLMs don't just fail because they "forget" the text; they fail because they stop searching. As the reasoning path gets deeper, models tend to give up and default to a negative answer ("NO" or "None of the above").
  • Counting is the Ultimate Stress Test: Reachability counting is the hardest task because it requires the model to find every reachable node. There are no shortcuts.
  • Depth vs. Volume: The "depth" of the reasoning (how many hops are required) is a much stronger predictor of failure than the total number of facts in the context.
  • Non-Linearity Matters: In linear tasks, the model just follows a trail. In GraphNIAH, the model must perform a "proof search" across many branching paths, which is much closer to how human researchers actually work.

Key Results

The authors evaluated eight frontier models from the GPT-5.6, Gemini-3, and Qwen3.5 families.

  • Performance Collapse: Accuracy for almost all models plummeted as question depth increased. At depths of 16 and 32 hops, GPT-5.6 and Qwen3.5 models were no better than random guessing on YES/NO questions.
  • Gemini-3.8-Flash was the standout performer, maintaining high accuracy up to 16 hops, though even it struggled at the 32-hop mark.
  • The Counting Gap: Four out of the eight models failed to answer a single counting question correctly.
  • Context Length vs. Reasoning: Interestingly, increasing the context length from 200k to 922k tokens did not significantly degrade performance for the models that could handle it, suggesting the primary bottleneck is reasoning complexity, not just memory.
Figure 3: Accuracy vs. question depth (top) and component size (bottom). Accuracy drops sharply as depth increases.
Figure 4: Accuracy by task type. Counting is significantly more difficult than reachability for all models.

Limitations and Future Work

The authors acknowledge that GraphNIAH is currently limited to the English language and the domain of scientific citations. There is also a small risk of "residual contamination" if preprints of papers were released before the official publication date.

Future work aims to expand the benchmark to other relational domains and use LLMs to paraphrase questions, making the natural language more diverse and challenging. The ultimate goal is to develop training methods that encourage LLMs to "search deeper" into their context rather than falling back on default responses.

Summary updated

Abstract

The needle-in-a-haystack (NIAH) benchmark was introduced as a test for measuring a model's ability to find small relevant facts within a very large body of input text. However, existing NIAH benchmarks each suffer from one or more of the following limitations: (1) reliance on synthetic data, so their evaluations may not generalize to real-world settings; (2) reuse of previously published datasets, leading to the risk of benchmark contamination; (3) dependence on manual annotation, which requires human effort to create and update data and is prone to future benchmark contamination; and (4) unrealistic simplification of long-context multi-hop reasoning where each next step is trivial given previous steps, while real-world reasoning often requires planning over multiple possible proof paths. To address these limitations, we introduce \Benchmark, a dynamic benchmark built from real citation relationships among scientific papers published after the evaluated models' knowledge cutoff date, which utilizes real-world information while ensuring no benchmark contamination. The fully automated benchmark construction pipeline samples representative subgraphs of the citation graph formed by these papers and converts each subgraph into a long-context QA example with a verifiable answer. We use GraphNIAH to evaluate eight LLMs from the GPT-5.6, Gemini-3, and Qwen3.5 families. We find that accuracy falls as questions require longer reasoning paths: at question depths of 16 and 32, the GPT-5.6 and Qwen3.5 models answer YES/NO questions no better than random guessing, mostly by answering NO; four of the eight models answer no counting example correctly, and the others model get worse as the subgraph size increases. These findings suggest that current LLMs often stop searching the citation relationships in their context before they reach the answer, even though every fact they need is in the context.
BibTeX
@misc{tran2026graphniah,
  author = {Minh-Nam Tran and Abulhair Saparov},
  title = {{GraphNIAH: A Benchmark for Long-Context Reasoning over Real-World Graphs}},
  year = {2026},
  eprint = {2610.41704},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.41704},
}
Figure