💻 computer science

Evidence-Tracked Tape Semantics for Probabilistic Computation

This paper introduces an evidence-tracked tape semantics for probabilistic computation that unifies intensional and extensional perspectives through a realizability framework, enabling higher-order logic with uniform evidence transformers to derive sound quantitative laws and support probability-one reasoning via tape-rewiring and pushforward abstractions.

Original authors: Liron Cohen (Ben-Gurion University of the Negev, Beer-Sheva, Israel), Tomer Samara (Ben-Gurion University of the Negev, Beer-Sheva, Israel)

Published 2026-05-12

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Liron Cohen (Ben-Gurion University of the Negev, Beer-Sheva, Israel), Tomer Samara (Ben-Gurion University of the Negev, Beer-Sheva, Israel)

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to understand how a computer program makes decisions when it involves chance, like rolling a die or flipping a coin.

Most computer scientists usually look at these programs from the "outside." They ask: "If I run this program a million times, what is the final distribution of results?" This is like looking at a bag of marbles after you've shaken it and asking, "What percentage are red?" This is called extensional reasoning. It's useful, but it forgets how the marbles got mixed.

This paper proposes a different way to look at things: intensional reasoning. Instead of just looking at the final bag of marbles, the authors imagine the program as a machine that reads from a long, explicit tape of random numbers (like a roll of film or a stream of bits).

Here is a breakdown of their ideas using simple analogies:

1. The "Random Tape" Metaphor

Think of a probabilistic program not as a magic box that generates randomness, but as a deterministic robot reading from a pre-written script.

The Script (The Tape): Imagine a very long piece of paper with a sequence of random numbers written on it (0s and 1s).
The Robot: The program reads this paper from left to right. If it needs a random number, it reads the next bit. If it needs another, it reads the next one.
The Twist: Because the robot reads from a single, physical piece of paper, if it reads a "1" and then uses that same "1" again later, the program knows they are the same. If it reads two different bits, it knows they are different.

This is crucial because in the "outside" view (the bag of marbles), reusing a number and picking two new numbers often look the same statistically. But in the "tape" view, they are completely different actions. This allows the authors to track correlations (how one random choice affects another) much better.

2. The "Evidence Tracker" (The Receipt)

The paper introduces a concept called Evidence-Tracked Semantics.

The Analogy: Imagine you are a judge in a court case. Usually, you just decide if a statement is true or false. But here, the authors want a receipt for every proof.
How it works: When the authors prove that "Program A leads to Result B," they don't just say "It's true." They produce a specific piece of code (an "evidence transformer") that acts like a translator. This translator takes the "proof" that A works and mechanically transforms it into a "proof" that B works.
Why it matters: This makes the logic proof-relevant. It's not just about what is true, but how we know it's true. If you change the way the program reads the tape (rewiring the tape), this "translator" code can be updated to show that the proof still holds, just in a new format.

3. The "Splitting" Trick (Independence)

One of the hardest things to do in probabilistic programming is ensuring two things happen independently.

The Problem: If you have one long tape and you run two programs one after the other, they will naturally read from the same tape. They aren't independent; they are sharing the same stream of randomness.
The Solution: The authors propose a "Splitter." Imagine taking that single long tape and cutting it in half. The top half goes to Program A, and the bottom half goes to Program B.
The Magic: They show that if you have a mathematical rule (a "realizable map") that can split the tape, you can prove that the two programs are now using independent randomness. They can then take a proof made for "two separate tapes" and mathematically "stitch" it back together to prove something about a "single tape" program. This is like proving a rule for two separate dice, and then showing how to apply that rule to a single die that has been split into two faces.

4. From "Tape" to "Law" (The Translation)

The paper builds a bridge between their detailed "tape" view and the standard "law" view (the bag of marbles).

The Process:
1. Intensional Layer: They do all their complex reasoning on the tape, tracking exactly how randomness is used.
2. The Measure: They decide on a specific way to sample the tape (e.g., "assume every bit is a fair coin flip").
3. Extraction: They use a mathematical tool (Expectation) to translate their detailed tape proofs into standard numbers (probabilities).
4. The "Almost Sure" Filter: They introduce a filter that ignores "null sets" (events so rare they have a probability of zero). This is like saying, "If something only happens on a tape that is infinitely unlikely, we can pretend it never happens." This cleans up the math and makes it robust.

