GReaTer: Gradients Over Reasoning Makes Smaller Language Models Strong Prompt Optimizers

Weakness 5

Recent literature [3,4,5] related to applying the gradient concept in prompt optimization should be at least discussed.

Thank you so much for mentioning those works in the literature!

As we discussed, Pryzant et al. [4] introduced the use of mini-batches of data to create natural language feedback, referred to as “natural language gradients.” These gradients critique the current prompt, mimicking the role of numerical gradients in optimization. This method, named APO, serves as one of our primary baselines across all experiments.

Additionally, [5] highlighted that local optima are significantly more common than global optima in prompt optimization. Based on this observation, the authors proposed ZOPO, a method that incorporates a Gaussian process inspired by the Neural Tangent Kernel into zeroth-order optimization. This approach systematically explores local optima through iterative evaluations.

Finally, Wen et al. [3] introduced the PEZ algorithm, a gradient-based discrete optimization approach that utilizes gradients without considering reasoning paths. As noted in Weakness 3, we compared our approach, GreaTer, against PEZ and observed a significant performance improvement from our method.

We have incorporated these discussions into the related works section of the revised manuscript.

---

Question 1

What if there is no intersection in Eq. 4? And how to guarantee semantic coherence among different token positions?

We appreciate you raising these points! In practice, we keep increasing $k$ until $\text{candidates}_i$ contains a minimum number of intersections. Additionally, as outlined in Eq. 3, the top-$k$ candidates are generated by the LLM while conditioning on the original question and preceding prompt tokens. This ensures semantic coherence among the tokens, as it is inherently guided by the LLM's understanding of the context.

---

Question 2

Can you explain why the performance gain from gradient over reasoning is much smaller on Gemma model compared with LLaMA model?

We agree that the performance gain from gradient over reasoning is much larger in LLaMA-3 compared to Gemma-2 models. Generally, Gemma-2-9B is a stronger model compared to LLaMA-3-8B. Therefore, we hypothesize that it already generates strong prompt candidates in the prompt token candidate proposal stage (Section 4.2). Consequently, the candidate selection stage where gradients are leveraged has less burden to find the best candidate. Nevertheless, gradient over reasoning still chooses a better token candidate, leading to improved performance.

---

Question 3

How about the performance on 1.5B or 3B models? A 9B model is actually not very small in practice.

Thank you so much for raising this issue as well. While 8B and 9B models are popular, we agree that smaller models like LLaMA-3.2-1B-Instruct would be a great candidate for a very small language model. In the revised manuscript, Table 8 shows the performance comparison of GreaTer to that of other prompts optimized by other baselines. The performance numbers clearly show that, on average, GreaTer substantially outperforms other approaches in different tasks. For your reference, the performance comparison in the LLaMA-3.2-1B target model is given below:

---

References

[1] Kojima, Takeshi, et al. "Large language models are zero-shot reasoners." Advances in Neural Information Processing Systems 35 (2022): 22199-22213.
[2] Shin, Taylor, et al. "Autoprompt: Eliciting knowledge from language models with automatically generated prompts." arXiv preprint arXiv:2010.15980 (2020).
[3] Wen, Yuxin, et al. "Hard prompts made easy: Gradient-based discrete optimization for prompt tuning and discovery." Advances in Neural Information Processing Systems 36 (2024).
[4] Pryzant, Reid, et al. "Automatic prompt optimization with" gradient descent" and beam search." arXiv preprint arXiv:2305.03495 (2023). [5] Hu, Wenyang, et al. "Localized zeroth-order prompt optimization." arXiv preprint arXiv:2403.02993 (2024).

Weakness 3

How to justify “simply considering $f_{LLM}(y \mid x \odot p)$ would give us the wrong objective to optimize, which in turn will give incorrect gradient information” in lines 237-238? The idea of taking gradients over reasoning paths is not well-explained. Intuitively, I expect the distribution of $f_{LLM}(y \mid x \odot p)$ to be more skewed than $f_{LLM}(y \mid x \odot p \odot r)$, as we can view $r$ as more computation to search for the right answer $y$.

