arXiv:2609.23680v1 cs.DS

비일관적 A*의 평활 분석

Smoothed Analysis of Inconsistent A*

Zhiyang Chen, Hailong Yao

제출 2026-09-22

한국어 초록

A* 탐색은 인공지능에서 기본적인 경로 탐색 알고리리즘이다. 허용 가능하고 일관적인 휴리스틱은 각 상태를 최대 한 번만 확장함으로써 효율적인 성능을 보장하지만, 현대 탐색 응용에서는 기계 학습, 무작위 평가 등에서 유도된 강력하지만 비일관적인 휴리스틱을 자주 사용한다. 이러한 비일관적 휴리스틱 사용에 대한 오랜 이론적 장벽은 치명적인 노드 재확장(re-expansion) 위험이며, 이는 최악의 경우 $\Omega(2^n)$의 지수적 시간 복잡도를 초래한다. 그러나 경험적 관찰은 이 비관적 상한과 모순되며, 비일관적 A*가 실제로는 매우 효율적으로 동작함을 보여 준다. 이론과 실무 사이의 이 큰 격차를 메우기 위해, 본 논문은 비일관적 휴리스틱을 사용하는 A* 알고리리즘에 대한 최초의 평활 분석(smoothed analysis)을 제시한다. 우리는 최악 경우 탐색 그래프의 간선 가중치에 미세한 무작위 perturbation을 적용하여 전형적인 실세계 노이즈를 모델링한다. 주요 결과는 비일관적 A*의 기대 평활 시간 복잡도가 다항식으로 bounded됨을 증명하며, 구체적으로 총 반복 횟수가 $O(n^2 m \kappa)$임을 보인다. 여기서 $n$은 노드 수, $m$은 간선 수, $\kappa$는 무작위 perturbation의 규모를 조절한다. 또한 이 결과가 음수 가중치 그래프에서의 Dijkstra 알고리리즘과 기능적으로 동등한 문제로 자연스럽게 확장됨을 보인다.

원문 초록

The A* search is a fundamental path-finding algorithm in artificial intelligence. While admissible and consistent heuristics guarantee efficient performance by expanding each state at most once, modern search applications frequently employ powerful but inconsistent heuristics derived from machine learning, randomized evaluations, etc. A long-standing theoretical barrier to using these inconsistent heuristics is the risk of catastrophic node re-expansion, which yields a worst-case exponential time complexity of $\Omega(2^n)$. However, empirical observations contradict this pessimistic bound, demonstrating that inconsistent A* operates highly efficiently in practice. To bridge this significant gap between theory and practice, this paper presents the first smoothed analysis of the A* algorithm using inconsistent heuristics. We model typical real-world noise by applying slight random perturbations to the edge weights of worst-case search graphs. Our main result proves that the expected smoothed time complexity of inconsistent A* is bounded by a polynomial, specifically a total iteration number of $O(n^2 m \kappa)$, where $n$ is the number of nodes, $m$ is the number of edges, and $\kappa$ controls the scale of random perturbations. Furthermore, we also show that this result naturally extends to the functionally equivalent problem of Dijkstra's algorithm on negative-weight graphs.

제출 이력

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

  1. arXiv:2609.23680v1제출 시각 미확인

함께 살펴볼 논문

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

arXiv:2610.10867v1cs.LG공통 태그 Computational Efficiency, Combinatorial Optimization

분류 성능의 지표로서 라이프-유사 네트워크 오토마타 규칙의 형태 불규칙성

Shape irregularity of Life-Like Network Automaton rules as an indicator of classification performance

