arXiv:2606.05464v2 cs.AI

확장되는 탐색 공간에서 LLM의 최적화형 추론

Optimization-like Reasoning in LLMs over Expanding Search Spaces

Nicol\'as Astorga, Nabeel Seedat, Mihaela van der Schaar

제출 2026-11-18

한국어 초록

검증 가능한 보상 학습은 수학 및 코딩 추론을 향상시켰으나, 이러한 영역은 단계별 의사결정의 일부만을 포착한다. 실제 세계의 많은 과제는 다수의 유효한 대안 중에서 가치가 높은 실행 가능한 계획을 찾아내야 한다. 본 논문은 복잡도 축을 따라 LLM의 단계별 최적화형 추론을 학습하고 평가하기 위한 확장 가능한 최적화형 과제군인 OPT*를 제안한다. 각 과제는 실현 가능성 검사기와 평가기를 제공하며, 복잡도 매개변수는 새로운 인간 레이블 없이 탐색 공간을 확장한다. 이는 이러한 과제를 두 가지 체제에서 연구하는 동기가 된다. (i) 해결기를 부분 상태에 대한 가치 오라클로 사용하고 순위 기반 보상 설계를 적용하여 더 나은 다음 단계를 강화하는 해결기 안내 온라인 정책 최적화, 그리고 (ii) 이러한 해결기를 사용할 수 없을 때의 탐색 기반 오프라인 강화학습이다. 이론적으로는 큰 탐색 공간에서의 성공을 추론기가 탐색 예산 단위당 추출하는 정보와 연관시킨다. 실험적으로는 OPT*에서 탐색을 효율적으로 만드는 요소들을 절제 실험으로 분석하고, OPT*로 학습하면 단계별 최적화형 추론이 향상됨을 보인다.

원문 초록

Verifiable reward training has improved mathematical and coding reasoning, but these domains capture only part of step-by-step decision making. Many real-world tasks require finding a high-value feasible plan among many valid alternatives. We introduce OPT*, a scalable family of optimization-style tasks for training and evaluating LLM step-by-step optimization-like reasoning along a complexity axis: each task provides a feasibility checker and evaluator, while a complexity parameter expands the search space without requiring new human labels. This motivates studying these tasks in two regimes: (i) solver-guided online policy optimization, which uses a solver as a value oracle for partial states and applies rank-based reward shaping to reinforce better next steps, and (ii) search-based offline RL when such solvers are unavailable. Theoretically, we relate success in large search spaces to the information a reasoner extracts per unit of search budget. Empirically, we ablate the ingredients that make search efficient on OPT* and show that training on OPT* improves step-by-step optimization-like reasoning.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2606.05464v2제출 시각 미확인

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

공통 태그로 연결된 공개 논문이 아직 없습니다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.