Counterfactual Regret Minimization (CFR) is the algorithm behind the poker AIs that famously beat top human pros. It works by walking through a giant tree of possible game states — sometimes billions of them — and repeatedly nudging a strategy toward "less regret" at every decision point. It's one of the most important algorithms in imperfect-information game theory.

Here's the awkward part: despite living in the era of GPU-everything, CFR has stubbornly run faster on CPUs than on GPUs. That's a strange outlier. Deep learning, physics sims, graphics — all of them love GPUs. So why not CFR?

The authors identify the culprit: overhead, not math. A CFR iteration is millions of tiny operations — gather this, scatter that, add these — all touching different parts of the game tree in specific orders. On a GPU, each of these little operations finishes in microseconds. But launching a GPU operation from Python or a generic framework also takes microseconds. When your work is that granular, you spend more time telling the GPU what to do than actually doing it. The GPU sits idle while the CPU catches up.

Their fix has two parts:

• Compile the game to static dataflow. For a fixed game (say, a specific poker variant), the tree structure never changes between iterations — only the numbers flowing through it do. So they trace the whole computation once, ahead of time, into a fixed graph of GPU operations. No more general-purpose "tree interface" being interpreted on every step.
• CUDA Graph replay. CUDA Graphs let you record a sequence of GPU operations and then replay the entire sequence with a single launch command. Instead of paying the launch tax millions of times per iteration, you pay it once. The GPU just chews through the pre-baked plan at full speed.

The payoff is right in the title: 80x faster than prior GPU implementations, and finally faster than the tuned CPU code that had been winning all along.

The broader lesson is worth chewing on. GPUs aren't magically fast — they're fast at bulk work. Any workload with lots of small, dependent steps runs into the same wall CFR did. Compiling the workload into a static plan and replaying it as one unit is becoming a standard trick, and this paper is a nice demonstration of it rescuing an algorithm the GPU world had basically given up on.