Lobster: A GPU-Accelerated Framework for Neurosymbolic Programming

Neurosymbolic programs pair a neural network that perceives messy data with a symbolic logic program that reasons over it, and they train end-to-end — but existing frameworks run the neural half on the GPU and the logic half on the CPU, an uneasy split where the slow CPU reasoning becomes the bottleneck; this paper (Penn and Johns Hopkins — Paul Biberstein, Ziyang Li, Joseph Devietti, Mayur Naik) builds Lobster, which runs the whole thing on the GPU by compiling the logic language Datalog down to a new restricted intermediate language, APM, that is expressive enough for discrete, probabilistic, and differentiable reasoning yet shaped to fit the GPU's lockstep threads and coalesced memory, reaching 3.9 times average and over 100 times peak speedups over the state-of-the-art Scallop.

The argument in one glance

Problem

Pairing a neural net with a logic program is powerful, but half of it runs slow

Deep learning is great at messy, high-dimensional perception — seeing objects in an image, parsing text — while classical algorithms are great at clear-cut rules and structured data — sorting, shortest paths. Many real problems need both, and neurosymbolic programming gets them by splitting the work: a neural network handles perception and a symbolic program handles the reasoning, connected so gradients flow through the logic back into the network, training the whole thing end to end. This buys data efficiency, interpretability, and generalizability that pure deep learning lacks, which matters for safety-critical uses like security and healthcare. But there is a structural flaw in how the current frameworks are built. The neural half runs on the GPU, fast and scalable, while the symbolic half runs on the CPU, slow. The reasoning side, which has to track probabilities on every fact and keep extra bookkeeping so the computation stays differentiable, becomes the bottleneck, and the elegant idea is throttled by where its two halves live.
What people did

Keep the neural component on the GPU and the symbolic component on the CPU

Existing frameworks like DeepProbLog and Scallop write the symbolic program in Datalog, a declarative logic language, and run it through a differentiable Datalog engine on the CPU, while the neural network runs on the GPU. Data is handed back and forth between the two devices each training step, each doing what it is conventionally good at.
Why it fell short

Symbolic reasoning does not fit the GPU, and the CPU cannot keep up

The reason the symbolic half stays on the CPU is that logic programming looks nothing like the regular, dense arithmetic GPUs love. Datalog computes over relations whose sizes change as rules fire, with irregular control flow and pointer-chasing data structures — the opposite of what a GPU wants. GPUs run threads in lockstep, penalize memory allocation during execution, and are fastest when neighboring threads touch neighboring memory, none of which a naive relational engine respects. So the symbolic engine is stuck on the CPU, where it is slow, and the constant device-to-device data movement adds insult. As models and problems scale, this reasoning bottleneck makes many neurosymbolic tasks impractically slow or outright infeasible.
This paper's idea

Compile the logic to a restricted parallel machine and run everything on the GPU

Lobster runs the entire neurosymbolic computation, neural and symbolic, on the GPU. Its core move is to compile Datalog down to a new intermediate language called APM — an Abstract Parallel Machine — that is deliberately restricted to fit the GPU: it has no control flow (to avoid thread divergence), requires all memory to be allocated up front in fixed-size vector registers (to avoid runtime allocation), and stores relations column by column (so memory accesses coalesce). APM is still expressive enough to support discrete, probabilistic, and differentiable reasoning uniformly, because Lobster carries a library of provenance semirings — the tags attached to each fact — and picking a reasoning mode is just picking a semiring. New optimization passes exploit the extra abstraction. Across 9 applications spanning language, vision, program reasoning, bioinformatics, and planning, Lobster averages 3.9 times faster than Scallop and over 100 times at peak, scaling tasks that were previously infeasible.

Why this problem is worth solving

Neurosymbolic programming is compelling precisely because it fuses two complementary strengths, and that fusion is where its cost lives.

