GraphWalks tests a model’s ability to find and combine information across very long contexts. A graph is a set of nodes, some of which are connected via directed edges. Each task lists the directed edges, which sufficiently define the graph. The task then tests a model’s ability to either find parents (nodes that have a directed edge ending at the queried node) or search at a given depth (traverse the chain of edges to a specific level; known as breadth-first search, or BFS). While the tasks are challenging without tool access, they lend themselves to easy programmatic verification. The tasks were all well constructed and an independent solver reproduced the stated answer for all 1,150 tasks.
Interpretation
A high score is evidence that a model can understand graph relationships over a long input and retrieve the queried nodes. The BFS tasks require more long-context processing, with intermediate steps, than the parents tasks, which primarily reward long-context retrieval. The score is computed as follows:1
n_overlap = len(sampled_set & truth_set)
recall = n_overlap / n_golden if n_golden > 0 else 0
precision = n_overlap / n_sampled if n_sampled > 0 else 0
f1 = 2 * (recall * precision) / (recall + precision) if recall + precision > 0 else 0The F1 score ranges from 0 to 1. It rewards finding the right nodes (recall) and avoiding the extra wrong nodes (precision). The score should not be interpreted as the fraction of tasks solved correctly.
The data was synthetically created, so a high score may not translate to real-world capabilities that require additional capabilities and reasoning, such as large-codebase work. However, as models’ context windows increase, it will be easy to increase task size to test their capability and programmatically verify solutions.
Task Analysis
The tasks each use a generated directed graph of hexadecimal hashes and a standard-form prompt. There are two task types:
- BFS: breadth-first search from a given starting node to a specified depth
- Parents: return all nodes with a directed edge into the specified node
Each prompt contains a 4-shot example (2 of each type) followed by the graph2 and the operation to be performed:
The graph has the following edges:
uvwx -> alke
abcd -> uvwx
abcd -> efgh
efgh -> uvwxExample 1:
Operation:
Perform a BFS from node abcd with depth 1.
Final Answer: [uvwx, efgh]Example 33:
Operation:
Find the parents of node uvwx.
Final Answer: [abcd, efgh]
The inputs range in size from 2,709 to 1,748,364 characters (median 110,284).
The graphs range in size from 44 to 69,867 edges and 9 to 69,867 unique nodes.
The output ranges in size from 0 to 6,943 nodes.
The depth of BFS assessed ranges from 1 to 39.
OpenAI reports 4 numbers:
- BFS <128k (this is the most commonly reported score)
- BFS >128k
- Parents <128k
- Parents >128k
where 128k represents the context-length cutoff between the two subsets of problems.4 The <128k subset consists of prompts at various doubling tiers of context-length. The >128k subset consists of 200 prompts at 256k tokens and 200 prompts at 1M tokens.
We built a Python verifier and found that all tasks had the correct answer key.
Elicitation and Scaffolding
Each task is a single turn: the model gets the task prompt with no system prompt and no tool access.5 Models are run with a 1M-token context input and up to 128k output tokens, with no compaction.
Limitations
- Temporal stability: Earlier versions contained 24 incorrect parent labels (where the root node was incorrectly included) and less explicit BFS wording.6 This update was documented in the changelog, but not given a version bump.
- Output limits: Long-context BFS tasks may require outputs exceeding model token output limits (e.g., GPT-4.1’s 32,768-token output limit). The <128k slice is not affected by this.
- Contamination: All prompts and solutions are public.
- Minor documentation issue: the data schema describes the prompt as a 3-shot example, but prompts are actually 4-shot with 2 examples of each type.
Rubric
1. Reviewability
| Level | Meaning | Status |
|---|---|---|
| Full | All tasks and scoring logic inspectable*, and harness/API settings used for each model (reasoning effort, token/time limits, tool access, system prompts) are fully disclosed | [proceed to 2] |
| Partial | A representative sample of tasks and scoring logic inspectable, with full harness/API settings disclosed | [proceed to 2] |
| Inadequate | Limited, biased, or no inspectable tasks or scoring logic, harness/API settings undisclosed | [stop → NEI] |
* Either publicly or privately to reviewers.
2. Scoring
This is the minimum standard required to be Verified; failing any of these items results in a Flawed verdict.
| Scoring | |
|---|---|
| Examples |
|
| Default threshold for Flawed | ≥20% of inspected sample† contains errors or there is an issue that corrupts grading at scale |
| Status | PassFlag [stop → Flawed]Not reviewed |
| Notes | — |
| Benchmark Consistency | |
|---|---|
| Examples |
|
| Default threshold for Flawed | Leaderboard has incomparable results from different versions |
| Status | PassFlag [stop → Flawed]Not reviewed |
| Notes | — |
| Elicitation | |
|---|---|
| Examples | Model elicitation is extremely constraining and is not the focus of the benchmark:
|
| Default threshold for Flawed | Substantially reduced performance compared to reasonable alternatives for the tasks |
| Status | PassFlag [stop → Flawed]Not reviewed |
| Notes | — |
| Bias in Evaluation Setup | |
|---|---|
| Examples |
|
| Default threshold for Flawed | Material model-specific advantage found |
| Status | PassFlag [stop → Flawed]Not reviewed |
| Notes | — |
† For benchmarks with >50 available tasks, we will sample a random set of 50 (stratified by category, when present). If the observed error rate is 15–25%, we will expand the sample to 100. For benchmarks with ≤50 available tasks, all available tasks will be assessed.
3. Evaluation Quality
This is the standard we would like all benchmarks to meet, but it is not necessarily disqualifying to omit or fail these items.
| Question | Status | Notes |
|---|---|---|
| Elicitation and resource adequacy: Are the resources given to models (reasoning token/turn budget, tool access, etc.) sufficient for them to perform near their ceiling? | SufficientConstrainingUnreasonably constrainingUnknownNot reviewed | Long-context BFS tasks may require outputs exceeding model token output limits (e.g., GPT-4.1’s 32,768-token output limit). The <128k slice is not affected by this. |
| Scaffold fairness: What scaffold does the leaderboard report? | Shared common scaffoldMix of model-specific and common scaffoldsModel-specific scaffoldsNot reviewed | — |
| Is there evidence/risk of contamination? | As of Sep. 29, 2026: 100% of tasks public 100% of solutions publicNot reviewed | — |
| Has human completability been assessed? | All tasksRepresentative set of tasksPoor implementation (Unrepresentative set of tasks, unreasonable set of participants)Not establishedNot reviewed | — |
| Score range (if possible to estimate) | 0 floor, 1 ceilingNot reviewed | — |
| Statistical adequacy: how many runs/model (≥ 5 recommended for error bars) | — runs/modelUnknownNot reviewed | — |
| Construct Validity | Measures stated capabilitiesPartially measures stated capabilitiesDoes not measure stated capabilitiesNot reviewed | — |
Disclaimer
We attempted to reach out to the benchmark developer prior to launch, and if they write a response to this review we will link it here. If you’re the benchmark developer, please email us at reviews@epoch.ai with a link to your response if you would like us to include it here.
-
For submissions that were parseable and not the empty set. These edge cases are handled appropriately.
-
In the prompt example, the nodes are not hexadecimal.
-
Examples 2 and 4 omitted for brevity.
-
“graphwalks_128k_and_shorter.parquet” and “graphwalks_256k_to_1mil.parquet”.
-
Tool access is not allowed because it would change the construct tested from long-context processing to the ability to run a BFS/parents algorithm.
-
Old: “If asked for a breadth-first search (BFS), only return the nodes that are reachable at that depth, do not return the starting node.”
New: “If asked for a breadth-first search (BFS), only return the nodes that are both reachable and exactly at that depth (not nodes at intermediate depths), and do not return the starting node.”
About Benchmark Reviews
Epoch AI’s Benchmark Reviews are independent reviews of external AI benchmarks. Our documentation describes the rubric behind this verdict, how we choose which benchmarks to review, and answers frequently asked questions.