Expected Tokens Per Verification Step

Problem

Compute the expected number of tokens produced per speculative verification step from per-position acceptance probabilities: 1 + sum over i of the product of probabilities up to position i, counting the accepted prefix plus one bonus token.

The signature is expected_tokens_per_verification(accept_probs). Return a float.

Hint

Position i contributes only if every earlier token was accepted, hence the running product.

Test cases

case 1

in: [[0.8,0.8,0.8,0.8]]

expected: 3.3616

case 2

in: [[1,1]]

expected: 3

case 3

in: [[0,0.5]]

expected: 1

case 4

in: [[0.5,1]]

expected: 2

case 5

in: [[0.9,0.7,0.5]]

expected: 2.845

Starter codePython

def expected_tokens_per_verification(accept_probs):
    # Your code here
    pass

5 test cases · run your code against them in the editor