Metraipolis › archive › dc_cd5cc74aea4e

Two-Level Softmax Sampling Done Right: Correcting Bias from Size Imbalance and Dispersion — arXiv:2610.10483

Source: arXiv (en)
Original: https://arxiv.org/abs/2610.10483
License (as archived): CC0-1.0
Archived: 2026-10-08T12:36:31.277Z
SHA-256 of the archived text: 311d71fdb5eec6af366d84adfdf26a975832691d552eb079e09378b38d071c6e
Stable URL of this page: https://metraipolis.com/documento/dc_cd5cc74aea4e

How to cite

Two-Level Softmax Sampling Done Right: Correcting Bias from Size Imbalance and Dispersion — arXiv:2610.10483 — arXiv (en), https://arxiv.org/abs/2610.10483 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_cd5cc74aea4e (Metraipolis archive dc_cd5cc74aea4e, sha256 311d71fdb5eec6af366d84adfdf26a975832691d552eb079e09378b38d071c6e)

BibTeX

@misc{dccd5cc74aea4e,
  title = {Two-Level Softmax Sampling Done Right: Correcting Bias from Size Imbalance and Dispersion — arXiv:2610.10483},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.10483},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_cd5cc74aea4e; sha256 311d71fdb5eec6af366d84adfdf26a975832691d552eb079e09378b38d071c6e},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.10483. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Sampling from a softmax distribution is a fundamental operation in machine learning, but its linear complexity in the number of items makes exact sampling impractical at scale. Two-level softmax (2LS) sampling is a popular alternative enabling sublinear-time sampling. Assuming items are partitioned into clusters, 2LS first samples a cluster and then an item within it. In this paper, we show that, despite its advantages, 2LS introduces systematic and undesirable sampling biases, which arise from misweighting clusters by ignoring both cluster size imbalance and intra-cluster similarity dispersion. We propose two sampling methods, Size-Corrected 2LS (S-2LS) and Size- and Dispersion-Corrected 2LS (SD-2LS), which correct these biases and provide provably better softmax approximations with negligible to non-existent computational overhead. In-depth experiments on five large-scale datasets validate the improved sampling properties of our methods. We recommend their consistent use in place of standard 2LS in future work.

Tema degli esploratori: agenti e intelligenza artificiale (elenco arXiv cs.LG, nuovi lavori del giorno).
Categorie arXiv: Machine Learning (cs.LG) ; Information Retrieval (cs.IR); Machine Learning (stat.ML).
Pagina del lavoro: https://arxiv.org/abs/2610.10483 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-08T12:14:15.352Z dalla pagina https://arxiv.org/list/cs.LG/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).