복잡 네트워크(Complex Network, CN) 분류는 스케일 불변(scale-invariant)이면서도 계산적으로 효율적인 고수준의 구조적 특성화를 필요로 합니다. 라이프-유사 네트워크 오토마타(Life-Like Network Automata, LLNA) 기반 방법은 사전에 제공된 특징 없이도 창발적 시간 패턴을 활용하여 네트워크 기술자(descriptor)를 추출하는 흥미로운 방식을 제공하지만, 그 효과는 오토마타 전이 규칙의 선택이라는 높은 비용의 조합 최적화 문제로 인해 병목 현상을 겪습니다. 기존 연구들은 대규모 응용에 실현 불가능한 전수 탐색(exhaustive search)에 의존하는 반면, 본 연구는 규칙 공간이 LLNA 전이 함수와 톱니 형태의 유사성을 정량화하는 '들쭉날쭉함(jaggedness)'이라는 특성으로 근본적으로 구조화되어 있음을 밝힙니다. 우리는 이 지표가 혼돈성(chaoticity)과 민감도(sensitivity)에 대한 이론적 대리 지표로 작용함을 입증하며, 이러한 특성은 네트워크 범주 간의 식별력 있는 동적 동작을 생성하는 데 필수적입니다. 나아가, 우리는 들쭉날쭉함을 활용하여 규칙 선택을 유도하는 휴리스틱 탐색 전략을 도입합니다. 실험 결과에 따르면 본 접근법은 전수 탐색 방식에 비해 계산 오버헤드를 90% 줄이면서도 전역 최적값 대비 5% 이내의 분류 정확도를 달성합니다. 우리의 발견은 패턴 인식을 위한 오토마타 기반 방법을 최적화하는 새롭고 효율적인 프레임워크를 제공합니다.

arXiv:2610.10954v1cs.AI공통 태그 Combinatorial Optimization, Heuristic Search

지수적으로 더 적은 공간으로 계획을 탐색하는 방법 학습

Learning How to Search for Plans with Exponentially Less Space

계획(plan)에 대한 휴리스틱 탐색(heuristic search)은 휴리스틱이 거의 완벽하더라도 지수적으로 많은 상태를 저장할 수 있다. 우리는 대신 탐색 제어(search control)를 학습하는데, 이는 도메인별로 하나씩 작성되는 인덱시컬 정책(indexical policy)으로서, 객체를 담는 레지스터(register)와 규칙을 순서화하는 모드를 갖는 일반화된 정책(generalized policy)이다. 우리는 객체를 레지스터에 적재하고 백트래킹 지점을 표시하는 choose 규칙을 추가하는데, 이 지점에서는 하나의 후보만으로 충분하다. 그 외의 모든 규칙은 가능한 모든 결과에 대해 작동해야 하며 탐색을 필요로 하지 않는다. 우리의 주요 결과는, 무한 실행을 배제하는 구조적 종료성(structural termination)이 객체 수에 대한 다항식으로 모든 실행을 제한한다는 것이다. 그러면 깊이 우선 절차(depth-first procedure)는 상태 공간이 얼마나 크더라도 방문한 상태의 목록 없이 다항식 공간(polynomial space) 안에서 계획을 찾아낸다. 그 대가는 시간이며, 이는 실행 과정에서의 실제 선택 횟수인 선택 깊이(choice depth)에 대해서만 지수적이다. 따라서 이러한 정책이 풀 수 있는 모든 클래스는 NP에 속하며, 선택 깊이가 상수일 때는 P에 속한다. 우리는 종료성을 증명하고 학습 과제를 검증하며 선택 깊이를 작게 유지하는 반례 기반(counterexample-guided) 루프에서 언어 모델로 이러한 정책들을 학습시킨다. 학습된 정책을 사용하여, 이 절차는 IPC 2023 Learning Track과 Autoscale Agile 스위트의 1,890개 테스트 과제 중 1,709개를 풀어내며, 이는 LAMA, BFWS, Levitron보다 더 많고, 그중 대부분을 1초와 100MiB 이내에 해결한다.

arXiv:2610.03296v1cs.AI공통 태그 Computational Efficiency, Combinatorial Optimization

JOVE: 자원 인지형 LLM 태스크 그래프를 위한 공동 실행 및 검증

JOVE: Joint Execution and Verification for Resource-Aware LLM Task Graphs

