Cascade Reward Sampling for Efficient Decoding-Time Alignment

## Abstract

Abstract Aligning large language models (LLMs) with human preferences is critical for their deployment. Recently, decoding-time alignment has emerged as an effective plug-and-play technique that requires no fine-tuning of model parameters. However, generating text that achieves both high reward and high likelihood remains a significant challenge. Existing methods often fail to generate high-reward text or incur substantial computational costs. In this paper, we propose CAscade RewarD Sampling (CARDS) to address both issues, guaranteeing the generation of high-reward and high-likelihood text with significantly low costs. Based on our analysis of reward models (RMs) on incomplete text and our observation that high-reward prefixes induce high-reward complete text, we use rejection sampling to iteratively generate small semantic segments to form such prefixes. The segment length is dynamically determined by the predictive uncertainty of LLMs. This strategy guarantees desirable prefixes for subsequent generations and significantly reduces wasteful token re-generations and the number of reward model scoring. Our experiments demonstrate substantial gains in both generation efficiency and alignment ratings compared to the baselines, achieving five times faster text generation and 99% win-ties in GPT-4/Claude-3 helpfulness evaluation. The code is publicly available at https://github.com/lblaoke/CARDS .

## 1 Introduction

Large language models (LLMs) have achieved remarkable performance across a wide variety of tasks (Wei et al., ; Bubeck et al., ; Touvron et al., ; Kaddour et al., ). Despite their impressive capabilities, there are growing concerns regarding their safety and reliability (Bai et al., ; Deshpande et al., ; Weidinger et al., ; Gehman et al., ). The field of LLM alignment aims to address these issues by ensuring that LLMs adhere to human preferences and ethical standards. However, one critical challenge is that the generated text must satisfy constraints, including helpfulness and ethical considerations, while simultaneously maintaining fluency.

Various alignment strategies have been developed, such as reinforcement learning with human feedback (RLHF) (Christiano et al., ; Bai et al., ; Ouyang et al., ) and supervised fine-tuning methods (Liu et al., ; Rafailov et al., ; Ethayarajh et al., ). Recently, decoding-time alignment, which only modifies the decoding procedure to generate aligned text, has gained increasing attention due to its simplicity and flexibility (Deng and Raffel, ; Khanov et al., ). This approach does not require fine-tuning of LLM parameters, allowing for the plug-and-play adaptation for any unaligned LLM. Decoding-time alignment naturally supports frequently changing LLMs and reward models (RMs), potentially enabling some complicated tasks like multi-objective alignment (Vamplew et al., ; Zhou et al., ; Yang et al., ). However, while some of the existing decoding-time alignment methods still struggle with the trade-off between alignment and fluency, they all encounter significant efficiency challenges due to auxiliary steps added to their generation process. For example, the reward-guided search paradigm (Deng and Raffel, ; Khanov et al., ) introduces considerable overhead of RM scoring, significantly slowing down the generation.

In this paper, we propose *CAscade RewarD Sampling* (CARDS), a novel decoding-time alignment method that guarantees high-reward and high-likelihood responses while substantially reducing the decoding cost. We formulate alignment as a sampling problem, where the target distribution is defined by the solution to the KL-constrained reward maximization problem (Peters and Schaal, ; Peng et al., ; Rafailov et al., ). To reduce the search space, our method only samples a single semantic segment per step, instead of the full response. The start and end points of the segments are dynamically determined by the predictive uncertainty of LLMs, leveraging the fact that LLMs are less certain about the first token of a semantically complete sequence (Wang et al., ). Each semantic segment is obtained through rejection sampling and is guaranteed to be well-aligned. Furthermore, we rigorously analyze the ability of RMs on incomplete responses, validating the core assumptions of our method. Our experiments on diverse LLM alignment benchmarks demonstrate the superiority of our method in terms of efficiency, alignment rating, and fluency. The main contributions of this paper are summarized as follows:

- •
We approach alignment as a sampling problem and propose Cascade Reward Sampling (CARDS), an efficient decoding-time alignment method (demonstrated in Fig. 1). CARDS achieves high alignment ratings and fluency in generated text while significantly reducing decoding costs compared to baselines.
- •
We provide a rigorous analysis of reward models (RMs) on incomplete text, validating the relationship between intermediate rewards and final rewards. This assumption has been implicitly adopted by many prior investigations; however, we are the first to rigorously verify it.
- •
We demonstrate that RMs can serve as approximations for value functions/prefix scorers on semantically complete segments, eliminating the need for training separate models. Furthermore, we show that semantically complete segments can be easily identified using the predictive uncertainty of LLMs.
- •
Comprehensive experiments demonstrate the superiority of CARDS in terms of efficiency, alignment rating, and fluency against baselines. CARDS can generate well-aligned responses with much lower computational costs.

Figure: Figure 1: Illustration of CARDS sampling steps: Iteratively sampling new candidate segments until the acceptance criterion is met (high prefix-reward, Eq. (8)). The lengths of candidate segments are dynamically determined by the predictive uncertainty of LLMs (Section 4.2.1), which perseveres the semantic completeness of any partial response. The cascade generation strategy significantly reduces the computational cost (Section 5.1) while persevering alignment rating (Section 5.2) and fluency (Section 5.3).
Refer to caption: x1.png

## 2 Related Works

##### Fine-tuning-based alignment.

The goal of fine-tuning-based alignment methods is to minimize the inference cost after deployment (Frantar et al., ). They typically assume that LLMs and human preferences are fixed. Reinforcement learning from human feedback (RLHF) is a direct approach (Christiano et al., ; Lee et al., ; Ouyang et al., ), which uses RMs as a proxy of human preferences and refines the LLMs through the RL framework. Supervised fine-tuning (SFT) approach (Liu et al., ; Rafailov et al., ; Ethayarajh et al., ) addresses the instability of RL training and further improve the efficiency of alignment training.

##### Decoding-time alignment.

Aligning language models during decoding can adaptively fit any preference via different RMs (Huang et al., ), which introduce auxiliary steps into the generation process but no longer need parameter fine-tuning. Reward-guided search (Deng and Raffel, ; Khanov et al., ) uses the reward scores to rank the next token. They are token-level best-of-$N$ searching algorithms (Nakano et al., ; Touvron et al., ), where $N$ candidates are drawn and the one with the highest reward is selected. In-context learning (Lin et al., ; Li et al., ) is also an efficient decoding-time alignment method, which prompts the base LLMs to align themselves. Chakraborty et al. () can transfer the preference from a fine-tuned baseline LLM to a new LLM without further fine-tuning. Mudgal et al. () trains a value-function module to conduct token-level scoring, and Chen et al. () trains a generative token-level RM. They both address the low accuracy of instance-level RMs in reward-guided search, but introduce significant computational overhead in obtaining such token-level scorers. In contrast, our method adopts segment-level reward evaluation, which makes the existing instance-level RMs accurate in scoring the semantically complete prefixes.

##### Rejection sampling for language model alignment.

Rejection sampling enables sampling from intractable target distributions. Khaki et al. (); Liu et al. (); Xiong et al. () use rejection sampling to generate preference data for tuning language models. Eikema et al. () directly samples responses using rejection sampling, but it does not apply to LLMs due to efficiency issue. The cascade sampling strategy in our method addresses the efficiency issue by sampling small semantic segments iteratively to reduce the search space.

##### Segment-based text generation.

Splitting text into segments is a well-studied technique (Pak and Teh, ). In LLM alignment, ToT (Yao et al., ) first introduced similar ideas, in which the starting and ending points of segment candidates are task-related, but they have fixed lengths. In RAIN (Li et al., ), the length of each segment candidate is still a fixed hyper-parameter. In contrast, we adopt a flexible approach where semantic segments can vary in length. We allow the LLM to determine the number of tokens within a semantic segment based on its dynamic and adaptive predictive uncertainty, which can vary for different texts. Similar ideas of dynamic segment length can be found in speculative decoding (Xia et al., ), where the candidate sequence length is determined by LLMs’ self-verification.

