Thought-Level Beam Search for Reasoning

The Core Problem: Wasting Compute on Bad Reasoning Paths

Large language models solving hard math and reasoning problems benefit from extra computation at test time—but most approaches waste it badly. You either run many independent solution attempts in parallel (memory-intensive, treats all paths equally) or prune bad branches (starves the hardware, doesn't redirect compute to winners). The authors show there's a middle path: allocate compute dynamically by repeatedly killing weak reasoning traces and immediately spawning new branches from the strongest partial solutions.

How Gambit Works

Gambit performs thought-level beam search, meaning it operates on partial reasoning traces (sequences of reasoning steps) rather than individual tokens. Here's the pipeline:

During inference, the model generates reasoning steps incrementally. Periodically, Gambit scores each partial trace using a lightweight scorer that probes the model's hidden states—no expensive re-runs needed. It then prunes the bottom performers and immediately branches from top-scoring prefixes. This cycle repeats, constantly redirecting compute toward the most promising reasoning paths.

The key insight is timing: pruning and branching happen at the thought level (e.g., after completing a full reasoning step or paragraph), not token-by-token. This lets the algorithm chunk work efficiently and maintain continuous GPU utilization. The scorer stays light by examining internal model representations rather than requiring full forward passes, keeping overhead minimal.

Why This Matters

The efficiency gains are substantial. On HMMT-24 (a hard high school math competition), Gambit achieves +6.7% absolute accuracy over pruning baselines under the same compute budget. On AIME-25 (American Invitational Math Exam), it gains +3.3%. These aren't tiny margins—they reflect meaningful improvement in solving complex multi-step problems.

Beyond accuracy, throughput jumps >2× compared to completing traces under standard methods, and token consumption drops by up to 68.5% versus naive parallel sampling. That last number is critical: fewer tokens means lower cost and latency in production, which compounds across millions of inference calls.

The authors evaluate across multiple models and benchmarks, consistently showing Gambit dominates existing paradigms. The method dissolves a false choice: you don't have to pick between high hardware utilization or smart compute allocation. By interleaving pruning and branching at the thought level, Gambit achieves both.

Why Now

As reasoning models grow larger and test-time scaling becomes the dominant lever for performance, the bottleneck shifts from "how much compute?" to "where?". Gambit directly addresses that allocation problem with a simple, implementable algorithm. For any organization running inference under budget or latency constraints—especially on reasoning-heavy tasks—this matters: the same hardware delivers better answers.