Best strategy for running long almost fixed prompts on a large number of samples

I have a long prompt where every time only a small part of it (a few sentences) will change but the rest of it remains the same. I’m running this prompt for let’s say n samples where n could be at the scale of thousands or millions. The easy and costly way to run the GPT-4 model with the prompt is to change the prompt for every sample and send it to the model. But considering a large portion of the prompt is the same for all samples what would be the best cost-effective strategy without compromising model output accuracy? Some may say batching samples but one consideration is the accuracy of model output when you feed one sample at a time versus including lots of samples in one prompt.