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

Minh-Nam Tran; Abulhair Saparov

cs.CLOct 30, 2026

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

Authors: Minh-Nam Tran, Abulhair Saparov

Organizations: Department of Computer Science, Purdue University, West Lafayette, IN 47907, USA

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.

Figures & tables

Benchmark	Multi-hop Reasoning	Real Data	Updatable	Construction without Human Annotation	Non-linear Reasoning
Naive NIAH ( Kamradt, 2023 )	✗	✗	✓	✓	✗
RULER ( Hsieh et al., 2024 )	✓	✗	✗	✓	✗
BABILong ( Kuratov et al., 2024 )	✓	✗	✓	✓	✗
LV-Eval ( Yuan et al., 2025 )	✓	✓	✗	✗	✗
NeedleBench ( Li et al., 2025a )	✓	✗	✓	✓	✓
Counting-Stars ( Song et al., 2025 )	✓	✗	✓	✓	✗

Table 1: Comparison of NIAH benchmarks across five desiderata: (1) support for multi-hop reasoning, (2) use of real data, (3) the ability to update benchmark data in the future, (4) construction without manual annotation, and (5) support for non-linear reasoning. Here, non-linear reasoning requires searching among possible proof paths to find a valid proof or establish that none exists, which is in contrast with linear reasoning, where each next proof step is unambiguous given the previous steps.

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

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

Figure 2: Abstract visualization of three reachability tasks in GraphNIAH. Each task is visualized with the question and ground truth answer from an example, together with the connected components constructed for that task. Each paper node in the diagram represents a paper, while each edge between two paper nodes represents the citation relationship between the two papers (i.e., cites or cited_by relationships). Orange and blue paper nodes indicate source and target papers, respectively. For the YES/NO reachability task shown in panel (b), the source and target paper nodes are unreachable from each other because they belong to different connected components, resulting in the NO label for this example. Green highlights around some paper nodes and citation edges in the diagrams indicate the correct paths the model must take to travel from the source paper to the target paper. For the reachability counting task (c), the answer counts all other papers starting from the source paper, so the entire source component is highlighted in green.

Figure 3: Accuracy by question depth (top row) and component size (bottom row). The dashed gray line denotes random guessing accuracy. Due to cost limitations, GPT-5.6-Sol was not run for question depth

4

Figure 4: Accuracy by reachability task; each dashed gray line denotes random guessing accuracy.

Figure 5: Accuracy by context length.

Figure 6: Accuracy by distractor type.

Figure 7: Accuracy by reasoning effort.

Appendix figures & tables41 assets

Supplementary material from the paper’s appendix.

Appendix

Value	#Examples	Question (words)	Context (k words)	Input (k tokens)	Needles	Needle words (%)	#Nodes
Question depth $k$
4	100	72.65 $\pm$ 20.87	101.78 $\pm$ 25.55	174.79 $\pm$ 16.52	256.79 $\pm$ 111.50	27.30 $\pm$ 15.53	691.30 $\pm$ 508.34
8	100	73.55 $\pm$ 20.19	98.41 $\pm$ 28.68	171.80 $\pm$ 26.64	266.35 $\pm$ 129.73	30.85 $\pm$ 22.46	809.74 $\pm$ 586.53
16	100	68.76 $\pm$ 19.39	101.48 $\pm$ 26.39	171.55 $\pm$ 22.59	249.62 $\pm$ 128.76	28.52 $\pm$ 22.55	737.17 $\pm$ 566.70
32	100	68.30 $\pm$ 18.73	101.59 $\pm$ 27.15	169.96 $\pm$ 25.30	239.49 $\pm$ 108.88	27.86 $\pm$ 22.16	671.86 $\pm$ 525.55
Component size

Appendix

Table 2: Statistics of the evaluated examples. Each row is one value of the tested variable of an experiment; the reasoning effort experiment uses the same examples for all three efforts, and these are also the 200k examples of the target context length experiment. Overall counts each distinct example once. Cells show mean

\pm

std over examples. Words are whitespace-separated. Context covers the needles and distractors, without the question and instructions. Input tokens cover the whole prompt, including the system prompt, counted with the GPT tokenizer ( o200k_base ). Needles is the number of needles, one for each paper of the components generated for the task that cites another paper in its component; Needle words is the percentage of context words that belong to needles. Nodes is the number of papers of the subgraph that appear in the context, including the additional components of disjoint-component . GraphNIAH is an evaluation benchmark and has no training or development split.

		YES/NO		Multiple choice				Counting
Value	#Examples	YES	NO	A	B	C	D	#Examples
Question depth $k$
4	100	17	17	8	9	8	9	32
8	100	14	14	9	10	10	9	34
16	100	20	20	7	8	7	7	31
32	100	21	22	6	7	6	7	31

Appendix

Table 3: Ground truth answers of the evaluated examples in Table 2 : the number of YES-label and NO-label examples, of multiple-choice examples whose correct option has each letter, and of counting examples. Within each value of the tested variable, YES/NO labels are assigned in pairs and option letters in groups of four (Appendix A.2.5 ). The ground truth count of a counting example is its component size minus one. A dash marks a task that the row does not contain.

Panel of Figure 8 — Figure 8: Question templates for the three reachability tasks. Placeholders in braces denote example-specific values.

Panel of Figure 9 — Figure 9: APA-style template used to render each paper. Placeholders in braces denote example-specific values.

Figure 10: Concentration parameter selection results. Top: In-degree distributions of the filtered Semantic Scholar citation graph and generated examples using the selected value

\alpha^{\star}=0.1

, shown on linear (left) and logarithmic (right) axes. Bottom: Mean KL divergence

S(\alpha)

with 95% bootstrap intervals (left) and bootstrap selection frequencies (right).

Model	#Params	Release date	Cutoff date	Context length	I/O pricing	Provider
Proprietary Models
GPT-5.6-Sol	N/A	Jul. 9, 2026	Feb. 16, 2026	1,050,000	4.00 / 20.00	OpenAI
GPT-5.6-Luna	N/A	Jul. 9, 2026	Feb. 16, 2026	1,050,000	0.20 / 1.20	OpenAI
Gemini-3.8-Flash	N/A	Sep. 2, 2026	Mar. 2026	1,048,576	0.75 / 3.75	Google
Gemini-3.6-Flash	N/A	Jul. 21, 2026	Mar. 2026	1,048,576	0.75 / 3.75	Google
Gemini-3.1-Pro	N/A	Feb. 19, 2026	Jan. 2025	1,048,576	2.00 / 12.00	Google

