arXiv:2608.20153v3 cs.CL

FormalTCS: 대규모 언어 모델의 최전선 형식 이론 전산학 연구 전 과정(End-to-End) 벤치마킹

FormalTCS: Benchmarking End-to-End Frontier Formal Theoretical Computer Science Research of Large Language Models

Dingzirui Wang, Xuanliang Zhang, Keyan Xu, Qingfu Zhu, Wanxiang Che

제출 2026-09-24

한국어 초록

대규모 언어 모델(LLM)은 이론 전산학(TCS) 연구 자동화에서 점점 더 큰 잠재력을 보여 왔지만, 기존 벤치마크는 현실적인 연구 환경과는 여전히 거리가 멀다. 본 논문에서는 최전선(frontier)의 end-to-end TCS 연구에 대한 LLM 평가를 위한, 전문가가 검증한 벤치마크인 \ourbenchmark를 소개한다. \ourbenchmark는 2025-2026년 STOC, FOCS, SODA, COLT에 채택된 논문에서 추출한 $143$개의 인스턴스로 구성되며, 논문별 정의, 가정, 증명 의존성을 그대로 보존하고, 전문가가 검증한 Lean 형식화와 증명을 포함한다. 주요 LLM에 대한 평가 결과, 현재 모델들은 전체 연구 파이프라인을 안정적으로 완수하는 데 여전히 크게 못 미치는 것으로 나타났다. 특히 자동 형식화(autoformalization)가 가장 큰 병목이다. 가장 성능이 좋은 모델은 자연어 주장을 형식 정리 명제로 번역하는 과제에서 $11.5$에 그친 반면, 사람이 제공한 형식 명제를 증명하는 과제에서는 Pass@8 기준 $28.6$을 달성했다. \ourbenchmark를 바탕으로, 새로운 주장을 생성하고, 형식화하고, 필터링하고, 증명하는 자동화된 TCS 연구 프레임워크도 추가로 개발한다. 생성된 $64$개의 주장 중 최종적으로 전문가 평가와 증명 검증을 모두 통과한 것은 $6$개에 불과했으며, 이는 형식화 외에도 제한적인 연구 안목(research taste)이 자율적 TCS 연구를 가로막는 또 다른 주요 장벽임을 시사한다.

원문 초록

Large language models (LLMs) have shown growing potential for automated theoretical computer science (TCS) research, yet existing benchmarks remain far from realistic research settings. We introduce \ourbenchmark, an expert-validated benchmark for evaluating LLMs on frontier, end-to-end TCS research. \ourbenchmark contains $143$ instances drawn from papers accepted to STOC, FOCS, SODA, and COLT in 2025-2026, preserving paper-specific definitions, assumptions, and proof dependencies, with expert-verified Lean formalizations and proofs. Evaluations of leading LLMs reveal that current models remain far from reliably completing the full research pipeline. In particular, autoformalization is the sharpest bottleneck: the best model achieves only $11.5$ on translating natural-language claims into formal theorem statements, compared with $28.6$ Pass@8 when proving human-provided formal statements. Building on \ourbenchmark, we further develop an automated TCS research framework that generates, formalizes, filters, and proves new claims. Of $64$ generated claims, only $6$ ultimately pass expert evaluation and proof verification, indicating that beyond formalization, limited research taste remains another major barrier to autonomous TCS research.

제출 이력

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

  1. arXiv:2608.20153v3제출 시각 미확인

함께 살펴볼 논문

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

arXiv:2610.13461v1cs.AI공통 태그 Benchmarking, Math, formal verification

SqueezeBench: 포화에 강건한 수학적 능력 평가

SqueezeBench: Saturation-Resilient Evaluation of Mathematical Capability