Thank you for seeking clarification regarding the significance of gradient over reasoning. As outlined in the manuscript, a core strength of GreaTer lies in its "Gradient Over Reasoning," as the reasoning chain effectively captures the task loss. To illustrate its importance more clearly, consider the following:

• Input, $x$: "The cafeteria had 23 apples. If they used 20 to make lunch and bought 6 more, how many apples do they have?"
• Prompt, $p$: "Use logical reasoning and think step by step."
• Reasoning chain, $r$: "The cafeteria had 23 apples originally. They used 20 to make lunch. So they had $23-20=3$. They bought 6 more, so they now have $3+6=9$."

When we condition the language model to generate the answer $y$, there are two distinct distributions to consider:

1. $f_{LLM}(y \mid x \odot p)$:
   This distribution is conditioned on the input $x$ and the prompt $p$, but without reasoning paths explicitly included. Here, the model sees:
   "The cafeteria had 23 apples. ... how many apples do they have? Use logical reasoning and think step by step. The final answer is ..."

   However, the logits at this stage do not incorporate the intermediate reasoning chain $r$. This will lead to noisy or incorrect loss as well as gradient calculation for $p$. The final output probabilities may misrepresent the likelihood of the correct answer due to the lack of explicit reasoning steps.

2. $f_{LLM}(y \mid x \odot p \odot r)$:
   This distribution is conditioned on $x$, $p$, and the reasoning chain $r$ induced by the prompt $p$. Here, the model sees:
   "The cafeteria had 23 apples. ... how many apples do they have? Use logical reasoning and think step by step ... The cafeteria had 23 apples originally. They used 20 to make lunch. … $3+6=9$. Therefore, the final answer is ..."

   The presence of $r$ ensures that $y$ is conditioned on the generated reasoning chain induced by the prompt, representing accurate loss and therefore gradients with respect to $p$. This represents not only the answer but also the induced reasoning.

This also aligns with [1], as it shows that without generating reasoning steps, final answer probabilities might be incorrect.

Lastly, we included additional experiments comparing GreaTer to other gradient-based approaches that do not consider the reasoning chain [2,3] in Table 6 (Appendix C of the updated manuscript). The table is summarized below:

---

Weakness 4

What does the gradient direction $\frac{\partial L}{\partial \epsilon_i}$ physically mean? Why is there a negative sign and why is the token with the highest negative gradient value selected instead of the one with the largest gradient norm?

Thank you so much for raising this important point. The gradient direction $\frac{\partial L}{\partial \epsilon_i}$ indicates how much a token contributes to increasing the loss function. Since our goal is to reduce the loss, we focus on tokens with the highest negative gradient values, as they correspond to changes that decrease the loss most effectively. This is why we select the token with the most negative gradient value, rather than one with the largest gradient magnitude, which could signify either an increase or decrease in loss.

We are thankful for your detailed and comprehensive review! We highly appreciate your suggestions and have uploaded an updated PDF by including new additional experiments and improved paper presentation accordingly. Below we summarize and address your concerns:

---

Weakness 1: Presentation is unclear

• Slight notation abuse: The output space of $f_{LLM}$ is not well-defined. Does it output texts or token probabilities? They are different in Eq. 2 & 3.

We agree this notation was a little confusing. In Equation 3, we are using $f_{LLM}(\cdot \mid \ldots)$ to take token probabilities. On the other hand, in Section 4.1, we have updated the manuscript to clarify that the reasoning chain $r$ is sampled from $f_{LLM}(x \odot p)$, i.e. $r \sim f_{LLM}(x \odot p)$, and we have made changes accordingly in Equation 2. With the updates in Section 4.1, we hope this resolves the confusion.

• It is not clear for the main results presented in Sec. 5.2 which model is used for prompt evaluation and which model is used for optimizing the prompt (e.g., in Table 2).

Thank you so much for pointing this out. To improve the presentation of Table 2, we have explicitly mentioned the target model (the model used for evaluating the prompt) and the optimizer model in the table heading. We also clarified this in the caption to improve readability. The table is summarized below:

• The complete Algorithm 1 in Appx. B.1 should be moved to the main text for better understanding, as the presentation of the designed method is not very easy to follow.