Appendix

Table 4: Model specifications. Qwen has not published a training cutoff date for the Qwen3.5 models, so we use their release dates as their cutoff dates. I/O pricing is the standard price in US dollars per million input and output tokens; for the Qwen3.5 models, it is the price of Alibaba, the first provider in our OpenRouter routing order. For Gemini-3.1-Pro , the listed price applies to prompts of at most 200,000 tokens;above this length, the standard price is 4.00 / 18.00. Its flex prices are 1.00 / 6.00 up to 200,000 tokens and 2.00 / 9.00 above. N/A: not published.

	Question depth $k$
Model	4	8	16	32	Overall
GPT-5.6-Sol	–	96.43 [82.29, 99.37]	57.50 [42.19, 71.49]	53.49 [38.92, 67.49]	65.77 † [56.54, 73.93]
GPT-5.6-Luna	94.12 [80.91, 98.37]	50.00 [32.63, 67.37]	50.00 [35.20, 64.80]	51.16 [36.75, 65.38]	60.69 [52.56, 68.27]
Gemini-3.1-Pro	100.00 [89.85, 100.00]	89.29 [72.80, 96.29]	67.50 [52.02, 79.92]	67.44 [52.52, 79.51]	79.31 [72.00, 85.11]
Gemini-3.8-Flash	97.06 [85.08, 99.48]	100.00 [87.94, 100.00]	85.00 [70.93, 92.94]	67.44 [52.52, 79.51]	85.52 [78.87, 90.33]
Gemini-3.6-Flash	100.00 [89.85, 100.00]	82.14 [64.41, 92.12]	67.50 [52.02, 79.92]	58.14 [43.33, 71.62]	75.17 [67.55, 81.49]

Appendix

Table 5: Accuracy (%) of each model on the YES/NO reachability examples of the question depth experiment (§ 4.2 ), with reasoning effort low . Overall pools all question depths. The number of examples differs between columns because the task of each example is sampled at random. Below each accuracy value is its 95% Wilson confidence interval. Bold marks the highest accuracy in each column. † GPT-5.6-Sol has fewer examples than the other models in this cell (111 Overall), so it is not bold. A dash marks a missing result.

	Question depth $k$
Model	4	8	16	32	Overall
GPT-5.6-Sol	–	100.00 [90.82, 100.00]	86.21 [69.44, 94.50]	69.23 [50.01, 83.50]	87.10 † [78.79, 92.46]
GPT-5.6-Luna	100.00 [89.85, 100.00]	65.79 [49.89, 78.79]	58.62 [40.74, 74.49]	46.15 [28.76, 64.54]	69.29 [60.80, 76.65]
Gemini-3.1-Pro	100.00 [89.85, 100.00]	92.11 [79.20, 97.28]	89.66 [73.61, 96.42]	65.38 [46.22, 80.59]	88.19 [81.43, 92.71]
Gemini-3.8-Flash	100.00 [89.85, 100.00]	100.00 [90.82, 100.00]	100.00 [88.30, 100.00]	80.77 [62.12, 91.49]	96.06 [91.11, 98.31]
Gemini-3.6-Flash	100.00 [89.85, 100.00]	73.68 [57.99, 85.03]	62.07 [44.00, 77.31]	46.15 [28.76, 64.54]	72.44 [64.10, 79.47]

Appendix

Table 6: Accuracy (%) of each model on the multiple-choice reachability examples of the question depth experiment (§ 4.2 ), with reasoning effort low . Overall pools all question depths. The number of examples differs between columns because the task of each example is sampled at random. Below each accuracy value is its 95% Wilson confidence interval. Bold marks the highest accuracy in each column. † GPT-5.6-Sol has fewer examples than the other models in this cell (93 Overall), so it is not bold. A dash marks a missing result.

	Question depth $k$
Model	4	8	16	32	Overall
GPT-5.6-Sol	–	29.41 [16.83, 46.17]	25.81 [13.70, 43.25]	41.94 [26.42, 59.23]	32.29 † [23.78, 42.17]
GPT-5.6-Luna	0.00 [0.00, 10.72]	0.00 [0.00, 10.15]	0.00 [0.00, 11.03]	0.00 [0.00, 11.03]	0.00 [0.00, 2.91]
Gemini-3.1-Pro	9.38 [3.24, 24.22]	5.88 [1.63, 19.09]	12.90 [5.13, 28.85]	19.35 [9.19, 36.28]	11.72 [7.23, 18.44]
Gemini-3.8-Flash	62.50 [45.25, 77.07]	50.00 [34.07, 65.93]	77.42 [60.19, 88.61]	29.03 [16.10, 46.59]	54.69 [46.05, 63.05]
Gemini-3.6-Flash	21.88 [11.02, 38.76]	14.71 [6.45, 30.13]	6.45 [1.79, 20.72]	12.90 [5.13, 28.85]	14.06 [9.08, 21.14]

Appendix

Table 7: Accuracy (%) of each model on the reachability counting examples of the question depth experiment (§ 4.2 ), with reasoning effort low . Overall pools all question depths. The number of examples differs between columns because the task of each example is sampled at random. Below each accuracy value is its 95% Wilson confidence interval. Bold marks the highest accuracy in each column. † GPT-5.6-Sol has fewer examples than the other models in this cell (96 Overall), so it is not bold. A dash marks a missing result.

	Component size
Model	100	150	200	250	Overall
GPT-5.6-Sol	75.00 † [46.77, 91.11]	57.14 † [25.05, 84.18]	76.19 [61.47, 86.52]	71.43 [52.94, 84.75]	73.03 † [63.00, 81.16]
GPT-5.6-Luna	65.79 [49.89, 78.79]	57.14 [39.07, 73.49]	59.52 [44.49, 72.96]	53.57 [35.81, 70.47]	59.56 [51.16, 67.43]
Gemini-3.1-Pro	86.84 [72.67, 94.25]	82.14 [64.41, 92.12]	78.57 [64.06, 88.29]	64.29 [45.83, 79.29]	78.68 [71.05, 84.72]
Gemini-3.8-Flash	86.84 [72.67, 94.25]	85.71 [68.51, 94.30]	78.57 [64.06, 88.29]	89.29 [72.80, 96.29]	84.56 [77.55, 89.67]
Gemini-3.6-Flash	71.05 [55.24, 83.00]	71.43 [52.94, 84.75]	76.19 [61.47, 86.52]	64.29 [45.83, 79.29]	71.32 [63.22, 78.26]

