GPU-CFR: Compiling the Game So the CPU Beats the GPU, Then the GPU Beats Everything

Paper: 2609.11923 Authors: Boning Li, Longbo Huang Categories: cs.DC, cs.AI, cs.GT, cs.MS, cs.PL

The Gap

Counterfactual regret minimization is one of the few large numerical workloads that still runs faster on CPUs than on GPUs. That is a striking exception, and the paper explains why it exists: each iteration sweeps a game tree with up to billions of states in millions of small, interdependent gather and scatter steps issued through a generic tree interface.

The mechanism of the failure is a gap between kernel duration and dispatch cost. On a GPU every kernel finishes in microseconds, so kernel launches and framework dispatch dominate the run time — the arithmetic is finished before the machinery to start it has wound down. That is why prior GPU implementations have lost to optimized CPU code: the GPU is not slower at the computation, it is slower at orchestrating a workload made of millions of tiny dependent steps.

   CFR: A STRIKING EXCEPTION

   CFR is ONE OF THE FEW LARGE NUMERICAL WORKLOADS THAT STILL RUNS
   FASTER ON CPUs THAN ON GPUs
        |
        v
   WHY: each iteration sweeps a game tree with UP TO BILLIONS OF STATES
        in MILLIONS of SMALL, INTERDEPENDENT GATHER AND SCATTER STEPS
        issued through a GENERIC TREE INTERFACE
        |
        v
   [THE MECHANISM OF THE FAILURE: KERNEL DURATION vs DISPATCH COST]
     on a GPU, EVERY KERNEL FINISHES IN MICROSECONDS
     -> KERNEL LAUNCHES and FRAMEWORK DISPATCH DOMINATE THE RUN TIME
     -> the ARITHMETIC is finished before the MACHINERY TO START IT
        has wound down
        |
        v
   -> that is why PRIOR GPU IMPLEMENTATIONS HAVE LOST TO OPTIMIZED
      CPU CODE
      <- the GPU is not slower at the COMPUTATION
      <- it is slower at ORCHESTRATING a workload made of MILLIONS OF
         TINY DEPENDENT STEPS

The Increment

One sentence: Before this paper, GPU CFR lost to CPUs because dispatch overhead dominated; after it, compiling the game into static dataflow and replaying it as one CUDA graph beats every baseline, and the compiled form alone already beats the GPU baseline on CPUs.

Core Mechanism

The insight is a single observation with large consequences: for a fixed game, everything about a CFR iteration except the numerical values is known before the first iteration runs. Shapes, indices, edge structure, depth levels, buffer addresses — all fixed by the game, not by the solve. And CFR’s update rule does not change, so nothing about the schedule varies between iterations. That is the condition under which compilation is possible at all.

So the game is compiled once into static dataflow: flat edge and information-set arrays, precomputed indices, and depth-level batched passes fix the entire operation sequence, and only solver state changes between iterations. The internal techniques each reduce a specific source of overhead — static chance folding, depth-level execution blocks, and a dual-lane reach buffer — and together they cut the number of framework operations by up to 18.1×. So the first gain is a genuine algorithmic-systems reduction, not merely a harness change: fewer operations means less to dispatch.

And then the payoff that only static shapes allow: because shapes, indices and buffer addresses never change, CUDA Graph Replay records the iteration once and replays it with a single graph launch. This is the step that directly attacks the diagnosis. If dispatch dominates, collapsing millions of launches into one is the right remedy, and it is only available because the compiled representation made the schedule invariant.

The results separate the two contributions, which is the most instructive part of the reporting. On one A100, across an eight-game suite spanning card games, dice games and board games:

• 29.8–80.4× faster than the fastest prior GPU CFR on the same accelerator.
• 14–258× faster than LiteEFG, one of the fastest open-source CPU implementations, on the four largest games.
• And the attribution: the compiled representation carries most of that margin — on eight CPU threads with no accelerator it is already 2.2–51.1× faster than the GPU baseline.

That last figure is the one to dwell on. A CPU run beating a GPU baseline by up to 51× means the win is mostly not from using the GPU better — it is from doing far less orchestration work. The GPU then multiplies a gain that the compilation had already produced. Reporting the CPU-only number alongside the GPU result is what lets a reader see that decomposition.

Two further verifications are worth noting. On the CPU, the optimized path reproduces the reference iterates bitwise — so the compilation is semantics-preserving, not an approximation, which matters because CFR’s guarantees depend on the update rule. And tree construction and graph capture pay for themselves within the first solve, so the compilation cost is amortised within a single use rather than requiring many solves to justify.

