@inproceedings{suh-etal-2026-think,
    title = "Think Hard Only When Needed: A Hybrid Best-of-N and Beam Search for Efficient Test-Time Compute",
    author = "Suh, Hyewon  and
      Li, Chaojian  and
      Shih, Cheng-Jhih  and
      Wang, Zheng  and
      Xia, Kejing  and
      Fu, Yonggan  and
      Lin, Yingyan Celine",
    editor = "Demberg, Vera  and
      Inui, Kentaro  and
      Marquez, Llu{\'i}s",
    booktitle = "Findings of the {A}ssociation for {C}omputational {L}inguistics: {EACL} 2026",
    month = mar,
    year = "2026",
    address = "Rabat, Morocco",
    publisher = "Association for Computational Linguistics",
    url = "https://preview.aclanthology.org/ingest-eacl/2026.findings-eacl.315/",
    pages = "6004--6017",
    ISBN = "979-8-89176-386-9",
    abstract = "Test-time compute has emerged as a promising paradigm that enables small language models (SLMs) to achieve large language model (LLM)-level capabilities by allocating additional compute for explicit reasoning during inference. Two common approaches are beam search and Best-of-N sampling. Beam search improves reasoning quality by scoring and optimizing token sequences using Process Reward Models (PRMs), but can incur non-trivial computational overhead and latency. In contrast, Best-of-N executes all reasoning trajectories without PRM guidance, often wasting compute on low-quality trajectories that may have gone astray early in the generation process. To address both inefficiencies, we propose THROW (THink haRd Only When needed){---}a hybrid inference pipeline that combines the diversity of Best-of-N with the reasoning trajectory optimization of beam search. THROW introduces a selective branch truncation and expansion mechanism: it generates shorter initial trajectories than Best-of-N and evaluates them using PRMs to classify each query as ``easy'' or ``hard.'' Based on this classification, THROW applies branch truncation for easy queries, mimicking Best-of-N, and PRM-guided branch expansion for hard ones, similar to beam search. Evaluations on MATH500, AMC23, and AIME24 demonstrate that THROW achieves 1.54{\texttimes} and 14.38{\texttimes} latency speedups and 35.7{\%} and 80.4{\%} token reductions on average while preserving high reasoning accuracy compared to Best-of-N and Beam Search, respectively."
}