Truthful Aggregation of LLMs with an Application to Online Advertising

Thank you for the review. Below are our responses: **"No real-world testing with actual advertiser data."** This is a great suggestion and we would really like to do it. The problem is that any such data would be closely held by advertising companies, and we don’t have access. As far as we are aware, there is no such public data available. **“An analysis of how the mechanism handles scalability under different numbers of candidate replies or advertisers:”** In Section 4.2, we explain why we consider our mechanism computationally efficient. Our mechanism scales linearly in both the number of participating advertisers and the number of candidate replies. This is also the case for the first and second price auctions that are used by major online platforms to run hundreds of billions of ad auctions on a yearly basis. We will expand on this section in the final version of the paper. **"Given that the mechanism optimizes for advertiser reward and divergence from a reference LLM, there is a risk of unintentional bias in the final output.”** In Section 4.1 and Appendix A.2, we prove that MOSAIC is an unbiased estimator of the optimal distribution for the platform’s objective. If the platform’s objective is unbiased, the same will be true for the output of our estimator. If bias here refers to societal bias, then using a base LLM which has been post-trained to remove such bias should help mitigate this issue. **"What is the mathematical variance of the estimator?**" The precise variance is provided in Section 4.1, lines 239-245, with a detailed derivation in Appendix A.2. **"Convergence rate with number of candidate sequences."** In section 6.2 figure (a), we show experimentally that MOSAIC can converge to the target distribution using 20 candidate replies. In Section 4. and appendix A.2, we show MOSAIC’s variance as an estimator. From the form of that variance, using standard concentration inequalities we can prove that our estimator converges to the true distribution at a rate proportional to 1$/\sqrt{M}$, where $M$ is the number of candidate replies generrated. We will add this detailed derivation in the appendix. **"How does the choice of hyperparameter $\tau$ qualitatively influence the trade-off between advertisers’ rewards and divergence from the reference LLM?"** The reference LLM can be interpreted as one additional advertiser with her own reward function. By setting $\tau$ equal to 1, all participants (the reference LLM and the advertisers) are treated equally. By setting $\tau$ to any other number, it is as though we insert $\tau$ such identical “reference LLM participants” in the auction. Thus, larger values of tau place more weight towards the reference LLM, and smaller values place more value towards the advertisers. **"The strategy proofness guarantee hinges on honest reporting by advertisers. But how robust is MOSAIC if advertisers engage in complex forms of gaming?"** MOSAIC is **dominant** strategy incentive compatible. This means that it is always in an advertiser’s best interests to report truthfully her preferences, even if the other advertisers are misreporting. There are no complex forms of gaming that will result in better outcomes for the advertisers – at least not unilaterally. This is one of MOSAIC’s greatest strengths. If advertisers are able to collude with each other, they might be able to benefit themselves, but this is an unavoidable problem that always arises in strategyproof mechanism design, and platforms can prevent this possibility in practice. **"In scenarios where advertisers have strongly opposing interests, does MOSAIC risk generating responses that conflict with each other?"** Potentially yes, but the platform’s objective can account for this. Intuitively, if the total utility of an "equivocating" answer for advertiser A and advertiser B is less than either "just prefer A", or "just prefer B", a single advertiser is more likely to be picked. On the other hand, if the advertisers are happy to be promoted together, that outcome is more likely. In our experiments, MOSAIC only includes 54% of the advertisers on average when it has converged, as opposed to 81% prior to convergence. We will include this result in the appendix.

Thank you for the helpful review. Below are our responses: **"Differences between reference and context-aware LLM from a theoretical perspective."** In Section 4.1, lines 239-246, we explain how our allocation rule is an importance-sampling based estimator, and show how the variance of that estimator depends on how well the LLM that generates the candidate replies “matches” with the reference LLM. If that LLM is not tuned well, the variance of the estimator will blow up, meaning it will require more samples to achieve the same quality of approximation. We provide all details in Appendix A.2. **"Do the authors have any preliminary insights for how to introduce contextual information into the current model?"** This depends on the application. For our flagship application of online advertising, we detail how we do this in the footnote of line 269. For 50 practical examples, please see the file advertiser_prompts.py provided in the supplementary material. We will also include these examples in the appendix for convenience. **“Can the mechanism incorporate constraints such as advertisers’ budget/ROI constraints, or the maximum length of the LLM output?”:** Yes, MOSAIC can incorporate all three of these considerations. The maximum length of the output reply can be easily incorporated by the platform. The platform chooses the LLM that generates the candidate replies, and it can enforce that constraint in the reply generation. For budget constraints, the advertiser should only bid rewards up to her maximum budget. For ROI constraints, the advertiser should “bid shade” when reporting her reward function to ensure that their ROI constraint is satisfied. Both of these changes would lead to worse utility per instance for the advertiser compared to truthful bidding. This is the case for any strategyproof mechanism, with the upshot being that she can extend her budget to more auction instances. However, for our mechanism we can additionally prove a new version of the “what you give is what you get” property (equation (5)) for this case. Informally: if an advertiser’s shaded reported rewards still contribute to the social welfare of the final allocation, then her true utility will be positive, and even higher than Lemma 5.2 in the current version would suggest. We will add this discussion and the new theoretical result in the appendix.

