ترجمه فارسی مقاله اتصال بدون ارتباطات و رمزگشایی سوداگرانه پیش نویس

چکیده

Suppose Alice has a distribution $P$ and Bob has a distribution $Q$. Alice wants to generate a sample $a\sim P$ and Bob a sample $b \sim Q$ such that $a = b$ with has as high of probability as possible. It is well-known that, by sampling from an optimal coupling between the distributions, Alice and Bob can achieve $Pr[a = b] = 1 – D_{TV}(P,Q)$, where $D_{TV}(P,Q)$ is the total variation distance. What if Alice and Bob must solve this same problem without communicating at all? Perhaps surprisingly, with access to public randomness, they can still achieve $Pr[a=b] \geq \frac{1-D_{TV}(P,Q)}{1+D_{TV}(P,Q)} \geq 1-2D_{TV}(P,Q)$. In fact, this bound can be obtained using a simple protocol based on the Weighted MinHash algorithm. In this work, we explore the communication-free coupling problem in greater depth. First, we show that an equally simple protocol based on Gumbel sampling matches the worst-case guarantees of the Weighted MinHash approach, but tends to perform better in practice. Conversely, we prove that both approaches are actually sharp: no communication-free protocol can achieve $Pr[a=b]>\frac{1-D_{TV}(P,Q)}{1+D_{TV}(P,Q)}$ in the worst-case. Finally, we prove that, for distributions over $n$ items, there exists a scheme that uses just $O(\log(n/ε))$ bits of communication to achieve $Pr[a = b] = 1 – D_{TV}(P,Q) – ε$, i.e. to essentially match optimal coupling. Beyond our theoretical results, we demonstrate an application of communication-free coupling to speculative decoding, a recent method for accelerating autoregressive large language models [Leviathan, Kalman, Matias, ICML 2023]. We show that communication-free protocols yield a variant of speculative decoding that we call Drafter-Invariant Speculative Decoding, which has the desirable property that the output of the method is fixed given a fixed random seed, regardless of what drafter is used for speculation.

چکیده به فارسی (ترجمه ماشینی)

فرض کنید آلیس دارای توزیع P $ $ و باب توزیع $ q $ است.آلیس می خواهد یک نمونه $ a \ sim p $ و bob یک نمونه $ b \ sim q $ تولید کند به گونه ای که $ a = b $ با احتمال زیاد باشد.کاملاً مشهور است که ، با نمونه برداری از اتصال بهینه بین توزیع ها ، آلیس و باب می توانند به $ pr [a = b] = 1 – d_ {tv} (p ، q) $ ، که در آن $ d_ {tv ((تلویزیون $) (p ، q) $ فاصله کل تغییر است.چه می شود اگر آلیس و باب بدون برقراری ارتباط اصلاً همین مشکل را حل کنند؟شاید با کمال تعجب ، با دسترسی به تصادفی عمومی ، آنها هنوز هم می توانند به $ pr [a = b] \ geq \ frac {1-d_ {tv (p ، q)} {1+d_ {tv (p ، q)} دست پیدا کنند.\ GEQ 1-2D_ {TV} (P ، Q) $.در حقیقت ، این محدوده را می توان با استفاده از یک پروتکل ساده بر اساس الگوریتم وزنه بردار Minheash بدست آورد.در این کار ، ما مشکل اتصال بدون ارتباط را در عمق بیشتر بررسی می کنیم.اول ، ما نشان می دهیم که یک پروتکل به همان اندازه ساده مبتنی بر نمونه گیری Gumbel با ضمانت های بدترین حالت از رویکرد وزنی Minhash مطابقت دارد ، اما تمایل دارد در عمل عملکرد بهتری داشته باشد.در مقابل ، ما ثابت می کنیم که هر دو رویکرد در واقع تیز هستند: هیچ پروتکل بدون ارتباطات نمی تواند به $ pr [a = b]> \ frac {1-d_ {tv (p ، q)} {1+d_ {tv (p (p) دست یابد.، س)} $ در بدترین حالت.سرانجام ، ما ثابت می کنیم که ، برای توزیع بیش از موارد $ n $ ، طرحی وجود دارد که فقط از $ o (\ log (n/ε)) استفاده می کند تا بیت ارتباطات برای دستیابی به $ pr [a = b] = 1 – d_ {تلویزیون} (p ، q) – ε $ ، یعنی برای مطابقت با جفت بهینه.فراتر از نتایج نظری ما ، ما یک کاربرد اتصال بدون ارتباطات را به رمزگشایی سوداگرانه نشان می دهیم ، روشی اخیر برای تسریع در مدل های بزرگ زبان بزرگ [Leviathan ، Kalman ، Matias ، ICML 2023].ما نشان می دهیم که پروتکل های بدون ارتباطات نوعی از رمزگشایی سوداگرانه را به دست می آورند که ما آن را رمزگشایی سوداگرانه Drafter-Invarian می نامیم ، که دارای خاصیت مطلوبی است که خروجی این روش با توجه به آنچه Drafter برای حدس و گمان استفاده می شود ، یک بذر تصادفی ثابت ثابت می کند.