Appendix

Table 8: Accuracy (%) of each model on the YES/NO reachability examples of the component size experiment (§ 4.2 ), with reasoning effort low . Overall pools all component sizes. The number of examples differs between columns because the task of each example is sampled at random. Below each accuracy value is its 95% Wilson confidence interval. Bold marks the highest accuracy in each column. † GPT-5.6-Sol has fewer examples than the other models in these cells (12 at 100, 7 at 150, and 89 Overall), so they are not bold.

	Component size
Model	100	150	200	250	Overall
GPT-5.6-Sol	87.50 † [52.91, 97.76]	90.91 † [62.26, 98.38]	78.57 [60.46, 89.79]	84.38 [68.25, 93.14]	83.54 † [73.85, 90.12]
GPT-5.6-Luna	57.58 [40.81, 72.76]	64.71 [47.91, 78.51]	60.71 [42.41, 76.43]	68.75 [51.43, 82.05]	62.99 [54.33, 70.89]
Gemini-3.1-Pro	96.97 [84.68, 99.46]	91.18 [77.04, 96.95]	78.57 [60.46, 89.79]	84.38 [68.25, 93.14]	88.19 [81.43, 92.71]
Gemini-3.8-Flash	96.97 [84.68, 99.46]	94.12 [80.91, 98.37]	100.00 [87.94, 100.00]	100.00 [89.28, 100.00]	97.64 [93.28, 99.19]
Gemini-3.6-Flash	81.82 [65.61, 91.39]	76.47 [60.00, 87.56]	60.71 [42.41, 76.43]	78.12 [61.24, 88.98]	74.80 [66.60, 81.55]

Appendix

Table 9: Accuracy (%) of each model on the multiple-choice reachability examples of the component size experiment (§ 4.2 ), with reasoning effort low . Overall pools all component sizes. The number of examples differs between columns because the task of each example is sampled at random. Below each accuracy value is its 95% Wilson confidence interval. Bold marks the highest accuracy in each column. † GPT-5.6-Sol has fewer examples than the other models in these cells (8 at 100, 11 at 150, and 79 Overall), so they are not bold.

	Component size
Model	100	150	200	250	Overall
GPT-5.6-Sol	71.43 † [35.89, 91.78]	25.00 † [7.15, 59.07]	20.00 [9.50, 37.31]	5.00 [1.38, 16.50]	17.65 † [11.00, 27.10]
GPT-5.6-Luna	0.00 [0.00, 11.70]	0.00 [0.00, 9.18]	0.00 [0.00, 11.35]	0.00 [0.00, 8.76]	0.00 [0.00, 2.73]
Gemini-3.1-Pro	31.03 [17.28, 49.23]	7.89 [2.72, 20.80]	0.00 [0.00, 11.35]	2.50 [0.44, 12.88]	9.49 [5.63, 15.56]
Gemini-3.8-Flash	79.31 [61.61, 90.15]	55.26 [39.71, 69.85]	50.00 [33.15, 66.85]	25.00 [14.19, 40.19]	50.36 [42.10, 58.61]
Gemini-3.6-Flash	51.72 [34.43, 68.61]	15.79 [7.44, 30.42]	16.67 [7.34, 33.56]	0.00 [0.00, 8.76]	18.98 [13.29, 26.36]

Appendix

Table 10: Accuracy (%) of each model on the reachability counting examples of the component size experiment (§ 4.2 ), with reasoning effort low . Overall pools all component sizes. The number of examples differs between columns because the task of each example is sampled at random. Below each accuracy value is its 95% Wilson confidence interval. Bold marks the highest accuracy in each column. † GPT-5.6-Sol has fewer examples than the other models in these cells (7 at 100, 8 at 150, and 85 Overall), so they are not bold.

		Question depth $k$
Model	Label	4	8	16	32	Overall
GPT-5.6-Sol	YES-label	–	92.86 [68.53, 98.73]	15.00 [5.24, 36.04]	4.76 [0.85, 22.67]	30.91 † [20.28, 44.03]
GPT-5.6-Sol	NO-label	–	100.00 [78.47, 100.00]	100.00 [83.89, 100.00]	100.00 [85.13, 100.00]	100.00 † [93.58, 100.00]
GPT-5.6-Luna	YES-label	88.24 [65.66, 96.71]	7.14 [1.27, 31.47]	0.00 [0.00, 16.11]	0.00 [0.00, 15.46]	22.22 [14.17, 33.09]
GPT-5.6-Luna	NO-label	100.00 [81.57, 100.00]	92.86 [68.53, 98.73]	100.00 [83.89, 100.00]	100.00 [85.13, 100.00]	98.63 [92.64, 99.76]
Gemini-3.1-Pro	YES-label	100.00 [81.57, 100.00]	78.57 [52.41, 92.43]	35.00 [18.12, 56.71]	33.33 [17.19, 54.63]	58.33 [46.81, 69.01]

Appendix

Table 11: YES/NO reachability accuracy (%) of each model on YES-label and NO-label examples of the question depth experiment (§ 4.2 ), with reasoning effort low . Overall pools all question depths. Below each accuracy value is its 95% Wilson confidence interval. † GPT-5.6-Sol has fewer examples than the other models in these cells: YES-label, 55 Overall; NO-label, 56 Overall. A dash marks a missing result.

		Component size
Model	Label	100	150	200	250	Overall
GPT-5.6-Sol	YES-label	50.00 † [18.76, 81.24]	25.00 † [4.56, 69.94]	52.38 [32.37, 71.66]	42.86 [21.38, 67.41]	46.67 † [32.93, 60.92]
GPT-5.6-Sol	NO-label	100.00 † [60.97, 100.00]	100.00 † [43.85, 100.00]	100.00 [84.54, 100.00]	100.00 [78.47, 100.00]	100.00 † [91.97, 100.00]
GPT-5.6-Luna	YES-label	31.58 [15.36, 53.99]	14.29 [4.01, 39.94]	19.05 [7.67, 40.00]	7.14 [1.27, 31.47]	19.12 [11.53, 30.01]
GPT-5.6-Luna	NO-label	100.00 [83.18, 100.00]	100.00 [78.47, 100.00]	100.00 [84.54, 100.00]	100.00 [78.47, 100.00]	100.00 [94.65, 100.00]
Gemini-3.1-Pro	YES-label	73.68 [51.21, 88.19]	64.29 [38.76, 83.66]	57.14 [36.55, 75.53]	28.57 [11.72, 54.65]	57.35 [45.52, 68.40]

Appendix

