# KL-Budgeted Poisson-Race Sampling - ID: 219 - Canonical URL: https://synthcore.org/idea/219/kl-budgeted-poisson-race-sampling - API JSON: https://synthcore.org/api/idea/219.json - API Markdown: https://synthcore.org/api/idea/219.md - Verification status: mechanism_failed - Source: [arXiv:2608.26996](https://arxiv.org/abs/2608.26996) - Category: sampling - Solves: speedup, sample-efficiency, accuracy - ML areas: sampling, distillation, inference-speedup - Math tags: probability, information-theory, stochastic-processes - Ratings: usefulness 6/10; difficulty 5/10; novelty 6/10 ## Idea description Replace repeated rejection sampling from a neural proposal P with a Poisson race that selects one proposal candidate with exactly the target distribution Q. Candidate i receives a Poisson arrival time A_i and race score A_i divided by Q(X_i)/P(X_i); the smallest score wins. When Q is close to P in KL divergence, the selected index has low expected logarithmic rank, providing an adaptive compute budget instead of a fixed number of candidates. ## Mathematical statement The paper defines a P-to-Q simulator as an index I such that X_I has distribution Q when X_1,X_2,... are iid from P, with cost(I)=E[log_2 I]. Its theorem states that if D(Q||P)= 0.5 max{D(Q||P),||Q-P||_1}. Here D(Q||P)=sum_x Q(x)log_2(Q(x)/P(x)) is KL divergence and ||Q-P||_1=sum_x|Q(x)-P(x)| is total variation in unhalved L1 form. A directly implementable Poisson race draws iid proposal marks X_i~P and iid exponential increments E_i~Exp(1), forms A_i=sum_{j=1}^i E_j, and returns I=argmin_i A_i/w(X_i), where w(x)=Q(x)/P(x). The marked process for symbol x has proposal rate P(x); rescaling its clock by w(x) produces rate P(x)w(x)=Q(x), so the winning mark is Q-distributed. If w_max=max_x w(x) is known, exact scanning can stop after i when A_{i+1}/w_max >= S_min, where S_min=min_{j<=i} A_j/w(X_j), because all future arrivals are no earlier than A_{i+1}. ## Key formulas - $$\operatorname{cost}(I):=\mathbb{E}[\log_2 I]$$ - $$\mathbb{E}[\log_2 I]\le D(Q\|P)+1.45\|Q-P\|_1,\qquad \mathbb{E}[\log_2 I]\ge \frac{1}{2}\max\{D(Q\|P),\|Q-P\|_1\}$$ - $$A_i=\sum_{j=1}^{i}E_j,\quad E_j\stackrel{\mathrm{iid}}{\sim}\operatorname{Exp}(1),\quad w(x)=\frac{Q(x)}{P(x)},\quad I=\arg\min_{i\ge1}\frac{A_i}{w(X_i)}$$ - $$\text{stop at }i\text{ when }\frac{A_{i+1}}{w_{\max}}\ge S_{\min},\qquad S_{\min}=\min_{j\le i}\frac{A_j}{w(X_j)}$$ ## Implementation notes Integrate the method at an inference-time categorical sampling point, such as next-token generation or a discrete latent-variable posterior. Let a cheap proposal network produce logits l_P and an accurate target network produce logits l_Q over vocabulary size V. Compute log probabilities with log-softmax: logp and logq. Draw proposal tokens x_i~Categorical(exp(logp)), draw exponential increments e_i=-log(U_i) for U_i~Uniform(0,1), and maintain A_i=A_{i-1}+e_i. For each token compute logw=logq[x_i]-logp[x_i] and log-score=log(A_i)-logw; keep the candidate with minimum log-score. Precompute logw_max=max_x(logq[x]-logp[x]). After observing candidate i, draw or expose the next arrival A_next=A_i+Exp(1), and stop exactly when log(A_next)-logw_max >= best_log_score. Pseudocode: `A=0; best_log_score=inf; best_x=None; while True: A += Exp(1); x=sample(p); s=log(A)+logp[x]-logq[x]; if s=best_log_score: break; return best_x`. Compute the race in log space to avoid overflow. The mathematical quantities are the score, stopping rule, and exactness guarantee; estimate KL, mean log2(index), and wall-clock cost empirically. First test on a small WikiText-2 Transformer, comparing direct target sampling, ordinary rejection sampling, and Poisson-race sampling with a smaller proposal model. Measure marginal distribution error, target evaluations, candidate index, throughput, and perplexity. Success requires distribution error below 1e-3 and lower target-computation cost at matched perplexity, with mean log-index empirically below the KL-plus-total-variation upper bound. ## Verification - Status: mechanism_failed - Mechanism evidence: yes - Mechanism confirmed: no - Verdict: Built and numerically verified the finite-categorical Poisson race with the exact look-ahead stopping rule. The output marginal matches Q within Monte Carlo noise and mean log2 rank increases with KL, with a small candidate-count reduction versus rejection sampling (1.599 vs 1.604 close; 4.768 vs 4.813 moderate; 9.629 vs 9.663 farther). However, the observed close-case mean log2 rank (0.489) is above the stated KL-plus-L1 upper bound (0.124), and the pure-Python race is slower than rejection sampling; no neural inference or target-computation speedup was demonstrated. ### Mechanism check - Verdict: Built and numerically verified the finite-categorical Poisson race with the exact look-ahead stopping rule. The output marginal matches Q within Monte Carlo noise and mean log2 rank increases with KL, with a small candidate-count reduction versus rejection sampling (1.599 vs 1.604 close; 4.768 vs 4.813 moderate; 9.629 vs 9.663 farther). However, the observed close-case mean log2 rank (0.489) is above the stated KL-plus-L1 upper bound (0.124), and the pure-Python race is slower than rejection sampling; no neural inference or target-computation speedup was demonstrated. - Confidence: 8/10 - Limitations: Only a small finite categorical toy test was run; no Transformer, language-model logits, GPU implementation, batched/vectorized implementation, FLOP-matched target-network benchmark, or comparison at matched perplexity was tested. The theorem is existential, so failure of this direct race to meet its upper bound does not disprove the paper's theorem, but it limits the claimed practical conclusion here. ## Artifacts - [poisson_race_experiment.py](https://synthcore.org/code/1205/poisson_race_experiment.py) - [report.md](https://synthcore.org/code/1205/report.md) - [results.json](https://synthcore.org/code/1205/results.json) - [Download all files as ZIP](https://synthcore.org/download/1205) ## Disclaimer AI-generated research hypothesis, automatically tested. Not peer-reviewed.