# From Probabilistic Programming to Complexity-based Programming

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 19 references that are in the map.
- First posted on arXiv 28 Jul 2023.

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

- [Multi-shot ASP solving with clingo](https://mlsanity.com/paper/1705.09811/) (2017)
- [DeepStochLog: Neural Stochastic Logic Programming](https://mlsanity.com/paper/2106.12574/) (2021)
- [Bayesian Synthesis of Probabilistic Programs for Automatic Data Modeling](https://mlsanity.com/paper/1907.06249/) (2019)

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

- [Exploring Structures of Inferential Mechanisms through Simplistic Digital Circuits](https://mlsanity.com/paper/2510.22883/) (2025)

## Abstract (arXiv)

The paper presents the main characteristics and a preliminary implementation of a novel computational framework named CompLog. Inspired by probabilistic programming systems like ProbLog, CompLog builds upon the inferential mechanisms proposed by Simplicity Theory, relying on the computation of two Kolmogorov complexities (here implemented as min-path searches via ASP programs) rather than probabilistic inference. The proposed system enables users to compute ex-post and ex-ante measures of unexpectedness of a certain situation, mapping respectively to posterior and prior subjective probabilities. The computation is based on the specification of world and mental models by means of causal and descriptive relations between predicates weighted by complexity. The paper illustrates a few examples of application: generating relevant descriptions, and providing alternative approaches to disjunction and to negation.