A neurosymbolic program decomposes a task between a neural network, which perceives noisy high-dimensional input, and a symbolic program, which reasons over structured facts. The symbolic side is written declaratively, typically in Datalog, a logic language where you state rules and the engine derives all their consequences — for example, given an edge relation, a rule computes the transitive closure to get a path relation. What makes the pairing trainable end to end is that the Datalog engine is differentiable: the neural network’s outputs enter the logic as facts tagged with probabilities (its confidences), the logic derives conclusions whose probabilities combine the inputs’, and gradients of a final loss can be back-propagated through the logic all the way into the network’s weights. That means the network learns which features matter without hand-engineering, guided by the symbolic program’s structure. The payoff over pure deep learning is real: better data efficiency (the logic supplies knowledge the network would otherwise have to learn from scratch), interpretability (the reasoning is explicit), and generalization. These properties are exactly what safety-critical domains need, which is why the paradigm is worth accelerating rather than abandoning. But the differentiable, probabilistic reasoning that gives these benefits is also computationally heavy, and that heaviness is what a good framework must tame.

The specific weight the symbolic side carries is the tagging that makes reasoning probabilistic and differentiable.

In discrete Datalog a fact is simply present or absent. Neurosymbolic reasoning enriches this: every fact carries a tag, and the tag records something extra the computation must propagate. For probabilistic reasoning the tag is a probability, and when the engine derives a conclusion multiple ways it must combine all the derivations’ probabilities correctly, which is expensive because the number of derivations can explode — so frameworks resort to approximate inference like keeping only the top few proofs. For differentiable reasoning the tag additionally carries the information needed to compute gradients, tracking each input’s contribution to each output, which multiplies the bookkeeping in both space and time. This tag propagation is not a side computation; it runs alongside every relational operation the logic performs, so it inflates the cost of the reasoning throughout. On a CPU, single-threaded and cache-bound, this heavy tagged computation over growing relations is slow, and it is the part of the neurosymbolic pipeline that does not benefit from the GPU the neural network already uses. Making the symbolic side fast therefore means making tagged relational computation run in parallel on the GPU, which is precisely what nothing had managed, because the shape of that computation fights the GPU at every turn.

What people did before, and where it broke

Symbolic engine on the CPU, neural network on the GPU (DeepProbLog, Scallop). Run the differentiable Datalog reasoning on the CPU and the network on the GPU, exchanging data each step. Where it broke. The CPU symbolic engine is slow at the heavy tagged, differentiable relational computation and does not scale, and shuttling data between the two devices adds overhead, so reasoning becomes the bottleneck.
Approximate probabilistic inference to cut the cost. Keep only the most likely few derivations (top-k proofs) rather than reasoning exactly. Where it broke. It helps, but only with limited scalability benefit; the underlying tagged computation is still done serially on the CPU, so large problems remain slow.
General GPU-accelerated Datalog engines. Use existing systems that run plain Datalog on GPUs. Where it broke. They handle discrete reasoning but not the probabilistic and differentiable tagged modes neurosymbolic learning needs, so they cannot back-propagate gradients or manage provenance, and are not usable for neurosymbolic training.
Hand-porting a relational engine to CUDA directly. Write GPU code for relational operators as-is. Where it broke. Datalog’s irregular control flow, dynamically-sized relations needing runtime allocation, and pointer-chasing structures clash with the GPU’s lockstep warps, dislike of in-flight allocation, and demand for coalesced memory, so a direct port runs poorly.
The gap. No framework ran both the neural and the symbolic halves of a neurosymbolic program on the GPU with a single engine that supports discrete, probabilistic, and differentiable reasoning — because doing so requires reshaping the logic computation into a form the GPU can execute massively in parallel without losing the expressiveness the reasoning modes need.

How Lobster works

Compiling differentiable Datalog through a restricted parallel machine onto the GPU

↓ →
new
↓ →
new
↓ →
new
↓ →
new
↓ →
new

The idea

Run the whole neurosymbolic program on one device by bringing the logic to the GPU. The framing insight is that the “uneasy marriage” of a GPU neural half and a CPU symbolic half is not a law of nature but an artifact of nobody having made logic reasoning run well on GPUs. If the symbolic engine could execute on the GPU, the bottleneck and the cross-device shuffling both vanish, and the reasoning scales with the same hardware the network already exploits. Lobster commits to this unification, becoming the first framework to run both halves on the GPU end to end, for discrete, probabilistic, and differentiable reasoning alike. The obstacle is that Datalog’s relational computation is irregular where the GPU demands regularity, so the work is to transform it into a parallel-friendly form rather than to accept it as CPU-bound. Taking a logic language shown to be effective for neurosymbolic work and making it run natively on massively parallel hardware, rather than treating symbolic reasoning as inherently sequential, is the same ambition the work on optimizing Datalog for the GPU covered elsewhere on this site pursues, insisting that declarative logic can be a GPU workload. Lobster’s distinctive step is to do it for the tagged, differentiable reasoning that neurosymbolic learning specifically needs, not just plain Datalog.

