CS Paper Radar

Stochastic Summaries: Characterizing Structured Datasets Using Probabilistic Programs

Jack Stanek, Adithya Murali

cs.PL ·submitted 2026-10-31 18:41 UTC · v1
benchmark

Abstract

What does my data look like? We study the problem of representing and learning summaries of datasets that account for both their structural and statistical properties. This problem is widely useful across many application domains that involve large datasets and analysis/modeling of data, and is of particular interest to Programming Languages. In particular, in this work we focus on the problem of learning these "stochastic summaries" for tree-like data composed of inductive datatypes and argue that probabilistic programs over inductive datatypes can effectively represent the desired summaries. We present Tali, a Probabilistic Programming Language over inductive datatypes, and study the problem of learning such programs from data samples. We identify a semantic property, called Observation-Bounded Compilability, which identifies a set of recursive probabilistic programs which admit exact inference, and can represent many useful and complex probabilistic structures. We then propose an algorithm for learning Tali programs satisfying the OBC property from observations using a combination of program synthesis (stochastic search) and maximum likelihood inference. We implement our learning framework, evaluate it on a diverse benchmark suite, and record our observations on the merits of our approach. We demonstrate the utility of learning stochastic summaries as symbolically-represented priors for downstream learning tasks. We also showcase another utility by using our technique to learn operational profiles of real-world datasets.

Closest papers

Nearest neighbours by meaning across the whole index.

Type-Directed Discretization of Probabilistic Programs (Extended Version)

cs.PL ·2026-08-17 ·Katherine Wu, Jules Jacobs, Kevin Batz, Alexandra Silva
published similarity 0.65
Abstract · Extended version of OOPSLA'26 paper (with appendices)

We study exact discretization as a semantics-preserving transformation for recursive, higher-order probabilistic programs with continuous distributions. We target programs where continuous values are compared against finitely many constants, so exact inference reduces to a discrete problem. Our central technical contribution is a non-local, type-directed analysis that infers where continuous values can be partitioned into finitely many observationally relevant regions, then rewrites sampling and comparison behavior over those regions. We call this transformation Slice. Because this construction is global and type-directed, correctness requires reasoning beyond the local syntax: we formalize the transformation and prove soundness for boolean queries using a coupling-style logical relations argument over operational semantics. As an application, transformed programs can be executed by discrete engines such as Dice, Roulette, and Storm. Our empirical evaluation shows two complementary strengths of Slice when paired with discrete backends: it enables exact inference for challenging continuous programs that lie beyond the reach of previous exact systems, and, on benchmarks where direct comparison is possible, it is competitive with state-of-the-art exact inference systems for continuous programs.

0.23

Bayes Rule for Conditioning Probabilistic Programs

cs.PL cs.LO ·2026-10-07 ·Feras A. Saad
similarity 0.64
Abstract

Probabilistic programs provide a rigorous programming-language foundation for expressing rich probabilistic models and offer language-level support for solving challenging statistical inference problems. A key theoretical challenge that probabilistic programs inherit from probability theory is conditioning a probability distribution on an observation that has probability zero. Many languages address this challenge by using computational rules for conditioning that may work well for some problems but are statistically unsound for others. This article introduces a principled mathematical approach for conditioning probabilistic programs. We first show that existing techniques based on "soft conditioning" and "neighborhood limits" exhibit semantic issues from the perspective of measure theory and produce inference results that disagree with sound statistical reasoning. By leveraging tools from geometric measure theory, we construct a novel disintegration-based semantics for probabilistic program traces that enables sound conditioning. The theory delivers an explicit Bayes rule representation of the conditional distribution, which is directly compatible with widely used probabilistic inference algorithms that require access to unnormalized posterior densities. Our Bayes rule handles probabilistic models with loops, branches, discrete, continuous, and mixed-type distributions, observations on manifolds, differentiable structure, and additional modeling motifs that arise in practice.

0.15

Foundations of MT-PDCL: Measure-Theoretic Probabilistic Definite Clause Logic

cs.AI ·2026-08-13 ·Costin Bădică, Amelia Bădică
similarity 0.62
Abstract

