CBR control strategies provide constant or relatively constant bitrate output with variable quality. The control strategies include various techniques and tools, which can be used in combination or independently. For example, an audio encoder uses a trellis in two-pass or delayed-decision CBR encoding. The trellis nodes are states derived by quantizing buffer fullness values. The transitions between nodes of a previous stage and nodes of a current stage depend on encoding a current chunk of audio at different quality levels. When pruning the trellis, the encoder uses a cost function that considers smoothness in quality as well as quality in absolute terms. The encoder may store compressed data at different quality levels, then output the compressed data after simplification of the trellis to a suitable point. If the two-pass or delayed-decision CBR encoding fails, the encoder uses one-pass CBR encoding for the sequence or part of the sequence.