Discrete Prompt Optimization via Constrained Generation for Zero-shot Re-ranker

Motivation

• LLMs can serve as zero-shot re-rankers when prompted, but manual cross-validation over handcrafted prompts is expensive and may transfer poorly (Sachan et al., 2022).Earlier work highlights appropriate prompts as important for eliciting LLM performance without parameter updates.Source: §1 · p. 1

Research gap

• Existing discrete prompt-optimization methods focus on classification or mask-filling, while generation-oriented reinforcement learning uses discrete-label rewards and does not address re-ranking's continuous output scores (Shin et al., 2020; Gao et al., 2021; Prasad et al., 2022; Deng et al., 2022).Source: §1 · p. 1

Method

• Co-Prompt frames prompt search as constrained generation, using a zero-shot re-ranker to score prompt optimality and a decoder-only PLM to sample high-prior prompt tokens without additional training.The discriminator's metric estimates whether a prompt guides an LLM to distinguish relevant documents for a query; the generator restricts candidates for evaluation.Source: §1 · pp. 1–2

Results

• Co-Prompt consistently generates well-performing prompts across T0 and OPT on MSMARCO and Natural Question, with qualitative analyses finding human-like language patterns.The paper evaluates against other optimization baselines on both LLMs and datasets.Source: §1 · p. 2

Contributions

• The paper highlights the impact of prompt optimization for zero-shot re-ranking and presents Co-Prompt as a discrete optimization method for improving re-ranker guidance.Source: §1 · p. 2

Document Ranking with Generative Model

• Generative ranking methods use query likelihood scores, while Sachan et al. (2022, 2023) use LLMs for zero-shot re-ranking or unsupervised dense retrieval training.Unlike this paper, Sachan et al. require manually designed prompts, which may limit transferability.Source: §2 · p. 2

Prompt Optimization

• Prompt optimization includes discrete prompt search (Shin et al., 2020; Gao et al., 2021; Deng et al., 2022) and continuous-space soft prompt learning (Liu et al., 2021; Qin and Eisner, 2021; Lester et al., 2021).Prompt selection is important for LLM performance across NLP tasks (Kojima et al., 2022; Xie et al., 2022).Source: §2 · p. 2
• Existing prompt optimization focuses on classification or mask-filling, leaving discrete prompt optimization for zero-shot re-ranking underexplored.The paper targets higher relevance scores for more relevant query-document pairs via constrained generation.Source: §2 · p. 2

Constrained Generation

• Prior constrained-generation methods use discriminators to guide text toward constraints via Bayes’ rule; this paper uses a zero-shot re-ranker as the discriminator.Constrained generation derives text sequences that satisfy a specified constraint (Keskar et al., 2019; Dathathri et al., 2020; Krause et al., 2021; Chaffin et al., 2022).Source: §2 · p. 2

3.1 Preliminaries

• Because the prompt is the only controllable variable in the re-ranker’s scoring setup, the method focuses on optimizing it.The re-ranker scores a document with respect to a query through query-generation scoring.Source: §3.1 · p. 2

3.2 Constrained Prompt Generation

• Co-Prompt defines the optimal prompt as the one maximizing query-generation scores and uses a discriminator’s likelihood, based on relevance scores for sampled document-query pairs, to evaluate prompt quality.The discriminator measures how effectively a prompt guides the re-ranker to generate the query from a document.Source: §3.2 · pp. 2–3
• A decoder-only PLM samples likely prompt tokens, while beam search iteratively generates candidates and evaluates them with the discriminator.The generator avoids scoring every token in the vocabulary, which the paper describes as prohibitively costly.Source: §3.2 · p. 3

Datasets

• Experiments use MS-MARCO from Bing search logs and Natural Question (NQ) from Google search engines, evaluating only the datasets’ document data.The passages attribute MS-MARCO to Nguyen et al. (2016) and NQ to Kwiatkowski et al. (2019).Source: §4 · p. 3

Evaluation Metrics

• The study evaluates re-ranked results with ACC, the percentage of relevant retrieved documents, and nDCG, which rewards higher ranks for more relevant documents.Table 1 describes ACC@k at k = 20 and 100, but the supplied passage does not provide its scores.Source: §4 · p. 3, Table 1 · p. 3

Retriever & Re-ranker

• BM25 and DPR serve as sparse and dense retrievers, while T0 and OPT are the zero-shot re-rankers.The cited works are BM25 (Robertson and Zaragoza, 2009), DPR (Karpukhin et al., 2020), T0 (Sanh et al., 2022), and OPT (Zhang et al., 2022).Source: §4 · p. 3

Prompt Baselines

• Co-Prompt is compared with Null Prompt, P-Tuning, RL-Prompt, and a manual prompt, with P-Tuning and RL-Prompt adapted for re-ranking.The manual prompt, suggested by Sachan et al. (2022), is “Please write a question based on this passage”; Co-Prompt uses left-to-right zero-shot generation.Source: §4 · p. 3

Implementation Details

• The discriminator MD is the zero-shot re-ranker; for T0, GPT2-Large is the decoder-only generator, while OPT serves as both discriminator and generator; experiments use start token Please, beam width 10, and maximum prompt length 10.Source: §4 · p. 4

Environment

• Experiments run on V100 32GB GPUs with BEIR for retrieval and re-ranked-result evaluation, using publicly available 3B-parameter T0 and 2.7B-parameter OPT models.The passage cites BEIR (Thakur et al., 2021) and the Huggingface model hub (Wolf et al., 2020).Source: §4 · p. 4

