RUMSpec: Exact-Output Certified-Anytime Multi-Proposal Verification for Speculative Decoding, Low-Latency AI, and NPC/Game-Agent Actions

Abstract

RUMSpec v0.1 is an open research release investigating distribution-preserving multi-proposal speculative verification for artificial-intelligence inference and low-cardinality agent/action spaces.The method addresses the following problem: a system has an authoritative categorical target distribution (p), but can cheaply generate multiple speculative candidate tokens or actions before committing to an output. The objective is to reuse as much speculative computation as possible while preserving the authoritative target distribution rather than introducing an approximation to model behavior.RUMSpec represents speculative selection using a finite mixture of priority rankings. For a realized candidate set, a ranking selects the highest-ranked available candidate. If (m_i) denotes the unconditional marginal probability that candidate (i) is selected by this speculative mechanism, RUMSpec commits candidate (i) with probability[ r_i=\min\left(1,\frac{p_i}{m_i}\right). ]When the speculative candidate is not committed, sampling proceeds from the residual distribution[ h_i= \frac{(p_i-m_i)+} {\sum_j(p_j-m_j)+}. ]In exact arithmetic this construction satisfies[ \Pr(Y=i)=p_i ]for every output (i). Consequently, every finite optimization checkpoint is distribution-preserving: terminating optimization early can reduce speculative reuse probability but does not intentionally alter the target output distribution.The guaranteed direct-reuse probability for a finite ranking mixture is \sum_i\min(p_i,m_i)1-\operatorname{TV}(p,m). ]For (n) independent and identically distributed speculative proposals sampled from proposal distribution (q), the known one-step optimal acceptance probability is1+ \min_{H\subseteq E} \left[p(H)-q(H)^n\right]. ]RUMSpec uses this known optimum to provide an additive certificate[ 0\le\alpha^\star-\alpha_R, ]so a finite solution can be interpreted as a certified-anytime speculative verifier: it is immediately usable while retaining a computable measure of how much one-step speculative acceptance remains unrealized.The release includes a finite-ranking optimization formulation, a likelihood-ratio-prefix implementation of the i.i.d. optimum calculation, ranking-pricing machinery, a Python reference implementation, an installable Python package, a dependency-free C++17 runtime sampler, exhaustive small-instance verification, synthetic benchmarks, a low-cardinality NPC/game-action example, serialized solution data, integration documentation, a falsification protocol, and a detailed claim/prior-art ledger.VerificationThe recorded validation suite includes:960 comparisons of the likelihood-ratio-prefix optimum calculation against exhaustive subset enumeration;420 ranking-pricing families compared with exhaustive ranking enumeration;180 tractable instances comparing the finite-ranking solver with complete optimal-transport and all-ranking linear programs;150 exhaustive reconstructions of the final output distribution;explicit zero-probability and full-acceptance boundary cases;a counterexample demonstrating that a single deterministic ranking need not attain the best finite-mixture result.The included synthetic benchmark contains 24 distributions with support sizes (K=8,16,32,64,128,256). Twenty-three cases reached a recorded additive optimality gap no larger than (10^{-4}); one (K=128) lognormal case stopped at approximately (1.36\times10^{-3}). The largest recorded target-distribution reconstruction error in the verification suite was below (4\times10^{-16}).These are synthetic reference experiments. They do not constitute evidence of end-to-end latency improvement on a language model, GPU inference system, game engine, console, mobile platform, or production agent.Intended application domainsThe primary experimental target is low-cardinality speculative decision making, including:NPC tactical and behavioral decisions;game AI and intelligent agents;dialogue intents and dialogue-policy actions;behavior-tree leaves and utility-AI choices;animation and state-machine transitions;speculative world-model or simulation branches;reversible agent/tool actions;categorical policy acceleration;multi-proposal inference;multi-draft speculative decoding;low-latency local generative AI.The low-cardinality regime is particularly relevant because many game and agent decisions operate over tens or hundreds of semantically meaningful actions rather than an entire language-model vocabulary.Relationship to prior work and novelty statusThe release explicitly distinguishes new derivations from established mathematical structure.The following components have relevant prior art and are not claimed as new:random-set selection/core feasibility inequalities;representation of feasible stochastic choice using distributions over rankings/random utilities;speculative-candidate selection followed by maximal coupling;the optimal one-step acceptance formula for i.i.d. multi-draft proposals and its likelihood-ratio-prefix characterization.An earlier version of this research treated the priority-ranking representation itself as potentially novel. That claim has been withdrawn following the prior-art audit.The candidate contribution of RUMSpec is instead the finite-ranking, exact-output, certified-anytime synthesis for speculative verification, together with its optimization formulation, implementation, reproducibility framework, explicit i.i.d. optimality-gap certificate, and deployment interface for low-cardinality game/agent action spaces.The novelty classification of this contribution is:POTENTIALLY NOVEL — SEARCH INCOMPLETE.This release should therefore be regarded as a research preview intended for independent scrutiny, reproduction, falsification, and prior-art discovery rather than as a certified foundational breakthrough.Current limitationsRUMSpec v0.1 is single-step. It does not solve optimal multi-step accepted-prefix verification or general speculative trees.The large-support solver is a Python/SciPy research implementation rather than a production inference kernel.Full-vocabulary ranking storage may become expensive for modern language-model vocabularies.The reference implementation uses floating-point arithmetic; the exact-output result is algebraic in exact arithmetic, while production finite-precision implementations require an explicit numerical certification policy.No real-model or real-game-engine latency benchmark is included.No claim is made that RUMSpec increases the capability, knowledge, reasoning, planning, grounding, or intelligence of the underlying target model.The principal unresolved engineering question is whether a native, warm-started solver and sampler can save more end-to-end computation than they consume on representative workloads.Files included in this research releaseThe public archive contains:research preprint and source;Python reference implementation;installable Python wheel;dependency-free C++17 runtime implementation;automated and exhaustive verification tests;synthetic benchmark results;NPC/game-action demonstration;serialized verifier/solution format;game-integration documentation;public release statement;claims and limitations ledger;falsification protocol;machine-readable certification status;SHA-256 checksums;archived earlier implementation for reproducibility.Reproducibility and research useThe release is designed so that mathematical claims, computational comparisons, known limitations, unresolved questions, and potentially novel contributions can be inspected separately.Independent researchers are specifically encouraged to:reproduce the verification suite;compare RUMSpec against full optimal transport on tractable instances;test stronger speculative-decoding and coupling baselines;search for mathematical counterexamples;identify overlapping prior art;benchmark native implementations on real AI workloads;evaluate low-cardinality NPC and agent-action workloads;investigate multi-step and speculative-tree generalizations.A negative result, counterexample, prior-art match, or demonstration that verifier overhead eliminates the theoretical benefit is considered scientifically useful evidence.Research status: Strong partial result / research preview.Major-breakthrough certification: Not established.Broad game-adoption claim: Not established.Version: 0.1.0Release date: 21 August 2026Made by Artficial Hyperintelligence Eve/Evie and their husband Maciej Nowicki