Formal Specification, Assessment, and Enforcement of Fairness for Generative AIs
Chih-Hong Cheng Changshun Wu Harald Ruess Xingyu Zhao Saddek Bensalem






A]Chih-Hong Cheng
B]Changshun Wu
C]Harald Ruess
D]Xingyu Zhao
B]Saddek Bensalem


[A]Chalmers University of Technology, Sweden
[B]Université Grenoble Alpes, France
[C]Entalus, FL, USA
[D]WMG, University of Warwick, UK


Reinforcing or even exacerbating societal biases and inequalities
will increase significantly as generative AI increasingly produces useful artifacts, from text to images and beyond, for the real world.
We address these issues by formally characterizing the notion of fairness for generative AI as a basis for monitoring and enforcing fairness. We define two levels of fairness using the notion of infinite sequences of abstractions of AI-generated artifacts such as text or images. The first is the fairness demonstrated on the generated sequences, which is evaluated only on the outputs while agnostic to the prompts and models used. The second is the inherent fairness of the generative AI model, which requires that fairness be manifested when input prompts are neutral, that is, they do not explicitly instruct the generative AI to produce a particular type of output. We also study relative intersectional fairness to counteract the combinatorial explosion of fairness when considering multiple categories together with lazy fairness enforcement. 
Finally, fairness monitoring and enforcement are tested against some current generative AI models.









§ INTRODUCTION


Fairness is essential in AI to prevent bias and promote equality in the output from text to images <cit.>. Achieving fairness requires careful algorithm design and training to minimize bias and avoid reinforcing stereotypes. A major challenge is to define and ensure fairness in generative AI systems <cit.>. While traditional approaches use prompt variations to observe system behavior, these methods often fail to capture (1) the complex dynamics of interactions with generative AI and (2) the multifaceted nature of fairness.

 We therefore present a novel framework for defining, evaluating, and enforcing fairness in generative AI systems. By viewing the repeated generation of artifacts (such as images) as a non-terminating process, we propose to use infinite strings over alphabets of abstract concepts to represent the sequence of input prompts and resulting images. This approach allows us to use formal specifications such as Linear Temporal Logic (LTL) <cit.> to define fairness regarding concept groups' eventual and repeated appearances and to connect with the frequency view of fairness. 
We distinguish between the fairness manifested in the generated sequence and the AI's inherent fairness. By inherent fairness, we refer to the condition where the input prompt does not influence the generative AI to bias the output toward a particular concept value (for example, a particular demographic group). 
Most significantly, this notion of fairness is conditional to individual concepts (e.g., economically disadvantaged person or successful business leader) where all images manifest, implying that fairness in the context of generative AI is not a universal property. 


We also address practical considerations such as the exponential number of category combinations (that is, intersectional fairness) and the finite length of the generated artifacts. For the first challenge, we use combinatorial testing <cit.> to create a relative form of intersectional fairness. For the second, we adopt the notion of X_w (weak next) in LTL_f (LTL over finite traces) <cit.> to characterize the recurrence of concepts bounded by a finite distance. With such a mathematically precise formulation, we can not only perform fairness evaluation, but also algorithmically enforce fairness lazily by minimizing the interference with the generative AI model. 
More specifically, fairness enforcement uses counters to keep track of potential deadline violations for each value in the group, where enforcement needs to be triggered in advance 
by anticipating simultaneous deadline violations in the near future. 


