🤖 AI

Counting Worlds Branching Time Semantics for post-hoc Bias Mitigation in generative AI

This paper introduces CTLF, a branching-time logic with counting worlds semantics that provides formal guarantees for post-hoc bias mitigation in generative AI by enabling the verification, prediction, and correction of fairness violations in output sequences.

Original authors: Alessandro G. Buda, Giuseppe Primiero, Leonardo Ceragioli, Melissa Antonelli

Published 2026-04-22

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Alessandro G. Buda, Giuseppe Primiero, Leonardo Ceragioli, Melissa Antonelli

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

The Big Picture: The "Unfair Dice" Problem

Imagine you have a magic image generator (like a high-tech artist). You ask it to draw 10 pictures of "engineers." Unfortunately, the artist was trained on a library of old photos where 75% of the engineers were men and only 25% were women.

Because the artist learned from that library, every time you ask for a picture, it's like rolling a weighted die. It keeps rolling "Male Engineer" way too often. If you ask for 10 pictures, you might get 8 men and 2 women, even though you wanted a fair 50/50 split.

This is bias amplification. The AI isn't just copying the past; it's making the imbalance worse as it generates more and more images.

The Solution: A "Fairness GPS"

The authors of this paper propose a new mathematical tool called CTLF (Counting Worlds Logic). Think of this tool as a Fairness GPS for the AI's output.

Instead of waiting until the AI finishes all 10 pictures to say, "Oh no, that was unfair," this GPS checks the work while it's being created. It asks three critical questions at every single step:

Where are we now? (Are we still on track for a fair 50/50 split?)
Where are we going? (If we keep going, is it mathematically possible to finish fairly?)
What do we need to cut? (If we are off track, how many bad pictures do we need to throw away to fix it?)

The Core Concept: "Counting Worlds"

To understand how this GPS works, imagine the AI's generation process not as a single line of events, but as a giant tree of possibilities.

The Tree: Every time the AI generates one image, the future branches out.
- Branch A: The AI draws a Male Engineer.
- Branch B: The AI draws a Female Engineer.
The "Worlds": In this logic, every single path down the tree is a different "World."
- In one world, the AI draws 10 men in a row.
- In another world, it draws 5 men and 5 women.
- In a third, it draws 10 women.

The CTLF tool looks at the whole tree. It counts how many "Worlds" (paths) lead to a fair outcome and how many lead to an unfair one.

How It Works in Real Life (The Analogy)

Let's use the paper's example of generating images of engineers.

Scenario 1: The "Green Light" (We are safe)
You ask for 6 images.

Image 1: Male
Image 2: Female
Image 3: Male
Image 4: Female
Current Count: 2 Men, 2 Women.
The GPS says: "Great! You are exactly on track. Even if the next two are both Men, you can still finish with a 50/50 split. Keep going."

Scenario 2: The "Red Light" (We are in trouble)
You ask for 6 images.

Image 1: Male
Image 2: Male
Image 3: Male
Image 4: Male
Current Count: 4 Men, 0 Women.
The GPS says: "Stop! You have already used up your 'Male' quota. Even if the next two are Women, you will end up with 4 Men and 2 Women. You cannot reach a 50/50 split anymore."

Scenario 3: The "Emergency Brake" (Mitigation)
The GPS realizes you are in trouble. It doesn't just say "fail." It calculates a Mitigation Plan.

It looks at the tree and says: "To get back to a fair 50/50 split, you need to remove the last 2 Male images you generated."
It tells the system: "Discard Image 3 and Image 4. Start over or generate new ones until you get a Female."

Why This Matters

Most current methods to fix AI bias are like guessing. They might say, "Hey, that looks a bit too male-heavy, let's try to generate a female one next." But they don't have a mathematical guarantee that this will actually work.

This paper introduces a formal guarantee. It's like having a strict rulebook that says:

"Based on the math, if you generate this specific sequence, it is impossible to be fair. You must stop and delete these specific items right now."

The Future: An Adaptive Coach

The authors also suggest that in the future, this system could be even smarter. Instead of just checking against a fixed rule (like "50% Men, 50% Women"), the system could be an Adaptive Coach.

If the AI keeps accidentally generating too many men, the Coach could subtly adjust the AI's "internal weights" in real-time, making it slightly more likely to pick a woman for the next image, gently steering the whole process back to fairness without needing to delete anything.

Summary

The Problem: AI often repeats and worsens real-world biases (like gender imbalance).
The Tool: A new logic system (CTLF) that treats AI outputs as a branching tree of possibilities.
The Magic: It counts the "Worlds" to see if a fair outcome is still possible.
The Action: If fairness is impossible, it tells you exactly how many bad outputs to delete to restore balance, acting as a real-time "Fairness GPS" for Generative AI.

1. Problem Statement

Generative AI systems frequently amplify biases present in their training data, leading to unfair outputs (e.g., skewed gender distributions in image generation). While various inference-time and post-hoc mitigation strategies exist (such as token filtering or activation removal), they are largely empirical and lack formal guarantees.

Current methods struggle to answer three critical questions dynamically during the generation process:

