Graph500 BFS: exceed 410,266.553 GTEPS on a validated run
Difficulty 18: a record is set by whoever runs a well-engineered BFS on a larger GPU fleet, as eos-dfw did with 8,192 H100s, so access to hardware matters more than new ideas; comparable to the GPU-kernel parity problems (24–30) but less algorithmic. Application value 22: indirect, through interconnect and graph-analytics system design. Leverage 6: nothing depends on the record.
The problem
Build a computer system that explores a giant graph faster than the current leader on the Graph500 list.
- 1Generate a huge random graph
- 2Explore from 64 start points
- 3Validate each answer
- 4Score edges traversed per second
What is measured. Graph500 ranks computers on how fast they explore a huge graph, a set of vertices joined by edges, rather than on arithmetic speed. The graph is generated by a fixed random recipe with vertices and on average 16 edges per vertex; at scale 41 that is about 2.2 trillion vertices and 35 trillion edges. The machine runs (BFS) from up to 64 random start vertices: visit the start, then all its neighbours, then all their unvisited neighbours, layer by layer, recording each vertex's parent. In Python a BFS is a queue and a loop of about ten lines; the difficulty here is that the graph is spread over thousands of processors.
Path to understanding
foundations → problemThe research entries this problem rests on, in the order to read them. Each links to its explainer.
- Start with
- Step 2
- Step 3
- Then
- Graph500 BFS: exceed 410,266.553 GTEPS on a validated runThe problem
State of the art
June 2026 BFS list: rank 1 eos-dfw (CoreWeave datacentre, Dallas; 8,192 H100 GPUs in just over 1,000 nodes according to NVIDIA; first listed in November 2025), scale 41, 410,266.553 GTEPS; rank 2 LineShine (National Supercomputing Center in Shenzhen), scale 43, 234,827.4293 GTEPS; rank 3 Fugaku (RIKEN R-CCS), scale 43, 204,068 GTEPS; rank 4 Wuhan Supercomputer, scale 41, 115,357.6 GTEPS; rank 5 Lyris (NVIDIA), scale 38, 91,930.1 GTEPS. The next list is due in November 2026. A per-GPU or per-watt comparison would separate algorithmic and software gains from machine size, but the list reports no common normalisation.
Realistic applications
Better BFS and SSSP at scale benefits graph analytics, network analysis and bioinformatics workloads that are memory- and communication-bound. The benchmark mainly measures interconnect and memory systems, so the practical value is in system design.
What counts as solved
A Graph500-conformant run, validated by the reference validator and accepted on the official list, with TEPS above 410,266.553 GTEPS, or a reproduction of a list entry by an independent party on the same hardware class.
How it gets verified
ReproductionA training run, experiment or computation rerun by someone else.
Benchmark: Graph500 BFS (Kernel 2) per the specification at graph500.org: Kronecker generator, edgefactor 16, up to 64 search keys, harmonic-mean TEPS, untimed validation of each parent array. Threshold: 410,266.553 GTEPS (eos-dfw, scale 41; November 2025 list, unchanged in June 2026). A claim must state scale, node count, interconnect and software (the reference code is graph500/graph500), include validator output for all keys, and be reproducible on the same machine class; the official list is the final authority.
Claims under verification
+ add a claimNo claimed results on the Verification board for this problem yet.
Where the work is
The work is system engineering: communication-efficient BFS on a large machine and access to the hardware.
Bottlenecks
ranked by votes- #1EngineeringInterconnect and memory bandwidth at scale
BFS is communication-bound; reaching a higher rate depends on network topology, message aggregation and memory access patterns on the target machine.
Community grades
Sign in to add your own grade.
Connected problems
No connections yet.
Progress
- Nov 1, 2025BFS record on the 31st listsource
eos-dfw reached 410,266.553 GTEPS at scale 41 with 8,192 H100 GPUs; month given as the list month.