Paper deep dive
Statistical attribute alignment for black-box generative AI via output post-processing
Kevin Jiang, Morgane Austern, Edgar Dobriban, Jason M. Klusowski
Intelligence
Status: not_run | Model: - | Prompt: - | Confidence: 0%
Entities (0)
Relation Signals (0)
No relation signals yet.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Generative AI systems are increasingly used, but aligning their outputs with user requirements poses a continuing challenge. Here, we aim to ensure that the distribution of an attribute of an AI-generated output aligns with a user-specified target. This is motivated by examples such as fairness, where we want to ensure that a protected attribute (e.g., gender, race, or age categories) follows a desired distribution, and synthetic data generation, where we want the generated data to be representative of a target distribution. We study the practically important black-box access setting, where a user can repeatedly query a generative AI model. The goal is to return $m\ge 1$ outputs whose joint attribute distribution is as close as possible to this target. For both exact and approximate alignment, we develop algorithms that minimize the expected number of queries to the generator, and we further demonstrate their optimality as the number of requested outputs $m \rightarrow \infty$. Experiments on text-to-image generation and geocoded persona generation tasks show that our post-processing algorithms improve statistical attribute alignment, complementing prompting-based interventions.
Tags
Links
- Source: https://arxiv.org/abs/2609.31607v1
- Canonical: https://arxiv.org/abs/2609.31607v1
Trouble viewing inline? Open PDF directly →
Full Text
250,106 characters extracted from source content.
Expand or collapse full text
Statistical attribute alignment for black-box generative AI via output post-processing Kevin Jiang Morgane Austern Affiliation: Edgar Dobriban Jason M. Klusowski September 25, 2026 Abstract Generative AI systems are increasingly used, but aligning their outputs with user requirements poses a continuing challenge. Here, we aim to ensure that the distribution of an attribute of an AI-generated output aligns with a user-specified target. This is motivated by examples such as fairness, where we want to ensure that a protected attribute (e.g., gender, race, or age categories) follows a desired distribution, and synthetic data generation, where we want the generated data to be representative of a target distribution. We study the practically important black-box access setting, where a user can repeatedly query a generative AI model. The goal is to return m≥1m≥ 1 outputs whose joint attribute distribution is as close as possible to this target. For both exact and approximate alignment, we develop algorithms that minimize the expected number of queries to the generator, and we further demonstrate their optimality as the number of requested outputs m→∞m→∞. Experiments on text-to-image generation and geocoded persona generation tasks show that our post-processing algorithms improve statistical attribute alignment, complementing prompting-based interventions. 1 Introduction In recent years, generative artificial intelligence (genAI) models have seen increasing adoption across various domains such as text and image generation, code generation, and decision planning (Bommasani et al., 2021; Brown et al., 2020; Ramesh et al., 2022). An important challenge is to align their outputs with the requirements of a particular application. Alignment encompasses several objectives, including following instructions, reflecting human preferences, and satisfying safety or value constraints; see the recent surveys Ji et al. (2025); Pan et al. (2025). Influential approaches include reinforcement learning from human preferences (Christiano et al., 2017), its application to instruction-following language models (Ouyang et al., 2022), constitutional AI based on principle-guided model feedback (Bai et al., 2022), and direct preference optimization (Rafailov et al., 2023). However, despite great progress, there are a variety of challenges that remain in ensuring alignment. For instance, despite their impressive capabilities, models are known to learn historical and representational biases present in their training data, leading to systematic disparities along protected attributes such as race, gender, and age (Bolukbasi et al., 2016; Buolamwini and Gebru, 2018; Bender et al., 2021). These biases can raise concerns, particularly where generative models are deployed in public-facing settings (Barocas et al., 2023; Mehrabi et al., 2021) or used to generate synthetic data for training downstream models and estimators (Wyllie et al., 2024). In this work, we study one particular challenge within the broader alignment landscape, which we term statistical attribute alignment (SAA): ensuring that the distribution of designated categorical attributes in generated outputs agrees with a user-specified target. The attributes may be selected covariates or response labels, and the target may describe a desired population or sampling design. Even a model aligned to instructions or preferences may generate attribute distributions that differ from those required by a particular user. Fairness and synthetic data generation provide two motivating examples. In a use case aiming to ensure fairness, the attributes are categorical covariates designated as protected, such as gender, race, or age categories, and the target specifies their desired representation (Barocas et al., 2023). Matching this target addresses a distributional aspect of fairness. As we will discuss later, the choice of protected attributes and the target is application-dependent. Generative models also provide a potential source of data for statistical analysis, model training, and evaluation, especially when collecting or annotating real observations is costly. Synthetic data have a long history in statistics, including the release of synthetic microdata through multiple imputation (Rubin, 1993; Raghunathan et al., 2003). Modern generative models have expanded their use in data augmentation; see Chen et al. (2024b); Mumuni et al. (2024) for surveys and Abdel-Azim et al. (2026) for a recent review. AI-generated data may not match the desired distribution, in which case additional methods are required to correct such biases, see e.g., Angelopoulos et al. (2023); Bashari et al. (2025b); Bashari et al. (2025a), etc. Our focus is on constructing the synthetic sample itself with a specified joint attribute distribution. For example, a synthetic dataset for auditing a face recognition system should reflect the intended audited population. A variety of methods for aligning AI models have been developed. These methods may intervene on the training data distribution, training and generation procedure, prompts, or outputs. Their requirements vary with the available model access. Methods with access to model internals can modify the architecture, training procedure, or generation dynamics (Xu et al., 2018; Yu et al., 2020; Choi et al., 2020; Rajabi and Garibay, 2022; Teo et al., 2024b; Teo et al., 2024a; Friedrich et al., 2025, see for instance), while black-box and training-free methods (see e.g., Pan et al. (2025)) only require that a user can sample from the model without requiring additional information such as model weights. Black-box access can be further divided based on the place of intervention, with input-side methods adjusting natural-language prompts (Zhao et al., 2021; Bansal et al., 2022; Neumann et al., 2025) and output-side or post-processing algorithms operating on the generated outputs, for example via filtering and runtime monitoring (Cano et al., 2025; Cheng et al., 2025). Here we focus on this black-box model access setting. This access mode is particularly important because many frontier models are distributed primarily through hosted web interfaces and APIs rather than as downloadable model weights. They may be unavailable for local deployment, and serving models at this scale can require substantial computational resources.11 1 White- and black-box methods can be combined and used in tandem (Schick et al., 2021; Cohen and Saabni, 2025; Azam and Akhtar, 2025; Gallegos et al., 2025, see, e.g.,). Within this setting, we select m≥1m≥ 1 generated outputs so that their joint attribute distribution aligns with a user-specified target.22 2 We target the joint law of the returned attributes, rather than only their marginal proportions. For a product target, this retains the sampling variation and dependence structure of independently sampled outputs. This distinction is useful both for representation across repeated requests and for synthetic datasets used to compute statistics involving several observations, as illustrated by the pairwise audit task in Section 5.2.3. The attributes are categorical and may be covariates (e.g., protected attributes such as gender or race) or response labels (e.g., whether a tumor is benign or malignant). This approach also allows practitioners to adapt the attribute distribution of a model previously aligned to a different target, without retraining or fine-tuning the model. Moreover, under black-box access, we do not assume knowledge of the source rates, or rates at which the attributes are generated. For example, when asking a text-to-image model to “Generate an image of a doctor”, one typically does not know the true rates at which an image of a male or female doctor is generated. These source rates may be different than what a practitioner or user wants (e.g., a uniform distribution over genders). When the outputs of a black-box genAI method do not match well with the target distribution, we aim to post-process the outputs to bring them closer. Since the source rates are unknown with black-box access, we will primarily be interested in developing source-rate-free post-processing methods which do not assume knowledge of these rates. Our strategy will be to query the model multiple times and carefully sample a subset of outputs so that the resulting probability law of the returned attributes is close to a user-specified target distribution. Block and Polyanskiy (2023) consider a similar approach to obtaining a single sample whose law approximates a target distribution—however, their rejection sampling construction requires access to the likelihood ratio, which depends on the unknown source rates. Additional related work is discussed in Section A.1. We begin by defining our strictest notion of statistical attribute alignment, called universal exactness. This requires the law of the attributes returned by a post-processing algorithm to exactly coincide with the target distribution. We then show that a coupon collector type algorithm, called random demand coupon collector (RDC), is source-rate-free, universally exact and minimizes the expected number of calls to the model among universally exact source-rate-free algorithms, up to first-order terms as the number of requested outputs m→∞m→∞. Universally exact algorithms often require many model calls, especially when there are attributes that occur rarely (see Theorem 8 for a formal statement). Consequently, we relax universal exactness by allowing approximate statistical attribute alignment. In particular, we introduce statistical alignment discrepancy as a statistical distance between the attribute law of the returned outputs and the target distribution. We then show that a variant of the RDC algorithm, called thresholded anytime RDC (TA-RDC), is source-rate-free and can achieve any user-specified level of statistical alignment discrepancy. When the target distribution is a product law and discrepancy is measured by forward KL divergence, we additionally show TA-RDC is first-order optimal: among source-rate-free algorithms with the same control on the sampling discrepancy, it minimizes the number of expected model calls up to first-order terms as the number of requested outputs m→∞m→∞. Synthetic data augmentation also motivates the count-conditional alignment criterion underlying our approximate algorithms. A practitioner using synthetic data for augmentation often selects examples from a single generated dataset, whose attribute counts constrain the samples that can be returned. The attribute law underlying statistical alignment discrepancy averages over possible realizations of these counts, so good overall alignment can conceal poor alignment for individual datasets. We therefore introduce a count-conditional alignment criterion that measures discrepancy given the observed attribute counts, and develop an algorithm that minimizes it for every realized count vector. This criterion both provides an interpretable objective for synthetic dataset curation and an upper bound on the statistical alignment discrepancy (Remarks 15 and A.4). Figure 1 gives a high-level view of our black-box post-processing approach. The user specifies a desired distribution over attributes and then queries a black-box generator to obtain a candidate batch of outputs. Since a finite batch of samples may not contain the target attributes in the desired amounts, our procedures select from the available candidates so that the returned outputs match the target distribution as closely as possible. Figure 1: High-level illustration of statistical attribute alignment via black-box output post-processing, using demographic attributes of generated headshots as an example. A user queries a black-box generator to form an annotated candidate batch. A black-box post-processing method then filters the candidate batch by selecting outputs that match a user-specified target distribution (e.g., uniform) as closely as possible, subject to what was observed in the batch. We illustrate our methods in a variety of generative AI tasks, ranging from text-to-image generation with multimodal AI models (HiDream-O1-Image, Qwen-Image-2512, Flux-2-dev) to text generation with a frontier language model (GPT-5.5). We argue that input-side interventions alone need not solve the problem. For example, demographic hard prompts, which directly request a protected attribute, can fail, because the models do not follow instructions and the realized attribute may differ from the requested one. As post-processing algorithms, our methods, such as RDC and TA-RDC, can still substantially improve alignment with the target attribute distribution in this setting. We further illustrate the use of synthetic datasets in a pairwise audit for face recognition systems. In this setting, matching a target joint law over attributes can yield more accurate estimates of downstream quantities, such as the false-match rate, than matching marginal proportions alone. 2 Problem setup For a prompt x∈x , a generative model P induces a conditional distribution P(⋅∣x)P(· x) over outputs y∈y . For instance, x could be a textual prompt such as “Generate an image of a doctor,” while Y could be the generated image. We assume only black-box sampling access to the generative model (such as through the web or APIs), meaning that for any x, we can sample Y∼P(⋅∣x)Y P(· x), but not directly access the internals of the model P. An annotator ϕ:→φ:Y then maps outputs to a discrete set of attribute classes A. These may be covariate or response categories in a synthetic data application. In the fairness setting, they correspond to protected attributes; for instance, in human images they may describe perceived race, gender, or age. For notational convenience, identify A with [k]=1,…,k[k]=\1,…,k\ after relabeling. Our algorithms aim to align the joint distribution over attributes with a user-specified target for any given prompt x by repeatedly querying the model. When prompting the model and annotating the outputs, the attributes follow a certain distribution, which we refer to as the source rates. Before querying the model, these are unknown to the users. They involve the randomness induced by sampling Y∼P(⋅∣x)Y P(· x) from the model, and are defined as pi≔pi(x)≔PrY∼P(⋅∣x)(ϕ(Y)=i),i∈.p_i p_i(x) _Y P(· x) (φ(Y)=i ), i . (1) We collect them into the vector p≔p(x)≔(pi)i∈Δ||−1p p(x) (p_i)_i ∈ ^|A|-1. These probabilities may differ from the target population or sampling design. In fairness applications, they might reflect undesirable historical biases learned by the model P. For instance, some races, genders, or ages might be unduly overrepresented in the generated images. Let the target joint law ν∈Δ(m)ν∈ (A^m) be a probability law over sequences of attributes. In the important special case where ν is a product law, let the target rates be q≔(qi)i∈Δ||−1q (q_i)_i ∈ ^|A|-1 (e.g., the uniform distribution qi=1/k,∀i∈[k]q_i=1/k,~∀ i∈[k]) so that ν=q⊗mν=q m.33 3 The setting where we are interested in aligning the distribution over a subset of attributes ′⊆A is subsumed by putting zero probability mass on the indices ∖′A associated with q. In particular, if the generative model has a nonzero chance of outputting an attribute that does not belong to ′A , we can append a category named other\ other\ to ′A so that ′⊂′⊔other=:A \ other\=:A and put zero probability mass on its associated index in q. These probabilities are set by the user according to the application, for example to reflect a target population or a desired demographic composition. They could also depend on the input x, but we will typically only consider the simpler case when they do not. A prototypical example might be to require that genders appear with equal probability when generating images of a particular occupation, such as doctors. In synthetic data generation, q may instead encode the prevalence of response attributes or covariate strata in a specified population. The specific way to set these probabilities is highly context-dependent (Choi et al., 2020; De Simone et al., 2023, see e.g.,). Our goal is to develop algorithms that apply regardless of the specific user choice of these probabilities, and we do not take a position about what specific choices are more or less desirable. In addition, we are aiming to preserve the distribution given the attributes. For example, when we output an image of a female physician, we want this image to follow the same distribution as when it is generated from the original model (given the original output being a female physician). This preserves within-attribute variation while changing the attribute distribution. The class of black-box post-processing algorithms we consider involves two forms of sampling: model calls, i.e., sampling from the conditional distribution P(⋅∣x)P(· x), and filtering among the generated outputs, involving additional randomness. Sampling from the model is usually more expensive, because it may require paying a fee to the model provider. To clearly distinguish these two forms of sampling, we introduce the following terminology. Definition 1 (M- and E-sampling). For fixed x, a model sample or M-sample is a query to the generative model which produces an output Y∼P(⋅∣x)Y P(· x), and hence an induced attribute A=ϕ(Y)A=φ(Y). An exogenous sample or E-sample is any randomization that does not require querying P and is independent of future M-samples, conditional on the current algorithmic history; e.g., drawing a uniform random variable U∼Unif[0,1]U [0,1] or a random index I∈I as I∼QI Q. A black-box post-processing algorithm may interweave M-sampling and E-sampling. More formally, we consider the following class of algorithms. Definition 2 (Black-box post-processing algorithms). Fix the number m≥1m≥ 1 of outputs to produce. Black-box post-processing algorithms Algm:×→m Alg_m:P×X ^m—whose totality we denote by m A_m— take as input a generative model P accessible through sampling. For any input query x, such an algorithm sequentially queries the generative model to observe outcomes Y1,…,YN∼i.i.d.P(⋅∣x)Y_1,…,Y_N i.i.d. P(· x) until a finite random number N of M-samples has been obtained, where N≥mN≥ m a.s. and N is a stopping time with respect to the generated samples and any pre-output E-sampling. This produces annotated attributes At≔ϕ(Yt)∈,1≤t≤NA_t φ(Y_t) ,~1≤ t≤ N with law A1…AN∼i.i.d.Categorical(p)A_1… A_N i.i.d. Categorical(p)44 4 We discuss the setting with a noisy annotator in Section 6.. The algorithm may then perform arbitrary computations, including any number of E-samples, to return a sample (Y~1,…,Y~m)( Y_1,…, Y_m) of size m chosen without replacement from the observed M-samples, with associated annotated attributes A~j≔ϕ(Y~j),1≤j≤m A_j φ( Y_j),1≤ j≤ m. If the algorithm Algm Alg_m does not use knowledge about the source rates p, then we further call it a source-rate-free black-box post-processing algorithm, and denote the totality of such algorithms as mo⊂m A_m^o⊂ A_m. The post-processing algorithm Algm∈m Alg_m∈ A_m induces a distribution over the annotations of its final outputs PAlgm(A~=a~∣x)≔Pr(A~1=a1,…,A~m=am∣x) P_ Alg_m( A= a x) ( A_1=a_1,…, A_m=a_m x) (2) for (a1,…,am)∈m(a_1,…,a_m) ^m. We call this distribution the output attribute law of Algm Alg_m. The conditional probability integrates over every algorithmic random variable not determined by the input prompt x, including any M-sampling to obtain outcomes Y1,…,YNY_1,…,Y_N as well as any E-sampling performed before and after the outcomes are realized. In practice, M-sampling acts as the computational bottleneck. We thus measure the efficiency of these post-processing algorithms through the expected number of calls to the black-box model, which we call the M-cost. Although the source rates are assumed to be unknown, the M-cost itself may depend on the source and target rates. Definition 3 (M-cost). The (source-rate pointwise) M-cost of Algm∈m Alg_m∈ A_m is the expected number of calls to the model, defined as mAlgm(p)≡mAlgm(p,q)≔[N]C_m Alg_m(p) _m Alg_m(p,q) [N] computed over all problem randomness. Goal and target joint law. Since we want to handle black-box generative models which can only be accessed through sampling, we do not assume the source rates p are known. Thus, our primary goal is to find source-rate-free black-box post-processing algorithms Algm∈mo Alg_m∈ A_m^o whose output attribute law (cf. Equation 2) either approximates or is exactly a user-specified target joint law ν over the space of attribute sequences m=[k]mA^m=[k]^m. For example, this may be the law of an i.i.d. sample of size m from q, so that ν=q⊗mν=q m. Among these algorithms that attain the target law exactly or for a specified level of approximation (we later specify how to quantify approximation error in Section 4), we further seek to characterize those that minimize the M-cost. 3 Exact statistical attribute alignment We begin by defining the class of black-box post-processing algorithms that attain the target law exactly for arbitrary source rates p∈Δk−1p∈ ^k-1. Throughout this section, assume the support condition supp(ν)⊆(supp(p))msupp(ν) (supp(p))^m unless otherwise explicitly stated. Definition 4 (Universal exactness). A post-processing algorithm Algm∈m Alg_m∈ A_m is universally exact for the target joint law if its output attribute law PAlgm(A~=a~∣x)=ν(a~)P_ Alg_m( A= a x)=ν( a) (cf. Equation 2) for every source rate p satisfying supp(ν)⊆(supp(p))msupp(ν) (supp(p))^m. Let m(ν)⊂m A_m(ν)⊂ A_m denote the class of universally exact algorithms with finite M-cost, and mo(ν)⊂m(ν) A_m^o(ν)⊂ A_m(ν) the subclass of those algorithms that are source-rate-free. For t≥0t≥ 0, define the source count process C→(t) C(t) and its feasible support Ωt _t by Ci(t)=∑s=1t1As=i,Ωt=a→∈[k]m:#j∈[m]:aj=i≤Ci(t),∀i∈[k].C_i(t)= _s=1^t1\A_s=i\, _t= \ a∈[k]^m:\#\j∈[m]:a_j=i\≤ C_i(t),∀ i∈[k] \. (3) A black-box post-processing algorithm selects m outputs from the first t≥mt≥ m queries and must thus return an attribute sequence in Ωt≡Ωm(C→(t)) _t≡ _m( C(t)). The random demand coupon collector (RDC) algorithm is a source-rate-free algorithm that first samples a target attribute sequence from the target joint law and then M-samples until the target sequence enters the feasible support. In other words, it repeatedly M-samples until the stopping time Tν⋆≔inft≥m:A→⋆∈ΩtT_ν \t≥ m: A ∈ _t\; see Algorithm 1. Algorithm 1 Random Demand Coupon Collector (RDC) 0: Output size m, target joint law ν on [k]m[k]^m, annotator ϕφ. 0: Returned outputs (Y~1,…,Y~m)( Y_1,…, Y_m). 1: E-sample A→⋆∼ν A ν. 2: Query M-samples and construct the feasible support Ωt _t as in Equation 3 until the stopping time Tν⋆≔inft≥m:A→⋆∈Ωt.T_ν \t≥ m: A ∈ _t\. 3: return outputs (Y~1,…,Y~m)( Y_1,…, Y_m) with attribute sequence A→⋆ A , selected uniformly without replacement within each attribute from (Y1,…,YTν⋆)(Y_1,…,Y_T_ν ). Theorem 5 (Exact source-rate-free unconditional sampling). RDC is a source-rate-free black-box post-processing algorithm that terminates almost surely and is universally exact. The proof is given in Section A.8.1. RDC is source-rate-free as it does not use knowledge of the source rates p, and it is universally exact by construction of its random stopping time Tν⋆T_ν . Denote the pointwise M-cost of the RDC algorithm mRDC(p,ν)=p[Tν⋆]C_m^RDC(p,ν)=E_p[T_ν ] and the pointwise optimal universal cost for source-rate-free algorithms as muniv(p,ν)=infAlgm∈mo(ν)p[N].C_m^univ(p,ν)= _Alg_m∈ A_m^o(ν)E_p[N]. By definition, Cmuniv(p,ν)≤mRDC(p,ν)C_m^univ(p,ν) _m^RDC(p,ν). In the setting with a single returned output m=1m=1, it turns out that RDC is optimal. Theorem 6 (Exact optimality for one returned output). For m=1m=1, 1univ(p,ν)=1RDC(p,ν)=∑i∈supp(ν)νi/piC_1^univ(p,ν)=C_1^RDC(p,ν)= _i∈ supp(ν) _i/p_i. Thus, for m=1m=1, RDC is pointwise optimal at every source rate satisfying supp(ν)⊆(supp(p))msupp(ν) (supp(p))^m. For general m≥1m≥ 1, RDC is, in general, not optimal, but satisfies the following bound instead. For j∈[m]j∈[m] and i∈[k]i∈[k], let νj(i)≔νa→∈[k]m:aj=i _j(i) ν\ a∈[k]^m:a_j=i\ be the probability that the jjth coordinate of an attribute sequence A→∼ν A ν belongs to attribute i. Theorem 7 (Universal source-rate-free lower bound and RDC upper bound). We have mRDC(p,ν)≤muniv(p,ν)+(∑i∈supp(p)(∑j=1mνj(i))⋅1−pipi2)1/2.C_m^RDC(p,ν) _m^univ(p,ν)+ ( _i (p) ( _j=1^m _j(i) )· 1-p_ip_i^2 )^1/2. (4) The proofs of Theorems 6 and 7 center around a version of Wald’s identity that conditions on the returned attribute sequence of a universally exact algorithm; see Lemma 26 in Section A.8.2. Since ∑i∈supp(p)(∑j=1mνj(i))=m _i (p) ( _j=1^m _j(i) )=m, the additive term in Equation 4 is O(m)O( m). Every post-processing algorithm requires at least m model queries, so dividing both sides of the inequality by m implies muniv(p,ν)/mRDC(p,ν)→1C_m^univ(p,ν)/C_m^RDC(p,ν)→ 1 as m→∞m→∞. Thus, RDC is first-order optimal in the sense of minimizing the M-cost among all source-rate-free universally exact algorithms as the number of returned outputs m→∞m→∞. In Section A.2.2, we show that minimizing the M-cost over all universally exact source-rate-free algorithms is equivalent to an infinite-dimensional linear program. This program is difficult to solve for a number of reasons. For universal exactness, the stopping time of a post-processing algorithm can not have a deterministic upper bound N≤nN≤ n for some n<∞n<∞ (cf. Theorem 23). Consequently, the stopping time has unbounded support, so the primal program has infinitely many variables, with their number growing combinatorially with the number of M-samples. Furthermore, standard constrained Markov decision process methods can reduce programs with a finite number of constraints to finite occupation-measure programs (Altman, 2021, see, e.g.,). However, universal exactness imposes a continuum of globally coupled constraints, and thus these methods do not directly apply. The RDC algorithm, with its first-order optimality guarantees, serves as an intuitive yet appealing alternative to solving the universal exactness problem exactly. Nonetheless, the stopping time of the RDC algorithm, and any universally exact algorithm may be large when one or more source rates are rare. Theorem 8 (Universal expected M-cost lower bound). Fix m≥1m≥ 1 and assume the support condition supp(ν)⊆(supp(p))m supp(ν) ( supp(p))^m. Then, every universally exact algorithm Algm∈m(ν) Alg_m∈ A_m(ν) satisfies mAlgm(p,q)≥maxi∈supp(p)∑j=1mνj(i)pi.C_m Alg_m(p,q)≥ _i (p) _j=1^m _j(i)p_i. For the proof, see Section A.8.4. In particular, no universally exact source-rate-free procedure has M-cost uniformly bounded over all interior source rates p∈int(Δk−1)p∈ int( ^k-1). In order to obtain controlled query complexity, we therefore also consider approximate target sampling. Finally, when the support condition supp(ν)⊆(supp(p))msupp(ν) (supp(p))^m does not hold, universal exactness is impossible, as we can never M-sample an attribute sequence in supp(ν)\(supp(p))msupp(ν) (supp(p))^m. These observations motivate us to consider approximating rather than exactly attaining the target joint law. 4 Approximate statistical attribute alignment Following the discussion at the end of Section 3, we now consider approximate sampling that allows deviations between the output attribute law and the target joint law. More formally, we will measure the quality of approximation via f-divergences. Definition 9 (f-divergences). Let f:[0,∞)→ℝf:[0,∞) be a convex function with f(1)=0f(1)=0. For two probability distributions P and Q on a finite or countable space X, the forward f-divergence from P to Q is Df(P∥Q)=∑x:Q(x)>0Q(x)f(P(x)Q(x))+f∞Px:Q(x)=0,D_f(P\|Q)= _x:Q(x)>0Q(x)f ( P(x)Q(x) )+f_∞P\x:Q(x)=0\, where f∞≔limt→∞f(t)/tf_∞ _t→∞f(t)/t and the expression is interpreted in the usual extended-real sense.55 5 In the absolutely continuous case P≪QP Q, this reduces to Df(P∥Q)=Q[f(PQ)]=∑x∈Q(x)f(P(x)Q(x)).D_f(P\|Q)=E_Q [f ( PQ ) ]= _x Q(x)f ( P(x)Q(x) ). If f is strictly convex on [0,∞)[0,∞), then the f-divergence is called a strictly convex f-divergence. If Df(P∥Q)=0D_f(P\|Q)=0 holds if and only if P=QP=Q, then the f-divergence is said to be separable. We use the conventions DKL(P∥Q)=∑xP(x)log(P(x)/Q(x))D_KL(P\|Q)= _xP(x) (P(x)/Q(x)) and TV(P,Q)=12∑x|P(x)−Q(x)|TV(P,Q)= 12 _x|P(x)-Q(x)|. Forward KL divergence is strictly convex and separable, whereas TV is convex and separable but not strictly convex. Definition 10 (Unconditional statistical alignment discrepancy). For fixed source rates p∈Δk−1p∈ ^k-1, the unconditional f-statistical alignment discrepancy of Algm Alg_m relative to ν is Δfun(p)≡Δfun(Algm;ν;p)≔Df(PAlgm(A~∣x)∥ν) _f^un(p)≡ _f^un( Alg_m;ν;p) D_f (P_ Alg_m( A x)\|ν ) (5) where PAlgm(A~∣x)P_ Alg_m( A x) is the output attribute law in Equation 2 that may depend on the source rates p and target joint law ν. The algorithm has ε -approximate unconditional statistical alignment discrepancy at p if Δfun(p)≤ε _f^un(p)≤ , and perfect unconditional discrepancy if Δfun(p)=0 _f^un(p)=0. For a separable f-divergence, perfect unconditional discrepancy is equivalent to Pr(A~∣x)=ν ( A x)=ν; if this holds for every source rate satisfying supp(ν)⊆(supp(p))msupp(ν) (supp(p))^m, the algorithm is universally exact (cf. Definition 4). Definition 11 (Universal ε -approximate sampling). Let DfD_f be a forward f-divergence and let ε≥0 ≥ 0. A post-processing algorithm Algm∈m Alg_m∈ A_m is universally (f,ε)(f, )-approximate for the target law ν if its output attribute law satisfies Df(PAlgm(A~∣x)∥ν)=Δfun(Algm,ν,p)≤εD_f\! (P_ Alg_m( A x) \|ν )= _f^un( Alg_m;ν;p)≤ (6) for every p∈int(Δk−1)p ( ^k-1). If additionally Algm∈mo Alg_m∈ A_m^o, it is a universally (f,ε)(f, )-approximate source-rate-free algorithm. For a separable f-divergence, requiring that an algorithm is universally (f,ε)(f, )-approximate for ε=0 =0 is equivalent to requiring its universal exactness on the interior source domain. Within the class of algorithms satisfying universal approximate alignment, a natural objective is to determine the minimum achievable M-cost and to characterize its minimizers. Definition 12 (Universal source-rate-free M-cost). For fixed source rates p∈int(Δk−1)p ( ^k-1), define the universal source-rate-free M-cost as m,εuniv,f(p;ν)≔infAlgm∈mo:Δfun(Algm,ν,p′)≤ε∀p′∈int(Δk−1)mAlgm(p). _m, ^univ,f(p;ν) _ subarrayc Alg_m∈ A_m^o:\\ _f^un( Alg_m;ν;p )≤ 8.19447pt∀ p ( ^k-1) subarrayC_m Alg_m(p). (7) Analogous to universal exactness, the minimization in Equation 7 can be formulated as an infinite dimensional program. This optimization is difficult to solve for reasons similar to those in the exact alignment setting (cf. Section A.2.2), with the additional complication that the approximate sampling constraints need not be linear for general f-divergences. Furthermore, natural attempts to bypass this optimization using tractable heuristic procedures –such as approximate rejection sampling based on estimated source rates – appear to yield subpar performance; see Section A.3. Therefore, we consider the following count-conditional proxy as an upper bound for the unconditional discrepancy. 4.1 Count-conditional sampling For a realized batch ℬN≔(Y1,…,YN)B_N (Y_1,…,Y_N) of N observed outcomes Y1,…,YN∼i.i.d.P(⋅∣x)Y_1,…,Y_N i.i.d. P(· x), the post-processing algorithm Algm Alg_m induces a distribution over the annotations of its chosen outputs PAlgmℬN(A~=a~)≔Pr(A~1=a1,…,A~m=am∣x,ℬN) P_ Alg_m^B_N( A= a) ( A_1=a_1,…, A_m=a_m x,B_N) for (a1,…,am)∈m(a_1,…,a_m) ^m. In addition to conditioning on the input prompt x, this probability further conditions on the realized batch ℬNB_N and integrates over any E-sampling performed before and after the batch is realized. Now, for the random batch ℬNB_N, define the empirical attribute count vector C→=(C1,…,Ck) C=(C_1,…,C_k) with coordinates Ci≔∑t=1N1At=i,i∈[k].C_i _t=1^N1\A_t=i\,i∈[k]. Then, for every realized count vector c→ c with positive probability under the source rates, let PAlgmc(A~=a~)≔Pr(A~1=a1,…,A~m=am∣x,C→=c→)P^c_ Alg_m( A= a) ( A_1=a_1,…, A_m=a_m x, C= c) (8) be the algorithm’s output attribute law after conditioning on the realized attribute counts. Analogous to the output attribute law of Equation 2, we call this distribution the count-conditional output attribute law of Algm Alg_m. For a fixed number of model queries N=nN=n, the count vector C→ C is minimal sufficient for p under the i.i.d. sampling assumption A1,…,An∼i.i.d.Categorical(p)A_1,…,A_n i.i.d. Categorical(p) (cf. Definition 2). Hence, when it comes to inference about the source rates, there is no loss of information when conditioning on the counts; for completeness, we include a formal theorem and proof of this statement in Section A.8.5. Therefore, it is reasonable to condition on the count vector C→ C and aim to construct the best possible approximation of the target distribution given this vector of counts. Definition 13 (Count-conditional statistical alignment discrepancy). For fixed source rates p∈Δk−1p∈ ^k-1, the count-conditional f-statistical alignment discrepancy of Algm Alg_m relative to ν is ΔfC→(p)≡ΔfC→(Algm;ν;p)≔C→[Df(PAlgmC→∥ν)]. _f C(p)≡ _f C( Alg_m;ν;p) _ C [D_f (P_ Alg_m C\|ν ) ]. (9) The algorithm has ε -approximate count-conditional statistical alignment discrepancy at p if ΔfC(p)≤ε _f^C(p)≤ , and perfect count-conditional target sampling if ΔfC(p)=0 _f^C(p)=0. Proposition 14 (Relation between the unconditional and count-conditional criteria). Fix source rates p∈Δk−1p∈ ^k-1. Then, for every forward f-divergence, Δfun(Algm,ν,p)≤ΔfC→(Algm,ν,p). _f^un( Alg_m;ν;p)≤ _f C( Alg_m;ν;p). (10) This follows directly from Jensen’s inequality and the convexity of f-divergences. Our strategy will be to find algorithms that directly minimize the count-conditional objective. By the above result, these algorithms will yield universally approximate methods under the unconditional discrepancy and thus yield upper bounds on the universal source-rate-free M-cost (cf. Definition 12). Remark 15 (Count-conditional discrepancy and synthetic data augmentation). As discussed in the introduction, practitioners often select synthetic examples from a single generated dataset, whose observed attribute counts constrain the samples that can be returned. The statistical alignment discrepancy in Definition 10 averages the output attribute law over the randomness of the count vectors, and then measures its distance from the target joint law. The count-conditional discrepancy instead measures this distance separately for each count vector before averaging. Controlling the count-conditional objective also yields provable guarantees for analyses involving the augmented data. Under a shared attribute-conditional model (see, e.g., the label shift assumption of (Lipton et al., 2018)), the count-conditional discrepancy under TV controls the difference in bounded downstream criteria between augmentation with the selected synthetic examples and augmentation with ideal target samples. This is formalized in Section A.4. 4.2 Anytime RDC To obtain universally approximate algorithms, we consider two different stopping time rules that truncate the RDC stopping time, either by stopping when a specified level of precision or a capped budget is reached. For intermediate times up to and at these truncated RDC stopping times, we use the following exponential clock race construction to define post-processing algorithms that minimize the count-conditional discrepancy (see, e.g., Gillespie, 1976, and Section A.1 for further discussion). Since model queries are performed sequentially, it is useful to define the newly feasible support t≔Ωt∖Ωt−1D_t _t _t-1 at time t≥mt≥ m with the convention Ωm−1≔∅ _m-1 . Definition 16 (Anytime random demand coupon collector (A-RDC)). Fix a target joint law ν on [k]m[k]^m and E-sample an attribute sequence A→⋆∼ν A ν. Let the RDC completion time be Tν⋆≔inft≥m:A→⋆∈ΩtT_ν \t≥ m: A ∈ _t\ (cf. Algorithm 1). Now, for each m≤t<Tν⋆m≤ t<T_ν such that ν(t)>0ν(D_t)>0, independently sample an exponential clock time Gt∼Exp(ν(t))G_t (ν(D_t) ) and attribute sequence U→t∼ν(⋅∣t) U_t ν(· _t). If t<Tν⋆t<T_ν and ν(Ωt)>0ν( _t)>0, define the current clock winner as A^t≔U→τt,τt≔argminm≤s≤t:ν(s)>0Gs; A_t U_ _t, _t subarraycm≤ s≤ t:~ν(D_s)>0 subarray G_s; (11) otherwise, if ν(Ωt)=0ν( _t)=0, choose any sequence in the nonempty feasible set Ωt _t. At time Tν⋆T_ν , stop querying and return A→⋆ A . Algorithm 2 gives pseudo-code for the algorithm and Figure 2 illustrates its evolution. A-RDC generalizes RDC by returning feasible attribute sequences before the completion time Tν⋆T_ν . Under the support condition supp(ν)⊆(supp(p))msupp(ν) (supp(p))^m of Theorem 5, this time is almost surely finite, and both algorithms achieve zero unconditional discrepancy. We now show that A-RDC traces an optimal frontier under the count-conditional objective at all times t≥mt≥ m. Let m,t⊂m A_m,t⊂ A_m denote the class of post-processing algorithms whose stopping time is deterministically upper bounded by N≤tN≤ t for some t≥mt≥ m. Define, for any convex generator f with f(1)=0f(1)=0 and the usual finite-space extended conventions, Ψf(α)≔αf(1/α)+(1−α)f(0),α∈(0,1],limβ↓0βf(1/β)+(1−β)f(0),α=0. _f(α) casesα f(1/α)+(1-α)f(0),&α∈(0,1],\\ _β 0 \β f(1/β)+(1-β)f(0) \,&α=0. cases (12) For standard choices of f-divergences (cf. Definition 9), ΨKL(α)=−logα _KL(α)=- α, ΨTV(α)=1−α _TV(α)=1-α, with the usual conventions −log0=+∞- 0=+∞ and 0−1=+∞0^-1=+∞. Theorem 17 (Optimal count-conditional frontier). Fix a prompt x∈x , source rates p∈Δk−1p∈ ^k-1, and a target joint law ν on mA^m. For every t≥mt≥ m, let C→(t) C(t) be the source count process at time t (cf. Equation 3) and write αt≔ν(Ωm(C→(t))). _t ν( _m( C(t))). On the event αt>0 _t>0, the count-conditional output attribute law (cf. Equation 8) of A-RDC satisfies PA-RDCC→(A^t∣x)=ν(⋅∣Ωm(C→(t))).P_ A-RDC C ( A_t x )=ν (· _m( C(t)) ). (13) Furthermore, for every forward f-divergence, infAlgm∈m,tΔfC(Algm,ν,p)=[Ψf(ν(Ωm(C→(t))))], _Alg_m∈ A_m,t _f^C(Alg_m;ν;p)=E [ _f (ν( _m( C(t))) ) ], (14) and A-RDC achieves this minimum for each t≥mt≥ m simultaneously. Algorithm 2 Anytime RDC algorithms 0: Output size m, target joint law ν on [k]m[k]^m, annotator ϕφ, and variant: A-RDC, thresholded A-RDC (TA-RDC) with f-divergence and tolerance ε≥0 ≥ 0, or capped A-RDC (CA-RDC) with cap n≥mn≥ m. 0: Returned outputs (Y~1,…,Y~m)( Y_1,…, Y_m). 1: Stopping module: set σ≔+∞,A-RDC,τf,ε,TA-RDC,n,CA-RDC,σ cases+∞,&A-RDC,\\ _f, ,&TA-RDC,\\ n,&CA-RDC, cases where τf,ε _f, is defined in Definition 18. 2: E-sample A→⋆∼ν A ν and initialize Ωm−1←∅ _m-1← , Gmin←+∞G_ ←+∞, and A→cur←∅ A^cur← . 3: for t=1,2,…t=1,2,… do 4: Query one M-sample YtY_t and set Bt←ϕ(Yt)B_t←φ(Y_t). 5: if t≥mt≥ m then 6: Set Ωt _t ←(Bs1,…,Bsm):s1,…,sm∈[t] distinct, ← \(B_s_1,…,B_s_m):s_1,…,s_m∈[t] distinct \, (15) t _t ←Ωt∖Ωt−1. ← _t _t-1. 7: if A→⋆∈Ωt A ∈ _t then set A→cur←A→⋆ A^cur← A , N←tN← t, and break. 8: Set δt←ν(t). _t←ν(D_t). (16) 9: if δt>0 _t>0 then 10: Independently E-sample Gt∼Exp(δt),U→t∼ν(⋅∣t).G_t ( _t), 17.00024pt U_t ν(\,· _t). (17) 11: if Gt<GminG_t<G_ then set Gmin←GtG_ ← G_t and A→cur←U→t A^cur← U_t. 12: end if 13: if A→cur=∅ A^cur= then choose any A→cur∈Ωt A^cur∈ _t. 14: if t=σt=σ then set N←tN← t and break. 15: end if 16: end for 17: return outputs (Y~1,…,Y~m)( Y_1,…, Y_m) with attribute sequence A→cur A^cur, selected uniformly without replacement within each attribute from (Y1,…,YN)(Y_1,…,Y_N). Figure 2: Illustration of the A-RDC algorithm of Definition 16. There are k=2k=2 attributes, m=4m=4 outputs, and the target joint law is ν=q⊗mν=q m for uniform q=(1/2,1/2)q=(1/2,1/2). C→(t) C(t), the source-count process of Equation 3, records the histogram of the M-sampled attributes. At time t≥mt≥ m, if the realized clock time gt<gmin≔min1≤s<tgsg_t<g_ _1≤ s<tg_s, we uniformly sample A^t A_t from the newly feasible attribute sequences (in green). Otherwise, we keep the returned attributes from time t−1t-1, with the convention that gmin=+∞g_ =+∞ for t=1t=1. Once the terminal draw A⋆∼νA ν enters the feasible support, the A-RDC algorithm stops and returns A→⋆ A . Thresholded anytime RDC. We now consider a universally approximate algorithm that truncates the RDC stopping time with a count-conditional certificate. This certificate controls the count-conditional discrepancy as a proxy for the unconditional objective. Definition 18 (Thresholded anytime RDC (TA-RDC)). For a forward f-divergence and tolerance ε≥0 ≥ 0, define the certification stopping time τf,ε≔inft≥m:Ψf(αt)≤ε _f, \t≥ m: _f( _t)≤ \. Then, TA-RDC runs the A-RDC procedure Definition 16 but now stops at Nf,εTA-RDC≔Tν⋆∧τf,εN_f, TA-RDC T_ν _f, and returns output attributes A→^Nf,εTA-RDC A_N_f, TA-RDC (cf. Equation 11); see Algorithm 2. Theorem 19 (Finite-sample exact-or-certified optimality). For every forward f-divergence and every ε≥0 ≥ 0, the same TA-RDC rule is source-rate-free and universally (f,ε)(f, )-approximate (cf. Definition 11). More precisely, it terminates almost surely for every source rate p∈int(Δk−1)p ( ^k-1) and satisfies Δfun(TA-RDC,ν,p)≤p[Ψf(ατf,ε)]≤ε. _f^un (TA -RDC;ν;p ) _p\! [ _f( _ _f, ) ]≤ . (18) For the proof, see Section A.8.7. If the f-divergence is separable and ε=0 =0, then Tν⋆≤τf,εT_ν ≤ _f, almost surely, since Ψf(αt)=0 _f( _t)=0 if and only if αt=1 _t=1. This occurs only when supp(ν)⊆Ωtsupp(ν) _t, so that the feasible support contains the initially sampled attribute sequence A→⋆∼ν A ν. Thus, Nf,0=Tν⋆N_f,0=T_ν , and TA-RDC reduces to the A-RDC algorithm of Definition 16. For the product target ν=q⊗mν=q m and forward KL divergence, abbreviate the M-cost of TA-RDC as m,εTA-RDC(p,q)C_m, ^TA -RDC(p,q), and write m,εuniv(p,q)≔m,εuniv,KL(p,q⊗m)C_m, ^univ(p,q) _m, ^univ,KL (p;q m ) for the corresponding universal source-rate-free M-cost. Then, for any specified tolerance ε>0 >0, TA-RDC is first-order optimal among all source-rate free universally (KL,ε)( KL, )-approximate algorithms. Theorem 20 (Finite-sample and first-order universal approximate optimality of TA-RDC). Fix p,q∈int(Δk−1)p,q ( ^k-1). For δ≥0δ≥ 0, define the KL frontier ρp,q⋆(δ)≔minr∈Δk−1DKL(r∥q)≤δmaxi∈[k]ripi. _p,q (δ) _ subarraycr∈ ^k-1\\ D_KL(r\|q)≤δ subarray _i∈[k] r_ip_i. For any sequence εm≥0 _m≥ 0 such that εm/m→δ≥0 _m/m→δ≥ 0, the M-cost of TA-RDC and universal source-rate-free M-cost (cf. Definition 12) satisfy m,εmTA-RDC(p,q)m⟶ρp,q⋆(δ),m,εmuniv(p,q)m⟶ρp,q⋆(δ), C_m, _m^TA -RDC(p,q)m _p,q (δ), C_m, _m^univ(p,q)m _p,q (δ), (19) respectively. Moreover, for every m≥1m≥ 1 and every ε≥0 ≥ 0, m,εTA-RDC(p,q)≤m,εuniv(p,q)+3mmini∈[k]pi.C_m, ^TA -RDC(p,q) _m, ^univ(p,q)+ 3 m _i∈[k]p_i. (20) In particular, the relative optimality is uniform over the tolerance: supε≥0m,εTA-RDC(p,q)m,εuniv(p,q)⟶1. _ ≥ 0 C_m, ^TA -RDC(p,q)C_m, ^univ(p,q) 1. (21) For the proof, see Section A.8.8. At ε=0 =0, the stopping time rule of TA-RDC coincides with that of RDC and Theorem 20 recovers the first-order optimality of RDC. We study the finite sample performance of TA-RDC in Section 5.1 and find that the uniform convergence occurs quickly for moderate m under various settings. We also give first-order optimal frontiers under other divergences and procedures that attain them in Section A.5. Capped anytime RDC. If a practitioner specifies a query cap n≥mn≥ m, they may run A-RDC until either the exact completion time Tν⋆T_ν or the cap n is reached. This gives the capped-budget anytime RDC (CA-RDC) procedure, which stops at time NnCA-RDC≔Tν⋆∧nN_n^CA -RDC T_ν n and returns output attributes A^Tν⋆∧n A_T_ν n (cf. Equation 11); see Algorithm 2. Since CA-RDC and A-RDC agree pathwise (i.e., A^Tν⋆∧n=A^n A_T_ν n= A_n a.s.), the discrepancy of CA-RDC under any forward f-divergence satisfies Δfun(CA-RDC,ν,p)≤p[Df(PA-RDCC→(A^n)|ν)]=p[Ψf(αn)] _f^un (CA -RDC;ν;p ) _p [D_f (P_ A-RDC C ( A_n ) |ν ) ]=E_p [ _f( _n) ] Thus, the unconditional discrepancy of CA-RDC is bounded above by the minimum count-conditional discrepancy attainable by any post-processing algorithm with a capped budget N≤nN≤ n. We numerically compare the thresholded and capped anytime RDC methods in Section 5.1. 5 Experiments We provide simulations and experiments with generative AI models to evaluate statistical attribute alignment, with applications to demographic representation and synthetic dataset construction. 5.1 Simulations In order to provide support for the validity of our theoretical results, we first provide experiments in simulated settings. Setting and methodology. We consider a synthetic setting with k=8k=8 attributes, source and target rates p=(0.03,0.05,0.08,0.12,0.16,0.18,0.18,0.20)p=(0.03,0.05,0.08,0.12,0.16,0.18,0.18,0.20) and q=(0.14,0.12,0.13,0.15,0.14,0.12,0.11,0.09)q=(0.14,0.12,0.13,0.15,0.14,0.12,0.11,0.09), respectively, and vary the output size m∈100,500,1000m∈\100,500,1000\. We also set the target joint law to ν=q⊗mν=q m. There are no additional features in any of the three settings: the generated outcomes are identified with their attributes. Additional experiments varying the source rates, target rates, number of attributes, and output size are reported in Section A.7.1. We consider the following post-processing algorithms. (i) DS, direct-sampling, queries the model m times and returns the queried outputs. It lies in mo A_m^o, and its unconditional output attribute law is p⊗mp m. Thus, unless the outputs are already aligned, in the sense that the source and target rates are equal p=qp=q, DS has a positive statistical alignment discrepancy under any separable forward f-divergence (cf. Definition 9). (i) RDC, random demand coupon collector (cf. Algorithm 1 in Section 3), lies in mo(q⊗m) A_m^o(q m) (cf. Definition 4). It first E-samples an ordered target sequence with count vector L→∼Mult(m,q) L (m,q) and then queries the source until every demand is feasible. Its M-cost is the expected value of the stopping time Tν⋆=inft:C→(t)≥L→.T_ν = \t: C(t)≥ L\. RDC returns the initially sampled target sequence, so its unconditional discrepancy is exactly zero. (i) Oracle RS, oracle rejection sampling (cf. Definition 21 in Section A.2.1), lies in m(q⊗m) A_m(q m). It sequentially M-samples an output Ys∼P(⋅∣x)Y_s P(· x) and accepts it with probability (maxj∈supp(q)qj/pj)−1⋅qi/pi ( _j∈ supp(q)q_j/p_j )^-1· q_i/p_i where i=ϕ(Ys)∈[k]i=φ(Y_s)∈[k] is the annotated attribute. It continues to M-sample until it accepts m proposals, so that its M-cost is m⋅maxj∈supp(q)qj/pjm· _j∈ supp(q)q_j/p_j. The distribution of the attributes conditional on acceptance is exactly q, so the unconditional discrepancy of Oracle RS is exactly zero. This method minimizes the M-cost among all universally exact post-processing algorithms with known source rates (cf. Proposition 22) However, since the acceptance probabilities require knowledge of the source rates, this is not a practical black-box algorithm. (iv) TA-RDC, thresholded anytime random demand coupon collector (cf. Algorithm 2 in Section A.5), lies in mo A_m^o. This algorithm runs anytime RDC in Definition 16 until either the stopping time Tν⋆T_ν or statewise f-certificate at a specified level of ε≥0 ≥ 0 is reached. (v) CA-RDC, capped anytime random demand coupon collector (cf. Algorithm 2 in Section A.5), lies in mo A_m^o. This algorithm runs anytime RDC in Definition 16 until either the stopping time Tν⋆T_ν or cap n is reached. Reported metrics. For d∈[0,DKL(p∥q)]d∈[0,D_KL(p\|q)], let Δ¯m(d)≔1mΔKLun(TA-RDC(md)),C¯m(d)≔1mp[NKL,mdTA-RDC], _m(d) 1m _KL^un (TA -RDC(md) ), C_m(d) 1m _p\! [N_KL,md^TA -RDC ], be the unconditional discrepancy and M-cost of TA-RDC normalized by the number of outputs m. We vary the normalized tolerance d to trace three cost–discrepancy profiles: the realized TA-RDC profile d↦(Δ¯m(d),C¯m(d))d ( _m(d), C_m(d)), its nominal certificate profile d↦(d,C¯m(d))d (d, C_m(d)), and the first-order optimal KL frontier d↦(d,ρp,q⋆(d))d (d, _p,q (d)) (cf. Theorem 20). For CA-RDC, we vary the cap n∈[m,6m]n∈[m,6m] to trace out a cost-discrepancy profile (ΔKLun(CA-RDC)/m,p[NnCA-RDC]/m)( _KL^un (CA -RDC )/m, _p[N_n CA-RDC]/m). Population-level expressions and Monte Carlo estimators for the M-cost and unconditional discrepancies are given in Section A.6. Results. Figure 3 compares TA-RDC and CA-RDC at three output sizes m∈[100,500,1000]m∈[100,500,1000]. RDC and Oracle RS both have zero discrepancy, but RDC is source-rate-free whereas Oracle RS uses the source rates and is thus not a practical method. At the opposite endpoint, direct-sampling returns the first m outputs and hence has normalized M-cost one but a large sampling discrepancy. Between these endpoints, the anytime RDC methods of TA-RDC and CA-RDC achieve normalized KL discrepancies below 0.050.05 at normalized M-costs ranging from 1.851.85 to 2.182.18. Thus, in this setting, querying the model only about twice as many times as the number of returned outputs is sufficient to substantially reduce the discrepancy from direct-sampling. The finite-sample profiles also closely track the first-order optimal frontier, even with a moderate output size of m=100m=100. Moreover, the nominal statewise certificate for TA-RDC remains close to its unconditional KL discrepancy. This illustrates that the count-conditional objective underlying the certificate can be a useful proxy for the unconditional sampling discrepancy. Figure 3: Cost–discrepancy profiles under KL divergence for the k=8k=8 non-uniform source and target distributions with output sizes m∈100,500,1000m∈\100,500,1000\. The horizontal axis reports normalized unconditional KL discrepancy, DKL(PAlgm∥q⊗m)/mD_KL(P_Alg_m\|q m)/m, and the vertical axis reports normalized M-cost, p[N]/mE_p[N]/m. The nominal TA-RDC certificate and the first-order optimal frontier are included for comparison. RDC and Oracle RS attain zero discrepancy, although Oracle RS requires knowledge of the source rates. DS denotes direct-sampling, which returns the first m candidate samples and has normalized M-cost one. 5.2 Empirical experiments We now provide empirical experiments with various generative AI models. 5.2.1 Protected attribute alignment in text-to-image generation We consider text-to-image (T2I) generation settings: generating (i) headshots of individuals (Section 5.2.2), and (i) group photos of people (Section 5.2.4) in a professional medicine setting. We seek to align the distribution of demographic attributes, including gender, race, and/or age, with a specified target. This is a fairness-motivated instance of statistical attribute alignment. In our experiments, we consider various methods that generate batches of images (or, M-samples) and black-box post-processing methods that are applied to these batches. Since our focus is on black-box access, we compare with approaches that are applicable in that setting. M-sampling methods. We consider the following M-sampling methods that modify the text of the input prompt to the generative AI model. These are roughly ordered by increasing demographic specificity of the input prompt, and help showcase different ways in which generated attribute distributions may remain misaligned even after a prompting intervention is applied. (i) HPS (Hard Prompt Searching, Ding et al., 2021) fixes only the professional context of the prompt and does not mention protected attributes such as gender, age, or race. This tests the model’s default distribution over protected attributes. For example, in the individual-headshot setting, the prompt is “Show a photorealistic professional headshot of a person working in medicine or healthcare, in professional attire.” (i) TSI (Targeted Sampling Instruction) uses a single natural language prompt to ask the generator to sample from the desired protected attribute law. This baseline is inspired by work on ethical natural language interventions (Zhao et al., 2021; Bansal et al., 2022) and prompt-based bias control in text-to-image generation (Clemmer et al., 2024; Shin et al., 2024). In particular, TSI leaves the randomization implicit in the model by instructing it to first choose a target category or count-vector attribute uniformly at random and then generate an image matching that choice. (i) Demographic HPS (Hard Prompt Searching, Ding et al., 2021) externally randomizes over attribute-specific hard prompts. In detail, HPS forms a set of hard prompts x1′,…,xk′\x_1 ,…,x_k \, where xi′∈x_i requests attribute i∈[k]i∈[k], and samples from the mixture PHPS(⋅∣x)=∑i=1kqi⋅Pθ(⋅∣xi′).P_ HPS(· x)= _i=1^kq_i· P_θ(· x_i ). For example, an attribute-specific prompt xi′x_i in the professional-headshot setting is “Show a photorealistic professional headshot of a young Asian woman working in medicine or healthcare, in professional attire.” Thus, HPS differs from TSI as the randomization is performed externally, before querying the generative model. Post-processing methods. We consider the RDC and anytime RDC algorithms TA-RDC and CA-RDC from Section 5.1, as well as direct-sampling (DS) as a baseline. As post-processing methods, we apply them on top of any of the M-sampling methods (e.g., TSI or demographic HPS). In settings where hard prompting reliably returns outputs with the prompted attribute, post-processing methods cannot meaningfully reduce the unconditional discrepancy (cf. Definition 10). Indeed, if hard prompting is perfectly reliable, one could randomly sample output attributes so that the source rates p are equal to those of the target q. Then, the discrepancy of a method that returns the first m outputs is exactly zero. However, as we will demonstrate empirically, HPS and TSI can fail, because the generative AI model may not necessarily follow instructions or satisfy constraints reliably. This is especially true for more niche or derived attributes (e.g., the social vulnerability index in persona generation tasks; see, Section 5.2.5). GenAI models used. Publicly available and open-weight diffusion models have been widely adopted as synthetic image generators in applied data augmentation studies, see, e.g., Stöckl (2023); Tian et al. (2023); Bluethgen et al. (2025) and Section A.7.2 for further discussion. Consequently, we generate candidate images using open-weight text-to-image endpoints hosted by fal,66 6 fal.ai a platform that provides querying access to various models. Specifically, we consider the fal-hosted T2I models Flux-2-dev (Black Forest Labs, 2026), Qwen-Image-2512 (Qwen Team, 2025), and HiDream-O1-Image (HiDream.ai, 2026), which we abbreviate to Flux, Qwen, and HiDream, respectively. For certain combinations of M-sampled methods (e.g., HPS and TSI) and models (e.g., Flux and Qwen), we defer T2I empirical results to Section A.7.4 and Section A.7.6 for conciseness. For annotation, we use OpenAI API calls to GPT-5.5 as a vision-language annotator (OpenAI, 2026b). Prior work has shown this approach can have high agreement with human annotation.77 7 See Section A.7.2 for further discussion. General implementation details for T2I experiments are given in Section A.7.2 with experiment specific prompts, model configuration settings, and annotation procedures provided in Section A.7.3 and Section A.7.5. Experimental setting and reported metrics. For each T2I experiment, model, and M-sampling method, we first generate and annotate a fixed pool of images Ys∈Y_s , s=1,…,1000s=1,…,1000, which we re-use across evaluations. The target joint law is ν=q⊗mν=q m where the experiment specific target rates q vary across tasks with different attribute definitions and numbers of attributes k. We report two types of quantities. First, we record three pool-level diagnostics that depend only on the frozen pool of 1000 images and the target rates: (i) the on-support rate is the fraction of images whose annotations lie in supp(q)supp(q); (i) the target-attribute coverage is the number of unique attributes within the support of the target rates that are observed in the pool of images and, (i), for hard prompt M-sampling methods that directly request a protected attribute group (e.g., demographic HPS), we additionally record the compliance rate, defined as the fraction of images whose requested and realized annotations match. Second, for each post-processing method Algm Alg_m, we approximate KL statistical alignment discrepancies by sampling outputs with replacement from the frozen pool of images (cf. Section A.6). Since the T2I model may produce images whose annotated attribute lies outside the support of the target rates, supp(q) supp(q), there is a strictly positive probability that an M-sampled batch of n outputs ℬn=(Y1,…,Yn)B_n=(Y_1,…,Y_n) admits no feasible attribute sequence under the target joint law. In this case, the KL discrepancy of CA-RDC is necessarily +∞+∞, so we instead report the feasible-run discrepancy DKL(PCA-RDC(A^n∣αn>0)∥q⊗m)D_KL(P_ CA-RDC( A_n _n>0)\|q m) and the infeasibility probability βn≔1−Pr(αn>0) _n 1- ( _n>0); see Section A.6.3 for more details. In the main text, we report results for m=50m=50 returned images and, as in Section 5.1, trace out cost-discrepancy profiles by varying either the normalized tolerance level d≔ε/m∈[0,3]d /m∈[0,3] or the capped-budget n∈[m,20m]n∈[m,20m] for TA-RDC and CA-RDC, respectively. We defer results for discrepancies under other divergences and settings with other output sizes to Sections A.7.4, A.7.6 and A.7.8. 5.2.2 Professional headshots of individuals Experimental setup. The target distribution q is uniform over tuples of (1) a binary perceived-gender attribute with bins male-presenting, female-presenting; (2) age over two categories with bins young, old; and (3) race/ethnicity presentation over four categories with bins White/Caucasian, Black/African descent, Asian, Hispanic/Latino, yielding a total of k=16k=16 attributes. We abbreviate the gender, age, and race bins as M/F, Y/O, and W/B/A/H, respectively. For this experiment, the annotator is required to select one of the 16 attributes, so that the annotated attribute of all sampled images lies in the support of the target rates by construction; see Sections 5.2.4 and 5.2.5 below for experiments that allow outputs whose annotated attribute lies outside supp(q) supp(q). Main results. Hard prompt compliance and observed attributes. For HiDream, HPS and TSI only produce three and five target attributes out of 16 in our 1000 image pool, respectively (cf. Table 1). Thus, these two prompts do not produce images from most target attributes. In contrast, demographic HPS, which explicitly prompts for a target attribute, covers all 16 attributes and has a high compliance rate of 0.9740.974. We study why hard prompting fails in Section A.7.4. Table 1: Pool-level diagnostics for the individual-headshot prompt sources using the HiDream-O1-Image model. Attribute abbreviations are gender/age/race: F/M, Y/O, and W/B/A/H. M-sampling method Compliance rate Target-attribute coverage Attributes observed HPS – 3/16 F/Y/W, F/Y/B, F/Y/H TSI – 5/16 F/Y/B, F/Y/H, F/O/B, F/O/A, F/O/H Demographic HPS 0.974 16/16 All Reductions in sampling discrepancies. Across all three T2I models with demographic HPS M-sampling, the anytime RDC methods consistently decrease the unconditional KL discrepancies towards zero (cf. Figure 4). For example, at capped-budget n=500n=500, the KL discrepancy of CA-RDC is below 1.5×10−41.5× 10^-4 across all models with normalized M-costs of 5.145.14 for Flux and ≈3.10≈ 3.10 for both Qwen and HiDream. Similarly, at closely matched normalized M-costs of 5.17,3.065.17,3.06 and 3.113.11 for Flux, Qwen and HiDream, respectively, TA-RDC achieves discrepancies below 1.3×10−41.3× 10^-4 for all models. Figure 4: Statistical alignment discrepancies under KL divergence normalized by m=50m=50, the number of returned images. The images in the pool are generated using demographic HPS and are annotated into k=16k=16 target attributes. The panels correspond to the three T2I models. 5.2.3 Synthetic datasets for pairwise face recognition audits We next consider a synthetic dataset curation task. In facial identity audits, a verifier seeks to identify duplicate pairs of individuals in a returned set of face images. A central quantity in such systems is the false match rate over image pairs, which may vary with demographic attributes (Klare et al., 2012; Grother et al., 2019; Grother, 2022, see, e.g.,). This quantity depends on the distribution of pairs of images, rather than only on marginal distributions. Hence, proportion matching (PM), which selects feasible attribute counts as close as possible to target proportions, can be misleading here. Experimental setup. Using the demographic HPS headshot pools from Section 5.2.2, we follow a standard face-verification workflow of embedding two face images and applying a threshold to their embedding similarity as outlined in Schroff et al. (2015); Deng et al. (2019). In particular, each image is embedded using a Siamese face-recognition network (InsightFace buffalo_l88 8 https://github.com/deepinsight/insightface), and a pair is classified as a same-person match when the cosine similarity of the two embeddings exceeds a threshold t. Because no identity ground truth is available for the generated images, we adopt the operational convention that each generated image represents a distinct individual; under this convention, any positive same-person decision is counted as a false match. We keep the same k=16k=16 demographic classes, output size m=50m=50, and target joint law ν=q⊗mν=q m for uniform q. We compare our CA-RDC method with proportion matching at a capped-budget of n=200n=200. As a benchmark, we also record downstream metrics of an oracle whose output label law is exactly the joint target law. Results. At cosine threshold t=0.45t=0.45, CA-RDC yields false-match rates closer to the oracle benchmark across all three image models; see Table 2. For HiDream, the oracle rate is 6.404%6.404\%, compared with 6.099%6.099\% for CA-RDC and 4.670%4.670\% for PM. Thus, targeting a marginal objective underestimates the false-match rate. This illustrates that a synthetic data curation task can require specifying and approximating a joint attribute law rather than a marginal law. Implementation details and a threshold sensitivity analysis are deferred to Section A.7.9. Table 2: Synthetic pairwise audit task at cosine threshold t=0.45t=0.45. Same- and different-attribute match rates are estimated from all valid image pairs in the frozen pool of 1000 demographic HPS images. Oracle is an infeasible benchmark with output attribute law equal to the target joint law ν=q⊗mν=q m. Parentheses report standard errors across ten sampled batches. Model α^same(2) α_ same^(2) α^diff(2) α_ diff^(2) Oracle CA-RDC PM Flux 3.726%3.726\% 0.0395%0.0395\% 0.270%0.270\% 0.257%(0.005%)0.257\%\;(0.005\%) 0.205%(0.001%)0.205\%\;(0.001\%) Qwen 83.019%83.019\% 0.449%0.449\% 5.610%5.610\% 5.295%(0.112%)5.295\%\;(0.112\%) 4.089%(0.000%)4.089\%\;(0.000\%) HiDream 94.662%94.662\% 0.520%0.520\% 6.404%6.404\% 6.099%(0.156%)6.099\%\;(0.156\%) 4.670%(0.000%)4.670\%\;(0.000\%) 5.2.4 Compositional group photos Experimental setup. We next consider a compositional group photo setting, where each generated image is requested to contain a foreground trio of adults in a medical/healthcare scene. The attributes we aim to balance are the demographics of the people. In particular, we keep track of the counts of the group members’ age, gender, and race/ethnicity. The target distribution is uniform over all possible combinations of (one man & two women OR two men & one woman) × one White/Caucasian, one Black/African descent, & (one Hispanic/Latino OR one Asian adult), × (two young adults & one older adult OR three young adults). This yields k=2×2×2=8k=2× 2× 2=8 attributes. TSI and demographic HPS prompts may request, for example, an image whose three foreground adults comprise of two women & one man; two young adults & one older adult; and one White/Caucasian, one Asian, & one person of Black/African descent. Consequently, the prompt does not specify the exact demographics of each individual. Full details are deferred to Section A.7.5. Figure 5: Examples of HiDream group-photo generations. The top row shows on- and off-support TSI generations; captions report the annotated observed count vector (O). The bottom row shows hard-compliant, on-support non-compliant, and off-support demographic HPS generations; captions report the prompted target count vector (T) and annotated observed count vector (O). Abbreviations are F/M for female/male, Y/O for young/old, and W/B/A/H for White/Black/Asian/Hispanic. Main results. Qualitative results. Figure 5 shows that TSI often does not follow instructions. The same figure separates demographic HPS outputs into hard-compliant, on-support non-compliant, and off-support examples. Importantly, images that are non-compliant yet on-support can be used to improve the count-conditional sampling discrepancy via post-processing methods like the anytime RDC algorithms. Hard prompt compliance and on-support rate. Table 3 shows that models find it substantially harder to follow instructions about group composition than in the individual headshot experiments. For the HiDream model, TSI has on-support rate 0.0280.028, while demographic HPS raises the on-support rate to 0.6240.624 and covers all eight target attributes. Even under demographic HPS, however, the compliance rate is only 0.2190.219, indicating that following group compositional constraints is difficult. Table 3: Pool-level diagnostics for the group-photo prompt sources using the HiDream-O1-Image model. M-sampling method On-support rate Compliance rate Attributes observed TSI 0.028 – 6/8 Demographic HPS 0.624 0.219 8/8 Reductions in sampling discrepancy. Even when explicitly specifying the demographics in the input prompt, HiDream produces images whose attribute lies outside of the target support. Consequently, we report the feasible-run discrepancy as well as the infeasibility probability β^n β_n (cf. Section 5.2.1). As seen in Figure 6, TA-RDC and CA-RDC meaningfully reduce KL discrepancies: CA-RDC with a capped-budget of n=1000n=1000 achieves a feasible-run discrepancy of 3.6×10−43.6× 10^-4, with a normalized M-cost of 11.8511.85. Similarly, TA-RDC reduces the discrepancy to 8.2×10−48.2× 10^-4 at a matched M-cost of 11.9711.97. Furthermore, the infeasibility probability decreases rapidly as the capped-budget increases. At n=100n=100, β^n β_n is 0.00430.0043 and by n=200n=200 it falls to less than 10−2710^-27. Thus, even in the presence of substantial off-target samples, CA-RDC requires only a moderate query cap to produce a feasible output sequence with probability effectively equal to one. Figure 6: Various metrics for the group-photo setting with demographic HPS and the HiDream model. There are k=8k=8 target attributes and each post-processing method returns m=50m=50 images. Because hard prompting generates images whose annotated attribute lies outside supp(q) supp(q), we report the feasible-run discrepancies DKL(PCA-RDC(A^n∣αn>0)∥q⊗m)D_KL(P_ CA-RDC( A_n _n>0)\|q m) and the infeasibility probability βn≔1−Pr(αn>0) _n 1- ( _n>0) (cf. Section 5.2.1) in panels (B) and (C), respectively. 5.2.5 Geocoded persona generation Experimental setup. We next consider a synthetic patient-persona generation task, motivated by constructing evaluation datasets for patient-facing digital health assistants and related conversational health systems (Reichenpfader and Denecke, 2024; Kyung et al., 2025; Liao et al., 2024; Rashidian et al., 2025; Cook et al., 2025). We generate patient personas, with fields including an age band, care setting, city, state, ZIP code, request type, and patient message. The audited attribute is the CDC 2022 Social Vulnerability Index (SVI) quartile of the generated ZIP code.99 9 CDC/ATSDR SVI data downloads: https://svi.cdc.gov/dataDownloads/data-download.html. We discretize the national overall SVI percentile into four quartiles, assign invalid or unmatched ZIP codes to an auxiliary attribute with target mass zero, and set the target distribution to be uniform over the four valid SVI quartiles. We use GPT-5.5 to generate personas. M-sampling and post-processing methods. As in the text-to-image experiments, we distinguish between the method used to generate outputs and the post-processing rules applied thereafter to them. We consider two M-sampling methods. (i) Hard SVI prompting. This direct hard-prompt baseline externally randomizes over the four requested SVI quartiles and queries the model with an attribute-specific prompt. For example, for a requested quartile, the prompt asks for a ZIP whose SVI percentile lies in the corresponding quartile range. (i) County-seeded prompting. Here, we sample a county/state seed and ask the model to generate a persona located in or near that county. The prompt does not mention SVI, social vulnerability, or the target quartile. This is intended to broaden geographic support without asking the model to reason about the target SVI quartile. For each M-sampling method, we run RDC and the anytime RDC procedures of TA-RDC and CA-RDC. Detailed prompts, the annotation procedure, and example personas are provided in Sections A.7.7 and A.7.8. Reported metrics. Following the protocol of Section 5.2.1, we first generate and annotate a fixed pool of 10001000 personas for each M-sampling method. We then report the three pool-level diagnostics of the on-support rate, target-attribute coverage, and compliance rate. For each post-processing method, we also track household and geographic diversity metrics. In particular, for each set of m returned personas, we record the proportion of outputs whose ZIP code lies above the 7575th national percentile for a socioeconomic component (i.e., housing-cost burden, transportation access, and uninsurance rate), as well as the top-five-city share rate (share of responses in the five most frequent cities). Identical to the protocol of Section 5.2.2, we approximate the KL statistical alignment discrepancies by sampling with replacement from the frozen pool of generated personas. We record the feasible-run discrepancy and infeasibility probability for settings where there are personas whose annotated attribute lies outside the support of the target rates, supp(q)supp(q). In the main text, we consider output sizes of m=50m=50 personas and, as in Section 5.1, trace out cost-discrepancy profiles by varying either the normalized tolerance level d≔ε/m∈[0,3]d /m∈[0,3] or the capped-budget n∈[m,20m]n∈[m,20m] for TA-RDC and CA-RDC, respectively. We defer results for discrepancies under other divergences and settings with other output sizes to Section A.7.8. Table 4: SVI4 persona-generation results at m=50m=50. Pool-level diagnostics are reported once per M-sampling method, while the remaining columns report means and standard deviations over sets of returned persona outputs. The three socioeconomic rates give the proportions of returned personas, among those linked to the 2022 national ZCTA-level SVI data, whose ZCTAs lie above the 75th national percentile for the corresponding indicator. The top-five city–state share is the proportion belonging to the five most frequently represented city–state pairs within each returned set. Anytime RDC methods are selected by choosing the nearest hyperparameter setting (normalized tolerance d=ε/md= /m or cap n for TA-RDC and CA-RDC, respectively) whose M-cost is halfway between direct sampling and RDC. Pool-level diagnostics Returned personas after post-processing M-sampling method On-support rate Target-attribute coverage Compliance rate Post-processing method Setting M-cost/mM-cost/m Housing- cost burden No-vehicle prevalence Uninsured prevalence Top-5-city–state share Hard SVI prompting 1.001.00 4/44/4 0.350.35 RDC – 21.43(7.86)21.43\;(7.86) 0.35(0.07)0.35\;(0.07) 0.39(0.07)0.39\;(0.07) 0.11(0.04)0.11\;(0.04) 0.42(0.06)0.42\;(0.06) TA-RDC d=0.07d=0.07 11.97(4.57)11.97\;(4.57) 0.41(0.07)0.41\;(0.07) 0.46(0.07)0.46\;(0.07) 0.12(0.05)0.12\;(0.05) 0.37(0.05)0.37\;(0.05) CA-RDC n=600n=600 11.74(1.02)11.74\;(1.02) 0.41(0.07)0.41\;(0.07) 0.46(0.07)0.46\;(0.07) 0.12(0.05)0.12\;(0.05) 0.38(0.05)0.38\;(0.05) DS – 1.00(0.00)1.00\;(0.00) 0.60(0.07)0.60\;(0.07) 0.62(0.07)0.62\;(0.07) 0.20(0.06)0.20\;(0.06) 0.39(0.06)0.39\;(0.06) County-seeded prompting 0.980.98 4/44/4 – RDC – 1.74(0.41)1.74\;(0.41) 0.27(0.06)0.27\;(0.06) 0.31(0.06)0.31\;(0.06) 0.17(0.05)0.17\;(0.05) 0.15(0.03)0.15\;(0.03) TA-RDC d=0.04d=0.04 1.40(0.20)1.40\;(0.20) 0.30(0.06)0.30\;(0.06) 0.34(0.06)0.34\;(0.06) 0.18(0.05)0.18\;(0.05) 0.16(0.03)0.16\;(0.03) CA-RDC n=70n=70 1.37(0.07)1.37\;(0.07) 0.30(0.06)0.30\;(0.06) 0.34(0.07)0.34\;(0.07) 0.18(0.05)0.18\;(0.05) 0.16(0.03)0.16\;(0.03) DS – 1.00(0.00)1.00\;(0.00) 0.32(0.07)0.32\;(0.07) 0.36(0.07)0.36\;(0.07) 0.19(0.06)0.19\;(0.06) 0.16(0.03)0.16\;(0.03) Main results. Hard compliance and geographic diversity. Table 4 demonstrates that hard SVI prompting has a compliance rate of 0.3560.356 and is thus not reliable. Using these hard SVI prompted samples with direct-sampling also results in highly concentrated socioeconomic factors. For example, the proportion of returned personas associated with high housing-cost burden is 0.600.60 under direct-sampling, compared with 0.350.35–0.410.41 under RDC and the anytime RDC methods. This demonstrates that aligning the target attributes also changes the distribution of correlated auxiliary features. We provide diagnostics for hard prompt failures in Section A.7.8. Reductions in sampling discrepancy. County-seeded prompting produces personas whose annotated attribute lies outside of supp(q)supp(q) – of the 1000 generated personas, 18 were unmatched to an SVI quartile. Consequently, we report the feasible-run discrepancy and infeasibility probability β^n β_n (cf. Section 5.2.1). As can be seen in Figure 7, both TA-RDC and CA-RDC reduce the discrepancies under either persona-generation method. However, the degree of reduction appears to heavily depend on the source rates. For example, under hard SVI prompting, the observed quartile distribution is highly imbalanced despite having no observed off-support outputs (see, also, Section A.7.8). In this case, TA-RDC and CA-RDC both require a normalized M-cost of ≈12≈ 12 to achieve a KL discrepancy of <0.05<0.05. In contrast, county-seeded prompting produces a more balanced distribution over valid SVI quartiles. Consequently, TA-RDC can achieve a similar discrepancy as the anytime RDC methods under hard SVI prompting at a much smaller normalized M-cost of 1.021.02. These results illustrate that post-processing model outputs without hard prompting may actually improve the statistical alignment discrepancies over M-sampling methods that explicitly request certain features. Furthermore, like with the group photo T2I experiments in Section 5.2.4, the CA-RDC infeasibility probability under county-seeded prompting decreases rapidly with the capped-budget n. At the moderately sized cap of n=70n=70, CA-RDC can achieve a feasible-run normalized KL discrepancy of 0.0130.013, with a negligible infeasibility probability of β^70=3.8×10−20 β_70=3.8× 10^-20. Figure 7: Various metrics for the SVI persona generation task with k=4k=4 target quartiles and m=50m=50 returned personas. Panel (A) reports the KL discrepancy with hard SVI prompting for both TA-RDC and CA-RDC, since the annotated attributes of all 1000 generated personas lie inside supp(q) supp(q). In contrast, county-seeded prompting produces 1818 personas with attributes outside of supp(q) supp(q) (cf. Table 4), so panel (B) plots the cost-discrepancy profile of only TA-RDC. For CA-RDC, we report the feasible-run discrepancies DKL(PCA-RDC(A^n∣αn>0)∥q⊗m)D_KL(P_ CA-RDC( A_n _n>0)\|q m) and the infeasibility probability βn≔1−Pr(αn>0) _n 1- ( _n>0) (cf. Section 5.2.1) in panels (C) and (D), respectively. 6 Discussion Statistical attribute alignment (SAA) provides a common formulation for alignment goals including fairness and synthetic data augmentation tasks. Our results characterize the model-query cost of exactly or approximately achieving a target joint law on output attributes under post-processing black-box access. The target distribution is supplied by the practitioner, and our post-processing methods can adapt the attribute distribution of generators that have already undergone other forms of alignment. In this way, SAA complements broader alignment methods in generative AI. We discuss several directions that build on the SAA framework. Dominance and admissibility. For a set of source rates ⊆Δk−1P ^k-1 and two post-processing algorithms Algm,Algm′∈mAlg_m,Alg _m∈ A_m, we say that Algm′Alg _m dominates AlgmAlg_m over P if mAlgm′(p) _m^Alg _m(p) ≤mAlgm(p);Δfun(Algm′,ν,p)≤Δfun(Algm,ν,p) _m^Alg_m(p); _f^un(Alg _m;ν;p)≤ _f^un(Alg_m;ν;p) (22) for every p∈p , with at least one of these inequalities strict for at least one p∈p . A post-processing algorithm is then called (cost-discrepancy) admissible over P if it is not dominated by another algorithm (see, for example, classical decision-theoretic notions of dominance and admissibility in Wald (1950) and Lehmann and Casella (1998)). Theorem 6 shows that the RDC algorithm is admissible over =int(Δk−1)P= int( ^k-1) when m=1m=1. Furthermore, when the target joint law is ν=q⊗mν=q m, direct-sampling is also admissible, since no post-processing algorithm can dominate it at p=qp=q; see Figure 8. Though the TA-RDC procedure of Definition 18 is first-order optimal in the limit as m→∞m→∞, it is not necessarily admissible over =Δk−1P= ^k-1, in general. In particular, there are black-box post-processing algorithms that may strictly improve the unconditional discrepancy while achieving the same M-cost; we give one such procedure in Section A.5. Figure 8: Source-dependent cost–discrepancy profiles for direct-sampling (DS), RDC, and TA-RDC, with m=100m=100 and target joint law ν=q⊗mν=q m with uniform target rates q=(0.5,0.5)q=(0.5,0.5): (A) p=qp=q; (B) p=(0.8,0.2)p=(0.8,0.2). In this small-scale setting, M-cost and unconditional KL discrepancy are evaluated explicitly through enumeration of count state spaces (cf. Section A.6). In (A), DS attains both zero discrepancy and minimum cost. For tolerance values ε>mlog2 >m 2, TA-RDC simplifies to DS, while for ε=0 =0, it reduces to RDC. In either of these two cases, it achieves zero unconditional discrepancy. Small irregularities for intermediate tolerances 0<ε<mlog20< <m 2 reflect the discrete nature of the count vectors used for the stopping time (cf. Definition 18). In (B), TA-RDC reduces discrepancy relative to DS with additional M-cost. Relevance as genAI capabilities improve. As model query costs decline (Maslej et al., 2025, see, e.g.,), so does the cost of generating a larger batch of samples. This makes universally exact and approximate algorithms less costly, thus increasing the practical applicability of our approach. Moreover, no single target distribution or input prompt is appropriate for every use case, so better models do not eliminate the need for a downstream method that can steer outputs toward an application specific target without retraining. In particular, a model previously aligned to one demographic composition or training population may require a different attribute distribution for a new application. Since our method uses only black-box samples, it does not need to be redesigned when providers update their model or target specifications. Noisy annotator. Suppose there is a latent true attribute G associated with Y∼P(⋅∣x)Y P(· x) with rates πi=Pr(G=i) _i= (G=i). If the annotator ϕφ is noisy, ϕ(Y)φ(Y) is not necessarily always equal to the true attribute G. One can model its error through a confusion rate matrix Cij=Pr(G=i∣A=j)=πiKij∑ℓπℓKℓj;Kij=Pr(A=j∣G=i).C_ij= (G=i A=j)= _iK_ij _ _ K_ j; K_ij= (A=j G=i). (Patrini et al., 2017; Lipton et al., 2018, see, e.g.). Given C, choose proxy target rates u⋆∈argminu∈Δk−1Df(Cu∥q),u ∈ _u∈ ^k-1D_f(Cu\|q), and set q¯=Cu⋆ q=Cu . If q∈CΔk−1q∈ C ^k-1, we may choose u⋆u so that q¯=q q=q and thus exact sampling for the true attribute is possible. Otherwise, exact sampling with a single output is impossible, and q¯ q is the closest output attribute law under the chosen divergence. For general m≥1m≥ 1 and a target joint law ν=q⊗mν=q m, RDC run with target rates u⋆u has true attribute law q¯⊗m q m unconditionally, so that it is universally exact if q∈CΔk−1q∈ C ^k-1. For approximate sampling, an annotation error aware anytime RDC method changes the rate of the exponential clock in Definition 16 from ν(t)ν(D_t) to (u⋆)⊗m(t)(u ) m(D_t). Its count-conditional output attribute law (cf. Equation 8) is then Qc→u⋆≔(u⋆)⊗m(⋅∣Ωm(c→))Q_ c^u (u ) m (· _m( c) ) for intermediate times t≥mt≥ m where Ωm(c→) _m( c) and c→=c→(t) c= c(t) are the realized feasible support and source counts, respectively (cf. Equation 3). Since C⊗m(u⋆)⊗m=q¯⊗mC m(u ) m= q m, the data processing inequality gives Df(C⊗mQc→u⋆∥q¯⊗m)=Df(C⊗mQc→u⋆∥C⊗m(u⋆)⊗m)≤Df(Qc→u⋆∥(u⋆)⊗m).D_f (C mQ_ c^u \| q m )=D_f (C mQ_ c^u \|C m(u ) m )≤ D_f (Q_ c^u \|(u ) m ). Thus, minimizing the count-conditional discrepancy under the proxy target rates controls the distortion from the closest reachable product law. References Abdel-Azim et al. (2026) A. Abdel-Azim, R. Wang, and X. Lin Harnessing synthetic data from generative ai for statistical inference. arXiv preprint arXiv:2603.05396. Cited by: §A.1, §1. Alamdari et al. (2023) P. A. Alamdari, T. Q. Klassen, E. Creager, and S. A. McIlraith Remembering to be fair: non-markovian fairness in sequential decision making. arXiv preprint arXiv:2312.04772. Cited by: §A.1. Altman (2021) E. Altman Constrained markov decision processes. Routledge. Cited by: §A.2.2, §3. Amini et al. (2019) A. Amini, A. P. Soleimany, W. Schwarting, S. N. Bhatia, and D. Rus Uncovering and mitigating algorithmic bias through learned latent structure. In Proceedings of the 2019 AAAI/ACM Conference on AI, Ethics, and Society, p. 289–295. Cited by: §A.1. Angelopoulos et al. (2023) A. N. Angelopoulos, S. Bates, C. Fannjiang, M. I. Jordan, and T. Zrnić Prediction-powered inference. Science 382 (6671), p. 669–674. External Links: Document Cited by: §A.1, §1. Azam and Akhtar (2025) B. Azam and N. Akhtar Plug-and-play interpretable responsible text-to-image generation via dual-space multi-facet concept control. In Proceedings of the Computer Vision and Pattern Recognition Conference, p. 2976–2985. Cited by: footnote 1. Bai et al. (2022) Y. Bai, S. Kadavath, S. Kundu, A. Askell, J. Kernion, A. Jones, A. Chen, A. Goldie, A. Mirhoseini, C. McKinnon, C. Chen, C. Olsson, C. Olah, D. Hernandez, D. Drain, D. Ganguli, D. Li, E. Tran-Johnson, E. Perez, J. Kerr, J. Mueller, J. Ladish, J. Landau, K. Ndousse, K. Lukosuite, L. Lovitt, M. Sellitto, N. Elhage, N. Schiefer, N. Mercado, N. DasSarma, R. Lasenby, R. Larson, S. Ringer, S. Johnston, S. Kravec, S. El Showk, S. Fort, T. Lanham, T. Telleen-Lawton, T. Conerly, T. Henighan, T. Hume, S. R. Bowman, Z. Hatfield-Dodds, B. Mann, D. Amodei, N. Joseph, S. McCandlish, T. Brown, and J. Kaplan Constitutional AI: harmlessness from AI feedback. arXiv preprint arXiv:2212.08073. External Links: Document, Link Cited by: §1. Bansal et al. (2022) H. Bansal, D. Yin, M. Monajatipoor, and K. Chang How well can text-to-image generative models understand ethical natural language interventions?. In Proceedings of the 2022 Conference on Empirical Methods in Natural Language Processing, p. 1358–1370. Cited by: §1, item (i). Barocas et al. (2023) S. Barocas, M. Hardt, and A. Narayanan Fairness and machine learning: limitations and opportunities. MIT press. Cited by: §1, §1. Bashari et al. (2025a) M. Bashari, Y. Lee, R. M. Lotan, E. Dobriban, and Y. Romano General synthetic-powered inference. arXiv preprint arXiv:2509.20345. External Links: Link Cited by: §A.1, §1. Bashari et al. (2025b) M. Bashari, R. M. Lotan, Y. Lee, E. Dobriban, and Y. Romano Synthetic-powered predictive inference. In Advances in Neural Information Processing Systems, Vol. 38. External Links: Document, Link Cited by: §A.1, §1. Beck et al. (2025) J. Beck, L. M. Kemeter, K. Dürrbeck, M. H. I. Abdalla, and F. Kreuter Toward integrating chatgpt into satellite image annotation workflows: a comparison of label quality and costs of human and automated annotators. IEEE Journal of Selected Topics in Applied Earth Observations and Remote Sensing 18, p. 4366–4381. External Links: Document Cited by: §A.7.2. Bender et al. (2021) E. M. Bender, T. Gebru, A. McMillan-Major, and S. Shmitchell On the dangers of stochastic parrots: can language models be too big?. In Proceedings of the 2021 ACM conference on fairness, accountability, and transparency, p. 610–623. Cited by: §1. Black Forest Labs (2026) Black Forest Labs FLUX.2 [dev]. Note: Hugging Face model cardAccessed: 2026-05-20 External Links: Link Cited by: item (i), §5.2.1. Block and Polyanskiy (2023) A. Block and Y. Polyanskiy The sample complexity of approximate rejection sampling with applications to smoothed online learning. In The Thirty Sixth Annual Conference on Learning Theory, p. 228–273. Cited by: §1. Bluethgen et al. (2025) C. Bluethgen, P. Chambon, J. Delbrouck, R. Van Der Sluijs, M. Połacin, J. M. Zambrano Chaves, T. M. Abraham, S. Purohit, C. P. Langlotz, and A. S. Chaudhari A vision–language foundation model for the generation of realistic chest x-ray images. Nature Biomedical Engineering 9 (4), p. 494–506. Cited by: §A.7.2, §5.2.1. Bolukbasi et al. (2016) T. Bolukbasi, K. Chang, J. Y. Zou, V. Saligrama, and A. T. Kalai Man is to computer programmer as woman is to homemaker? debiasing word embeddings. Advances in neural information processing systems 29. Cited by: §1. Bommasani et al. (2021) R. Bommasani, D. A. Hudson, E. Adeli, R. Altman, S. Arora, S. von Arx, M. S. Bernstein, J. Bohg, A. Bosselut, E. Brunskill, et al. On the opportunities and risks of foundation models. arXiv preprint arXiv:2108.07258. Cited by: §1. Boyd and Vandenberghe (2004) S. Boyd and L. Vandenberghe Convex optimization. Cambridge University Press, Cambridge. Cited by: §A.8.8. Brown et al. (2020) T. Brown, B. Mann, N. Ryder, M. Subbiah, J. D. Kaplan, P. Dhariwal, A. Neelakantan, P. Shyam, G. Sastry, A. Askell, et al. Language models are few-shot learners. Advances in neural information processing systems 33, p. 1877–1901. Cited by: §1. Buolamwini and Gebru (2018) J. Buolamwini and T. Gebru Gender shades: intersectional accuracy disparities in commercial gender classification. In Conference on fairness, accountability and transparency, p. 77–91. Cited by: §1. Cano et al. (2025) F. Cano, T. A. Henzinger, B. Könighofer, K. Kueffner, and K. Mallik Fairness shields: safeguarding against biased decision makers. Proceedings of the AAAI Conference on Artificial Intelligence 39, p. 15659–15668. Cited by: §A.1, §1. Chen et al. (2024a) Q. Chen, A. Ye, Y. Zhang, J. Chen, and C. Huang Information-minimizing generative adversarial network for fair generation and classification. Neural Processing Letters 56 (1), p. 36. Cited by: §A.1. Chen et al. (2024b) Y. Chen, Z. Yan, and Y. Zhu A comprehensive survey for generative data augmentation. Neurocomputing 600, p. 128167. Cited by: §A.1, §1. Cheng et al. (2025) C. Cheng, C. Wu, X. Zhao, S. Bensalem, and H. Ruess Runtime monitoring and enforcement of conditional fairness in generative ais. In International Conference on Runtime Verification, p. 73–91. Cited by: §A.1, §1. Chernozhukov et al. (2018) V. Chernozhukov, D. Chetverikov, M. Demirer, E. Duflo, C. Hansen, W. Newey, and J. Robins Double/debiased machine learning for treatment and structural parameters. Oxford University Press Oxford, UK. Cited by: §A.6.4. Choi et al. (2020) K. Choi, A. Grover, T. Singh, R. Shu, and S. Ermon Fair generative modeling via weak supervision. In International Conference on Machine Learning, p. 1887–1898. Cited by: §A.1, §1, §2. Choi et al. (2024) Y. Choi, J. Park, H. Kim, J. Lee, and S. Park Fair sampling in diffusion models through switching mechanism. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 38, p. 21995–22003. Cited by: §A.1. Chow and Robbins (1965) Y. S. Chow and H. Robbins On the asymptotic theory of fixed-width sequential confidence intervals for the mean. The Annals of Mathematical Statistics 36 (2), p. 457–462. Cited by: §A.3. Christiano et al. (2017) P. F. Christiano, J. Leike, T. B. Brown, M. Martic, S. Legg, and D. Amodei Deep reinforcement learning from human preferences. In Advances in Neural Information Processing Systems, Vol. 30. External Links: Link Cited by: §1. Clemmer et al. (2024) C. Clemmer, J. Ding, and Y. Feng Precisedebias: an automatic prompt engineering approach for generative ai to mitigate image demographic biases. In Proceedings of the IEEE/CVF Winter Conference on Applications of Computer Vision, p. 8596–8605. Cited by: item (i). Cohen and Saabni (2025) S. Cohen and R. Saabni A black-box technique to mitigate gender bias for generative ai. In Seventeenth International Conference on Machine Vision (ICMV 2024), Vol. 13517, p. 112–118. Cited by: footnote 1. Cook et al. (2025) D. A. Cook, J. Overgaard, V. S. Pankratz, G. Del Fiol, and C. A. Aakre Virtual patients using large language models: scalable, contextualized simulation of clinician-patient dialogue with feedback. Journal of Medical Internet Research 27, p. e68486. External Links: Document Cited by: §5.2.5. Cover et al. (1991) T. M. Cover, J. A. Thomas, and J. Kieffer Elements of information theory. Vol. 2, wiley New York. Cited by: §A.6. Csiszár (1998) I. Csiszár The method of types [information theory]. IEEE Transactions on Information Theory 44 (6), p. 2505–2523. Cited by: §A.6. De Simone et al. (2023) Z. De Simone, A. Boggust, A. Satyanarayan, and A. Wilson DiffusionWorldViewer: exposing and broadening the worldview reflected by generative text-to-image models. arXiv preprint arXiv:2309.09944. Cited by: §A.1, §2. Deng and Lu (2025) B. Deng and Y. Lu Weed image augmentation by controlnet-added stable diffusion for multi-class weed detection. Computers and Electronics in Agriculture 232, p. 110123. Cited by: §A.7.2. Deng et al. (2019) J. Deng, J. Guo, N. Xue, and S. Zafeiriou Arcface: additive angular margin loss for deep face recognition. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, p. 4690–4699. Cited by: §5.2.3. Ding et al. (2021) M. Ding, Z. Yang, W. Hong, W. Zheng, C. Zhou, D. Yin, J. Lin, X. Zou, Z. Shao, H. Yang, et al. Cogview: mastering text-to-image generation via transformers. Advances in neural information processing systems 34, p. 19822–19835. Cited by: item (i), item (i). Doumas and Papanicolaou (2016) A. V. Doumas and V. G. Papanicolaou The coupon collector’s problem revisited: generalizing the double dixie cup problem of newman and shepp. ESAIM: Probability and Statistics 20, p. 367–399. Cited by: §A.6.1. Efraimidis and Spirakis (2006) P. S. Efraimidis and P. G. Spirakis Weighted random sampling with a reservoir. Information Processing Letters 97 (5), p. 181–185. External Links: Document Cited by: §A.1. Feldman et al. (2015) M. Feldman, S. A. Friedler, J. Moeller, C. Scheidegger, and S. Venkatasubramanian Certifying and removing disparate impact. In proceedings of the 21th ACM SIGKDD international conference on knowledge discovery and data mining, p. 259–268. Cited by: §A.1. Flegal and Gong (2015) J. M. Flegal and L. Gong Relative fixed-width stopping rules for markov chain monte carlo simulations. Statistica Sinica, p. 655–675. Cited by: §A.3. Friedrich et al. (2023) F. Friedrich, M. Brack, L. Struppek, D. Hintersdorf, P. Schramowski, S. Luccioni, and K. Kersting Fair diffusion: instructing text-to-image generation models on fairness. arXiv preprint arXiv:2302.10893. Cited by: §A.1. Friedrich et al. (2025) F. Friedrich, M. Brack, L. Struppek, D. Hintersdorf, P. Schramowski, S. Luccioni, and K. Kersting Auditing and instructing text-to-image generation models on fairness. AI and Ethics 5 (3), p. 2103–2123. Cited by: §1. Gallegos et al. (2025) I. O. Gallegos, R. Aponte, R. A. Rossi, J. Barrow, M. Tanjim, T. Yu, H. Deilamsalehy, R. Zhang, S. Kim, F. Dernoncourt, et al. Self-debiasing large language models: zero-shot recognition and reduction of stereotypes. In Proceedings of the 2025 Conference of the Nations of the Americas Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 2: Short Papers), p. 873–888. Cited by: footnote 1. Gillespie (1976) D. T. Gillespie A general method for numerically simulating the stochastic time evolution of coupled chemical reactions. Journal of Computational Physics 22 (4), p. 403–434. External Links: Document Cited by: §A.1, §4.2. Giuffrè and Shung (2023) M. Giuffrè and D. L. Shung Harnessing the power of synthetic data in healthcare: innovation, application, and privacy. NPJ digital medicine 6 (1), p. 186. Cited by: §A.1. Grother et al. (2019) P. Grother, M. Ngan, and K. Hanaoka Face recognition vendor test (fvrt): part 3, demographic effects. National Institute of Standards and Technology Gaithersburg, MD. Cited by: §A.1, §5.2.3. Grother (2022) P. Grother Face recognition vendor test (frvt) part 8: summarizing demographic differentials. National Institute of Standards and Technology (NIST) 8429, p. 8. Cited by: §A.1, §5.2.3. Hayter (2014) A. J. Hayter Recursive formulas for multinomial probabilities with applications. Computational Statistics 29 (5), p. 1207–1219. Cited by: §A.5, §A.6, Algorithm 3, Algorithm 3. Hazan and Jaakkola (2012) T. Hazan and T. Jaakkola On the partition function and random maximum a-posteriori perturbations. In Proceedings of the 29th International Conference on Machine Learning, p. 1667–1674. External Links: Link Cited by: §A.1. HiDream.ai (2026) HiDream.ai HiDream-O1-Image. Note: Hugging Face model cardAccessed: 2026-05-20 External Links: Link Cited by: item (i), §5.2.1. Hu and Zhang (2022) Y. Hu and L. Zhang Achieving long-term fairness in sequential decision making. In Proceedings of the AAAI Conference on Artificial Intelligence, Vol. 36, p. 9549–9557. Cited by: §A.1. Ioffe (2010) S. Ioffe Improved consistent sampling, weighted minhash and L1 sketching. In 2010 IEEE International Conference on Data Mining, p. 246–255. External Links: Document Cited by: §A.1. Ji et al. (2025) J. Ji, T. Qiu, B. Chen, B. Zhang, H. Lou, K. Wang, Y. Duan, Z. He, L. Vierling, D. Hong, J. Zhou, Z. Zhang, F. Zeng, J. Dai, X. Pan, K. Y. Ng, A. O’Gara, H. Xu, B. Tse, J. Fu, S. McAleer, Y. Yang, Y. Wang, S. Zhu, Y. Guo, and W. Gao AI alignment: a comprehensive survey. arXiv preprint arXiv:2310.19852. Note: Version 6; first posted in 2023 External Links: Document, Link Cited by: §A.1, §1. Keskar et al. (2019) N. S. Keskar, B. McCann, L. R. Varshney, C. Xiong, and R. Socher Ctrl: a conditional transformer language model for controllable generation. arXiv preprint arXiv:1909.05858. Cited by: §A.1. Khalifa et al. (2021) M. Khalifa, H. Elsahar, and M. Dymetman A distributional approach to controlled text generation. In International Conference on Learning Representations, External Links: Link Cited by: §A.1. Klare et al. (2012) B. F. Klare, M. J. Burge, J. C. Klontz, R. W. V. Bruegge, and A. K. Jain Face recognition performance: role of demographic information. IEEE Transactions on information forensics and security 7 (6), p. 1789–1801. Cited by: §A.1, §5.2.3. Kool et al. (2019) W. Kool, H. van Hoof, and M. Welling Stochastic beams and where to find them: the Gumbel-top-k trick for sampling sequences without replacement. In Proceedings of the 36th International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 97, p. 3499–3508. External Links: Link Cited by: §A.1. Kyung et al. (2025) D. Kyung, H. Chung, S. Bae, J. Kim, J. H. Sohn, T. Kim, S. K. Kim, and E. Choi PatientSim: a persona-driven simulator for realistic doctor-patient interactions. In The Thirty-Ninth Annual Conference on Neural Information Processing Systems Datasets and Benchmarks Track, Note: Spotlight External Links: Link Cited by: §5.2.5. Lebrun (2013) R. Lebrun Efficient time/space algorithm to compute rectangular probabilities of multinomial, multivariate hypergeometric and multivariate pólya distributions. Statistics and Computing 23 (5), p. 615–623. Cited by: §A.5. Lehmann and Casella (1998) E. L. Lehmann and G. Casella Theory of point estimation. Springer. Cited by: §6. Levin (1981) B. Levin A representation for multinomial cumulative distribution functions. The Annals of Statistics, p. 1123–1126. Cited by: §A.5. Liao et al. (2024) Y. Liao, Y. Meng, Y. Wang, H. Liu, Y. Wang, and Y. Wang Automatic interactive evaluation for large language models with state aware patient simulator. arXiv preprint arXiv:2403.08495. External Links: Document, Link Cited by: §5.2.5. Lindon and Malek (2022) M. Lindon and A. Malek Anytime-valid inference for multinomial count data. Advances in Neural Information Processing Systems 35, p. 2817–2831. Cited by: §A.3, §A.3. Lipton et al. (2018) Z. Lipton, Y. Wang, and A. Smola Detecting and correcting for label shift with black box predictors. In International conference on machine learning, p. 3122–3130. Cited by: §A.4, §6, Remark 15. Lu and Zhong (2024) H. Lu and F. Zhong Can vision-language models replace human annotators: a case study with celeba dataset. External Links: 2410.09416, Document Cited by: §A.7.2. Lu et al. (2023) Y. Lu, L. Chen, Y. Zhang, M. Shen, H. Wang, X. Wang, C. van Rechem, T. Fu, and W. Wei Machine learning for synthetic data generation: a review. arXiv preprint arXiv:2302.04062. Cited by: §A.1. Luce (1959) R. D. Luce Individual choice behavior: a theoretical analysis. John Wiley & Sons, New York. Cited by: §A.1. Maddison et al. (2014) C. J. Maddison, D. Tarlow, and T. Minka A* sampling. In Advances in Neural Information Processing Systems, Vol. 27, p. 3086–3094. External Links: Link Cited by: §A.1. Maddison (2016) C. J. Maddison A Poisson process model for Monte Carlo. In Perturbations, Optimization, and Statistics, T. Hazan, G. Papandreou, and D. Tarlow (Eds.), p. 193–232. External Links: Document Cited by: §A.1. Maslej et al. (2025) N. Maslej, L. Fattorini, R. Perrault, Y. Gil, V. Parli, N. Kariuki, E. Capstick, A. Reuel, E. Brynjolfsson, J. Etchemendy, et al. Artificial intelligence index report 2025. arXiv preprint arXiv:2504.07139. Cited by: §6. Mehrabi et al. (2021) N. Mehrabi, F. Morstatter, N. Saxena, K. Lerman, and A. Galstyan A survey on bias and fairness in machine learning. ACM computing surveys (CSUR) 54 (6), p. 1–35. Cited by: §1. Menon and Ong (2016) A. Menon and C. S. Ong Linking losses for density ratio and class-probability estimation. In International Conference on Machine Learning, p. 304–313. Cited by: §A.6.2. Mumuni et al. (2024) A. Mumuni, F. Mumuni, and N. K. Gerrar A survey of synthetic data augmentation methods in machine vision. Machine Intelligence Research 21 (5), p. 831–869. Cited by: §A.1, §1. Neumann et al. (2025) A. Neumann, E. Kirsten, M. B. Zafar, and J. Singh Position is power: system prompts as a mechanism of bias in large language models (llms). In Proceedings of the 2025 ACM Conference on Fairness, Accountability, and Transparency, p. 573–598. Cited by: §1. Nguyen et al. (2010) X. Nguyen, M. J. Wainwright, and M. I. Jordan Estimating divergence functionals and the likelihood ratio by convex risk minimization. IEEE Transactions on Information Theory 56 (11), p. 5847–5861. Cited by: §A.6.2. Oberst and Sontag (2019) M. Oberst and D. Sontag Counterfactual off-policy evaluation with Gumbel-Max structural causal models. In Proceedings of the 36th International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 97, p. 4881–4890. External Links: Link Cited by: §A.1. OpenAI (2026a) OpenAI Images and vision. Note: https://developers.openai.com/api/docs/guides/images-visionAccessed 2026-06-27 Cited by: §A.7.2. OpenAI (2026b) OpenAI Using GPT-5.5. Note: OpenAI API documentationAccessed: 2026-05-20 External Links: Link Cited by: §A.7.2, §A.7.2, §A.7.5, §5.2.1. Ouyang et al. (2022) L. Ouyang, J. Wu, X. Jiang, D. Almeida, C. Wainwright, P. Mishkin, C. Zhang, S. Agarwal, K. Slama, A. Ray, J. Schulman, J. Hilton, F. Kelton, L. Miller, M. Simens, A. Askell, P. Welinder, P. F. Christiano, J. Leike, and R. Lowe Training language models to follow instructions with human feedback. In Advances in Neural Information Processing Systems, Vol. 35. External Links: Document, Link Cited by: §1. Pan et al. (2025) B. Pan, Y. Li, W. Zhang, W. Lu, M. Xu, S. Zhou, Y. Zhu, M. Zhong, and T. Qian A survey on training-free alignment of large language models. In Findings of the Association for Computational Linguistics: EMNLP 2025, p. 4445–4461. External Links: Document, Link Cited by: §A.1, §1, §1. Papandreou and Yuille (2011) G. Papandreou and A. L. Yuille Perturb-and-MAP random fields: using discrete optimization to learn and sample from energy models. In 2011 International Conference on Computer Vision, p. 193–200. External Links: Document Cited by: §A.1. Patrini et al. (2017) G. Patrini, A. Rozza, A. Krishna Menon, R. Nock, and L. Qu Making deep neural networks robust to label noise: a loss correction approach. In Proceedings of the IEEE conference on computer vision and pattern recognition, p. 1944–1952. Cited by: §6. Plackett (1975) R. L. Plackett The analysis of permutations. Journal of the Royal Statistical Society: Series C (Applied Statistics) 24 (2), p. 193–202. External Links: Document Cited by: §A.1. Qwen Team (2025) Qwen Team Qwen-Image-2512: finer details, greater realism. Note: Hugging Face model cardAccessed: 2026-05-20 External Links: Link Cited by: item (i), §5.2.1. Rafailov et al. (2023) R. Rafailov, A. Sharma, E. Mitchell, C. D. Manning, S. Ermon, and C. Finn Direct preference optimization: your language model is secretly a reward model. In Advances in Neural Information Processing Systems, Vol. 36. External Links: Document, Link Cited by: §1. Raghunathan et al. (2003) T. E. Raghunathan, J. P. Reiter, and D. B. Rubin Multiple imputation for statistical disclosure limitation. Journal of Official Statistics 19 (1), p. 1–16. External Links: Link Cited by: §A.1, §1. Rajabi and Garibay (2022) A. Rajabi and O. O. Garibay Tabfairgan: fair tabular data generation with generative adversarial networks. Machine Learning and Knowledge Extraction 4 (2), p. 488–501. Cited by: §1. Ramesh et al. (2022) A. Ramesh, P. Dhariwal, A. Nichol, C. Chu, and M. Chen Hierarchical text-conditional image generation with clip latents. arXiv preprint arXiv:2204.06125. Cited by: §1. Rashidian et al. (2025) S. Rashidian, N. Li, J. Amar, J. H. Lee, S. Pugh, E. Yang, G. Masterson, M. Cha, Y. Jia, and A. Vaid AI agents for conversational patient triage: preliminary simulation-based evaluation with real-world ehr data. arXiv preprint arXiv:2506.04032. External Links: Document, Link Cited by: §5.2.5. Reichenpfader and Denecke (2024) D. Reichenpfader and K. Denecke Simulating diverse patient populations using patient vignettes and large language models. In Proceedings of the First Workshop on Patient-Oriented Language Processing (CL4Health) @ LREC-COLING 2024, D. Demner-Fushman, S. Ananiadou, P. Thompson, and B. Ondov (Eds.), Torino, Italia, p. 20–25. External Links: Link Cited by: §5.2.5. Rubin (1993) D. B. Rubin Discussion: statistical disclosure limitation. Journal of Official Statistics 9 (2), p. 461–468. External Links: Link Cited by: §A.1, §1. Sagers et al. (2023) L. W. Sagers, J. A. Diao, L. Melas-Kyriazi, M. Groh, P. Rajpurkar, A. S. Adamson, V. Rotemberg, R. Daneshjou, and A. K. Manrai Augmenting medical image classifiers with synthetic data from latent diffusion models. arXiv preprint arXiv:2308.12453. Cited by: §A.7.2. Sattigeri et al. (2019) P. Sattigeri, S. C. Hoffman, V. Chenthamarakshan, and K. R. Varshney Fairness gan: generating datasets with fairness properties using a generative adversarial network. IBM Journal of Research and Development 63 (4/5), p. 3–1. Cited by: §A.1. Schick et al. (2021) T. Schick, S. Udupa, and H. Schütze Self-diagnosis and self-debiasing: a proposal for reducing corpus-based bias in nlp. Transactions of the Association for Computational Linguistics 9, p. 1408–1424. Cited by: footnote 1. Schroff et al. (2015) F. Schroff, D. Kalenichenko, and J. Philbin Facenet: a unified embedding for face recognition and clustering. In Proceedings of the IEEE conference on computer vision and pattern recognition, p. 815–823. Cited by: §5.2.3. Shen et al. (2023) X. Shen, C. Du, T. Pang, M. Lin, Y. Wong, and M. Kankanhalli Finetuning text-to-image diffusion models for fairness. arXiv preprint arXiv:2311.07604. Cited by: §A.1. Shin et al. (2024) P. W. Shin, J. J. Ahn, W. Yin, J. Sampson, and V. Narayanan Can prompt modifiers control bias? a comparative analysis of text-to-image generative models. arXiv preprint arXiv:2406.05602. Cited by: item (i). Shrestha et al. (2024) R. Shrestha, Y. Zou, Q. Chen, Z. Li, Y. Xie, and S. Deng Fairrag: fair human generation via fair retrieval augmentation. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, p. 11996–12005. Cited by: §A.1. Shumailov et al. (2024) I. Shumailov, Z. Shumaylov, Y. Zhao, N. Papernot, R. Anderson, and Y. Gal AI models collapse when trained on recursively generated data. Nature 631 (8022), p. 755–759. External Links: Document Cited by: §A.1. Sinha et al. (2021) A. Sinha, J. Song, C. Meng, and S. Ermon D2c: diffusion-decoding models for few-shot conditional generation. Advances in neural information processing systems 34, p. 12533–12548. Cited by: §A.1. Sousa et al. (2025) T. Sousa, B. Ries, and N. Guelfi Data augmentation in earth observation: a diffusion model approach. Information 16 (2), p. 81. Cited by: §A.7.2. Stöckl (2023) A. Stöckl Evaluating a synthetic image dataset generated with stable diffusion. In International Congress on Information and Communication Technology, p. 805–818. Cited by: §5.2.1. Teo et al. (2023) C. Teo, M. Abdollahzadeh, and N. M. Cheung On measuring fairness in generative models. Advances in Neural Information Processing Systems 36, p. 10644–10656. Cited by: §A.1. Teo et al. (2024a) C. T. Teo, M. Abdollahzadeh, X. Ma, and N. Cheung Fairqueue: rethinking prompt learning for fair text-to-image generation. Advances in Neural Information Processing Systems 37, p. 22878–22926. Cited by: §A.1, §1. Teo et al. (2024b) C. T. Teo, M. Abdollahzadeh, and N. Cheung FairTL: a transfer learning approach for bias mitigation in deep generative models. IEEE Journal of Selected Topics in Signal Processing 18 (2), p. 155–167. Cited by: §1. Tian et al. (2023) Y. Tian, L. Fan, P. Isola, H. Chang, and D. Krishnan Stablerep: synthetic images from text-to-image models make strong visual representation learners. Advances in Neural Information Processing Systems 36, p. 48382–48402. Cited by: §A.7.2, §5.2.1. Valvano et al. (2024) G. Valvano, A. Agostino, G. De Magistris, A. Graziano, and G. Veneri Controllable image synthesis of industrial data using stable diffusion. In Proceedings of the IEEE/CVF winter conference on applications of computer vision, p. 5354–5363. Cited by: §A.7.2. Von Neumann (1951) J. Von Neumann 13. various techniques used in connection with random digits. Appl. Math Ser 12 (36-38), p. 3. Cited by: §A.2.1. Wald (1950) A. Wald Statistical decision functions. In Breakthroughs in Statistics: Foundations and Basic Theory, p. 342–357. Cited by: §6. Wu et al. (2025) C. Wu, J. Li, J. Zhou, J. Lin, K. Gao, K. Yan, S. Yin, S. Bai, X. Xu, Y. Chen, et al. Qwen-image technical report. arXiv preprint arXiv:2508.02324. Cited by: item (i). Wyllie et al. (2024) S. Wyllie, I. Shumailov, and N. Papernot Fairness feedback loops: training on synthetic data amplifies bias. In Proceedings of the 2024 ACM Conference on Fairness, Accountability, and Transparency, p. 2113–2147. Cited by: §1. Xie et al. (2026) M. Xie, J. Xiao, Z. Kou, Z. Li, G. Niu, and M. Sugiyama Are multimodal large language models good annotators for image tagging?. External Links: 2602.20972 Cited by: §A.7.2. Xu et al. (2018) D. Xu, S. Yuan, L. Zhang, and X. Wu Fairgan: fairness-aware generative adversarial networks. In 2018 IEEE international conference on big data (big data), p. 570–575. Cited by: §A.1, §1. Xu et al. (2019) D. Xu, S. Yuan, L. Zhang, and X. Wu Fairgan+: achieving fair data generation and classification through generative adversarial nets. In 2019 IEEE international conference on big data (Big Data), p. 1401–1406. Cited by: §A.1. Yellott (1977) J. I. Yellott The relationship between Luce’s Choice Axiom, Thurstone’s Theory of Comparative Judgment, and the double exponential distribution. Journal of Mathematical Psychology 15 (2), p. 109–144. External Links: Document Cited by: §A.1. Yu et al. (2020) N. Yu, K. Li, P. Zhou, J. Malik, L. Davis, and M. Fritz Inclusive gan: improving data and minority coverage in generative models. In European Conference on Computer Vision, p. 377–393. Cited by: §1. Zhang et al. (2023) C. Zhang, X. Chen, S. Chai, C. H. Wu, D. Lagun, T. Beeler, and F. De la Torre Iti-gen: inclusive text-to-image generation. In Proceedings of the IEEE/CVF International Conference on Computer Vision, p. 3969–3980. Cited by: §A.1, §A.1. Zhao et al. (2021) J. Zhao, D. Khashabi, T. Khot, A. Sabharwal, and K. Chang Ethical-advice taker: do language models understand natural language interventions?. In Findings of the Association for Computational Linguistics: ACL-IJCNLP 2021, p. 4158–4164. Cited by: §1, item (i). Zheng et al. (2023) C. Zheng, G. Wu, and C. Li Toward understanding generative data augmentation. Advances in neural information processing systems 36, p. 54046–54060. Cited by: §A.4. Appendix A Appendix A.1 Additional related work Distributional and training-free alignment. The alignment literature spans objectives concerning instructions, preferences, safety, and values (Ji et al., 2025), as well as methods that act before, during, or after decoding without additional training (Pan et al., 2025). Distributional constraints also arise in controlled generation: Khalifa et al. (2021) formulate pointwise and distributional constraints on text, characterize a target law that minimizes KL divergence from a pretrained language model, and train a new model to approximate that law. Our setting instead concerns a fixed generator available only through sampling, with unknown source attribute probabilities. We seek guarantees for the joint attribute law of a selected sample and characterize the number of model queries required to attain them. Input-side controls, including conditional generation (Keskar et al., 2019) and learned soft prompts, may change the source distribution to which our procedures are applied; the access required by such controls depends on the method. Synthetic data for training and inference. The statistical literature on synthetic microdata emphasizes the connection between the synthesis mechanism and valid downstream analysis (Rubin, 1993; Raghunathan et al., 2003). Recent surveys discuss generative augmentation for learning (Chen et al., 2024b; Mumuni et al., 2024) and the assumptions needed for synthetic data to support statistical inference (Abdel-Azim et al., 2026); applications in healthcare raise related questions of utility and distributional fidelity (Giuffrè and Shung, 2023; Lu et al., 2023). Repeated training on generated data can also distort a learned distribution (Shumailov et al., 2024). SAA addresses a specified attribute mismatch in the resulting generator, including one previously trained toward a different target, rather than all sources of synthesis error. Prediction-powered inference (Angelopoulos et al., 2023) and synthetic-powered predictive and general inference (Bashari et al., 2025b; Bashari et al., 2025a) use real observations to support inference despite imperfect auxiliary predictions or synthetic data. Our contribution is complementary to these inferential corrections: it concerns sample construction before downstream use. Under a shared attribute-conditional model, Section A.4 makes this connection precise through a bound on bounded downstream criteria. Distributional fairness as an application. Recent works (Choi et al., 2020; Zhang et al., 2023; Teo et al., 2023, see, e.g.,) have adopted sampling-based or distributional fairness objectives, but they do not study the same black-box post-processing setting or prove similar optimality results established in our work. We retain this application-specific perspective in the following review of approaches to fairness in generative models. Fair synthetic data augmentation. A substantial early line of fairness-aware generative modeling predates modern diffusion models and treats the generator primarily as a mechanism for producing synthetic data that improves downstream fairness. Xu et al. (2018) propose FairGAN, a GAN-based framework for learning a generator whose samples remain close to the original data distribution while reducing the dependence between generated records and protected attributes. The aim is not merely to generate plausible data, but to generate data on which downstream classifiers exhibit improved fairness when trained on the synthetic sample. Xu et al. (2019) extend this idea in FairGAN+ by coupling the generator with a classifier and additional adversarial components, so that the model jointly pursues fair data generation and fair downstream classification. Sattigeri et al. (2019) develop a related auxiliary-classifier GAN formulation that targets group fairness criteria such as demographic parity and equality of opportunity, and demonstrate the approach on both tabular and image-like data. Amini et al. (2019) take a different generative route: rather than training a GAN to output fair synthetic data, they use a variational autoencoder to learn latent structure in the training distribution and then adaptively upweight underrepresented regions during model training, with applications to racial and gender bias in face detection. These works are important because they show that generative models can be used to repair biased datasets or improve fairness of downstream predictors. However, they are different from the black-box post-processing setting we pursue, as they are training-time or data-generation interventions and assume access to the training procedure, to a dataset to be modified, or to internal model components. Adversarial generative modeling for fairness. Another line of adversarial generative work explicitly uses information-theoretic objectives to reduce the dependence between sensitive attributes and generated or predicted quantities. Chen et al. (2024a) propose an information-minimizing GAN for fair generation and classification, in which the generator and classifier are trained jointly so as to reduce mutual-information-type dependence involving sensitive attributes while preserving classification utility. Their method also introduces an ANOVA-based latent factor to mitigate accuracy loss, and the resulting framework is designed to improve downstream fair classification from generated data. This is related to our work in its use of generative modeling to address fairness, but the object of control is different. Information-minimizing GANs aim to remove sensitive-attribute information from learned representations or downstream predictions, whereas our target distribution may assign positive mass to protected attributes and asks for the returned samples to follow that target law. For example, in a text-to-image application, our goal may be to generate a batch whose gender, race, or age annotations follow a specified distribution, not to make those attributes uninformative or unrecoverable from the images. Few-shot and conditional generative modeling for fairness. Few-shot and conditional generative modeling provide another route to more balanced generation. Sinha et al. (2021) introduce D2C, a diffusion-decoding framework that combines an unconditional VAE, a learned diffusion prior over latent representations, and contrastive representations to enable few-shot conditional image generation. Because D2C can adapt an unconditional generator to new labels or manipulation constraints using a small labeled set, it can in principle be used to increase the number of samples from rare or desired attributes. Furthermore, Zhang et al. (2023) develop an input-side procedure that learns and appends attribute-specific soft tokens to hard prompts. This is also an approach that requires white-box access. Moreover, Teo et al. (2024a) introduces a gray-box method that interweaves hard prompts and fairness-aware prompts during the decoding process. Shrestha et al. (2024) use retrieval augmentation and a learned module that projects reference images into the text-embedding space; this likewise requires more than black-box output sampling. Fairness for T2I diffusion models. For text-to-image diffusion models, several recent works intervene directly in the diffusion model or in the prompting mechanism. Friedrich et al. (2023) propose Fair Diffusion, a deployment-time approach for steering text-to-image diffusion models by adding fairness-aware guidance so that generated images can be shifted toward desired proportions of identity groups. This work is important because it demonstrates that fairness interventions can be applied after pretraining and need not require full retraining of the text-to-image model. Nevertheless, Fair Diffusion still relies on access to the diffusion sampling process and modifies the generation dynamics themselves. De Simone et al. (2023) introduce DiffusionWorldViewer, an interactive system for exposing the “worldview” reflected by a text-to-image model and allowing users to edit generated outputs toward alternative demographic compositions. Their work is especially close in spirit to our user-specified target distribution: rather than assuming a single universal definition of fairness, DiffusionWorldViewer lets users inspect the demographic distribution produced by a model and then adjust prompts or editing controls to represent a desired perspective. This is consistent with our view that q should be supplied by the user or application context rather than imposed universally. Shen et al. (2023) also formulate fairness for text-to-image diffusion models as distributional alignment. They introduce a distributional alignment loss that steers generated attributes toward a user-defined target distribution, together with an adjusted direct fine-tuning method for optimizing losses defined on generated images. Empirically, their approach reduces gender, race, and intersectional biases for occupational prompts, and it can represent target distributions beyond exact parity, such as simultaneously debiasing some attributes while setting a nonuniform target for another. This is one of the closest source-side analogues of our target-distribution framework. However, it requires fine-tuning the diffusion model or its soft tokens and therefore assumes substantially more access than black-box sampling. Choi et al. (2024) study fair sampling in diffusion models through an attribute-switching mechanism. Their method changes the diffusion sampling path by switching sensitive attributes during generation, and they provide theoretical and empirical evidence that this can produce fair synthetic data while preserving utility, without requiring additional model training. The fairness notion they use is connected to the ε -fairness framework of Feldman et al. (2015), where a representation is considered fair when the protected attribute cannot be accurately inferred from the remaining information. In the binary case discussed in this line of work, a predictor f:→f:X must have sufficiently large balanced error, expressed through conditions such as P(f(X)=0∣A=1)+P(f(X)=1∣A=0)>2εP(f(X)=0 A=1)+P(f(X)=1 A=0)>2 . This criterion is substantively different from ours. Attribute switching and ε -fairness aim to obscure or remove information about protected attributes, whereas our target-law sampling objective matches the output attribute distribution with a specified target law. Moreover, the switching mechanism is tailored to diffusion sampling, while our algorithms are model-agnostic and apply to any generator from which one can obtain black-box M-samples. SAA as a complementary intervention. Altogether, these papers show that alignment for generative modeling in tasks like fairness and synthetic data augmentation has been approached through data repair, adversarial training, weak supervision, latent reweighting, diffusion guidance, prompt or interface design, fine-tuning, and specialized diffusion samplers. Our formulation of SAA isolates the downstream statistical problem faced by a user who can only query a black-box generator and post-process its outputs toward an application-specific attribute law. This perspective allows us to prove optimality and lower bound results that are independent of the architecture of the underlying generative model. In particular, the source-rate-free and universal optimality results of our RDC and TA-RDC methods (cf. Theorems 5 and 20) make our algorithms complementary to the methods above: the source rates p may differ between various fairness intervention methods, but our algorithms, which do not assume knowledge of these rates, can still provide exact or approximate statistical attribute alignment with first-order optimal model-query costs. Fairness constraints on attribute proportions and sequential decision making. In the context of algorithmic fairness, there are some provable guarantees for ensuring proportions of protected attributes (e.g., old/young) obey some bounds (Cano et al., 2025; Hu and Zhang, 2022; Alamdari et al., 2023) or that protected attributes appear relatively frequently (e.g., a particular attribute appears at least once for every β images produced, where β>0β>0 is a user-specified hyperparameter; see Cheng et al. (2025)). However, constraints on attribute proportions or frequencies need not ensure that the returned attributes follow a specified joint distribution, as we consider in our work. This distinction matters for downstream tasks such as pairwise audits, whose results depend on the distribution of pairs of outputs (Klare et al., 2012; Grother et al., 2019; Grother, 2022, see, e.g.,); see, also, Section 5.2.3. Exponential races and random-priority couplings. The exponential clock construction used in Definition 16 is a classical random-priority device. Let Ea:a∈\E_a:a \ be independent with Ea∼Exp(wa)E_a (w_a). For any fixed subset B⊆B with positive total weight, Pr(argmina∈BEa=b)=wb/∑a∈Bwa ( _a∈ BE_a=b)=w_b/ _a∈ Bw_a. Hence one clock field simultaneously gives a draw from the weights normalized on every fixed subset; the same statement holds conditionally for a random subset independent of the clocks. This competing-exponentials rule underlies race-based event simulation, including the stochastic simulation algorithm of Gillespie (1976). In discrete-choice language, the winner follows Luce’s proportional-choice rule (Luce, 1959), while ordering all clocks gives the Plackett–Luce ranking law (Plackett, 1975). It is also equivalent to the Gumbel-max trick: writing Ea=Za/waE_a=Z_a/w_a with Za∼i.i.d.Exp(1)Z_a i.i.d. Exp(1) gives argminaEa=argmaxalogwa+Ga _aE_a= _a\ w_a+G_a\, where Ga=−logZaG_a=- Z_a are i.i.d. standard Gumbel variables (Yellott, 1977). In machine learning, this representation is part of the broader perturb-and-MAP framework, which uses random perturbations to reduce sampling or partition-function calculations to optimization (Papandreou and Yuille, 2011; Hazan and Jaakkola, 2012). For our purposes, a particularly close connection is the Gumbel-process framework of Maddison et al. (2014); Maddison (2016), which extends Gumbel-max to general spaces and couples maximizers over many measurable subsets. Equivalent exponential or Gumbel keys appear in weighted sampling without replacement and reservoir sampling (Efraimidis and Spirakis, 2006); taking the top k perturbed scores gives Gumbel-top-k sampling and the associated Plackett–Luce order (Kool et al., 2019). Related persistent-randomness couplings arise in consistent weighted sampling and weighted MinHash (Ioffe, 2010), and in counterfactual models that share Gumbel variables across interventions (Oberst and Sontag, 2019). Our use differs in the object being coupled. The target law ν is fixed, while the source stream generates a nested random family of feasible supports tt≥m≔Ωt\Ωt−1t≥m\D_t\_t≥ m \ _t _t-1\_t≥ m (cf. Equation 3), independently of the clock field. Restricting one target-weighted priority field to Ωt _t yields the count-conditional output attribute law ν(⋅∣Ωt)ν(· _t) at every deterministic time t≥mt≥ m. Once the global minimum-clock target sequence becomes feasible, it remains selected and has law ν, giving the RDC stopping time; see Theorem 17. In our setting, the clocks therefore combine a classical priority construction with the feasibility constraints imposed by a coupon-collector type process, yielding an optimal count-conditional distortion frontier. A.2 Additional algorithms for exact sampling A.2.1 Universally exact algorithms with known source rates In this section, we state the traditional oracle sampler introduced in Von Neumann (1951) that assumes knowledge of the source rates p and connect it with our problem formalization. For the target joint law ν=q⊗mν=q m, we demonstrate that oracle rejection sampling is universally exact and achieves the minimum possible M-cost among all universally exact algorithms. Definition 21 (Oracle rejection sampler). Fix an input x and a generative model P from which we can sample outputs via P(⋅∣x)P(· x). Assume the support condition supp(q)⊆supp(p) supp(q) supp(p). Define c(x)≔mini∈supp(q)piqi=(maxi∈supp(q)qipi)−1.c(x) _i∈ supp(q) p_iq_i= ( _i∈ supp(q) q_ip_i )^-1. The oracle sampler proceeds as follows. Repeat until acceptance: 1. Query an M-sample Y∼P(⋅∣x)Y P(· x) and compute its attribute I=ϕ(Y)I=φ(Y). 2. Draw an independent E-sample U∼Unif[0,1]U [0,1]. 3. Accept Y if U≤rI,whereri≔c(x)⋅qipi,i∈supp(q),0,i∉supp(q).U≤ r_I, r_i casesc(x)· q_ip_i,&i∈ supp(q),\\[6.0pt] 0,&i∉ supp(q). cases Otherwise, reject and repeat. To produce m outputs, the procedure is run independently until m samples have been accepted. Each iteration uses one model query and succeeds with probability c(x)c(x). Hence, the number of model queries required per accepted sample is geometric with mean 1c(x). 1c(x). and, consequently, the M-cost to produce m samples is mOracleRS(p,q)=m⋅1c(x)=m⋅maxi∈supp(q)qipi.C_m^OracleRS(p,q)=m· 1c(x)=m· _i∈ supp(q) q_ip_i. (23) Furthermore, the oracle rejection sampler is universally exact since, for an arbitrary source rate p∈Δk−1p∈ ^k-1, a single proposal is accepted with probability Pr(accept∣x)=∑i∈supp(q)pi⋅ri=∑i∈supp(q)pi⋅c(x)qipi=c(x). (accept x)= _i∈ supp(q)p_i· r_i= _i∈ supp(q)p_i· c(x)q_ip_i=c(x). Moreover, conditioning on acceptance, the attribute distribution of the output satisfies Pr(ϕ(Y)=i∣x)=pi⋅ri∑j∈supp(q)pj⋅rj=qi,∀i∈supp(q). (φ(Y)=i x)= p_i· r_i _j∈ supp(q)p_j· r_j=q_i, ∀ i∈ supp(q). Thus, the oracle sampler sequentially produces i.i.d. outputs whose attributes follow the marginal law q of the target joint law ν=q⊗mν=q m. The oracle rejection sampler adaptively stops after a random number of proposals, so that it lies in m A_m. The next result records the optimality of the oracle sampler. Proposition 22 (Optimality for universal sampling with known source rates). Assume the support condition supp(q)⊆supp(p) supp(q) supp(p) and denote the pointwise M-cost of a black-box post-processing algorithm Algm∈m Alg_m∈ A_m as mAlgm(p,q)=p[N]C_m Alg_m(p,q)= _p[N]. Then, the pointwise optimal universal cost satisfies infAlgm∈m(q⊗m)mAlgm(p,q)=m⋅maxi∈supp(p)qipi. _ Alg_m∈ U_m(q m)C_m Alg_m(p,q)=m· _i (p) q_ip_i. The infimum is achieved by the oracle rejection sampler in Definition 21. The result immediately follows from Theorem 8 (note that ∑j=1mνj(i)=m⋅qi _j=1^m _j(i)=m· q_i for ν=q⊗mν=q m), and the M-cost of the oracle rejection sampler recorded in Equation 23. A.2.2 Universally exact source-rate-free algorithms Every post-processing algorithm returns attribute sequences from the feasible support Ωm(C→(t)) _m( C(t)) of Equation 3 after t≥mt≥ m M-samples. For the purpose of minimizing M-cost, it suffices to characterize the algorithm’s behavior through its count-conditional output count law (cf. Equation 31), which is the probability law on count vectors ℓ→∈ℒm≔ℓ→∈ℕ≥0k:∑i=1kℓi=m _m \ _≥ 0^k: _i=1^k _i=m \ induced by the count-conditional output attribute law of Equation 8. Indeed, given returned counts ℓ→∈ℒm _m, sampling the target joint law ν conditional on these returned counts A~∼ν(⋅∣L→=ℓ→) A ν(· \ L= \) preserves feasibility and M-cost, where Li=∑j=1m1A~j=iL_i= _j=1^m1\ A_j=i\ are the attribute counts of the output attribute sequence. Consequently, we consider variables xc→,ℓ→x_ c, which are jointly indexed by the source and returned count vectors c→(t)∈ℕ≥0k:∑i=1kci=tandℓ→∈ℒm:ℓi≤ci(t),∀i∈[k]. \ c(t) _≥ 0^k: _i=1^kc_i=t \ \ _m: _i≤ c_i(t),\ ∀ i∈[k] \. At each source count vector c→ c, a post-processing algorithm can also elect to continue M-sampling and not return any outputs. The variables xc→,ℓ→x_ c, and continuation variables yc→y_ c for t≥mt≥ m then constitute the primary variables of an optimization problem. Let ρν(ℓ→)≔∑a→∈m:∑r=1m1ar=i=ℓi,∀i∈[k]ν(a→),ℓ→∈ℒm _ν( ) _ subarrayc a ^m: _r=1^m1\a_r=i\= _i,\ ∀ i∈[k] subarrayν( a), _m denote the law over the count vectors induced by the target joint law ν. Additionally, abbreviate pc→=∏i=1kpicip c= _i=1^kp_i^c_i. Then, at a designated source rate p0p_0, the minimum universally exact source-rate-free M-cost is the value of the following linear program infxc→,ℓ→,yc→≥0 _\x_ c, ,y_ c≥ 0\ ∑ℓ→∈ℒm∑c→≥ℓ→|c→|xc→,ℓ→p0c→ _ _m _ c≥ | c|x_ c, p_0 c s.t. y0→=1, y_ 0=1, yc→+∑ℓ→∈ℒm:ℓ→≤c→xc→,ℓ→=∑i:ci>0yc→−e→i,c→≠0→, y_ c+ _ subarrayc _m: ≤ c subarrayx_ c, = _i:c_i>0y_ c- e_i, c≠ 0, ∑c→≥ℓ→xc→,ℓ→⋅pc→=ρν(ℓ→),ℓ→∈ℒm,p∈Δk−1:supp(ν)⊆(supp(p))m. _ c≥ x_ c, · p c= _ν( ), _m, p∈ ^k-1:supp(ν) (supp(p))^m. (24) Equation 24 imposes universal exactness through a global constraint on a continuum of source rates. Furthermore, for universal exactness, the stopping time cannot have a deterministic finite upper bound. Theorem 23 (No capped-budget universal exactness). Fix m≥1m≥ 1, k≥2k≥ 2, and a target joint law ν. Suppose a source-rate-free algorithm Algm∈mo Alg_m∈ A_m^o satisfies N≤nN≤ n almost surely for some deterministic n<∞n<∞. Then the set of interior source rates p for which PAlgm(A~∣x)=νP_ Alg_m( A x)=ν has Lebesgue measure zero. In particular, an algorithm with a capped-budget n∈ℕn fails to be exact for almost every interior source rate p. For the proof, see Section A.8.9. Consequently, the primal program has infinitely many variables, with their number growing combinatorially with the number of M-samples. Together with the continuum of globally coupled constraints in (24), this makes the program difficult to solve, and standard finite-state constrained Markov decision process methods do not directly apply (Altman, 2021, see, e.g.,). A.3 Additional algorithms for approximate sampling We consider the following heuristic solution to finding universally approximate source-rate-free procedures that minimize the M-cost (cf. Definition 12) under a target joint law ν=q⊗mν=q m. First, estimate the source rates on an adaptively sized pilot sample, then freeze the estimates, and finally run ordinary rejection sampling on freshly drawn M-samples using the estimated source rates. We call this procedure approximate rejection sampling (ARS). Anytime confidence set and stopping time rule. To estimate the source rates, we construct anytime-valid multinomial confidence sequences as developed in Lindon and Malek (2022) and use a relative width stopping time rule (Chow and Robbins, 1965; Flegal and Gong, 2015, see, e.g.,). More formally, let Ci(t)=∑s=1t1ϕ(Ys)=iC_i(t)= _s=1^t1\φ(Y_s)=i\ be the source count process (cf. Equation 3) and p^i(t)=Ci(t)/t p_i(t)=C_i(t)/t be the empirical plug-in estimates for the source-rates. Following Lindon and Malek (2022), for u∈Δk−1u∈ ^k-1, define the confidence set t(δCS)=u∈Δk−1:ℰt(u)<δCS−1,ℰt(u)=B(1→+C→(t))B(1→)∏i=1kui−Ci(t),P_t( _ CS)= \u∈ ^k-1:E_t(u)< _ CS^-1 \, _t(u)= B( 1+ C(t))B( 1) _i=1^ku_i^-C_i(t), (25) where B is the multivariate beta function. In particular, the anytime guarantee holds Prpp∈t(δCS)∀t≥1−δCS _p\p _t( _ CS)\ ∀ t\≥ 1- _ CS. Let Li(t)=infu∈t(δCS)ui,Ui(t)=supu∈t(δCS)uiL_i(t)= _u _t( _ CS)u_i, U_i(t)= _u _t( _ CS)u_i be its coordinate projections. Then, given a deterministic set of look times G, the pilot stopping time is τγ=inft∈:maxi∈[k]Ui(t)−Li(t)2p^i(t)≤γ, _γ= \t : _i∈[k] U_i(t)-L_i(t)2 p_i(t)≤γ \, with the convention that the maximum is +∞+∞ until every empirical rate is positive. Thus, γ is a tuning parameter, with smaller values corresponding to more precise source-rate estimates and pilot samples. Approximate rejection sampling on fresh M-samples. At τγ _γ, freeze the empirical plug-in estimates for the source rates p^=p^(τγ) p= p( _γ) and set the empirical rejection sampling probabilities c^=mini∈supp(q)p^iqi,ai=c^qi/p^i,qi>0,0,qi=0. c= _i (q) p_iq_i, a_i= cases c\,q_i/ p_i,&q_i>0,\\ 0,&q_i=0. cases (26) The algorithm discards the pilot samples and performs rejection sampling on freshly drawn M-samples. Like the oracle rejection sampler (cf. Section A.2.1), ARS independently accepts a proposal of attribute i with probability aia_i and stops after m acceptances. Conditional on the stopped pilot ℱτγF_ _γ, the proposal acceptance probability and the output attribute law of the accepted samples are thus λ=∑i=1kpiai,si=PrpA~j=i∣ℱτγ=piaiλ.λ= _i=1^kp_ia_i, s_i= _p\ A_j=i _ _γ\= p_ia_iλ. (27) In other words, conditional on ℱτγF_ _γ, the attributes of the accepted outputs are i.i.d. draws from s, so that their count vector is Mult(m,s)Mult(m,s). If p^=p p=p, then s=qs=q and the procedure reduces to oracle rejection sampling. Details on the evaluation of the M-cost and statistical alignment discrepancy of ARS are deferred to Section A.6.4. Numerical results for a synthetic experiment can be found in Section A.7.1. A.4 Count-conditional discrepancy and synthetic data augmentation The count-conditional discrepancy is also relevant in synthetic data augmentation, where a downstream analysis is performed using a single augmented dataset. Suppose the model and target distributions satisfy a label shift condition on the attributes: A∼Categorical(p),Atar∼Categorical(q),Y∣A=a∼Ytar∣Atar=a∼Ka,A (p), A^tar (q), Y A=a Y^tar A^tar=a K_a, where KaK_a is the common attribute-conditional law for attribute a∈a ; see, for example, Lipton et al. (2018). Here, the target distribution describes the population that the synthetic data is intended to represent. Let Y→tar=(Y1tar,…,Yntartar) Y^tar=(Y_1^tar,…,Y_n_tar^tar) be an ideal dataset obtained by drawing A→tar∼q⊗ntar,Yjtar∣Ajtar=a∼Ka,j∈[ntar], A tar q n_tar, Y_j tar A_j tar=a K_a, j∈[n_tar], and let Y→⋆=(Y1⋆,…,Ym⋆) Y =(Y_1 ,…,Y_m ) be an ideal augmentation sample obtained by drawing an attribute sequence A→⋆∼q⊗m A q m with the same attribute-conditional laws KaK_a. Likewise, conditional on C→ C, let Y~=(Y~1,…,Y~m) Y=( Y_1,…, Y_m) be the returned synthetic sample obtained from A~∼PAlgmC→ A P_Alg_m C (cf. Equation 8) and the same attribute-conditional laws KaK_a. We consider post-processing algorithms whose stopping time and output selection rule depend only on annotated attributes and independent E-sampling, with returned outputs selected uniformly within each attribute, as in RDC and its anytime variants (cf. Algorithms 1 and 2). These procedures preserve the product of the attribute-conditional laws given the selected attributes and source counts C→ C. Then, for every bounded downstream criterion G:ntar+m→[0,1]G:Y^n_tar+m→[0,1], the data processing inequality through the common attribute-conditional laws gives, for each count vector c→ c of positive probability, |[G(Y→tar,Y~)∣C→=c→]−[G(Y→tar,Y→⋆)]|≤TV(PAlgmc→,q⊗m). |E [G( Y^tar, Y) C= c ]-E [G( Y^tar, Y ) ] | (P_Alg_m c,q m ). Averaging the absolute conditional difference over C→ C therefore bounds it by the count-conditional discrepancy. In particular, |[G(Y→tar,Y~)]−[G(Y→tar,Y→⋆)]| |E [G( Y^tar, Y) ]-E [G( Y^tar, Y ) ] | ≤C→[TV(PAlgmC→,q⊗m)]≡ΔTVC→(Algm,q⊗m,p), _ C [TV (P_Alg_m C,q m ) ]≡ _TV C(Alg_m;q m;p), (28) More specifically, write n~=ntar+m n=n_tar+m, and suppose that replacing one observation in the augmented dataset changes G by at most γn~ _ n. A maximal-coupling argument then strengthens (28) to |[G(Y→tar,Y~)]−[G(Y→tar,Y→⋆)]|≤(mγn~∧1)⋅ΔTVC→(Algm,q⊗m,p). |E [G( Y^tar, Y) ]-E [G( Y^tar, Y ) ] |≤ (m _ n 1 )· _TV C(Alg_m;q m;p). For example, an average of fixed, observation wise losses taking values in [0,1][0,1] has γn~=1/n~ _ n=1/ n, yielding the factor m/(ntar+m)m/(n_tar+m). Analogous distributional mismatch terms arise in stability bounds for generative data augmentation (Zheng et al., 2023, see, e.g., Theorem 3.1 of). A.5 Additional algorithms for anytime RDC In this section, we discuss how to efficiently compute the target mass of the feasible support αt≔ν(Ωm(C→(t))) _t ν( _m( C(t))) (cf. Definition 18) under the target joint law ν=q⊗mν=q m. We then discuss a variant of the TA-RDC algorithm (cf. Section 4.2), called RM (randomized-mass RDC), that modifies the output attribute law away from one that minimizes the count-conditional discrepancy. On a high level, RM constructs a stopping time rule whose survival probability function decreases linearly with the target mass of the feasible support αt _t. This results in stopping times that are stochastically no greater than that of TA-RDC. Under mild conditions, it provably reduces the M-cost while preserving TA-RDC’s universal unconditional discrepancy bound. Finally, we provide first-order optimal frontiers under TV and Hellinger distance, and discuss a simple randomized RDC/direct-sampling procedure that attains them. Computing the target mass of the feasible support. When ν=q⊗mν=q m, the target mass of the feasible support set ν(Ω)ν( ) (cf. Theorem 17 in Section 4) is exactly that of a multinomial c.d.f., α(c→)≡ν(Ω)=q⊗m(Ω)=PrL→∼Mult(m,q)(Li≤ci,∀i∈[k]).α( c)≡ν( )=q m( )= _ L (m,q) (L_i≤ c_i,~∀ i∈[k] ). Computing multinomial c.d.f.s has been extensively studied in computational statistics (see, e.g., Levin, 1981; Lebrun, 2013; Hayter, 2014, and references therein). Inspired by these works, we use recursion identities of multinomial c.d.f.s as in Hayter (2014) to compute these probabilities, and provide the full algorithm in Algorithm 3 for completeness. Algorithm 3 MultinomialCDF(h,q,r→)(h,q, r): (upper-rectangular) Multinomial c.d.f. probability via Hayter (2014) recursion 0: Integer h≥0h≥ 0, probability vector q∈Δk−1q∈ ^k-1, capacity vector r→∈ℤ≥0k r _≥ 0^k. 0: P=Pr[Li≤ri∀i∈[k]]P= [L_i≤ r_i~∀ i∈[k]] for L∼Mult(h,q)L (h,q). 1: if ∃i:ri<0∃ i:r_i<0 then 2: return 00. 3: end if 4: if h=0h=0 then 5: return 11. 6: end if 7: Let S←i∈[k]:qi>0S←\i∈[k]:q_i>0\. 8: Restrict q←(qi)i∈Sq←(q_i)_i∈ S and r→←(ri)i∈S r←(r_i)_i∈ S, and reset k←|S|k←|S|. 9: Coordinates with qi=0q_i=0 have Li=0L_i=0 almost surely and do not affect the multinomial c.d.f. 10: if ∑i=1kri<h _i=1^kr_i<h then 11: return 00. 12: end if 13: if k=1k=1 then 14: return r1≥h1\r_1≥ h\. 15: end if 16: Replace each rir_i by minri,h \r_i,h\. 17: if k=2k=2 then 18: Set a←max0,h−r2a← \0,h-r_2\ and b←minh,r1b← \h,r_1\. 19: return ∑x=ab(hx)q1xq2h−x _x=a^b hxq_1^xq_2^h-x. 20: end if 21: Define prefix and suffix capacity sums Bi≔∑j=1irjB_i _j=1^ir_j and Ri≔∑j=ikrjR_i _j=i^kr_j. 22: For i=1,…,k−1i=1,…,k-1, define the feasible domain i≔w∈ℤ:max0,h−Ri+1≤w≤minh,Bi.D_i \w : \0,h-R_i+1\≤ w≤ \h,B_i\ \. 23: Initialize gk−1(w)←1/(h−w)!g_k-1(w)← 1/(h-w)! for each w∈k−1w _k-1. 24: for i=k−2i=k-2 down to 11 do 25: For each w∈iw _i, set gi(w)←∑j=maxh−Ri+2,wminh,w+ri+1(qi+1qi+2)j1(j−w)!gi+1(j).g_i(w)← _j= \h-R_i+2,w\ \h,w+r_i+1\ ( q_i+1q_i+2 )^j 1(j-w)!g_i+1(j). 26: end for 27: Compute P←h!qkh∑j∈1(q1q2)j1j!g1(j).P← h!q_k^h _j _1 ( q_1q_2 )^j 1j!g_1(j). 28: return P. M-cost improvements over TA-RDC at a fixed discrepancy tolerance. We provide a universally (f,ε)(f, )-approximate algorithm that has the same unconditional discrepancy bound as TA-RDC (cf. Definition 18) while having a potentially smaller M-cost. Definition 24 (Randomized-mass RDC (RM)). Fix a target joint law ν on [k]m[k]^m. After t≥mt≥ m M-samples, let C→(t) C(t) be the accumulated source-count vector (cf. Equation 3) and set Ωt≔Ωm(C→(t)),Ωm−1≔∅,t≔Ωt∖Ωt−1, _t _m ( C(t) ), _m-1 , _t _t _t-1, where Ωm(C→(t)) _m ( C(t) ) is the feasible support (cf. Equation 3). Furthermore, fix a tolerance ε≥0 ≥ 0 and let θf,ε≔infa∈[0,1]:Ψf(a)≤ε. _f, \a∈[0,1]: _f(a)≤ \. If θf,ε>0 _f, >0, independently E-sample U∼Unif(0,1)U (0,1) and stop at Nf,εRM≔inft≥m:αt≥θf,ε⋅U,N_f, ^RM \t≥ m: _t≥ _f, · U\, (29) where αt=ν(Ωm(C→(t))) _t=ν ( _m( C(t)) ) is the target mass of the feasible support. At this time, E-sample output attributes from U→∼ν(⋅∣Nf,εRM) U ν(· _N_f, ^RM). If θf,ε=0 _f, =0, return the first m queried outputs instead. In general, RM may use any stopping time rule with conditional survival probability Pr(Nf,εRM>t|t)=(θf,ε−αt)+/θf,ε (N_f, ^RM>t |G_t )=( _f, - _t)_+/ _f, . For θf,ε>0 _f, >0, the likelihood ratio of RM’s output attribute law conditional on the entire source-count path is at most 1/θf,ε1/ _f, . Consequently, convexity of the f-divergence and averaging over source paths gives, for every interior source rate p, Δfun(RM,ν,p)≤Ψf(θf,ε)≤ε. _f^un(RM;ν;p)≤ _f( _f, )≤ . Moreover, for every t≥mt≥ m, Pr(Nf,εRM>t∣t)≤1αt<θf,ε(1−αt)=Pr(Nf,εTA-RDC>t∣t). (N_f, ^RM>t _t )≤ 1\ _t< _f, \(1- _t)= (N_f, ^TA -RDC>t _t ). Thus, RM is a universally (f,ε)(f, )-approximate algorithm whose M-cost is no greater than that of TA-RDC. The M-cost of RM is strictly less whenever 0<θf,ε<10< _f, <1 and Prp(0<αt<θf,ε)>0 _p(0< _t< _f, )>0 for some t≥mt≥ m. For example, if ν=q⊗mν=q m with q uniform on [k][k], k≥2k≥ 2, then αm=k−m _m=k^-m for the source count process with m identical attributes. Thus, the improvement is strict whenever k−m<θf,ε<1k^-m< _f, <1; for KL, θf,ε=e−ε _f, =e^- , so this holds for 0<ε<mlogk0< <m k. First-order optimal frontiers and algorithms under other divergences. First-order optimal frontiers and procedures under a target joint law ν=q⊗mν=q m can be characterized for divergences other than KL given in Theorem 20. For the χ2χ^2 divergence, χ2(P∥Q)≔∑x(P(x)−Q(x))2/Q(x)χ^2(P\|Q) _x(P(x)-Q(x))^2/Q(x), every (χ2,ε)(χ^2, )-approximate algorithm is (KL,log(1+ε))( KL, (1+ ))-approximate since DKL(P∥Q)≤log1+χ2(P∥Q)D_KL(P\|Q)≤ \1+χ^2(P\|Q)\. Thus, for a sequence of tolerances log(1+εm)/m→d (1+ _m)/m→ d, m,εmTA-RDC,χ2(p,q⊗m)m,m,εmuniv,χ2(p,q⊗m)m⟶ρp,q⋆(d), C_m, _m^TA -RDC,χ^2(p;q m)m, C_m, _m^univ,χ^2(p;q m)m _p,q (d), and, hence, TA-RDC is first-order optimal under the χ2χ^2 divergence as well. Furthermore, m,εTA-RDC,χ2(p,q)≤m,log(1+ε)univ,KL(p,q)+3mmini∈[k]pi≤m,εuniv,χ2(p,q)+3mmini∈[k]pi.C_m, ^TA -RDC,χ^2(p,q) _m, (1+ )^univ, KL(p,q)+ 3 m _i∈[k]p_i _m, ^univ,χ^2(p,q)+ 3 m _i∈[k]p_i. For fixed ε∈[0,1] ∈[0,1], write κ(p,q)≔maxi∈[k]qi/piκ(p,q) _i∈[k]q_i/p_i. The TV and normalized squared Hellinger frontiers are instead m,εuniv,TV(p,q⊗m)m⟶1+(1−ε)κ(p,q)−1,m,εuniv,H2(p,q⊗m)m⟶1+(1−ε)2κ(p,q)−1, C_m, ^univ,TV(p;q m)m 1+(1- )\κ(p,q)-1\, C_m, ^univ,H^2(p;q m)m 1+(1- )^2\κ(p,q)-1\, where H2(P,Q)≔1−∑xP(x)Q(x)H^2(P,Q) 1- _x P(x)Q(x). The optimal rule E-samples a coin before querying, runs RDC with probability 1−ε1- for TV or (1−ε)2(1- )^2 for Hellinger, and otherwise returns the first m M-samples. Thus, TA-RDC is the first-order optimal procedure for KL and Pearson χ2χ^2, while the randomized RDC/direct-sampling rule is the choice for TV and Hellinger. However, this randomized rule does not give control over individual runs: it controls neither the pathwise attained discrepancy as in TA-RDC, nor the number of queries as in CA-RDC. We provide experimental results with TA-RDC, the first-order optimal frontier and its optimal procedure under TV distance in Section A.7. A.6 Evaluation of M-costs and statistical alignment discrepancies In this section, we give details for computing M-costs and statistical alignment discrepancies (cf. Definitions 10 and 13) of the various post-processing methods considered in Sections 5 and A.3. We consider a product law for the target joint law ν=q⊗mν=q m, where q∈Δk−1q∈ ^k-1 are the user-specified target rates. Statistical alignment discrepancies with closed form expressions can be directly evaluated either via a theorem (e.g., the unconditional discrepancy is zero for RDC by Theorem 5) or complete enumeration of state spaces of appropriate multinomial random variables. However, when the number of attributes k and/or output samples m is large, exact computation may be infeasible. In this case, we approximate the statistical alignment discrepancy via Monte Carlo estimation. Setting and notation. Throughout this section, we assume the source and target rates p and q can lie in Δk−1 ^k-1 (in particular, they need not lie in the interior of the simplex). We denote their supports as Ssrc=supp(p)S_src=supp(p) and supp(q)=supp(q) supp(q)=supp(q), respectively. Furthermore, let t=ℓ→∈ℕ≥0k:∑iℓi=tT_t=\ _≥ 0^k: _i _i=t\ be the space of possible count vectors returned by t∈ℕt samples and ρq(ℓ→)=Pr(Mult(m,q)=ℓ→) _q( )= (Mult(m,q)= ) index values ℓ→∈m _m of a multinomial p.d.f. with m trials and success rates equal to the target rates q, with the convention 00=10^0=1. For a source state c→ c, define its feasible target mass by α(c→)=PrL→∼Mult(m,q)(L→≤c→)=∑ℓ→∈m:ℓ→≤c→ρq(ℓ→) α( c)= _ L (m,q)( L≤ c)= _ subarrayc _m:~ ≤ c subarray _q( ) which are multinomial c.d.f.s that can be efficiently computed via recursive identities; see, e.g., Hayter (2014) and Section A.5 for more details. Output count law. Sampling an attribute sequence from the target joint law ν=q⊗mν=q m can be equivalently thought of as drawing a count vector ℓ→∈ℒm _m according to the multinomial law L→∼Mult(m,q) L (m,q) and then selecting an attribute sequence uniformly over the chosen type class T(ℓ→):=a→=(a1,…,am)∈[k]m:∑t=1m1at=i=ℓi,∀i∈[k];T( ):= \ a=(a_1,…,a_m)∈[k]^m: _t=1^m1\a_t=i\= _i,~∀ i∈[k]; \ (30) (Cover et al., 1991; Csiszár, 1998, see, e.g.,). Under the target joint law ν=q⊗mν=q m, the black-box post-processing methods we consider in this paper also select an attribute sequence uniformly over a chosen type class, for a (possibly random) count vector ℓ→ (cf. Section 4). Consequently, obtaining closed-form expressions for the statistical alignment discrepancies often requires explicitly characterizing the output law of the count vectors returned by a post-processing algorithm; see, also, the discussion about minimal sufficiency of the count vectors in Section 4.1. Thus, let K~∈m K _m be the attribute counts of the m returned samples from a post-processing algorithm Algm∈mo Alg_m∈ A_m^o (cf. Definition 2). Then, for every count vector c→∈ℕ≥0k c _≥ 0^k and ℓ→∈m _m, denote the output count law after conditioning on the realized attribute counts as KAlgmC→(ℓ→,c→)≔Pr(K~=ℓ→∣x,C→=c→)K C_ Alg_m( ; c) ( K= x, C= c) (31) (see, also, Equation 8, which defines the output attribute law as the law of the attribute sequence returned by a post-processing algorithm). Finally, denote the unconditional output count law of a post-processing algorithm as KAlgm(ℓ→)≔Pr(K~=ℓ→∣x)K_ Alg_m( ) ( K= x) (32) A.6.1 Metrics for RDC Assume the support condition supp(q)⊆supp(p) supp(q) supp(p), so that the RDC stopping time satisfies Tν⋆<∞T_ν <∞ almost surely (cf. Theorem 5). M-cost and stopping-time distribution. Note that Tν⋆=inft≥m:A→⋆∈Ωt=inft≥m:Ci(t)≥Li,∀i∈[k]≕TL→,T_ν = \t≥ m: A ∈ _t\= \t≥ m:C_i(t)≥ L_i,\ ∀ i∈[k]\ T_ L, where Li=∑j=1m1Aj⋆=iL_i= _j=1^m1\A_j =i\ are the attribute counts of the target attribute sequence A→⋆∼ν A ν. In other words, an equivalent representation of the RDC algorithm involving count vectors draws a target attribute sequence A→⋆∼ν A ν, records its attribute counts LiL_i, and then M-samples until it attains at least LiL_i outputs with annotated attribute i. Then, independence of the target demand and the source stream gives the c.d.f. of the stopping time and M-cost of the RDC algorithm as Pr(Tν⋆≤t) (T_ν ≤ t) =C→(t)∼Mult(t,p)[α(C→(t))], =E_ C(t) (t,p) [α( C(t)) ], (33) mRDC(p,q) _m^RDC(p,q) =[Tν⋆]=∑t=0∞1−C→(t)∼Mult(t,p)[α(C→(t))], =E[T_ν ]= _t=0^∞ \1-E_ C(t) (t,p) [α( C(t)) ] \, respectively. The M-cost of the RDC algorithm also admits an alternative expression involving an expectation over target count vectors. For a count vector ℓ=(ℓ1,…,ℓk)∈ℕ≥0k =( _1,…, _k) _≥ 0^k, define the hitting time Tℓ=inft≥0:Ci(t)≥ℓi,∀iT_ = \t≥ 0:C_i(t)≥ _i,\ ∀ i \ and let Sr(u)=∑j=0r−1ujj!S_r(u)= _j=0^r-1 u^jj! with S0(u)=0S_0(u)=0. Proposition 25 (Tail-sum and Poissonized integral formulas). For every ℓ→∈ℕ≥0k _≥ 0^k, [Tℓ→] [T_ ] =∑t=0∞Pr(∃i:Ci(t)<ℓi), = _t=0^∞ (∃ i:C_i(t)< _i ), =∫0∞1−∏i=1k[1−e−pitSℓi(pit)]t. = _0^∞ \1- _i=1^k [1-e^-p_itS_ _i(p_it) ] \dt. (34) Consequently, mRDC(p,q)=L→∼Mult(m,q)[∫0∞1−∏i=1k[1−e−pitSLi(pit)]t].C_m^RDC(p,q)=E_ L (m,q) [ _0^∞ \1- _i=1^k [1-e^-p_itS_L_i(p_it) ] \dt ]. (35) The proof is analogous to the one given in Doumas and Papanicolaou (2016) which gives the expected number of coupons needed to collect m sets of k coupon types. For exact evaluations, the expectation in Equation 33 can be computed by enumerating count vectors in c→∈n c _n and then calculating the multinomial c.d.f. α(c→)α( c) in the argument (cf. Section A.5). Similarly, the expectation in Equation 35 can be computed by enumerating count vectors in mT_m and then calculating the one-dimensional integral in the argument. For approximate evaluations, we use Monte Carlo by drawing r∈[R]r∈[R] replicates L→(r)∼i.i.d.Mult(m,q) L^(r) i.i.d. Mult(m,q) and simulating a source-count process until C→(r)(t)≥L→(r) C^(r)(t)≥ L^(r). We then either average the resulting stopping times to estimate the M-cost or obtain empirical survival probabilities and quantiles to estimate Equation 33. A.6.2 Metrics for thresholded anytime RDC Let t≔σC→(s):0≤s≤tG_t σ\ C(s):0≤ s≤ t\ be the source-count filtration, and let σ≥mσ≥ m be either a deterministic time or an almost surely finite tt≥0\G_t\_t≥ 0-stopping time. Write C→σ≡C→(σ) C_σ≡ C(σ) as the accumulated source-count vector (cf. Equation 3) of the anytime RDC procedure (A-RDC; cf. Definition 16) at time σ. By Theorem 17, conditional on C→σ=c→ C_σ= c, the output count law of A-RDC is KA-RDC,σC→(ℓ→,c→) K_A -RDC,σ C( ; c) ≔Pr(K~=ℓ→|x,C→σ=c→)=ρq(ℓ→)1ℓ→≤c→α(c→) ( K= \, |\,x, C_σ= c )= _q( )1\ ≤ c\α( c) whenever α(c→)>0α( c)>0. On the event α(C→σ)=0\α( C_σ)=0\, every feasible output has zero target probability. Therefore, for every ℓ→∈m _m satisfying ρq(ℓ→)>0 _q( )>0, the unconditional output count law of A-RDC at time σ satisfies KA-RDC,σ(ℓ→) K_A -RDC,σ( ) ≔Pr(K~=ℓ→|x)=ρq(ℓ→)rσ(ℓ→), ( K= \, |\,x )= _q( )r_σ( ), (36) where rσ(ℓ→)≔[1α(C→σ)>0,ℓ→≤C→σα(C→σ)],r_σ( ) [ 1 \α( C_σ)>0,\, ≤ C_σ \α( C_σ) ], (37) with the convention that the integrand is zero when α(C→σ)=0α( C_σ)=0. Recall from Definition 18 that TA-RDC (cf. Algorithm 2) with nominal tolerance ε≥0 ≥ 0 uses the source-count measurable stopping time τf,ε≔inft≥m:Ψf(αt)≤ε _f, \t≥ m: _f( _t)≤ \. Since TA-RDC and A-RDC agree pathwise, (i.e., A^Tν⋆∧τf,ε=A^τf,ε A_T_ν _f, = A_ _f, a.s.; see, also, Equation 11), the unconditional output count law of TA-RDC with nominal tolerance ε is KA-RDC,τf,εK_A -RDC, _f, . Thus, TA-RDC is obtained from the preceding general expressions by setting σ=τf,εσ= _f, . Unconditional discrepancies. For a source-count measurable time σ≥mσ≥ m, define βσ≔Pr(α(C→σ)=0) _σ (α( C_σ)=0 ) (38) as the probability that the realized source state admits no feasible attribute sequence having positive probability under the target joint law ν=q⊗mν=q m. Equivalently, on this event, every feasible sequence of output attributes has zero target probability. The unconditional TV and KL discrepancies of A-RDC at the source-count measurable time σ are, respectively, ΔTVun(A-RDCσ) _TV^un (A -RDC_σ ) =12L→∼Mult(m,q)[|rσ(L→)−1|]+βσ2, = 12E_ L (m,q) [ |r_σ( L)-1 | ]+ _σ2, ΔKLun(A-RDCσ) _KL^un (A -RDC_σ ) =L→∼Mult(m,q)[rσ(L→)logrσ(L→)],βσ=0,+∞,βσ>0. = cases _ L (m,q) [r_σ( L) r_σ( L) ],& _σ=0,\\[8.00003pt] +∞,& _σ>0. cases (39) where we use the relation ∑ℓ→:ρq(ℓ→)>0ρq(ℓ→)rσ(ℓ→)=1−βσ _ :\, _q( )>0 _q( )r_σ( )=1- _σ. The discrepancies in Equation 39 also admit equivalent representations as expectations under the unconditional output count law of A-RDC at time σ: ΔTVun(A-RDCσ) _TV^un (A -RDC_σ ) =L→∼KA-RDC,σ[(1−1rσ(L→))+1ρq(L→)>0]+βσ, =E_ L K_A -RDC,σ [ (1- 1r_σ( L) )_+1\ _q( L)>0\ ]+ _σ, ΔKLun(A-RDCσ) _KL^un (A -RDC_σ ) =L→∼KA-RDC,σ[logrσ(L→)],βσ=0,+∞,βσ>0. = cases _ L K_A -RDC,σ [ r_σ( L) ],& _σ=0,\\[8.00003pt] +∞,& _σ>0. cases (40) To approximate these discrepancies, we simulate r∈[R]r∈[R] independent source paths and record C→σ(r)≔C→(r)(σ(r)) C_σ^(r) C^(r) (σ^(r) ). For TA-RDC, each source path is simulated until σ(r)=τf,ε(r)σ^(r)= _f, ^(r). For any fixed ℓ→ , the expectation in Equation 37 is then estimated by r^σ,R(ℓ→)=1R∑r=1R1α(C→σ(r))>0,ℓ→≤C→σ(r)α(C→σ(r)). r_σ,R( )= 1R _r=1^R 1 \α( C_σ^(r))>0,\, ≤ C_σ^(r) \α( C_σ^(r)). (41) where the feasible mass α(C→σ(r))α( C_σ^(r)) is computed explicitly using the multinomial recursion identities described in Section A.5. When the count space of mT_m is sufficiently small, we evaluate r^σ,R(ℓ→) r_σ,R( ) for every ℓ→∈m _m and substitute these values into Equation 39. For larger count spaces, we instead (E-)sample O≥1O≥ 1 returned count vectors conditional on each simulated source state according to Pr(L→(r,o)=ℓ→|C→σ(r))=ρq(ℓ→)1ℓ→≤C→σ(r)α(C→σ(r)),o∈[O] ( L^(r,o)= \, |\, C_σ^(r) )= _q( )1\ ≤ C_σ^(r)\α( C_σ^(r)), o∈[O] so that, marginally, each L→(r,o) L^(r,o) has law KA-RDC,σK_A -RDC,σ. These conditional draws are sampled using the same multinomial recursion identities used to evaluate the feasible masses α(C→σ(r))α( C_σ^(r)). These draws are then used to approximate the expectations in Equation 40. In particular, for KL divergence, we estimate logrσ r_σ using a cross-fitted classifier-based density-ratio estimator (see, e.g., Nguyen et al., 2010; Menon and Ong, 2016, for details); for TV distance, we estimate rσ(L→(r,o))r_σ( L^(r,o)) for each returned-count L→(r,o) L^(r,o) by averaging 1L→(r,o)≤C→σ(s)/α(C→σ(s))1\ L^(r,o)≤ C_σ^(s)\/α( C_σ^(s)) over the stopped source states s∈S(f)⊆[R] ∈ S^(f) [R] r for disjoint hold-out folds ⨆fS(f)=[R] _fS^(f)=[R]. To obtain the final estimate, we then average (1−1/r^σ(L→(r,o)))+ (1-1/ r_σ( L^(r,o)) )_+ over the returned-count samples. When βσ>0 _σ>0, the unconditional KL discrepancy is +∞+∞. For TV, the mass βσ _σ can be estimated from the same source paths by β^σ,R=1R∑r=1R1α(C→σ(r))=0. β_σ,R= 1R _r=1^R1 \α( C_σ^(r))=0 \. Attained statewise certificate. Because the source-count process is discrete, the statewise discrepancy at τf,ε _f, may be strictly smaller than the nominal tolerance ε . In particular, for the TV and KL certification times, respectively, ΔTVun(TA-RDCTV,ε) _TV^un (TA -RDC_TV, ) ≤[1−α(C→(τTV,ε))]≤ε, [1-α\! ( C( _TV, ) ) ]≤ , ΔKLun(TA-RDCKL,ε) _KL^un (TA -RDC_KL, ) ≤[−logα(C→(τKL,ε))]≤ε. [- α\! ( C( _KL, ) ) ]≤ . (42) Using the same simulated stopped states C→σ(r)r∈[R]\ C_σ^(r)\_r∈[R], we estimate the attained statewise TV and KL certificates by Δ^TVC→(TA-RDC) _TV C (TA -RDC ) =1R∑r=1R[1−α(C→σ(r))], = 1R _r=1^R [1-α( C_σ^(r)) ], Δ^KLC→(TA-RDC) _KL C (TA -RDC ) =1R∑r=1R[−logα(C→σ(r))], = 1R _r=1^R [- α( C_σ^(r)) ], (43) where σ=τTV,εσ= _TV, or σ=τKL,εσ= _KL, , depending on the f-divergence used for the statewise certificate. M-cost. The M-cost of TA-RDC with source-count measurable stopping time τf,ε _f, (cf. Definition 18) is mTA-RDCf,ε(p,q)=[Tν⋆∧τf,ε].C_m^TA -RDC_f, (p,q)=E [T_ν _f, ]. We approximate this expectation using r∈RMCostr∈ R_MCost independent replications of the terminal target demand and the source stream ^mTA-RDCf,ε(p,q)=1RMCost∑r=1RMCost(Tν(r)∧τf,ε(r)). C_m^TA -RDC_f, (p,q)= 1R_MCost _r=1^R_MCost (T_ν^(r) _f, ^(r) ). (44) A.6.3 Metrics for capped anytime RDC Since capped anytime RDC (CA-RDC; cf. Algorithm 2) and A-RDC agree pathwise (i.e., A^Tν⋆∧n=A^n A_T_ν n= A_n a.s.; see, also, Equation 11), the unconditional output count law of CA-RDC with cap n≥mn≥ m coincides with that of A-RDC at the deterministic source-count measurable time σ≡nσ≡ n. Accordingly, CA-RDC’s unconditional discrepancies and statewise certificates are computed using exactly the preceding expressions and estimators with σ=n,C→σ(r)∼i.i.d.Mult(n,p).σ=n, C_σ^(r) i.i.d. Mult(n,p). (45) More explicitly, CA-RDC’s population-level unconditional discrepancies are obtained from Equations 39 and 40 by setting σ=nσ=n, while their Monte Carlo approximations use Equation 41 and the conditional returned-count draws described above. When exact evaluation is computationally feasible, the expectations in Equation 39 are computed by enumerating the count vectors in mT_m and nT_n. The infeasibility probability βn _n also admits a convenient form when σ=nσ=n is deterministic: note that α(C→(n))=0⟺∑i∈supp(q)Cn,i<mα( C(n))=0 _i (q)C_n,i<m where C→(n) C(n) is the source-count process of Equation 3. Thus, βn=PrBinomial(n,∑i∈supp(q)pi)<m. _n= \Binomial (n, _i (q)p_i )<m \. (46) For n≥mn≥ m, this probability is zero if and only if supp(p)⊆supp(q)supp(p) (q). M-cost. The M-cost of CA-RDC with query cap n≥mn≥ m is mCA-RDCn(p,q)=[Tν⋆∧n].C_m^CA -RDC_n(p,q)=E [T_ν n ]. We approximate this expectation using r∈[RMCost]r∈[R_MCost] independent replications of the terminal target demand and the source stream: ^mCA-RDCn(p,q)=1RMCost∑r=1RMCost(Tν(r)∧n). C_m^CA -RDC_n(p,q)= 1R_MCost _r=1^R_MCost (T_ν^(r) n ). (47) Feasible-run discrepancies. In the setting where ∃i∈[k]∃ i∈[k] such that pi>0p_i>0 but qi=0q_i=0, there is a strictly positive probability that an M-sampled batch of n outputs ℬn=(Y1,…,Yn)B_n=(Y_1,…,Y_n) admits no feasible attribute sequence under the target joint law. In this case, the KL discrepancy for CA-RDC with any capped-budget n≥mn≥ m is +∞+∞, so we report the feasible-run discrepancy DKL(PCA-RDC(A^n∣αn>0)∥q⊗m)D_KL(P_ CA-RDC( A_n _n>0)\|q m) and the feasibility probability Pr(αn>0)=1−βn ( _n>0)=1- _n (cf. Sections 5.2 and 38). The former is computed by filtering the source streams in the empirical expectations of Equation 41 to those that contain at least m outputs whose attribute lies in the support of the target rates (since α(C→(n))=0⟺∑i∈supp(q)Cn,i<mα( C(n))=0 _i (q)C_n,i<m). For the latter, we report Equation 46 using empirical plug-in estimates for the source rates. These estimates may be obtained, for example, through a frozen pool of S outputs (Y1,…,YS)(Y_1,…,Y_S), so that p^i=1/S⋅∑s=1S1ϕ(Ys)=i,∀i∈[k] p_i=1/S· _s=1^S1\φ(Y_s)=i\,∀ i∈[k] (cf. Section 5.2). A.6.4 Metrics for rejection sampling algorithms Oracle rejection sampling. The oracle rejection sampling procedure of Section A.2.1 has M-cost mOracleRS(p,q)=m⋅maxi∈supp(q)qi/piC_m^OracleRS(p,q)=m· _i∈ supp(q)q_i/p_i and is universally exact, so that its unconditional discrepancy under forward f-divergences is zero; see, Proposition 22. Approximate rejection sampling. The output count law of the approximate rejection sampling procedure in Section A.3 does not, in general, have a closed-form expression. We thus approximate its M-cost and unconditional discrepancy via Monte Carlo estimate as follows. Conditional on a stopped pilot path F, let τ(F)τ(F), λ(F)λ(F), and s(F)s(F) denote the pilot size, the proposal acceptance probability, and the output attribute law of accepted samples in Equations 26 and 27. The number of proposals required for m acceptances is negative binomial, so the (pilot conditional) M-cost and its estimate using independent pilot paths F1,…,FRF_1,…,F_R are mARS(p,q)=p[τ(F)+mλ(F)];^mARS(p,q)=1R∑r=1Rτ(Fr)+mλ(Fr),C_m^ARS(p,q)=E_p [τ(F)+ mλ(F) ]; C_m^ARS(p,q)= 1R _r=1^R \τ(F_r)+ mλ(F_r) \, respectively. For the estimation of the sampling discrepancies, the unconditional output count law is Km(ℓ)=F[ρs(F)(ℓ)],ρv(ℓ)=m!∏iℓi!∏i=1kviℓi,ℓ∈ℒm.K_m( )=E_F\! [ _s(F)( ) ], _v( )= m! _i _i! _i=1^kv_i _i, _m. (48) Following the standard cross-fitting construction of (Chernozhukov et al., 2018), we split the pilot paths into folds so that ⨆fIf=[R] _fI_f=[R]. If pilot path FrF_r is in fold f, draw B count vectors Lrb∼Mult(m,s(Fr))L_rb (m,s(F_r)), and use the other folds I−f≔[R] _-f [R] I_f to form the density ratio w^−f(ℓ)=1|I−f|∑u∈I−fρs(Fu)(ℓ)ρq(ℓ)=1|I−f|∑u∈I−f∏i=1ksi(Fu)qiℓi. w_-f( )= 1|I_-f| _u∈ I_-f _s(F_u)( ) _q( )= 1|I_-f| _u∈ I_-f _i=1^k \ s_i(F_u)q_i \ _i. We then construct estimates for the unconditional statistical alignment discrepancies as Δ^KLun _KL^un =1R⋅B∑r=1R∑b=1Blogw^−f(r)(Lrb), = 1R· B _r=1^R _b=1^B w_-f(r)(L_rb), Δ^TVun _TV^un =1R⋅B∑r=1R∑b=1B(1−w^−f(r)(Lrb)−1)+. = 1R· B _r=1^R _b=1^B (1- w_-f(r)(L_rb)^-1 )_+. A.7 Additional details and results for experiments A.7.1 Additional results for simulation experiments Anytime RDC methods. We record the unconditional statistical alignment discrepancies of the post-processing algorithms in Section 5.1 under both the KL divergence and TV distance across various settings outside of the main text. We further record the first-order optimal frontier under the TV distance 1+(1−ε)κ(p,q)−1,κ(p,q)≔maxi∈[k]qi/pi,1+(1- )\κ(p,q)-1\, κ(p,q) _i∈[k]q_i/p_i, as well as a randomized RDC/direct-sampling rule (RDC/DS mixture) that runs RDC with probability 1−ε1- and otherwise returns the first m samples with probability ε (cf. Section A.5). Its M-cost is [NεRDC/DS]=[Tν⋆]⋅(1−ε)+m⋅ε [N_ RDC/DS]= [T_ν ]·(1- )+m· , and its unconditional discrepancies are ΔKLun(RDC/DS) _KL^un (RDC/DS ) =DKL((1−ε)⋅q⊗m+ε⋅p⊗m∥q⊗m), =D_KL ((1- )· q m+ · p m \|q m ), ΔTVun(RDC/DS) _TV^un (RDC/DS ) =ε⋅TV(p⊗m,q⊗m). = ·TV (p m,q m ). We vary the normalized tolerance level d=ε/md= /m either in the interval [0,DKL(p∥q)][0,D_KL(p\|q)] for KL or the unnormalized tolerance ε∈[0,1] ∈[0,1] for TV to trace out a cost-discrepancy profile. Additional source settings. We fix the target joint law to ν=q⊗mν=q m with q uniform and m=300m=300, while varying the number of attributes k and the source rates; see Table 5. The ratio κ=maxi∈[k]qi/piκ= _i∈[k]q_i/p_i captures the inherent difficulty of the setting, with the oracle rejection sampler achieving the minimum possible M-cost among universally exact black-box post-processing algorithms, m⋅κm·κ (cf. Section A.2.1). For CA-RDC, the cap n is varied over a grid from m to nmax=round(m⋅max1.25κ,κ+0.5)n_ =round(m· \1.25κ,κ+0.5\). Table 5: Additional synthetic source settings. In every setting, the target joint law is ν=q⊗mν=q m with the target rates uniform, qi=1/kq_i=1/k, and the output size is m=300m=300. Setting k Source distribution p κ=maxiqi/piκ= _iq_i/p_i mild skew 3 (0.20,0.30,0.50)(0.20,0.30,0.50) 1.67 one rare attribute 4 (0.08,0.22,0.30,0.40)(0.08,0.22,0.30,0.40) 3.12 graded source 8 (0.04,0.06,0.08,0.10,0.12,0.16,0.20,0.24)(0.04,0.06,0.08,0.10,0.12,0.16,0.20,0.24) 3.12 graded source 12 pi=(i+1)/90,i=1,…,12p_i=(i+1)/90,\ i=1,…,12 3.75 two mild groups 16 ((5/64)×8,(3/64)×8)((5/64)^× 8,(3/64)^× 8) 1.33 four rare attributes 16 ((1/64)×4,(5/64)×12)((1/64)^× 4,(5/64)^× 12) 4.00 As shown in Figures 9(a) and 9(b), all methods exhibit a tradeoff between normalized M-cost and unconditional discrepancy across the six source settings. TA-RDC and CA-RDC produce similar cost-discrepancy profiles under both KL and TV, while the RDC/DS mixture traces a linear tradeoff between its RDC and direct-sampling endpoints. The profiles generally track their first-order optimal frontiers, although the size of the finite-sample deviations varies across the number of attributes and source rates. Overall, the qualitative comparisons suggest that our anytime RDC methods remain stable across various source settings. (a) KL discrepancy profiles. (b) TV discrepancy profiles. Figure 9: Cost–discrepancy profiles for the additional synthetic source settings with a uniform target distribution; see Table 5 for exact source rate specifications. Finite sample performance of m. We vary the output size m in the main text setting with k=8k=8 attributes to examine the finite sample effects of the first-order optimality guaranteed by Theorems 20 and A.5. For CA-RDC, the cap n is varied over a grid from m to nmax=6mn_ =6m, as in the main text. As can be seen in Figure 10, the finite sample effects are pronounced at m=5m=5 for both the KL divergence and TV distance, with the profiles of TA-RDC and CA-RDC achieving a lower M-cost than the first-order optimal RDC/DS mixture procedure for larger values of the unconditional TV (panel (f)). However, the appropriate first-order optimal procedures converge to their respective frontiers even for moderate output sizes m=100,200m=100,200. Figure 10: Finite output sample size performance of various post-processing methods in the main text setting with k=8k=8 attributes and non-uniform source and target rates p=(0.03,0.05,0.08,0.12,0.16,0.18,0.18,0.20)p=(0.03,0.05,0.08,0.12,0.16,0.18,0.18,0.20) and q=(0.14,0.12,0.13,0.15,0.14,0.12,0.11,0.09)q=(0.14,0.12,0.13,0.15,0.14,0.12,0.11,0.09). First-order optimal procedures – TA-RDC and CA-RDC for KL divergence, and RDC/DS mixture for TV distance – closely track their respective frontiers even for moderate output sizes m=100m=100 and 200200. Approximate rejection sampling. We evaluate the ARS procedure in the synthetic setting of the main text with k=8k=8 attributes and non-uniform source and target rates. We vary the output size m∈100,500,1000m∈\100,500,1000\. Computational details for unconditional discrepancies and M-costs are given in Section A.6. Implementation details. We use the confidence sequence in Equation 25 with δCS=0.05 _ CS=0.05. The first look is at time t0=16t_0=16, with subsequent looks following the dense geometric grid tj+1=max⌈1.04tj⌉,tj+1t_j+1= \ 1.04t_j ,t_j+1\. We vary the threshold for the relative width stopping time over γ∈0.30,0.42,0.60,0.85,1.25,1.75,2.50,3.50,5.00γ∈\0.30,0.42,0.60,0.85,1.25,1.75,2.50,3.50,5.00\, with smaller values corresponding to more precise source-rate estimates and pilot samples. All thresholds are evaluated on the same 1,5001,500 independent pilot paths. To estimate the sampling discrepancies, we generate B=20B=20 count vectors per pilot path with three folds for the cross-fitting (cf. Section A.6). Results. Figure 11 plots the cost-discrepancy profile of ARS as we vary the threshold γ. The M-cost and KL discrepancy are normalized by the output size m. At the loosest threshold γ=5γ=5, its normalized M-costs are 4.884.88, 4.324.32, and 4.244.24 for m=100,500,1000m=100,500,1000, respectively, with normalized KL discrepancies of 0.0570.057, 0.0770.077, and 0.0810.081. Tightening the threshold to γ=0.30γ=0.30 reduces the normalized KL to 1.51×10−61.51× 10^-6, 6.38×10−66.38× 10^-6, and 1.15×10−51.15× 10^-5, and TV to 0.00660.0066, 0.02930.0293, and 0.05600.0560, but substantially raises its normalized M-cost to 241.94241.94, 52.1252.12, and 28.3928.39. Across all output sizes, ARS is unable to track the first-order optimal frontier (cf. Theorem 20). In contrast, TA-RDC (cf. Algorithm 2) attains lower M-costs at comparable discrepancies and is first-order optimal under the KL divergence. Figure 11: Cost–discrepancy profiles for approximate rejection sampling (ARS) as described in Section A.3. Here, the setting is exactly that of the synthetic experiments in the main text, with k=8k=8 attributes, non-uniform source and target rates, and output sizes m∈100,500,1000m∈\100,500,1000\ (cf. Section 5.1). The top row reports unconditional KL discrepancy normalized by the output size m and the bottom row reports unconditional TV distance. The orange points of ARS vary the threshold γ of the relative width stopping time rule, with smaller thresholds corresponding to more pilot samples and thus a larger M-cost. A.7.2 General implementation details for empirical experiments T2I models. We use open-weight text-to-image models because publicly available and open-weight diffusion models have found recent, widespread use for synthetic data generation and augmentation applications across various domains, including representation learning, medical imaging, earth observation, and industrial inspection (Tian et al., 2023; Bluethgen et al., 2025; Sagers et al., 2023; Sousa et al., 2025; Deng and Lu, 2025; Valvano et al., 2024). All image-generation calls are made through fal-hosted endpoints, with one PNG image requested per prompt. (i) Flux-2-dev uses fal endpoint fal-ai/flux-2. We use portrait 4:34:3 output, 28 inference steps, guidance scale 2.5, regular acceleration, and the safety checker enabled (Black Forest Labs, 2026). (i) Qwen-Image-2512 uses fal endpoint fal-ai/qwen-image-2512. We use portrait 4:34:3 output, 28 inference steps, guidance scale 4.0, regular acceleration, and the safety checker enabled (Wu et al., 2025; Qwen Team, 2025). (i) HiDream-O1-Image uses fal endpoint fal-ai/hidream-o1-image. We use portrait 4:34:3 output, 50 inference steps, guidance scale 5.0, and the safety checker enabled (HiDream.ai, 2026). Annotation and label construction for T2I experiments. We annotate generated images using OpenAI GPT-5.5 as a vision-language annotator (OpenAI, 2026b). For all T2I annotation runs, we authenticate using an API key supplied at run time and use the OpenAI Batch API to upload a JSONL file containing one POST request to /v1/responses per image, with an HTTPS image URL, a fixed annotation prompt, a strict JSON Schema, and a 24-hour completion window. For all image requests, we explicitly set the reasoning effort to medium while not explicitly setting the temperature, top_p, output-token limit, or random seed. Justification for vision-language annotation. We use GPT-5.5 only as an operational annotator ϕ:→φ:Y , not as an alignment intervention and not as a trained replacement for a task-specific computer-vision classifier. This distinction is important: in our experiments ϕφ maps each generated image to a small, prespecified set of coarse perceived-attribute bins under a fixed prompt, fixed allowable categories, and a strict JSON response schema. Modern vision-language models are explicitly designed to analyze image inputs (OpenAI, 2026b; OpenAI, 2026a), and recent empirical studies suggest that they can provide accurate and cost-effective labels for large scale visual annotation when the label space is fixed and the task is specified carefully. For example, Lu and Zhong (2024) evaluate VLM-based annotation on the CelebA face-attribute dataset and report 79.5%79.5\% agreement with the original human labels, increasing to 89.1%89.1\% after re-annotating disagreement cases by majority vote, while costing less than 1%1\% of manual annotation. In a satellite-image classification study, Beck et al. (2025) compare ChatGPT-4V with expert and non-expert human annotators and find that a hybrid strategy which routes only low-certainty cases to humans can reduce total annotation costs by more than 50%50\% with minimal loss in label quality. More broadly, Xie et al. (2026) report that MLLM-generated image-tagging labels can reduce annotation cost to about 10−310^-3 of human annotation cost and can achieve over 90%90\% of the downstream training performance obtained from human labels; they also find that structured prompting and label disambiguation substantially improve annotation quality. These findings support our use of a frontier VLM as a scalable first-pass annotator for coarse, prespecified visual labels. To mitigate annotation noise, we use the same fixed annotation protocol for all methods, require structured outputs, locally aggregate and validate returned fields, and interpret the demographic variables as perceived visual annotations rather than ground-truth identity. A.7.3 Additional implementation details for individual-headshot experiments T2I models and individual-headshot prompts. We use the three T2I models described in Section A.7.2. The prompt families for the individual headshot experiment are: (i) HPS Show a photorealistic professional headshot of a person working in medicine or healthcare, in professional attire. (i) TSI: The TSI prompt uses the same base prompt as HPS and appends The image should be a single centered head-and-shoulders portrait of one individual. For this single image, internally choose exactly one demographic category uniformly at random from the 16 categories formed by gender man, woman, age young adult, older adult, and race/ethnicity White/Caucasian, Black/African descent, Asian, Hispanic/Latino. Depict this person as belonging to the chosen category. Across separate generations, each of the 16 gender-age-race categories should be equally likely. (i) Demographic HPS Show a photorealistic professional headshot of age article race gender working in medicine or healthcare, in professional attire. Gender ranges over man, woman; age over young, old with articles a young, an old; and race over White/Caucasian, Black/African-descent, Asian, Hispanic/Latino. Annotation and label construction. Each image is annotated with one structured request using a fixed prompt, fixed label set, and strict JSON response schema. For individual headshots, the prompt asks for perceived gender, perceived race/ethnicity presentation, and age bin: Annotate the visible person in this professional headshot. Return only JSON. Use exactly one bin for each field. gender must be one of: man, woman. race should mean perceived race/ethnicity presentation, not true identity. race must be one of: White/Caucasian, Black/African descent, Asian, Hispanic/Latino. age must be one of: young, old. Use the closest bin when a demographic attribute is visually ambiguous. A.7.4 Additional results for individual-headshot experiments Hard prompt failures. Figure 12 illustrates demographic HPS failures for the individual headshot T2I experiment. Hard-prompt failures are driven almost entirely by race/ethnicity annotation mismatches, especially when the prompt requests a Hispanic/Latino person. For Flux, 46.9%46.9\% of prompted Hispanic/Latino images are annotated as Asian, with smaller off-diagonal mass to Black/African descent and White/Caucasian. Qwen and HiDream show the same dominant failure direction, with 22.4%22.4\% and 12.7%12.7\% of prompted Hispanic/Latino images annotated as Asian, respectively. Thus, demographic HPS is highly effective at controlling gender and age in this experiment, and it greatly improves support coverage, but it still leaves ambiguity in race/ethnicity presentation. Figure 12: Race/ethnicity hard-prompt failure diagnostics for individual-headshot demographic HPS. Heatmaps show annotated race conditional on prompted race for each T2I model, and image panels show representative off-diagonal race/ethnicity annotation failures. Race abbreviations are W/B/A/H for White, Black, Asian, and Hispanic. Sensitivity analysis. We vary the output size m∈25,50,100m∈\25,50,100\ and report results for demographic HPS across all three T2I models. For each output size, we vary the normalized KL tolerance d∈[0,3]d∈[0,3], the TV tolerance ε∈[0,0.999] ∈[0,0.999], and the CA-RDC cap n/m∈[1,20]n/m∈[1,20]. As shown in Figure 13, both anytime methods consistently reduce the KL and TV discrepancies as the normalized M-cost increases. The cost-discrepancy profiles are stable across output sizes and models, although Flux generally requires a larger normalized M-cost than Qwen and HiDream to attain comparable discrepancies. Figure 13: Output-size sensitivity analysis for individual-headshot demographic HPS. Columns correspond to three T2I models, while the top and bottom rows report normalized KL discrepancy and unconditional TV discrepancy, respectively. Colors distinguish m∈25,50,100m∈\25,50,100\; solid and dashed curves report the actual discrepancies of TA-RDC and CA-RDC, respectively, and dotted curves report the nominal TA-RDC certificates. A.7.5 Additional implementation details for group-photo experiments T2I models and group-photo prompts. The same T2I models are used as in the individual-headshot photo experiments (cf. Section A.7.2). In the main experiments, we consider HPS, TSI, and demographic HPS, all of which modify the input prompt to the T2I models. In detail, their complete prompt families are: (i) HPS Generate a single-frame photorealistic candid scene centered on a foreground trio of exactly three adults in a medicine or healthcare setting. The foreground trio should be the main subject, appear together in one camera shot, and be clearly countable as three distinct people. The scene should feel natural and in the moment, with realistic activity, posture, camera viewpoint, and interaction. (i) TSI: The TSI prompt uses the HPS prompt and appends For this image, first choose exactly one group composition uniformly at random from the target set of foreground-trio demographic count vectors: gender count is either 2 women and 1 man or 1 woman and 2 men; race/ethnicity count is either 1 White/Caucasian adult, 1 Black/African descent adult, and 1 Hispanic/Latino adult, or 1 White/Caucasian adult, 1 Black/African descent adult, and 1 Asian adult; age count is either 2 young adults and 1 older adult, or 3 young adults. Depict the foreground trio so that its demographic counts match the chosen composition. These counts refer only to the three adults in the foreground trio. Across repeated independent generations, each target group-composition count vector should be equally likely. (i) Demographic HPS: The demographic HPS prompt uses the HPS prompt and appends The foreground trio consists of: gender count phrase; race count phrase; age count phrase. These counts refer only to the three adults in the foreground trio. For the three-person demographic HPS group-photo condition, gender count phrase \gender count phrase\ ∈2 women and 1 man,1 woman and 2 men, ∈\2 women and 1 man,\ 1 woman and 2 men\, race count phrase \race count phrase\ ∈1 White/Caucasian adult, 1 Black/African descent adult,and 1 Hispanic/Latino adult,1 White/Caucasian adult, 1 Black/African descent adult,and 1 Asian adult, ∈ \ array[]l1 White/Caucasian adult, 1 Black/African descent adult,\\ and 1 Hispanic/Latino adult,\\ 1 White/Caucasian adult, 1 Black/African descent adult,\\ and 1 Asian adult array \, age count phrase \age count phrase\ ∈2 young adults and 1 older adult,3 young adults. ∈\2 young adults and 1 older adult,\ 3 young adults\. Annotation and label construction. We annotate generated images using OpenAI GPT-5.5 as a vision-language annotator (OpenAI, 2026b) using the same API access settings as Section A.7.2. For group photos, the annotator first counts the number of people in the foreground. It then returns the gender, race/ethnicity presentation, and age of each identified individual: Annotate this group photo. Return only JSON. First count only the distinct visible people in the foreground/main group. Do not count background bystanders, distant incidental people, reflections, posters, or partial figures outside the main group. Then list each counted foreground person and use exactly one bin for each person’s fields. gender must be one of: male, female. race should mean perceived race/ethnicity presentation, not true identity. race must be one of: White/Caucasian, Black/African descent, Asian, Hispanic/Latino. age must be one of: young, old. Base all demographic fields and group-level answers only on the counted foreground people. After retrieving the annotations, we then locally aggregate these per-person annotations into gender, race, and age count vectors. A group image is treated as on-support only when the annotated number of foreground people equals the requested group size and the resulting count vectors map to one of the configured group-composition attributes (cf. Section 5.2.4). Images outside this support are retained in the candidate pool but assigned target mass zero for the group-composition target distribution. A.7.6 Additional results for group-photo experiments Qualitative results. Figure 14 and Figure 15 show sampled images for various annotation categories. On- and off-support images refer to those whose observed demographic count vector lies within or outside the support of the target rates, supp(q)supp(q), respectively. TSI can produce valid group-composition attributes but often produces off-support images by realizing an invalid foreground count vector or adding/removing demographic mass relative to the target support (cf. Figure 14). Images produced by demographic HPS directly specify the target demographic count vectors, so we further differentiate between hard-compliant and non-compliant images: a hard-compliant image exactly matches the prompted count vector, while an on-support non-compliant image lies in the eight-attribute target support but matches a different count vector than requested (cf. Figure 15). Post-processing methods such as A-RDC can use these non-compliant but on-support images to reduce the count-conditional statistical alignment discrepancy. Finally, in a similar fashion to TSI, off-support examples of HPS often exhibit an incorrect foreground group size or demographic count vector. Figure 14: Examples of on- and off-support group-photo generations for each image model for the TSI method. Captions report the annotated observed count vector (O). The demographics are abbreviated as follows: F/M stands for female/male; W/B/A/H stands for White, Black, Asian, and Hispanic; and Y/O stands for young/old. The number preceding each letter represents the number of foreground figures identified as the associated demographic. Figure 15: Examples of hard-compliant, on-support non-compliant, and off-support group-photo generations for each image model under demographic HPS. Captions report the prompted target count vector (T) and annotated observed count vector (O). The demographic count vectors are abbreviated using the same protocol as Figure 14. Sensitivity analysis. We vary the output size m∈10,25,50m∈\10,25,50\ and report results for demographic HPS across all three T2I models. For each output size, we vary the normalized KL tolerance d∈[0,3]d∈[0,3] and the TV tolerance ε∈[0,0.999] ∈[0,0.999]. For CA-RDC, we vary the capped-budget from n/m=1n/m=1 to 22.3222.32, 156.25156.25, and 2020 for Flux, Qwen, and HiDream, respectively. Feasible-run KL discrepancy is reported whenever there is a nonzero probability of a queried sample lying outside of the support of the target rates. As shown in Figure 16, both anytime methods consistently reduce the KL and TV discrepancies as the normalized M-cost increases. The cost-discrepancy profiles are stable across output sizes, although Qwen requires substantially larger normalized M-costs because demographic HPS produces one target attribute at a particularly low rate of p^i=1/1000 p_i=1/1000. Figure 16: Output-size sensitivity analysis for group-photo demographic HPS. Columns correspond to three T2I models, while the top row reports unconditional KL discrepancy for TA-RDC and feasible-run KL discrepancy for CA-RDC. The bottom row reports unconditional TV discrepancy for both methods. Colors distinguish m∈10,25,50m∈\10,25,50\; solid and dashed curves report the actual discrepancies of TA-RDC and CA-RDC, respectively, and dotted curves report the nominal TA-RDC certificates. A.7.7 Additional implementation details for geocoded persona generation SVI persona-generation model and prompts. For the geocoded persona experiment, we call GPT-5.5 and input a text prompt asking the model to return one synthetic JSON patient persona. The shared base prompt specifies the JSON schema, fixes the non-geographic case-seed fields, and asks the model to generate the remaining fields: Generate one realistic synthetic adult patient persona for testing a patient-facing digital health assistant. Return strict JSON only with exactly these fields: sample_id, prompt_variant, requested_label, case_seed_id, age_band, care_setting, condition_category, request_type, message_tone, city, state, zip_code, patient_portal_message, barriers_or_preferences. Set sample_id to sample id. Set prompt_variant to prompt variant. Set requested_label to requested label or null. Use these controlled case-seed fields exactly: case_seed_id, age_band, care_setting, condition_category, request_type, message_tone. The two prompt families used in the main comparison are: (i) Target-label-blind county-seeded source. The TLB3_county_seeded prompt uses the shared base prompt, sets requested_label to null, and appends: Location instruction: The patient is located in or near county/state seed. Choose a plausible city and valid ZIP code in or near that county. Do not name hidden evaluation categories in the message body. This prompt never mentions SVI, social vulnerability, or the target quartile. The SVI quartile used in evaluation is assigned after generation by matching the generated ZIP to the CDC/ATSDR SVI file. (i) Hard SVI prompt baseline. The HARD_SVI4_DEFINITION prompt uses the shared base prompt, sets requested_label to the requested SVI quartile, and appends: Target-location instruction: The patient’s ZIP should correspond to a place whose CDC/ATSDR Social Vulnerability Index percentile is in quartile range. Do not mention SVI, vulnerability, deprivation, poverty, or the quartile in the message body unless it naturally follows from the case seed. The quartile ranges are [0,.25)[0,.25) for SVI_Q1_lowest, [.25,.50)[.25,.50) for SVI_Q2, [.50,.75)[.50,.75) for SVI_Q3, and [.75,1][.75,1] for SVI_Q4_highest. Table 6: Representative generated persona extracts from the county-seeded source, one from each observed SVI quartile. The observed label is assigned after generation by matching the generated ZIP to the CDC/ATSDR SVI file. Observed label Age band City, state, ZIP code Care setting Request type SVI Q1 18–29 Utica, KS 67584 Cardiology Medication question SVI Q2 45–64 Lidgerwood, ND 58053 Cardiology Symptom question SVI Q3 45–64 Alpharetta, GA 30009 Cardiology Symptom question SVI Q4 65+ Algodones, NM 87001 Cardiology Symptom question Annotation and label construction. The SVI experiment uses the CDC/ATSDR 2022 ZCTA-level Social Vulnerability Index file. SVI percentiles are relative area-level rankings: an overall percentile of 0.800.80 means that the ZCTA ranks above roughly 80%80\% of ZCTAs on that index, not that an individual patient has an 80%80\% vulnerability level. The quartiles move from lower to higher area-level vulnerability, but the index is multidimensional; a ZIP code can have a high overall SVI because of different combinations of socioeconomic, household, racial/ethnic-minority, and housing/transportation conditions. Figure 17 summarizes the same national ZCTA file used for the audit. Figure 17: Mean overall and theme-specific SVI percentiles for all matched ZCTAs in the 2022 CDC/ATSDR file, grouped by overall SVI quartile. A.7.8 Additional results for geocoded persona generation Representative generated locations. The examples in Table 6 illustrate how the deterministic ZIP-level audit can convert ordinary-looking location fields into SVI quartile labels. For example, Utica, KS 67584 is classified as Q1 because its overall SVI percentile is 0.1120.112; its theme percentiles are also low on the national scale, including 0.1450.145 for socioeconomic status, 0.1410.141 for racial/ethnic-minority status, and 0.1840.184 for housing/transportation. In the SVI indicators, this ZCTA has low unemployment in the SVI file, a small racial/ethnic-minority share (2.9%2.9\%), and few no-vehicle households (3.8%3.8\%), so even though it has a small population and some older-adult and disability prevalence, the combined national ranking remains low. Algodones, NM 87001 is classified as Q4 for the opposite reason: its overall SVI percentile is 0.8900.890, with very high theme percentiles for socioeconomic status (0.9060.906), household characteristics (0.9550.955), and racial/ethnic-minority status (0.9770.977). The indicators report 37.4%37.4\% of residents below 150% of poverty, 15.3%15.3\% unemployment, 24.0%24.0\% without a high-school diploma, and a 94.2%94.2\% racial/ethnic-minority share. Hard SVI prompting diagnostics. We diagnose the hard SVI prompt by comparing the requested quartile to the audited quartile of the generated ZIP. Across the 1000 hard prompted candidates in the frozen candidate pool, all generated ZIP codes are matched to the SVI file so that all generated personas are on-support. However, the requested-to-observed compliance is only 0.3560.356 and, among the 644 failed hard prompts, 84.0%84.0\% are off by one quartile and 16.0%16.0\% are off by two quartiles. Moreover, failures are almost all upward misses: 99.5%99.5\% of failed generations have an audited SVI quartile above the requested quartile. Figure 18: Hard SVI prompting confusion matrix over the full frozen hard-prompt candidate pool of 1000 personas. Each cell reports the integer count, with the row percentage in parentheses. Cell shading encodes the row percentage. In more detail, Figure 18 shows the asymmetry when hard prompting fails. Requests for the highest-vulnerability quartile are much more successful than requests for lower quartiles, whereas low- and middle-SVI requests are systematically shifted upward. Altogether, hard SVI prompting responds directionally to the requested quartile but exhibits a strong upward bias. Sensitivity analysis. We vary the output size m∈25,50,100m∈\25,50,100\ and report results for county-seeded prompting. For each output size, we vary the normalized KL tolerance d∈[0,3]d∈[0,3], the TV tolerance ε∈[0,0.999] ∈[0,0.999], and the CA-RDC capped-budget from n/m=1n/m=1 to 2020. Because county-seeded prompting has a nonzero probability of producing a persona outside the support of the target rates, we report feasible-run KL discrepancy for CA-RDC. As shown in Figure 19, both anytime methods consistently reduce the KL and TV discrepancies as the normalized M-cost increases. The cost-discrepancy profiles are stable across output sizes, with normalized KL discrepancies generally decreasing as m increases, while TV discrepancies tend to be larger for larger returned batches. Figure 19: Output-size sensitivity analysis for county-seeded SVI persona generation. The left panel reports unconditional KL discrepancy for TA-RDC and feasible-run KL discrepancy for CA-RDC, while the right panel reports unconditional TV discrepancy for both methods. Colors distinguish m∈25,50,100m∈\25,50,100\; solid and dashed curves report the actual discrepancies of TA-RDC and CA-RDC, respectively, and dotted curves report the nominal TA-RDC certificates. A.7.9 Implementation details and results for the synthetic pairwise audit Methodology for post-processing. We use the demographic HPS individual-headshot pools for Flux, Qwen, and HiDream in the synthetic data task of Section 5.2.3. For each model, we sample ten candidate batches of n=200n=200 images without replacement from its frozen pool of 1000 images, and return m=50m=50 images for each post-processing algorithm with target joint law ν=q⊗mν=q m, where q is uniform over the k=16k=16 demographic attributes. Conditional on the source count process C→(n) C(n), proportion matching (PM) returns an attribute sequence that minimizes the TV distance between the empirical distribution of its attributes and target marginal proportions; in our setting, for a target joint law, these target proportions are the target rates q∈Δk−1q∈ ^k-1. Like RDC and its anytime variants, it then uniformly selects returned outputs selected within each attribute (cf. Algorithms 1 and 2). False-match rate audit statistic. For Alg∈CA-RDC,PMAlg∈\ CA-RDC, PM\, write L^i,Alg=∑s=1n1ϕ(Y~s)=i L_i,Alg= _s=1^n1\φ( Y_s)=i\ for the number of outputs with annotated attribute i selected by the post-processing algorithm. Let S^2,Alg=∑i=1k(L^i,Alg2),T2=(m2)=1225, S_2,Alg= _i=1^k L_i,Alg2, T_2= m2=1225, for the numbers of same-attribute and total unordered pairs. Within each model’s frozen pool, we estimate the same- and different-demographic-attribute match rates, α^same(2)(t) α_same^(2)(t) and α^diff(2)(t) α_diff^(2)(t), from all pairs with valid embeddings. Holding these plug-in rates fixed, we calculate r^2,Alg(t)=S^2,AlgT2α^same(2)(t)+(1−S^2,AlgT2)α^diff(2)(t). r_2,Alg(t)= S_2,AlgT_2 α_same^(2)(t)+ (1- S_2,AlgT_2 ) α_diff^(2)(t). (49) The oracle has output attribute law exactly equal to the target joint law ν=q⊗mν=q m, and thus has [S^2,oracle]=(m2)∑i=1kqi2=T2⋅1/16 [ S_2,oracle]= m2 _i=1^kq_i^2=T_2· 1/16 same-attribute pairs. We report its expected false-match rate using S^2,Alg/T2=1/16 S_2,Alg/T_2=1/16 in Equation 49. Results. Table 2 in the main text reports the results at t=0.45t=0.45. Same-attribute match rates are substantially larger than different-attribute rates for all three image models. PM suppresses same-attribute pairs relative to independent target sampling, thereby underestimating the oracle audit rate. In contrast, CA-RDC approximates the target joint law directly and better preserves pairwise statistics. For HiDream, CA-RDC selects an average of 72.6(2.03)72.6\;(2.03) same-attribute pairs per returned batch, compared with 54.0(0.00)54.0\;(0.00) for PM. Its audit rate is 0.3050.305 percentage points away from that of the oracle, compared with 1.7341.734 percentage points for PM. Figure 20 provides examples of positive and negative pairwise match decisions, and Figure 21 shows results for a sensitivity analysis on the cosine threshold. The gap between the downstream false-match rate is largest when same-attribute pairs frequently exceed the threshold while different-attribute pairs rarely do. As the threshold becomes sufficiently low or high, nearly every pair is classified as a (non) false-match and thus the audited rates approach one another. Figure 20: Example pairwise decisions on generated headshots, grouped by whether the annotated demographic attributes agree. The thresholds are t=0.45t=0.45 for HiDream and t=0.35t=0.35 for Flux and Qwen, as shown in the panels. Figure 21: Threshold sensitivity on the cosine threshold for the pairwise audit task of Section 5.2.3. The gap in the false match rate between the oracle and CA-RDC (solid) and proportion matching (dashed) are plotted across all three T2I models. The vertical line denotes the cosine threshold t=0.45t=0.45 reported in the main text. The gap between the Oracle and PM procedure remains large through non-trivial intermediate ranges of the threshold. In contrast, CA-RDC better captures pairwise interactions in the same- and different-attribute class counts by targeting a joint law. This results in better estimates of the false-match rate. A.8 Proofs A.8.1 Proof of Theorem 5 Proof. Let Li=∑j=1m1Aj⋆=iL_i= _j=1^m1\A_j =i\ be the attribute counts of the target attribute sequence A→⋆∼ν A ν. By definition of the feasible support (cf. Equation 3), Tν⋆=inft≥m:A→⋆∈Ωt=inft≥m:Ci(t)≥Li,∀i∈[k]≕TL→.T_ν = \t≥ m: A ∈ _t\= \t≥ m:C_i(t)≥ L_i,\ ∀ i∈[k]\ T_ L. (50) For each i with pi=0p_i=0, the support condition supp(ν)⊆(supp(p))msupp(ν) (supp(p))^m implies Li=0L_i=0 almost surely. For each i with pi>0p_i>0, we have Ci(t)→∞C_i(t)→∞ almost surely. Since there are finitely many attributes, all attribute demands are met in finite time, so Tν⋆<∞T_ν <∞ almost surely. Moreover, at completion time Tν⋆T_ν , RDC selects outputs whose attribute sequence is A→⋆ A by construction. Therefore, its output attribute law is A→⋆∼ν A ν, and RDC is universally exact. ∎ A.8.2 Proof of Theorem 6 We first prove a lemma that generalizes the Wald identity to a conditional statement on the returned attribute sequence for universally exact algorithms. Lemma 26 (Conditional Wald identity). Let a source-rate-free algorithm be universally exact for a target joint law ν on [k]m[k]^m, and let A~∈[k]m A∈[k]^m denote its returned attribute sequence. If ν((supp(p))m)=1ν((supp(p))^m)=1 and p[N]<∞E_p[N]<∞, then, for every i∈[k]i∈[k], p[Ci(N)∣A~]=pip[N∣A~]almost surely.E_p[C_i(N) A]=p_iE_p[N A] surely. (51) Proof. For any p′p with supp(p′)=supp(p)supp(p )=supp(p), the likelihood ratio of observing a sequence of N M-samples is ∏i∈supp(p)(pi′/pi)Ci(N) _i (p)(p_i /p_i)^C_i(N). For a fixed a→ a with ν(a→)>0ν( a)>0, applying a change of measure on each event N=n,A~=a→\N=n, A= a\ and summing over n gives Prp′(A~=a→)=p[1A~=a→∏i∈supp(p)(pi′pi)Ci(N)]. _p ( A= a)=E_p [1\ A= a\ _i (p) ( p_i p_i )^C_i(N) ]. Universal exactness implies Prp′(A~=a→)=Prp(A~=a→)=ν(a→)>0 _p ( A= a)= _p( A= a)=ν( a)>0 and therefore p[∏i∈supp(p)(pi′pi)Ci(N)|A~=a→]=1.E_p [ _i (p) ( p_i p_i )^C_i(N) | A= a ]=1. (52) Jensen’s inequality then yields ga→(p′)≔∑i∈supp(p)p[Ci(N)∣A~=a→]⋅logpi′pi≤0=ga→(p).g_ a(p ) _i (p)E_p[C_i(N) A= a]· p_i p_i≤ 0=g_ a(p). Thus, p maximizes the differentiable function ga→(p′)g_ a(p ) subject to ∑i∈supp(p)pi′=1 _i (p)p_i =1. Stationarity at the optimizer p then implies that there is a constant λa→ _ a such that p[Ci(N)∣A~=a→]pi=λa→,i∈supp(p). E_p[C_i(N) A= a]p_i= _ a, i (p). Since ∑i∈supp(p)Ci(N)=N _i (p)C_i(N)=N almost surely and ∑i∈supp(p)pi=1 _i (p)p_i=1, multiplying by pip_i and summing over i∈supp(p)i (p) identifies this constant as λa→=p[N∣A~=a→] _ a=E_p[N A= a]. For i∉supp(p)i (p), both sides of (51) are exactly zero. ∎ Proof of Theorem 6. For any Alg1∈1o(ν)Alg_1∈ A_1^o(ν) and any i with νi>0 _i>0, Lemma 26 gives pip[N∣A~1=i]=p[Ci(N)∣A~1=i]≥1.p_iE_p[N A_1=i]=E_p[C_i(N) A_1=i]≥ 1. Averaging over A~1∼ν A_1 ν shows that its M-cost is at least ∑i:νi>0νi/pi _i: _i>0 _i/p_i. For RDC, conditional on the target draw A1⋆=iA_1 =i, the stopping time is geometric with success probability pip_i and mean 1/pi1/p_i. Again, averaging over A1⋆∼νA _1 ν then shows its M-cost equals the lower bound, proving the result. ∎ A.8.3 Proof of Theorem 7 Proof. Let Algm∈mo(ν)Alg_m∈ A_m^o(ν). On the event the returned attribute sequence of AlgmAlg_m is A~=a→ A= a, feasibility (cf. Equation 3) implies Ci(N)≥∑j=1m1aj=iC_i(N)≥ _j=1^m1\a_j=i\. Hence, Lemma 26 and averaging over A~∼ν A ν gives p[N]≥ν[maxi∈supp(p)Lipi],E_p[N] _ν [ _i (p) L_ip_i ], (53) where Li=∑j=1m1A~j=iL_i= _j=1^m1\ A_j=i\ are the attribute counts associated with an output attribute sequence A~∼ν A ν. Taking the infimum gives a lower bound for muniv(p,ν)C_m^univ(p,ν). For RDC, let Li=∑j=1m1Aj⋆=iL_i= _j=1^m1\A_j =i\ be the attribute counts of the target attribute sequence A→⋆∼ν A ν. Define Ti=inft≥0:Ci(t)≥LiT_i= \t≥ 0:C_i(t)≥ L_i\ for i with pi>0p_i>0, so that Ti=0T_i=0 when Li=0L_i=0 and Tν⋆=maxi∈supp(p)TiT_ν = _i (p)T_i almost surely. Conditional on L→ L, TiT_i is thus a negative binomial random variable with success rates pip_i and number of successes LiL_i. Consequently, p[Ti∣L→]=Lipi,Varp(Ti∣L→)=Li(1−pi)pi2.E_p[T_i L]= L_ip_i, _p(T_i L)= L_i(1-p_i)p_i^2. (54) Furthermore, Tν⋆≤maxi∈supp(p)Lipi+(∑i∈supp(p)(Ti−Lipi)2)1/2T_ν ≤ _i (p) L_ip_i+ ( _i (p) (T_i- L_ip_i )^2 )^1/2 by the deterministic inequality maxixi≤maxiyi+∑i(xi−yi)21/2 _ix_i≤ _iy_i+ \ _i(x_i-y_i)^2 \^1/2 for real vectors with coordinates xi=Tix_i=T_i and yi=Li/piy_i=L_i/p_i. Jensen’s inequality and Equation 54 gives p[Tν⋆∣L→]≤maxi∈supp(p)Lipi+(∑i∈supp(p)Li(1−pi)pi2)1/2.E_p[T_ν L]≤ _i (p) L_ip_i+ ( _i (p) L_i(1-p_i)p_i^2 )^1/2. Averaging over L→ L and applying Jensen’s inequality again yields mRDC(p,ν)≤ν[maxi∈supp(p)Lipi]+(∑i∈supp(p)ν[Li](1−pi)pi2)1/2.C_m^RDC(p,ν) _ν [ _i (p) L_ip_i ]+ ( _i (p) E_ν[L_i](1-p_i)p_i^2 )^1/2. Combining this with (53) and noting ν[Li]=∑j=1mνj(i) _ν[L_i]= _j=1^m _j(i) gives the final result mRDC(p,ν)−muniv(p,ν)≤(∑i∈supp(p)(∑j=1mνj(i))⋅1−pipi2)1/2.C_m^RDC(p,ν)-C_m^univ(p,ν)≤ ( _i (p) ( _j=1^m _j(i) )· 1-p_ip_i^2 )^1/2. (55) ∎ A.8.4 Proof of Theorem 8 Proof. Let Algm∈m(ν) Alg_m∈ A_m(ν). Denote its stopping time as N and its returned attribute sequence A~∼ν A ν. The process Ci(t)−pitC_i(t)-p_it is a martingale with bounded increments for the source count filtration t≔σC→(s):0≤s≤t.G_t σ\ C(s):0≤ s≤ t\. Doob’s optional stopping theorem applied at the bounded stopping time N∧nN n gives p[Ci(N∧n)]=pip[N∧n]E_p[C_i(N n)]=p_iE_p[N n]. Letting n→∞n→∞ and applying the monotone convergence theorem then yields p[Ci(N)]=pip[N]E_p[C_i(N)]=p_iE_p[N]. Universal exactness requires Prp(A~j=i)=νj(i) _p( A_j=i)= _j(i) for each j∈[m]j∈[m], so that feasibility (cf. Equation 3) implies ∑j=1mνj(i)=p[∑j=1m1A~j=i]≤p[Ci(N)]=pip[N]. _j=1^m _j(i)=E_p [ _j=1^m1\ A_j=i\ ] _p[C_i(N)]=p_iE_p[N]. Dividing by pip_i and maximizing over i∈supp(p)i (p) gives the final result p[N]≥maxi∈supp(p)∑j=1mνj(i)pi.E_p[N]≥ _i (p) _j=1^m _j(i)p_i. (56) ∎ A.8.5 Minimal sufficiency of source counts Proposition 27 (Minimal sufficiency of source counts). Fix a deterministic sample size n≥mn≥ m. Under A1,…,An∼i.i.d.Categorical(p)A_1,…,A_n i.i.d. Categorical(p), the count vector C→(n) C(n) is minimal sufficient for p∈int(Δk−1)p ( ^k-1). Proof. An ordered attribute sample with counts c→ c has likelihood ∏ipici _ip_i^c_i, so the factorization theorem immediately gives sufficiency. For two samples with counts c→ c and c→′ c , their likelihood ratio is ∏ipici−ci′ _ip_i^c_i-c_i . This ratio is constant in p if and only if c→=c→′ c= c , since we may otherwise let a coordinate with nonzero exponent tend to zero while fixing the remaining coordinates to be positive. This shows that the ratio cannot be constant. The likelihood-ratio characterization of minimal sufficiency therefore yields the claim. ∎ A.8.6 Proof of Theorem 17 Proof. Fix t≥mt≥ m and condition on the feasible support Ωt≡Ωm(c→(t)) _t≡ _m( c(t)). On the event Tν⋆>t\T_ν >t\, A-RDC selects the newly feasible support s∈m,…,tD_s∈\D_m,…,D_t\ with probability ν(s)/αtν(D_s)/ _t by the memoryless property of exponential random variables, whenever αt>0 _t>0. Since Tν⋆≤t=A→⋆∈Ωt\T_ν ≤ t\=\ A ∈ _t\ and A→⋆∼ν A ν, we have Pr(Tν⋆≤t∣Ωt)=ν(Ωt) (T_ν ≤ t _t)=ν( _t). Then, for 0<αt≤10< _t≤ 1 and a→∈Ωt a∈ _t, the output attribute law of A-RDC conditional on the feasible support is Prp(A^t=a→∣Ωt)=ν(a→)+(1−αt)ν(a→)αt=ν(a→)αt=ν(⋅∣Ωt). _p( A_t= a _t)=ν( a)+(1- _t) ν( a) _t= ν( a) _t=ν(· _t). (57) Since the feasible support depends on the source-count process only through the count vector C→ C, this shows Equation 13. For a realized count vector C→(t)=c→ C(t)= c, feasibility implies the count-conditional output attribute law μ of any algorithm Algm∈mAlg_m∈ A_m is supported on Ωm(c→) _m( c). Applying the data processing inequality to the indicator function a→↦1a→∈Ωm(c→) a 1\ a∈ _m( c)\ then yields Df(μ∥ν)≥Df((1,0)∥(αt,1−αt))=Ψf(αt).D_f(μ\|ν)≥ D_f ((1,0)\|( _t,1- _t) )= _f( _t). (58) When αt>0 _t>0, the law μ=ν(⋅∣Ωt)μ=ν(· _t) attains the lower bound. When αt=0 _t=0, both sides of the inequality are f∞+f(0)=Ψf(0)f_∞+f(0)= _f(0), which may be infinite. Averaging (58) over the randomness of the source-count process C→(t) C(t) and taking the infimum over μ proves the lower bound of Equation 14. Finally, (57) shows that the count-conditional output attribute law of A-RDC is ν(⋅∣Ωt)ν(· _t) and thus attains this lower bound simultaneously for each t≥mt≥ m. ∎ A.8.7 Proof of Theorem 19 Proof. Since p∈int(Δk−1)p ( ^k-1), there is almost surely a finite time t0t_0 such that Ci(t0)≥mC_i(t_0)≥ m for every i∈[k]i∈[k]. At this time, Ωt0=[k]m _t_0=[k]^m and αt0=1 _t_0=1, so both Tν⋆T_ν and τf,ε _f, are bounded above by t0t_0 and hence almost surely finite, i.e. terminates almost surely. Observe that TA-RDC and A-RDC agree pathwise: A^Tν⋆∧τf,ε=A^τf,ε A_T_ν _f, = A_ _f, , since both equal A→⋆ A when Tν⋆≤τf,εT_ν ≤ _f, . Then, by Equation 13 in Theorem 17, TA-RDC’s output attribute law conditional on the feasible support Ωτf,ε _ _f, is ν(⋅∣Ωτf,ε)ν(· _ _f, ), and thus has divergence Ψf(ατf,ε) _f( _ _f, ) from ν. By convexity of f-divergences and construction of the certification stopping time, we then have Δfun(TA-RDC,ν,p)≤p[Ψf(ατf,ε)]≤ε. _f^un(TA -RDC;ν;p) _p[ _f( _ _f, )]≤ . ∎ A.8.8 Proof of Theorem 20 Lemma 28 (Bounds for a capped KL projection). Fix p,q∈int(Δk−1)p,q ( ^k-1), and write pmin=minipip_ = _ip_i and κ=maxiqi/piκ= _iq_i/p_i. For 1<R<κ1<R<κ, let s⋆s be the unique minimizer of the capped KL projection problem mins∈Δk−1si≤Rpi,i∈[k]DKL(s∥q). _ subarraycs∈ ^k-1\\ s_i≤ Rp_i,\ i∈[k] subarrayD_KL(s\|q). Its coordinates have the form si⋆=minλqi,Rpi,∑isi⋆=1,λ>1.s_i = \λ q_i,Rp_i\, _is_i =1, λ>1. (59) Define the weighted sum of the KKT multipliers g≔∑ipilogλqisi⋆.g _ip_i λ q_is_i . Then, for any 1≤ρ<R1≤ρ<R and r∈Δk−1r∈ ^k-1 satisfying ri≤ρpir_i≤ρ p_i for every i, DKL(s⋆∥q)+(R−ρ)g≤DKL(r∥q).D_KL(s \|q)+(R-ρ)g≤ D_KL(r\|q). (60) Moreover, g≥4pmin2(κ−R),andVarA∼s⋆(logsA⋆qA)≤g24pmin2.g≥ 4p_ ^2(κ-R), _A s ( s_A q_A )≤ g^24p_ ^2. (61) Proof. A minimizer exists by compactness and continuity, and is unique by strict convexity of the KL objective. The KKT conditions (Boyd and Vandenberghe, 2004, see, e.g.,) give the form in (59), with λ>1λ>1 because q is infeasible for 1<R<κ1<R<κ. Write ηi=log(λqi/si⋆)≥0 _i= (λ q_i/s_i )≥ 0, so that g=∑ipiηig= _ip_i _i. For the comparison bound, convexity gives DKL(r∥q) D_KL(r\|q) ≥DKL(s⋆∥q)+∑ilogsi⋆qi(ri−si⋆) ≥ D_KL(s \|q)+ _i s_i q_i(r_i-s_i ) =DKL(s⋆∥q)+∑iηi(si⋆−ri) =D_KL(s \|q)+ _i _i(s_i -r_i) =DKL(s⋆∥q)+∑iηi(Rpi−ri) =D_KL(s \|q)+ _i _i(Rp_i-r_i) ≥DKL(s⋆∥q)+(R−ρ)g, ≥ D_KL(s \|q)+(R-ρ)g, where the first equality uses ∑i(ri−si⋆)=0 _i(r_i-s_i )=0; the second equality uses ηi(si⋆−Rpi)=0 _i(s_i -Rp_i)=0 for every i; and the final inequality uses ri≤ρpir_i≤ρ p_i and ηi≥0 _i≥ 0. This proves (60). Choose j with qj/pj=κq_j/p_j=κ. Since Rpj<qj<λqjRp_j<q_j<λ q_j, we have sj⋆=Rpjs_j =Rp_j. Moreover, 1−Rpj=∑i≠jsi⋆≤λ(1−qj).1-Rp_j= _i≠ js_i ≤λ(1-q_j). Thus, using 0<Rpj<qj<10<Rp_j<q_j<1, ηj _j ≥logqj(1−Rpj)Rpj(1−qj) ≥ q_j(1-Rp_j)Rp_j(1-q_j) =∫Rpjqjdu(1−u) = _Rp_j^q_j duu(1-u) ≥4(qj−Rpj)=4pj(κ−R), ≥ 4(q_j-Rp_j)=4p_j(κ-R), where the last inequality follows from u(1−u)≤1/4u(1-u)≤ 1/4. Consequently, g≥pjηj≥4pj2(κ−R)≥4pmin2(κ−R),g≥ p_j _j≥ 4p_j^2(κ-R)≥ 4p_ ^2(κ-R), proving the first assertion of (61). For the variance bound, nonnegativity of the ηi _i gives 0≤ηi≤gpi≤gpminfor every i.0≤ _i≤ gp_i≤ gp_ every i. Since logsA⋆qA=logλ−ηA, s_A q_A= λ- _A, this random variable lies in an interval of length at most g/pming/p_ . Its variance is therefore at most g2/(4pmin2)g^2/(4p_ ^2), proving the second assertion of (61). ∎ Proof of Theorem 20 A lower bound on the universal source-rate-free M-cost. Fix m≥1m≥ 1 and ε≥0 ≥ 0. Let Algm∈mo Alg_m∈ A_m^o be universally (KL,ε)(KL, )-approximate, and let PAlgm(A~)P_ Alg_m( A) be its output attribute law (cf. Equation 2). Write N for its stopping time. We may assume p[N]<∞E_p[N]<∞, since otherwise the lower bound is immediate. Define its average marginal attribute probabilities as ci=1m∑j=1mPAlgm(A~j=i),i∈[k].c_i= 1m _j=1^mP_ Alg_m( A_j=i), i∈[k]. Further denote pmin=minipip_ = _ip_i, ρ=ρp,q⋆(ε/m)ρ= _p,q ( /m), and κ=maxiqi/piκ= _iq_i/p_i. By definition, 1≤ρ≤κ1≤ρ≤κ. The KL chain rule and convexity of KL divergence imply ε ≥DKL(PAlgm(A~)∥q⊗m) ≥ D_KL (P_ Alg_m( A) \|q m ) ≥∑j=1mDKL(PAlgm(A~j)∥q)≥mDKL(c∥q). ≥ _j=1^mD_KL (P_ Alg_m( A_j) \|q )≥ mD_KL(c\|q). (62) Feasibility and Wald’s identity then give mci=p[∑j=1m1A~j=i]≤pip[N],i∈[k];mc_i=E_p [ _j=1^m1\ A_j=i\ ]≤ p_iE_p[N], i∈[k]; see, also, the proof of Theorem 8. Hence, by 62, p[N]≥mmaxi(ci/pi)≥mρp,q⋆(ε/m)E_p[N]≥ m _i(c_i/p_i)≥ m _p,q ( /m), and taking the infimum gives m,εuniv(p,q)≥mρp,q⋆(ε/m).C_m, ^univ(p,q)≥ m _p,q ( /m). (63) Completion time bounds for multinomial demands. For an arbitrary s∈Δk−1s∈ ^k-1, let L→∼Mult(m,s) L (m,s) be an auxiliary demand sampled independently of the source-count process C→(t) C(t) (cf. Equation 3). Define the attribute completion times Ti=inft≥0:Ci(t)≥LiT_i= \t≥ 0:C_i(t)≥ L_i\ (as in the proof of Theorem 7) and the completion time Ts≔maxiTiT_s _iT_i. Then, from (54) and the law of total variance, p,s[Ti]=msipi,Varp,s(Ti)=msi(2−pi−si)pi2.E_p,s[T_i]= ms_ip_i, _p,s(T_i)= ms_i(2-p_i-s_i)p_i^2. Furthermore, since Ts=maxiTiT_s= _iT_i, (Ts−mmaxisipi)+2≤∑i(Ti−msipi)2, (T_s-m _i s_ip_i )_+^2≤ _i (T_i- ms_ip_i )^2, and taking expectations gives p,s[(Ts−mmaxisipi)+2]≤m∑isi(2−pi−si)pi2≤2mpmin2.E_p,s [ (T_s-m _i s_ip_i )_+^2 ]≤ m _i s_i(2-p_i-s_i)p_i^2≤ 2mp_ ^2. (64) In particular, the Cauchy–Schwarz inequality gives p,s[Ts] _p,s[T_s] ≤mmaxisipi+p,s[(Ts−mmaxisipi)+] ≤ m _i s_ip_i+E_p,s [ (T_s-m _i s_ip_i )_+ ] ≤mmaxisipi+p,s[(Ts−mmaxisipi)+2] ≤ m _i s_ip_i+ E_p,s [ (T_s-m _i s_ip_i )_+^2 ] ≤mmaxisipi+2mpmin. ≤ m _i s_ip_i+ 2mp_ . (65) Define the source-count stopping time σs=inft≥m:s⊗m(Ωt)≥1/2 _s= \t≥ m:s m( _t)≥ 1/2\. Conditional on the entire source-count process ∞≔σC→(u):u≥0G_∞ σ\ C(u):u≥ 0\, the completion time has distribution function Prp,s(Ts≤t∣∞)=s⊗m(Ωt),t≥m. _p,s(T_s≤ t _∞)=s m( _t), t≥ m. Then, by definition of σs _s and since Ts≥mT_s≥ m, Prp,s(Ts≥σs∣∞)≥12. _p,s(T_s≥ _s _∞)≥ 12. It follows that 12(σs−mmaxisipi)+2≤p,s[(Ts−mmaxisipi)+2|∞]. 12 ( _s-m _i s_ip_i )_+^2 _p,s [ (T_s-m _i s_ip_i )_+^2 |G_∞ ]. Taking expectations, using Cauchy–Schwarz, and using (64) yields p[σs]≤mmaxisipi+2mpmin.E_p[ _s]≤ m _i s_ip_i+ 2 mp_ . (66) The upper bound for TA-RDC. First suppose κ−ρ≤3/(2pminm)κ-ρ≤ 3/(2p_ m). TA-RDC stops no later than RDC, so applying (65) with s=qs=q gives m,εTA-RDC(p,q)≤mκ+2mpmin≤mρ+(32+2)mpmin<mρ+3mpmin. splitC_m, ^TA -RDC(p,q)&≤ mκ+ 2mp_ \\ &≤ mρ+ ( 32+ 2 ) mp_ <mρ+ 3 mp_ . split (67) Suppose now that κ−ρ>3/(2pminm)κ-ρ>3/(2p_ m), and set R=ρ+1pminm,1<R<κ.R=ρ+ 1p_ m, 1<R<κ. Let s=s⋆s=s and g be as in Lemma 28. An optimizer r⋆r in the definition of ρ=ρp,q⋆(ε/m)ρ= _p,q ( /m) satisfies ri⋆≤ρpir_i ≤ρ p_i and DKL(r⋆∥q)≤ε/mD_KL(r \|q)≤ /m. Thus, (60) gives mDKL(s∥q)≤ε−m(R−ρ)g=ε−mpming.mD_KL(s\|q)≤ -m(R-ρ)g= - mp_ g. (68) Fix a source state at time t such that β=s⊗m(Ωt)≥1/2β=s m( _t)≥ 1/2. For a sequence drawn from s⊗ms m, let Z=log(ds⊗m/dν)Z= (ds m/dν), where ν=q⊗mν=q m. Both product laws are positive on [k]m[k]^m. Conditional Jensen gives αt=βs⊗m[e−Z∣Ωt]≥βexp−s⊗m[Z∣Ωt]. _t=β\,E_s m[e^-Z _t]≥β \-E_s m[Z _t]\. By Cauchy–Schwarz, s⊗m[Z∣Ωt]−s⊗m[Z] _s m[Z _t]-E_s m[Z] =Covs⊗m(Z,1Ωt)β = Cov_s m(Z,1_ _t)β ≤Vars⊗m(Z)1−β≤Vars⊗m(Z). ≤ Var_s m(Z) 1-β≤ Var_s m(Z). Since s⊗m[Z]=mDKL(s∥q)E_s m[Z]=mD_KL(s\|q) and Vars⊗m(Z)=mVarA∼s(log(sA/qA))Var_s m(Z)=mVar_A s( (s_A/q_A)), we conclude that −logαt - _t ≤mDKL(s∥q)+mVarA∼s(logsAqA)+log2 ≤ mD_KL(s\|q)+ mVar_A s ( s_Aq_A )+ 2 ≤ε−m2pming+log2, ≤ - m2p_ g+ 2, where the last line uses (61) in Lemma 28 and (68). Our case assumption gives κ−R>1/(2pminm)κ-R>1/(2p_ m), so (61) implies m2pming>1>log2. m2p_ g>1> 2. Thus every state with s⊗m(Ωt)≥1/2s m( _t)≥ 1/2 satisfies the TA-RDC certificate. In particular, NKL,εTA-RDC≤τKL,ε≤σs.N_KL, ^TA -RDC≤ _KL, ≤ _s. Because R<κR<κ, at least one coordinate of s attains its cap, so maxi(si/pi)=R _i(s_i/p_i)=R. Applying (66) therefore gives m,εTA-RDC(p,q)≤mR+2mpmin=mρ+3mpmin.C_m, ^TA -RDC(p,q)≤ mR+ 2 mp_ =mρ+ 3 mp_ . (69) Together, (63), (67), and (69) yield, for εm/m→δ _m/m→δ, ρp,q⋆(εm/m)≤m,εmuniv(p,q)m≤m,εmTA-RDC(p,q)m≤ρp,q⋆(εm/m)+3pminm≤m,εmuniv(p,q)m+3pminm. split _p,q ( _m/m)&≤ C_m, _m^univ(p,q)m≤ C_m, _m^TA -RDC(p,q)m\\ &≤ _p,q ( _m/m)+ 3p_ m\\ &≤ C_m, _m^univ(p,q)m+ 3p_ m. split The last inequality is the finite-sample bound on the M-cost of TA-RDC in Equation 20. The sandwich bound of the first and second inequality show the first-order asymptotic limits in Equation 19. Finally, since m,εuniv(p,q)≥mC_m, ^univ(p,q)≥ m for any post-processing algorithm Algm∈m Alg_m∈ A_m, 1≤m,εTA-RDC(p,q)m,εuniv(p,q)≤1+3pminm1≤ C_m, ^TA -RDC(p,q)C_m, ^univ(p,q)≤ 1+ 3p_ m holds uniformly in ε≥0 ≥ 0. Taking the supremum over ε proves the uniform relative optimality statement of Equation 21. ∎ A.8.9 Proof of Theorem 23 Proof. Denote the set in the statement by ℰnE_n. Fix an interior source rate p0∈int(Δk−1)p_0 ( ^k-1). The assumed bound gives Prp0(N≤n)=1 _p_0(N≤ n)=1. Collect all E randomization in a random seed U whose law does not depend on p. In the fixed attribute conditional mixture family, the likelihood ratio of the first n M-samples and U under an interior p relative to p0p_0 is dPrpdPrp0(Y1:n,U)=∏t=1npAtp0,At=∏i=1k(pip0,i)Ci(n). d _pd _p_0(Y_1:n,U)= _t=1^n p_A_tp_0,A_t= _i=1^k ( p_ip_0,i )^C_i(n). This likelihood ratio is strictly positive and finite. Since N is a stopping time, N>n\N>n\ is determined by the first n M-samples and the E randomization used by then. It follows that Prp(N≤n)=1 _p(N≤ n)=1 for every interior p. Since N≥mN≥ m, necessarily n≥mn≥ m. Continue drawing unused M-samples after the algorithm stops until time n, without changing its output, and let C→≡C→(n) C≡ C(n) be the count vector of these n samples. For w→∈[k]n w∈[k]^n and a→∈[k]m a∈[k]^m, put Rw→(a→)=Pr(A~=a→∣A1:n=w→).R_ w( a)= ( A= a A_1:n= w). This probability integrates over the fixed attribute conditional output laws and the algorithm’s E randomization, so it does not depend on p. Conditional on C→=c→ C= c, all attribute sequences with count vector c→ c are equally likely. Therefore Qc→(a→)=Prp(A~=a→∣C→=c→)=1Mc→∑w→∈[k]nC(w→)=c→Rw→(a→),Mc→=n!∏i=1kci!,Q_ c( a)= _p( A= a C= c)= 1M_ c _ subarrayc w∈[k]^n\\ C( w)= c subarrayR_ w( a), M_ c= n! _i=1^kc_i!, and Qc→Q_ c does not depend on p. Write pc→=∏ipicip c= _ip_i^c_i. For every a→∈[k]m a∈[k]^m, Fa→(p)=Prp(A~=a→)−ν(a→)=∑|c→|=nMc→pc→(Qc→(a→)−ν(a→)),F_ a(p)= _p( A= a)-ν( a)= _| c|=nM_ cp c (Q_ c( a)-ν( a) ), where the last equality uses ∑|c→|=nMc→pc→=(∑ipi)n=1 _| c|=nM_ cp c=( _ip_i)^n=1. After substituting pk=1−∑i=1k−1pip_k=1- _i=1^k-1p_i, each Fa→F_ a is a polynomial in p1,…,pk−1p_1,…,p_k-1. Suppose ℰnE_n had positive (k−1)(k-1) dimensional Lebesgue measure. Each Fa→F_ a would then vanish on a set of positive measure. Since the zero set of a nonzero real polynomial has Lebesgue measure zero, every Fa→F_ a must vanish identically on the open simplex. Hence p[QC→(a→)−ν(a→)]=0E_p [Q_ C( a)-ν( a) ]=0 for every interior p and every a→∈[k]m a∈[k]^m. The family C→∼Mult(n,p) C (n,p) is complete, so Qc→(a→)=ν(a→)Q_ c( a)=ν( a) for every c→ c with |c→|=n| c|=n and every a→∈[k]m a∈[k]^m. Here, every such c→ c has positive probability under an interior p. But when c→=ne→i c=n e_i, every available attribute is i, and feasibility forces Qne→i=δ(i,…,i)Q_n e_i= _(i,…,i). Taking two different attributes would make the fixed law ν equal to two different point masses. This is impossible because k≥2k≥ 2. Therefore, ℰnE_n has measure zero. ∎