UC Santa Barbara

Modern workloads increasingly rely on combinatorial optimization and large-scale neural generation, yet their performance is often limited less by arithmetic than by memory movement, energy cost, and the difficulty of exploring large discrete state spaces. This dissertation advances stochastic sampling as a hardware-aware computing principle, using controlled stochasticity to replace portions of dense deterministic computation with sparse, scalable alternatives. First, the dissertation develops noise-augmented chaotic bit networks for Ising machine optimization and sampling. Chaotic bits use deterministic billiard-ball dynamics to generate binary spin states, providing a chaotic analogue of probabilistic bits. Chaotic bit networks reproduce key sampling phenomena, including agreement with the quantum Boltzmann law in a one-dimensional transverse-field Ising model and critical dynamics in classical Ising and spin-glass systems. The dissertation further introduces a hybrid chaotic-probabilistic adaptive parallel tempering algorithm, improving performance on spin-glass optimization and semiprime factorization while retaining the asynchronous, massively parallel structure that motivates specialized Ising machine hardware. Building on this sampling perspective, the dissertation addresses the memory bandwidth bottlenecks of transformer inference. In long-context autoregressive decoding, repeatedly streaming the key-value cache often dominates execution time. To address this, the dissertation introduces Stochastic Additive No-mulT Attention (SANTA), which samples value rows from the post-softmax attention distribution and aggregates them using sparse gather-and-add operations. SANTA provides an unbiased estimator of the dense post-softmax value aggregation, reducing value-cache access while removing value-stage multiplications. Variance-reduced sampling and custom GPU kernels yield practical long-context acceleration, including up to 1.5x kernel-level attention speedup and up to 1.25x end-to-end decode-latency speedup for Llama-3.1-8B-Instruct while preserving accuracy on reasoning and long-context benchmarks. A complementary Bernoulli score-stage estimator suggests a path toward sparse key access. Finally, the dissertation extends this framework to transformer feedforward networks, demonstrating how stochastic activations can dynamically induce sparsity that may be exploitable by sparse down-projection kernels. Collectively, these contributions establish stochastic sampling as a practical route toward hardware-efficient inference and optimization, from chaotic Ising machines to sparse transformer inference.