5. The "Must" Abstraction

Finally, they look at a specific type of safety check called the "Must" property.

The Analogy: Imagine a safety inspector checking a rollercoaster. They don't care if the coaster might crash 1% of the time; they care if it crashes any time it has a non-zero chance of happening.
The Result: They show that if a program is proven safe on the "tape" level (meaning it works for almost every possible tape), it translates perfectly into a "Must" safety guarantee on the "law" level. This gives a way to prove that a program will almost certainly terminate or stay safe, without getting bogged down in complex probability numbers.

Summary

In short, this paper builds a new language for talking about random programs.

Instead of just guessing the final odds, it treats randomness as a physical resource (a tape) that programs consume.
It provides receipts (evidence) for every logical step, allowing us to track how changes in the random source affect the program.
It offers tools to split randomness to create independence and stitch it back together.
It finally translates these detailed, tape-based proofs into the standard, high-level probability statements we are used to, ensuring that the math is sound and the logic is transparent.

The authors aren't saying this is the only way to do it, but they argue it's a much clearer way to understand how randomness is used inside a program, especially when programs are complex and nested.

Technical Summary: Evidence-Tracked Tape Semantics for Probabilistic Computation

Problem Statement

Probabilistic computation is typically modeled in two distinct ways: extensionally, by the output distribution (law) of a program, and intensionally, by how the program consumes randomness. Extensional approaches, such as probabilistic Hoare logic or weakest-preexpectation calculus, excel at reasoning about quantitative bounds and output distributions but abstract away the internal structure of randomness consumption. Conversely, tape-based semantics model probabilistic programs as deterministic functions consuming an explicit random tape (e.g., a stream of bits). While this approach naturally captures correlations, reuse of randomness, and deterministic transformations of the random source, it often lacks a principled logical framework to connect intensional tape-level reasoning with extensional quantitative statements.

Existing literature often treats tape-based reasoning operationally or handles the link to probabilistic statements outside the logic. There is a need for a unified framework that maintains the intensional benefits of tape-based models (such as proof-relevant tracking of randomness reuse) while providing a sound mechanism to extract quantitative probabilistic guarantees (expectations, probabilities) and support transformation arguments (e.g., rewiring random sources).

Methodology

The authors develop a evidence-tracked tape semantics by instantiating a generic pipeline for constructing models of higher-order intuitionistic logic: Monadic Core $\to$ Evidenced Frame $\to$ Realizability Tripos.

Monadic Core Construction:
- Monad: The computational effect is modeled using a Reader Monad over a measurable tape space $(R, \Sigma)$ . A computation is a measurable function $m: R \to X_\perp$ (where $X_\perp$ includes a divergence value). This makes randomness an explicit parameter rather than an internal probabilistic choice.
- Truth Values: Instead of Boolean values, truth values are tape-indexed quantitative predicates $\Omega_R := R \to [0, 1]$ , ordered pointwise. This allows for "success levels" on specific tapes.
- Modality: An $M$ -modality $\diamond$ is defined as a weakest-precondition style transformer: $\langle \diamond x \leftarrow m \diamond \rangle \psi(x)$ evaluates the post-condition $\psi$ on the output of $m$ using the same tape $r$ . This preserves correlations across sequential composition.
Evidenced Frames:
- The framework constructs an Evidenced Frame where entailments $\phi \xrightarrow{e} \psi$ are witnessed by a uniform evidence transformer $e$ (a code).
- This transformer maps realizers of the premise to realizers of the conclusion uniformly across all tapes. This "proof-relevance" is crucial for tracking how evidence adapts when the random source is transformed (e.g., rewired or split).
Extraction and Quotienting:
- To recover numeric probabilistic statements, a probability measure $\rho$ is fixed on the tape space.
- Extraction: Expectation maps $\alpha \in \Omega_R$ to a number $E_\rho(\alpha)$ . Since expectation is monotonic, tape-level entailments yield sound numeric inequalities.
- Almost-Sure Quotient: To eliminate null-set artifacts, the authors quotient the truth values by almost-sure equality ( $\equiv_{a.s.}$ ), forming $\Omega_{a.s.}$ . This yields a "probability-one" fragment compatible with the logical structure, supporting reasoning about properties that hold with probability 1 (e.g., almost-sure termination).
Intensional Principles:
- Realizable Tape Maps: The paper introduces realizable tape maps $\kappa: R \to R'$ . If a map is "realizable" (admits a code translation $tr_\kappa$ ), entailments and their evidence can be transported from one tape model to another. This supports proof reuse across changes in random source representation.
- Splitting: For stream tapes ( $R = \{0,1\}^\mathbb{N}$ ), a canonical splitting map (separating even/odd bits) is used to enforce independent draws. The framework shows how to transport reasoning about independent draws (on a product space) back to a single-tape setting via realizability.