Overall Results

• Co-Prompt shows robust performance gains across LLMs, datasets, and retrievers, and with OPT it outperforms the other methods.The authors attribute this to prompts that better serve as instructions for guiding LLMs than prompts from other optimization methods.Source: §5 · p. 4

Impact of Start Tokens

• Co-Prompt works efficiently with different start tokens, but choosing the optimal token for a dataset is important for better results.The alternatives tested include “Score” and “This.”Source: §5 · p. 4

Impact of Generator

• Different generators can produce prompts that guide the zero-shot re-ranker efficiently, but vocabulary mismatch between the generator and re-ranker affects performance.The authors suggest a more suitable generator may be needed for better results.Source: §5 · p. 4

Relevance Score

• Positive and BM25-retrieved negative document-query pairs have overlapping but distinct relevance-score distributions, and prompt optimization increases score mean and variance.The LLM can distinguish positive pairs even without a prompt.Source: §5 · pp. 4–5, Figure 2 · p. 4

Case Study of Prompts

• Co-Prompt generates human-interpretable, human-language-like prompts that outperform other discrete prompts, unlike the ungrammatical gibberish produced by RL-prompt.Its prompts include the task keyword “question” across datasets, which the authors say can help users understand how LLMs work.Source: §5 · p. 5

• Co-Prompt uses left-to-right constrained generation to restrict prompt candidates and evaluate the optimum without parameter updates.Source: §6 · p. 5
• The method outperformed consistently across the experiments, and the observed impact of prompt optimization highlights its importance for zero-shot re-ranking.Source: §6 · p. 5
• The optimal prompts were interpretable to humans; future work will extend the method to other open-ended generation tasks using LLMs.Source: §6 · p. 5

Limitations

• OPT is more suitable for Co-Prompt prompts than T0, which requires a separate generator such as GPT-2, and prompt performance may vary with the generator’s vocabulary and training process.The experiments demonstrate effectiveness in two LLMs.Source: Limitations · p. 5
• Increasing beam size and the number of document-query pairs raises the probability of finding a more optimal prompt but proportionally lengthens search time.Source: Limitations · p. 5

Ethics Statement

• The authors report no offensive or upsetting prompts in their experiments, but acknowledge this remains a possibility because of generator bias.The concern is stated despite the absence of such prompts in the experiments.Source: Ethics Statement · p. 5
• Because prompt optimization adds no training, Co-Prompt has difficulty removing bias already present in the language model.Source: Ethics Statement · p. 5
• The authors expect ongoing research on reducing language-model bias and filtering inappropriate text to sufficiently address these problems in the future.Source: Ethics Statement · p. 5

A.1 Datasets

• The experiments use MS-MARCO and Natural Questions (NQ), with 1,500 document-query pairs from each dataset used for prompt optimization.MS-MARCO has about 8M passages and 6,980 development queries; NQ has about 2M passages and 3,452 test queries.Source: §A.1 · p. 8

A.2 Metrics

• Evaluation uses accuracy (ACC), nDCG, and mean average precision (MAP).MAP measures the mean average precision of relevant-document ranks for a query.Source: §A.2 · p. 8

A.3 Retrievers

• The re-ranking experiments use BM25 sparse retrieval and DPR dense retrieval to retrieve documents for LLMs.BM25 scores relevance using term and inverse document frequencies; DPR uses a BERT-initialized biencoder trained with contrastive learning.Source: §A.3 · p. 8

A.4 Zero-shot Re-rankers

• T0 and OPT serve as zero-shot re-rankers, using the template “Passage: {document} {delimiter} {prompt} {delimiter} {query}.”The delimiter is a space for T0 and a newline for OPT; OPT is used instead of GPT-3 due to academic budget.Source: §A.4 · p. 8

A.5 Baselines

• Baselines include Sachan et al. (2022)’s manually selected prompt, P-tuning3 (Liu et al., 2021), and RL-Prompt (Deng et al., 2022).P-tuning3 trains a prompt encoder for 10 epochs to generate 10-length soft prompts; RL-Prompt uses a query-generation likelihood reward and generates 5-token prompts over 12,000 steps.Source: §A.5 · p. 8

B.1 Likelihood PMD(Ds|ρ1:t)

• The base likelihood performs across datasets and LLMs, while the contrastive likelihood performs worse on MS-MARCO.The comparison considers PMD(D_s|ρ_1:t) against the base metric; the supplied passages do not report specific values.Source: §B.1 · p. 9, Table 5 · p. 9

B.2 Impact of Generator

• Prompts from different generators follow human-language patterns but differ in the words they use.Table 4 compares generator prompts and evaluates them on documents retrieved from MS-MARCO by BM25.Source: §B.2 · p. 9, Table 4 · p. 9

• Co-Prompt’s generated prompts resemble human language more than RL-Prompt’s, often include “question,” and contrast with other methods’ dense embeddings or ungrammatical gibberish.Source: §B.3 · p. 9
• Co-Prompt suggests prompts can function as a natural user interface for understanding a black-box model.Source: §B.3 · p. 9
• Co-Prompt ranked first or second on every metric across experiments, while manual prompts optimized for NQ underperformed on MSMARCO and RLPrompt and P-Tuning never led all experiments.Source: §B.3 · p. 9, Table 6 · p. 10