Thank you for the constructive feedback. At a high level, we want to acknowledge your correct intuition that thinking about VCG is the right direction for this problem. This was also our starting point for this research project: “how can we apply a VCG-like mechanism to an RLHF setting?” However, the obvious ways of doing this either are intractable to implement, lose the nice properties of VCG in practice, or don’t target the objective we focus on. We took care to design a mechanism that can be implemented using familiar, easy operations on LLMs; can scale up or down with more or less compute; and, crucially, maintains good properties, even when scaled down. If it still looks very VCG-like even after meeting all those constraints, we consider this a success. Below, we address specific points: **"MOSAIC is only an approximation of VCG."** In Section 3.2, we clarify why VCG is not applicable in our setting. There are two versions of VCG to consider. Running VCG directly in distribution space is impractical due to high RLHF costs and latency constraints that the platform cannot afford on a per query basis, and it would not be strategy-proof without perfect convergence. Running VCG over a set of candidate replies also does not yield the optimal distribution for the platform's objective. Our allocation rule achieves this target, and implementing it in dominant strategies requires a different, non-VCG payment rule for truthfulness. Thus, while we are aiming for some similar goals, MOSAIC is not simply approximate VCG. **"Other contributions are case-by-case operations that do not bring significance to the mechanism itself."** These contributions are tailored specifically for online advertising, a multi-billion-dollar application, making them highly meaningful. **"Compare VCG with MOSAIC when applicable."** VCG is not applicable in our setting (see above). We consider naive MOSAIC a strong benchmark, as it also provably converges to the optimal distribution. Please also see our first reply to reviewer pFaF. **"Why define KL divergence with $\pi_{ref}$ on the right hand?"** We use the standard RLHF objective, which has led to significant progress in LLM performance over the past five years. In principle, the platform could choose some other notion of distance between the two distributions. As long as the corresponding optimization problem has a closed-form solution, MOSAIC is in principle applicable, under two requirements. The allocation rule would have to correspondingly change to correspond to the new target distribution, and the payment rule would have to change to ensure truthfulness. This can be achieved iff the new allocation rule also satisfies cyclic monotonicity due to [Rochet 1987]. **"If a sub-optimal solution is chosen, VCG’s strategy-proofness is no longer guaranteed."** Correct. There are numerous studies that detail how in general VCG’s strategy-proofness fails without the optimal solution, see (Nisan & Ronen, 2007; 1999; Lehmann et al., 2002). **"Feasible to sample from (2) using rejection sampling and $\pi_{con}$."** Indeed, there is a strong connection between our mechanism and rejection sampling, as there is a fundamental connection between rejection and importance sampling algorithms. Your rejection sampling suggestion using $\pi_{con}$ can be viewed as a dynamic, online version of MOSAIC, and would converge to the optimal distribution if advertisers reported truthfully. However, your rejection sampling proposal introduces two new challenges that make it inapplicable: Now the mechanism is dynamic, with each advertiser’s report in one round influencing follow-up rounds. The design of appropriate payments to make such a dynamic mechanism dominant strategy incentive compatible is much more challenging, and it is unclear if such payments even exist. Second, the mechanism can no longer be parallelized across the generation of candidate replies. Thus, even if this suggested mechanism converged using the same number of replies as ours, it would still result in a large increase in user-perceived latency compared to our mechanism or directly querying an LLM. **"MOSAIC’s performance in the presence of low-probability large rewards."** You have correctly identified many of the design challenges we faced. The aim of the context-aware LLM is precisely to solve this problem, and we make a formal argument of exactly how it achieves this goal in Section 4.1 and Appendix A.2. The variance of our allocation rule in Section 4.1 ensures that MOSAIC converges at a rate of $1/ \sqrt{M}$ regardless of the distribution of rewards. Additionally, please note that for our realistic prompts, we experimentally show that the use of the context-aware LLM solves this issue.

