LatticeTTS: Deadline-Aware Frontier Compilation for Verifier-Guided Test-Time Scaling

Verifier-guided test-time scaling (TTS) improves the reasoning of compact models by expanding and scoring several candidate paths. Under a time budget, a candidate helps only if it is generated and verified before the deadline. Existing serving systems make each stage faster but treat the requested frontier as a fixed amount of work. Our measurements show this cost is discontinuous, since one more child can push either stage across a batch boundary and raise its latency by up to 26% while leaving the other almost unchanged. We present LatticeTTS, a serving layer that keeps every selected parent and decides only how many children to run beneath each, without retraining or changing the ranking rule. A joint service lattice records the generator, verifier, and key–value (KV) cache state of each round, and an online planner moves along a nested sequence of child counts, admitting only children whose complete cycle fits the remaining deadline. Across three model pairs, three reasoning benchmarks, and three search policies, LatticeTTS achieves a 5.75× geometric-mean end-to-end speedup, up to 18.36× higher throughput under concurrent load, and up to 16.7 percentage points higher fixed-deadline accuracy under tight budgets.