Key Contributions

Evidence-Tracked Tape Semantics: The paper presents a higher-order logic where entailments are uniform, tape-by-tape refinements witnessed by concrete evidence transformers. This makes the logic intensional and correlation-aware, distinguishing between reusing a random bit and drawing two independent bits, even if marginal distributions are identical.
Proof-Relevant Transport: The authors introduce realizable tape maps and prove a transport theorem (Theorem 15). This allows entailments proven in one tape model (e.g., with a specific random source) to be translated into another model (e.g., a rewired source) while preserving the evidence code. This enables formalizing arguments about reshaping random sources.
Canonical Splitting for Independence: A disciplined approach to modeling independent draws is developed using a splitting map on stream tapes. The paper demonstrates how to transport entailments from a multi-tape (independent) setting back to a single-tape setting, bridging the gap between operational independence and single-tape semantics.
Bridge to Quantitative Semantics: The work establishes a rigorous bridge between intensional tape proofs and extensional probabilistic statements. By fixing a measure and applying expectation extraction, tape-level entailments are shown to yield sound quantitative inequalities.
Probability-One Abstraction: The paper defines a must-style abstraction over finitary distributions. This abstraction captures probability-one properties (like safety and almost-sure termination) and is shown to be the robust fragment of tape reasoning that aligns with extensional laws without requiring full quantitative extraction.

Results

Soundness of Extraction: The paper proves that if an entailment $\phi \xrightarrow{e} \psi$ holds in the tape evidenced frame, then for any fixed measure $\rho$ , the extracted numeric values satisfy $E_\rho(\phi) \leq E_\rho(\psi)$ (Theorem 15 combined with Lemma 17).
Transport of Evidence: Theorem 15 demonstrates that if a tape map $\kappa$ is realizable, any entailment in the target tape space can be pulled back to the source space with a translated evidence code. This is applied to the von Neumann unbiasing procedure, showing how symmetry in the tape model translates to fairness in the extracted probability.
Independence via Splitting: The paper shows that splitting a stream tape into even/odd components induces a product measure (Lemma 18). Consequently, reasoning about independent draws on the product space can be transported to a single tape, validating standard amplification arguments (e.g., majority voting) within the evidence-tracked framework (Example 20).
Quotienting: Proposition 12 establishes that the almost-sure quotient preserves the entailment structure, allowing the logic to ignore null sets while maintaining the higher-order Heyting structure necessary for the realizability tripos.

Significance and Claims

The paper claims to provide a clean, evidence-tracked account of tape-based computation that resolves the tension between intensional structure and extensional probability.

Intensional vs. Extensional: Unlike standard probabilistic logics that internalize quantitative specifications (e.g., "probability of $P$ is $\ge 0.9$ "), this approach keeps internal reasoning measure-agnostic. Quantitative claims are only recovered after fixing a measure, allowing the same tape-level proof to be instantiated with different probabilistic readings.
Proof Relevance: The framework emphasizes that entailments are not just relations between predicates but are witnessed by concrete code transformers. This is essential for transformation arguments where the random source is reshaped; the evidence code must be updated to match the new tape structure.
Modesty: The authors note that while the framework supports quantitative reasoning, the primary novelty lies in the instantiation of the generic monadic-core-to-tripos pipeline for tape-consuming computation and the resulting bridge theorems. The paper does not claim to replace existing quantitative logics but to provide a foundational layer that supports proof-relevant transport and independence disciplines invisible at the level of output laws.
Future Work: The paper identifies extending the model to general measurable spaces (beyond countable outcomes) and developing a syntactic proof theory for the induced tripos as natural next steps. It also suggests characterizing the "largest law-level fragment" obtainable from tape proofs.

In summary, the paper offers a semantic foundation where randomness is an explicit resource, correlations are visible, and proofs are transportable across different representations of that resource, with a rigorous mechanism to extract standard probabilistic guarantees.