I consider using an index to be "cheating" - or rather, my intended use-case is decompression of a stream that you've never seen before, which was generated by

I consider using an index to be "cheating" - or rather, my intended use-case is decompression of a stream that you've never seen before, which was generated by a "dumb" compressor. That said, the approach I intend to take is similar. The idea is that one thread is dedicated to "looking ahead", parsing as fast as it can (or even jumping far ahead and using heuristics to re-sync the parse state. There will be false-positives but you can verify them later), building an index but not actually doing decompression, while secondary threads are spawned to do decompression from the identified block start points. The hard part is dealing with missing LZ references to data that hasn't yet been decompressed. Worst-case performance will be abysmal, but I think on most real-world data, you'll be able to beat a serial decompressor if you can throw enough threads at it.