# Boolean Matrix Logic Programming on the GPU

arXiv: https://arxiv.org/abs/2408.10369 · HTML: https://mlsanity.com/paper/2408.10369/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 47 references that are in the map.
- First posted on arXiv 19 Aug 2024.

## Builds on (most cited first, 12 of 12)

- [Learning Explanatory Rules from Noisy Data](https://mlsanity.com/paper/1711.04574/) (2017)
- [End-to-End Differentiable Proving](https://mlsanity.com/paper/1705.11040/) (2017)
- [Clingo = ASP + Control: Preliminary Report](https://mlsanity.com/paper/1405.3694/) (2014)
- [Inductive logic programming at 30](https://mlsanity.com/paper/2102.10556/) (2021)
- [Abductive Knowledge Induction From Raw Data](https://mlsanity.com/paper/2010.03514/) (2020)
- [Logical reduction of metarules](https://mlsanity.com/paper/1907.10952/) (2019)
- [Towards a Formal Distributional Semantics: Simulating Logical Calculi with Tensors](https://mlsanity.com/paper/1304.5823/) (2013)
- [Search-Based Regular Expression Inference on a GPU](https://mlsanity.com/paper/2305.18575/) (2023)
- [Modular Materialisation of Datalog Programs](https://mlsanity.com/paper/1811.02304/) (2018)
- [Embedding Tarskian Semantics in Vector Spaces](https://mlsanity.com/paper/1703.03193/) (2017)
- [Optimizing Datalog for the GPU](https://mlsanity.com/paper/2311.02206/) (2023)
- [Boolean matrix logic programming for active learning of gene functions in genome-scale metabolic network models](https://mlsanity.com/paper/2405.06724/) (2024)

## Built on by (most cited first, 1 of 1)

- [Adaptive Data-Knowledge Alignment in Genetic Perturbation Prediction](https://mlsanity.com/paper/2510.00512/) (2025)

## Abstract (arXiv)

Traditional logic programming relies on symbolic computation on the CPU, which can limit performance for large-scale inference tasks. Recent advances in GPU hardware enable high-throughput matrix operations, motivating a shift toward parallel logic inference. Boolean Matrix Logic Programming (BMLP) introduces a novel approach to datalog query evaluation using Boolean matrix algebra, well-suited to GPU acceleration. Building on this paradigm, we present two GPU-accelerated BMLP algorithms for bottom-up inference over linear dyadic recursive datalog programs. We further extend the BMLP theoretical framework to support general linear recursion with binary predicates. Empirical evaluations on reachability queries in large directed graphs and the Freebase 15K dataset show that our methods achieve 1-4 orders of magnitude speed up over state-of-the-art systems. These results demonstrate that Boolean matrix-based reasoning can significantly advance the scalability and efficiency of logic programming on modern hardware. Source code is available on https://github.com/lun-ai/BMLP.git.