Implementations relate to improving instruction following capabilities of large language models (LLMs) using instruction decomposition, self-evaluation, and optionally progressive refinement. Processor(s) of a system can: obtain natural language (NL) based input, generate a plurality of candidate responses and evaluate the candidate responses based on instructions included in the NL based input, using an LLM, and progressively refine the candidate responses until it is determined that one or more termination criteria are satisfied. In some implementations, the NL based input can be received from a client device. In these implementations, a given candidate response that is progressively refined can be rendered for presentation at the client device and responsive to the NL base input. In additional or alternative implementations, the NL based input can be obtained from database(s). In these implementations, a given candidate response that is progressively refined can be utilized in fine-tuning of the LLM.