Multi-primitive in-memory computing for Monte Carlo tree search

Tergel Molom-Ochir, Benjamin F. Morris Iii, Yintao He, Archit Gajjar, Giacomo Pedretti, Hai Helen Li, Yiran Chen, Jim Ignowski, Aishwarya NatarajanarXiv 2026 · arXiv

TL;DR

This paper introduces "phase-to-primitive decomposition," a hardware-software co-design methodology that allows irregular, multi-phase algorithms to run entirely on-chip using in-memory computing (IMC). By mapping the distinct phases of Monte Carlo Tree Search (MCTS) to specialized memory primitives (CAM, SRAM, RRAM, and combinational logic), the authors created an accelerator that consumes just ~60 mW. This architecture delivers up to a 2,059× energy efficiency boost over an NVIDIA H100 GPU, enabling data-center-grade AI planning on power-constrained edge devices.

What Problem Does This Paper Address?

Monte Carlo Tree Search (MCTS) is a powerful decision-making algorithm responsible for milestones in AI like AlphaGo, as well as practical applications in robotic path planning and molecular optimization. However, MCTS is notoriously power-hungry, typically drawing 55–300 W on conventional processors. This high power consumption confines MCTS to data centers and keeps it out of reach for milliwatt-scale embedded platforms like autonomous drones, surgical robots, or wearable medical devices.

The root cause is structural: MCTS relies on irregular tree traversals, heavy control-flow branching, and frequent statistical updates. These operations parallelize poorly on standard CPUs and GPUs, leading to massive energy waste from data movement. While in-memory computing (IMC) drastically reduces data movement by co-locating compute and storage, it has traditionally only been compatible with highly regular, uniform workloads like deep learning matrix multiplications. This paper addresses the fundamental challenge of adapting IMC to irregular, multi-phase algorithms.

Methods

The authors propose a four-step framework called phase-to-primitive decomposition: profile the algorithm's phases, match each phase to a native IMC primitive, reformulate incompatible phases, and compose them into an end-to-end on-chip pipeline.

Fig. 1: Phase-to-primitive decomposition. a, Monte Carlo tree search (MCTS) iterates through four phases (selection, expansion, rollout, backpropagation) over a search tree. b, Phase-to-primitive mapping: each phase corresponds to a co-located in- memory computing (IMC) primitive (content-addressable memory (CAM), combina- tional logic, resistive random-access memory (RRAM) crossbar, static random-access memory (SRAM)). c, The IMC workload landscape, with prior IMC accelerators occupying the homogeneous quadrants and IMC-MCTS in the phase-heterogeneous, multi-primitive quadrant.

They applied this methodology to create IMC-MCTS, mapping the four core phases of MCTS to four distinct hardware primitives on a single substrate:

  1. Selection: Restructured from a pointer-chasing hash-table traversal into a parallel associative lookup using a Content-Addressable Memory (CAM) array, enabling $O(1)$ single-cycle selection.
  2. Expansion: Handled by a Game Logic Unit (GLU) built from combinational logic, evaluating all board cells simultaneously to generate legal moves in a single cycle.
  3. Rollout: Replaced variable-length random simulations with a fixed-latency neural network evaluator mapped onto an analog Resistive RAM (RRAM) crossbar, eliminating weight-fetching overhead.
  4. Backpropagation: Executed via in-place read-modify-write operations directly inside an on-chip SRAM bank using saturating counters, keeping all search data on-chip.

A Ternary CAM (TCAM)-based Finite State Machine (FSM) orchestrates the entire four-stage pipeline to maintain deterministic timing and prevent pipeline stalls.

Fig. 2: IMC-MCTS architecture and resource scaling. a, Chip view: multiple tiles connected through a top-level control block and a host Peripheral Component Interconnect Express (PCIe) interface. b, Tile view: cores share a level-2 (L2) SRAM through a tile controller. c, Core schematic: one core implements the four-stage MCTS pipeline (Selection, Expansion, Rollout, Backpropagation) under TCAM-based finite- state-machine control. d, Per-component area scaling from 2×2 to 19×19 Go. e, Per- component power distribution during sustained 5,000-iteration-per-move search at 9×9, summing to 60.26 mW. Per-component values are in Supplementary Table S3.

Datasets