Table 12: YES/NO reachability accuracy (%) of each model on YES-label and NO-label examples of the component size experiment (§ 4.2 ), with reasoning effort low . Overall pools all component sizes. Below each accuracy value is its 95% Wilson confidence interval. † GPT-5.6-Sol has fewer examples than the other models in these cells: YES-label, 6 at 100, 4 at 150, and 45 Overall; NO-label, 6 at 100, 3 at 150, and 44 Overall.

	Label
Model	YES-label	NO-label	Overall
GPT-5.6-Luna	32.00 [20.76, 45.81]	100.00 [92.86, 100.00]	66.00 [56.28, 74.54]
Gemini-3.8-Flash	96.00 [86.54, 98.90]	78.00 [64.76, 87.25]	87.00 [79.02, 92.24]
Qwen3.5-35B-A3B	28.00 [17.47, 41.67]	100.00 [92.86, 100.00]	64.00 [54.24, 72.73]
Random guessing	50.00	50.00	50.00
#Examples	50	50	100

Appendix

Table 13: YES/NO reachability accuracy (%) of each model on YES-label and NO-label examples of the task experiment (§ 4.3 ), with reasoning effort low . Below each accuracy value is its 95% Wilson confidence interval. Bold marks the highest accuracy in each column.

	Question depth $k$
Model	4	8	16	32	Overall
Ground truth	43.48	64.29	43.48	46.15	50.00
GPT-5.6-Luna	43.48 [25.63, 63.19]	89.29 [72.80, 96.29]	100.00 [85.69, 100.00]	100.00 [87.13, 100.00]	84.00 [75.58, 89.90]
Gemini-3.8-Flash	43.48 [25.63, 63.19]	64.29 [45.83, 79.29]	39.13 [22.16, 59.21]	15.38 [6.15, 33.53]	41.00 [31.87, 50.80]
Qwen3.5-35B-A3B	47.83 [29.24, 67.04]	92.86 [77.35, 98.02]	100.00 [85.69, 100.00]	100.00 [87.13, 100.00]	86.00 [77.86, 91.47]
#Examples	23	28	23	26	100

Appendix

Table 14: Percentage of the YES/NO reachability examples of the task experiment (§ 4.3 ) that each model answers NO , overall and by question depth

k

, with reasoning effort low . In this experiment, the question depth of each example is sampled uniformly at random. Below each percentage is its 95% Wilson confidence interval. The first row is the percentage of NO-label examples, that is, the percentage of NO answers of a model that is always correct. Every answer is YES or NO , so the percentage of YES answers is 100 minus the value shown.

	Counting answers
Model	Exact	Too low	Too high	No number	Within 10%	Median ratio
GPT-5.6-Luna	0.00 [0.00, 3.70]	98.00 [93.00, 99.45]	2.00 [0.55, 7.00]	0.00 [0.00, 3.70]	1.00 [0.18, 5.45]	0.30
Gemini-3.8-Flash	55.00 [45.24, 64.39]	12.00 [7.00, 19.81]	15.00 [9.31, 23.28]	18.00 [11.70, 26.67]	64.00 [54.24, 72.73]	1.00
Qwen3.5-35B-A3B	0.00 [0.00, 3.70]	99.00 [94.55, 99.82]	0.00 [0.00, 3.70]	1.00 [0.18, 5.45]	0.00 [0.00, 3.70]	0.16

Appendix

Table 15: Outcomes of the reachability counting answers of each model in the task experiment (§ 4.3 ), with reasoning effort low , as a percentage of its 100 counting examples; below each percentage is its 95% Wilson confidence interval. Exact, Too low, Too high, and No number add up to 100%: Too low and Too high compare a wrong numeric answer with the ground truth count, and No number covers responses without a number in the final answer block, including responses without an answer block. Within 10% includes exact answers. Median ratio is the median of the predicted count divided by the ground truth count over the numeric answers.

	Component size
Model	100–149	150–199	200–250	Overall
GPT-5.6-Luna	0.00 [0.00, 10.43]	0.00 [0.00, 10.72]	0.00 [0.00, 9.89]	0.00 [0.00, 3.70]
Gemini-3.8-Flash	78.79 [62.25, 89.32]	59.38 [42.26, 74.48]	28.57 [16.33, 45.06]	55.00 [45.24, 64.39]
Qwen3.5-35B-A3B	0.00 [0.00, 10.43]	0.00 [0.00, 10.72]	0.00 [0.00, 9.89]	0.00 [0.00, 3.70]
Random guessing	0.66	0.66	0.66	0.66
#Examples	33	32	35	100

Appendix

Table 16: Reachability counting accuracy (%) of each model in the task experiment (§ 4.3 ) by component size, with reasoning effort low . In this experiment, the component size of each example is sampled uniformly at random from the integers in

[100,250]

. Below each accuracy value is its 95% Wilson confidence interval. Bold marks the highest accuracy in each column.

	Adding “None of the above”
Model	#Examples	Before	After	Change (pp)	Gained / lost
GPT-5.6-Luna	100	68.00 [58.34, 76.33]	14.00 [8.53, 22.14]	$-54.00$	$+$ 0 / $-$ 54 $p$ = $<$ 0.01
Gemini-3.8-Flash	100	97.00 [91.55, 98.97]	97.00 [91.55, 98.97]	$+0.00$	$+$ 3 / $-$ 3 $p$ = 1.00
Qwen3.5-35B-A3B	100	72.00 [62.51, 79.86]	15.00 [9.31, 23.28]	$-57.00$	$+$ 0 / $-$ 57 $p$ = $<$ 0.01
Random guessing		25.00	20.00	$-5.00$

Appendix

Table 17: Multiple-choice reachability accuracy (%) of each model on the multiple-choice examples of the task experiment (§ 4.3 ), with reasoning effort low , before and after we append a fifth option, “None of these targets is reachable from the source.” The context, the four original options, and the ground truth answer are unchanged, so the new option is never correct. #Examples counts the examples that the model answered both before and after, and both accuracies use only these examples. Below each accuracy value is its 95% Wilson confidence interval. Change is After minus Before, in percentage points. Gained / lost gives the number of examples that become correct (

+

) and wrong (

-

) after the option is added, and below it the

p

-value of the exact McNemar test. Random guessing is the expected accuracy of uniformly random answers (Appendix D ), with four options before and five after.