AI 시스템은 수학 분야에서 빠르게 발전하고 있지만, 이러한 발전을 측정하기는 어렵다. 이미 풀린 문제들로 구성된 벤치마크(benchmark)는 포화(saturate)되며, 미해결 문제들로 구성된 벤치마크에서는 각 문제가 최초로 단 한 번만 해결될 수 있다. 우리는 포화에 강건한 벤치마크인 SqueezeBench를 제시한다: 성공은 문제를 제거하는 대신 기준을 높인다. 각 문제는 작은 $n$에 대해서만 값이 알려진 정수 함수 $f(n)$을 고정하며, 벤치마크는 이에 대한 하한(lower) 기록과 상한(upper) 기록을 유지한다. 기록(record)은 $f$를 한정(bound)함을 기계 검증된 증명(machine-checked proof)으로 보인 계산 가능한 Lean 함수이다. 제출(submission)은 새로운 함수를 제안하고, 그 함수가 $f$를 한정하며, 모든 $n$에서 현재 기록보다 나쁘지 않고, 일부 $n$에서는 엄밀히 더 우수함을 증명한다. 채택되면 해당 제출은 다음 제출이 넘어서야 할 새로운 기록이 된다. 따라서 이 시스템은 한계값(bound)뿐 아니라 그 증명까지 선택하며, 단일 $n$에서의 기록을 개선할 수도 있고 성장률(growth rate)을 개선할 수도 있다. 모든 $n$에서 두 기록 사이의 간극은 인증된 한계값들이 $f(n)$을 결정하는 데에서 얼마나 떨어져 있는지를 보여준다. 모든 증명은 두 개의 독립적인 Lean 커널에 의해 검증되므로, 심판이 수학적 내용을 검토할 필요가 없다. 검증 과정은 또한 작은 $n$에서 전수 탐색(exhaustive search)으로 $f$를 계산하는 함수를 거부하며, 유지관리자(maintainer)는 제출자의 보고서만 읽고 더 큰 $n$에서 그러한 탐색이 있는지를 확인한다. 우리는 극단적 조합론(extremal combinatorics) 분야의 열 가지 문제를 스무 개의 증명된 초기 기록 및 승인 도구(admission tools)와 함께 공개한다. 기준선(baseline)으로서, 최신(frontier) 언어 모델(language model) 기반 에이전트(agent)는 기록당 최대 한 시간을 사용하여 82건의 제출을 승인받았고 모든 기록을 개선했으며, 이는 기존 발표된 문헌의 범위를 넘어서지는 않았다. 이후 두 개의 더 새로운 모델(model) 기반 에이전트들이 이 기록들로부터 시작하여 60건의 추가 제출을 승인받았고, 20개의 기록 중 19개를 다시 개선했다. 열 가지 문제 중 여덟 가지 문제에서는, 적어도 하나의 기록이 여전히 발표된 최선의 한계값(bound)에 비해 점근적으로(asymptotically) 뒤처져 있다.

arXiv:2610.02488v2cs.LG공통 태그 Benchmarking, Math, Large Language Model

LLM을 에이전트로 활용하기: 비용은 얼마인가?

Harnessing LLMs as Agents: What Does It Cost?

언어 모델 에이전트는 제한된 컨텍스트(bounded context), 영속 메모리(persistent memory), 도구, 검증, 반복 실행을 관리하는 하네스(harness)에 점점 더 의존하고 있지만, 기존의 모델 능력 개념은 이러한 메커니즘이 소비하는 계산 자원을 정량화하지 못한다. 우리는 기저 의미론적 모델(semantic model)은 고정한 채 하네스 수준의 자원을 명시적으로 과금하는 자원 제약 추상화인 언어 모델 에이전트 머신(Language Model Agent Machine, LAM)을 도입한다. 우리는 네 가지 범주의 결과를 확립한다. 통신(Communication): LAM 실행은 동시적인 호출-전송 예산(call-transfer budget) 하에서 적-청 페블링(red-blue pebbling)과 인스턴스 단위로 동등하며, 이는 고전적인 입출력 하한(I/O lower bound)을 컨텍스트-메모리 트래픽으로 전이시킨다. 접근(Access): 메모리 인터페이스는 포인터 체이싱(pointer chasing)에서 무작위 접근과 비추측적(non-speculative) 순차 접근 사이의 $Θ(n)$ 격차를 포함하여 점근적 분리(asymptotic separation)를 유발한다. 재계산(Recomputation): 비트 반전(bit-reversal) DAG는 컨텍스트 용량 $C$와 영속 메모리 용량 $S$ 하에서 $Θ(n^2/(C+S)+n)$회의 모델 호출을 필요로 하며, 이는 저장된 중간 상태가 반복적인 의미론적 계산을 언제 피할 수 있는지를 정량화한다. 신뢰성(Reliability): 우리는 엄밀한 단계별(stage-local) 샘플링 한계, 불완전 검증(imperfect-verification)의 정확한 비용, 그리고 닫힌 형태의 최적 검증 간격을 갖는 영-데일리(Young-Daly) 유형의 체크포인트 법칙을 유도한다. GPT-6 Astra에 대한 통제 실험과 홀드아웃(held-out) 실험은 체크포인트 최적값, 프로그래밍적 검사(programmatic checking) 하에서의 정책 선택, 그리고 연쇄 MATH 과제에서 호출 단위(call granularity), 논리적 입력 트래픽, 신뢰성 간의 트레이드오프를 포함하여 통신 및 신뢰성 예측을 검증한다. 종합적으로, 이 결과들은 언어 모델 에이전트 하네스의 계산 비용에 대한 자원 이론(resource theory)을 제공한다.

arXiv:2610.13672v2cs.CL공통 태그 Math, Large Language Model

토큰이 아닌 턴 주입하기: 자기 수정을 위해 LLM 추론을 리디렉션할 위치 학습

Inject a Turn, Not a Token: Learning Where to Redirect LLM Reasoning for Self-Correction

