A token stream that preserves token identities. Say you have a token stream of [t0, t1] and add a new token t2 between t0 and t1 to get [t0, t2, t1]. What you want is to be able to identify t0 and t1 in the new stream as being the same tokens as in the old stream. If you simply re-lex to get new tokens, that won't happen, and if you use character offsets as your token identities, t1 in the new and old stream will have different identities.

Incremental lexing is pretty easy: just convert the tokens around the damage back into text, re-lex that text, and then work from front and back of the new partial stream to replace new tokens with old existing tokens if their lexical categories match (e.g. an old identifier's text can be updated with a new identifier's contents, but that is ok because parsing only depends on the fact that the token is an identifier). You might not win any performance awards, but those reused old tokens make very good keys into various data structures for incremental parsing, incremental type checking, and even incremental re-execution (if you are into live programming).