A Domain-Specific Probabilistic Programming Language for Reasoning about Reasoning (Or: A Memo on memo)

Kartik Chandra, Tony Chen, Joshua B. Tenenbaum, Jonathan Ragan-Kelley

TL;DR

memo is a new domain-specific probabilistic programming language (PPL) designed to model "theory of mind"—the human ability to reason about the thoughts of others. By compiling recursive probabilistic models into high-performance array programs (via JAX), memo achieves speedups of up to several orders of magnitude while providing a specialized syntax that prevents common logic errors in multi-agent modeling.

What Problem Does This Paper Address?

Cognitive scientists and economists often use the "Recursive Rationality" (RR) paradigm to model how agents interact. In this framework, Alice thinks about what Bob thinks Alice wants. While elegant, these models are notoriously difficult to implement for two reasons:

  1. Correctness ("Perpetration Confusion"): In general-purpose PPLs, it is easy to accidentally let one agent "mind-read" another. For example, a programmer might inadvertently give an agent access to a variable representing the "true" state of the world that the agent shouldn't actually know. The authors call this "perpetration confusion"—a mix-up of which agent is responsible for which choice.
  2. Efficiency: Thinking about thinking leads to a combinatorial explosion. If Alice considers 10 possible goals for Bob, and Bob considers 10 possible actions for Alice, the state space balloons rapidly. Traditional PPLs often rely on Monte Carlo sampling, which struggles to produce precise results in these deep, nested recursive loops, leading to models that take days to run.

Methods

The authors introduce memo, a PPL embedded in Python that treats "agency" as a first-class citizen.

  • Frames of Mind: The compiler statically tracks "frames of mind"—nested data structures that define what each agent knows versus what they find uncertain. This allows the compiler to catch "mind-reading" bugs at compile-time.
  • Inference as Array Programming: A key insight is that most RR models use discrete distributions with modest cardinality. memo compiles these nested inference queries into a sequence of array operations (tensor contractions and normalizations).
  • JAX Integration: By targeting JAX, memo models are end-to-end differentiable and can run on GPUs. This allows researchers to use standard deep learning optimizers (like Adam) to fit model parameters to experimental data in seconds rather than hours.

Datasets

The paper evaluates memo across several benchmarks:

  • Classic Models: Rational Speech Acts (RSA), Schelling coordination games, and Markov Decision Processes (MDPs/POMDPs).
  • "In-the-Wild" Research: Two real-world models migrated from other languages: a theory of lying (originally in Gen) and a model of social relationship inference based on "saliva sharing" (originally in R).
  • New Benchmarks: The authors introduce a "Font Design" task (integrating RSA with a ResNet-based vision model) and a "Takeaway" game that requires the model to reason about the computational cost of its own thinking.

Key Insights and Ideas

  • Exact beats Sampling: For the specific structure of recursive reasoning, exact enumerative inference is often faster and more stable than sampling. By turning inference into a "truth table" or "payoff matrix" calculation, the authors bypass the variance issues of Monte Carlo methods.
  • Agency is a Type System: By formalizing "who knows what" into the language's static semantics, memo transforms philosophical principles of agency (like "no mind control") into catchable compiler errors.
  • Reflecting on FLOPs: Because memo uses JAX, it can extract the exact number of floating-point operations (FLOPs) required for a computation. This enables a new class of "resource-rational" models where agents decide how much to "think" based on the predicted computational cost.

Key Results

The performance gains are dramatic, as summarized in the paper's evaluation:

  • Speed: memo outperformed expert-written implementations in every case. The "Lying" model saw a 2,000,000x speedup over the original Gen implementation (largely due to the shift from sampling to exact enumeration in recursive loops). The Schelling game was 200x faster than the WebPPL version.
  • Conciseness: Models were consistently shorter. The "Lying" model shrank from 220 lines of code to just 50.
  • GPU Scaling: For large-scale MDP planning (21x21 grid), memo on a GPU took 0.377s, whereas the CPU-based WebPPL version took 79 seconds.

Limitations and Future Work

The authors acknowledge that memo is currently specialized for discrete random variables. While continuous variables can be discretized, the array-oriented backend does not natively support continuous distributions or complex, dynamic control flow where the sequence of choices isn't known statically.

Future directions include exploring hybrid inference backends to support continuous variables and using memo as a "language of thought" to improve the theory-of-mind capabilities of Large Language Models (LLMs).

Summary updated

Abstract

The human ability to think about thinking ("theory of mind") is a fundamental object of study in many disciplines. In recent decades, researchers across these disciplines have converged on a rich computational paradigm for modeling theory of mind, grounded in recursive probabilistic reasoning. However, practitioners often find programming in this paradigm challenging: first, because thinking-about-thinking is confusing for programmers, and second, because models are slow to run. This paper presents memo, a new domain-specific probabilistic programming language that overcomes these challenges: first, by providing specialized syntax and semantics for theory of mind, and second, by taking a unique approach to inference that scales well on modern hardware via array programming. memo enables practitioners to write dramatically faster models with much less code, and has already been adopted by several research groups.
BibTeX
@inproceedings{chandra2025domain,
  author = {Kartik Chandra and Tony Chen and Joshua B. Tenenbaum and Jonathan Ragan-Kelley},
  title = {{A Domain-Specific Probabilistic Programming Language for Reasoning about Reasoning (Or: A Memo on memo)}},
  booktitle = {Proc. ACM Program. Lang},
  year = {2025},
  url = {https://openreview.net/forum?id=4jnm3TLWy2},
}

Loading related content...

Figure