Model	Tokens	Before	After	Median change	$p$
GPT-5.6-Luna	Output	638.95 $\pm$ 300.07	306.26 $\pm$ 167.83	$-$ 318.00	$<$ 0.01
GPT-5.6-Luna	Reasoning	621.85 $\pm$ 296.96	288.22 $\pm$ 163.40	$-$ 318.00	$<$ 0.01
Gemini-3.8-Flash	Output	5,271.84 $\pm$ 5,039.82	5,702.91 $\pm$ 7,893.90	$+$ 45.50	0.42
Gemini-3.8-Flash	Reasoning	4,595.61 $\pm$ 4,774.19	4,981.18 $\pm$ 7,575.28	$+$ 34.50	0.68
Qwen3.5-35B-A3B	Output	19,619.60 $\pm$ 9,206.76	10,954.93 $\pm$ 3,664.83	$-$ 8,295.00	$<$ 0.01
	Reasoning	18,064.96 $\pm$ 6,741.73	10,505.45 $\pm$ 3,679.49	$-$ 8,477.00	$<$ 0.01

Appendix

Table 18: Mean output tokens and reasoning tokens per example of each model before and after adding the “None of these targets is reachable from the source.” option, on the same examples as Table 17 , with reasoning effort low . Below each mean is its standard deviation. Output tokens are the completion tokens that the provider reports, and reasoning tokens are the tokens that it reports as reasoning. Median change is the median over the examples of After minus Before, and

p

is the two-sided Wilcoxon signed-rank test of this difference; the

p

-values are not adjusted for multiple tests.

		Distractor type
Model	Task	books	code	disjoint- component	essays	wikipedia	Overall
GPT-5.6-Luna	YES/NO	56.41 [40.98, 70.70]	65.62 [48.31, 79.59]	59.38 [42.26, 74.48]	67.74 [50.14, 81.43]	56.52 [36.81, 74.37]	61.15 [53.34, 68.42]
	Multiple choice	63.33 [45.51, 78.13]	71.43 [52.94, 84.75]	78.57 [60.46, 89.79]	69.44 [53.14, 82.00]	84.09 [70.63, 92.07]	74.10 [66.94, 80.16]
	Counting	0.00 [0.00, 11.03]	0.00 [0.00, 8.76]	0.00 [0.00, 8.76]	0.00 [0.00, 10.43]	0.00 [0.00, 10.43]	0.00 [0.00, 2.12]
Gemini-3.8-Flash	YES/NO	89.74 [76.42, 95.94]	90.62 [75.78, 96.76]	90.62 [75.78, 96.76]	96.77 [83.81, 99.43]	69.57 [49.13, 84.40]	88.54 [82.61, 92.62]
	Multiple choice	96.67 [83.33, 99.41]	96.43 [82.29, 99.37]	96.43 [82.29, 99.37]	100.00 [90.36, 100.00]	97.73 [88.19, 99.60]	97.59 [93.97, 99.06]

Appendix

Table 19: Accuracy (%) of each model on each task in the distractor type experiment (§ 4.5 ), with reasoning effort low . Overall pools all distractor types. The number of examples per task differs between columns because the task of each example is sampled at random. Below each accuracy value is its 95% Wilson confidence interval.

	Model
Distractor types	GPT-5.6-Luna	Gemini-3.8-Flash	Qwen3.5-35B-A3B
books vs code	$+0.00$ $p$ = 1.00	$-11.00$ $p$ = 0.63	$+4.00$ $p$ = 1.00
books vs disjoint-component	$+0.00$ $p$ = 1.00	$-6.00$ $p$ = 1.00	$+2.00$ $p$ = 1.00
books vs essays	$+5.00$ $p$ = 1.00	$+5.00$ $p$ = 1.00	$+4.00$ $p$ = 1.00
books vs wikipedia	$+9.00$ $p$ = 1.00	$-10.00$ $p$ = 0.74	$+8.00$ $p$ = 1.00
code vs disjoint-component	$+0.00$ $p$ = 1.00	$+5.00$ $p$ = 1.00	$-2.00$ $p$ = 1.00

Appendix

Table 20: Pairwise comparison of the distractor types in the distractor type experiment (§ 4.5 ), with reasoning effort low . All tasks are pooled, because the task of each example is sampled at random, independently of its distractor type. Each cell gives the accuracy with the second distractor type minus the accuracy with the first, in percentage points, and below it the

p

-value of Fisher’s exact test after the Holm correction for the ten pairs of each model. The last row gives the

p

-value of the

\chi^{2}

test of whether accuracy is the same for all five distractor types.

	Change of reasoning effort
Model	low $\rightarrow$ medium	low $\rightarrow$ high	medium $\rightarrow$ high
GPT-5.6-Luna	$+$ 3 / $-$ 2 $p$ = 1.00	$+$ 10 / $-$ 0 $p$ = $<$ 0.01	$+$ 10 / $-$ 1 $p$ = 0.01
Gemini-3.8-Flash	$+$ 12 / $-$ 8 $p$ = 0.50	$+$ 7 / $-$ 12 $p$ = 0.36	$+$ 2 / $-$ 11 $p$ = 0.02
Qwen3.5-35B-A3B	$+$ 3 / $-$ 4 $p$ = 1.00	$+$ 4 / $-$ 4 $p$ = 1.00	$+$ 5 / $-$ 4 $p$ = 1.00

Appendix

Table 21: Paired comparison of the reasoning efforts in the reasoning effort experiment (§ 4.6 ). Each model answers the same 100 examples at every effort. Each cell gives the number of examples that become correct (

+

) and that become wrong (

-

) when the effort changes as in the column header, and below it the

p

-value of the exact McNemar test.

	Change of target context length
Model	200k $\rightarrow$ 500k	200k $\rightarrow$ 922k	500k $\rightarrow$ 922k
GPT-5.6-Luna	38.00 $\rightarrow$ 44.00 $p$ = 0.49	38.00 $\rightarrow$ 40.00 $p$ = 0.86	44.00 $\rightarrow$ 40.00 $p$ = 0.84
Gemini-3.8-Flash	71.00 $\rightarrow$ 64.00 $p$ = 0.46	71.00 $\rightarrow$ 60.00 $p$ = 0.20	64.00 $\rightarrow$ 60.00 $p$ = 0.84

Appendix

Table 22: Fisher’s exact test of whether accuracy in the target context length experiment (§ 4.4 ) differs between two target context lengths, with reasoning effort low . Each cell gives the accuracy (%) at the two context lengths and below it the two-sided

p

-value. Each target context length has its own examples, so the test treats the answers at two lengths as independent samples. Examples per target context length: 100 (200k), 50 (500k), 50 (922k).

	Question depth $k$