Interpose a restricted intermediate language shaped to the GPU’s three demands. The way Lobster makes irregular logic fit regular hardware is by compiling Datalog through a new intermediate language, APM, whose restrictions are chosen to answer exactly the properties that make GPUs fast. GPUs execute threads in lockstep warps, so divergent control flow wastes them — APM therefore has no control flow, keeping threads marching together. GPUs punish memory allocation during execution and pointer-chasing structures — APM is in static single-assignment form with every register explicitly sized up front, so all allocation is decided at compile time and no B-trees or tries appear. GPUs reach peak bandwidth only when neighboring threads read neighboring addresses — APM makes every register a vector and stores relations column by column, so the common per-column operations produce coalesced accesses. The genius is that these restrictions are simultaneously what makes APM compilable to fast GPU code and what keeps it expressive enough, via its operators, to still capture full relational reasoning. Designing an intermediate representation whose deliberate constraints line up with the target hardware’s execution model, so that being restricted is what makes it fast, is the same principle the GPU tensor-computation IR work covered elsewhere on this site is built on, shaping the IR around the machine rather than the source language. Lobster applies it to relational logic instead of tensor algebra.

Make reasoning modes a plug-in choice of tag algebra, so one engine serves all. Rather than build separate engines for discrete, probabilistic, and differentiable reasoning, Lobster observes that they differ only in what tag rides along with each fact and how tags combine — captured formally by a provenance semiring, an algebra saying how to merge tags when a fact is derived multiple ways and how to combine them across the steps of a derivation. Lobster carries a library of these semirings, including the differentiable versions that enable gradient flow, and executing in a given mode is simply selecting the corresponding semiring; APM’s operators propagate whatever tag the semiring defines alongside the relational data. This is what lets a single GPU engine support all three modes without special-casing, and it is what makes the whole thing differentiable, since the gradient-tracking semirings turn the symbolic reasoning into something a loss can be back-propagated through. Unifying multiple reasoning behaviors under one abstraction by making the semantics a swappable, differentiable component rather than hard-coded control is the same modular-and-differentiable stance the differentiable e-graph-extraction work covered elsewhere on this site takes, exposing a symbolic process to gradients through a clean algebraic interface. Lobster’s version turns the entire spectrum from crisp logic to gradient-carrying probability into a single parameter of the runtime.

Following a neurosymbolic training step through Lobster

Training an image-graph program end to end on the GPU

A trace, drawn from the paper's design, of how Lobster executes one differentiable neurosymbolic step entirely on the GPU.

Step 1 of 5

The neural network emits probability-tagged facts

On the GPU, the neural network processes an input (say, an image) and outputs facts for the symbolic program — for instance an edge relation where each edge tuple is tagged with the network's confidence probability. These tagged facts are the input to the reasoning, and they already live in GPU memory.

Because the network already runs on the GPU, no cross-device transfer is needed to hand its outputs to the reasoning.

Why it works

Running both halves on the GPU removes the bottleneck and the transfers. The CPU symbolic engine was slow and required shuttling data to and from the GPU → but Lobster executes the reasoning on the GPU beside the network → so the reasoning scales on the same hardware and no cross-device movement remains.
APM’s lack of control flow keeps warps from diverging. Irregular logic control flow wastes lockstep threads → but APM has no control flow, so operators run uniformly across facts → so threads in a warp stay converged and the SIMD execution is efficient.
Static, sized registers avoid the GPU’s allocation penalty. Allocating memory while GPU code runs, and pointer-chasing structures, are slow → but APM’s static single-assignment form pre-sizes every register at compile time → so no runtime allocation or pointer chasing stalls execution.
Columnar vector registers make accesses coalesce. Irregular relational layouts scatter memory accesses → but APM stores relations column by column in vector registers → so per-column operations read neighboring addresses and hit peak GPU bandwidth.
A semiring library gives all reasoning modes on one engine. Building separate engines per mode would be redundant and hard → but the reasoning mode is just a choice of provenance semiring propagated by shared operators → so discrete, probabilistic, and differentiable reasoning all run, differentiably, on the same GPU pipeline.

