Unveiling the Lexical Sensitivity of LLMs: Combinatorial Optimization for Prompt Enhancement

Pengwei Zhan, Zhen Xu, Qian Tan, Jie Song, Ru Xie

Abstract

Large language models (LLMs) demonstrate exceptional instruct-following ability to complete various downstream tasks. Although this impressive ability makes LLMs flexible task solvers, their performance in solving tasks also heavily relies on instructions. In this paper, we reveal that LLMs are over-sensitive to lexical variations in task instructions, even when the variations are imperceptible to humans. By providing models with neighborhood instructions, which are closely situated in the latent representation space and differ by only one semantically similar word, the performance on downstream tasks can be vastly different. Following this property, we propose a black-box Combinatorial Optimization framework for Prompt Lexical Enhancement (COPLE). COPLE performs iterative lexical optimization according to the feedback from a batch of proxy tasks, using a search strategy related to word influence. Experiments show that even widely-used human-crafted prompts for current benchmarks suffer from the lexical sensitivity of models, and COPLE recovers the declined model ability in both instruct-following and solving downstream tasks.

Introduction: The Lexical Sensitivity Problem

While Large Language Models (LLMs) are often treated as if they understand the high-level intent of human instructions, they are actually hyper-sensitive to specific lexical choices. This phenomenon, termed lexical sensitivity, means that changing a single word in a prompt to a near-synonym can cause performance to plummet, even if the meaning remains identical to a human reader.

Research indicates a "Synonym Paradox": LLMs do not treat synonyms equally. Replacing "meaning" with "theme" or "identify" with "specify" can drastically shift how the model attends to input data. Furthermore, latent proximity does not guarantee performance parity. Prompts that are mathematically close in the model's internal representation space often yield wildly different accuracy levels, suggesting that human intuition is a poor optimizer for prompt engineering.

Figure 2: Latent representation of neighborhood prompts versus their task accuracy across different models and datasets.

Methodology: The COPLE Framework

To address this brittleness, we introduce COPLE (Combinatorial Optimization for Prompt Lexical Enhancement), a black-box framework designed to refine prompt wording without requiring access to a model's internal weights. The COPLE process follows three iterative steps:

  1. Identify Word Influence: The framework determines which words in a prompt are most "influential" by measuring the performance drop on proxy tasks when specific words are removed.
  2. Build a Search Space: For influential words, a Masked Language Model (MLM), such as RoBERTa, suggests semantically similar replacement candidates.
  3. Iterative Optimization: COPLE performs a greedy search, substituting words one by one. If a substitution improves performance on proxy tasks, the change is retained, iteratively "enhancing" the prompt.
Figure 1: The COPLE framework performing iterative lexical optimization to improve task pool accuracy.

Experimental Results

COPLE was evaluated using the GLUE and MMLU benchmarks against models like Llama-2-7B-chat, Mistral-7B-Instruct, and GPT-3.5-turbo. The results demonstrate significant performance recovery across various tasks:

  • Llama-2-7B-chat: Average accuracy increased from 44.15% to 56.04%, an 11.89% absolute gain. On the QQP dataset, accuracy rose from 35% to 57%.
  • Mistral-7B: Observed an average accuracy increase of 4.13%.
  • ChatGPT (GPT-3.5): Even highly-tuned proprietary models showed a 6.67% improvement through COPLE optimization.

Interestingly, optimized prompts often exhibited higher "perplexity," using less common word combinations that provided specific, non-obvious lexical cues the models favored over standard human phrasing.

Conclusion

LLMs possess latent abilities that are often masked by sub-optimal human-crafted instructions. COPLE demonstrates that by treating prompt engineering as a combinatorial optimization problem, we can significantly improve model performance and robustness. Future work will explore expanding this optimization beyond word-level substitutions to include structural changes and broader task formatting.

Summary updated

Abstract

Large language models (LLMs) demonstrate exceptional instruct-following ability to complete various downstream tasks. Although this impressive ability makes LLMs flexible task solvers, their performance in solving tasks also heavily relies on instructions. In this paper, we reveal that LLMs are over-sensitive to lexical variations in task instructions, even when the variations are imperceptible to humans. By providing models with neighborhood instructions, which are closely situated in the latent representation space and differ by only one semantically similar word, the performance on downstream tasks can be vastly different. Following this property, we propose a black-box Combinatorial Optimization framework for Prompt Lexical Enhancement (COPLE). COPLE performs iterative lexical optimization according to the feedback from a batch of proxy tasks, using a search strategy related to word influence. Experiments show that even widely-used human-crafted prompts for current benchmarks suffer from the lexical sensitivity of models, and COPLE recovers the declined model ability in both instruct-following and solving downstream tasks.
BibTeX
@inproceedings{zhan2024unveiling,
  author = {Pengwei Zhan and Zhen Xu and Qian Tan and Jie Song and Ru Xie},
  title = {{Unveiling the Lexical Sensitivity of LLMs: Combinatorial Optimization for Prompt Enhancement}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2024},
  url = {https://openreview.net/forum?id=DImnqt08xR},
}
Figure