Real-time character animators generate motion a few frames at a time. A typical system samples one continuation from a learned model, commits it, and moves on. When the motion has to satisfy several requirements at once, such as no foot sliding, low jerk, staying clear of an obstacle, and tracking a steering command, the usual fix is to draw several samples and keep the best. This proposal argues that "keep the best whole sample" wastes most of what was computed. Across a batch of rollouts, one may have clean footwork in the first half and a collision in the second, while another has the opposite. If the requirements are mostly local in time, the right move is to cut rollouts at compatible poses and splice their good pieces together. We call this splice search. It is crossover, the recombination operator of genetic algorithms, applied to a pool of generated rollouts and carried out exactly by a small heuristic search under a frame-time budget.
The opportunity comes from evolutionary computation theory. That literature has proved that recombining complementary partial solutions can be exponentially faster than improving one candidate at a time. The clearest case is A Many-Objective Problem Where Crossover Is Provably Indispensable, which shows NSGA-III, a standard many-objective genetic algorithm, needs $O(n^3/(1-p_c)+p_c)$ generations with crossover and $\Omega(n^{\Omega(n)})$ without it. Those results live on synthetic bitstrings. Motion generation offers a natural place to test whether the "building block" story survives contact with real data. The building blocks are time windows of motion, the parents are batched model rollouts, and the selection problem has three to five conflicting objectives.
Core Claim
Our claim is narrow and testable. When motion quality objectives decompose over time windows, recombining a pool of $N$ rollouts makes the number of samples needed for a fully acceptable motion grow roughly logarithmically with horizon length. Picking the best whole rollout makes it grow exponentially. Recombination therefore beats best-of-N at equal model compute, which is the only compute that matters at 30 frames per second.
The argument is a one-line transplant of the Royal Road reasoning. Suppose a horizon is split into $W$ windows, each rollout's window independently meets all constraints with probability $p$, and a splice between two rollouts at a window boundary is kinematically compatible with probability $q$. Then the chance of getting at least one fully acceptable motion is
$$P_{\text{best-of-}N} = 1-(1-p^W)^N, \qquad P_{\text{splice}} \approx \big(1-(1-p)^N\big)^W \cdot q_{\text{eff}}^{\,W-1},$$
where $q_{\text{eff}}$ is the probability that some compatible splice exists among the good candidates at a boundary. It rises toward 1 as $N$ grows because there are about $N^2$ candidate pairs per boundary. The first expression needs $N \sim p^{-W}$. The second needs only $N \sim \log W / p$. The approximation fails in two ways that we will measure directly rather than assume away: per-window quality may be correlated within a rollout, and splice compatibility may be rare. The first failure would shrink the gain. The second would erase it.
Research Program
We first build the splice lattice. At each control tick, a pretrained generator produces $N$ rollouts over a horizon of $W$ windows in one batched forward pass. We use two generators: T2M-GPT's discrete token model for text-conditioned motion, and A-MDM's autoregressive diffusion model for interactive steering. A node in the lattice is a pair (window $w$, rollout $i$). An edge connects $(w,i)$ to $(w+1,j)$ only when the decoded pose and joint velocities at the boundary are within a tolerance. This constraint carries a lesson from the constrained-crossover literature (Aneta Neumann et al.; Analysis of the (1+1) EA on LeadingOnes with Constraints): recombining two feasible parents often yields an infeasible child, so feasibility has to be built into the operator rather than repaired afterward. Each node carries a cost vector of per-window foot sliding, jerk, obstacle penetration and tracking error. Each edge carries a splice discontinuity cost.
Second, we search the lattice exactly with multi-objective A*, the best-first search that expands nodes in order of cost so far plus an estimated cost-to-go. The cost-to-go estimate is factored: for each remaining window, take the componentwise minimum over all candidates and sum these vectors. This bound ignores nonnegative splice costs, so it never overestimates and it is consistent. That follows the factored-projection construction of Approximate Factoring for A* Search. By the results in The Optimality of A* Revisited, a consistent bound means no admissible algorithm with the same information expands fewer nodes. That paper proves this for scalar costs; we rely on it only for the scalarized variant and treat the vector case as an empirical question.
We are explicit about one point. For small pools, around $N=16$ and $W=4$, exhaustive dynamic programming over the lattice is cheap, and A* earns its place only as $N$ and $W$ grow. Part of the program is to find that crossover point. The search returns the set of non-dominated spliced motions, those that no other splice beats on every objective. Text or style alignment is a property of the whole sequence and does not decompose over windows, so it is applied only as a final reranking over this set.
Third, we control the size of that set. Under a latency budget, the non-dominated set must be capped. Many-objective theory makes a sharp prediction about how the cap should be chosen. Crowding distance, the default diversity rule in NSGA-II, favors extreme points once there are three or more objectives and starves the middle of the trade-off surface. Balanced tie-breaking (Speeding Up the NSGA-II with a Simple Tie-Breaking Rule) and reference-point association (A Mathematical Runtime Analysis of the Non-dominated Sorting Genetic Algorithm III (NSGA-III)) avoid this. We keep a capped trade-off set so that when the controller's priorities change mid-stream, for example when an obstacle suddenly appears, the next tick can pick a different trade-off without regenerating. We will test whether the crowding-distance pathology appears in this small, non-asymptotic setting.
Fourth, we smooth the splice seams. Token splices are decoded with a rectified-flow decoder in the style of DisCoRD, which maps discrete motion tokens to continuous motion and was shown to reduce jerk relative to feed-forward decoders. The search commits the first window, and the next tick conditions the generator on the committed spliced history. The generator therefore always sees a coherent past, which limits the mismatch caused by splicing segments that were generated under different prefixes.
Baselines
The naive reference point is a single rollout per tick: greedy decoding of T2M-GPT on HumanML3D, and single-sample A-MDM on LaFAN1 and 100STYLE steering tasks. Its cost is one rollout, which defines the floor for both quality and latency.
Best-of-N whole-rollout reranking is the most direct competitor, because it spends exactly the same generator compute and differs only in throwing away partial successes. We run it with the identical $N$ rollouts the splice search sees, ranked once by a tuned weighted sum of objectives and once by non-dominated selection with the same final text reranker. Splice search beats it if it reaches the same constraint-satisfaction rate with at least 2× fewer rollouts, or a higher rate at equal $N$, across horizons. It must do so without degrading FID by more than the seed-to-seed spread.
Masked window regeneration is the strongest existing method. Following MoMask, which fills token masks iteratively with a bidirectional transformer, we identify windows that violate constraints and re-mask and regenerate them conditioned on the context on both sides. MoMask reports an FID of 0.045 on HumanML3D, against 0.116 for T2M-GPT reported in the T2M-GPT paper. MoMask's paper also quotes a T2M-GPT FID of 0.141. For the temporally local constraint metrics we target, such as foot sliding, penetration and tracking error under a frame budget, we found no reported result on Lacuna for any of these methods, so all of them will be measured under one protocol. For fairness, regeneration receives the same wall-clock budget per tick, measured on the same GPU, with its number of refinement passes tuned on a held-out split using the same tuning budget as our splice tolerance. Splice search beats it if it matches or exceeds regeneration's constraint-satisfaction rate at lower latency, since it reuses computed segments instead of running extra passes.
For latency context, we report MotionLCM, which generates motion in one to four steps at 30 ms per sentence with FID 0.467, but has no test-time search.
Three ablations isolate the ingredients. The first splices at random boundaries with no compatibility edges, to test whether compatibility-constrained recombination rather than mere cutting carries the gain. The second replaces the Pareto search with a scalarized single-objective search, to test whether keeping trade-offs matters once priorities change. The third compares crowding distance against balanced and reference-point capping of the trade-off set.
Why not just…?
Why not just draw more samples and keep the best? This is the baseline the scaling argument is aimed at. Its required pool grows like $p^{-W}$, so it should fall behind as horizons lengthen. The prediction is falsifiable. We will measure the within-rollout correlation of window quality, and if windows succeed or fail together, best-of-N will match splice search and we will report that.
Why not just regenerate the bad windows with a masked model? This is the real threat. Regeneration conditions properly on both neighbors, whereas splicing reuses segments generated under a different prefix. If regeneration matches splice search at equal wall-clock time, the contribution shrinks to the diagnostic analysis and to cheap trade-off switching. The equal-latency comparison settles it. A plausible outcome is a hybrid in which splicing proposes and a single regeneration pass repairs seams, and we would test that hybrid if both methods prove competitive.
Why not just fold the objectives into a weighted training loss? MDM shows that foot-contact losses reduce sliding, but fixed weights are set before deployment. Interactive constraints such as a sudden obstacle arrive at test time and change which trade-off is correct. The priority-switch experiment below measures whether retraining-free switching from a stored trade-off set beats a fixed-weight model.
Why not just run beam search or dynamic programming? For small lattices, exact dynamic programming is our method. A matters only as pool size grows, and we will report the crossover point honestly rather than claim A is always needed.
Proposed Experiments
The decisive experiment sweeps the horizon length $W$ and the pool size $N$ on HumanML3D, using text prompts plus synthetic foot-contact and obstacle constraints, and on LaFAN1 and 100STYLE steering with A-MDM. For each method, we plot the $N$ required to reach 90% full-constraint satisfaction against $W$. The scaling claim predicts that best-of-N curves rise exponentially while splice-search curves rise roughly logarithmically. We overlay the measured within-rollout correlation of window quality and the measured compatibility rate, so that any failure is attributed to one of the two named causes.
We separately check that splicing does not damage realism. We report FID and R-precision on HumanML3D and KIT-ML, and DisCoRD's symmetric jerk percentage error at seams compared with unspliced frames.
The priority-switch test injects obstacles mid-stream and compares the stored trade-off set against regeneration and against fixed scalar weights, measuring both latency and collisions.
Latency is profiled per tick against the frame budget, with A-MDM's reported ~21 ms per frame as the reference. We also profile how much of that time goes to dominance checking, which Revisiting Dominance Pruning in Decoupled Search reports can reach 60% of runtime in planning.
Finally, the capping ablation tests whether crowding distance loses middle trade-offs at three or more objectives, as the asymptotic theory predicts, in a regime of tens of candidates where that theory does not formally apply.
References
- A Many-Objective Problem Where Crossover Is Provably Indispensable
- Analysis of (1+1) EA on LeadingOnes with Constraints
- Approximate Factoring for A* Search
- The Optimality of A* Revisited
- Speeding Up the NSGA-II with a Simple Tie-Breaking Rule
- A Mathematical Runtime Analysis of the Non-dominated Sorting Genetic Algorithm III (NSGA-III)
- DisCoRD: Discrete Tokens to Continuous Motion via Rectified Flow Decoding
- Generating Human Motion from Textual Descriptions with Discrete Representations
- Interactive Character Control with Auto-Regressive Motion Diffusion Models
- MoMask: Generative Masked Modeling of 3D Human Motions
- MotionLCM: Real-Time Controllable Motion Generation via Latent Consistency Model
- Human Motion Diffusion Model
- Revisiting Dominance Pruning in Decoupled Search