Question about Encoder Logic #87

JackxTong · 2024-07-20T20:28:05Z

I noticed the encode() method has extra logic with a while loop to find the lowest merge index:

    def encode(self, text):
        text_bytes = text.encode("utf-8") # raw bytes
        ids = list(text_bytes) # list of integers in range 0..255
        while len(ids) >= 2:
            stats = get_stats(ids)
            pair = min(stats, key=lambda p: self.merges.get(p, float("inf")))
            if pair not in self.merges:
                break # nothing else can be merged anymore
            idx = self.merges[pair]
            ids = merge(ids, pair, idx)
        return ids

Can we simplify it like this:

    def encode(self, text):
        tokens = text.encode("utf-8")
        tokens = list(map(int, tokens))
        for pair, index in self.merges.items():
            tokens = merge(tokens, pair, index)
        return tokens

Since merge() merges all occurrences, it seems a simple for loop suffices. Is there a reason for the more complex logic?
I have trained my tokenizer vs the basictokenizer on some text data, and achieved the exact same vocab & encoder.
Maybe I missed something. Could you clarify?

Thanks!

Update:
I made a pytest from my forked repo just to show mine is also correct:
For anyone interested to try out

202030481266 · 2024-08-07T11:55:26Z

I think it's a little bit different, but the effect should be the same (your python version should be higher than 3.7). Your implementation completely iterates over all merge items, but the original code can jump out. I think the reason the original code was written this way was to prevent the dictionary order might not be in the order it was added. Karpathy seems to mention this in the video, but the issue was fixed in py3.8.

alexandermorgan · 2024-08-07T12:24:45Z

As @202030481266 mentioned, your simpler version iterates over all of the merges made in the vocabulary. For a realistic tokenizer this is a lot of merges (~50k for GPT2, 200k for GPT4o) so at a practical scale your approach would require a lot more work and most of the merges applied would not even be in the chunk of text being processed.
But there is a little overly complex thing in Karpathy's code here. He calls get_stats inside of encode but only uses the keys from the get_stats dictionary. Since we're only using the keys here, there's no sense in going through the trouble of calculating the values (which is the point of get_stats). So instead of using get_stats(ids) it would be a lot less work to line up the consecutive pairs like this zip(ids, ids[1:]). Even if the ids list is only one element long that will still work correctly without throwing an out of range error.

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Question about Encoder Logic #87

Question about Encoder Logic #87

JackxTong commented Jul 20, 2024 •

edited

Loading

202030481266 commented Aug 7, 2024

alexandermorgan commented Aug 7, 2024

Question about Encoder Logic #87

Question about Encoder Logic #87

Comments

JackxTong commented Jul 20, 2024 • edited Loading

202030481266 commented Aug 7, 2024

alexandermorgan commented Aug 7, 2024

JackxTong commented Jul 20, 2024 •

edited

Loading