A graph compiler called Tiga ran a billion-edge message-passing workload on a 16 GB consumer GPU by paging graph rows from NVMe storage through host memory instead of keeping the full relation on the device. The forward pass completed in a median 414.25 seconds, with a 10.27 GiB native GPU memory peak.
Message passing is the operation at the center of many graph neural networks. Each destination gathers features from related source nodes, transforms or weights those messages, and reduces them into an output. Frameworks can express that pattern in compact code, but a general implementation may first build a large edge list or materialize one message for every edge. Runtime and memory then grow with the intermediate representation as well as the graph itself.
Tiga keeps three choices explicit in its intermediate representation: how a relation is generated, how messages are reduced, and where graph data is stored. Its compiler can fuse relation construction with reduction when the neighborhood rule is generated from data, while static graphs can use compressed sparse row storage. The same program can therefore select dense tensor operations, fused CUDA kernels or paged sparse execution without rewriting the model around one backend.
Generated neighborhoods avoid large intermediates
The researchers first tested two workloads that construct neighborhoods at runtime. A dynamic-radius graph connects points within a distance threshold. At the largest reported size, Tiga took 1.84 milliseconds, versus 80.24 milliseconds for PyTorch Geometric and 1,870.09 milliseconds for a pure PyTorch implementation. Peak framework-tracked GPU allocation was 23.14 MiB for Tiga, 400.22 MiB for PyTorch Geometric and 355.01 MiB for PyTorch.
An exact k-nearest-neighbor workload showed a narrower but still material gain. At 131,072 points, Tiga took 172.37 milliseconds, compared with 393.21 milliseconds for PyTorch Geometric and 1,908.43 milliseconds for PyTorch. Its tracked allocation was 13.50 MiB, versus 121.13 and 285.00 MiB. Across the six measured sizes, Tiga was 2.28 to 12.06 times faster than the PyTorch Geometric path.
These measurements used FP32 forward passes on an RTX 5070 Ti with 16 GiB of memory. The primary benchmark host was shared and its GPU clocks were not locked. Reported timings exclude the first compilation and cache-filling run. The speedups describe these generated-relation kernels; they do not establish that brute-force neighbor search is preferable to a spatial index. Tiga's exact k-nearest-neighbor implementation still performs quadratic candidate-distance work.
Paging extends capacity, but storage becomes the bottleneck
For the capacity test, the team generated a static relation with one billion edges and stored its compressed rows and source indices on NVMe. Tiga mapped that data into host memory, staged bounded row ranges, and copied each chunk to the GPU for reduction. The relation occupied 15.37 GiB on disk. The authors estimated that holding the topology, output and one minimal edge-sized buffer on the GPU would require at least 18.86 GiB, rising to 22.82 GiB for a common source-index and message arrangement.
Nine measured trials produced a median forward time of 414.25 seconds, with a range of 411.36 to 415.61 seconds. Maximum native GPU allocation was 10.27 GiB and forward-process resident memory was 8.83 GiB. The verification step checked all two billion output scalars, rather than sampling a subset.
The run proves capacity more clearly than speed. An instrumented trace attributed only 1.60 seconds to CUDA kernels. Host-side copying, indexing and staging consumed most of the elapsed time. The paper therefore identifies asynchronous prefetching, pinned buffers and overlap between transfer and computation as necessary next steps, rather than presenting the current paged path as a fast out-of-core engine.
The evaluation also stops short of billion-edge training. Tiga supports automatic differentiation on several paths and checks selected gradients against explicit references, but the billion-edge experiment is forward-only. Some backward routes fall back to less specialized code, and a wide-feature case in the paper was slower than PyTorch Geometric.
Sources
- Paper record and abstract, submitted September 21, 2026
- Full paper with compiler design, benchmark conditions and limitations
- Tiga compiler source code
- Benchmark scripts and measurement artifacts
- Lead image: Figure 4 from the paper, “Performance and memory summary,” published under the paper's CC BY 4.0 license.