Block-OSRB: Exact Output-Statistic Rao–Blackwellization for Aggregate-Invariant Vector Black-Box Optimization

Optimizing differentiable models against vector-valued black-box scores is expensive when each query evaluates thousands of binary decisions. Many utility and fairness scores depend only on public aggregates, despite an unknown mapping from aggregates to values. We ask whether this structure can reduce gradient noise without increasing oracle queries. Block Output-Statistic Rao–Blackwellization (Block-OSRB) conditions a two-query antithetic estimator on paired block aggregates, integrating out row identities invisible to the evaluator. The same two oracle values suffice for every row, without counterfactual calls. For independent Bernoulli decisions, the estimator is unbiased for the unsmoothed objective and has no greater covariance than its DisARM parent for each output column. Nested blocks provide a variance–compute path; common refinement gives joint covariance control, and weighted-total conditioning dominates weight-category count conditioning. On Adult, ACSIncome, Waterbirds, and UCI Credit, count Block-OSRB has lower mean one-time holdout hypervolume regret in all eight task–budget cells than the evaluated DisARM and true UGC arms: 2.0–19.7% and 2.2–23.8% reductions, respectively. The first three DisARM holdouts use the ordinary parent; UCI Credit uses relevance masking. A separately frozen Student Dropout trainable-MLP test shows an estimator gain, while a deterministic group-ranking policy performs better. On weighted UCI Credit development data, conditioning on totals removes 59.4–60.7% of the covariance trace remaining after category-count conditioning. The approach targets declared aggregate interfaces when oracle queries dominate local computation.