Abstract
In the last few years there has been a growing interest towards methods for statistical inference and learning based on computational geometry and, notably, tropical geometry, that is, the study of algebraic varieties over the min-plus semiring. At the same time, recent work has demonstrated the possibility of interpreting higher-order probabilistic programming languages in the framework of tropical mathematics, by exploiting algebraic and categorical tools coming from the semantics of linear logic. In this work we combine these two worlds, showing that tools and ideas from tropical geometry can be used to perform statistical inference over higher-order probabilistic programs. Notably, we first show that each such program can be associated with a degree and a n-dimensional polyhedron that encode its most likely runs. Then, we use these tools in order to design an intersection type system that estimates most likely runs in a compositional and efficient way.
| Original language | English |
|---|---|
| Article number | 33 |
| Pages (from-to) | 951-980 |
| Journal | Proceedings of the ACM on Programming Languages (PACMPL) |
| Volume | 10 |
| Issue number | POPL |
| Early online date | 8 Jan 2026 |
| DOIs | |
| Publication status | Published - 8 Jan 2026 |
Funding
The authors would like to greatly thank the anonymous reviewers for their careful reading and forseveral questions that helped us significantly improve the first version of the paper.Davide Barbarossa has been funded by the EPSRC grant number EP/W035847/1. Paolo Pistonehas been funded by the ANR grant number ANR-23-CPJ1-0054-01. For the purpose of Open Accessthe authors have applied a CC BY public copyright licence to any Author Accepted Manuscriptversion arising from this submission.