Bring back usage of cached labels

Fixes #565 and replaces #566