The disclosed embodiments provide a remembered set implementation for use during an incremental garbage collection, wherein the implementation includes a trie that can be dynamically coarsened to conserve memory. During operation, responsive to storing a reference into a location in a referenced memory area during the execution of a software program, the system finds, within a trie that serves as a remembered set for the referenced memory area, a particular entry that corresponds to a particular address range that covers the location. The system then marks the particular entry to indicate that the particular address range should be processed during a garbage collection. Based on a policy, the system then coarsens a particular subtree of the trie in which the particular entry is stored. Next, during the garbage collection, the system processes a particular larger address range when a root entry of the particular subtree is visited.