Lithium'll fail on anything where you need to make correlated deletions, true. But you'd have similar issues with eg input that contains sizes, pointers, checksums...which aren't going to work with a generic strategy.

As to speed...well the kind of problem I was using it on was reducing an excessive dataset that was used by the entire test suite of an app; so each iteration was a complete test run of a minute or two. I was under no illusions that this was going to be fast, so I left the script to do its thing and came back to check on it after lunch. In terms of time I didn't have to waste hacking that data myself, it was a win.