REVIEW 3 major objections 5 minor 36 references
GRL-Prompt: Towards Knowledge Graph based Prompt Optimization via Reinforcement Learning
T0 review · 3 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash
Pith's one-line read GRL-Prompt claims that building a knowledge graph from a user query and candidate in-context examples, then training a policy network with reinforcement learning to select and order those examples, improves LLM generation scores by…
desk verdict A novel but formally under-specified RL approach to ordered in-context example selection; the core idea is worth engaging, but the policy-gradient math needs major repair and the headline gains are overstated. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is a heterogeneous knowledge graph $G(q)$ with one query node and one node per candidate example, carrying three edge relations ($r_{cc}$, $r_{qc}$, $r_{cq}$), embedded by a two-layer Heterogeneous Graph Transformer. On top of it, the policy network factors as a product over a pairwise edge classifier (which computes order probabilities between two candidates via a sin-based pair score) and an in-context matching network (which scores query-candidate relevance with a scaled sigmoid attention). The policy-gradient update uses the REINFORCE estimator with an embedding-based reward $R(a,\hat{a}) = \lambda R_m(a,\hat{a}) + (1-\lambda)R_e(a,\hat{a})$ that stabilizes training. This machinery matters because it couples relevance and order into one differentiable distribution while keeping the LLM a black box that only supplies rewards.
What would settle it
Instrument the sampler on a fixed query: compute every pairwise order score and matching score, record the ordered prompt the system actually sends to the LLM, and check whether that prompt has the highest probability under Eq. (5); any prompt whose probability is not maximal, or any pair predicted in a cycle, shows the training objective is not the distribution being evaluated.
Extended reading notes
Core claim
The paper's central claim is that prompt optimization for in-context learning can be cast as a structured reinforcement-learning problem over a knowledge graph. The query and candidate examples become nodes; a heterogeneous graph transformer embeds them; a policy network scores each candidate's relevance to the query (in-context matching network) and predicts, for every pair of candidates, which should appear first (pairwise edge classifier). The two scores multiply into one policy distribution, and policy gradient maximizes an embedding-shaped reward that combines fuzzy textual similarity with cosine embedding similarity. Across Alpaca and Dolly with GPT-4, GPT-3, and LLaMA, the resulting ordered example sequences outperform all tested baselines by the reported margins, with ablations attributing the gains to both the knowledge graph and the reward feedback.
Load-bearing premise
The claim assumes the prompts actually evaluated are sampled from the distribution the policy gradient optimizes, but the paper never specifies how the per-candidate matching scores decide how many examples are selected or how conflicting pairwise order predictions are resolved into a single ordered prompt.
Editorial extensions
If this is right
- The same knowledge-graph-plus-policy design can be re-trained for any black-box LLM, since the generator only supplies rewards, so prompt optimization becomes a transferable service rather than a per-model manual exercise.
- Directly modeling pairwise order should make prompt selection less sensitive to permutation effects, which prior retrieval and fixed-length selectors ignore.
- The ablations imply that both the knowledge-graph representation and the reward-feedback loop are doing measurable work, so future prompt optimizers should keep structure and feedback rather than relying on embeddings alone.
- Because the reward is computed from ROUGE/BLEU scores, the approach is immediately extendable to other text-to-text metrics, and the same pipeline can be pointed at a new dataset without changing the method.
Reading between the lines
- The paper never fixes the number of in-context examples, so a reader could test whether the gains come from choosing a different-length prompt rather than from ordering; comparing against a variant with K fixed would separate the two effects.
- The knowledge graph edges are all pre-defined rather than learned, so the graph construction may be less important than the HGT embedding and RL reward; replacing the graph with a plain encoder in the same training loop would isolate that.
- The loose link between the factored policy in Eq. (5) and the topological-sort sampling in Eq. (6) suggests the training objective and the executed prompt distribution may diverge; checking this directly is a concrete falsification experiment.
- The same order-sensitive selection view transfers naturally to retrieval-augmented generation, where the order of retrieved passages is known to affect answers, so GRL-Prompt-style pairwise ranking could be adapted to rerank retrieved contexts.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper proposes GRL-Prompt, a reinforcement-learning framework for in-context prompt optimization. It constructs a graph from the user query and candidate examples, applies a heterogeneous graph transformer to embed the graph, and uses a policy network combining a pairwise edge classifier (PEC) and an in-context matching network (ICMN) to select and order in-context examples. Experiments on Alpaca and Dolly with GPT-4, GPT-3, and LLaMA report improved ROUGE and BLEU scores over several baselines, together with ablations and sensitivity analyses.
Significance. If the method works as described, it would add a useful learned alternative to random, retrieval-based, and fixed-length prompt-selection methods, with the claimed advantage of handling order sensitivity through RL. The paper ships ablations, sensitivity analyses, and a stated public code release. However, the formalization of the policy distribution and the RL update is not sound as written, and the empirical claims are weakened by missing variance and significance reporting. The core idea is worth considering, but the manuscript needs substantial technical clarification before the claims can be assessed.
major comments (3)
- [4.2.1, Eqs. (5)-(6) and 4.2.3, Eq. (8)] The distribution p(pi) in Eq. (5) is not a probability distribution over ordered subsets of candidate examples. It multiplies f_icmn over all N candidates and f_pec over all i<j pairs, with no normalization over subset sizes and no non-selection factors (1-f_icmn) for excluded examples. Consequently, Eq. (5) cannot be the distribution from which the ordered prompt in Eq. (6) is sampled, and the log-probability used in the REINFORCE estimator in Eq. (8) is not the log-probability of the sampled sequence. Moreover, the mechanism by which pairwise PEC predictions are converted into a global ordering via topological sorting is undefined when the predicted pairwise orders contain cycles, which have positive probability under Eq. (3). Please specify the exact sampling procedure: how many examples K are selected, how the subset size is chosen, and how cyclic pairwise predictions are resolved. Then provide the correct log-probability of the sampled sequence and re-derive the policy-gradient update.
- [Abstract and Section 5.2, Table 1] The abstract claims an average improvement of 0.10 in ROUGE-1, 0.07 in ROUGE-2, 0.07 in ROUGE-L, and 0.05 in BLEU, but this is not the gain over the best baseline. In Table 1, the margins over the best baseline are at most 0.04, and several cells show no improvement at all (e.g., Dolly/GPT-4 ROUGE-2, ROUGE-L, and BLEU are all +0.00). Please clarify the reference point for the reported average improvement and, given that the experiments were repeated three times, report standard deviations or a statistical significance test so that the reader can judge whether the small margins are reliable.
- [5.1.2 and 4.2.1] The number of in-context examples K used by the main method is never defined. The prompt template in the appendix uses →P_ic = [p^1_ic, ..., p^K_ic], and Eq. (6) defines the state space over all possible ordered subsets, but the policy network in Eq. (5) does not specify how many examples are selected or how K is determined. The ablation variant “-w/o RF” sets the number of examples to 2, but the main method’s K is absent. Without this, the action space and the reported results are not fully reproducible.
minor comments (5)
- [5.1.2] The text says “We compare GRL-Prompt with three baselines” but then lists five baselines (Random, PromptPG, CoT, Pillow, UDR). Please correct the enumeration.
- [Eq. (3)] The pair score function ps(vi_c, vj_c) is defined via a softmax-like expression, but Eq. (2) then takes the max over the two directions. It is unclear why a max is used rather than a direct probability over the two directions, and the notation ps is easy to confuse with a probability. Please clarify the motivation and notation.
- [4.2.2, Eq. (7)] The reward term Rm is called “fuzzy textual similarity” but is never precisely defined; if it is automatically computed by ROUGE/BLEU or a related n-gram overlap measure, that should be stated explicitly, especially because the evaluation metrics are the same family of scores.
- [References] The LLaMA citation is listed as “Hugo et al.”; the correct author is Touvron et al. (2023).
- [Appendix A.2] The prompt template is called “Figure 1,” but Figure 1 in the main text is the system overview. The cross-referencing between the main text and appendix is confusing; please renumber or refer explicitly.
Circularity Check
No significant circularity: the policy is trained on a separate training split and evaluated on held-out test queries; the reward is a training-signal proxy for the reported text-similarity metrics, not a fitted parameter that determines the test result.
full rationale
The paper's central derivation is a policy-gradient training procedure for selecting and ordering in-context examples. The claimed prediction is that the learned policy improves ROUGE and BLEU on held-out test queries from Alpaca and Dolly after RL training on a separate 200-query split. No equation defines the reported test metrics in terms of the fitted parameters. Eq. (5) defines a policy probability from PEC/ICMN scores, Eq. (6) samples ordered sequences via topological sorting, Eq. (7) defines a reward from response similarity, and Eq. (8) is a standard REINFORCE update. The reward uses lexical and embedding similarity, which are proxies for the reported text-similarity metrics, but these rewards are computed on training responses; the reported ROUGE/BLEU values are computed on 800 held-out test queries, so the policy must generalize beyond its training signal. There are no load-bearing self-citations: prior-work citations are external baselines or standard components such as HGT, BERT, and REINFORCE. The appendix limitation (A.6) cautions that automatic-score rewards may not align with human evaluation, which is a validity caveat rather than a circularity. The main formal weakness is that the paper does not fully specify how the product in Eq. (5) is converted into the sampled subset/order used in Eq. (6) and Eq. (8), so the REINFORCE estimator may not match the actual sampling distribution; that is a correctness gap, not a reduction of the result to its inputs.
Assumptions & free parameters
free parameters (4)
- lambda (reward weight) =
0.4
- HGT layer count =
2
- size of RL training set =
200
- number of in-context examples K
assumptions (5)
- standard math Policy gradient theorem (Williams 1992) gives an unbiased gradient of the expected reward.
- domain assumption A heterogeneous graph transformer can learn useful representations from the fully connected KG defined in Section 4.1.1.
- ad hoc to paper The three fixed relation types with complete connectivity form a meaningful state representation.
- domain assumption Automatic similarity scores are a valid reward proxy for prompt quality.
- ad hoc to paper Predicted pairwise orders from PEC can be composed by topological sorting into a valid total order.
Cite this review
Pith. "Pith review of GRL-Prompt: Towards Knowledge Graph based Prompt Optimization via Reinforcement Learning." pith.science (2026). https://pith.science/paper/MBEEECK2
@misc{pith2026241114479,
author = {Pith},
title = {Pith review of: GRL-Prompt: Towards Knowledge Graph based Prompt Optimization via Reinforcement Learning},
year = {2026},
howpublished = {\url{https://pith.science/paper/MBEEECK2}},
note = {Machine review of arXiv:2411.14479}
}
read the original abstract
Large language models (LLMs) have demonstrated impressive success in a wide range of natural language processing (NLP) tasks due to their extensive general knowledge of the world. Recent works discovered that the performance of LLMs is heavily dependent on the input prompt. However, prompt engineering is usually done manually in a trial-and-error fashion, which can be labor-intensive and challenging in order to find the optimal prompts. To address these problems and unleash the utmost potential of LLMs, we propose a novel LLMs-agnostic framework for prompt optimization, namely GRL-Prompt, which aims to automatically construct optimal prompts via reinforcement learning (RL) in an end-to-end manner. To provide structured action/state representation for optimizing prompts, we construct a knowledge graph (KG) that better encodes the correlation between the user query and candidate in-context examples. Furthermore, a policy network is formulated to generate the optimal action by selecting a set of in-context examples in a rewardable order to construct the prompt. Additionally, the embedding-based reward shaping is utilized to stabilize the RL training process. The experimental results show that GRL-Prompt outperforms recent state-of-the-art methods, achieving an average increase of 0.10 in ROUGE-1, 0.07 in ROUGE-2, 0.07 in ROUGE-L, and 0.05 in BLEU.
Figures
Figures from the paper (9 more)
Reference graph
Works this paper leans on
-
[1]
online" 'onlinestring :=
ENTRY address archivePrefix author booktitle chapter edition editor eid eprint eprinttype howpublished institution journal key month note number organization pages publisher school series title type volume year doi pubmed url lastchecked label extra.label sort.label short.list INTEGERS output.state before.all mid.sentence after.sentence after.block STRING...
-
[2]
write newline
" write newline "" before.all 'output.state := FUNCTION n.dashify 't := "" t empty not t #1 #1 substring "-" = t #1 #2 substring "--" = not "--" * t #2 global.max substring 't := t #1 #1 substring "-" = "-" * t #2 global.max substring 't := while if t #1 #1 substring * t #2 global.max substring 't := if while FUNCTION word.in bbl.in capitalize " " * FUNCT...
-
[3]
Bach, Victor Sanh, Zheng-Xin Yong, Albert Webson, Colin Raffel, Nihal V
Stephen H. Bach, Victor Sanh, Zheng-Xin Yong, Albert Webson, Colin Raffel, Nihal V. Nayak, Abheesht Sharma, Taewoon Kim, M Saiful Bari, Thibault Fevry, Zaid Alyafeai, Manan Dey, Andrea Santilli, Zhiqing Sun, Srulik Ben-David, Canwen Xu, Gunjan Chhablani, Han Wang, Jason Alan Fries, Maged S. Al-shaibani, Shanya Sharma, Urmish Thakker, Khalid Almubarak, Xia...
arXiv 2022
-
[4]
Rishi Bommasani and Claire Cardie. 2020. Intrinsic evaluation of summarization datasets. In Proc. of the International Conference on Empirical Methods in Natural Language Processing, pages 8075--8096
work page 2020
-
[5]
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. 2020. Language models are few-shot learners. In Proc. of the International Conference on Neural Information Processing Systems, pages 1877--1901
work page 2020
-
[6]
Xiaojun Chen et al. 2020. A review: Knowledge reasoning over knowledge graph. Expert Systems with Applications, 141:112948
work page 2020
-
[7]
Mike Conover, Matt Hayes, Ankit Mathur, Jianwei Xie, Jun Wan, Sam Shah, Ali Ghodsi, Patrick Wendell, Matei Zaharia, and Reynold Xin. 2023. Free dolly: Introducing the world’s first truly open instruction-tuned llm. Company Blog of Databricks
2023
-
[8]
Mingkai Deng, Jianyu Wang, Cheng-Ping Hsieh, Yihan Wang, Han Guo, Tianmin Shu, Meng Song, Eric P Xing, and Zhiting Hu. 2023. Rlprompt: Optimizing discrete text prompts with reinforcement learning. In Proc. of the Conference on Empirical Methods in Natural Language Processing, pages 3369--3391
work page 2023
Show all 36 references
-
[9]
Qingxiu Dong, Lei Li, Damai Dai, Ce Zheng, Zhiyong Wu, Baobao Chang, Xu Sun, Jingjing Xu, and Zhifang Sui. 2022. A survey on in-context learning. arXiv preprint arXiv:2301.00234
2022 arXiv
-
[10]
Deepanway Ghosal, Navonil Majumder, Rada Mihalcea, and Soujanya Poria. 2021. Stack: Sentence ordering with temporal commonsense knowledge. In Proc. of the International Conference on Empirical Methods in Natural Language Processing, pages 8676--8686
2021
-
[11]
Ziniu Hu, Yuxiao Dong, Kuansan Wang, and Yizhou Sun. 2020. Heterogeneous graph transformer. In Proc. of the Web Conference, pages 2704--2710
2020
-
[12]
Touvron Hugo, Lavril Thibaut, Izacard Gautier, Martinet Xavier, Lachaux Marie-Anne, Lacroix Timothée, Rozière Baptiste, Goyal Naman, Hambro Eric, Azhar Faisal, Rodriguez Aurelien, Joulin Armand, Grave Edouard, and Lample Guillaume. 2023. Llama: Open and efficient foundation la...
2023 arXiv
-
[13]
Mike Lewis, Yinhan Liu, Naman Goyal, Marjan Ghazvininejad, Abdelrahman Mohamed, Omer Levy, Ves Stoyanov, and Luke Zettlemoyer. 2019. Bart: Denoising sequence-to-sequence pre-training for natural language generation, translation, and comprehension. arXiv preprint arXiv:1910.13461
2019 arXiv
-
[14]
Chengzhengxu Li, Xiaoming Liu, Yichen Wang, Duyi Li, Yu Lan, and Chao Shen. 2024 a . Dialogue for prompting: a policy-gradient-based discrete prompt generation for few-shot learning. In Proc. of the AAAI Conference on Artificial Intelligence, pages 18481--18489
2024
-
[15]
Guozheng Li, Wenjun Ke, Peng Wang, Zijie Xu, Ke Ji, Jiajun Liu, Ziyu Shang, and Qiqing Luo. 2024 b . Unlocking instructive in-context learning with tabular prompting for relational triple extraction. In Proc. of International Conference on Computational Linguistics, pages 17131--17143
2024
-
[16]
Xiaonan Li, Kai Lv, Hang Yan, Tianyang Lin, Wei Zhu, Yuan Ni, Guotong Xie, Xiaoling Wang, and Xipeng Qiu. 2023. Unified demonstration retriever for in-context learning. In Proc. of the Annual Meeting of the Association for Computational Linguistics, pages 4644--4668
2023
-
[17]
Yihao Li, Ru Zhang, Jianyi Liu, and Gongshen Liu. 2024 c . An enhanced prompt-based llm reasoning scheme via knowledge graph-integrated collaboration. arXiv preprint arXiv:2402.04978
2024 arXiv
-
[18]
Chin-Yew Lin. 2004. Rouge: A package for automatic evaluation of summaries. In Proc. of the International Conference on Association for Computational Linguistics, pages 74--81
2004
-
[19]
Chin-Yew Lin and Franz Josef Och. 2004. Automatic evaluation of machine translation quality using longest common subsequence and skip-bigram statistics. In Proc. of the Annual Meeting of the Association for Computational Linguistics, pages 605--612
2004
-
[20]
Jiachang Liu, Dinghan Shen, Yizhe Zhang, Bill Dolan, Lawrence Carin, and Weizhu Chen. 2021. What makes good in-context examples for gpt- 3 ? arXiv preprint arXiv:2101.06804
2021 arXiv
-
[21]
Pan Lu, Liang Qiu, Kai-Wei Chang, Ying Nian Wu, Song-Chun Zhu, Tanmay Rajpurohit, Peter Clark, and Ashwin Kalyan. 2023. Dynamic prompt learning via policy gradient for semi-structured mathematical reasoning. pages 1--26
2023
-
[22]
Yao Lu, Max Bartolo, Alastair Moore, Sebastian Riedel, and Pontus Stenetorp. 2022. Fantastically ordered prompts and where to find them: Overcoming few-shot prompt order sensitivity. In Proc. of the Annual Meeting of the Association for Computational Linguistics, pages 8086--8098
2022
-
[23]
Sewon Min, Xinxi Lyu, Ari Holtzman, Mikel Artetxe, Mike Lewis, Hannaneh Hajishirzi, and Luke Zettlemoyer. 2022. Rethinking the role of demonstrations: What makes in-context learning work? arXiv preprint arXiv:2202.12837
2022 arXiv
-
[24]
Feng Nie, Meixi Chen, Zhirui Zhang, and Xu Cheng. 2022. Improving few-shot performance of language models via nearest neighbor calibration. arXiv preprint arXiv:2212.02216
2022 arXiv
-
[25]
Zhenting Qi, Xiaoyu Tan, Shaojie Shi, Chao Qu, Yinghui Xu, and Yuan Qi. 2023. Pillow: Enhancing efficient instruction fine-tuning via prompt matching. In Proc. of the Conference on Empirical Methods in Natural Language Processing, pages 471--482
2023
-
[26]
Colin Raffel, Noam Shazeer, Adam Roberts, Katherine Lee, Sharan Narang, Michael Matena, Yanqi Zhou, Wei Li, and Peter J Liu. 2020. Exploring the limits of transfer learning with a unified text-to-text transformer. Journal of machine learning research, 21(140):1--67
2020
-
[27]
Xindi Shang, Zehuan Yuan, Anran Wang, and Changhu Wang. 2021. Multimodal video summarization via time-aware transformers. In Proc. of the International Conference on Multimedia, pages 1756--1765
2021
-
[28]
Richard S Sutton and Andrew G Barto. 2018. Reinforcement learning: An introduction. MIT press
2018
-
[29]
Rohan Taori, Ishaan Gulrajani, Tianyi Zhang, Yann Dubois, Xuechen Li, Carlos Guestrin, Percy Liang, and Tatsunori B Hashimoto. 2023. Stanford alpaca: An instruction-following llama model
2023
-
[30]
Daniel J Velleman and Gregory S Call. 1995. Permutations and combination locks. Mathematics Magazine, 68(4):243--253
1995
-
[31]
Jianing Wang, Qiushi Sun, Xiang Li, and Ming Gao. 2023. Boosting language models reasoning with chain-of-knowledge prompting. arXiv preprint arXiv:2306.06427
2023 arXiv
-
[32]
Jason Wei, Maarten Bosma, Vincent Y Zhao, Kelvin Guu, Adams Wei Yu, Brian Lester, Nan Du, Andrew M Dai, and Quoc V Le. 2022 a . Finetuned language models are zero-shot learners. In Proc. of the International Conference on Learning Representations, pages 1--46
2022
-
[33]
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al. 2022 b . Chain-of-thought prompting elicits reasoning in large language models. In Proc. of the International Conference on Neural Information Processing Systems, pages 24824--24837
2022
-
[34]
Ronald J Williams. 1992. Simple statistical gradient-following algorithms for connectionist reinforcement learning. Machine learning, 8:229--256
1992
-
[35]
Xin Xu, Yue Liu, Panupong Pasupat, Mehran Kazemi, et al. 2024. In-context learning with retrieved demonstrations for language models: A survey. arXiv preprint arXiv:2401.11624
2024 arXiv
-
[36]
Jiacheng Ye, Zhiyong Wu, Jiangtao Feng, Tao Yu, and Lingpeng Kong. 2023. Compositional exemplars for in-context learning. In Proc. of the International Conference on Machine Learning, pages 39818--39833
2023
Reviewed August 12, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.