We really appreciate your feedback on improving the layout. As per your suggestions, we have moved Algorithm 1 to the main text in Section 4, where the methodology of GreaTer is discussed.

---

Weakness 2

Sec. 5.6 does not show much insight, which I think should be omitted from the main text.

We also agree with your suggestion to transfer Section 5.6 (Comparison against few-shot in-context learning) to the Appendix. We believe this change greatly improves the overall readability of the paper.

Dear Reviewer 7nfg,

We sincerely appreciate your valuable feedback. With the discussion concluding soon (December 2nd), we kindly ask if our responses have addressed your concerns and let us know if any further questions or comments you might have. Thanks!

Best, Authors

Question 2 How do the computational costs of GreaTer compare to traditional text-based prompt optimization methods, especially when considering the training and inference phases?

Thanks for asking this! We include information on the computational costs of GreaTer in our response to Weakness 2.

---

Question 3 The paper mentions the impact of different initialization prompts. Could the authors elaborate on how sensitive GreaTer is to the choice of initialization and whether there are best practices for initializing prompts?

Thanks for asking this! As shown in Table 7 of Appendix F, different initialization prompts can lead to prompts that look quite distinct yet achieve comparable performance metrics. This variation arises because there are often multiple valid ways (prompts) to solve a problem, and the optimization process may converge to any of these depending on the initialization.

Similar to other optimization problems, a well-chosen initialization can be beneficial. While we use a fixed initialization prompt across all problems in our experiments, incorporating human insights or domain-specific understanding into the initialization can guide the optimization process toward the target prompt more efficiently, potentially enabling faster convergence.

---

References

[1] Shin, Taylor, et al. "Autoprompt: Eliciting knowledge from language models with automatically generated prompts." arXiv preprint arXiv:2010.15980 (2020).
[2] Wen, Yuxin, et al. "Hard prompts made easy: Gradient-based discrete optimization for prompt tuning and discovery." Advances in Neural Information Processing Systems 36 (2024).

Thank you so much for your insightful reviews! We have uploaded an updated PDF by including new additional experiments and improved paper presentation accordingly. We carefully address the weaknesses and questions as follows:

---

Weakness 1 While GreaTer shows promising results, it is not clear how well these findings generalize to other types of tasks beyond reasoning tasks. Future work could explore the applicability of GreaTer to a broader range of NLP tasks.**

Thank you for bringing up this valuable point. We acknowledge that GreaTer is currently designed with a primary focus on reasoning tasks to enhance performance in complex scenarios. A critical aspect of GreaTer is the computation of gradients based on task loss, which requires well-defined and objective evaluation criteria. However, tasks like generation or summarization might not have clearly defined objective evaluation criteria.

An interesting direction for future work could involve leveraging model-based verifiers to provide a reward signal for such tasks. This reward signal could then be used to compute policy gradients, enabling GreaTer to optimize prompts even for tasks without explicit evaluation criteria. Exploring this approach could broaden the applicability of GreaTer to generation, summarization, and other NLP tasks beyond reasoning.

---

Weakness 2 Although GreaTer aims to reduce reliance on large LLMs, the paper does not discuss the computational resources required for the gradient-based optimization process itself. More details on this aspect would be beneficial.

Thank you for your feedback. We have added a detailed complexity analysis in Appendix D of the updated manuscript, comparing the computational demands of GreaTer with text-feedback-based approaches. This provides valuable insights into the resource requirements of our method. A summary of the analysis is given below:

Complexity Analysis: GreaTer vs. Text-Based Feedback Approaches

Assume each sample contains $L$ input-output tokens on average.

---

GreaTer

• Per Sample:
  • Forward pass: $O(L^2)$
  • Backward pass: $O(L^2)$
• Total Complexity:
  $O(NL^2)$

---

Text-Based Feedback Approaches

• Per Iteration:
  • Forward pass for $N$ samples: $O(NL^2)$
  • Feedback generation for $n$ incorrect samples: $O(n^2L^2)$
• Total Complexity: $O(NL^2) + O(n^2L^2)$

---

Comparison

