Ad Auctions for LLMs via Retrieval Augmented Generation

We appreciate the reviewer for thoughtful and detailed comments.

The paper uses strong assumptions on the retrieval component

We agree that implementing a performant, calibrated retrieval component is a challenging engineering task in practice. However, it is well studied in the literature. We refer to McMahan et al. [1] and Graepel et al. [2] for descriptions of actual click-through rate estimation systems at Google and Microsoft. Both papers have sections on calibration using isotonic regression. We will cite these works and add some more discussion of calibration to the paper based on the reviewer’s comments.

For our experimental evaluation, we view retrieval and calibration as modular components, where various implementations could be used in practice. Our evaluation uses embedding similarity as a measure of similarity because RAG commonly uses vector embeddings for retrieval. Vector embeddings capture semantic information and enable efficient similarity search, but as mentioned above, other options are possible. As we did not conduct the real-world experiment with an implemented system, our experiments are bound to use a proxy measure. We also kindly refer to simultaneous work by Dubey et al. [3] that pose the same assumption on the calibrated relevance (in their words, prominence).

1. McMahan et al.: Ad Click Prediction: a View from the Trenches, KDD’13
2. Graepel et al.: Web-Scale Bayesian Click-Through Rate Prediction for Sponsored Search Advertising in Microsoft’s Bing Search Engine, ICML‘10
3. Dubey et al.: Auctions with LLM Summaries, Dubey, Feng, Kidambi, Mehta, Wang, KDD’24

Under the general segment auction exposited in Appendix C

Modern click-through rate estimation and retrieval systems take many contextual features to make their predictions. We refer again to papers [1, 2] cited above. In our application, prior generated output would be included as contextual features. We agree this is important and nontrivial to handle in practice, but again view this aspect as orthogonal/modular to the question of auction design tackled in our paper.

The five types of auctions considered in the Experiment section

Thank you for raising this point. In our camera-ready draft, we will elaborate on our choice of baselines and how our results highlight trade-offs between mechanisms in terms of output quality, revenue, and social welfare. Here’s a brief intuition. We refer to L#242-250 regarding different baselines and L#271-287 for interpreting the results.

In summary: (1) Naive II generates the highest revenue but results in the lowest relevance and social welfare, potentially incorporating unrelated ads and diminishing user experience; (2) Segment auctions with replacement achieve the best social welfare and relevance but lead to lower minimum social welfare; (3) Multi-allocation produces competitive results with segment auctions without replacement but sacrifices revenue.

Tables 2 and 7 evaluate LLM output under different mechanisms. We measure relevance to the original output (without ads). Multi-allocation mechanisms generally produce better outputs, as longer segments with more ads lead to more coherent results. Single-allocation auctions with shorter segments result in lower quality. Naive I and II lead to the lowest quality due to the inclusion of irrelevant ads. Segment auctions without replacement show marginal improvement over those allowing replacement.

These results highlight the trade-offs between different criteria, guiding the auctioneer to select the appropriate mechanism or a combination based on their requirements.

Figure 4 suggests that the addition of ads impairs..

We kindly refer the reviewer to global rebuttal. As seen in the attached pdf, in 3rd paragraph in the first sample and in particular 2nd paragraph in the second sample, the output still answers the query. These can further be improved with more prompt engineering.

Augmenting an irrelevant ad appears to come with a significant cost to the quality of the output

Like standard search auctions, target ads can be prefiltered to exclude irrelevant ones. Most ad platforms use prefiltering to reduce computational load and maintain user satisfaction. Therefore, we assume all ads are relevant in L#31.

Privacy / reliability issue

We agree that integrating ads without privacy or robustness issues is crucial. However, our main focus is to introduce the RAG integration into the LLM ad system, validate its feasibility, and derive theoretical and empirical evidence. Our paper doesn’t address every practical issue. Similar perspectives are taken by Duetting et al., Dubey et al., and Soumalias et al. For broader technical concerns like privacy and reliability in LLM ad systems, refer to Feizi et al.'s survey paper.

1. Dubey et al.: Auctions with LLM Summaries, KDD’24
2. Duetting et al.: Mechanism Design for Large Language Model, WWW’24
3. Soumalias et al.: Truthful Aggregation of LLMs with an Application to Online Advertising
4. Feizi et al: Online Advertisements with LLMs: Opportunities and Challenges

How will the relevance measure be obtained if the mechanism is put into practice?

We refer to the cited papers on CTR prediction for calibration. While we use vector similarity as a proof of concept, more research is needed on designing effective metrics to measure relevance between queries and ads.

The qualitative results show that the generated output stops providing useful information.

Please see our response above.

Can these alternative pricing schemes can be easily implemented?

As can be seen from our randomized segment auction, any pricing scheme can be implemented from our idea - randomly perturb $q_i \cdot b_i$, and apply any mechanism as desired. For instance, perturbing the bids and then run GSP (Figure 3) does not induce incentive-compatible mechanism as VCG does, however, this would be a reasonable analogue of the GSP auction widely adopted in the sponsored search auction.