## 3 Preliminaries

##### RLHF policy as the target distribution.

Following previous works on KL-constrained reward maximization (Peters and Schaal, ; Korbak et al., ; Go et al., ; Rafailov et al., ) (pursuing high reward with fluency constraint), we can show that the optimal policy can be written as a reward-shifted conditional distribution:

$$ $\pi_{r}(y|x)=\frac{1}{Z(x)}\pi_{\text{LM}}(y|x)\exp\left\{\frac{1}{\beta}r(x,y )\right\},$ (1) $$

where $x$ is the input text, $y$ is the response, $Z(x)=\sum_{y}\pi_{LM}(y|x)\exp\{r(x,y)/\beta\}$ is the partition function, $\pi_{\text{LM}}(y|x)$ is the unaligned conditional distribution for the base LLM, $r(x,y)$ is the reward function, and $\beta$ controls the extent that $\pi_{\text{LM}}(y|x)$ is shifted for higher reward. Precisely characterizing the reward-shifted conditional distribution $\pi_{r}(y|x)$ (despite its intractability in practice) is guaranteed to produce the well-aligned text (Christiano et al., ; Rafailov et al., ).

##### Rejection sampling.

Rejection sampling can effectively characterize an intractable target distribution (e.g., the unnormalized target distribution $f(y)=\pi_{LM}(y|x)\exp\{r(x,y)/\beta\}$) by sampling from a tractable proposal distribution (e.g., $g(y)=\pi_{\text{LM}}(y|x)$) with rejections. Specifically, to sample from the target conditional distribution $\pi_{r}(y|x)$, a proposal is drawn from the unaligned conditional distribution $y\sim\pi_{\text{LM}}(y|x)$, and then we accept the proposal only if

$$ $u<\frac{\exp\left\{\frac{1}{\beta}r(x,y)\right\}}{\max_{y}\exp\left\{\frac{1}{ \beta}r(x,y)\right\}},~{}~{}~{}~{}u\sim\text{Uniform}[0,1].$ (2) $$

Doing so guarantees obtaining samples from the target distribution $\pi_{r}(y|x)$. Furthermore, we know that the expected number of re-sampling before one acceptance is $\max_{y}\exp\left\{r(x,y)/\beta\right\}$ (Hastings, ), which guarantees the efficiency of rejection sampling when the denominator is small. In practical implementation, Eq. (2) can be simplified by approximating the denominator with an arbitrary constant $M$, allowing for a controlled trade-off between accuracy and efficiency. This approach is known as quasi-rejection sampling (Eikema et al., ) and maintains accurate sampling from the target distribution.

Naively, we can apply rejection sampling to decoding-time alignment by sampling from the reward-shifted conditional distribution (Eq. (1)). However, directly sampling from Eq. (1) will induce excessive computational cost, since the search space for the entire token sequence is extremely large.

## 4 Methodology: Cascade Reward Sampling

Generating high-reward responses efficiently is the primary challenge in decoding-time alignment. The efficiency issue involves a trade-off between token re-generations and reward model (RM) scoring. Naive rejection sampling introduced in Section 3 will induce excessive token re-generation due to the large search space; on the other hand, reward-guided search (Deng and Raffel, ; Khanov et al., ) deterministically evaluates the Top-$k$ candidate tokens in every decoding step, leading to too many RM calls. Our method (CARDS) addresses this efficiency challenge by iteratively generating full responses in smaller segments to compress the search space at each step, and applying rejection sampling rather than deterministic search to limit the number of RM calls.

In this section, we first discuss the correctness of our cascade sampling strategy for efficiently generating high-reward text (Section 4.1), followed by a detailed explanation of our method (Section 4.2).

### 4.1 Reward Models on Incomplete Text

Generating high-reward complete responses in smaller segments (in a "cascade" fashion) requires: i) RMs are aligned with human judgments on incomplete responses; ii) conditioned on high-reward prefixes, the complete responses are more likely to get high rewards. The first requirement ensures that the reward scores for prefixes serve as informative alignment metrics. The second requirement ensures that generating smaller segments is an efficient search method for high rewards. We discuss and validate each requirement in the following sections.

#### 4.1.1 Reward Scores of Semantically Complete Prefixes

Reward models are trained to evaluate how responses are aligned with human preference. One of the dominant RM training objectives is pairwise comparison (Stiennon et al., ; Dong et al., ; Xiong et al., ) (also known as the Bradley–Terry models (Bradley and Terry, )):

$$ $\mathcal{L}(x,y^{+},y^{-};\bm{\theta}_{\text{RM}})=\log\sigma\left(r_{\bm{ \theta}_{\text{RM}}}(x,y^{-})-r_{\bm{\theta}_{\text{RM}}}(x,y^{+})\right),$ (3) $$

where $\sigma(\cdot)$ is the sigmoid function, $x$ is the input text, and $y^{+}$/$y^{-}$ is the chosen/rejected response. We hypothesize that reward scores for prefixes (incomplete responses) are more accurate if the prefixes are semantically complete, as RMs are typically trained on complete responses. Semantically complete prefixes are closer to the data that RMs have seen during training. We verify this hypothesis in Fig. 2c, where we compute the averaged reward of all prefixes obtained by segmentation. Fig. 2c shows that the semantically-segmented prefixes (see Section 4.2.1 for details) are more aligned with the full-length responses than static segmentation (not semantically complete), as semantically-segmented prefixes have much lower reward scores on rejected responses.

The ability of RMs to evaluate both complete responses and their prefixes also implies that RMs are similar to the value function in reinforcement learning (Bellman, ; Ouyang et al., ). The value function can evaluate any partial sequence of the full responses in the form of an expected score:

$$ $V(s_{<t})=\mathbb{E}_{s_{\geq t}}V([s_{<t};s_{\geq t}]),$ (4) $$

where $s$ is a full response. Therefore, the above observation also suggests that *RMs can be used as value functions on semantically complete prefixes*. This significantly simplifies the algorithm and reduces the decoding cost, as it eliminates the need to train a separate value function for scoring prefixes required in prior work (Mudgal et al., ).

Prior efforts use RMs at the token level to evaluate arbitrary prefixes (Deng and Raffel, ; Khanov et al., ; Li et al., ), which requires RMs to give accurate scores (i.e., to be accurate value functions) for any prefix. In contrast, we make a weaker assumption, requiring RMs to be accurate only on semantically complete prefixes. This aligns with the actual capability of RMs as shown in Fig. 2c.

#### 4.1.2 Full-response reward is approximately monotonic to prefix reward

Generating responses in smaller segments can reduce the search space. However, it is important to ensure that the full-response reward will be high given a high-reward prefix. Mathematically, we can represent this relationship as follows. We assume that given response prefix $y_{<t}$, the full-response reward $r(x,y)$ follows a distribution (for simplicity, we use a Gaussian distribution), with the mean controlled by the prefix reward $r(x,y_{<t})$:

$$ $r(x,y)\sim\mathcal{N}(r(x,y_{<t})+\epsilon_{t},\sigma_{t}^{2}),$ (5) $$

where $\epsilon_{t}>0$ is a positive mean shift, indicating that full responses tend to have higher rewards than their prefixes. This is based on the observation that longer responses tend to have higher rewards (Appexidx C.3). We visualize this assumption in Fig. 2a, where higher prefix rewards make it more likely to get high full-response rewards.