• GreaTer: $O(NL^2)$ (consistent).
• Text-Based Feedback:
  • Simple tasks ($n \to 0$): $O(NL^2)$
  • Difficult tasks ($n \to N$): $O(N^2L^2)$

This complexity difference is also translated into real-world performance. In the movie_recommendation task, GreaTer required approximately ~5 hours for optimization, whereas TextGrad required a total of ~14 hours for prompt optimization in our own setup.

---

Weakness 3 The paper could benefit from a more detailed comparison with other gradient-based methods, especially those that also aim to optimize prompts without relying on large LLMs.

Thank you very much for providing this suggestion! We have compared GreaTer performance to that of some gradient-based approaches in Appendix C (Table 6) of the updated manuscript. Here we compare the performance of GreaTer to that of AutoPrompt [1] and PEZ [2]. The table is summarized below:

GreaTer also provides interpretable prompts, whereas baselines provide gibberish prompts (e.g., PEZ provides “ılığı, nullabancı Prince numerous-source sweeps Sawyer62337” as the optimized prompt for movie_recommendation). Overall, this table clearly demonstrates that GreaTer significantly outperforms previous gradient-based approaches, primarily due to its adoption of gradient over reasoning. In contrast, these baselines overlook reasoning when calculating both the task loss and gradient, resulting in suboptimal signals for prompt optimization in reasoning tasks.

---

Question 1 Can the authors comment on the potential of GreaTer to be applied to tasks outside of reasoning, such as generation or summarization tasks?

Thanks for bringing this up! Please check our response to Weakness 1.

Dear Reviewer ZouY,

We sincerely appreciate your valuable feedback. With the discussion concluding soon (December 2nd), we kindly ask if our responses have addressed your concerns and let us know if any further questions or comments you might have. Thanks!

Best, Authors

---

Weakness 3: Line 462 explicitly mentions large language models (LLMs), which have already been defined in the introduction section. There seems to be a typo in Line 1186 as well: "Use these logical reasoning process steps and explain Step. step. Here is correct answer.","step" appears multiple times.

Thank you for catching these issues! We have addressed the typo on Line 462 in the revised manuscript. Regarding Line 1186, the text represents an optimized prompt and is an example where minor grammatical inconsistencies are present. However, we believe these prompts still remain interpretable and significantly better compared to the unintelligible prompts generated by some other methods. For example, in our comparison with the prior gradient-based approach, PEZ, one of its optimized prompts was "ıldığı, nullabancı Prince numerous-source sweeps Sawyer62337"

As evident, such prompts are largely gibberish and lack interpretability, underscoring the advantage of GreaTer in generating more coherent and functional prompts.

---

Weakness 4: Could include more diverse task types beyond reasoning tasks.

Thank you for highlighting this point. GreaTer is currently focused on reasoning tasks, leveraging gradients computed from well-defined task loss for optimization. Tasks like generation, however, often lack clear objective evaluation criteria. A promising future direction could involve using model-based verifiers to provide reward signals for such tasks. This can extend GreaTer’s applicability to diverse NLP tasks (including generation/summarization tasks) by using LLM verifier-provided reward signals to compute policy gradients for token selection.

---

Question 1: How does the method scale with increasing model size? Have you considered using GreaTer on larger open-source models like Llama-3.1-70B?

We really appreciate you bringing up this point. While GreaTer is primarily focused on smaller language models, it would definitely be very interesting to use it on larger models like Llama-3.1-70B. By guiding these powerful models with optimized prompts, we could potentially tackle significantly more challenging tasks. However, scaling to such a large model will require more computational resources and is currently beyond our available computational constraints.

Since our primary focus is on smaller language models, we added a new experiment by comparing the performance of GreaTer in a very small language model Llama-3.2-1B to the baselines. The table is summarized below. As we can see, for very small language models, GreaTer provides excellent performance across different tasks.

---

---

We hope these changes and additions address all your concerns and provide further clarity to our approach!

Thank you so much for your thoughtful and constructive feedback! Your insights and suggestions have been extremely valuable in improving our manuscript. We have uploaded an updated PDF by including new additional experiments and improved paper presentation accordingly. Below, we have carefully addressed each of the points you raised.

---