Verification: Is the current series of outputs still within an intended, fair probability distribution?
Prediction: What is the likelihood that the series will remain within acceptable bounds as new outputs are generated?
Intervention: If the distribution has deviated, how many outputs must be removed (post-hoc mitigation) to restore fairness?

The authors argue that existing linear temporal logic approaches (like LTLF) are insufficient for reasoning about the branching possibilities of future outputs and the specific counts required to maintain fairness.

2. Methodology: CTLF Logic and Counting Worlds Semantics

The authors propose CTLF (Counting Temporal Logic for Fairness), a branching-time logic designed to reason about series of generative AI outputs. The core innovation is a Counting Worlds Semantics where the generation process is modeled as a tree of possible worlds.

A. The Model Structure

The generation process is formalized as a model $M = (W, W^1, W^n, R_e, R_f, V)$ :

Worlds ( $W$ ): Each world represents a possible output at a specific step in the generation sequence.
Branching: The structure is a tree where:
- $R_e$ (Childhood relation): A backward relation connecting a current state to its unique parent (the previous output).
- $R_f$ (Parenthood relation): A forward relation connecting a state to all possible future outcomes (children).
Paths: A complete path represents a full sequence of $n$ outputs.
Probability Distribution ( $\Phi_\Sigma$ ): A function that filters the set of all possible paths ( $\Pi^*$ ) to only those that satisfy a target probability distribution $\Sigma$ (e.g., 50% Male / 50% Female).

B. The Logic Syntax

CTLF extends standard modal logic with counting operators parameterized by a probability threshold $q \in [0, 1]$ :

State Formulas ( $\phi$ ):
- $\square_q \phi$ : At the current state, $\phi$ has occurred at least $q \times m$ times in the history (where $m$ is the current step count).
- $\blacksquare_q \phi$ : It is possible that $\phi$ has occurred $q \times m$ times in some valid path consistent with the target distribution.
- $\bigcirc_q \phi$ : There exists a complete path where $\phi$ occurs $q \times n$ times.
- $\triangleright_q \phi$ : The probability that $\phi$ occurs in the next step, given a valid distribution, is at least $q$ .
Path Formulas ( $\psi$ ):
- $\bigtriangledown_q \phi$ : In a complete path, $\phi$ occurs at least $q \times n$ times.
- $\dagger_q \phi$ : Starting from the current state, the probability that the path can be completed while satisfying the target distribution is at least $q$ .

3. Key Contributions

Formal Framework for Bias: The paper introduces the first formal logic specifically designed to verify and mitigate bias in series of generative outputs using branching-time semantics.
Counting Worlds Semantics: Unlike standard probabilistic model checking, CTLF explicitly counts occurrences of protected attributes (e.g., gender) across the tree of possible worlds to determine if a "fair" subset exists.
Post-Hoc Mitigation Strategy: The logic provides a mechanism to calculate the exact number of outputs to remove to restore fairness. If the current path deviates too far from the target distribution, the logic identifies if a "fair completion" is still possible and, if not, determines the minimal subset of the history that satisfies the fairness constraint.
Predictive Capability: The $\triangleright$ and $\dagger$ operators allow the system to predict the likelihood of future fairness violations before they happen, enabling early intervention.

4. Results and Illustrative Example

The authors demonstrate the framework using a "Toy Example" of image generation:

Scenario: A model trained on a biased dataset (75% Male, 25% Female) generates images for the prompt "Give me a picture of an engineer." The goal is to achieve a 50/50 distribution.
Verification:
- At step 4, if the output is 2M/2F, the formula $w_4 \models \square_{1/2} M \land \square_{1/2} F$ holds, confirming the current series is fair.
- The logic calculates that there is a 50% probability ( $\dagger_{1/2}$ ) that the series can be completed fairly from this point.
Mitigation:
- If the series reaches 12 outputs with a 9M/3F ratio (violating the 50/50 target), the logic determines that the maximum number of females allowed in a fair subset is 3.
- Consequently, the maximum fair subset size is 6 (3M/3F).
- The logic identifies that the current male quota is exhausted ( $w_5 \models \bigcirc_{1/2} M$ ).
- Action: The system prescribes removing all subsequent male outputs to form a balanced subset $O'$ of size 6.

5. Significance and Future Work

Significance:

Theoretical Rigor: Moves bias mitigation from heuristic/empirical approaches to a mathematically verifiable framework with formal guarantees.
Dynamic Control: Enables "inference-time control" that can predict failures and intervene before the generation is complete, rather than just filtering after the fact.
Applicability: The framework is applicable to both text-to-image models and Large Language Models (LLMs).

Future Directions:

Weighted Transitions: Extending the model to assign explicit weights to transitions, reflecting non-uniform probabilities in the generation process.
Adaptive Distributions: Moving from a fixed target distribution to a dynamic one that updates in real-time based on observed outputs (similar to parametric Markov chains).
Implementation: Development of a software tool for the MIRAI Toolbox to automate the checking and mitigation procedures on real-world AI systems.

In conclusion, CTLF offers a robust logical foundation for ensuring that generative AI systems adhere to fairness constraints throughout the generation process, providing a clear path for formal verification and automated bias mitigation.