GPU-CFR: 80x Faster Counterfactual Regret Minimization

Counterfactual regret minimization has a dirty secret: the algorithm that solved heads-up poker and underpins the entire imperfect-information game stack runs faster on CPUs. Every prior GPU implementation has lost. The reason is mundane and damning — a CFR iteration is millions of tiny, dependent gather/scatter ops through a dynamic tree interface, so each GPU kernel finishes in microseconds and the runtime dies in launch overhead and framework dispatch. A new compiler system (arXiv:2609.11923, Boning Li & Longbo Huang, Tsinghua) flips this: 29.8–80.4x faster than the best prior GPU CFR on one A100, and 14–258x faster than LiteEFG, one of the fastest open-source CPU solvers. Same update rule. Pure systems work.

The problem: GPUs choke on dynamic tree workloads

CFR is one of the last big numerical workloads where the GPU is the wrong machine. The iteration loop walks a game tree that can hold billions of states, and every step's memory access pattern depends on the tree structure, which today's frameworks discover at runtime through generic tree interfaces. On a CPU, that's fine — a single core chews through dependent scalar work. On a GPU, you pay a kernel launch and framework dispatch tax per operation, and the arithmetic never gets a chance to dominate. Prior GPU ports therefore ran slower than tuned CPU code, which is why serious poker solvers still run on silicon designed for spreadsheets.

The method: freeze everything except the numbers

The observation is almost embarrassingly simple, and that's the point: for a fixed game, everything about a CFR iteration except the numerical values is known before iteration zero. The compiler exploits it in three moves. First, it compiles the game once into static dataflow — flat edge and information-set arrays with precomputed indices, no runtime tree interface. Second, static chance folding, depth-level execution blocks, and a dual-lane reach buffer restructure the sweep into large batched passes, cutting framework operations by up to 18.1x. Third, since shapes, indices, and buffer addresses never change between iterations, the whole iteration is recorded once as a CUDA Graph and replayed with a single launch. Dispatch overhead doesn't shrink — it's deleted.

mindmap
  root((GPU-CFR))
    Compile once
      Flat edge + IS arrays
      Precomputed indices
      Static chance folding
    Restructure
      Depth-level batched passes
      Dual-lane reach buffer
      18.1x fewer framework ops
    Replay
      CUDA Graph capture
      One launch per iteration
    Receipts
      29.8–80.4x vs prior GPU
      14–258x vs LiteEFG CPU
      2.2–51.1x on CPU alone
      Bitwise identical iterates
            

The results: the compiler is the contribution, not the GPU

Across an eight-game suite (cards, dice, boards) on a single A100, GPU-CFR beats every CPU and GPU baseline on mid-to-large games. But the number that reframes the paper is this: the compiled representation alone, running on eight CPU threads with no accelerator, is already 2.2–51.1x faster than the prior GPU baseline. Most of the "GPU" win isn't the GPU — it's static compilation of the game structure. The A100 margin on top is the reward for getting out of the CPU's dependent-branch regime once the dispatch tax is gone. Two hygiene receipts close the loop: on CPU, the optimized path reproduces the reference solver's iterates bitwise (this is a reimplementation of the same fixed-point iteration, not an approximation), and one-time costs — tree construction, graph capture — pay for themselves within the first solve, so there's no amortization cliff for single-shot solving.

Limitations the paper doesn't dwell on

Read the fine print: the headline ranges come from the four largest games of an eight-game suite, and the authors themselves note the wins concentrate on mid-to-large games. Tiny trees don't fill an A100 — small games likely see modest or no benefit. Second, the speedup is for vanilla CFR's fixed update rule; the modern state of the art has moved to CFR+ and MCCFR variants, and the paper doesn't show these compile-time tricks extend to them — plausible, since they share the tree-sweep structure, but unproven. Third, the static-dataflow premise (structure known ahead of time) excludes exactly the research settings where GPU flexibility was doing quiet work: on-the-fly game abstraction, subgame decomposition that rebuilds trees mid-solve, and RL-in-the-loop setups where the "game" mutates. Recompiling per mutation may eat the margin. And there's no scaling study — one A100, no H100/MI300 numbers, so where this lands on newer hardware is open.

Why builders should care

The transferable lesson has nothing to do with poker: if your workload's structure is static and your tensors are small, a compiler that freezes the dataflow beats any amount of framework tuning. That's the same pattern showing up across 2026 — graph capture, pre-flattened indices, batched-by-depth execution — and it's directly applicable to agent infrastructure, tree-search rollouts, and any tree/graph-shaped numeric loop currently drowning in per-op dispatch. For the game-solving crowd specifically: imperfect-information solvers just got roughly two orders of magnitude cheaper on one GPU, which moves Nash-equilibrium-quality baselines for abstracted games from "overnight cluster job" toward "afternoon laptop-GPU job." And the CPU result is the sharper prod — before you buy accelerators, ask what your framework is doing that a compiler could delete. The bottleneck was never the math. It was the interface standing between the math and the machine.