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) 뒤처져 있다.
원문 초록
AI systems are making rapid progress in mathematics, but this progress is hard to measure. Benchmarks of solved problems saturate, and in benchmarks of open problems each problem can be resolved for the first time only once. We present SqueezeBench, a benchmark that is resilient to saturation: a success raises the bar instead of removing the problem. Each problem fixes an integer function $f(n)$ whose values are known only for small $n$, and the benchmark keeps a lower and an upper record on it. A record is a computable Lean function with a machine-checked proof that it bounds $f$. A submission proposes a new function and proves that it bounds $f$, that it is no worse than the current record at any $n$, and that it is strictly better at some $n$. Once accepted, it becomes the record that the next submission has to beat. The system thus chooses the bound as well as its proof, and it may improve the record at a single $n$ or its growth rate. At every $n$, the gap between the two records shows how far the certified bounds are from determining $f(n)$. Every proof is checked by two independent Lean kernels, so no referee needs to check the mathematics. The checks also reject a function that computes $f$ by exhaustive search at small $n$, and a maintainer only reads the submitter's report and looks for such a search at larger $n$. We release ten problems from extremal combinatorics with twenty proved initial records and the admission tools. As a baseline, agents based on a frontier language model, with at most one hour per record, had 82 submissions accepted and improved every record, without going beyond the published literature. Agents based on two newer models then started from these records, had 60 more submissions accepted and improved 19 of the 20 records again. For eight of the ten problems, at least one record is still asymptotically behind the best published bound.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
검토는 더 강력한 모델을 거의 능가하지 못한다: LLM 파이프라인에서 검증과 능력 전이의 분리
Review Rarely Beats the Stronger Model: Separating Verification from Capability Transfer in LLM Pipelines
CityDeploy-Bench: 다중 송신기 네트워크 배치를 위한 물리 기반 공간 집합 계획 벤치마킹
CityDeploy-Bench: Benchmarking Physics-Grounded Spatial Set Planning for Multi-Transmitter Network Deployment
도시 규모의 무선 배치 자동화는 복잡한 도심 전파 환경과 네트워크 전역의 간섭 속에서 여전히 어려운 과제로 남아 있다. 본 논문에서는 다중 송신기 배치 문제를 통합된 광선 추적(ray-tracing) 검증기 하에서 물리 기반 공간 집합 계획(physics-grounded spatial set planning) 문제로 재구성한 벤치마크인 CityDeploy-Bench를 소개한다. 이 벤치마크는 유틸리티(utility) 표현과 계획 다이내믹스를 분리함으로써, 다양한 플래너(planner)에 대해 직접적인 스칼라 보상, 관계형 모델, 그리고 고차 상호작용 구조 간의 통제된 비교를 가능하게 한다. 실험 결과, 물리적 결합(coupling)이 커질수록 계획 행동에서 명확한 전환이 나타난다. 배치 품질은 학습된 유틸리티가 송신기 간의 집합적 상호작용을 포착하는지에 점점 더 의존하게 되며, 반면 더 강력한 탐색만으로는 누락된 관계형 구조를 보완할 수 없다. 이는 다중 송신기 배치가 독립적인 공간적 의사결정들의 집합이 아니라, 물리적으로 상호작용하는 집합에 대한 조정(coordination) 문제임을 보여준다. 우리는 의사결정 학습(decision learning)과 물리 기반 무선 네트워크 설계를 연결하는 연구를 위한 재현 가능한 테스트베드로서 CityDeploy-Data와 벤치마크 프레임워크를 공개한다.
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)을 제공한다.
다국어 GSM-Symbolic: 언어 간 능력 전이를 결정하는 요인은 무엇인가?
Multilingual GSM-Symbolic: What determines capability transfer across languages?
한 언어에서 습득된 능력이 다른 언어로 어떻게 전이되는지, 혹은 무엇이 이러한 전이를 지배하는지에 대해서는 알려진 바가 거의 없습니다. 기존 평가는 비교 불가능하고 포화되기 쉬운 데이터셋에 의존하며 전이의 결정 요인들을 함께 검토하는 경우가 드뭅니다. 전이를 예측하는 요인을 식별하면 모든 언어 쌍에 걸친 소모적인 평가를 피할 수 있으며, 개발자가 저자원 언어에서의 성능을 제한하는 요소를 집중 공략할 수 있게 됩니다. 교차 언어 능력 전이를 평가하기 위해, 본 연구에서는 15개 언어에 걸쳐 항목별로 매칭된 30,000개의 질문-답변 쌍을 포괄하는 확장 가능한 다국어 수학 데이터셋인 Multilingual GSM-Symbolic을 소개합니다. 이 데이터셋은 단일 샘플로부터 수백만 개의 고품질 변형 생성을 가능하게 함으로써 과적합을 방지하고 일반화를 보장하기 위해 기호 템플릿을 활용합니다. Multilingual GSM-Symbolic을 사용하여 능력의 가장 큰 결정 요인을 모델 크기($β= 1.77$), 언어 자원 수준($β= 0.77$), 추론($β= 0.67$), 언어유형학적 거리($β= -0.25$)로 정량화합니다. 이러한 공동 추정을 통해 결정 요인들을 상호 간의 관계로 표현할 수 있습니다. 즉, 마라티어로 평가된 32B 모델은 영어에서의 10B 모델과 유사하게 동작합니다. 본 연구 결과는 모델 개발자에게 중요한 시사점을 제공하며, 모델 크기와 추론 능력이 저자원 언어와 고자원 언어 간의 성능 격차를 좁히는 반면($β= -0.27$ 및 $β= -0.20$), 유사한 수단들이 언어유형학적으로 거리가 먼 언어에는 거의 또는 전혀 영향을 미치지 않음을 보여줍니다. 전반적으로 본 분석 프레임워크는 언어 간 변량의 92%를 설명하지만 모델-언어 간 변량은 23%만 설명하며, 확인되지 않은 언어에 대한 모델의 성능을 6.0%p 이내로 예측합니다(r=.96). 타깃 언어에서 단 10개 템플릿의 측정값을 통합하면 이를 4.19%p로 낮출 수 있어, 다운스트림 데이터셋이 거의 없거나 아예 없는 상황에서도 합리적인 성능 추정이 가능해집니다.
검증자가 정답을 유출할 수 있다: 폐루프 에이전트 디버깅에서 최적화에 앞선 진단 가능성
A Verifier Can Leak the Answer: Diagnosability Before Optimization in Closed-Loop Agent Debugging
에이전트(agent) 개발자들은 시뮬레이터 기반 검증자(verifier)를 통해 프롬프트, 도구, 정책 및 진단 알고리즘을 비교하는 방식을 점점 더 많이 활용하고 있습니다. 그러나 검증자는 솔버(solver) 비교를 무의미하게 만들 수도 있습니다. 즉, 검증자의 프로브(probe)나 술어(predicate)가 타깃의 식별 정보를 인코딩하고 있다면, 정확한 옵티마이저(optimizer)는 어떠한 실질적인 모호성도 해결하지 못한 채 효과적인 것처럼 보일 수 있습니다. 본 연구에서는 폐루프(closed-loop) 의사결정 에이전트를 위한 집계 트레이스 디버거에서 발생하는 이러한 실패 사례를 보고합니다. 정확한 최소 적중 집합(Minimum Hitting Set, MHS)과 전파 인식 탐욕 알고리즘(propagation-aware greedy method)은 12개 개발 사례 모두에서 동일한 지지 집합(support)을 반환했으며, 9/12 사례에서 동일한 주입 결함(planted fault) 복구를 달성했습니다. 후속 감사 결과, 정확한 앵커(exact-anchor) 술어가 9/9 사례에서 주입된 쌍을 생성한 것으로 확인되었습니다. 해당 앵커들을 제거한 후 전체 주입 쌍 복구율은 8/9였습니다. 그럼에도 불구하고 하드 프로브 싱글톤(hard-probe singleton) 쌍은 9/9 사례에서 주입된 쌍과 일치했으며, 전파 후 비어 있지 않은 잔여 충돌군(residual conflict family)이 유지된 사례는 전무했습니다(0/9). 옵티마이저는 올바르게 작동했으나, 검증자가 이미 정답을 노출하고 있었던 것입니다. 이에 본 논문에서는 솔버 우선 평가 방식을 지지 집합 기반 게이팅(support-gated) 검증 규약으로 대체합니다. 먼저 클린 참조 맵(clean reference map)을 통해 반복적인 컴포넌트 노출을 입증해야 하며, 그다음 일치된 참조/현재 게이트를 통해 비교 가능한 런타임 증거를 확립해야 하고, 그 이후에만 독립적으로 보정된 신호 규칙이 탐지 결과를 반환할 수 있습니다. 1,440개의 사례와 21,600개의 파티션 행으로 구성된 사전 등록된 홀드아웃(heldout) 평가에서, 55/72 체제-컴포넌트(regime-component) 단위가 참조 게이트를 통과했고, 54/55가 런타임 게이트를 통과했으며, 표현된 컴포넌트의 안정적 위허용(stable false admission)은 단측 정확 95% 상한선 0.1391과 함께 0/20을 기록했습니다. 승인된 단위 내에서는 영향을 받은 정상 트래픽이 공칭 결함 셀 비율(nominal fault-cell fraction)보다 탐지를 더 잘 예측했습니다. 본 연구의 핵심적인 구조적 교훈은 컴포넌트 선택기를 최적화하기 전에 증거의 적격성과 비공개성(non-revelation)을 먼저 검증해야 한다는 점입니다. 그렇지 않으면 더 강력한 솔버가 단지 더 강력한 검증자 아티팩트(artifact)를 인증하는 것에 불과할 수 있습니다.
형식 수학 및 소프트웨어 검증에서 감사 가능한 추론을 위한 FORALL-LEAN-AGENT
FORALL-LEAN-AGENT for Auditable Reasoning in Formal Mathematics and Software Verification
코딩 에이전트(agent)는 Lean 증명 개발을 점점 더 자동화하고 있지만, 컴파일 성공만으로는 후보 증명이 허용 가능한 가정 하에서 의도한 명제를 증명한다는 점을 확증하지 못합니다. 본 논문에서는 형식 수학 및 소프트웨어 검증에서 감사 가능한 추론을 위한 프런트엔드 독립적 프레임워크인 FORALL-LEAN-AGENT를 제시합니다. 이 프레임워크는 격리된 작업 공간, Lean 도구, 새로운 검토를 명제 비교, 공리 감사, 그리고 지원되는 경우 독립적인 증명 검사와 결합합니다. 검증 증거와 검토자의 결정은 동일한 후보 아티팩트에 바인딩되어 수락 과정을 추적할 수 있도록 합니다. 우리는 VeriSoftBench, PutnamBench, 그리고 Lean Eval 소프트웨어 검증 트랙의 두 문제 모두에서 이 프레임워크를 평가합니다. 100개 과제로 구성된 VeriSoftBench 하위 집합에서, FORALLLEAN-AGENT와의 통합은 GPT-5.6 Sol의 벤치마크 규칙 성공을 낮은 노력으로 93개에서 100개로 높이는 동시에 비용을 69달러에서 62달러로 절감합니다. PutnamBench 평가에서는 전체 672개 문제를 평균 4.72달러에 모두 통과시킵니다. 이러한 결과는 에이전트 하네스 설계가 총 해결 횟수를 넘어서는 증거를 제공하는 동시에 정확성과 효율성을 향상시킬 수 있음을 보여줍니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.