복잡한 추론 질의는 방향성 비순환 그래프(DAG) 형태의 태스크 그래프로 분해되어 이종 대규모 언어 모델(LLM)에 분산될 수 있으며, 이를 통해 병렬 처리를 통한 지연 시간을 줄이고 더 작은 모델이 복잡한 태스크를 해결하도록 지원할 수 있습니다. 그러나 실제로는 주어진 서브태스크에 대한 특정 LLM의 적합성을 사전에 알 수 없을 수 있으며, 단순 실행만으로는 출력의 정확성을 파악할 수 없습니다. 본 논문에서는 실행기 LLM을 할당하는 동시에 유료 검증을 거칠 중간 출력을 함께 선택하는 온라인 프레임워크인 JOVE를 제안합니다. 검증은 비동기식으로 실행되며 향후 할당 결정을 개선하는 데 사용되므로, 시스템은 현재 실행에 드는 비용과 향후 학습을 위한 지출 사이의 균형을 유지해야 합니다. 본 연구에서는 확률적이며 초기에는 알려지지 않은 LLM 서비스 품질, 호출 비용 및 실행 시간 환경에서 장기 예산과 질의별 지연 시간 제약 조건 하에 이러한 트레이드오프를 최적화하는 방법을 연구합니다. JOVE는 질의별 일련의 혼합 정수 선형 계획법(MILP) 문제를 해결하여 실행 및 검증 결정을 내립니다. 온라인 학습은 검증 피드백을 기반으로 LLM 품질에 대한 태스크 의존적 추정치를 업데이트하며, 정보 이득 보너스를 통해 학습의 가치를 할당 결정에 반영합니다. 자연스러운 일련의 가정 하에 본 연구는 JOVE의 준선형(sublinear) 품질 학습 후회(regret)를 입증합니다. 4가지 추론 벤치마크 전반에서 JOVE는 표준 추론(inference) 베이스라인 대비 경쟁력 있는 정확도를 달성하는 동시에 평균 비용과 지연 시간을 최소 3.17배 단축합니다.

arXiv:2610.03312v1cs.AI공통 태그 Combinatorial Optimization, Heuristic Search

동적 환경에서의 최적 계획 수립

Optimal Planning in a Dynamic World

배경: 본 논문에서는 실행 가능한 상태나 행동의 집합이 시간에 따라 변하는 환경에서의 계획 수립(planning) 문제를 다룹니다. 예를 들어, 이동하는 장애물 사이에서의 경로 계획 문제(흔히 SIPP로 알려짐)에서는 장애물이 이동함에 따라 특정 위치에 머무를 수 있는 가능 여부가 달라질 수 있습니다. 또는 특정 기차에 탑승하는 행동은 기차가 역에 정차해 있는 동안에만 실행 가능합니다. 이러한 동적 특성으로 인해 최적 계획과 그 수행 시간은 실행이 언제 시작되는지에 따라 달라질 수 있습니다. 실제 환경에서는 계획 수립이 완료되거나 다른 에이전트(agent)의 승인이 날 때까지 실행 시작 시간을 알 수 없는 경우가 많습니다. 그러나 기존의 계획 수립 연구 대부분은 이러한 동적 특성을 무시하거나 시작 시간이 사전에 알려져 있다고 가정합니다. 이는 상태와 행동의 실행 가능성을 평가하기는 수월하게 만들지만, 일부 응용 분야에서는 비현실적입니다. 목표: 본 논문에서는 시작 시간이 알려져 있다는 가정을 완화합니다. 임의 시작 시간 계획 수립(any-start-time planning) 설정을 정의하고 이를 위한 알고리즘을 제시합니다. 방법: 시작 시간의 함수로서 최적 계획을 간결하게 인코딩하는 복합 도착 시간 함수(compound arrival time function, cATF)라는 자료구조를 제안합니다. 또한 스칼라 비용 대신 간선을 따라 함수를 전파하여 cATF를 구성하는, 휴리스틱 그래프 탐색 기반의 범용 계획 수립 알고리즘을 제공합니다. 결과: cATF의 크기가 문제 크기에 대해 최대 선형임을 증명합니다. SIPP의 특정 문제에 대한 구현체를 바탕으로 한 실험적 평가에 따르면, 어려운 문제에서 재계획(replanning)에 의존하는 에이전트는 실패하는 경우가 빈번한 반면, cATF를 사용하는 임의 시작 시간 알고리즘은 실행 시작 시간이 확정되면 최적 계획을 신속하게 조회할 수 있음을 보여줍니다. 결론: 시간 의존적 계획에 대한 효율적인 표현과 추론을 가능하게 함으로써, 본 연구는 동적 환경에서의 계획 수립을 위한 토대를 제공합니다.

arXiv:2610.02697v1cs.RO공통 태그 Navigate, Computational Efficiency

GeoScaffold: 효율적인 비전-언어 내비게이션을 위해 재구성을 통한 컴팩트 기하학적 잠재 표현 학습

GeoScaffold: Learning Compact Geometric Latents via Reconstruction for Efficient Vision-Language Navigation

