Techniques related to entropy coding with look-up-table based probability updating for video coding including setting a search range for candidate probabilities. This also involves selecting one of the candidate probabilities of the look-up table to update a previous probability for coding of a symbol, and selecting based on, at least in part, the bit-cost associated with updating the previous probability with at least one of the candidate probabilities.