Thank you for the constructive feedback. We address each comment below: **"The authors can strengthen the differences between their proposed mechanism and the algorithms used in standard RLHF and rejection sampling."** Rather than emphasizing the differences, we want to highlight the similarities between our mechanism and traditional rejection sampling/RLHF. The use of these familiar operations, which are well-optimized and well-understood, is a key strength of our approach. Our focus was on building an incentive-compatible system from established, reliable components, rather than creating novel fine-tuning techniques that may be less practical or harder to optimize. **"No comparative analysis between MOSAIC and other mechanisms."** The only comparable mechanism in the literature that aggregates multiple LLMs is Duetting et al., which is not strategy-proof. Additionally, the authors provided no implementation details/code, making it very hard to compare against. The only other potential comparison is VCG, which, as explained in Section 3.2, is not applicable since it does not align with the platform’s objective. Hence, there is no valid baseline for comparison other than naive MOSAIC without advertiser contexts, which we consider a high benchmark given that it provably converges to the platform’s optimal distribution based on Corollary 4.1. **"Evaluate across different LLMs."** We have evaluated MOSAIC with T5, and the results were nearly identical. We will extend this evaluation with additional LLMs and include the results in the appendix. **"Could the authors provide the different prompts used in the experiments?"** All experimental prompts are available in the supplementary material under advertiser_prompts.py. We will also include them in the appendix for convenience. **"How different prompts affect the mechanism’s performance?"** MOSAIC’s performance across a wide range of prompts is demonstrated in our experiments (see section 6.2). Theoretically, the variance formula in lines 239-245 explains the impact of out-of-distribution prompts. Regardless of the prompt distribution, the variance result ensures that MOSAIC converges at a rate of $1/\sqrt{M}$, where $M$ is the number of candidate replies generated. Please also refer to our response to reviewer MGd7. **"Extend comparison to other mechanisms from similar studies."** Please refer to our response above regarding the unavailability of other comparable mechanisms. **"Utilize various closed-source models."** Our implementation is fully compatible with both open- and closed-source models, and the provided source code only relies on API calls compatible with both types of models. While testing with closed-source models is of interest, it is not an expense we can process with our institution in one week.

Thank you for your response, and the opportunity to clarify our contributions. Indeed, MOSAIC leverages established methods, which, as you noted, are both reliable and practical for addressing our problem. Our primary contribution, however, lies not in innovating these methods but in utilizing them to construct the first mechanism that simultaneously achieves: (a) truthfulness, (b) practical applicability for aggregating preferences over LLM-generated responses, and (c) provable convergence to the platform’s optimal objective. This is a transformative step forward in an area poised to become a multi-billion-dollar application, where no other mechanism in the literature fulfills more than one of these three objectives. Additionally, we tackled the critical challenge of free-riding, which could undermine the long-term success of mechanisms in this seting. We designed a novel payment rule that aligns advertiser utility with their contribution to social welfare, ensuring meaningful participation. This payment rule is theoretically sound and experimentally validated, with no prior work addressing this issue, further highlighting the novelty of our approach. Thank you as well for clarifying your concern regarding Corollary 4.1. To address this: the corollary establishes that our mechanism converges at a theoretical rate of $1 / \sqrt{M}$, independent of the reward distribution. While it is true that comparison with baselines is infeasible due to the lack of existing mechanisms addressing this problem, this highlights precisely why our contribution is novel. Although real-world testing is not yet possible due to the absence of appropriate datasets, our experimental results provide robust evidence of MOSAIC’s practicality. Specifically, we demonstrated that for realistic prompts and a representative distribution of advertisers, our mechanism converges rapidly to the platform's objective, yielding substantial value for advertisers and significant revenue for the platform. The results are statistically significant (as we tested 1250 instances) and generalize across different LLM architectures (as detailed in the revised version of the paper). Thus, we believe we have substantiated very robustly MOSAIC’s practical applicability and effectiveness in its flagship application of online advertising. To further address your concerns: could you clarify what additional empirical results you envision as necessary to substantiate MOSAIC’s practical applicability?