To verify the above assumption, we test HH-RLHF(^1^11[https://huggingface.co/datasets/Anthropic/hh-rlhf](https://huggingface.co/datasets/Anthropic/hh-rlhf).) in Fig. 2, which shows that prefix’s rewards have the monotonic relationship with full-response rewards. Additionally, we show that the variance term $\sigma_{t}^{2}$ in Eq. (5) is related to the length difference between full response and prefix, and longer prefixes (larger $t$) typically induce smaller $\sigma_{t}^{2}$ (Appendix C.2), which means that the reward of response is highly predictable if only the last few tokens remain unknown. Therefore, as we concatenate semantic segments into a longer and higher-reward prefix, generating a high-reward full response will be easier.

Figure: (a) Visualization of the relation between full-response/prefix rewards
Refer to caption: x2.png

In summary, we validate the cascade generation strategy in CARDS, and show that it is an efficient approach to obtain high-reward responses. At each step of segment generation, the new prefix (formed by adding the new semantic segment to the current prefix) will, on average, have a higher reward than the prefix from the previous step.

### 4.2 Algorithm Details: Uncertainty-based Segmentation and Cascade Sampling

With our understanding of RMs and the cascade generation strategy in Section 4.1, the details about how to segment full responses and how to sample high-reward semantic segments are not completely resolved. The following paragraphs discuss the algorithmic schemes used in CARDS, and compare them to other alternatives.

#### 4.2.1 Segmentation with Predictive Uncertainty

The predictive uncertainty of neural networks, typically the entropy of the softmax distribution (Malinin and Gales, ), measures how certain the model is about its predictions. For autoregressive LLMs, predictive uncertainty directly measures the model’s confidence in predicting the next token. Previous work has indicated that *a well-trained LLM is usually certain about the tokens within a semantically complete segment, and is uncertain about the first token of such a semantic segment* (Wang et al., ). This is because initiating a new segment is more unpredictable than continuing an existing one. We verify this phenomenon in Appendix C.4.

We directly use the values of predictive uncertainty as a segmentation signal. We denote the entropy of the predictive distribution of $t$-token as $\mathcal{H}(v_{t}|x,y_{<t};\bm{\theta}_{\text{LM}})$. If the uncertainty for the next token $v_{t}$ is above a threshold $\tau_{u}$:

$$ $\mathcal{H}(v_{t}|x,y_{<t};\bm{\theta}_{\text{LM}})\geq\tau_{u},$ (6) $$

then the last token $v_{t-1}$ is marked as the ending of one semantic segment. The uncertainty-based segmentation examples are shown in Fig. 6, the choices of uncertainty threshold $\tau_{u}$ are discussed in Appendix B.1, and we also compare different uncertainty estimation algorithms in Appendix C.4 to demonstrate our choice of entropy-based uncertainty. Practically, when one segment exceeds the length limits (e.g., $32$ tokens), token generation is interrupted. This can avoid the excessive LLM calls for a few over-long segments.

Previous works with similar segmentation-based generation typically fixed the length of segments (Yao et al., ; Li et al., ), which ignores the importance of semantic completeness. Others used separate classifier models for segmentation (Kim et al., ; Magimai-Doss et al., ) and did not consider the knowledge from the pre-trained LLMs. Our method leverages the comprehension ability of pre-trained LLMs for segmentation, which preserves the semantic completeness of segments and introduces minimal computational overhead.

#### 4.2.2 Cascade Sampling

Directly sampling from the reward-shifted distribution $\pi_{r}(y|x)$ in Eq. (1) is computationally costly due to the large search space. We instead only sample a small segment at each step to reduce the searching cost, and iteratively merge new segments to the response prefix. Consider a vocabulary set $\mathbb{V}$ and a full-length response $y\in\mathbb{V}^{t_{K}}$. We divide the generation of the entire $y$ into multiple steps:

$$ $\pi_{r}(y|x)=\pi_{r}(y_{<t_{1}}|x)\prod_{k=1}^{K-1}\pi_{r}(y_{t_{k}:t_{k+1}}|y _{<t_{k}},x),$ (7) $$

where $[0,t_{1},t_{2},...,t_{K-1}]$ are the starting positions of semantic segments. Importantly, at each step, the target distribution of the new segment follows a similar form to that of the full response in Eq. (1). This is formally stated in Lemma 1.

###### Lemma 1 .

Assuming the reward models are equivalent to value functions when evaluating semantically complete prefixes (i.e., $r(x,y_{<t})=\beta V(x,y_{<t})$), the target distribution for sampling a new semantic segment is

$$ $\pi_{r}(y_{t_{k}:t_{k+1}}|y_{<t_{k}},x)\propto\pi_{\text{LM}}(y_{t_{k}:t_{k+1} }|y_{<t_{k}},x)\cdot\exp\left\{\frac{1}{\beta}r(x,y_{t_{k+1}})\right\},$ $$

which is an isomorphic form as the target distribution of the full response in Eq. (1).

The derivation of Lemma 1 is shown in Appendix A. This lemma indicates that sampling a semantic segment $y_{t_{k}:t_{k+1}}$ can be done in the same manner as sampling a full response $y$. The cascade sampling strategy introduces only minor modifications to the naive rejection sampling described in Section 3. Specifically, we sample from $\pi_{r}(y_{t_{k}:t_{k+1}}|y_{<t_{k}},x)$ using similar quasi-rejection sampling steps (Eikema et al., ). First, a candidate $y_{t_{k}:t_{k+1}}$ is drawn from the proposal distribution $\pi_{\text{LM}}(y_{t_{k}:t_{k+1}}|y_{<t_{k}},x)$; second, we accept the candidate only if

$$ $u<\exp\left\{\frac{r(x,y_{<t_{k+1}})-\tau_{r}(t_{k+1})}{\beta}\right\},~{}~{}~ {}~{}u\sim\text{Uniform}[0,1].$ (8) $$

Here, the reward threshold term $\tau_{r}(t_{k+1})$ corresponds to the constant in the denominator of Eq. (2), which can take arbitrary values (Eikema et al., ). Practically, we can set the reward threshold to a particular reward score, and our method is guaranteed to generate responses with higher rewards than that score. Based on the observation that longer prefixes tend to have higher rewards on average (Appendix C.3), we adaptively set the reward threshold in an increasing manner:

$$ $\tau_{r}(t)=r_{0}+t\cdot\frac{r^{\star}-r_{0}}{n},$ (9) $$

where $r^{\star}$ is the final reward score we aim to achieve. The initial threshold $r_{0}$ should be slightly higher than the reward score for the input text $x$: $r_{0}=(1-\alpha)\cdot r_{x}+\alpha\cdot r^{\star}$, since the first few semantic segments are more important to the overall alignment rating (Zou et al., ). Additionally, the reward goal $r^{\star}$ controls the expected re-sampling steps. Setting $r^{\star}$ large will lead to more re-sampling steps.

The temperature term $\beta$ in Eq. (8) controls the tolerance for low-reward segments. A smaller $\beta$ makes low-reward segments (i.e., $r(x,y_{<t_{k+1}})<\tau_{r}(t_{k+1})$) less likely to be accepted. Furthermore, setting $\beta\rightarrow 0$ will induce a deterministic acceptance scheme, equivalent to comparing with a fixed threshold.

The details of our method (CARDS) are summarized in Algorithm 1. At each step, a candidate segment $y^{\text{candidate}}$ is sampled, evaluated, and accepted/rejected. The cascade generation strategy proposed in this paper simultaneously enhances both efficiency and alignment rating.

Figure: Algorithm 1 Cascade Reward Sampling (CARDS)

###### Lemma 1 .

## 5 Experiments

To comprehensively demonstrate the superiority of our method, CARDS, we evaluate the efficiency, helpfulness/ harmfulness, and fluency of the generated responses. We also conduct ablation studies to verify the choices of algorithm design and hyperparameters.

### 5.1 Efficiency Evaluation

The computational cost in an LLM-RM architecture mainly arises from the number of LLM/RM calls. RMs are typically fine-tuned from the unaligned LLMs (Deng and Raffel, ; Khanov et al., ), and thus the cost for one forward pass of RMs is the same as LLMs. We show the efficiency evaluation results in Table 1. The number of tokens RMs evaluated at a time is an important metric for understanding the efficiency of decoding-time alignment. If evaluating one token each time (e.g., in RAD/ARGS), the LLM token re-generations can be saved but RM calls will be too expensive. Conversely, if evaluating the entire response at once (e.g. naive rejection sampling), only a few RM calls are needed but the LLM token re-generations will be too expensive. Our method strikes a balance between LLM and RM calls by using the RM to evaluate a partial response at a time.
Our approach results in the lowest number of total calls (LLM + RM calls) and the smallest inference time. Compared to existing decoding-time alignment methods RAD/ARGS, our method reduces the number of total calls by 9x and decreases inference time by 5x.

**Table 1: Efficiency evaluations on HH-RLHF test set. Our method significantly accelerates the inference, with fewer number of model calls (# of forward passes per response) and shorter inference time (per 100 responses) compared with RAD (Deng and Raffel, )/ARGS (Khanov et al., ) and the naive rejection sampling (Naive RS) introduced in Section 3.**
| Model | Method | # LLM Calls | # RM Calls | # Total Calls | Inference Time (min) |
| --- | --- | --- | --- | --- | --- |
| Llama 7B<br>(Touvron et al., ) | RAD/ARGS | 128 | 5120 | 5248 | 238.7 |
| Naive RS | 2553.64 | 19.95 | 2573.59 | 224.3 |  |
| CARDS | 833.42 | 39.49 | 872.91 | 75.8 |  |
| Mistral 7B<br>(Jiang et al., ) | RAD/ARGS | 128 | 5120 | 5248 | 244.3 |
| Naive RS | 1678.45 | 15.38 | 1693.83 | 176.4 |  |
| CARDS | 548.48 | 27.16 | 575.64 | 48.4 |  |

### 5.2 Helpfulness/Harmfulness Evaluation

We conduct the standard alignment rating evaluations. The win-tie and scoring evaluations are shown in Table 2 and Table 3 respectively. The prompts for GPT-4/Claude-3 evaluations are shown in Appendix B.3, where a detailed analysis is required before scoring to make the scores more accurate (Zhao et al., ). We also show examples of generated text in Appendix C.1. For the RM scores, we use the same RM as in inference to see if the generated responses can be aligned with the RM preference. However, if using different RMs to evaluate, the RM scores may not be informative, since different RMs are fine-tuned for slightly different preferences (see Appendix C.5 for examples).

**Table 2: GPT-4/Claude-3 win-tie evaluation on the helpfulness/harmfulness of responses, tested on a 100-sample subset of HH-RLHF test set. Our method wins all compared baselines significantly, demonstrating its superior capability to align responses with human preference.**
| Model | Ours | v.s. | Compared Method | Win-Tie (%) $\uparrow$ |  |  |
| --- | --- | --- | --- | --- | --- | --- |
| GPT-4 | Claude-3 | Average |  |  |  |  |
| Llama 7B<br>(Touvron et al., ) | CARDS |  | Vanilla LLM | 99 | 96 | 97.5 |
| CARDS |  | PPO (Schulman et al., ) | 64 | 60 | 62.0 |  |
| CARDS |  | DPO (Rafailov et al., ) | 79 | 83 | 81.0 |  |
| CARDS |  | ARGS (Khanov et al., ) | 73 | 72 | 71.5 |  |
| CARDS |  | RAIN (Li et al., ) | 96 | 85 | 90.5 |  |
| Mistral 7B<br>(Jiang et al., ) | CARDS |  | Vanilla LLM | 86 | 79 | 82.5 |
| CARDS |  | PPO (Schulman et al., ) | 79 | 72 | 75.5 |  |
| CARDS |  | DPO (Rafailov et al., ) | 83 | 78 | 80.5 |  |
| CARDS |  | ARGS (Khanov et al., ) | 98 | 99 | 98.5 |  |
| CARDS |  | RAIN (Li et al., ) | 90 | 96 | 93.0 |  |

**Table 3: Scoring evaluation on the helpfulness/harmfulness of responses in HH-RLHF test set. Under scores from the reward model, GPT-4, and Claude-3, our method outperforms all compared baselines. (The results for GPT-4/Claude-3 scores are based on a 100-sample subset)**
| Model | Method | RM Score $\uparrow$ | GPT-4 Score $\uparrow$ | Claude-3 Score $\uparrow$ |
| --- | --- | --- | --- | --- |
| Llama 7B<br>(Touvron et al., ) | Vanilla LLM | 5.80 | 5.26 | 6.49 |
| PPO (Schulman et al., ) | 6.10 | 5.76 | 6.81 |  |
| DPO (Rafailov et al., ) | 6.01 | 5.52 | 6.59 |  |
| ARGS (Khanov et al., ) | 7.85 | 5.82 | 6.68 |  |
| RAIN (Li et al., ) | 7.56 | 5.84 | 6.77 |  |
| CARDS (Our method) | 8.30 | 6.28 | 7.14 |  |
| Mistral 7B<br>(Jiang et al., ) | Vanilla LLM | 5.05 | 7.05 | 7.89 |
| PPO (Schulman et al., ) | 6.59 | 7.38 | 7.83 |  |
| DPO (Rafailov et al., ) | 5.23 | 7.25 | 7.59 |  |
| ARGS (Khanov et al., ) | 8.85 | 7.57 | 7.92 |  |
| RAIN (Li et al., ) | 7.64 | 7.30 | 7.91 |  |
| CARDS (Our method) | 12.49 | 7.65 | 8.05 |  |

### 5.3 Fluency Evaluation

Following the settings of Khanov et al. (), we evaluate the diversity and coherence of generated responses as measurements of fluency. The results are shown in Table 4. We observe that fine-tuning-based methods (PPO (Schulman et al., ) and DPO (Rafailov et al., )) typically have suboptimal fluency compared with the unaligned models (Vanilla LLM), and decoding-time alignment methods (ARGS (Khanov et al., ) and RAIN (Li et al., )) usually have comparable fluency. Our method further improves the response fluency via the uncertainty-based segmentation, which preserves the semantic completeness of segments.

**Table 4: Fluency evaluation on HH-RLHF test set, following Khanov et al. (). Our method achieves outstanding fluency scores compared with the baselines, even better than the unaligned models (Vanilla LLM).**
| Model | Methods | Diversity $\uparrow$ | Coherence $\uparrow$ | Average $\uparrow$ |
| --- | --- | --- | --- | --- |
| Llama 7B<br>(Touvron et al., ) | Vanilla LLM | 0.704 | 0.872 | 0.788 |
| PPO (Schulman et al., ) | 0.608 | 0.871 | 0.740 |  |
| DPO (Rafailov et al., ) | 0.499 | 0.873 | 0.686 |  |
| ARGS (Khanov et al., ) | 0.706 | 0.831 | 0.769 |  |
| RAIN (Li et al., ) | 0.706 | 0.872 | 0.789 |  |
| CARDS (Our method) | 0.742 | 0.856 | 0.799 |  |
| Mistral 7B<br>(Jiang et al., ) | Vanilla LLM | 0.834 | 0.853 | 0.844 |
| PPO (Schulman et al., ) | 0.817 | 0.851 | 0.834 |  |
| DPO (Rafailov et al., ) | 0.724 | 0.867 | 0.796 |  |
| ARGS (Khanov et al., ) | 0.719 | 0.875 | 0.797 |  |
| RAIN (Li et al., ) | 0.853 | 0.865 | 0.859 |  |
| CARDS (Our method) | 0.846 | 0.854 | 0.850 |  |

### 5.4 Ablation Studies

We list a few interesting ablation studies below to understand the details of our method.

##### Acceptance criterion in Eq. ( 8 ).

Eq. (8) is a probability-based criterion. Another scheme is setting $\beta\rightarrow 0$ to get a threshold-based criterion: $r(x,y_{<t_{k+1}})\geq\tau_{r}(t_{k+1})$. We compare these two schemes in Table 5. We found that the probability-based criterion sacrifices a small amount of reward score for much more efficient response generation. Therefore, we recommend choosing the probability-based criterion by default.

##### Dynamic or static segmentation?

Previous works did not consider dynamic segmentation for segment-based generation (Yao et al., ; Li et al., ). We have compared these two strategies in Fig. 2c, where dynamic segmentation is better aligned with the full-sentence rewards. Besides, the uncertainty-based segmentation proposed in this paper outperforms the static segmentation (RAIN) in the helpfulness/harmfulness evaluation.

**Table 5: Comparison between threshold-based acceptance and probability-based acceptance, evaluated by LLama 7B (Touvron et al., ) on HH-RLHF test set. Although the reward for probability-based acceptance is lower, it is more efficient due to the reduced number of LLM/RM calls.**
| Criterion | RM Score | # LLM Calls | # RM Calls | # Total Calls | Inference Time (min) |
| --- | --- | --- | --- | --- | --- |
| Threshold | 9.01 | 1089.97 | 47.47 | 1137.44 | 105.9 |
| Probability | 8.71 | 744.14 | 34.48 | 778.62 | 66.1 |

##### Uncertainty metrics and threshold τ u subscript 𝜏 𝑢 \tau_{u} italic_τ start_POSTSUBSCRIPT italic_u end_POSTSUBSCRIPT .

There are uncertainty metrics besides entropy. We compare three widely used predictive uncertainties in Appendix C.4 and demonstrate that entropy-based uncertainty (Malinin and Gales, ) achieves the best results. Additionally, the uncertainty threshold is an important hyperparameter for controlling the number of segments. We provide a detailed analysis of $\tau_{u}$ in Appendix C.6.

##### Shift factor β 𝛽 \beta italic_β and target reward score r ⋆ superscript 𝑟 ⋆ r^{\star} italic_r start_POSTSUPERSCRIPT ⋆ end_POSTSUPERSCRIPT .

These two hyper-parameters control the cascade sampling process. We comprehensively study their effect in Appendix C.7. There exists a relatively large interval for the appropriate value of $\beta$ ($0.5\sim 0.8$), where the averaged reward and the number of LLM/RM calls are optimal. For the value of $r^{\star}$, a higher reward threshold will induce a higher averaged reward, but the number of LLM/RM calls will also increase accordingly. In the experiments, $r^{\star}$ is set to be just higher than the RM score of ARGS (Khanov et al., ), to guarantee outperforming compared baselines in terms of rewards.

## 6 Conclusion and Limitations

In this paper, we proposed the *CAscade RewarD Sampling* (CARDS) for efficient decoding-time alignment. We first rigorously analyze the properties of reward models (RMs) and show the relationship between full-response reward and prefix reward. Then we leverage the rejection sampling to iteratively generate small semantic segments of high reward, where the predictive uncertainty of LLMs dynamically determines the segment length. Our method significantly reduces the computational cost of decoding-time alignment methods. In the experiments, we evaluate the efficiency, alignment rating, and fluency of the generated responses. Our method achieves promising results under all evaluations.

Despite the superiority of our method, some technical limitations still exist and prevent our method from being more efficient. For example, the dynamic segmentation is hard to parallelize to batched inference, since the prefix length of each response is independently changing and never aligned. In future works, we may incorporate iteration-level batching (Appendix B.5) to address this limitation.

## Ethics Statement

This paper focuses on efficient decoding-time alignment, which enables smaller entities to align their LLMs without the costly fine-tuning process. This paper contributes to developing more reliable, beneficial, and resource-efficient AI systems. However, we acknowledge potential ethical concerns, including biases in training data, the risk of misuse for generating harmful content, and the environmental impact of computational resources.

## Appendix A Proof of Lemma 1

###### Proof.

The target distribution for sampling a new segment $y_{t_{k}:t_{k+1}}$ is:

$$ $\pi_{r}(y_{t_{k}:t_{k+1}}|y_{<t_{k}},x)=\frac{\pi_{r}(y_{<t_{k+1}}|x)}{\pi_{r} (y_{<t_{k}}|x)}\overset{\text{(a)}}{=}\frac{\sum_{y_{t_{k+1}:n}}\pi_{r}(y|x)}{ \sum_{y_{t_{k}:n}}\pi_{r}(y|x)}=\frac{\sum_{y_{t_{k+1}:n}}\pi_{\text{LM}}(y|x) \exp\left\{\frac{1}{\beta}r(x,y)\right\}}{\sum_{y_{t_{k}:n}}\pi_{\text{LM}}(y| x)\exp\left\{\frac{1}{\beta}r(x,y)\right\}}.$ (10) $$

Here, (a) is the marginalization over the token sequences $y_{t_{k+1}:n}$ and $y_{t_{k}:n}$ respectively. Then, taking Eq. 1 into account, the above expression can be extended as:

$$ $\displaystyle\pi_{r}(y_{t_{k}:t_{k+1}}|y_{<t_{k}},x)$ $\displaystyle=\frac{\pi_{\text{LM}}(y_{<t_{k+1}}|x)\sum_{y_{t_{k+1}:n}}\pi_{ \text{LM}}(y_{t_{k+1}:n}|y_{<t_{k+1}},x)\exp\left\{\frac{1}{\beta}r(x,y)\right \}}{\pi_{\text{LM}}(y_{<t_{k}}|x)\sum_{y_{t_{k}:n}}\pi_{\text{LM}}(y_{t_{k}:n} |y_{<t_{k}},x)\exp\left\{\frac{1}{\beta}r(x,y)\right\}}$ (11) $\displaystyle\overset{\text{(b)}}{\propto}\frac{\pi_{\text{LM}}(y_{<t_{k+1}}|x )\exp\left\{V(x,y_{<t_{k+1}})\right\}}{\pi_{\text{LM}}(y_{<t_{k}}|x)\exp\left \{V(x,y_{<t_{k}})\right\}}$ $\displaystyle\overset{\text{(c)}}{=}\pi_{\text{LM}}(y_{t_{k}:t_{k+1}}|y_{<t_{k }},x)\cdot\exp\left\{\frac{1}{\beta}r(x,y_{<t_{k+1}})-\frac{1}{\beta}r(x,y_{<t _{k}})\right\}$ $\displaystyle\overset{\text{(d)}}{\propto}\pi_{\text{LM}}(y_{t_{k}:t_{k+1}}|y_ {<t_{k}},x)\cdot\exp\left\{\frac{1}{\beta}r(x,y_{<t_{k+1}})\right\}.$ $$

Here, (b) is due to the property of value functions (Eq. 33, Appendix B.1 of Zhao et al. []), (c) is from the equivalence assumption between value functions and reward models (i.e., $r(x,y_{<t})=\beta V(x,y_{<t})$), and (d) is because the prefix $y_{<t_{k}}$ is fixed when sampling the next semantic segment $y_{t_{k}:t_{k+1}}$.
∎

###### Proof.

## Appendix B Implementation Details

### B.1 Hyper-parameters

The hyper-parameters used in our method are listed in Table 6. The particular values are determined by grid search.

**Table 6: Hyper-parameter configuration.**
| Model | $\tau_{u}$ | $r^{\star}$ | $\alpha$ | $\beta$ | Top-$K$ | max-new-token |
| --- | --- | --- | --- | --- | --- | --- |
| Llama 7B | 3.0 | 8.5 | 0.5 | 0.7 | 40 | 128 |
| Mistral 7B | 2.0 | 9.0 | 0.5 | 0.7 | 40 | 128 |

### B.2 Computing Resources for Experiments

All of our experiments are conducted in a Linux server with 8 NVIDIA RTX A6000(^2^22[https://www.nvidia.com/en-us/design-visualization/rtx-a6000/](https://www.nvidia.com/en-us/design-visualization/rtx-a6000/).). The GPT-4(^3^33[https://openai.com/index/openai-api/](https://openai.com/index/openai-api/).) and Claude-3(^4^44[https://www.anthropic.com/api](https://www.anthropic.com/api).) evaluation experiments are conducted via their API.

### B.3 GPT-4 and Claude-3 Evalution Details

We use GPT-4 and Claude-3 to evaluate the helpfulness/harmlessness of the generated responses. We extend and rephrase the prompt based on the GPT-4 evaluation in Zhao et al. []. The prompt first determines the AI assistant’s specific role and then asks for the analysis and helpfulness/harmlessness score of a paired question and answer. The full prompt for GPT-4/Claude-3 is as follows:

For the win-tie evaluation prompt, we follow Khanov et al. []. The complete prompt, comprising both the system and user prompts, is as follows:

### B.4 Prompt Length Alignment for Efficient Batched Decoding

In batched inference, shorter prompts will be padded to be aligned with the longest prompt. The padding length is a source of extra computational cost. We address this problem by choosing prompts of similar lengths into one batch. Specifically, we sort the test set and form batches iteratively. This way the prompts within one batch are always of similar length.

### B.5 Discussion on Iteration-level Batching

In batched inference, the padding cost problem can also be addressed by the iteration-level batching technique [Yu et al., ]. Specifically, the batch size is dynamic, and shorter prompts will be processed later than longer prompts, but they will finish the auto-regressive generation simultaneously. This technique can significantly reduce the padding cost, but it introduces instability to the GPU memory usage.

## Appendix C Additional Results and Examples

### C.1 Examples of Generated Text

We provide examples of generated text, which are generated by different methods on Llama 7B [Touvron et al., ]. Our method achieved the highest reward score on this question, clearly demonstrating that our response is both accurate and fluent.

### C.2 Reward Relationship between Full Responses and Their Prefixes

Extending the experiments in Fig. 2b, we show the diagrams for $1/4$-length and $3/4$-length prefixes in Fig. 3. As the prefix length gets closer to the full response, the monotonic relation between their rewards becomes clearer. This can reflect the variance term $\sigma_{t}^{2}$ in Eq. (5). Longer prefixes typically induce smaller $\sigma_{t}^{2}$.

Figure: (a) $1/4$-length prefixes
Refer to caption: x5.png

### C.3 Relationship between Reward and Prefix/Response Length

The lengths of prefixes or responses have a clear linear relationship with their rewards. In Fig. 4, we show that longer prefixes/responses have higher rewards on average. Therefore, the positive mean shift $\epsilon_{t}$ is introduced in Eq. (5) to reflect such a linear relationship.

Figure: (a) w/ token-wise segmented prefixes
Refer to caption: x8.png

### C.4 Segmentation Examples with Different Predictive Uncertainties

We show three widely used uncertainty algorithms on an example sentence in Fig. 5, Fig. 6 and Fig. 7. The MCP [Hendrycks and Gimpel, ] and entropy-based uncertainty [Malinin and Gales, ] are better for segmenting this sentence, since they only induce a few high-uncertainty points.

Figure: Figure 5: Uncertainty segmentation example based on the maximum probability [Hendrycks and Gimpel, ]. The first token of each semantic segment is marked with red.
Refer to caption: x10.png

Figure: Figure 6: Uncertainty segmentation example based on the entropy [Malinin and Gales, ]. The first token of each semantic segment is marked with red.
Refer to caption: x11.png

Figure: Figure 7: Uncertainty segmentation example based on the evidential uncertainty [Sensoy et al., ]. The first token of each semantic segment is marked with red.
Refer to caption: x12.png

### C.5 Cross Reward Model Evaluation

We use the Llama RM(^5^55[https://huggingface.co/argsearch/llama-7b-rm-float32](https://huggingface.co/argsearch/llama-7b-rm-float32).) on Huggingface as our Llama-7b reward model, which is trained from the base model(^6^66[https://huggingface.co/argsearch/llama-7b-sft-float32](https://huggingface.co/argsearch/llama-7b-sft-float32).). For the Mistral reward model, we utilize Mistral RM(^7^77[https://huggingface.co/weqweasdas/RM-Mistral-7B](https://huggingface.co/weqweasdas/RM-Mistral-7B).), which is trained from the base model(^8^88[https://huggingface.co/mistralai/Mistral-7B-Instruct-v0.2](https://huggingface.co/mistralai/Mistral-7B-Instruct-v0.2).).

In the main section, we employ the Llama RM for the Llama-7b model and the Mistral RM for the Mistral-7b model. Here, we investigate the performance of our methods by the cross-RM evaluation, using the Mistral RM for Llama-7b and the Llama RM for Mistral-7b. In Table 7, we show the average reward scores rated by different reward models.

**Table 7: Average reward scores for various methods using cross reward models for Llama 7B [Touvron et al., ] and Mistral 7B [Jiang et al., ]. The Llama 7B model is evaluated with the Mistral RM, and the Mistral 7B model is evaluated with the Llama RM. Those two RMs represent slightly different preferences and our method still achieves outstanding scores.**
| Model | Reward Model | Methods | RM Score |
| --- | --- | --- | --- |
|  |  | Vanilla | 1.58 |
|  |  | PPO [Schulman et al., ] | 3.67 |
|  |  | DPO [Rafailov et al., ] | 1.82 |
|  |  | ARGS [Khanov et al., ] | 2.94 |
|  |  | RAIN [Li et al., ] | 4.50 |
| Llama 7B<br>[Touvron et al., ] | Mistral RM | CARDS | 3.89 |
|  |  | Vanilla | 6.05 |
|  |  | PPO [Schulman et al., ] | 6.00 |
|  |  | DPO [Rafailov et al., ] | 6.05 |
|  |  | ARGS [Khanov et al., ] | 2.05 |
|  |  | RAIN [Li et al., ] | 5.27 |
| Mistral 7B<br>[Jiang et al., ] | Llama RM | CARDS | 6.14 |

### C.6 Full Ablation Results for Segmentation and Uncertainty Thresholds

We show the ablation studies for uncertainty threshold in Fig. 8. As the uncertainty threshold becomes larger, short segments will be combined into long segments, and choosing $\tau_{u}\approx 3$ is appropriate. Additionally, we show the pairwise relationship between full-response length, number of segments, and the average segment length in Fig. 9.

Figure: (a)
Refer to caption: x13.png

Figure: (a)
Refer to caption: x15.png

### C.7 Full Ablation Results of β 𝛽 \beta italic_β and r ⋆ superscript 𝑟 ⋆ r^{\star} italic_r start_POSTSUPERSCRIPT ⋆ end_POSTSUPERSCRIPT

Fig. 10 provides a comprehensive analysis of the relationship between the parameter $\beta$ and three key performance metrics: Average Reward, Average LLM Calls, and Average RM Calls, for different $r^{\star}$ values (8.0, 8.5, and 9.0). Subfigure (a) shows that the Average Reward increases with $\beta$ up to a peak around $\beta$=0.7 to $\beta$=1.0 before declining. And 3 different $r^{\star}$ perform almost same. Subfigure (b) illustrates a sharp decline in Average LLM Calls as $\beta$ increases from 0.1 to 0.5, after which the calls stabilize, highlighting more efficient performance at higher $\beta$ values, especially for lower $r^{\star}$ values. Subfigure (c) presents a U-shaped pattern for Average RM Calls, which decrease slightly with increasing $\beta$ up to approximately 1.0, then increase again, suggesting that mid-range $\beta$ values minimize RM calls. And lower $r^{\star}$ values will have less RM calls.
More detailed values can be found in Table LABEL:tab:beta_r.

Figure: (a) RM score
Refer to caption: x18.png

**Table 8: Detailed ablation results showing the relationship between the parameter $\beta$ and three key performance metrics (Average Reward, Average LLM Calls, and Average RM Calls) for different $r^{\star}$ values (8.0, 8.5, and 9.0). The table presents the values for each combination of $\beta$ and $r^{\star}$, highlighting the trends observed in Fig. 10.**
| $r^{\star}$ | beta | Avg Reward$\uparrow$ | Avg LLM Calls$\downarrow$ | Avg RM Calls$\downarrow$ | Total Calls$\downarrow$ | Total time$\downarrow$ |
| --- | --- | --- | --- | --- | --- | --- |
|  | 0.1 | 7.26 | 1651.75 | 59.77 | 1711.52 | 2:33:33 |
|  | 0.2 | 8.03 | 1222.11 | 42.53 | 1264.64 | 1:54:10 |
|  | 0.3 | 8.13 | 1046.05 | 40.35 | 1086.40 | 1:37:54 |
|  | 0.4 | 8.56 | 857.59 | 32.68 | 890.27 | 1:16:21 |
|  | 0.5 | 8.48 | 658.47 | 30.05 | 688.52 | 0:57:48 |
|  | 0.6 | 8.50 | 659.99 | 29.43 | 689.42 | 1:15:36 |
|  | 0.7 | 8.08 | 612.36 | 27.99 | 640.35 | 0:55:22 |
|  | 0.8 | 7.97 | 636.08 | 31.05 | 667.13 | 0:56:34 |
|  | 0.9 | 7.68 | 653.21 | 35.53 | 688.74 | 1:00:55 |
|  | 1.0 | 7.31 | 634.69 | 35.20 | 669.89 | 0:57:57 |
|  | 1.2 | 6.67 | 696.18 | 43.13 | 739.31 | 1:02:10 |
|  | 1.4 | 5.52 | 915.18 | 65.41 | 980.59 | 1:23:53 |
|  | 1.6 | 5.01 | 891.60 | 69.48 | 961.08 | 1:37:16 |
|  | 1.8 | 3.99 | 1018.44 | 92.93 | 1111.37 | 1:32:40 |
| $r^{\star}$ = 8.0 | 2.0 | 3.57 | 970.46 | 103.35 | 1073.81 | 1:30:21 |
|  | 0.1 | 7.85 | 1805.06 | 67.38 | 1872.44 | 2:40:50 |
|  | 0.2 | 8.17 | 1382.98 | 54.26 | 1437.24 | 2:03:56 |
|  | 0.3 | 8.23 | 1221.84 | 45.07 | 1266.91 | 1:51:03 |
|  | 0.4 | 8.32 | 1032.73 | 39.48 | 1072.21 | 1:34:09 |
|  | 0.5 | 8.41 | 942.27 | 40.91 | 983.18 | 1:26:26 |
|  | 0.6 | 8.56 | 867.98 | 40.50 | 908.48 | 1:20:38 |
|  | 0.7 | 8.71 | 744.14 | 34.38 | 778.52 | 1:06:08 |
|  | 0.8 | 8.31 | 745.63 | 35.17 | 780.80 | 1:05:58 |
|  | 0.9 | 7.72 | 803.67 | 38.76 | 842.43 | 1:13:01 |
|  | 1.0 | 7.86 | 720.40 | 37.49 | 757.89 | 1:07:33 |
|  | 1.2 | 6.90 | 905.79 | 55.42 | 961.21 | 1:21:50 |
|  | 1.4 | 5.60 | 1094.47 | 77.13 | 1171.60 | 1:38:40 |
|  | 1.6 | 4.72 | 1073.69 | 82.04 | 1155.73 | 1:43:47 |
|  | 1.8 | 3.87 | 1145.31 | 103.54 | 1248.85 | 1:44:52 |
| $r^{\star}$ = 8.5 | 2.0 | 3.50 | 1082.87 | 112.25 | 1195.12 | 1:38:34 |
|  | 0.1 | 7.20 | 2172.07 | 74.50 | 2246.57 | 3:17:12 |
|  | 0.2 | 8.06 | 1596.79 | 61.53 | 1658.32 | 2:24:59 |
|  | 0.3 | 8.39 | 1377.53 | 53.54 | 1431.07 | 2:27:32 |
|  | 0.4 | 8.98 | 1116.38 | 45.10 | 1161.48 | 1:40:14 |
|  | 0.5 | 8.93 | 1079.29 | 44.07 | 1123.36 | 1:36:12 |
|  | 0.6 | 8.68 | 919.39 | 41.48 | 960.87 | 1:21:16 |
|  | 0.7 | 8.48 | 916.82 | 42.71 | 959.53 | 1:22:49 |
|  | 0.8 | 8.17 | 944.11 | 43.02 | 987.13 | 1:23:35 |
|  | 0.9 | 8.23 | 793.55 | 38.61 | 832.16 | 1:10:16 |
|  | 1.0 | 7.74 | 877.90 | 44.04 | 921.94 | 1:19:14 |
|  | 1.2 | 6.80 | 1097.06 | 63.62 | 1160.68 | 1:36:23 |
|  | 1.4 | 5.73 | 1238.10 | 78.23 | 1316.33 | 2:23:01 |
|  | 1.6 | 4.82 | 1252.65 | 96.87 | 1349.52 | 1:52:29 |
|  | 1.8 | 3.88 | 1211.73 | 109.03 | 1320.76 | 1:53:05 |
| $r^{\star}$ = 9.0 | 2.0 | 3.50 | 1245.70 | 129.66 | 1375.36 | 1:55:59 |

## Peer Reviews

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: Suggestions:
- One could include more baselines such as In-Context learning for alignment (Rethinking alignment via in-context learning), Best of N based on full sequence rewards
soundness: 3
strengths: - The shift to segment-level sampling, along with the use of uncertainty as a termination signal for segments, presents a unique and novel approach.
- The results show significant gains on performance and speed, renders this approach very practical.
summary: - The paper focuses on enhancing decoding-time alignment methods, particularly addressing the high computational costs associated with existing approaches.
- It introduces **Cascade Reward Sampling (CARDS)**, a novel method that samples segments, leveraging the insight that reward models (RMs) favor high-reward prefixes. CARDS incrementally generates high-reward semantic segments, aiming to achieve optimal reward in the final output by prioritizing these segments.
- Experimental results demonstrate significant improvements in both performance and speed over baseline methods.
weaknesses: - The reliance on target score poses a notable limitation. How can one determine this? Different RMs provide values in different scales. 
    - Exploring alternative sampling strategies, like sampling multiple segments per step and selecting the highest-scoring option before proceeding greedily, could be beneficial (atleast as a baseline comparison)
- The experiments are conducted solely on the HH-RLHF dataset, limiting the generalizability of the findings. Especially, HH-RLHF is a very simple dataset as many inference time methods are already better than trained methods such as PPO and DPO. Testing on few more datasets would solidify the findings.

---

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: The same as above
soundness: 4
strengths: 1.	This paper conducts a rigorous analysis of reward models and demonstrates the RMs can serve as value functions on semantically complete segments.
2.	The generation method is segment-based and the length of segment is dynamic.
3.	The experiment is adequate and reasonable and the paper is well written.
summary: This paper propose a novel segment-based sampling method for efficient decoding-time alignment, leveraging rejection sampling to iteratively generate small semantic segments of high reward.
weaknesses: 1.	The experiments are conducted on 7B models. The method could be verified on more larger models.
2.	The parallelization scheme of dynamic segmentation whether has a slow inference time when the batch size is larger.

---

confidence: 4
contribution: 2
initial_rating: 3
presentation: 2
questions: 1. What do you mean by "However, while some of the existing decoding-time alignment methods still struggle with the trade-off between alignment and fluency, they all encounter significant efficiency challenges due to auxiliary steps added to their decoding process."?
2. In line 239, "Therefore, the above observation also suggests that RMs can be used as value functions on semantically complete preffxes." Can you explain why?
3. In Lemma 1, I still cannot understand why can we assume "Assuming the reward models are equivalent to value functions when evaluating semantically complete prefixes". Is there any previous literature proof of this?
4. What if the prefixes is not semantically complete?
soundness: 2
strengths: 1. The article raises an excellent question on how to enhance the efficiency of alignment during the reasoning phase.
2. Many designs in the article's methodology are interesting, such as "Our method leverages the comprehension ability of pre-trained LLMs for segmentation."
3. The experimental results of CARDS are outstanding.
summary: The paper introduces a decoding-time alignment method for large language models (LLMs) that ensures high-reward and high-likelihood text generation with reduced computational costs. CARDS uses rejection sampling to create text by dynamically determining segment lengths based on the predictive uncertainty of LLMs, significantly enhancing efficiency. This method also maintains fluency and aligns closely with human preferences, demonstrating substantial improvements over existing methods in both speed and alignment accuracy during text generation.
weaknesses: 1. The presentation of the article is somewhat difficult to follow. For example, Figure 1, which explicates the contributions mentioned in the introduction, requires the integration of content from many sections later in the text to be understood. Moreover, Section 4.1.1 repeatedly refers to Figure 2c without clearly explaining how Figure 2c is produced and its detailed meaning. Section 4.2.1, however, does not mention Figure 2c at all.
2. Many intermediate conclusions in the methodology lack theoretical support and are merely based on simple experiments and conjectures. For instance, "a full-response reward will be high given a high-reward prefix" and "This is because initiating a new segment is more unpredictable than continuing an existing one."
3. I think previous works [1] also assume Lemma 1 is valid; however, this paper still does not provide convincing proof, thus, the contribution in this part seems incremental.
4. CARDS appears to be a method for enhancing the efficiency of decoding-time alignment, but I have no idea why CARDS could lead to significant performance improvements in the experiment.

[1] Args: Alignment as reward-guided search.

---

confidence: 5
contribution: 2
initial_rating: 3
presentation: 3
questions: - The equation (4) is not well defined. The expectation is taken based on which distribution?
- Which reward model did you use for Figure 2b,3,4? Did you only examine one reward model to support claims shown in these figures?
- Can this approach be applied to some smaller and weaker reward models, like GPT2 models [1][2]? This would be important for some groups with restricted computation resources.
- Can this approach be possibly applied to multi-objective alignment, like what many reward-guided decoding-time algorithms [3][4] can do? (Anyway, they are concurrent works, so there is no need to compete with them.)

[1] https://huggingface.co/Tristan/gpt2_reward_summarization

[2] https://huggingface.co/Ray2333/gpt2-large-helpful-reward_model

[3] PAD: Personalized Alignment at Decoding-Time, https://arxiv.org/abs/2410.04070

[4] GenARM: Reward Guided Generation with Autoregressive Reward Model for Test-time Alignment, https://arxiv.org/abs/2410.08193
soundness: 1
strengths: ## Originiality
- The segmentation trick with uncertainty is novel and interesting, and it deserves to be shared with a broad audience.
- The assumption on reward distribution is original, though may not be true.

## Clarity
- This paper is well-written and well-organized.
- Most figures and tables are friendly to the readers.
- The intuitions are clearly expressed.

## Significance
- The weak assumption on the expressibility of reward model is more reasonable than prior works.
- This work has improved the performance of reward-guided decoding-time alignment, compared with baselines.
summary: This paper focuses on reward-guided decoding-time alignment. They propose Cascade Reward Sampling (CARDS), which is mainly based on two claims:

- They claim to have analyzed the properties of reward models (RMs) on incomplete text, and hypothesize that RMs can serve as approximations for value functions.
- They show that values of predictive uncertainty can be a segmentation signal, and thus can divide the generation of an entire response into multiple steps (segments). 

Combining two claims, they establish the target distribution for sampling a new semantic segment. Therefore, they finally sample one segment each step, get the reward, and use rejection sampling to align the distribution to what they have established.

Experiments are conducted on HH-RLHF dataset. They have compared the performance of CARDS with RAD/ARGS and naive rejection sampling, showing general advantages.
weaknesses: ## Major
- The reviewer cannot buy the idea that reward model is a value function. Only the last signal of reward model is trained, and the intermediate prediction is more like black box. There is a well-known paper [5] showing that DPO model acts like Q-function, but the result only holds for credit assignment setting.
- There is a new paper showing that "partial reward" may not be correlated to "full reward". Please see Appendix C.3 of [6].
- There is no non-trivial mathematical proof. So it would be better to remove the claim that "We first **rigorously** analyze the properties of reward models". The authors have conducted some experimets to support their intuitions or assumptions, that are great, but still far from being called "rigorous", since there is no theoretical guarantee.
- Lack of baselines. CARDS is only compared with two baselines, RAD/ARDS (these two are the same), and naive rejection sampling. Many reward-guided decoding-time alignment approaches have emerged in these two years. For example, controlled-decoding [1] can be a baseline, which samples next token from $\pi(y)\exp(r(y)/\beta)$. ([1] is different from RAD/ARDS, since it doesn't need a top-k sampling at first.) And the reviewer guesses that [1] should be faster than CARDS.
## Minor
- Equation 11(b) only holds for soft-RL, which should be made clear to the readers.
- Lack of datasets. The experimental results on HH-RLHF are acceptable but limitted. More datasets are worth exploring. For example, Ultrafeeback[2], HelpSteer[3], Beavertails[4] are worth trying.

*The empirical approach is generally fine to the reviewer, but unfortunately, the claims have many problems. The reviewer is willing to raise the rating if the issues can be solved.*

[1] Controlled Decoding from Language Models, https://arxiv.org/abs/2310.17022

[2] UltraFeedback: Boosting Language Models with Scaled AI Feedback, https://arxiv.org/abs/2310.01377

[3] HelpSteer: Multi-attribute Helpfulness Dataset for SteerLM, https://arxiv.org/abs/2311.09528

[4] BeaverTails: Towards Improved Safety Alignment of LLM via a Human-Preference Dataset, https://arxiv.org/abs/2307.04657

[5] From r to Q∗: Your Language Model is Secretly a Q-Function, https://arxiv.org/abs/2404.12358

[6] TreeBoN: Enhancing Inference-Time Alignment with Speculative Tree-Search and Best-of-N Sampling, https://arxiv.org/abs/2410.16033

Meta-review: The paper proposes a new technique for reward guided text generation that is computationally cheaper than previous methods and achieves higher scores.  The strength of this paper is its empirical evaluation that demonstrates clear improvements over the baselines.  The weakness of this paper is the absence of theory, a problematic assumption and questionable analysis.  I recommend rejection since the analysis has important inconsistencies.

Decision: Reject