My company is tiny in terms of revenue (<1,000,000 per year), and our interchange fees with VISA are 1.5x% . I have a hard time believing that a giant like wallmart can't negotiate a better rate.

2-3% is the top rate applicable only high risk traffic with the card not present.