대규모 언어 모델(LLM)은 자신의 추론 과정에서 발생한 오류를 안정적으로 식별하고 수정하는 데 어려움을 겪는다. 수정이나 피드백을 생성하도록 LLM을 미세조정하는 기존의 학습 기반 접근법과 달리, 우리는 실패한 롤아웃에서 어디에 개입할지를 학습하고 이를 어떻게 리디렉션할지를 결정한다. 개입 위치를 선택하기 위해, 우리는 최종 답안의 정답 여부만을 이용해 고정된 인코더 위에 130K개의 매개변수를 가진 MLP 헤드를 학습시킨다. 리디렉션의 경우, 고정된 생성 예산 하에서 테스트한 인라인 주입(inline injection)은 추론을 안정적으로 리디렉션하지 못하는 반면, 동일한 지시문을 새로운 사용자 턴(user turn)으로 제시하면 모델의 진행 방향이 바뀐다는 것을 발견했다. 그 결과로 만들어진 수정 프레임워크인 UPTURN(User-Prompt TURN injection at a learned position)은 LLM의 미세조정을 전혀 요구하지 않는다: 선택된 접두 문맥(prefix)을 유지하고, 지시문을 새로운 사용자 턴으로 주입한 뒤, 나머지 부분을 재생성한다. 네 가지 추론 모델과 여섯 가지 수학 벤치마크 전반에서, UPTURN은 32회 롤아웃 기준선(baseline) 대비 모든 설정에서 평균 정확도를 향상시킨다. 동일한 수정 예산 하에서 자기 수정(self-correction) 및 리플렉션 토큰(reflection-token) 주입 기준선을 능가하며, 재학습 없이도 다른 추론 모델과 GPQA-Diamond로 전이되고, GRPO 및 자기 수정 기법과도 상호보완적이다.

arXiv:2610.10942v2cs.AI공통 태그 Benchmarking, Large Language Model

StoreBench: 자율 운영자 에이전트의 평가 및 학습을 위한 라이브 커머스 환경

StoreBench: A Live-Commerce Environment for Evaluating and Training Autonomous Operator Agents

강화학습(RL) 환경은 이제 사후 학습(post-training)에서 대규모 언어 모델(LLM)의 역량을 향상시키는 주요 수단이 되었으나, 대부분의 에이전트 벤치마크는 여전히 정적입니다. 즉, 에이전트가 행동할 때만 환경이 변화하고, 보상은 최종적인 판정으로 주어지며, 통과 기준은 자의적으로 설정됩니다. 본 논문에서는 에이전트가 프로덕션 수준의 상거래 백엔드에서 중간 규모의 온라인 의류 매장을 운영하며 불확실성 속에서 장기 계획 수립 및 경제적 판단력을 시험받는 라이브 커머스 환경인 StoreBench를 소개합니다. 고객은 24시간 내내 주문하고, 공급업체는 가격을 재책정하거나 공급에 실패하며, 시장 충격은 부분적인 예고만 있거나 예고 없이 발생합니다. 에이전트는 실제 인간 운영자가 사용하는 것과 동일한 29개의 판매자 도구를 통해 행동하며, 취해진 행동의 함수로 시뮬레이션 시간을 계산하는 윈도우 기반 운영 예산 하에서 작동하므로 모델 지연 시간이 시뮬레이션 시간에 영향을 미칠 수 없습니다. 통과 임계값은 스크립트 기반 앵커 정책을 기준으로 보정되었고, 보상은 다양한 보상 해킹 목록에 대비해 강화되었으며, 일련의 행동이 주어지면 모든 에피소드가 동일하게 재현됩니다. 본 연구에서는 추론 노력을 일치시킨 상태에서 세 가지 월드 시드에 걸쳐 30~45일 및 시뮬레이션된 1년 전체에 해당하는 11개 시나리오를 바탕으로 7개의 프론티어 LLM을 평가합니다. 평균적으로 스크립트 기반 스마트 트리아지(smart-triage) 정책에 필적하는 모델은 없었습니다. 최고 성능을 보인 DeepSeek-V4-Pro는 휴리스틱의 97% 대비 49%의 태스크-시드 셀을 통과했습니다. 동일한 도구와 예산을 사용하여 작업한 인간 전문가는 모든 모델보다 높은 점수를 기록했습니다(평균 종합 점수 0.708 대 0.700). Claude Code 하네스 기반의 시뮬레이션된 1년 전체에 걸쳐 대다수 모델은 극적인 성능 향상을 보입니다. GRPO 사후 학습 실행에서 서로 다른 5개의 태스크로만 학습된 Qwen3.5-27B는 홀드아웃(held-out) 평가 태스크에서의 평균 종합 점수를 0.136에서 0.373으로 향상시켰습니다. 본 연구에서는 학습 분할용 예시 태스크 5개, 샘플 궤적 10개, 점수 측정 및 검증 툴링을 공개하며, 벤치마크 오염을 방지하기 위해 전체 환경과 평가 스위트는 비공개로 유지합니다.

토론

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