Methods, systems, and media for determining playlist title coherence and quality are provided. In some embodiments, a method for generating playlist recommendations includes: determining, using a hardware processor, a title of a playlist; generating, using the hardware processor, a byte-level representation of the title based on the title of the playlist; determining, using the hardware processor, an embedded representation of the title based on the byte-level representation; determining, using the hardware processor, a perplexity score of the title by inputting the embedded representation of the title into a trained language model, wherein the perplexity score is an output of the trained language model; and causing, using the hardware processor, a recommendation based on the perplexity score of the title to be presented.