Implement Top-p (Nucleus) Sampling in NumPy

Given a language model’s next-token probability distribution, implement top-p (nucleus) sampling. Task Implement top_p_sample(probs, p, rng) to sample a token id from probs using the following rule: Sort tokens by probability in descending order. Take the smallest prefix whose cumulative probability sum is >= p (where 0 < p <= 1). Renormalize probabilities within this prefix to sum to 1. Use the random generator rng (e.g., numpy.random.Generator) to sample and return a token index (token id). Input probs: 1D array of length V, each entry >= 0, and sum(probs) = 1. p: float nucleus threshold, 0 < p <= 1. rng: RNG object used for sampling. Output An integer token_id. Constraints / Edge cases V >= 1. Ties can be broken arbitrarily, but the chosen set must be the minimal prefix with cumulative sum >= p. Must be implemented with NumPy. Example test expectations (illustrative) probs=[0.4,0.3,0.2,0.1], p=0.5 → output ∈ {0,1} probs=[0.9,0.05,0.03,0.02], p=0.9 → output ∈ {0} probs=[0.25,0.25,0.25,0.25], p=0.51 → output from a 3-token set probs=[1.0], p=1.0 → 0 probs=[0.6,0.4], p=1.0 → output ∈ {0,1} Example Input probs=[0.4,0.3,0.2,0.1], p=0.5 Output token_id in {0,1}