Graphwalks BFS <128k
1 phaseActive
OpenAI's long-context multi-hop reasoning benchmark: models perform breadth-first search over a graph edge list within a 128k-token context window.
Overview
Graphwalks BFS <128k
Quick answer: Graphwalks BFS <128k is an OpenAI long-context reasoning benchmark that gives a model a graph encoded as a plain-text edge list and asks it to perform a breadth-first search (BFS) — returning the exact set of nodes reachable at a given depth — within a context window under 128,000 tokens, directly testing multi-hop structured reasoning over long text rather than simple retrieval.
At a Glance
What it tests: Whether a model can track and correctly traverse graph structure (which nodes connect to which) purely from a long, unstructured text encoding of the graph, without any external tool or code execution.
Why it matters: Long-context "needle in a haystack" retrieval tests only whether a model can find a single fact; Graphwalks instead requires multi-hop reasoning across the entire encoded structure, a much closer proxy for real long-context tasks like tracing dependencies through a large codebase or document set.
Known limitations: Grading requires an exact-match style precision/recall over a returned node list with strict output formatting, so models that reason correctly but format their final answer incorrectly can be penalized as if they failed the reasoning task itself.
What Graphwalks BFS <128k Measures
Each Graphwalks example presents a graph as a list of directed edges (e.g., abcd -> uvwx) embedded in a long text prompt, followed by an instruction to perform either a breadth-first search (BFS) from a given starting node to a specified depth, or to find the parents of a given node. The <128k variant specifically constrains the encoded graph and prompt to fit within a 128,000-token context window, isolating "moderate" long-context multi-hop reasoning from the even harder 256k–1M token variants of the same task family.
Because the model must return the exact set of correct node IDs with no partial credit for a "close enough" answer, the task cleanly separates models that can genuinely track graph connectivity across a long context from models that produce plausible-sounding but structurally incorrect answers. OpenAI released Graphwalks as a companion evaluation alongside the GPT-4.1 model family's long-context improvements.
Benchmark Specifications
| Field | Value |
|---|---|
| Task category | Reasoning / long-context multi-hop graph traversal |
| Metric | F1 score (precision + recall) over the returned node set |
| Number of tasks | 1,150 total examples (BFS and parents problem types combined) |
| Saturation | Medium — performance degrades as graph size approaches the 128k-token limit |
| Created by | OpenAI |
| Reference | OpenAI GPT-4.1 announcement |
| Dataset | openai/graphwalks |
How Graphwalks BFS <128k Is Scored
A model's final-answer node list is parsed from a required Final Answer: [...] format and compared against the ground-truth node set: recall is the overlap divided by the number of golden nodes, precision is the overlap divided by the number of nodes the model returned, and F1 is the harmonic mean of the two. Malformed or missing Final Answer: lines are treated as an empty (fully incorrect) response.
State-of-the-Art Results
See the OpenAI GPT-4.1 announcement for the original per-model BFS and parents F1 results across context-length buckets.
Graphwalks BFS <128k on Benchgen
No Benchgen results yet — [be the first to run Graphwalks BFS <128k](/benchmarks/openai/graphwalks-bfs-128k).
Graphwalks BFS <128k vs Other Benchmarks
| Benchmark | What it tests | Tasks | Saturation |
|---|---|---|---|
| Graphwalks BFS <128k | Long-context graph traversal (BFS), <128k tokens | 1,150 | medium |
| FRAMES | Multi-hop retrieval-augmented reasoning | — | low |
| RepoBench | Repository-level code completion | — | medium |
Graphwalks is distinguished from typical long-context needle-in-a-haystack tests and from RAG-style multi-hop benchmarks like FRAMES by requiring exact structural graph traversal purely from in-context text, with no retrieval or external tool assistance permitted.
Run Graphwalks BFS <128k on Your Model
Benchgen lets teams evaluate their own model's long-context multi-hop reasoning ability using Graphwalks' BFS task, tracking F1 score as context length approaches the 128k-token boundary.