Tag bits are left over bits you need to store with the block of data in order to differentiate that block from other blocks of data that could be stored in the same place.  You will always need tag bits with each block.

**Example: **Continuing from where the previous examples left off (click the links in the answer), we are given an 8-way set-associative cache, with 4 byte blocks, 1 kb total data, and addresses of 32 bits.

tag bits = 32 – # index bits – # offset bits = 32 – 5 – 2 = 25 tag bits for each block