The summary makes the scope explicit: GPU-CFR beats every CPU and GPU baseline on the mid-to-large games of the suite without changing the update rule. Both clauses matter — “mid-to-large” bounds where the win applies, and “without changing the update rule” bounds what was done to get it.

   THE INSIGHT: ONE OBSERVATION WITH LARGE CONSEQUENCES
     FOR A FIXED GAME, EVERYTHING ABOUT A CFR ITERATION EXCEPT THE
     NUMERICAL VALUES IS KNOWN BEFORE THE FIRST ITERATION RUNS
       <- SHAPES, INDICES, EDGE STRUCTURE, DEPTH LEVELS, BUFFER
          ADDRESSES: all fixed by the GAME, not by the SOLVE
       AND CFR's UPDATE RULE DOES NOT CHANGE
         -> nothing about the SCHEDULE varies between iterations
       <- that is the condition under which COMPILATION IS POSSIBLE
          AT ALL

   THE GAME IS COMPILED ONCE INTO STATIC DATAFLOW
     FLAT edge and information-set arrays
     PRECOMPUTED indices
     DEPTH-LEVEL BATCHED PASSES
       -> these FIX THE ENTIRE OPERATION SEQUENCE
     and ONLY SOLVER STATE CHANGES between iterations
     INTERNAL TECHNIQUES each reduce a SPECIFIC SOURCE OF OVERHEAD
       static chance folding | depth-level execution blocks |
       dual-lane reach buffer
       -> together they CUT THE NUMBER OF FRAMEWORK OPERATIONS BY UP TO
          18.1x
       <- the first gain is a GENUINE ALGORITHMIC-SYSTEMS REDUCTION,
          not merely a HARNESS CHANGE: FEWER OPERATIONS MEANS LESS TO
          DISPATCH

   THEN THE PAYOFF ONLY STATIC SHAPES ALLOW
     because shapes, indices and buffer addresses NEVER CHANGE,
     CUDA GRAPH REPLAY RECORDS THE ITERATION ONCE AND REPLAYS IT WITH A
     SINGLE GRAPH LAUNCH
       <- directly attacks the DIAGNOSIS: if DISPATCH DOMINATES,
          collapsing MILLIONS OF LAUNCHES INTO ONE is the right remedy
       <- ONLY available because the compiled representation made the
          SCHEDULE INVARIANT

   THE RESULTS SEPARATE THE TWO CONTRIBUTIONS -- the most instructive
   part of the reporting
     one A100, EIGHT-GAME SUITE (card, dice, board games)
       29.8-80.4x faster than the FASTEST PRIOR GPU CFR on the SAME
         ACCELERATOR
       14-258x faster than LiteEFG (a fastest open-source CPU
         implementation) ON THE FOUR LARGEST GAMES
     AND THE ATTRIBUTION:
       THE COMPILED REPRESENTATION CARRIES MOST OF THAT MARGIN -- on
       EIGHT CPU THREADS WITH NO ACCELERATOR it is ALREADY 2.2-51.1x
       FASTER THAN THE GPU BASELINE
       <- a CPU run beating a GPU baseline by up to 51x means the win is
          mostly NOT from USING THE GPU BETTER
       <- it is from DOING FAR LESS ORCHESTRATION WORK
       -> the GPU then MULTIPLIES a gain the COMPILATION had ALREADY
          produced
       <- reporting the CPU-ONLY number alongside the GPU result is what
          lets a reader SEE THAT DECOMPOSITION

   TWO FURTHER VERIFICATIONS WORTH NOTING
     on the CPU, the optimized path REPRODUCES THE REFERENCE ITERATES
     BITWISE
       <- the compilation is SEMANTICS-PRESERVING, not an approximation
       <- matters because CFR's GUARANTEES depend on the UPDATE RULE
     TREE CONSTRUCTION AND GRAPH CAPTURE PAY FOR THEMSELVES WITHIN THE
     FIRST SOLVE
       -> the COMPILATION COST is amortised within a SINGLE USE

   SCOPE MADE EXPLICIT
     beats every CPU and GPU baseline ON THE MID-TO-LARGE GAMES of the
     suite WITHOUT CHANGING THE UPDATE RULE
       <- "MID-TO-LARGE" bounds WHERE the win applies
       <- "WITHOUT CHANGING THE UPDATE RULE" bounds WHAT WAS DONE to
          get it