Standard probabilistic logic programming frameworks typically rely on grounding logic programs into discrete propositional representations. This operational requirement restricts exact inference to finite domains and discrete probability distributions. In this paper, we introduce Measure-Theoretic Probabilistic Definite Clause Logic (MT-PDCL), a generalized foundational framework that eliminates this finite-domain restriction. By explicitly defining stochastic variables over bounded index domains and equipping the interpretation space with standard Borel $σ$-algebras, MT-PDCL allows logical variables to operate natively over continuous measurable spaces. Building on Continuous Distribution Semantics, MT-PDCL models probabilistic rules as mutually independent causal events. However, rather than aggregating these derivations via finite boolean circuits, declarative entailment is formally defined through exact Lebesgue integration over the continuous measure space. We introduce a continuous immediate consequence operator that unifies the integration of continuous prior distributions with the evaluation of exact continuous observations. We demonstrate that this approach replaces the combinatorial bottleneck of discrete grounding with exact, algebraic, and structurally differentiable inference. While this transition trades discrete combinatorics for the geometric curse of dimensionality, it achieves the expressive power of continuous probabilistic models while preserving the pure declarative syntax of definite clause logic.

0.04

PassSum: Leveraging Paths of Abstract Syntax Trees and Self-Supervision for Code Summarization

cs.SE ·2026-10-11 ·Changan Niu, Chuanyi Li, Vincent Ng, Jidong Ge, Liguo Huang +1 more
publishedpositionhighly cited similarity 0.61
Abstract · Journal of Software Evolution and Process, 2024

Code summarization is to provide a high-level comment for a code snippet that typically describes the function and intent of the given code. Recent years have seen the successful application of data-driven code summarization. To improve the performance of the model, numerous approaches use Abstract Syntax Trees (ASTs) to represent the structural information of the code, which is considered by most researchers to be the main factor that distinguishes code from natural language. Then, such data-driven methods are trained on large-scale labeled datasets to obtain a model with strong generalization capabilities that can be applied to new examples. Nevertheless, we argue that state-of-the-art approaches suffer from two key weaknesses: (1) inefficient encoding of ASTs; (2) reliance on a large labeled corpus for model training. As a result, such drawbacks lead to (1) oversized model, slow training, information loss and instability; (2) inability to be applied to programming languages with only a small amount of labeled data. In light of these weaknesses, we propose PassSum, a code summarization approach that addresses the aforementioned weaknesses via (1) a novel input representation which contains an efficient AST encoding method; (2) introducing three pre-training objectives and pre-training our model with a large amount of (easy-to-obtain) unlabeled data under the guidance of self-supervised learning. Experimental results on code summarization for Java, Python and Ruby methods demonstrate the superiority of PassSum to state-of-the-art methods. Further experiments demonstrate that the input representation we use has both temporal and spatial advantages in addition to performance leadership. In addition, pre-training is also shown to make the model more generalizable with less labeled data, and also to speed up the convergence of the model during training.

0.60

Optimal Probabilistic Answer Set Programming: Complexity and Implementations

cs.LO cs.AI ·2026-11-06 ·Damiano Azzolini, Giuseppe Mazzotta, Francesco Ricca, Fabrizio Riguzzi
published similarity 0.59
Abstract · Accepted for publication in Theory and Practice of Logic Programming

Probabilistic Answer Set Programming (PASP) extends Answer Set Programming with the possibility of representing uncertain data. Among the possible available semantics, we focus here on the credal semantics. In this setting, prior work has focused exclusively on plain ASP programs, i.e., programs without optimization constructs. However, many real world tasks define optimality criteria over the possible solutions, which cannot be conveniently modeled with existing probabilistic ASP frameworks. In this paper, we close this gap and propose optimal Probabilistic Answer Set Programming, which extends PASP by also allowing weak constraints, which are the standard optimization construct of ASP. We define the semantics of such programs, study the computational complexity of the inference and most probable explanation tasks, and propose practical implementations based on Algebraic Model Counting and Answer Set Programming with Quantifiers. An empirical evaluation of the proposed approach on three real world tasks confirms the applicability of our framework.

0.38

Statopia: A Prover--Library Ecosystem for Automated Formalization and Proof Discovery in Statistics

cs.AI stat.CO ·2026-11-08 ·Ziyuan Chen, Tong Gan, Wei Zhang, Ruofei Fang, Boyue Tang +2 more
theory similarity 0.59
Abstract

