The visibility map itself is already an example of compression. If visibility information were randomly distributed among tuples, the visibility map would be nearly useless.
I believe it is very difficult to make visibility map update friendly without compromising durability. But such a functionality is very much wanted in PG still.
