Example apparatus and methods concern de-duplication reference tag reconciliation associated with garbage collection and/or reference health checking. One example method may include accessing data associated with members of a set of references to blocks of data stored by a data de-duplication system. The method may process the first data to manipulate a Bloom filter into a state from which membership in the set of references can be assessed. The method may also include accessing a block identifier identified with a member of the set of blocks of data stored by the data de-duplication system and assessing membership in the set of references for the block identifier by querying the Bloom filter with the block identifier. If the block is not referenced, as determined by querying the Bloom filter, then the method may include performing a block reclamation action on the unreferenced block.