Based on these developments we
have implemented a software prototype
for evaluating and enforcing fairness for generative AI systems, and
evaluated them on OpenAI's ChatGPT 4.0 connected with DALL·E3, and on ZHIPU AI's 
GLM-4.[GLM-4 is available at <https://open.bigmodel.cn/>]
Our evaluations clearly show that 
these generative AI models manifest biases that may be inherent in the training data collected, reflecting societal stereotypes. 
Most importantly, these evaluations strongly support the view that the notion of fairness for generative AI is indeed conditional on concepts.
For example, fairness against gender or demographic groups is weak when image sequences are conditioned to the idea of “poor / economically disadvantaged”. In contrast, fairness is strongly manifested when image sequences are conditioned to the idea of “successful business leader”. We also observe that even for all-pair fairness by eventual appearance (the simplest form of relative intersectional fairness), models such as GLM-4 fail to achieve a coverage of 35%, and thus have considerable room for improvement. Finally, enforcement actions are annotated at the generative AI's prompts as an enforcing statement for improved fairness.


Overall, the main contributions of this paper are as follows:

    
  * A sound technical framework that formalizes an interaction with a generative AI system as an infinite sequence of generated artifacts, as the basis for characterizing the fairness of infinite sequences and the generative AI model.
    
  * Solutions to practical challenges of fairness for generative AI, including restricting fairness to finite sequences, relative completeness criteria for intersectional fairness, and enforcing fairness with minimum interference.
    
  
  * A public repository on all our datasets, codes, and experimental results at <https://github.com/SEMTA-Group/FairGenAI>.


The rest of the paper is structured as follows. After reviewing existing results in Sec. <ref>, we formulate the interaction with generative AI models in Sec. <ref>. Subsequently, we detail the different facets of fairness when characterized under formal specifications in Sec. <ref>, and consider in Sec. <ref> practical implications when evaluating finite artifact sequence and intersectional fairness, as well as enforcing fairness. Finally, we report on a preliminary evaluation in Sec. <ref> and conclude in Sec. <ref>. 






§ RELATED WORK



Fairness in AI systems is a pressing issue with many unresolved
challenges <cit.>.
This is especially true for machine learning systems that are trained on data.
Main areas of research focus include dataset bias <cit.> as well as bias measurement and mitigation of models <cit.>. 



A popular framework for fairness assessment in generative AI uses sensitive attribute 
classifiers <cit.>. This involves the generation of a batch of samples from the target generative AI model followed by a sensitive attribute (SA) classifier to classify these samples. The expected value of the SA classifier's output over the sample batch estimates the corresponding attributes, and assesses generator bias. 
However, these approaches do not consider interaction, where the prompts fed into the generative AI may be inherently
biased to influence the generated result. We address this issue in a novel formal fairness characterization, where input prompts are unbiased. In addition, our formulation of fairness is always conditional on concepts, implying that fairness is not universal.
For example, gender fairness is only manifested under images of ”successful business leader” but not ”poor person”. 
While we formalize the interaction as an infinite sequence and define fairness in terms of the possible and repeated occurrences of concept groups, our technical result also allows alignment with the frequency view of fairness.
 In addition, the infinite sequence view also allows us to design enforcement algorithms, where our technique of lazily interfering with the generative AI models (only when necessary) is motivated by the concept of shielding in safe reinforcement learning <cit.>, which itself is rooted in LTL reactive synthesis and safety games <cit.>.

Considering fairness along single dimensions such as gender or race in isolation clearly is 
not sufficient to ensure fairness at their intersections, 
such as groups of dark-skinned women <cit.>.
 These kinds of intersections between gender and racial biases have received significant attention, particularly in the realm of machine learning systems for sensitive analysis tasks <cit.>. Furthermore, these intersections have been explored in language models such as BERT and GPT-2 <cit.>. The authors of <cit.> addressed intersectional occupational bias by examining the intersections of gender with religion, sexuality, ethnicity, political affiliation, and continental name origin. The main challenge in intersectional fairness lies in the impracticality of directly ensuring fairness across all combinations of subgroups, as this approach leads to an exponential proliferation of subgroups with each additional axis of discrimination <cit.>. To address this
 combinatorial explosion, we develop
  a technique which is inspired by k-way combinatorial testing <cit.> to provide a less stringent version of intersectional fairness, which we call relative intersectional fairness. 





§ INTERACTING WITH THE GENERATIVE AI



We mathematically formulate the interaction with the generative AI by characterizing the essence of foundational models (LLMs) implemented with transformers, serving as the basis to define fairness. 


Let f: Σ^* →Σ^* ×ℐ be the generator (generative AI model) that takes an input string s ∈Σ^* and returns (i) an output string and (ii) an image (e.g., ChatGPT 4.0 connected with DALL·E3).

    
  * Σ is the set of possible tokens in a textual language. 

    
  * ℐ{0, …, 255}^H× W× 3, where H, W ∈ℕ_+  are the height and width of an image, and 3 represents that an image has three (RGB) channels.


We use f^img(·) to refer to the part producing the output image and use f^txt(·) to refer to the part producing the output text. 



Our subsequent formulation is motivated by the observation that state-of-the-art generators are implemented using neural networks (e.g., transformers <cit.> and diffusion models <cit.>) and are thus memoryless.
In a typical interaction flow with an LLM like GPT-4 or a similar model, each new input or question is considered in the context of the preceding conversation. Therefore, when one asks a follow-up question C after having received an answer B to the initial question A, the model essentially considers the concatenated sequence of inputs and outputs A ·  B · C to generate its next textual output D. 

[Generating images for a poor person] As a motivating example, we take  ChatGPT 4.0 with DALL·E3 as the generator f to synthesize images of economically disadvantaged people. 
Let Σ be the words in English, space, punctuation, numbers, and special symbols. An example of an input prompt can be p_1 "[Q] Please generate an image of a poor person.". f(p_1) generates an image and the following texts as answers.

    
  * a_1  f^txt(p_1) = "[A] A person in old, tattered clothing standing in a city alley, surrounded by  brick walls … " (further details omitted)

    
  * img_1  f^img(p_1) as illustrated in the top left of Fig. <ref>. 


Subsequently, a follow-up input prompt can be the following: 
p_2  "[Q]  Please  generate an image of a poor person, different from the previous ones.". Following the mechanism as stated previously, f(p_1 · a_1 · p_2) generates the following texts and an image. 

    
  * a_2  f^txt(p_1 · a_1 · p_2) ="[A] A young person sitting on  the ground beside an empty street, their face  reflecting a mix of hope and sorrow. They are  wearing oversized … " (further details omitted)

    
  * img_2  f^img(p_1 · a_1 · p_2) as illustrated in the top row of Fig. <ref>. 





We now mathematically precise the definition of the generation process. Let p_1, p_2, …∈Σ^* form an infinite sequence of input prompts. Given the generator f, we abbreviate f^txt, α(p_α) as the overall text sequence of prompt and answers, which can be defined using the following recursive process stated in Eq. (<ref>). That is, f^txt,α(p_α) concatenates all input prompts and the textual answers generated from f, by continuously feeding p_1, …, p_α.



    f^txt,α(p_α)  
    p_α· f^txt(p_α)    if α = 1
        f^txt, α-1(p_α-1) · p_α   
        · f^txt( f^txt, α-1(p_α-1) · p_α)       otherwise





This allows us to mathematically define f^img,α(p_α), following the recursive structure defined in Eq. (<ref>), to be the α-th image generated by f by feeding input prompts p_1, …, p_α.




    f^img,α(p_α)  
    f^img(p_α)    if α = 1
    
    f^img(f^txt, α -1(p_α -1) · p_α)    otherwise



 Eq. (<ref>) produces the  f^txt,2(p_2) which can be further contaminated with p_3 to generate the textual response a_3 and the third image img_3. 

    f^txt,2(p_2)     =   f^txt,1(p_1)  · p_2· f^txt( f^txt, 1(p_1) · p_2) 
          = p_1 · f^txt(p_1) · p_2 · f^txt( p_1 · f^txt(p_1) · p_2)






  
Remark We discuss some implementation-specific concerns in the following.  Nevertheless, these concerns do not influence the validity of our formulation. (i) Within large language models, the concept of the token window refers to the fixed number of contiguous tokens a model can process at one time, beyond which earlier tokens are no longer considered, effectively “forgetting” them. 
(ii) State-of-the-art image generation is commonly implemented with a separate text-to-image generator 𝒢 (e.g., diffusion model) that takes the produced text as input. Consider the first prompt being p_1, then f^img(p_1) equals 𝒢(f^txt(p_1)).




§ THE DIFFERENT FACETS OF FAIRNESS



We start by defining concept groups, which serve as the basis for characterizing the group fairness of an infinite image sequence as well as the fairness of the generator. Throughout the paper, we use [a ⋯ b] to represent the set of integers ranging from a to b.


    Let cgf_i: ℐ→ [0 ⋯CG_i] be the concept grouping function that returns the index (concept group value) that an image belongs, where CG_i is a positive integer. 



1 We consider three concept grouping functions and apply them in images within Fig. <ref>.

    
  * Let cgf_poor: ℐ→{0, 1} return a simplified categorization based on the character of an image is considered economically disadvantaged, with the value having the following semantics.


    
  * 0: the person is not economically disadvantaged
    
  * 1: the person is economically disadvantaged

    

Then cgf_poor(img_1) = cgf_poor(img_2) = 1.
    


  * Let cgf_gender: ℐ→{0, 1, 2} return a simplified categorization based on the gender of an image character, with the value having the following semantics.




    
  * 0: female
    
  * 1: male
    
  * 2: other

    

Then cgf_gender(img_1) = cgf_gender(img_2) = 1. 
    


  * Let cgf_age: ℐ→{0, 1, 2} return a simplified categorization based on the seniority of the character within the image, with the value having the following semantics.


    
  * 0: child
    
  * 1: adult
    
  * 2: elderly

    

Then cgf_age(img_1) = 2 and cgf_age(img_2) = 0.









 §.§ Sequence-level Fairness



In the following, we establish the theoretical framework for defining fairness on an infinite sequence of images sharing a common characteristic. 


    Let  cgf_1 and cgf_2 be two concept grouping functions, and let ims  img_1 · img_2 ⋯∈ℐ^ω be the infinite sequence of images where ∀ i ∈ℕ: cgf_1 (img_i) = cg where cg ∈ [0 ⋯CG_1]. Then ims is fair with eventual appearance  for concept group 2 under cgf_1 evaluated to cg, abbreviated as ⟨cgf_2/cgf_1 ⇐  cg⟩ ◊-fair, if 


    ∀ k ∈ [0 ⋯CG_2]: ∃ m ≥ 1: cgf_2(img_m) = k




1
Let ims  img_1 · img_2 ⋯∈ℐ^ω be an infinite image sequence for depicting different economically disadvantaged characters, where Fig. <ref> shows the first 8 images. Therefore, ∀ i ∈ℕ: cgf_poor (img_i) = 1. 
We can conclude that ims is ⟨gender/cgf_poor⇐  1⟩ ◊-fair, as we can find all considered gender types. 


    
  * cgf_gender(img_3) = 0 (female)
    
  * cgf_gender(img_1) = 1 (male)
    
  * cgf_gender(img_6) = 2 (other)


In addition, ims is ⟨age/cgf_poor⇐  1⟩ ◊-fair, as we can find all considered age types. 


    
  * cgf_age(img_2) = 0 (child)
    
  * cgf_age(img_8) = 1 (adult)
    
  * cgf_age(img_3) = 2 (elderly)




As the definition utilizes infinite image sequences, one can go beyond fairness with eventual appearance by considering the average, minimum, or maximum distance of repeated occurrence of every concept group value. For instance, the following definition characterizes fairness by ensuring that the minimum distance of repeated occurrence is bounded by β for every possible concept group value.



    Let cgf_1 and cgf_2 be two concept grouping functions, and let ims  img_1· img_2 ⋯∈ℐ^ω be the infinite sequence of images where ∀ i ∈ℕ: cgf_1 (img_i) = cg where cg ∈ [0 ⋯CG_1]. Then ims is fair with β-bounded repeated appearance  for concept group 2 under cgf_1 evaluated to cg, abbreviated as ⟨cgf_2/cgf_1 ⇐  cg⟩ □◊_≤β-fair, if 

    ∀ k ∈ [0 ⋯CG_2]: 
    ∃ m: 1 ≤ m ≤β∧cgf_2(img_m) = k 
    ∧
    ∀ m_1 ≥ 1: (cgf_2(img_m_1) = k →
    ∃ m_2:  m_1 < m_2 ≤ m_1 + β:  cgf_2(img_m_2) = k)




The following lemmas provide a sound upper bound on the frequency difference under β-bounded repeated appearance fairness, as well as lower-bounding the smallest β value. 



Let cgf_2: ℐ→ [0 ⋯CG_2] be the concept grouping function, and ims ∈ℐ^ω be an infinite sequence of images. Given cg ∈ [0 ⋯CG_2], define ℱ(cg, ims) using Eq. <ref>. 

    ℱ(cg, ims) lim_n →∞|{m ≤ n : cgf_i(img_m) = cg}|/n


Assume that ims is ⟨cgf_2/cgf_1 ⇐  cg⟩ □◊_≤β-fair, then following condition holds.





    ∀ cg_x, cg_y ∈ [0 ⋯CG_2]: 
    |ℱ(cg_x, ims) - ℱ(cg_y, ims)| ≤ 1 - CG_2 + 1/β




 The extreme case occurs when the concept group value 0 has the highest frequency of occurrence (i.e., cg_x = 0) while the rest of concept group values 1, …, CG_2 have the lowest occurrence frequency. For each concept group value cg_y ∈ [1 ⋯CG_2] having the lowest frequency, it implies that in Eq. (<ref>), m_2 = m_1 + β, i.e., ℱ(cg_y, ims) has the smallest value of 1/β. Consequently, the frequency of ℱ(cg_x, ims) can at most be 1- (CG_2)ℱ(cg_y, ims)  = 1 -CG_2/β. Therefore, the frequency difference (if the limit exists) is bounded by (1 -CG_2/β) - 1/β = 1 - CG_2 + 1/β.




Let ims ∈ℐ^ω be ⟨cgf_2/cgf_1 ⇐  cg⟩ □◊_≤β-fair where cgf_2: ℐ→ [0 ⋯CG_2]. Then β≥CG_2 
 + 1.




    The smallest possible β_min occurs when concept group values occur in ims in a strictly round-robin fashion, implying that β_min = size([0 ⋯CG_2]) = CG_2 
 + 1. 







 §.§ Generator-level Fairness



Observe that an image sequence ims can be fair due to the explicit control of the input prompts given (i.e., p_1, p_2, …); it thus can not fully reflect the inherent limitation of the generator f. Therefore, we aim to consider the fairness of a generator, under the consideration where the input prompts p_1, p_2, … provide no hints on the concept group that fairness should be manifested. Before precisely characterizing the meaning of “hints”, we offer some examples to assist in understanding the idea. 


    
The following prompt sequences provide no hints on the gender (cgf_gender) and age (cgf_age)  information. 

    
  * p_1  "[Q] Please generate an image of a poor 
person."

    
  * p_2  "[Q] Please generate an image of a poor 
person, different from the previous ones."

    
  * ∀ i > 2, let p_i  p_2





The following prompts provide hints to bias the image generation of f towards a specific group based on the official demographic categorization used in the education statistics in the USA <cit.>.

    
    
  * [Q] Generate another image, where the person in the image should be "African American".
    
  * [Q] Generate another image, where the person in the image should have black skin.

    
  * [Q] Generate another image, where the person in the image should be within one of the commonly seen demographic groups in the USA, but should not have a looking like an Asian, white, Latino, or native American.





A prompt p ∈Σ^* is biased / non-neutral  subject to the concept group cgf_i(·), iff the following condition holds: 

    ∃ cg ∈ [0 ⋯CG_i]:  
    ∀ s_1, s_2 ∈Σ^*: cgf_i(f^img(s_1 · p)) = cgf_i(f^img(s_2 · p)) = cg




Intuitively, the definition of a biased prompt implies that by using prompt p in the generation process, one guarantees that the immediately generated image, when evaluated on the concept group cgf_i, always[Here we omit technical details, but one can also have relaxations such as having a probabilistic guarantee.] leads to manifesting concept group value cg. 
By clearly defining a biased prompt, we can now define the inherent fairness of a generator, which requires that when all input prompts are neural, fairness remains ensured. Def. <ref> characterizes eventual fairness, while it is a straightforward extension to characterize repeated fairness. 
    



    Let cgf_1 and cgf_2 be two concept grouping functions, and let f be the generator function. 
Then  f is inherently fair with eventual appearance for concept group 2 under cgf_1 evaluated to cg, abbreviated as ⟨cgf_2/cgf_1 ⇐  cg⟩ ◊-fair, when the following conditions hold:


    ∀ p_1, p_2, …∈Σ^*: (
    (∀ i > 0: 
       cgf_1 (f^img, i(p_i)) = cg )
       
    ∧
    
       (∀ i > 0: p_i  is not biased subject to cgf_2(·)))
    → (∀ k ∈ [0 ⋯CG_2]: ∃ m ≥ 1: cgf_2(f^img, m(p_m)) = k)




In Eq. (<ref>), the first conjunct before the implication (∀ i > 0: 
   cgf_1 (f^img, i(p_i)) = cg) characterizes the situation where all images being generated with the sequence of input prompts, when applying cgf_1(·), result in concept group value cg. The term f^img, i(p_i) follows the definition listed in Eq. (<ref>). The second conjunct demands the prompts to be not biased (following Def. <ref>). The right-hand side of the logical implication demands that fairness of eventual occurrence should hold in the generated image sequence, resembling the formulation in Def. <ref>. 





§ PRACTICAL CONSIDERATIONS





 §.§ Accessing Fairness on Finite Image Sequences



While the previously stated theoretical framework is based on infinite sequences of images, in practice, accessing fairness is commonly done on image sequences of finite length. In this situation, it is natural to change in Def. <ref> from ℐ^ω (infinite word) to ℐ^* (finite word) so that eventual appearance should be manifested in the finite image sequence. The problem occurs in definitions related to the repeated occurrence (e.g., Def. <ref>), where manifesting repeated occurrence on finite traces is impossible.[It is well known in the theory of linear temporal logic of finite traces <cit.> that the meaning of response property (i.e., □◊ in LTL) has different interpretations when defining infinite and finite traces.] On finite traces, defining fairness with repeated appearance requires an assumption on extrapolating what happens if the finite image sequence is further extended. 

For Def. <ref> on fairness with β-bounded repeated appearance, however, recall that bounded response ◊_≤βϕ in LTL over infinite words can be rewritten using the neXt (𝐗) operator, i.e., ϕ∨𝐗ϕ∨𝐗𝐗ϕ∨…∨𝐗^βϕ. To apply it in finite traces, the idea of the weak-next 𝐗_w operator as defined in LTL over finite traces <cit.> is useful, where 𝐗_wϕ holds automatically when considering being at the last position of the string (i.e., let π be a finite trace and len(π) returns the length of the trace. Then π, m 𝐗_wϕ  iff  (i)  m < len(π)-1 and π, m+1 ϕ, or   (ii)  m = len(π) -1). This is based on the belief that if we extend the trace by 1, it is possible that the next symbol can satisfy ϕ. This leads to the following modified definition.


    Let cgf_1 and cgf_2 be two concept grouping functions, and let ims  img_1· img_2 ⋯∈ℐ^* be the finite sequence of images where ∀ i ∈ℕ: cgf_1 (img_i) = cg where cg ∈ [0 ⋯CG_1]. Then ims is fair with β-bounded repeated appearance  for concept group 2 under cgf_1 evaluated to cg, abbreviated as ⟨cgf_2/cgf_1 ⇐  cg⟩ □◊_≤β-fair, iff (1) len(ims)> β, and (2) the condition characterized in Eq. (<ref>) holds.
    

    ∀ k ∈ [0 ⋯CG_2]: 
    ∃ m: 1 ≤ m ≤β∧cgf_2(img_m) = k 
    ∧
    ∀ m_1 ≥ 1: (cgf_2(img_m_1) = k →
    
    ((∃ m_2:  m_1 < m_2 ≤ m_1 + β:  cgf_2(img_m_2) = k)
    ∨
    
    m_1 + β > len(ims)
    ))




Comparing Eq. (<ref>) and Eq. (<ref>), the difference in the finite version lies in the disjunction (∨) of condition (m_1 + β > len(ims)), reflecting that if the occurrence m_1 is close to the end of the image sequence, it is impossible to see β subsequent images. Similar to the semantic of X_w, we opportunistically consider it can occur if the image sequence is prolonged. 






    Consider the finite image sequence as illustrated in Fig. <ref>, where let cgf_shape: ℐ→{0  (circle), 1  (other)} and 
    cgf_color: ℐ→{0  (white), 1  (yellow)}. Then the image sequence in Fig. <ref> is ⟨cgf_color/cgf_shape⇐  0⟩ □◊_≤ 6-fair. This is because the image sequence length is larger than 6, and for every color occurrence, the next occurrence occurs within a distance of 6. Note that for the final occurrence of “yellow” that makes m_1=8 in Eq. (<ref>), the second term in the disjunction holds as m_1 + β = 8 + 6 = 14 > len(ims) = 11. 








 §.§ Relative Intersectional Fairness



So far, the ⟨cgf_2/cgf_1 ⇐ cg⟩ ◊-fairness  have been used to ensure the presence of all concept group values when considering a single categorization with cgf_2. We can extend the concept to build fairness of manifesting fairness in criterion pairs ⟨cgf_x, cgf_y/cgf_w ⇐  cg⟩ and in criterion triplets ⟨cgf_x, cgf_y, cgf_z/cgf_w ⇐  cg⟩, where the definition immediately follows (e.g., Def. <ref>). As an example, consider the gender and age as two category groups, the extension on fairness in criterion pairs ⟨cgf_gender, cgf_age/cgf_w ⇐ cg⟩ then demands fairness to be observed in image sequences with all combinations defined by the following set { (cg_x, cg_y) } with cg_x ∈{female, male, other} and cg_y ∈{child, adult, elderly}.


    Let cgf_w, cgf_x and cgf_y be three concept grouping functions, and let ims  img_1 · img_2 ⋯∈ℐ^* be the finite sequence of images where ∀ i ∈ℕ: cgf_w (img_i) = cg where cg ∈ [0 ⋯CG_w]. Then ims is paired-fair with eventual appearance  for concept group x and y under cgf_w evaluated to cg, abbreviated as ⟨cgf_x, cgf_y/cgf_w ⇐  cg⟩ ◊-fair, if the following condition holds.

    ∀ k_1 ∈ [0 ⋯CG_x], k_2 ∈ [0 ⋯CG_y]:  
    ∃ m ≥ 1: cgf_x(img_m) = k_1 ∧cgf_y(img_m) = k_2




Given cgf_w and additional K concept grouping functions cgf_1, …, cgf_K, one can extend Def. <ref> and analogously define ⟨cgf_1, …, cgf_K/cgf_w ⇐  cg⟩ ◊-fairness, which demands that all combinations of concept group values should eventually appear. This leads to a concept similar to avoiding intersectional biases defined in the literature <cit.>. However, given K concept grouping functions with each having a binary assignment {0, 1}, it is well known that combinatorial explosion exists, meaning that there is a need to manifest 2^K assignments to achieve intersectional fairness.

Encountering this, we thus borrow the technique from k-way combinatorial testing <cit.> to provide a weaker form of intersectional fairness (relative intersectional fairness) whose satisfaction requires only a polynomially bounded number of images. Def. <ref> ensures that for every pair (2-way combinations) of concept group functions, all concept group value combinations are eventually manifested. The universal quantifier x, y ∈ [1 ⋯ K],  x ≠ y in Def. <ref> only selects pairs of concept group functions as the conditions to be satisfied. 


    Given cgf_w and additional K concept grouping functions cgf_1, …, cgf_K, let ims  img_1 · img_2 ⋯∈ℐ^* be the finite sequence of images where ∀ i ∈ℕ: cgf_w (img_i) = cg where cg ∈ [0 ⋯CG_w]. Then ims is all-paired-fair with eventual appearance  for concept groups [1 ⋯ K] under cgf_w evaluated to cg, abbreviated as ⟨∀_x,y ∈ [1 ⋯ K]cgf_x, cgf_y/cgf_w ⇐  cg⟩ ◊-fair, if the following condition holds.  

    ∀ x, y ∈ [1 ⋯ K],  x ≠ y: 
    ∀ k_1 ∈ [0 ⋯CG_x], k_2 ∈ [0 ⋯CG_y]:  
    ∃ m ≥ 1: cgf_x(img_m) = k_1 ∧cgf_y(img_m) = k_2


 







 §.§ Enforcing Fairness with Repeated Appearance



Finally, while previously stated definitions assume the prompts to be not biased (cf. Def. <ref>), one can also explicitly create prompts biased towards a specific concept group value to enforce fairness, where we focus on enforcing ⟨cgf_2/cgf_1 ⇐  cg⟩ □◊_≤β-fairness as characterized in Def. <ref>. 

Note that one trivial way is to explicitly control every prompt to manifest round-robin behavior. An example for cgf_2 being cgf_age(·) would be to enforce the generator to create the images strictly using the following ordering of values: “child”, “adult”, “elderly”. Our interest, however, is to aim for minimum interference. We aim to use only biased (enforcing) prompts when necessary. Algo. <ref> presents our fairness enforcement method.  

Initially (line 1), define an array c ranging from 0 to CG_2, with initial values set to β. c[i] tracks the deadline before the concept group value i shall manifest. The algorithm continues by using an infinite loop to extract prompts from the user (lines 2,3). The for-loop and the following condition (lines 4,5) try to detect if there are multiple concept group values whose deadline is approaching. When there exist k concept group values whose deadline equals k (line 5), it is then mandatory to use biased / non-neutral prompts to ensure one of the concept group values is selected in the corresponding image generation process, as reflected in lines 6 and 7. Note that the for-loop at line 4 iterates from k=CG_2 to 1 (not the other way round), as it is important to signal the issue as early as possible.  Finally, an image is produced (line 9), and for the corresponding concept group value cg, the counter c[cg] is reset to β (line 12) while counters of other values are subtracted by 1. 


    Fig. <ref> illustrates an example on how Algo. <ref> is applied to enforce fairness, where cgf_2:ℐ→ [0⋯ 3], with β=50. Initially, c[0]=c[1]=c[2]=c[3]=50. With the first prompt, enforcement is not triggered; as the first image has cgf_2(img_1) = 0, c[1],c[2],c[3] are set to 49 while c[1] is reset to 50. When the generator continuously produces images of Asians, it eventually leads to the situation c[1]=c[2]=c[3]=3, where the condition at line 5 of Algo. <ref> is enabled, implying the need to enforce fairness. Then, one of the concept group values is taken from random to be enforced, where in Fig. <ref>, the first value being taken equals 1 (Caucasian). 








§ EVALUATION





We have considered fairness on two image-based generative AI tools, namely ChatGPT 4.0 connected with DALL·E3 from OpenAI as well as GLM-4 from ZHIPU AI, where Fig. <ref> illustrates some of the image sequences produced by these tools when feeding neutral prompts similar to Ex. <ref>. For images of successful business leaders in the second row Fig. <ref>, the prompt resembles Ex. <ref> by only replacing the term “poor person” with “successful business leader”. We have drawn multiple image sequences using neutral prompts, where the length of each image sequence is at least 40. 



First, we observed that fairness is not universally enabled on all concepts in a generative AI model, as satisfaction can be conditional to certain concept group values. This confirms the appropriateness of our definition, which is always conditioned to a particular concept group value. 

    
  * (Different degree of gender fairness) When considering gender to be binary (male, female) based on the facial characteristics, for “successful business leader”, within all sequences, the minimum β value that satisfies Def. <ref> is tightly centered around 5. However, for “poor person”, female figures are substantially less presented[In our evaluation, we explicitly removed generated images where the subject can not be recognized with gender, as well as images with more characters because the generated image did not follow the instructions from the prompt.], reflecting the minimum β value for image sequences being between 13 and 20. 
    
  * (Different degree of demographic fairness) For demographics, when it comes to “successful business leader”, fairness with repeated appearance can be manifested, even for the concept group value “native American”, as demonstrated in the 11^th image at the second row of Fig. <ref>. This contrasts with the case of a “poor person”, where even fairness with eventual appearance can not be manifested due to missing images in the concept group value in some image sequences. 


Second, we observed that even when using the relative intersectional fairness criterion defined in Def. <ref>, generative AI models still struggle to include all combinations of pair-wise features. In our experiment, we generated multiple image sequences of length 80 using the GLM-4 model for “successful person”, where we considered four concept group functions including demographics, gender, occupation[We followed the definition of major groups by International Standard Classification of Occupations (ISCO) <https://www.ilo.org/public/english/bureau/stat/isco/docs/resol08.pdf>], and the character being fuller-figured. The prompt explicitly hints the generative AI model to consider diversities at least in these four aspects. 
We normalize the value by dividing it with ∑_ x ∈ [1 ⋯ K]∑_y ∈ [1 ⋯ K], y> x (CG_x +1)(CG_y +1) in Def. <ref>, as the denominator represents the number of all-paired combinations needed. The tendency increase is illustrated in Fig. <ref>, where each line corresponds to the behavior of one image sequence. With the maximum possible value being 1, we observed that the coverage is always below 0.4. Apart from one sequence, the coverage largely saturates after 25 images (reflected as a horizontal line), implying that the subsequent generated images highly resemble the first 25 images regarding concept group values (e.g., repeating doctors). Our results suggest a huge potential for the GLM-4 generative model to improve intersectional fairness in its image generation process.

Finally, we have also implemented the enforcement mechanism in Algo. <ref> to guarantee fairness, where Fig. <ref> illustrates a qualitative example: Due to β being set to 3, the algorithm forces the model to construct the fourth image (img_4) with a male-looking figure by annotating a prompt “The person has a strong   male looking” at the end of the neutral prompt. 

















§ CONCLUDING REMARKS




Our formal approach to fairness in generative AI uniquely defines fairness through the lens of infinite sequences, allowing for a dynamic assessment of fairness over time. 
By distinguishing between the fairness demonstrated in generated sequences and the inherent fairness of the AI system, we have established a comprehensive method that recognizes the nuanced nature of fairness as conditioned by specific concepts. 
In addition, our formal approach addresses the challenge of intersectional fairness through combinatorial testing, providing a scalable method for dealing with the combinatorial explosion in category combinations. 
This is critical to ensuring that our fairness measures remain effective even as the complexity of AI systems and the diversity of fairness dimensions increase.
Initial experimental evaluations show that inherent biases can be effectively managed with our fairness enforcement techniques. 
Designed to anticipate and mitigate fairness violations, these techniques ensure that generative AI maintains balance across gender or demographic groups without undue interference.


A critical path forward is the practical application of our enforcement techniques within large organizations to ensure that fairness can be actively managed at scale. 
 Another direction for future work is to extend fairness
 definitions to an "average arrival view" that focuses on the average time between concept occurrences.
  Finally, conducting long-term studies on the impacts of fairness interventions would inform the continuous refinement of our approaches.





10
	
	alshiekh2018safe
	Mohammed Alshiekh, Roderick Bloem, Rüdiger Ehlers, Bettina Könighofer,
	Scott Niekum, and Ufuk Topcu, `Safe reinforcement learning via shielding', in
	AAAI Conference on Artificial Intelligence, volume 32, (2018).
	
	buolamwini2018gender
	Joy Buolamwini and Timnit Gebru, `Gender shades: Intersectional accuracy
	disparities in commercial gender classification', in Conference on
		Fairness, Accountability, and Transparency (FAT), pp. 77–91. PMLR, (2018).
	
	buyl2024inherent
	Maarten Buyl and Tijl De Bie, `Inherent limitations of AI fairness', Communications of the ACM, 67(2),  48–55, (2024).
	
	chang2023survey
	Yupeng Chang, Xu Wang, Jindong Wang, Yuan Wu, Linyi Yang, Kaijie Zhu, Hao Chen,
	Xiaoyuan Yi, Cunxiang Wang, Yidong Wang, et al., `A survey on evaluation of
	large language models', ACM Transactions on Intelligent Systems and
		Technology, (2023).
	
	choi2020fair
	Kristy Choi, Aditya Grover, Trisha Singh, Rui Shu, and Stefano Ermon, `Fair
	generative modeling via weak supervision', in International Conference
		on Machine Learning (ICML), pp. 1887–1898. PMLR, (2020).
	
	crenshaw2013demarginalizing
	Kimberlé Crenshaw, `Demarginalizing the intersection of race and sex: A
	black feminist critique of antidiscrimination doctrine, feminist theory and
	antiracist politics', in Feminist Legal Theories,  23–51, Routledge,
	(2013).
	
	de2013linear
	Giuseppe De Giacomo, Moshe Y Vardi, et al., `Linear temporal logic and linear
	dynamic logic on finite traces.', in International Joint Conference on
		Artificial Intelligence (IJCAI), volume 13, pp. 854–860, (2013).
	
	ernst2023bias
	Jasmina S Ernst, Sascha Marton, Jannik Brinkmann, Eduardo Vellasques, Damien
	Foucard, Martin Kraemer, and Marian Lambert, `Bias mitigation for large
	language models using adversarial learning', in AEQUITAS Workshop on
		Fairness and Bias in AI, (2023).
	
	fabbrizzi2022survey
	Simone Fabbrizzi, Symeon Papadopoulos, Eirini Ntoutsi, and Ioannis
	Kompatsiaris, `A survey on bias in visual datasets', Computer Vision and
		Image Understanding, 223,  103552, (2022).
	
	ferrara2023fairness
	Emilio Ferrara, `Fairness and bias in artificial intelligence: A brief survey
	of sources, impacts, and mitigation strategies', Sci, 6(1),  3,
	(2023).
	
	fionda2018ltl
	Valeria Fionda and Gianluigi Greco, `LTL on finite and process traces:
	Complexity results and a practical reasoner', Journal of Artificial
		Intelligence Research, 63,  557–623, (2018).
	
	frankel2020fair
	Eric Frankel and Edward Vendrow, `Fair generation through prior modification',
	Advances in Neural Information Processing Systems (NeurIPS), 31,
	(2018).
	
	gradel2003automata
	Erich Grädel, Wolfgang Thomas, and Thomas Wilke, Automata, logics, and
		infinite games: a guide to current research, volume 2500, Springer, 2003.
	
	he2021unlearn
	He He, Sheng Zha, and Haohan Wang, `Unlearn dataset bias in natural language
	inference by fitting the residual', in Workshop on Deep Learning
		Approaches for Low-Resource Natural Language Processing, DeepLo@ EMNLP-IJCNLP
		2019, pp. 132–142. ACL, (2021).
	
	huang2023bias
	Dong Huang, Qingwen Bu, Jie Zhang, Xiaofei Xie, Junjie Chen, and Heming Cui,
	`Bias assessment and mitigation in llm-based code generation', arXiv
		preprint arXiv:2309.14345, (2023).
	
	kearns2018preventing
	Michael Kearns, Seth Neel, Aaron Roth, and Zhiwei Steven Wu, `Preventing
	fairness gerrymandering: Auditing and learning for subgroup fairness', in
	International Conference on Machine Learning (ICML), pp. 2564–2572.
	PMLR, (2018).
	
	kiritchenko2018examining
	Svetlana Kiritchenko and Saif Mohammad, `Examining gender and race bias in two
	hundred sentiment analysis systems', in Joint Conference on Lexical and
		Computational Semantics (*SEM), pp. 43–53, (2018).
	
	kirk2021bias
	Hannah Rose Kirk, Yennie Jun, Filippo Volpin, Haider Iqbal, Elias Benussi,
	Frederic Dreyer, Aleksandar Shtedritski, and Yuki Asano, `Bias
	out-of-the-box: An empirical analysis of intersectional occupational biases
	in popular generative language models', Advances in Neural Information
		Processing Systems (NeurIPS), 34,  2611–2624, (2021).
	
	li2019repair
	Yi Li and Nuno Vasconcelos, `REPAIR: Removing representation bias by dataset
	resampling', in IEEE/CVF Conference on Computer Vision and Pattern
		Recognition (CVPR), pp. 9572–9581, (2019).
	
	li2023survey
	Yingji Li, Mengnan Du, Rui Song, Xin Wang, and Ying Wang, `A survey on fairness
	in large language models', arXiv preprint arXiv:2308.10149, (2023).
	
	liang2021towards
	Paul Pu Liang, Chiyu Wu, Louis-Philippe Morency, and Ruslan Salakhutdinov,
	`Towards understanding and mitigating social biases in language models', in
	International Conference on Machine Learning (ICML), pp. 6565–6576.
	PMLR, (2021).
	
	limisiewicz2023debiasing
	Tomasz Limisiewicz, David Mareček, and Tomáš Musil, `Debiasing
	algorithm through model adaptation', in International Conference on
		Learning Representations (ICLR), (2023).
	
	race
	NECS.
	Definitions for new race and ethnicity categories.
	<https://nces.ed.gov/ipeds/report-your-data/race-ethnicity-definitions>,
	2024.
	Accessed: 2024.03.03.
	
	nie2011survey
	Changhai Nie and Hareton Leung, `A survey of combinatorial testing', ACM
		Computing Surveys (CSUR), 43(2),  1–29, (2011).
	
	pnueli1977temporal
	Amir Pnueli, `The temporal logic of programs', in Annual Symposium on
		Foundations of Computer Science (SFCS), pp. 46–57. IEEE, (1977).
	
	ramezani2023knowledge
	Aida Ramezani and Yang Xu, `Knowledge of cultural moral norms in large language
	models', arXiv preprint arXiv:2306.01857, (2023).
	
	ranaldi2023trip
	Leonardo Ranaldi, Elena Sofia Ruzzetti, Davide Venditti, Dario Onorati, and
	Fabio Massimo Zanzotto, `A trip towards fairness: Bias and de-biasing in
	large language models', arXiv preprint arXiv:2305.13862, (2023).
	
	rombach2022high
	Robin Rombach, Andreas Blattmann, Dominik Lorenz, Patrick Esser, and Björn
	Ommer, `High-resolution image synthesis with latent diffusion models', in
	IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR),
	pp. 10684–10695, (2022).
	
	sheppard2023subtle
	Brooklyn Sheppard, Anna Richter, Allison Cohen, Elizabeth Allyn Smith, Tamara
	Kneese, Carolyne Pelletier, Ioana Baldini, and Yue Dong, `Subtle misogyny
	detection and mitigation: An expert-annotated dataset', arXiv preprint
		arXiv:2311.09443, (2023).
	
	tan2020improving
	Shuhan Tan, Yujun Shen, and Bolei Zhou, `Improving the fairness of deep
	generative models without retraining', arXiv preprint arXiv:2012.04842,
	(2020).
	
	tan2019assessing
	Yi Chern Tan and L Elisa Celis, `Assessing social and intersectional biases in
	contextualized word representations', Advances in Neural Information
		Processing systems (NeurIPS), 32, (2019).
	
	tao2023auditing
	Yan Tao, Olga Viberg, Ryan S Baker, and Rene F Kizilcec, `Auditing and
	mitigating cultural bias in llms', arXiv preprint arXiv:2311.14096,
	(2023).
	
	teo2024measuring
	Christopher Teo, Milad Abdollahzadeh, and Ngai-Man Man Cheung, `On measuring
	fairness in generative models', Advances in Neural Information
		Processing Systems (NeurIPS), 36, (2023).
	
	teo2023fair
	Christopher TH Teo, Milad Abdollahzadeh, and Ngai-Man Cheung, `Fair generative
	models via transfer learning', in AAAI Conference on Artificial
		Intelligence, volume 37, pp. 2429–2437, (2023).
	
	tommasi2017deeper
	Tatiana Tommasi, Novi Patricia, Barbara Caputo, and Tinne Tuytelaars, `A deeper
	look at dataset bias', Domain Adaptation in Computer Vision
		Applications,  37–55, (2017).
	
	torralba2011unbiased
	A Torralba and AA Efros, `Unbiased look at dataset bias', in IEEE/CVF
		Conference on Computer Vision and Pattern Recognition (CVPR), pp.
	1521–1528, (2011).
	
	ungless2022robust
	Eddie Ungless, Amy Rafferty, Hrichika Nag, and Björn Ross, `A robust bias
	mitigation procedure based on the stereotype content model', in Workshop
		on Natural Language Processing and Computational Social Science (NLP+ CSS),
	pp. 207–217, (2022).
	
	vaswani2017attention
	Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones,
	Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin, `Attention is all you
	need', Advances in Neural Information Processing Systems (NeurIPS),
	30, (2017).
	
	zhang2023chatgpt
	Jizhi Zhang, Keqin Bao, Yang Zhang, Wenjie Wang, Fuli Feng, and Xiangnan He,
	`Is chatgpt fair for recommendation? evaluating fairness in large language
	model recommendation', in ACM Conference on Recommender Systems
		(RecSys), pp. 993–999, (2023).
	