What it costs (trade-offs and scope)

APM’s restrictions constrain what the compiler can express. Forbidding control flow and requiring static, sized allocation is what makes APM fast, but it also means every Datalog program must be compiled into that straitjacket; programs or reasoning patterns that do not fit the fixed-size, control-flow-free model may be awkward to express or require conservative over-allocation.
It is a specialized framework, not a general logic engine. Lobster targets Datalog-based neurosymbolic programs with provenance-semiring reasoning; workloads outside this shape, or symbolic reasoning not expressible in this Datalog dialect, are outside its scope, and adopting it means writing the symbolic side in its language.
The speedup varies widely by application. The average is 3.9 times but the peak exceeds 100 times, so the benefit is highly application-dependent; some workloads see enormous gains while others see modest ones, depending on how much of the cost was symbolic and how well the computation parallelizes.
GPU memory bounds the reasoning. Pre-allocating fixed-size vector registers and keeping relations resident on the GPU means the reasoning is limited by GPU memory; very large relations that would grow unpredictably could strain the static-allocation model or exceed device memory.
Evidence is a benchmark suite against specific baselines. The results come from 9 applications compared against Scallop and other systems; the “previously infeasible” claim and the speedups are for this suite and these baselines, and behavior on other neurosymbolic programs, GPUs, or reasoning modes is inferred rather than exhaustively shown.

The evaluation

Executing a neurosymbolic program's reasoning

Property	Scallop (CPU symbolic)	GPU Datalog (discrete only)	Lobster
Where the symbolic reasoning runs
Supports probabilistic reasoning
Supports differentiable reasoning
Fits GPU execution model
Reported speedup over Scallop

A comparison drawn from the paper. Lobster is evaluated on 9 applications spanning natural language processing, image processing, program reasoning, bioinformatics, and planning against Scallop and other systems; the 3.9-times-average and over-100-times-peak figures are the paper's reported speedups over Scallop, the closest state-of-the-art framework.Underlined values explain themselves when clicked.

Where this stops working

What to keep in mind

The full paper text was available (the authors’ arXiv version, 2503.21937), so this account of the mechanism — neurosymbolic programming and differentiable Datalog, the uneasy split of GPU neural and CPU symbolic components, the cost of propagating probabilistic and differentiable provenance tags, the three GPU constraints (lockstep warps, allocation penalties, coalesced memory), the APM (Abstract Parallel Machine) intermediate language with no control flow, static single-assignment sized vector registers, and columnar relations, the library of provenance semirings for discrete, probabilistic, and differentiable modes, and the Rust-and-CUDA compiler and runtime — follows the paper’s own description. The headline numbers are the paper’s reported results: across 9 applications Lobster achieves a 3.9 times average speedup and over 100 times peak over Scallop, the closest state-of-the-art framework, supporting 7 provenance semirings and enabling previously infeasible tasks. Those figures are for a specific benchmark suite and baselines; per-application results vary widely, and behavior on other programs and hardware is inferred. Exact per-application numbers, the APM semantics and compilation, and the optimization passes should be read from the paper itself. Lobster is open source (github.com/P-bibs/Lobster).

Background

Why bridging neural and symbolic computing is hard hardware-wise

It is worth appreciating why this integration is genuinely difficult at the hardware level, beyond any one framework. Deep learning won the hardware lottery: its core operation is dense linear algebra, which is regular, predictable, and embarrassingly parallel, so GPUs — built for exactly that — accelerate it enormously. Symbolic computation is the opposite kind of workload. Logic and relational reasoning are irregular: the amount of work depends on the data, control flow branches on conditions, data structures grow and shrink, and memory is accessed in scattered, pointer-following patterns. This is the classic profile of computation that GPUs handle poorly, which is why symbolic engines have historically stayed on CPUs. Neurosymbolic programming forces these two opposite workloads into one training loop, and the friction is exactly at their seam: the fast, regular neural part on the GPU and the slow, irregular symbolic part elsewhere. Getting large speedups therefore requires the hard work of restructuring the irregular symbolic computation until it becomes regular enough for the parallel hardware, without losing its meaning. That challenge of coaxing irregular, data-dependent computation into a form that massively parallel hardware can execute efficiently is the same problem the fine-grained-parallelism graph-mining accelerator work covered elsewhere on this site confronts, wringing parallelism out of computation that does not obviously offer it. Lobster shows that for relational logic, a carefully restricted intermediate language is the key to making the irregular regular.

