progress

~/problems / AI infrastructure

Stop sequences in a streamed reply

On a phone? Coding is easier on a laptop: email this problem to yourself . Meanwhile: quiz this topic or fight a boss.

medium assessment 2 levels ~40 min Microsoft

Level 1 Hold back what might be a stop

A chat model streams its reply to the user a few characters at a time. The request can name a stop sequence: a string that ends the reply. When the model writes it, the user must see everything before it and nothing from the stop sequence on. The text arrives in chunks, and a stop sequence can be split across two or more chunks, so you can't always show a chunk the moment it arrives.

Build StopFilter(stops). For this level stops is a list holding exactly one non-empty string, the stop sequence.

  • feed(chunk: str) -> str: the next piece of model output arrives. Return the text that is now safe to show (often "").
  • finish() -> str: the stream has ended. Return the text you are still holding back. No calls come after finish().
  • stopped() -> bool: has the stop sequence appeared?

Call everything fed so far text. The rules:

  • Stopping. As soon as the stop sequence occurs in text, the reply ends right before its first occurrence. If it starts at index i, everything you have returned, over all calls together, is exactly text[:i]. From then on stopped() is True, and feed and finish return "".
  • Holding back. Until then, show text as early as possible, but never show a character that might still turn out to be part of the stop sequence. Precisely: after each feed, everything you have returned is text without its longest suffix that is a prefix of the stop sequence. That suffix is held back until more text decides it.
f = StopFilter(["</s>"])
f.feed("Hello <")     # "Hello "     ("<" might start "</s>")
f.feed("b>world")     # "<b>world"   (it didn't)
f.feed(" bye</")      # " bye"       ("</" is held back)
f.feed("s>ignored")   # ""           (the stop sequence is complete: the reply is "Hello <b>world bye")
f.stopped()           # True
f.feed("more")        # ""
f.finish()            # ""

f = StopFilter(["END"])
f.feed("THE EN")      # "THE "
f.stopped()           # False
f.finish()            # "EN"       (the stream ended, so "EN" was just text)

Constraints: the stop sequence has 1 to 50 characters. The stream is ASCII text of up to 10^6 characters over up to 2 * 10^5 calls. A chunk may be empty.

⭐ Bonus: a speed test feeds 200,000 one-character chunks. It earns a star if a feed doesn't redo work for text that was already shown.

Level 2 unlocks when level 1 passes.

Topic: AI infrastructure. The plumbing around models: request batching, streaming responses, prompt caches, sampling, token limits and eval harnesses.

Read the visual guide
0:00
Ctrl ' run · Ctrl ↵ submit
esc