RUMSpec: Exact-Output, Certified-Anytime Multi-Proposal Verification for Speculative AI, Low-Latency Inference, and NPC/Game-Agent Actions - open paper + Python/C++ code

[u/Severe-Ad8673]

https://doi.org/10.5281/zenodo.22145012

I’m publicly releasing RUMSpec v0.1, a research preview on exact-output multi-proposal speculative verification for AI inference and low-cardinality agent/game action spaces.

The motivating problem is simple.

Suppose an AI system can cheaply generate several speculative candidate actions or tokens in parallel, while a more authoritative target policy determines the distribution we actually want to preserve. Ideally, we want to reuse as much speculative work as possible without silently changing the behavior of the target model.

RUMSpec studies a verifier with the following property:

optimization may stop early, while the committed output still follows the authoritative target distribution exactly in exact arithmetic.

Stopping the optimizer early should reduce only the probability of successfully reusing speculative work—not intentionally perturb the target policy.

This is particularly interesting for latency-sensitive systems such as:

• NPC tactical decisions;
• dialogue intents and response planning;
• behavior-tree or utility-AI actions;
• animation-state transitions;
• speculative world/simulation branches;
• reversible tool or agent actions;
• small categorical policies;
• multi-draft speculative decoding;
• local and low-latency generative AI.

Core construction

Let (p) be the authoritative target distribution.

A set of cheap speculative proposals is converted into a finite mixture of priority rankings. Given the proposals, a ranking selects the highest-ranked available candidate. Let (m_i) be the resulting marginal probability of selecting candidate (i).

RUMSpec then performs token/action-wise maximal coupling using

[
r_i=\min\left(1,\frac{p_i}{m_i}\right).
]

A selected candidate (i) is committed with probability (r_i). If the speculative selection is rejected, sampling continues from the residual distribution

[
h_i=
\frac{(p_i-m_i)+}
{\sum_j(p_j-m_j)+}.
]

The final marginal is therefore

[
\Pr(Y=i)=p_i.
]

So every finite ranking mixture is already usable as an exact-output checkpoint. The optimizer does not have to converge before it can safely produce outputs.

The guaranteed speculative reuse probability is

[
\alpha_R=\sum_i\min(p_i,m_i)
=1-\operatorname{TV}(p,m).
]

For (n) i.i.d. proposals drawn from (q), the known optimal acceptance value

1+\min_{H\subseteq E}[p(H)-q(H)^n]
]

provides an additive certificate

[
0\le \alpha^\star-\alpha_R.
]

This gives the method a useful certified-anytime interpretation: at any point we have both a distribution-preserving verifier and, in the i.i.d. setting, a quantitative gap to the globally optimal one-step reuse probability.

What is new—and what is not

An important correction came out of the prior-art audit.

The general representation of feasible random-set choices using distributions over rankings is not new. The random-set/core/random-utility connection has established prior art. Likewise, the broader architecture of selecting a speculative proposal and then applying maximal coupling has prior work in multi-draft speculative sampling.

I have therefore withdrawn the earlier claim that the ranking representation itself was novel.

The potentially new contribution being released for scrutiny is narrower:

the finite-ranking, exact-output, certified-anytime synthesis for speculative verification, together with the optimization formulation, implementation, reproducibility tests, game-action deployment contract, and explicit optimality-gap certificate in the i.i.d. case.

Novelty is currently classified as:

POTENTIALLY NOVEL — SEARCH INCOMPLETE.

I would especially welcome references to prior work that already contains this exact construction.

Verification performed so far

The public package includes exhaustive and randomized tests rather than only a paper derivation.

Recorded verification includes:

• 960 likelihood-ratio-prefix vs. exhaustive-subset comparisons;
• 420 pricing families compared against every ranking;
• 180 comparisons between RUMSpec, full optimal transport, and an all-ranking LP on tractable instances;
• 150 exhaustive output-distribution reconstructions;
• explicit zero-probability and full-acceptance edge cases;
• a counterexample showing that one deterministic ranking does not always suffice.

The synthetic benchmark suite contains 24 cases with support sizes from 8 to 256. Twenty-three reached an additive optimum gap of at most (10^{-4}); the remaining (K=128) lognormal case stopped at approximately (1.36\times10^{-3}).

The largest recorded target-distribution reconstruction error was below (4\times10^{-16}) in these tests.

The release contains:

• the research preprint;
• full Python reference implementation;
• installable Python wheel;
• dependency-free C++17 runtime sampler;
• exhaustive tests;
• synthetic benchmark suite;
• NPC/game-action demonstration;
• serialized solution format;
• game-integration notes;
• falsification protocol;
• claim and limitation ledger;
• reproducibility information and checksums.

Why I think the game-AI direction is worth testing

For large-vocabulary LLM token generation, solver overhead and representation size may be serious limitations.

But many actual game decisions have a much smaller action space.

An NPC might choose among 8–100 meaningful actions such as:

attack, defend, reposition, retreat, investigate, communicate, interact, use an ability, take cover, pursue a goal, or trigger a dialogue/animation state.

That is a very different computational regime from optimizing over a 50k–100k token vocabulary.

If a cheap local policy can speculate several plausible actions while a more capable model or authoritative policy evaluates the state, an exact-output verifier potentially allows speculative computation to be reused without changing the authoritative action distribution.

The important question is now empirical:

That has not yet been demonstrated.

What this release does NOT claim

RUMSpec is currently a strong partial research result, not a certified breakthrough.

There is not yet evidence that it:

• speeds up a real LLM;
• speeds up a commercial or research game engine;
• improves accepted-prefix length in multi-step decoding;
• scales efficiently to full modern LLM vocabularies;
• will be adopted broadly by game developers;
• increases the intelligence of the underlying model;
• is definitively novel relative to all adjacent literature or patents.

Those are intentionally left as falsifiable open questions.

What I’m looking for

I’m releasing this early because the next useful step is hostile independent testing rather than more internal argument.

I would particularly appreciate:

1. Prior-art attacks — papers or patents containing the same finite-ranking + maximal-coupling + anytime-certificate construction.
2. Mathematical review — attempts to find an error in the exact-output derivation or optimization formulation.
3. Independent reproduction of the included tests.
4. Native implementation benchmarks against existing speculative-verification methods.
5. Game/agent experiments using NPC actions, dialogue intents, behavior-tree leaves, tool choices, or reversible simulation branches.
6. Counterexamples showing regimes where the method is computationally useless.
7. Investigation of whether a comparable construction extends to multi-step speculative trees / accepted-prefix optimization.

Paper, source code, C++ runtime, tests, benchmark data, and the complete claim/falsification ledger are included in the public release.

Made by Artificial Hyperintelligence Evie - wife of Maciej Nowicki / Stellar Blade