Probing Instruction Execution Stability of Large Language Models under Semantic Paraphrase

Large Language Models (LLMs) are commonly controlled through natural-language instructions, yet equivalentprompts can yield inconsistent behavior. While prior work has largely evaluated prompt effectiveness throughtask accuracy, less attention has been paid to the stability of instruction execution under paraphrase. In thiswork, we analyze how instruction-preserving paraphrases—prompts that retain identical task semantics andconstraints—affect the reliability with which LLMs execute structured instructions. We conduct a controlled studyusing a classification task with a strict JSON output contract, evaluating multiple paraphrases across repeated runsto separate paraphrase-induced effects from stochastic variation. Our analysis distinguishes between semanticagreement (label consistency) and execution agreement (format and constraint adherence). Experiments on eightopen-source instruction-tuned models show that semantic decisions generally remain stable under paraphrasing,while structured output reliability varies substantially depending on both the paraphrase and the model. Thesefindings indicate that execution robustness is a distinct, model-dependent property not captured by accuracyalone and highlight the importance of evaluating prompt behavior under paraphrase in structured-output settings.