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

arXiv: https://arxiv.org/abs/2405.20701 · HTML: https://mlsanity.com/paper/2405.20701/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 30 of its 63 references that are in the map.
- First posted on arXiv 31 May 2024.

## Builds on (most cited first, 30 of 30)

- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [RoBERTa: A Robustly Optimized BERT Pretraining Approach](https://mlsanity.com/paper/1907.11692/) (2019)
- [Llama 2: Open Foundation and Fine-Tuned Chat Models](https://mlsanity.com/paper/2307.09288/) (2023)
- [Measuring Massive Multitask Language Understanding](https://mlsanity.com/paper/2009.03300/) (2020)
- [Explaining and Harnessing Adversarial Examples](https://mlsanity.com/paper/1412.6572/) (2014)
- [Scaling Laws for Neural Language Models](https://mlsanity.com/paper/2001.08361/) (2020)
- [BERTScore: Evaluating Text Generation with BERT](https://mlsanity.com/paper/1904.09675/) (2019)
- [GLUE: A Multi-Task Benchmark and Analysis Platform for Natural Language Understanding](https://mlsanity.com/paper/1804.07461/) (2018)
- [Large Language Models are Zero-Shot Reasoners](https://mlsanity.com/paper/2205.11916/) (2022)
- [SQuAD: 100,000+ Questions for Machine Comprehension of Text](https://mlsanity.com/paper/1606.05250/) (2016)
- [Towards Evaluating the Robustness of Neural Networks](https://mlsanity.com/paper/1608.04644/) (2016)
- [A Broad-Coverage Challenge Corpus for Sentence Understanding through Inference](https://mlsanity.com/paper/1704.05426/) (2017)
- [Fantastically Ordered Prompts and Where to Find Them: Overcoming Few-Shot Prompt Order Sensitivity](https://mlsanity.com/paper/2104.08786/) (2021)
- [Large Language Models Are Human-Level Prompt Engineers](https://mlsanity.com/paper/2211.01910/) (2022)
- [SemEval-2017 Task 1: Semantic Textual Similarity - Multilingual and Cross-lingual Focused Evaluation](https://mlsanity.com/paper/1708.00055/) (2017)
- [Neural Network Acceptability Judgments](https://mlsanity.com/paper/1805.12471/) (2018)
- [The Limitations of Deep Learning in Adversarial Settings](https://mlsanity.com/paper/1511.07528/) (2015)
- [Unified Language Model Pre-training for Natural Language Understanding and Generation](https://mlsanity.com/paper/1905.03197/) (2019)
- [BERT-ATTACK: Adversarial Attack Against BERT Using BERT](https://mlsanity.com/paper/2004.09984/) (2020)
- [Universal Sentence Encoder](https://mlsanity.com/paper/1803.11175/) (2018)
- [Larger language models do in-context learning differently](https://mlsanity.com/paper/2303.03846/) (2023)
- [TextBugger: Generating Adversarial Text Against Real-world Applications](https://mlsanity.com/paper/1812.05271/) (2018)
- [Black-box Generation of Adversarial Text Sequences to Evade Deep Learning Classifiers](https://mlsanity.com/paper/1801.04354/) (2018)
- [BAE: BERT-based Adversarial Examples for Text Classification](https://mlsanity.com/paper/2004.01970/) (2020)
- [Holistic Evaluation of Text-To-Image Models](https://mlsanity.com/paper/2311.04287/) (2023)
- [ExpertPrompting: Instructing Large Language Models to be Distinguished Experts](https://mlsanity.com/paper/2305.14688/) (2023)
- [Pathologies of Neural Models Make Interpretations Difficult](https://mlsanity.com/paper/1804.07781/) (2018)
- [Text and Patterns: For Effective Chain of Thought, It Takes Two to Tango](https://mlsanity.com/paper/2209.07686/) (2022)

## Built on by (most cited first, 13 of 13)

- [A Systematic Survey of Automatic Prompt Optimization Techniques](https://mlsanity.com/paper/2502.16923/) (2025)
- [Time Awareness in Large Language Models: Benchmarking Fact Recall Across Time](https://mlsanity.com/paper/2409.13338/) (2024)
- [No Loss, No Gain: Gated Refinement and Adaptive Compression for Prompt Optimization](https://mlsanity.com/paper/2509.23387/) (2025)
- [How Open Must Language Models be to Enable Reliable Scientific Inference?](https://mlsanity.com/paper/2603.26539/) (2026)
- [On the Transformations across Reward Model, Parameter Update, and In-Context Prompt](https://mlsanity.com/paper/2406.16377/) (2024)
- [Neuron-Level Analysis of Cultural Understanding in Large Language Models](https://mlsanity.com/paper/2510.08284/) (2025)
- [Prompt Segmentation and Annotation Optimisation: Controlling LLM Behaviour via Optimised Segment-Level Annotations](https://mlsanity.com/paper/2605.14561/) (2026)
- [Persona Conditioning as an Assessor-Sensitivity Probe for LLM-Based IR Evaluation](https://mlsanity.com/paper/2608.10385/) (2026)
- [Training Prompt Matters: State-Adaptive Optimization for Robust Fine-Tuning](https://mlsanity.com/paper/2606.01967/) (2026)
- [When Large Language Models Fail in Healthcare: Evaluating Sensitivity to Prompt Variations](https://mlsanity.com/paper/2606.07237/) (2026)
- [Towards Spec Learning: Inference-Time Alignment from Preference Pairs](https://mlsanity.com/paper/2606.24004/) (2026)
- [Prompt-Robust Language Models: Which Training Strategies Work?](https://mlsanity.com/paper/2609.01217/) (2026)
- [STEVE: Stabilizing Textual Gradient-Based Prompt Optimization via Error-Driven Refinement and Regularized Verification](https://mlsanity.com/paper/2609.23716/) (2026)

## Abstract (arXiv)

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.