If you remember only three things

1. Neurosymbolic programs pair a neural network (perception over messy data) with a symbolic Datalog program (reasoning over structured facts), trained end to end by back-propagating gradients through a differentiable logic engine, which gives data efficiency, interpretability, and generalizability. But existing frameworks run the neural half on the GPU and the symbolic half on the CPU, so the reasoning — burdened by propagating probabilistic and gradient-tracking provenance tags on every fact — becomes the bottleneck, and its irregular relational computation resists the GPU's lockstep warps, allocation penalties, and coalesced-memory preference.
2. Lobster is the first framework to run both halves on the GPU end to end. It compiles Datalog to a new intermediate language, APM (Abstract Parallel Machine), whose restrictions match the GPU: no control flow (avoiding thread divergence), static single-assignment form with explicitly sized vector registers (avoiding runtime allocation and pointer chasing), and columnar relation storage (making accesses coalesce). APM stays expressive by carrying a library of provenance semirings, so discrete, probabilistic, and differentiable reasoning all run on one engine by simply selecting the right semiring, and new optimization passes exploit the restricted form.
3. Across 9 applications spanning language, vision, program reasoning, bioinformatics, and planning, Lobster averages 3.9 times faster than the state-of-the-art Scallop and exceeds 100 times at peak, running existing Datalog neurosymbolic programs unmodified and scaling tasks that were previously infeasible. Its restrictions constrain what can be expressed, it targets Datalog-based provenance-semiring reasoning specifically, the speedup is highly application-dependent, and the reasoning is bounded by GPU memory; the compiler and runtime are written in Rust and CUDA and released open source.

Check yourself

Check your understanding

1. What is the "uneasy marriage" in existing neurosymbolic frameworks that Lobster addresses?
2. Why does symbolic (Datalog) reasoning not naturally fit the GPU?
3. What is APM and how does its design let Datalog run efficiently on the GPU?
4. How does Lobster support discrete, probabilistic, and differentiable reasoning on one engine, and what are its results?

Sources

The paper is “Lobster: A GPU-Accelerated Framework for Neurosymbolic Programming” by Paul Biberstein, Joseph Devietti, and Mayur Naik (University of Pennsylvania) and Ziyang Li (Johns Hopkins University), published at ASPLOS 2026, DOI 10.1145/3760250.3762232. It is licensed CC BY.

This explainer is based on the paper’s full text, obtained from the authors’ arXiv preprint (arXiv:2503.21937). The account of the mechanism — neurosymbolic programming as a decomposition between a neural network and a symbolic Datalog program trained end to end via a differentiable logic engine; the benefits (data efficiency, interpretability, generalizability) and the uneasy marriage of a GPU neural component with a CPU symbolic component; the cost of propagating probabilistic and differentiable provenance tags; the three GPU constraints (lockstep SIMD warps, the penalty of runtime allocation and pointer-chasing structures, and coalesced memory access); Lobster’s compilation of Datalog through a relational-algebra form to the APM (Abstract Parallel Machine) intermediate language with no control flow, static single-assignment sized vector registers, and columnar relation storage; the library of provenance semirings enabling discrete, probabilistic, and differentiable reasoning by selection; and the Rust-and-CUDA compiler and runtime — follows the paper’s own description. The reported results cited here are the paper’s own: across 9 applications spanning natural language processing, image processing, program reasoning, bioinformatics, and planning, Lobster achieves a 3.9 times average speedup and over 100 times at peak over Scallop, the closest state-of-the-art system, supports 7 provenance semirings, runs existing Datalog neurosymbolic programs without modification, and enables previously infeasible tasks. Lobster is available at github.com/P-bibs/Lobster. Exact per-application numbers, the APM semantics and compilation, and the optimization passes should be read from the paper itself.