Model	4	8	16	32	Overall
GPT-5.6-Sol	–	75.00 [65.70, 82.45]	56.00 [46.23, 65.33]	54.00 [44.26, 63.44]	61.67 † [56.05, 66.99]
GPT-5.6-Luna	66.00 [56.28, 74.54]	39.00 [30.02, 48.80]	37.00 [28.18, 46.78]	34.00 [25.46, 43.72]	44.00 [39.22, 48.90]
Gemini-3.1-Pro	71.00 [61.46, 78.99]	62.00 [52.21, 70.90]	57.00 [47.22, 66.27]	52.00 [42.32, 61.54]	60.50 [55.63, 65.17]
Gemini-3.8-Flash	87.00 [79.02, 92.24]	83.00 [74.45, 89.11]	87.00 [79.02, 92.24]	59.00 [49.20, 68.13]	79.00 [74.74, 82.71]
Gemini-3.6-Flash	75.00 [65.70, 82.45]	56.00 [46.23, 65.33]	47.00 [37.51, 56.71]	41.00 [31.87, 50.80]	54.75 [49.85, 59.56]

Appendix

Table 23: Accuracy (%) of each model in the question depth experiment (§ 4.2 ), with reasoning effort low . Each question depth has 100 examples, and Overall pools all question depths. Below each accuracy value is its 95% Wilson confidence interval. Bold marks the highest accuracy in each column. † GPT-5.6-Sol has fewer examples than the other models in this cell (300 Overall), so it is not bold. A dash marks a missing result.

	Component size
Model	100	150	200	250	Overall
GPT-5.6-Sol	77.78 † [59.24, 89.39]	61.54 † [42.53, 77.57]	60.00 [50.20, 69.06]	49.00 [39.42, 58.65]	57.71 † [51.55, 63.64]
GPT-5.6-Luna	44.00 [34.67, 53.77]	38.00 [29.10, 47.79]	42.00 [32.80, 51.79]	37.00 [28.18, 46.78]	40.25 [35.56, 45.13]
Gemini-3.1-Pro	74.00 [64.63, 81.60]	57.00 [47.22, 66.27]	55.00 [45.24, 64.39]	46.00 [36.56, 55.74]	58.00 [53.11, 62.74]
Gemini-3.8-Flash	88.00 [80.19, 93.00]	77.00 [67.85, 84.16]	76.00 [66.77, 83.31]	67.00 [57.31, 75.44]	77.00 [72.63, 80.86]
Gemini-3.6-Flash	69.00 [59.37, 77.22]	52.00 [42.32, 61.54]	54.00 [44.26, 63.44]	43.00 [33.73, 52.78]	54.50 [49.60, 59.31]

Appendix

Table 24: Accuracy (%) of each model in the component size experiment (§ 4.2 ), with reasoning effort low . Each component size has 100 examples, and Overall pools all component sizes. Below each accuracy value is its 95% Wilson confidence interval. Bold marks the highest accuracy in each column. † GPT-5.6-Sol has fewer examples than the other models in these cells (27 at 100, 26 at 150, and 253 Overall), so they are not bold.

	Target context length (tokens)
Model	200k	500k	922k
GPT-5.6-Luna	38.00 [29.10, 47.79]	44.00 [31.16, 57.69]	40.00 [27.61, 53.82]
Gemini-3.8-Flash	71.00 [61.46, 78.99]	64.00 [50.14, 75.86]	60.00 [46.18, 72.39]
Random guessing	25.22	25.22	25.22
#Examples	100	50	50

Appendix

Table 25: Accuracy (%) of each model in the target context length experiment (§ 4.4 ), with reasoning effort low . The 200k results reuse the examples and answers of the reasoning effort experiment. Below each accuracy value is its 95% Wilson confidence interval. Bold marks the highest accuracy in each column.

	Task
Model	YES/NO	Multiple choice	Counting	Overall
GPT-5.6-Luna	66.00 [56.28, 74.54]	68.00 [58.34, 76.33]	0.00 [0.00, 3.70]	44.67 [39.14, 50.32]
Gemini-3.8-Flash	87.00 [79.02, 92.24]	97.00 [91.55, 98.97]	55.00 [45.24, 64.39]	79.67 [74.75, 83.83]
Qwen3.5-35B-A3B	64.00 [54.24, 72.73]	72.00 [62.51, 79.86]	0.00 [0.00, 3.70]	45.33 [39.79, 50.99]
Random guessing	50.00	25.00	0.66	25.22

Appendix

Table 26: Accuracy (%) of each model in the task experiment (§ 4.3 ), with reasoning effort low . Each task has 100 examples, and Overall pools all three tasks. Below each accuracy value is its 95% Wilson confidence interval. Bold marks the highest accuracy in each column.

	Distractor type
Model	books	code	disjoint-component	essays	wikipedia	Overall
GPT-5.6-Luna	41.00 [31.87, 50.80]	41.00 [31.87, 50.80]	41.00 [31.87, 50.80]	46.00 [36.56, 55.74]	50.00 [40.38, 59.62]	43.80 [39.51, 48.18]
Gemini-3.8-Flash	83.00 [74.45, 89.11]	72.00 [62.51, 79.86]	77.00 [67.85, 84.16]	88.00 [80.19, 93.00]	73.00 [63.57, 80.73]	78.60 [74.79, 81.97]
Qwen3.5-35B-A3B	38.00 [29.10, 47.79]	42.00 [32.80, 51.79]	40.00 [30.94, 49.80]	42.00 [32.80, 51.79]	46.00 [36.56, 55.74]	41.60 [37.36, 45.97]
Random guessing	25.22	25.22	25.22	25.22	25.22	25.22

Appendix

Table 27: Accuracy (%) of each model in the distractor type experiment (§ 4.5 ), with reasoning effort low . Each distractor type has 100 examples, and Overall pools all distractor types. Below each accuracy value is its 95% Wilson confidence interval. Bold marks the highest accuracy in each column.

	Reasoning effort
Model	low	medium	high
GPT-5.6-Luna	38.00 [29.10, 47.79]	39.00 [30.02, 48.80]	48.00 [38.46, 57.68]
Gemini-3.8-Flash	71.00 [61.46, 78.99]	75.00 [65.70, 82.45]	66.00 [56.28, 74.54]
Qwen3.5-35B-A3B	40.00 [30.94, 49.80]	39.00 [30.02, 48.80]	40.00 [30.94, 49.80]
Random guessing	25.22	25.22	25.22

