Complex reasoning problems contain states that vary in the computational cost required to determine a good action plan. Taking advantage of this property, we propose Adaptive Subgoal Search (AdaSubS), a search method that adaptively adjusts the planning horizon. To this end, AdaSubS generates diverse sets of subgoals at different distances. A verification mechanism is employed to filter out unreachable subgoals swiftly and thus allowing to focus on feasible further subgoals. In this way, AdaSubS benefits from the efficiency of planning with longer subgoals and the fine control with the shorter ones. We show that AdaSubS significantly surpasses hierarchical planning algorithms on three complex reasoning tasks: Sokoban, the Rubik's Cube, and inequality proving benchmark INT, setting new state-of-the-art on INT.

AdaSubS 是一种自适应搜索方法，通过不同距离下生成不同的子目标，利用核实机制过滤不可达的子目标，实现长短子目标策略的高效平衡，从而在三个复杂推理任务中显著优于分层规划算法 —— 推箱子游戏，魔方和 INT 不等式证明基准。

快速而精确：利用自适应子目标搜索调整计划视界