유계 루프: 에이전트 하네스를 위한 실행 전 비용 지출 한계, 증명된 종료, 검증된 완료
Bounded Loops: Pre-Run Spend Bounds, Proved Termination, and Verified Completion for Agent Harnesses
한국어 초록
주류 에이전트(agent) 프레임워크에서는 에이전트 자체의 출력이 종료를 알릴 때 단계가 끝납니다. 내구성 실행(durable-execution) 플랫폼은 재시도 횟수와 시간을 제한하지만, 검사기(checker)는 관례적으로 작업과 동일한 코드베이스에 위치합니다. 이는 배포 환경이 준수할 것으로 신뢰하는 규율일 뿐, 하네스가 강제하는 속성이 아닙니다. 본 논문에서는 에이전트 하네스가 보장해야 하는 바를 명시하고 이를 증명하며, 하네스가 이를 충족하는지 측정하는 계측 도구를 구축합니다. 유계 루프(bounded loop)는 워커(worker), 워커가 쓸 수 없는 독립적인 게이트(gate), 그리고 선언된 예산으로 구성됩니다. 유계 루프 그래프는 다운스트림 실패 시 이미 완료된 업스트림 노드(node)를 다시 실행할 수 있도록 하는 복구(repair) 관계를 통해 이들을 결합합니다. 이에 따라 세 가지 보장이 수반됩니다. 첫째, 종료성(termination): 복구 예산이 노드별이 아닌 전역으로 주어질 경우, 폐쇄형(closed form)으로 계산되는 최악의 시도 횟수 총합 하에서 복구 중에도 종료가 유지됩니다. 둘째, 표류 방지: 복구로 인해 귀납적으로 적용할 위상 순서(topological order)가 남지 않으므로, 제어 흐름으로부터 증명되었듯이 어펜드 온리(append-only) 해시 체인 원장의 게이트 판정 없이는 어떤 노드도 DONE에 도달하지 않습니다. 셋째, 초과 지출 방지: 지출 상한은 시도 간이 아닌 시도 내부에서 강제됩니다. 게이트는 2계층 홀드아웃 돌연변이체 코퍼스(mutant corpus)를 바탕으로 측정됩니다. 우리는 타당해 보이는 검사가 무엇이든 통과시키게 만드는 두 가지 부류를 규명합니다. 즉, 검사 대상의 부재로 인해 충족되는 공허성(vacuity)과, 검사가 적용되는 값을 대상 자체가 제공하는 자기 증명(self-attestation)입니다. 69개 루프 카탈로그를 대상으로 해당 계측 도구를 적용한 결과, 배포 및 리뷰를 거친 코드에서 47개의 공허한 게이트를 발견했습니다. 복구된 게이트에 대해 테스트했을 때, 209개의 파괴 돌연변이체에서 오승인(false accept)이 전혀 보고되지 않았습니다($\alpha \le 1.8\%$, Wilson 95%). 그러나 이 수치는 포화(saturation)일 뿐 품질을 의미하지는 않습니다. 게이트를 동결(freezing)하고 새로운 연산자 군을 적용하자, 소진된 코퍼스에서는 0%로 보고되었던 곳에서 23.3%의 오승인율이 다시 나타났습니다. 특정 비율 수치는 개별 게이트에 종속되므로, 연구의 진정한 기여는 수치 자체가 아니라 이러한 평가 체계(apparatus)입니다. 엔진, 카탈로그, 코퍼스는 Apache-2.0 라이선스로 공개됩니다.
원문 초록
In mainstream agent frameworks, a step ends when the agent's own output says it has finished. Durable-execution platforms bound retries and time, but their checker conventionally lives in the same codebase as the work: a discipline the deployment is trusted to keep, not a property the harness enforces. We state what an agent harness must guarantee, prove it, and build the instrument that measures whether a harness delivers it. A bounded loop is a worker, an independent gate the worker cannot write to, and a declared budget; a bounded-loop graph composes them with a repair relation that lets a downstream failure re-run a finished upstream node. Three guarantees follow. It finishes: termination holds under repair, with the worst-case attempt total in closed form, if the repair budget is global not per node. It does not drift: no node reaches DONE without a gate verdict in an append-only hash-chained ledger, proved from control flow, since repair leaves no topological order to induct along. It does not overspend: the ceiling is enforced inside an attempt, not between attempts. Gates are measured against a two-tier held-out mutant corpus. We characterise two classes that let a sound-looking check pass anything: vacuity, satisfied by the absence of the thing checked, and self-attestation, where the subject supplies the value the check is applied to. On a 69-loop catalogue the instrument found 47 vacuous gates in shipped, reviewed code. Against the repaired gates it reports no false accepts over 209 destroying mutants ($\alpha \le 1.8\%$, Wilson 95%); that figure is saturation, not quality: freezing the gates and applying a fresh operator family recovers a 23.3% false-accept rate where the exhausted corpus reported none. A rate belongs to a specific gate; the apparatus, not our number, is the contribution. Engine, catalogue and corpus are Apache-2.0.
제출 이력
확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.
- arXiv:2609.27871v1제출 시각 미확인
함께 살펴볼 논문
공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.
Certified Robust Invariant Polytope Training in Neural Controlled ODEs
Proofs Without Nominals: G\"odel's Ontological Argument, its Shallow Embedding, and the Open Questions of the Monatshefte Notes
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) 뒤처져 있다.
구조적 결정 가능성: 진정한 무결점 시스템을 위한 설계 시점 검증
Decidable By Construction: Design-Time Verification for Truly Fearless Systems
컴파일러가 대기 상태(wait-for) 엣지를 추적하고, 멀티스레드 작업의 건전성을 증명하며, 분산 경계 계약을 보존할 때 동시성, 병렬성 및 분산 실행은 진정으로 두려움 없는(fearless) 시스템이 됩니다. 본 설계에서 저자들의 Composer 컴파일러는 C나 벤더 API를 통한 변환 없이 Clef를 네이티브 CPU, GPU, NPU 및 FPGA 코드로 직접 저수준화(lowering)하는 과정에서도 증명을 보존합니다. 본 연구의 프로그램 의미론 그래프(Program Semantic Graph)는 BAREWire의 언박싱된 경계 계약을 정당화하는 값, 관계 및 전제를 유지합니다. 또한 C 및 C++ 인터페이싱은 명시적인 마샬링 경계 역할을 하며, 증명은 실제 인자, 변환 및 반환값에 연계됩니다. 네 가지 검증 계층(tier)이 본 설계에 대한 설명을 유기적으로 연결합니다. 계층 1은 주 차원 유형(principal dimensional types)에 기반한 구조적 추론(inference)을 제공합니다. 계층 2는 노드(node) 수준에서 로컬 산술, 표현 및 계산 무결성을 생성하고 검사합니다. 계층 3은 Iris, Actris, Aneris가 지원하는 분산 증명을 포함하여 재사용 가능한 도메인 및 시스템 보조정리(lemma)를 인스턴스화합니다. 계층 1~3은 개발자의 어노테이션을 요구하지 않으며, 사용 사례 확장에 맞춰 적용 범위를 넓힐 수 있도록 인용 기반 보조정리 라이브러리 설계를 활용합니다. 계층 4는 계산 및 확률적 관계 증명을 수용하며, 프로젝트 어노테이션을 통해 필요한 관계를 식별합니다. 또한 동일한 라이브러리 방향성을 확장하여 하이퍼그래프 구조로부터 관계적 구성을 인식하도록 합니다. 형식적 합성 규칙은 산술, 소유권, 프로토콜 및 실체화 근거를 연결합니다. 본 연구에서 구현한 분산 리덕션(distributed reduction)은 동시 작업자, 도착 순서 변경 및 경계 매핑 전반에 걸쳐 명시된 단일 결과를 보존합니다. 그 확률적 확장은 명시적인 오류 허용 예산(failure budget)과 함께 작업자 및 변환 오류를 수용합니다. Urschel의 최근 연구와 결합하여, 바운드가 재사용 가능한 증명 항의 유효한 원천을 제공함을 입증합니다. 이러한 구조적 설계를 통해 다양한 하드웨어 타깃 전반에서 검증을 진정한 무결점 프로그램 및 시스템을 위한 핵심 엔지니어링 원칙으로 확립합니다.
틀에서 벗어난 사고: 언어 모델은 외부 지침에 선택적으로 의존할 수 있는가?
Thinking Outside the Box: Can Language Models Rely on External Guidance Selectively?
에이전트 하네스(agent harness)는 사람이 설계한 워크플로우를 통해 언어 모델을 개선하는 경우가 많지만, 모델의 능력이 향상됨에 따라 신뢰할 수 없는 지침은 오히려 모델의 실행을 제약할 수 있습니다. 본 연구에서는 유용한 지침을 활용하는 동시에 신뢰할 수 없는 지침은 기각하는 능력을 '틀에서 벗어난 사고(thinking outside the box)'라고 부릅니다. 저자들은 모델이 지침에 대한 의존도를 어떻게 조절하는지 분리해 파악하기 위해, 모델과 작업을 고정한 채 워크플로우의 신뢰도를 다양하게 변화시키는 Box$^2$-Bench를 도입합니다. Box$^2$-Bench에서 프론티어 모델들은 신뢰할 수 있는 지침으로부터 이점을 얻는 경우가 많지만, 지침이 오도하거나 신뢰할 수 없게 될 때는 여전히 취약한 상태로 남아 있습니다. 이러한 능력을 학습할 수 있는지 검증하기 위해, 평가를 위해 우수한 워크플로우는 남겨두고 불량한 워크플로우를 사용하여 두 개의 오픈 가중치(open-weight) 모델을 학습시킵니다. 또한 두 가지 상호 보완적인 학습 전략을 탐색합니다. 반사실적 지도 미세조정(counterfactual supervised fine-tuning)은 강건성을 향상시키는 반면, 결과 기반 강화학습(outcome-based reinforcement learning)은 도움이 되는 워크플로우를 더 적극적으로 활용하도록 균형을 이동시킬 수 있습니다. 나아가 이러한 동작이 워크플로우를 넘어 다른 형태의 외부 정보로도 확장되어 동료 수정(peer correction) 능력을 향상시키고 오염된 메모리에 대한 강건성을 높임을 확인했습니다. 종합적으로, 본 연구 결과는 오류 가능성이 있는 외부 정보에 대한 선택적 의존이 작업 수행 성능만으로는 포착되지 않는 에이전트 신뢰성의 중요한 한 차원임을 밝혀냅니다.
LLM 통합 하드웨어 설계 검증에 관한 서베이
A Survey on LLM-Integrated Hardware Design Verification
대규모 언어 모델(LLM)은 명세서 해석, 검증 산출물 생성, 디버깅, 정형 추론, 도구 오케스트레이션을 자동화하기 위해 하드웨어 검증에 점차 통합되고 있습니다. 본 서베이는 SystemVerilog 어서션 생성, 자극 및 테스트벤치 생성, 버그 위치 특정 및 설계 수정, 모델 검사 및 동등성 검사, SAT/SMT 최적화, 최신 에이전트 기반 검증 워크플로 전반에 걸친 LLM 지원 하드웨어 기능 검증에 대한 체계적인 검토를 제공합니다. 본 논문은 방법론, 검증 목표, 도구 상호작용, 벤치마크, 평가 기준별로 관련 문헌을 정리하며, 프롬프팅, 검색, 구조화된 추론, 에이전트 기반 워크플로를 포함한 추론(inference) 시점 기법과 학습(training) 시점 적응을 모두 살펴봅니다. 이러한 영역 전반에서 공통적인 패턴이 나타납니다. 시뮬레이터, 정형 엔진, 커버리지 도구, 솔버가 실행 가능한 피드백과 정확성 증거를 제공하는 반면, LLM은 검증을 고려한 워크플로 내에 내장된 의미론적 추론, 탐색, 오케스트레이션 구성 요소로서 가장 효과적입니다. 그러나 어서션, 테스트, 수정 또는 증명이 완전한 설계 의도를 충실히 포착하지 못한 채 제공된 검사만을 만족할 수도 있으므로, 도구 승인만으로는 검증 정확성이 확립되지 않습니다. 따라서 명세서와 검증 증거 간의 의미론적 정렬, 결정론적 도구와의 확장 가능한 통합, 미확인 설계에 대한 일반화, 그리고 정확성, 비용, 강건성, 인적 노력에 대한 엄격한 평가를 핵심 과제로 식별합니다. 마지막으로, LLM의 유연성과 독립적으로 검증 가능한 검증 증거를 결합하는 명세 중심, 신경-기호(neuro-symbolic), 지속형 에이전트 검증 시스템을 향한 새로운 방향을 논의합니다.
토론
이 논문과 연결된 포럼 글이 아직 없습니다.