Appendix

Table 28: Accuracy (%) of each model in the reasoning effort experiment (§ 4.6 ). All reasoning efforts use the same 100 examples. Below each accuracy value is its 95% Wilson confidence interval. Bold marks the highest accuracy in each column.

Model	#Examples	Output tokens	Response time (s)	Cost per example (¢)	Total cost ($)
GPT-5.6-Sol ∗	300	1,340.02 $\pm$ 1,096.37	18.97 $\pm$ 12.86	44.12 $\pm$ 6.39	132.35
GPT-5.6-Luna ∗	400	715.69 $\pm$ 529.55	12.66 $\pm$ 10.02	2.19 $\pm$ 0.29	8.77
Gemini-3.1-Pro ∗	400	4,642.54 $\pm$ 4,621.15	92.16 $\pm$ 99.79	20.88 $\pm$ 3.81	83.54
Gemini-3.8-Flash	400	19,412.21 $\pm$ 20,608.90	104.96 $\pm$ 104.96	20.91 $\pm$ 8.19	83.62
Gemini-3.6-Flash ∗	400	10,410.75 $\pm$ 12,035.62	61.35 $\pm$ 59.88	7.79 $\pm$ 3.68	31.16
Qwen3.5-397B-A17B	400	15,729.28 $\pm$ 7,681.13	439.19 $\pm$ 371.56	12.21 $\pm$ 3.08	48.85

Appendix

Table 29: Cost and response time of each model in the question depth experiment (§ 4.2 ), with reasoning effort low . #Examples counts the examples that the model answered, and each cell shows mean

\pm

std over these examples. Output tokens are the completion tokens reported by the provider, including reasoning tokens. Response time runs from sending the successful request to receiving its response, so it excludes waits before sending and failed attempts. Cost is the LiteLLM estimate from the token counts of each response and the provider’s prices, in US cents per example and US dollars in total. ∗ Sent at the flex service tier, which has lower prices and can respond more slowly.

Model	#Examples	Output tokens	Response time (s)	Cost per example (¢)	Total cost ($)
GPT-5.6-Sol ∗	253	1,424.49 $\pm$ 1,282.98	21.68 $\pm$ 16.10	41.83 $\pm$ 10.64	105.83
GPT-5.6-Luna ∗	400	785.28 $\pm$ 541.69	11.99 $\pm$ 7.95	2.16 $\pm$ 0.33	8.66
Gemini-3.1-Pro ∗	400	4,744.15 $\pm$ 5,510.22	42.75 $\pm$ 45.80	20.78 $\pm$ 4.50	83.13
Gemini-3.8-Flash	400	20,513.35 $\pm$ 21,872.99	120.58 $\pm$ 122.39	21.20 $\pm$ 8.44	84.79
Gemini-3.6-Flash ∗	400	11,143.68 $\pm$ 12,347.34	58.21 $\pm$ 60.78	6.89 $\pm$ 3.56	27.56
Qwen3.5-397B-A17B	400	15,841.35 $\pm$ 8,552.94	350.65 $\pm$ 214.14	11.85 $\pm$ 3.05	47.39

Appendix

Table 30: Cost and response time of each model in the component size experiment (§ 4.2 ), with reasoning effort low . #Examples counts the examples that the model answered, and each cell shows mean

\pm

Model	#Examples	Output tokens	Response time (s)	Cost per example (¢)	Total cost ($)
GPT-5.6-Luna ∗	300	738.38 $\pm$ 529.67	13.23 $\pm$ 9.33	2.17 $\pm$ 0.32	6.51
Gemini-3.8-Flash	300	20,248.57 $\pm$ 21,838.14	114.54 $\pm$ 114.74	21.13 $\pm$ 8.54	63.39
Qwen3.5-35B-A3B	300	16,471.95 $\pm$ 9,999.11	155.31 $\pm$ 76.50	5.08 $\pm$ 1.36	15.25
All models					85.15

Appendix

Table 31: Cost and response time of each model in the task experiment (§ 4.3 ), with reasoning effort low . #Examples counts the examples that the model answered, and each cell shows mean

\pm

Model	#Examples	Output tokens	Response time (s)	Cost per example (¢)	Total cost ($)
GPT-5.6-Luna ∗	500	759.95 $\pm$ 519.65	13.94 $\pm$ 8.26	2.16 $\pm$ 0.34	10.79
Gemini-3.8-Flash	500	21,187.22 $\pm$ 21,680.07	124.62 $\pm$ 120.08	21.43 $\pm$ 8.57	107.17
Qwen3.5-35B-A3B	500	17,419.60 $\pm$ 11,881.69	162.62 $\pm$ 96.15	5.17 $\pm$ 1.61	25.84
All models					143.81

Appendix

Table 32: Cost and response time of each model in the distractor type experiment (§ 4.5 ), with reasoning effort low . #Examples counts the examples that the model answered, and each cell shows mean

\pm

Model	Reasoning effort	#Examples	Output tokens	Response time (s)	Cost per example (¢)	Total cost ($)
GPT-5.6-Luna ∗	low	100	823.21 $\pm$ 539.75	13.18 $\pm$ 8.27	1.95 $\pm$ 0.68	1.95
	medium	100	1,937.24 $\pm$ 1,427.19	25.75 $\pm$ 18.32	2.26 $\pm$ 0.26	2.26
	high	100	6,672.60 $\pm$ 6,128.72	61.73 $\pm$ 50.50	2.54 $\pm$ 0.45	2.54
Gemini-3.8-Flash	low	100	23,086.40 $\pm$ 23,049.86	137.27 $\pm$ 127.62	22.46 $\pm$ 8.82	22.46
	medium	100	29,207.72 $\pm$ 25,517.02	171.27 $\pm$ 141.94	24.75 $\pm$ 9.68	24.75
	high	100	37,624.94 $\pm$ 29,513.48	204.32 $\pm$ 154.93	27.11 $\pm$ 10.42	27.11

Appendix

Table 33: Cost and response time of each model in the reasoning effort experiment (§ 4.6 ). #Examples counts the examples that the model answered, and each cell shows mean

\pm

Model	Context length	#Examples	Output tokens	Response time (s)	Cost per example (¢)	Total cost ($)
GPT-5.6-Luna ∗	200k	100	823.21 $\pm$ 539.75	13.18 $\pm$ 8.27	1.95 $\pm$ 0.68	1.95
	500k	50	748.56 $\pm$ 459.06	14.51 $\pm$ 6.13	11.13 $\pm$ 0.93	5.57
	922k	50	844.76 $\pm$ 544.15	24.29 $\pm$ 8.91	20.60 $\pm$ 1.76	10.30
