blog›fast or slow
Predicting TPU runtimes on 10,000-node graphs
On this page
XLA has to settle two choices before emitting TPU code: the physical layout of every tensor and the tile size of every fused kernel. Neither changes the math, yet picking badly can nearly double the runtime, and the only exact cost model is to compile and benchmark every option. Google's TpuGraphs dataset (NeurIPS 2023) turns that into a machine-learning benchmark, pairing programs up to 44k nodes with up to 100k timed configurations each, and Kaggle ran the Fast or Slow? competition on top of it.
I entered with Iafoss as team DI, and we finished 10th out of 616. Honestly, I walked away early after testing the public baseline and deciding the metric looked like a lottery. We came back right near the deadline, changed where the configuration enters the network, and built a graph transformer around it.
resnet50.4x4.fp16 from layout:xla:random, 5,673 nodes and 9,099 edges. Nodes are placed by longest-path depth, 1,289 levels, folded into fourteen rows, and only edges within a row are drawn. The 166 large squares are the configurable nodes. Colour is the 18-number layout vector of the node: the eight most common vectors each have a colour and the rarer ones are grey. The dataset has 5,704 measured configurations of this graph. The figure steps through forty of them, spread evenly from the fastest to the slowest. Hover or tap a large square to see its tensor, or click a bar to pick a layout.
The problem
Each sample pairs an XLA graph with a configuration and a measured TPU v3 runtime. Nodes represent tensor operations (140 features plus an opcode), and edges are tensors. The configurations come in two flavours: a layout sets the dimension order of tensors at every configurable node in a whole program (18 integers per node), while a tile sets the block shape for one small fused kernel (24 numbers for the entire subgraph).
| collection | graphs | median nodes | timed runs | runs per graph |
|---|---|---|---|---|
| layout:xla:random | 77 | 12,062 | 1,067,552 | 7,560 |
| layout:xla:default | 69 | 10,449 | 1,114,640 | 9,912 |
| layout:nlp:random | 227 | 3,296 | 14,832,169 | 67,000 |
| layout:nlp:default | 218 | 3,296 | 14,173,408 | 67,832 |
| tile:xla | 6,661 | 36 | 12,339,092 | 804 |
Training and validation graphs, counted from the statistics files published with the dataset. The last column is the median over graphs. The test graphs are not in those files.
XLA graphs cover a mix of vision and language models, whereas the NLP collections come from BERT variants. Configurations in random were sampled by random search, while default comes from a genetic search seeded at the compiler's default choice. Because the split is by graph, every test program is unseen.
The goal is ranking configurations from fastest to slowest on each test graph. Layout sets are scored by per-graph Kendall's τ. Tile sets only look at your top-five picks: 2 − (best runtime among your top five) ⁄ (best runtime overall). Averaging across all five collections gives 0.2 maximum per collection.
First, the public baseline
I started with the simplest thing on offer: the dataset class from the organisers' graph segment training (GST) baseline. It standardises node features, chops each large graph into ~1,000-node segments, and samples a handful of configurations per step on one random segment (I used 10 configurations per graph).
In that setup, the configuration goes straight into the input: write the 18 layout numbers onto each configurable node, pad everywhere else with zeros, and run the entire encoder separately for every configuration. That is early fusion, and on graphs this big it blows up fast. The largest graph has 43,615 nodes (1,158 configurable) and 1,960 timed configurations; evaluating all of them at once means pushing 85 million node vectors through every single layer. No wonder the baseline cuts graphs into segments and samples 10 configurations at a time.
The trouble is that 10 configurations give just 45 pairs to learn ordering from, when 1,960 configurations contain 1.9 million pairs, and Kendall's τ counts every last one. I also peeked at a pretrained Graphormer in that same notebook, only to bounce off quadratic attention: fine for 30-atom molecules, hopeless for a 10,000-op program.
Between that bottleneck and the realisation that each layout collection is scored across just a handful of test graphs, the competition felt close to a coin flip. We packed up, moved back to another competition, and left the repo sitting.
What the targets look like
To see why that metric felt so shaky, look at all seven validation graphs of layout:xla:random, with every measured layout sorted fastest to slowest:
On ResNet-50, the slowest layout takes nearly twice as long (1.96×) as the fastest. On the 3D U-Net, the entire spread from best to worst is 2.4%, with all 481 configurations sitting in flat plateaus. Because Kendall's τ weights every graph equally and treats every pair the same, a plateau of near-ties counts just as much as a clean 2× curve, and on just 7 XLA (or 20 NLP) validation graphs, a few flat graphs swing the average wildly.
Coming back: where the configuration goes in
We jumped back in close to the deadline with one clear idea: stop training on 10 configurations at a time. Notice the asymmetry in the data: the graph is huge and stays fixed, while the configurations are tiny and number in the thousands. So the whole design boils down to where you join them.
The textbook alternative to early fusion is late fusion:
Run the graph encoder once, pool all nodes into one summary vector, and concatenate the configuration afterwards. That is dirt cheap, except a layout assigns 18 numbers to specific nodes, and after global pooling the head gets a blurry graph summary alongside a flattened layout vector and has to guess which settings belonged to which node.
Instead, we met right in the middle: after the encoder, before pooling.
The heavy encoder runs once per graph and keeps every node vector intact. We slice out only the L′ configurable nodes, pair each of the C configurations with them node by node, run a small MLP on those C · L′ tiny vectors, and pool at the end. On the ResNet-50 graph at the top, L′ is 166 out of 5,673 nodes (2.9%), so encoding cost barely depends on C at all.
The trade-off is that non-configurable nodes never see the layout, and configurable nodes don't see each other's settings until pooling. What it bought us was fitting up to 1,000 configurations of a 10,000-node graph into a single step on one GPU, using the whole graph with zero segments.
Tiles first
Fused kernels only have a few dozen nodes, so ordinary attention works without breaking a sweat.
Eight residual graph blocks build local node representations, followed by two self-attention blocks for global mixing. Configurations then enter via four cross-attention blocks, querying the node vectors so the kernel itself still runs once. That model hit 0.97 on the tile metric in under a minute of training, scoring 0.197 public and 0.196 private on the leaderboard (0.198 / 0.196 across folds) out of a maximum 0.2. With tiles basically solved, we spent the rest of our time on layouts.
A transformer for ten thousand nodes
For layouts we needed an encoder that scales to ten thousand nodes. Plain message passing only travels a few hops across graphs that run more than a thousand levels deep, while full attention over 104 nodes runs out of memory (as I saw with Graphormer). So our starting point was linear attention.
- usual
- out = softmax(Q KT) V
- linear
- out = Q′ (K′T V) ⁄ Q′ (K′T 1)
- with
- Q′ = elu(Q) + 1, K′ = elu(K) + 1
with one row per node. K′T V is dh × dh per head, so time and memory are O(L · dh2) and not O(L2 · dh). The denominator comes from the same product by padding V with a column of ones.
Following EfficientViT, linear attention multiplies keys and values first, avoiding any L × L matrix while still letting every node talk to every other node. We swapped EfficientViT's ReLU kernel for ELU + 1 (much stabler in practice) and kept those inner products in float32 even during mixed-precision runs.
Global attention on its own has no idea which operations are wired to which, and we had no positional encoding. So we slipped a message-passing layer into the MLP slot of every block: global step first, local step second, x ← x + LA(LN(x)) and x ← x + GNN(GELU(LN(x))). My first version used SAGE, after which we tried APPNP, GAT and GPRGNN (directed and bidirectional edges, with APPNP slightly ahead). Other runs swapped the encoder for a 4- or 6-layer DIFFormer or replaced the residual sum with a gated unit.
We skipped linear attention in the tile model: kernels come batched with padding, and masking out padded tokens is awkward when the attention matrix is never explicitly formed.
Model details
- Node input. Instead of standardising features that include tensor sizes up to 106, we took log(x + 3) followed by a linear layer, then added an opcode embedding and a learned flag for configurable nodes. Extracting 29 extra node features with a modified version of the organisers' extractor made no difference.
- Encoder. 256 wide, up to 12 blocks, 8 heads, dropout 0.1.
- Layout input. Each of the 18 small integers per node gets a learned 4-wide vector, joining 72 numbers onto the node's 256.
- Head. Two MLP layers per configuration-node pair, mean + GeM pooling across configurable nodes, two more MLP layers, one scalar score.
- Speed. Seconds per epoch on tiles, minutes on XLA layouts, and 30 to 60 minutes on NLP layouts at up to 1,000 configurations per step.
A loss over a thousand configurations
Putting a thousand configurations in one step let us train with a listwise loss. ListMLE computes the negative log-likelihood of the true runtime ordering under a Plackett–Luce model:
- loss
- − Σi log ( exp(sπ(i)) ⁄ Σj ≥ i exp(sπ(j)) )
where π sorts the configurations of one graph by measured runtime and s are the predicted scores. Ties are broken at random at every step.
Because ListMLE depends only on rank order, we never had to normalise raw runtimes across programs whose speeds differ by orders of magnitude.
Initially, data loading choked the pipeline: each layout file packs up to 100,000 × L′ × 18 values for one graph, and reading the whole file just to sample 1,000 configurations was painfully slow. I converted the dataset once upfront: keep the graphs in one small in-memory file (a few gigabytes total), and shard each graph's configurations into chunks of 1,000 stored as int8. After that, disk I/O vanished as a bottleneck.
XLA and NLP graphs hit opposite hardware limits, so we trained them separately. Large XLA graphs hit memory limits (256 configurations per step on a 24 GB GPU, 1,000 on 48 GB); smaller NLP graphs easily fit 1,000 configurations in 24 GB, only to take up to an hour per epoch. Everything trained with AdamW (lr 5e-4, weight decay 1e-2, cosine schedule) for 5 epochs on tiles and 16 on layouts, using weight averaging and gradient accumulation on some runs.
Comparing model variants
Once training ran smoothly, we ran into a measurement problem when trying to tune anything. Almost every architectural tweak moved validation by less than simply rerunning the exact same model with a different random seed. Because τ averages across just 7 XLA or 20 NLP graphs, graph-to-graph variance dwarfs model-to-model differences; that's why this post has no ablation table.
We set up an 11-fold split (official validation plus 10 folds of the training graphs) to sharpen the signal, but with one NLP fold taking 8 to 16 hours and the deadline looming, we ran only a handful of folds per setup and folded them straight into the ensemble instead of picking winners.
If you can't reliably tell models apart, the safest play is averaging as many diverse runs as you have time to train, hoping an ensemble survives the jump from public to private leaderboard.
Results
Here are three of our final submissions from the writeup:
| submission | what is in it | public | private |
|---|---|---|---|
| Wide blend | 10 to 20 configurations each for XLA and NLP | 0.712 | 0.696 |
| Best on public | 2 APPNP models for XLA, 2 DIFFormer for NLP | 0.721 | 0.703 |
| Best on private | APPNP with gated units in place of the residual sum | 0.706 | 0.715 |
The wide blend that was supposed to be our "safe" insurance policy finished dead last on the private leaderboard (0.696). Our selected submission, four models that topped the public board at 0.721, landed 10th at 0.70318. Meanwhile, the submission we left unselected (trailing in last place on public at 0.706, identical except for swapping residual addition for a gated unit) jumped to 0.715 private. That would have tied 2nd place (0.71466), behind 1st at 0.72608 (while 9th through 11th sat packed at 0.70323, 0.70318 and 0.69927).
Our worst public submission was our best private one, by a margin wider than any ablation we ever measured. We knew the metric was a lottery going in, and the final table proved it.
What we didn't settle
- Which graph layer. APPNP edged out SAGE, GAT and GPRGNN, though well inside seed noise.
- Graph transformer or DIFFormer. Both went into our final picks, and we never settled which works better here.
- Gated units. Replacing residual sums gave our 0.715 private submission, yet one unselected run isn't proof and validation didn't flag it.
- The 11-fold scheme. Finished too late to resolve any of the three questions above.
Team and thanks
We competed as a two-person team, Iafoss (Maxim Shugaev) and me; he also authored our writeup, where most of these numbers come from.
The competition was organised by Mangpo Phothilimthana, Sami Abu-El-Haija and Bryan Perozzi at Google with Kaggle. Thank you for putting together such an unusual ML problem and releasing the entire dataset publicly; every graph and runtime plotted on this page comes straight from it.
Links
- Phothilimthana et al. TpuGraphs: A Performance Prediction Dataset on Large Tensor Computational Graphs. NeurIPS 2023, Datasets and Benchmarks track.
- Google - Fast or Slow? Predict AI Model Runtime. Kaggle competition, 2023.
- DrHB, Iafoss. 10th place solution: Fast or Slow with Graph Transformers. Kaggle writeup, November 2023.
- DrHB/tpuoptimize. My code for the layout model: data conversion, linear attention, the graph transformer block and the ListMLE loss.
- google-research-datasets/tpu_graphs. The dataset, its statistics and the baseline models.
- Kaufman et al. A Learned Performance Model for Tensor Processing Units. MLSys 2021.
- Cai et al. EfficientViT: Multi-Scale Linear Attention for High-Resolution Dense Prediction. ICCV 2023. The linear attention in the layout model.
- Wu et al. DIFFormer: Scalable (Graph) Transformers Induced by Energy Constrained Diffusion. ICLR 2023.