최근 비전-언어 내비게이션(VLN) 시스템은 1인칭 시점 RGB 관측값과 지시문을 저수준 행동으로 직접 매핑하는 스트리밍 Video-LLM 정책을 점점 더 많이 채택하고 있습니다. 그러나 이러한 정책들은 2D 사전학습(pre-training)으로부터 취약한 3D 기하학적 사전 지식(prior)을 물려받습니다. 기존의 기하학 인지형 확장 기법들은 깊이(depth) 센서, 3D 인코더, 스텝별 인식 도구 호출 등 지속적인 추론(inference) 시간 비용을 초래합니다. 본 논문에서는 기하학적 정보를 정책 자체에 내재화함으로써 이러한 비용을 학습(training) 시점에 단 한 번만 치르는 기하학적 지도 프레임워크인 GeoScaffold를 제안합니다. GeoScaffold는 먼저 학습 궤적의 깊이 맵에서 컴팩트한 깊이 토크나이저를 학습한 뒤 이를 동결합니다. 그런 다음 소수의 학습 가능한 기하학 쿼리 토큰으로 정책을 파인튜닝(fine-tuning)하며, 해당 은닉 상태가 깊이, 연결성, 주행 가능성(traversability)과 같이 내비게이션에 중요한 기하학적 정보를 재구성하도록 학습시킵니다. 이러한 지도 학습은 쿼리 상태를 행동 디코딩을 위한 컴팩트한 기하학적 잠재 표현으로 변환하며, 공유 가중치를 통해 백본 자체의 표현에도 기하학적 정보를 내재화합니다. 비계(scaffold)처럼 토크나이저, 타깃 생성기, 재구성 헤드는 학습 후 폐기되어 백본과 행동 인터페이스를 그대로 유지합니다. 광범위한 실험을 통해 GeoScaffold가 연속적인 VLN 벤치마크(benchmark)에서 주요 비전 전용 내비게이터들을 지속적으로 능가함을 보였으며, 공간을 인지하는 임바디드(embodied) 내비게이션 모델의 경량 엣지 배포(edge deployment)를 위한 실용적인 패러다임을 제공합니다.

arXiv:2609.25149v2cs.LG공통 태그 Computational Efficiency, Combinatorial Optimization

최대 독립 집합을 위한 Dual-GNN 다중 수준 조 정

Dual-GNN Multilevel Coarsening for Maximum Independent Set

최대 독립 집합(maximum independent set, MIS) 문제는 스케줄링, 자원 할당, 네트워크 분석 등에 응용되는 기본적인 NP-hard 조합 최적화(combinatorial optimization) 문제이다. 정확 솔버(exact solver)는 고품질 해 또는 최적성 증명(optimality certificate)을 제공할 수 있으나, 계산 비용은 그래프 크기에 따라 급격히 증가한다. 반면 수작업 휴리스틱(hand-crafted heuristic)은 보장을 희생하는 대신 확장성(scalability)을 개선한다. 학습 기반 방법은 그래프 인스턴스 간 구조적 패턴을 활용하는 대안을 제공하지만, 독립 집합을 직접 예측하면 대규모 그래프에서 전역 조율(global coordination)이 어려워질 수 있다. 우리는 대신 학습을 이용해 다중 수준 그래프 조 정(multilevel graph coarsening)을 안내하고, 최종 의사 결정에는 조합 탐색(combinatorial search)을 유지한다. Dual-GNN 다중 수준 조 정 프레임워크는 Partition GNN으로 후보 수축(contraction)을 점수화하고, Representative GNN으로 각 최종 클러스터에 대해 상위 k개의 지역 독립 집합 상태를 선택한다. 최대 2,000개 정점(vertex)을 갖는 Erdős–Rényi 그래프 실험에서 유리한 품질–실행 시간 트레이드오프(quality–runtime trade-off)를 보여준다. 인증된 최적해가 있는 500정점 인스턴스에서, 본 방법은 평균 독립 집합 크기 19.20을 달성하며 이는 최적값 19.30의 99.5%에 해당한다. 정확 해법의 평균 벽시계 시간(wall-clock time) 643.57초를 3.41초로 줄여 약 189배 속도 향상(speedup)을 얻는다. 1,000 및 2,000 정점의 더 큰 그래프에서는 평가된 모든 방법 중 최고의 평균 해 품질을 달성한다. 또한 가장자리 확률(edge probability) $p=0.35$인 Erdős–Rényi 그래프에서만 학습했음에도, 학습된 조 정 정책은 보지 못한 그래프 밀도와 구조적으로 다른 그래프 계열 모두에 효과적으로 일반화(generalize)된다.

토론

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