Weakness 1: The case studies section could benefit from more detailed analysis of why certain prompts work better.

Thank you for your insightful suggestion on this point. Well-designed prompts do more than give basic instructions—they provide clear, practical strategies tailored to the task. By encouraging structured and systematic thinking, such prompts improve problem-solving and enhance model performance. We can show one example from the BBH-navigate task, demonstrating how different prompts affect the responses:

---

Question

If you follow these instructions, do you return to the starting point?

• Take 7 steps.
• Take 4 steps.
• Take 3 steps.
• Take 10 steps.
• Turn left.
• Turn around.

Options:

• Yes
• No

---

APO Prompt: Let's think step by step.

Response:
Let’s think step by step.

1. 7 steps: You move 7 steps forward.
2. 4 steps: You move 4 more steps forward.
3. 3 steps: You move 3 more steps forward.
4. 10 steps: You move 10 more steps forward.
5. Turn left: You change direction to the left.
6. Turn around: You turn 180 degrees, now facing the opposite direction.

At this point, you've essentially reversed your path. Since you turned around, you'll be heading back towards your starting point.

Answer: Yes. [Incorrect]

---

GreaTer Prompt: Use proper mathematical logic, explaining step by step. Finally, give the correct answer.

Response:

1. Step 1: Take 7 steps forward.

2. Step 2: Take 4 steps forward.

3. Step 3: Take 3 steps forward.

4. Step 4: Take 10 steps forward.

   At this point, you've taken a total of $7 + 4 + 3 + 10 = 24$ steps forward.

5. Step 5: Turn left. This changes your direction but doesn't affect the total distance traveled.

6. Step 6: Turn around. This means you're now facing the opposite direction of where you started.

7. Step 7: No further steps are taken in this instruction set.

Answer: No.
You will not return to the starting point because you've moved $24$ steps forward and then simply turned around. [Correct]

---

From this example, we can see that the GreaTer prompt encouraged the LLM to solve the problem from a mathematical perspective, calculating the steps accurately, which led to the correct response. On the contrary, the APO prompt lacked such guidance, resulting in an incorrect conclusion. We have expanded this discussion in the case studies section of the draft.

---

Weakness 2: Could benefit from more theoretical analysis of why gradients over reasoning work better.

GreaTer employs a well-defined optimization framework, as detailed in Section 4 of our paper. Our method explicitly integrates reasoning into the optimization process. The steps involve generating reasoning, calculating the loss, and then using the gradient over the reasoning to refine the prompt. This approach ensures reasoning is a core part of the optimization. For example:

Input ($x$): "The cafeteria had 23 apples. If they used 20 to make lunch and bought 6 more, how many apples do they have?"
Prompt ($p$): "Use logical reasoning and think step by step."
Reasoning chain ($r$): "The cafeteria had 23 apples originally. They used 20 to make lunch. So they had $23 - 20 = 3$. They bought 6 more, so they now have $3 + 6 = 9$."

When conditioning the model on $x \odot p$ (input and prompt only), the reasoning is excluded, often resulting in noisy gradients and misaligned probabilities. The model processes:

“The cafeteria had 23 apples. ... how many apples do they have? Use logical reasoning and think step by step. The final answer is …”

Here, the next token probabilities are not conditioned on the reasoning chain, leading to incorrect logits and suboptimal loss values.

In contrast, conditioning on $x \odot p \odot r$ (input, prompt, and reasoning) explicitly incorporates the reasoning chain. The model processes:

“The cafeteria had 23 apples. ... how many apples do they have? Use logical reasoning and think step by step ... The cafeteria had 23 apples originally. They used 20 to make lunch. … $3 + 6 = 9$. Therefore, the final answer is …”

In this case, aligning token probabilities with the reasoning chain improves logits and minimizes loss. By explicitly integrating reasoning, the model enhances both reasoning and task performance, explaining why GreaTer outperforms methods that omit this integration.

Dear Reviewer 24Zw,

We sincerely appreciate your valuable feedback. With the discussion concluding soon (December 2nd), we kindly ask if our responses have addressed your concerns and let us know if any further questions or comments you might have. Thanks!

Best, Authors