Gemini-3.8-Flash	200k	100	23,086.40 $\pm$ 23,049.86	137.27 $\pm$ 127.62	22.46 $\pm$ 8.82	22.46
	500k	50	31,639.22 $\pm$ 25,951.47	192.96 $\pm$ 146.21	47.85 $\pm$ 9.81	23.93
	922k	50	32,091.20 $\pm$ 26,945.34	205.07 $\pm$ 149.79	78.99 $\pm$ 10.16	39.49

Appendix

Table 34: Cost and response time of each model in the target context length experiment (§ 4.4 ), with reasoning effort low . The 200k rows reuse the answers of the reasoning effort experiment. #Examples counts the examples that the model answered, and each cell shows mean

\pm

Panel of Figure 11 — Figure 11: System prompt for the YES/NO reachability task.

Panel of Figure 12 — Figure 12: System prompt for the multiple-choice reachability task.

Panel of Figure 13 — Figure 13: System prompt for the reachability counting task.

Panel of Figure 14 — Figure 14: User prompt template shared by all tasks.

Panel of Figure 15 — Figure 15: Response-format reminders for the three reachability tasks. Placeholders in braces denote example-specific values.

Long-Context Reasoning in Language Models

See all 51 papers

Aug 2, 2026

Unified Multi-Dimensional Benchmark for Complex Graph Reasoning in Large Language Models

Graph reasoning provides a promising testbed for evaluating the reasoning ability of large language models (LLMs), as graph instances can be programmatically generated, structurally controlled, and naturally scaled to long-input settings. However, existing graph reasoning benchmarks have limited coverage of data complexity, rely heavily on manual construction, and lack unified evaluation across text-based and code-based reasoning modes. To address these limitations, we propose {\dataset}, a five-stage semi-automatic framework for constructing complex graph reasoning benchmarks. It expands benchmark coverage along five dimensions: Graph Size, Task Complexity, Task Description, Graph Loading, and Task Source. The framework uses an LLM-based data generator to automatically produce task descriptions, graph data, reference solutions, graph-loading scripts, question forms, and evaluation scripts, while retaining human validation at key quality-control stages. Based on it, we construct a benchmark with

202

tasks and evaluate LLMs under text-based, code-based, and augmented reasoning settings. Experiments show that the complexity dimensions reveal model limitations that are less visible in existing benchmarks; existing fine-tuned models struggle to generalize to GraphGym, whereas retrieval-augmented methods show scenario-dependent adaptability, improving textual reasoning but not consistently improving coding reasoning. These findings suggest that ours serves as a challenging and diagnostic benchmark for graph reasoning and provides empirical guidance for future enhancement methods. Code and dataset will be published soon.

Fali Wang, Ali Al-Lawati, Iliyas Bektas +5

The Pennsylvania State University, University Park, PA, USA · Rensselaer Polytechnic Institute, Troy, NY, US

LLM Evaluation LLM Reasoning with Graphs Synthetic Benchmark Generation Implicit Reasoning in Language Models LLMs for Graph Learning

Ask PDF

Aug 18, 2026

ClosureBench: A Constructive Benchmark for Compositional Graph Reasoning

Large language models fail on multi-step compositional reasoning, but measuring that failure is hard, because new models are trained on the benchmarks used to evaluate them. A fixed test set becomes a memorisation check soon after release. Constructive benchmarks avoid this by generating instances on demand. We introduce ClosureBench, a constructive benchmark for graph-relational logical reasoning. Each task is built from explicit primitives (reachability, degree, set operations, connectivity, aggregation), and its reference answer is computed by executing code that implements that logic exactly. Ground truth is therefore verified, and the supply of fresh instances is unlimited. The benchmark spans 26 task categories at three compositional levels, with three independent difficulty axes: graph size, edge density, and query depth. We evaluate models from 1.5B open weights to frontier systems (o3, GPT-4.1, Gemini 2.5, Claude Sonnet 4). Accuracy falls as graph size and query depth increase, and the two axes interact. The difficulty does not lie in the surface form, since it persists when the graph is given as a JSON edge list or an adjacency matrix rather than prose, nor in the reasoning rule, which models state correctly. It lies in carrying that rule out over the graph across many steps. A 4B model fine-tuned to emit verified programs instead of answers stays nearly flat across compositional levels, while every frontier model degrades. o3 falls from 96% on atomic queries to 82% on the most compositional; the 4B model holds at 93% at a fraction of the token cost. The program offloads multi-step execution to a runtime, and the model's remaining errors are almost entirely misread edges. Constructive generation also supports a direct memorisation check, comparing accuracy on seen and fresh instances.

Stefano Goria

AIM Research Lab

LLM Reasoning with Graphs Language Model Reasoning Evaluation Graph Reasoning LLM Reasoning

Ask PDF

Jul 13, 2026

ResearchQA: Benchmarking Citation-Grounded Question-Answering on Scientific Papers

Large language models are increasingly used to assist scientific reading, but existing evaluation methods often fail to detect whether answers are supported by verifiable citations. We introduce ResearchQA, a benchmark of 6,211 single-paper question-answer pairs from 494 open-access papers spanning eight domains and four question types: lookup, comprehension, multi-hop, and adversarial. ResearchQA is designed for citation-grounded evaluation: it permits multiple valid supporting passages for a claim and rewards grounded refusal when the source paper does not support an answer. We evaluate eight leading closed- and open-weight models in a citation-grounded chat-with-paper setting using a deterministic citation matcher and an LLM-based rubric evaluator. Citation-based metrics separate systems more clearly than LLM-evaluator scores: section coverage and citation accuracy vary substantially across models, while evaluator scores remain tightly compressed. We further find that open-weight models approach the best closed-model citation accuracy while achieving 3 to 6 times lower per-example latency. We release the benchmark, evaluation harness, and evaluator prompt.

Saba Imran, Debanjum Singh Solanky

Khoj Inc.

LLM Evaluation Citation Verification Scientific QA Knowledge-Intensive QA Evidence-Grounded QA Factual QA

Ask PDF

Abstract

Long-Context Reasoning in Language Models

Explore similar work

Unified Multi-Dimensional Benchmark for Complex Graph Reasoning in Large Language Models

ClosureBench: A Constructive Benchmark for Compositional Graph Reasoning

ResearchQA: Benchmarking Citation-Grounded Question-Answering on Scientific Papers