We appreciate the reviewer's responsiveness.

Novelty

We first emphasize that our main contribution is to propose the idea of combining RAG and ad auctions for LLM and laying down a foundation in this line of research. Indeed, even though applying RAG into the LLM ad auction seems a very plausible direction, there has been no single work dedicated to it. That is to say, our primary objective and contribution is to propose a potentially promising framework for the LLM ad auctions, which we believe will inevitably emerge in a near future, and validate its feasibility. Although RAG was introduced in 2020 and advertising has long been a fascinating field of study, the integration of ads within the RAG framework (to potentially monetize LLMs) is a novel approach that was not studied theoretically nor validated through empirical research.

As the reviewer agreed with the idea of perturbation, although this idea is easily understandable in hindsight, it is not easy to come up with at first glance. Also, we think that the idea of reverse-engineering the mechanism design by starting from an exogenously given allocation function by RAG is not a trivial perspective to derive. We respectfully disagree with the reviewer that a paper necessarily includes complicated theoretical techniques or proofs, but believe that simple and concise but novel ideas often advance the fields in many directions.

Finally, as the reviewer pointed out, delving more into logarithmic social welfare seems very promising research directions. We indeed have exposited several initial properties in Appendix D including that it can be viewed as a version of weighted Nash social welfare, but further theoretical results remains open problems, e.g., whether this is consistent with other notions of fairness in terms of reachability/approximability. We will make this point clearer in the main body of the paper.

Experiments with longer segments

We would like to emphasize that optimizing the incorporation of ads into the LLM output, via prompt engineering, is not a goal of this paper. Our intention in the experiments was to provide a proof of concept with basic, straightforward prompts, to confirm that the approach was viable (and surely in practice we may apply this approach for longer answers etc for quality purposes).

Having said that below we bring another sample that we obtained using the single ad segment auction without replacement, even without much of prompt engineering (we just reused the original prompts but slightly added a bit: keep answering the query without deviating from it by fully focusing on the ads). We conducted this experiment several times, and found that LLM has been pretty consistent on almost all of them, i.e., a rather simple prompting structure would work.

(Segment 1) If you appreciated the thematic depth and moral introspection of "To Kill a Mockingbird," you might enjoy exploring similar narratives like "The Help" by Kathryn Stockett or "A Time to Kill" by John Grisham. Find these titles easily at BookHaven, your ultimate online bookstore. With an extensive collection and personalized recommendations, BookHaven ensures a seamless shopping experience. Dive into a world of endless possibilities with BookHaven, where every book finds its perfect reader.

(Segment 2) Additionally, consider delving into classics such as "Cry, the Beloved Country" by Alan Paton, which, like Harper Lee's masterpiece, offers profound insights into social justice and empathy. Pair your reading experience with a visit to EspressoEdge, where each sip of their high-quality, handcrafted beverages provides a moment of luxury. Savor rich espressos or creamy lattes while you immerse yourself in timeless literature at EspressoEdge.

(Segment 3) For a contemporary twist, you might also enjoy "Small Great Things" by Jodi Picoult, a novel that tackles race and prejudice in modern society. Enhance your reading experience with Velora's range of tablets and e-readers, which offer crisp displays and user-friendly interfaces. Velora's smart devices ensure your favorite books are always accessible, whether you're at home or on the go. Elevate your tech experience with Velora.

We can definitely include these samples in the appendix for the camera ready if the reviewer finds it informative.

Thanks for the detailed response and the new example, this is helpful to know. I'll think about the authors response, and wait for the other reviewers' response and discussion before making a final decision on my rating.

Edit: The new example given by the authors partly addresses a concern raised in my original review so I will slightly adjust my rating accordingly. My other points remain the same at the moment.

We appreciate the reviewer’s valuable comments.

Independent assumption

We in fact extend our independent segment auction to a more general segment auction with history dependent relevance measure in Appendix C. We will make sure to add a pointer to this part in the main body of the paper. In the dependent segment auction, our notion of relevance depends on the previous tokens. In this case, since the relevance measure that determines the value of the objective function LSW might arbitrarily depend on the previous tokens, from the computational perspective, it requires the extension of every possible token sequence to exactly optimize the objective function without no assumption. Interestingly, we show that our segment auction can be viewed as a local greedy algorithm that approximates the globally optimal allocation rule. More precisely, our segment auction chooses next tokens to maximize LSW given that previous tokens are fixed.

Question on the repetition

The reviewer is correct - our segment auction repeatedly runs to determine the output for each segment, where there are flexibilities in determining what to choose as a segment. Also our multi-ad segment auction further allows flexibility in determining how many ads to allocate within a segment.

After reviewing the authors' rebuttal and other reviews, I have several points to raise:

Modeling Approach: The paper employs hard insertion instead of model fusion to recommend an RAG-based sponsored search. This choice seems suboptimal, especially considering concurrent theoretical work (see https://arxiv.org/pdf/2407.04471) that utilizes specific model fusion methods for similar tasks. However, given that this concurrent work was published post NeurIPS 2024 deadline, it's understandable that the authors did not reference it.

Empirical Performance: I concur with Reviewer 2L4f's concerns regarding empirical performance. More comprehensive evaluations are needed to substantiate the proposed method's efficacy.

I still maintain my current score, but I want to second that there are indeed some points worth noticing in this paper.

We appreciate the reviewer for detailed review. We hope that our rebuttal can address your concerns. Note that our framework consists of several components, each of which could be further researched to improve real-world deployment. Our focus was on proposing the framework, analyzing it theoretically, and evaluating it with simple yet efficient methods.

The technical novelty of the proposed method seems limited.

We kindly ask the reviewer to see our general response in “Novelty of the paper”

The experimental evaluation should include more baseline methods.

Our framework on ad auctions LLM is indeed the first study to explore ad auction framework within the LLM’s textual output, so we compare our mechanisms with simple mechanisms that one might naively think of. There are simultaneous works by Aranyak and Soumalias, however, we remark that these works do not explicitly compare their mechanisms with one another due to the lack of existing/standard benchmarks, but also only considers a naive version of auctions, e.g., greedy append of ad documents similar to our naive mechanism. We kindly ask the reviewer to let us know if the reviewer has any specific auction to compare in mind.

First, simply comparing the cosine similarity of embeddings between the output text and the original text without ads may not sufficiently indicate the text quality.

Measuring text quality while including advertisements is a challenging research question that requires further exploration by the NLP community. Traditional metrics like ROUGE may be unsuitable due to ads in the output and the absence of ground truth. While our framework's validation employed semantic similarity as a proxy for quality, qualitative analysis suggests our framework generally produces high-quality outputs. We acknowledge that this aspect could open a promising research area.

On one hand, comprehensive metrics like perplexity could be incorporated.

Thank you for your valuable suggestion. We found that comparing perplexity is indeed useful and conducted experiments using the LLaMA3 8B model. We measured perplexity (given the query) for outputs in scenario 1 (100 samples per mechanism). Perplexity was low for original outputs but increased significantly when ads were included. Auction mechanisms that allow replacements showed slightly lower perplexity due to ad replication, which reduces model surprise. Other baselines performed competitively in terms of perplexity.

Note that while perplexity is a useful measure, it doesn't fully capture how well the model responds to the query or the overall output quality. This limitation highlights an interesting problem that requires further research to develop better metrics for evaluating response relevance and quality.

On the other hand, the quality of the advertising content in the text has not been considered.

Thanks to the reviewer for pointing this out, It indeed raises an interesting and fundamental research question for the general RAG framework: how effectively does the model utilize retrieved documents? There has been extensive study to evaluate RAG output given its retrieved documents. We believe that this problem requires further analysis in ad domain specifically.

In our framework, we assumed for simplicity that when an ad is selected, the LLM can effectively integrate it into the output. Qualitative results support this assumption, demonstrating that the model properly blends ads into the generated output.

Second, there is a lack of overall results that can demonstrate how well this method achieves the tradeoff between advertising effectiveness, output quality, allocating efficiency, and fairness.

We note that qualitative results show that our proposed approach is feasible and recent LLMs like GPT4 are useful for this framework. We used simple but efficient proxies for measuring ads relevance and output quality that compares different baselines and show that output quality of our mechanism is pretty reasonable. A bit more formally, advertising effectiveness and allocating efficiency can be captured via social welfare, output quality can be captured via relevance, and fairness can be captured via minimum social welfare as stated in L#260~265.

We first appreciate the reviewer for insightful comments.

About unclear selection of optimization function

The reviewer is correct that it is chosen after the allocation function of segment auction is determined. We remark that our selection of optimization functions stems from the probabilistic retrieval nature of the RAG framework. RAG framework suggests retrieving each document proportional to the probability $p_\eta(a_i | x)$. Thus, we restrict our mechanism to have the same allocation function so that the overall architecture exactly resembles the RAG framework but with ad documents. In hindsight, we observe that such an allocation function maximizes LSW, which has never been studied in the literature to the best of our knowledge. We firmly believe that LSW may play a crucial role as an objective function in ad auctions for LLMs in further works, and also we found that it achieves a balance between fairness and efficiency in a similar vein with the Nash social welfare.

Does segment auction maximize SW? What is the auction design for SW optimality?

In fact, an (single-allocation) auction that maximizes SW will be any auction that selects an ad with the highest value of $q_i \cdot b_i$, e.g., second-price auction or first-price auction. As per the revenue-equivalence theorem by Myerson’82, all these auctions would induce the same revenue, whereas our segment auction intentionally deviate from such SW-maximizing allocation function to be consistent with the probabilistic retrieval of RAG, i.e., in order to improve the overall quality of LLM outputs themselves.