The primary benchmark used to evaluate decision quality and hardware scaling was the game of Go (evaluated on board sizes ranging from $2\times2$ up to $19\times19$, with $9\times9$ as the primary baseline).

To demonstrate that the architecture is application-agnostic, the authors also evaluated the exact same hardware substrate across eight grid-based decision applications spanning four AI domains:

  • Strategy Games: Connect Four, Othello, Hex, and Go.
  • Navigation: FrozenLake and MiniGrid.
  • Scientific Optimization: Hydrophobic-polar (HP) protein folding.
  • Puzzles: Minesweeper.

Key Insights and Ideas

  • Heterogeneous IMC Substrates: Traditional IMC architectures rely on a single primitive (usually an analog crossbar for matrix math). This paper demonstrates that co-locating multiple, qualitatively distinct primitives (analog RRAM alongside digital CAM and SRAM) yields massive efficiency gains for complex algorithms.
  • Load-Bearing Co-Dependence: The hardware primitives reinforce one another. For example, the CAM's single-cycle lookup latency prevents pipeline stalls that would otherwise leave the analog RRAM crossbar sitting idle.
  • Algorithmic Noise Absorption: Analog RRAM crossbars are prone to hardware non-idealities like conductance noise. Crucially, the authors realized that MCTS's inherent statistical averaging over hundreds of search iterations naturally absorbs this analog noise, meaning device-level imperfections do not degrade overall playing strength.

Key Results

  • Exceptional Energy Efficiency: At a 22-nm process node, the IMC-MCTS chip consumes only ~60 mW during a sustained 5,000-iteration search on $9\times9$ Go. This achieves a 96× energy efficiency gain over a CPU baseline and a 65× to 2,059× gain over an NVIDIA H100 GPU (depending on the GPU's batch size).
  • Uncompromised Decision Quality: In a 1,050-game tournament, the IMC-MCTS hardware achieved a European Go Federation (EGF) rating of ~1727 (3 kyu), performing on par with established open-source software engines (Michi-C and Pachi-UCT) at matched compute.
  • Substrate Reusability: Without any architectural modifications or rewriting RTL, the chip successfully executed all eight cross-domain tasks simply by reprogramming the RRAM crossbar weights.

Limitations and Future Work

  • Grid-World Constraints: The current accelerator specifically targets grid-representable state spaces. Adapting the architecture to non-grid spaces (such as continuous robotic control or large-graph routing) will require encoding modifications.
  • Silicon Validation: While the hardware was modeled using parameters from fabricated RRAM arrays and characterized via standard tools (Synopsys Design Compiler, CACTI, SST), full end-to-end physical silicon validation is still noted as the next step.
  • Scaling for Professional Play: The current neural evaluator is lightweight (trained on a 2,000-position budget). Scaling up to professional-tier play (dan level) will require expanding the crossbar capacity to accommodate larger, deeper neural networks.

Summary updated

Abstract

Monte Carlo tree search (MCTS) enables artificial intelligence (AI) decision-making, but requires 55-300 W on conventional processors, limiting edge deployment. In-memory computing (IMC) is energy-efficient on regular workloads but has been considered incompatible with irregular multi-phase algorithms. We introduce phase-to-primitive decomposition, which reformulates each algorithmic phase as a hardware-native IMC primitive. Applied to MCTS, selection, expansion, rollout and backpropagation map to content-addressable memory, combinational logic, a resistive random-access memory (RRAM) crossbar and static random-access memory, keeping search on chip. At 22 nm with fabricated RRAM-array parameters, IMC-MCTS consumes ~60 mW for 9x9 Go, achieving 96x energy efficiency over a central processing unit (CPU) and 65x-2,059x over an H100 graphics processing unit (GPU). It reaches a European Go Federation rating within sample-size uncertainty of open-source Go engines (Pachi-UCT and Michi-C). The same substrate runs eight applications across four AI domains.
BibTeX
@misc{molomochir2026multi,
  author = {Tergel Molom-Ochir and Benjamin F. Morris III and Yintao He and Archit Gajjar and Giacomo Pedretti and Hai Helen Li and Yiran Chen and Jim Ignowski and Aishwarya Natarajan},
  title = {{Multi-primitive in-memory computing for Monte Carlo tree search}},
  year = {2026},
  eprint = {2607.22869},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2607.22869},
}
Figure