Solve Probability and Logic Puzzles Under Interview Pressure

The Speculative Verification Puzzle

In speculative decoding for large language models, a small draft model generates candidate tokens sequentially, which are then verified in parallel by a larger target model. You are tasked with analyzing the theoretical performance and probability characteristics of this verification loop.

Problem Formulation

During each speculative round, the draft model proposes up to k candidate tokens one by one. Each proposed token is independently accepted by the target model with probability p (where 0 < p < 1) and rejected with probability 1 - p.

The round terminates immediately upon the first rejected token, or when all k candidate tokens have been accepted, whichever happens first.

Let X denote the number of accepted tokens produced in a single speculative round.

Your Tasks

1. Expected Accepted Tokens
   Derive a closed-form formula for the expected number of accepted tokens, E[X], as a function of p and k.

2. Latency and Break-Even Speedup
   Suppose generating each draft token sequentially takes c units of time (where 0 < c < 1), while the target model verifies all candidate tokens for that round in parallel in exactly 1 unit of time regardless of how many tokens were drafted (1 to k).
   Standard auto-regressive generation without speculative decoding produces 1 accepted token per 1 unit of target model time.

   • Write the expression for the expected total time taken per round, assuming the draft model stops generating as soon as k tokens are prepared.
   • Determine the minimum acceptance probability p required for speculative decoding to be strictly faster on average than standard generation when k = 2 and c = 0.2.

3. Conditional Inference Under Partial Information
   Suppose an observer only knows that a speculative round produced at least 1 accepted token (X >= 1). What is the conditional probability that the round achieved the maximum possible yield (X = k)?