Scallop tags every fact with a provenance-semiring value, letting gradients flow through hand-written Datalog rules while only the neural predicates that feed them are trained.
lane: substrate · Scallop — arXiv:2304.04812 (Li, Huang, Naik, UPenn, cs.PL, submitted 2023-04-10); ancestor: DeepProbLog — arXiv:1805.10872 (Manhaeve, Dumancic, Kimmig, Demeester, De Raedt, NeurIPS 2018)
Gives. Hand-written Datalog gets gradients through provenance semirings; only the neural predicates feeding it train.
Needs. A human who writes the rules.
Breaks. Exact inference scales badly; where rules are unknown, end-to-end models win.
Every other differentiable-program approach on this hub lets an optimizer touch the program's structure in some indirect way, for example fitting constants in an LLM-proposed skeleton or growing a library. Scallop draws the line in the opposite place. The symbolic program, Datalog rules with recursion, stratified negation, and aggregation, is entirely hand-written by a human programmer and never touched by gradient descent or search. Only the neural components that produce the input facts' probability tags are trained. The mechanism that makes this work, provenance semirings, is itself swappable as a hyperparameter. The same rules can run under a plain-probability semiring, a max-min semiring, or a weighted-model-counting semiring, trading exactness for speed differently each time.
diff-max-min-prob (dmmp) runs in O(1) per operation, and its derivative has at most one nonzero entry. diff-add-mult-prob (damp) uses addition and multiplication with clamping; its saturation check always returns true, which the paper says makes it weaker for complex recursive programs. diff-top-k-proofs (dtkp) represents tags as DNF boolean formulas capped at k proofs, resolved by weighted model counting, a #P-complete operation and the dominant runtime cost; k=3 is usually adequate and often gives the best accuracy.DeepProbLog (ancestor, arXiv:1805.10872): extends ProbLog with "neural predicates," meaning predicates whose probability comes from a neural network call, and adapts ProbLog's existing probabilistic inference and learning machinery so the whole system trains end-to-end from examples. The paper's own framing calls it "the first" system integrating general-purpose neural networks with expressive probabilistic-logical reasoning trainable end-to-end, per WebSearch synthesis of the NeurIPS abstract. Exact benchmark numbers were not found in any page opened this session — UNVERIFIED beyond the mechanism-level claim.
The symbolic rule set is 100% discrete and fixed by the programmer at write time. Scallop never searches over which rules exist. Gradients flow only through the numeric tags, dual numbers under a differentiable provenance, that enter the program as neural-network outputs. These tags propagate through the fixed Datalog structure via ⊕, ⊗, and ⊖. The only thing crossing from symbolic back to neural is the gradient of final tag values with respect to the input tags, a precise backward pass, not a scalar score or natural-language residual. Choice of provenance, dmmp versus damp versus dtkp-k, is itself a hyperparameter the paper compares like any other, not something learned inside the loop.
Scallop wins hardest when exact probabilistic reasoning actually matters and data is scarce. On PacMan-Maze, a Scallop neurosymbolic agent reaches 99.4% test success after 50 training episodes, versus an end-to-end Deep Q-Learning agent's 84.9% after 50,000 episodes (Table 3/Section 6, full text), a roughly 1,000x reduction in training episodes for higher accuracy. The cost is runtime that depends sharply on the chosen provenance and scales badly for dtkp with recursion depth. On MNIST-R's sum4 task, dmmp, damp, and dtkp-3 run in 34-77 seconds per epoch, while dtkp-10 takes 4,329 seconds and DeepProbLog, exact weighted model counting with no approximation, times out entirely. On sum3, DeepProbLog needs 30,898 seconds per epoch versus Scallop's 34-1,430 seconds depending on provenance (Table 4). The paper states DeepProbLog needs roughly 40 days for 4K sum4 samples. Weighted model counting is explicitly #P-complete and is the dominant cost driver for the most accurate provenance, dtkp. More proofs, meaning a higher k, buy accuracy at worst-case exponential runtime cost. Scallop's own benchmark shows DeepProbLog's unmitigated exact inference simply failing to finish on the harder tasks in the same table.
From Section 6 (arxiv.org/html/2304.04812, full text):
1. Exact inference is the scaling wall, inside the paper's own benchmark: DeepProbLog, exact weighted model counting, times out on MNIST-R sum4 and needs roughly 40 days projected for 4K sum4 samples (Table 4). Classical exact probabilistic-logic inference fails to scale past small arithmetic compositions. 2. Provenance choice is its own hyperparameter search: the paper likens choosing a provenance to hyperparameter tuning, since no single setting is both fast and exact. dtkp-10, the most accurate provenance, also times out on CLEVR. 3. Hand-written rules are a named cost: Section 6.6 attributes most errors to an underpowered neural component or insufficient supervision. The stated remedies, more data, retuning the provenance, and integrity constraints, all require programmer intervention. Rules do not self-correct. 4. 2025 assurance benchmark (arXiv:2502.08932): tests Scallop-style systems against fully neural baselines on robustness, calibration, and interpretability. Advantages appear specifically "where arithmetic operations are defined and... the input space is high-dimensional." Claimed data-efficiency gains "typically" held only on class-imbalanced problems; gains are "not across the board." Interpretability can reveal shortcut solutions that carry greater adversarial vulnerability despite matched performance. 5. 2023 knowledge-graph neurosymbolic survey (WebSearch, not opened): the survey warns that a symbolic module can raise complexity rather than lower it, and that gains may come from model stacking rather than the symbolic component — UNVERIFIED at primary-source level. 6. REASON (arXiv:2601.20784, 2026) cites both DeepProbLog and Scallop, and by title appears to attack the same exact-inference scaling bottleneck. Its PDF returned unreadable binary to WebFetch — findings UNVERIFIED beyond its existence and apparent topic.
DeepProbLog, in 2018, established the template Scallop scales up: keep an existing symbolic or logical inference engine, ProbLog, built on Prolog, and bolt on "neural predicates" whose truth value comes from a network call, training the whole system end-to-end. Scallop's contribution is to swap ProbLog's exact probabilistic inference for a family of provenance semirings, trading exactness for tractable approximate gradients. It also targets a Datalog-style relational language, with recursion, aggregation, and stratified negation, rather than Prolog directly, aimed explicitly at being usable from ordinary machine-learning pipelines. The paper names DeepProbLog as the predecessor it aims to scale past. Its own MNIST-R runtime table is the direct quantitative argument for why: Scallop's approximate provenances finish in seconds on tasks where DeepProbLog's exact inference times out. In forward lineage, a 2025 assurance benchmark (arXiv:2502.08932) and a 2026 acceleration paper (arXiv:2601.20784, unopened) both treat Scallop as the reference neurosymbolic system to critique or extend, suggesting it has become the field's default example rather than DeepProbLog.
Verified: WebFetch on arxiv.org/abs/2304.04812 (metadata/abstract) and arxiv.org/html/2304.04812 (full text, two reads: chars 0-100000 for mechanism/limitations, chars 100000-162194 for Section 6 evaluation tables); WebSearch for DeepProbLog bibliographic/mechanism facts (NeurIPS/arXiv abstract mirrors — full text not opened, numeric results not found); WebFetch on arxiv.org/abs/2502.08932 (2025 assurance-benchmark critique, abstract-level); WebFetch attempt on arxiv.org/pdf/2601.20784 (REASON, 2026) blocked — PDF returned as unreadable compressed binary, not opened. · code: https://github.com/scallop-lang/scallop (named in secondary sources); https://github.com/ml-kuleuven/deepproblog (DeepProbLog, per SOTAVerified listing)