Think of it as a workshop where the tools are fine but fetching them takes longer than using them. Each operation takes microseconds; walking to the shelf takes longer. The fix is not a faster tool — it is arranging the workshop so that the whole sequence of operations is laid out in advance and can be executed without any fetching. Two details of the paper’s version map cleanly. First, the layout work is itself valuable independent of the fancy machinery: eight threads with no accelerator already beat the GPU version, which is the equivalent of saying the reorganisation alone paid for the upgrade. Second, the resulting sequence is identical every time, so you can record the entire session once and replay it — and that recording is only possible because nothing about the layout changes between runs.

Key Concepts

• Dispatch-bound rather than compute-bound: microsecond kernels mean launch overhead dominates. It relocates the problem from arithmetic to orchestration, which is what makes a compiler the right tool.
• Compilation enabled by schedule invariance: everything but the values is fixed before the first iteration. Without that invariance, static dataflow could not represent the iteration.
• An 18.1× reduction in framework operations: static chance folding, depth-level blocks and a dual-lane reach buffer. It is a real reduction in work, which is why it matters independently of the GPU.
• CUDA Graph Replay as the direct remedy: one launch instead of millions, available only because shapes and addresses never change.
• The CPU-only attribution: 2.2–51.1× over the GPU baseline on eight threads. It decomposes the win and shows the compilation, not the accelerator, carries the margin.
• Bitwise reproduction of reference iterates: semantics preserved exactly, which matters because the method’s guarantees depend on the update rule.

Framework Shift

Before (GPU CFR loses to CPU):
  millions of small interdependent steps through a generic interface
  -> microsecond kernels, dispatch dominates
  -> GPU slower at orchestration than CPU, despite faster arithmetic
  -> prior GPU implementations lost to optimized CPU code

After (compile the game, replay the iteration):
  everything but the values is known before iteration one
  -> static dataflow: flat arrays, precomputed indices, batched passes
  -> up to 18.1x fewer framework operations
  -> one recorded CUDA graph instead of millions of launches
  -> 29.8-80.4x over prior GPU CFR; 14-258x over fast CPU code
  -> and 2.2-51.1x over the GPU baseline on eight CPU threads alone

From trying to make a GPU faster at a workload it is bad at orchestrating, to compiling the workload so there is far less to orchestrate, the core shift is that the bottleneck was never the arithmetic — and the compiled representation, not the accelerator, carries most of the gain.

Expert Assessment

Problem choice: Excellent, and the framing is unusually well aimed. “One of the few workloads still faster on CPU” is a precise invitation to find out why, and the answer — dispatch overhead, not compute — immediately implies a compiler rather than a kernel. That is a diagnosis leading directly to the right class of solution.

Method maturity: The observation that everything but the values is fixed before the first iteration is the kind of insight that looks obvious once stated and had apparently not been exploited this way. The internal techniques each target a named overhead, and the 18.1× operation reduction is a real reduction rather than a harness trick. Using CUDA Graph Replay is the natural consequence of schedule invariance, not a separate optimisation. Most importantly, the reporting separates the two contributions by including the CPU-only number, which is the measurement that tells a reader where the gain actually comes from.

Experimental integrity: The comparisons are appropriately scoped: against the fastest prior GPU implementation on the same accelerator, against a fast open-source CPU implementation, and with the win bounded to mid-to-large games. Bitwise reproduction of reference iterates is the check that matters for a method with convergence guarantees, and it is reported on the CPU path where bitwise comparison is meaningful. The amortisation claim — construction and capture paid for within the first solve — removes the obvious objection about compilation cost. The limitation is that the win is conditional on games large enough to make the per-iteration orchestration significant, so small games, where the overhead ratio is less extreme, are outside the reported benefit.

Writing quality: The abstract states the diagnosis, the insight, the mechanism and the separated results in order, which makes the argument followable without the tables. Because the CPU-only figure is the most informative number in the paper, giving it prominence rather than burying it in a comparison table is the right editorial choice.

Verdict: strong accept — it diagnoses why GPUs lose at this workload, applies the compiler-shaped fix the diagnosis implies, and reports the results in a way that shows the compiled representation rather than the accelerator carries the gain.

Takeaways

• Distinguish compute-bound from dispatch-bound. When kernels finish in microseconds, the fix is fewer operations rather than faster ones.
• Look for schedule invariance before optimising. If nothing but the state changes between iterations, the iteration itself can be compiled.
• Report the decomposed contribution. The CPU-only figure here shows the compilation, not the GPU, produced most of the speedup.
• Verify semantics, not just speed. Bitwise agreement with reference iterates is what makes a compiled fast path usable for an algorithm with guarantees.