Theoretical results in statistics and machine learning rest on long, technically delicate proofs, and fluent arguments generated by large language models are not necessarily correct. Automated formalization makes such arguments mechanically checkable, and automated proving goes further by discovering machine-checked proofs for statements whose proofs are incomplete or missing altogether. Both require reconstructing assumptions from source materials, accessing specialized mathematical infrastructure and managing long proof developments. We present Statopia, an ecosystem that jointly develops Statopia Prover, an independent agent specialized for formalizing and proving results in statistics and machine learning, and Statlib, a Lean~4 library built with the prover and organized for automated use. The prover controls its own execution without relying on external coding agents. It is built for formal proof discovery and checking existing proofs. A natural-language proof, when available, guides its search but is not required: from a statement alone, the prover develops the argument itself and constructs a Lean proof. Its workflow integrates source preparation, statement review, library supported planning and proof construction. Dynamic proof dependency graphs and task groups support parallel, resumable proof development. Statlib's shared definitions and theorem interfaces are organized for retrieval and composition by agents, and its coverage of statistics keeps expanding. Verified results and usage feedback from the prover inform reviewed library updates, so that proof development drives this expansion. A cross-platform application provides an interactive workspace for uploading source files and running tasks locally or in the cloud.

0.13

Diverse Why-Provenance for Datalog Queries

cs.DB ·2026-10-17 ·Marco Calautti, Mostafa Milani, Andreas Pieris
similarity 0.57
Abstract · Extended version of a conference submission

Datalog is a powerful rule-based language that allows us to express complex recursive queries and has found numerous applications over the years. Explaining why a result to a Datalog query is obtained is an essential task towards explainable and transparent data-intensive applications that rely on Datalog. A standard way of explaining a query result is the so-called why-provenance, which provides information about the witnesses to a query result in the form of subsets of the input database that as a whole can be used to derive that result. The state-of-the-art approach for efficiently computing the why-provenance explanations of a certain query result aims at enumerating, without repetitions, the relevant explanations by relying on off-the-shelf SAT solvers. However, whenever the set of explanations is very large, outputting the entire set might be prohibitively expensive. Moreover, it is questionable the practical usefulness of flooding the user with a very large number of explanations, many of them possibly differing only marginally. In this case, one can argue that it would be practically more useful to compute a small, sufficiently diverse subset of the set of why-provenance explanations. The present work initiates the study of the latter problem. In particular, we formalize the problem of interest as an optimization problem, and, after showing that it is highly intractable (it is NP-hard even in data complexity), we investigate whether ILP optimization solvers can be employed towards practical solutions. Our main finding is that this is achievable as long as we keep the requested set of explanations small, or we employ approximation algorithms (with error guarantees).

0.20

DIADA: Automatic Data Composition in Data Lakes

cs.DB ·2026-10-01 ·Marc Maynou, Albert Martin, Sergi Nadal, Anna Queralt, Oscar Romero
similarity 0.57
Abstract

Data lakes contain a plethora of attributes scattered across many tables that, when combined, provide enhanced assets for data analysis. Nonetheless, deciding which attributes belong together in meaningful relations remains a manual, per-task effort. Merging by joinability alone provides no guarantees regarding attribute relevance, while selecting features against a single target discards attributes useful to other tasks. To address this gap, we introduce the data composition problem: organizing a fragmented, heterogeneous lake into meaningful relations, agnostic of any particular analytical task so that the resulting organization can serve as a common foundation for diverse downstream analyses. We propose DIADA, a composition system that employs multivariate dependence as the criterion for assessing the meaningfulness of a relation and approximates it by hypothesizing independence among attributes and identifying those sets that violate this hypothesis. To do so, we map the attributes to a predicate space, forming a lattice under inclusion and mining those predicate sets that exhibit dependence among their constituents. We contribute a dedicated and scalable algorithm to effectively explore this space, outscaling classical algorithms for mining relationships, thus discovering dependencies that would otherwise be impractical to identify. We demonstrate that applying a single data composition process benefits diverse potential downstream tasks. This is the result of providing a subset of low-noise, statistically relevant attributes that increases the confidence that detected patterns are grounded in real relationships, thus preventing common modeling issues in large-scale environments.

0.29