arXiv:2609.25056v1 cs.CL

피드백 기반 단어 추론을 위한 그래프 기반 추론: 조토(Jotto) 문제를 위한 확장 가능한 프레임워크

Graph-Based Inference for Feedback-Driven Word Deduction: A Scalable Framework for the Jotto Problem

Dakshi Arora, Prakhar Kumar Srivastava, Ranjib Banerjee

제출 2026-09-23

한국어 초록

조토(Jotto) 문제를 기반으로 한 피드백 기반 단어 추론(word deduction) 프레임워크가 제안되며, 문제 공간은 모든 유효한 단어가 노드에 해당하고 에지 가중치가 두 단어 간의 공통 글자 수로 정의되는 가중치 그래프로 표현된다. 마지막으로, 게임플레이는 피드백을 사용하여 그래프의 비호환 공간을 반복적으로 좁혀 나가는 반복적 제약 조건 전파 메커니즘으로 정의되며, 구조화되고 해석 가능한 방식으로 가설 공간의 축소를 용이하게 한다. 문제 공간이 통상적으로 고정된 길이의 이소그램(isogram)에 대해 정의되던 기존 접근법과 달리, 제안된 프레임워크는 가변 길이 단어(3글자에서 8글자 사이)로 일반화되고 글자가 반복되는 경우로 자연스럽게 확장되어, 현실적인 조토 문제 사례들을 최초로 단일화된 프레임워크 내에서 다룰 수 있게 한다. 또한 제안된 프레임워크의 적용 가능성과 솔버 동역학은 각각 대화형 구현과 정성적 사례 연구를 통해 논의된다. 약 3,000건의 시뮬레이션 게임플레이 시나리오에 대한 대규모 자동화 테스트를 통해 단어 길이가 길어질수록 기대 반복 횟수가 감소한다는 새로운 수렴 행동을 규명한다. 통계적 검정을 통해 로그 관계를 검증하는 강력한 상관관계를 확인하며, 이는 회귀 모델링과 적합도 검정을 통해서도 검증된다. 초기 문제 정의 외에도, 본 정식화는 해석 가능성을 갖춘 피드백 기반 추론(inference)을 위한 유효한 패러다임으로서의 그래프 가지치기(pruning)와, 이것이 기호 추론 및 대화형 지능형 시스템과 맺는 연관성을 제시한다.

원문 초록

A feedback-based word deduction framework based on the Jotto problem is proposed, and the problem space is represented as a weighted graph where all valid words correspond to nodes, and the edge weight is defined by the number of common letters between the two words. Finally, the gameplay is defined as an iterative constraint propagation mechanism where feedback is used to iteratively narrow the incompatible space of the graph, facilitating the reduction of the hypothesis space in a structured and interpretable manner. In contrast to existing approaches, where the problem space is typically defined for fixed-length isograms, the proposed framework generalizes to variable-length words (between 3 and 8 letters) and naturally extends to repeated letter cases, facilitating the treatment of realistic Jotto problem instances within a unified framework for the first time. The proposed framework's applicability and solver dynamics are also discussed through an interactive implementation and a qualitative case study, respectively. Significant automated tests on approximately 3,000 simulated gameplay scenarios identify a novel convergence behavior: the expected number of iterations diminishes with increasing word length. A strong relationship is confirmed using statistical tests to verify a logarithmic relationship, which is also verified using regression modeling and goodness-of-fit tests. In addition to the initial problem statement, this formulation introduces graph pruning as a viable paradigm for feedback-driven inference with interpretability and its association with symbolic reasoning and interactive intelligent systems.

제출 이력

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

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

함께 살펴볼 논문

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

arXiv:2607.22009v1cs.CR공통 태그 Sequential Decision Making, Combinatorial Optimization, Graph Learning

Active Directory 보안 강화를 위한 실용적 그래프 최적화 및 AI 기반 모델

Practical Graph Optimisation and AI-Driven Models for Active Directory Security Hardening

Microsoft의 Active Directory(AD)는 IT 관리자가 Windows 도메인 네트워크 내에서 보안 권한을 관리하고 접근을 제어할 수 있게 하는 디렉터리 서비스이다. 많은 조직의 핵심 관리 시스템인 AD는 적대자의 주요 공격 대상이 되었다. 공격 그래프를 강화하는 많은 해결책이 존재하지만, 이러한 노력은 AD 공격 그래프에 특화된 여러 핵심적인 실용적 과제를 해결하는 데 미흡하다. 첫째, 기존 모델은 그래프가 정적이라고 가정하는 경우가 많지만, 실제 AD 환경은 매우 동적이다. 둘째, 대부분의 제안된 해결책은 취약점을 제거하는(엣지 제거) 방어적 조치에 한정되어 있으며, 보다 능동적인 방어 메커니즘은 대체로 연구되지 않았다. 셋째, 모든 조치가 실행 가능한 것은 아니므로, 실용적인 end-to-end 모델은 우선순위 결정 과정에 시스템 관리자의 피드백을 반드시 포함해야 한다. 본 논문은 이러한 한계를 해결하기 위해 게임 이론적 및 최적화 기반 의사결정 모델들을 연구하고 제안하는 것을 목표로 한다. 첫째, 최단 경로 수와 Domain Admin에 도달 가능한 노드 수를 최소화하는 원칙에 기반한 허니팟/디코이 배치 모델을 제안한다. 둘째, 이 모델을 기반으로 AD 그래프의 동적/시간적 특성을 고려하는 방어 전략을 도입하며, 목표는 최악의 경우 사고 대응 시간을 최대화하는 디코이 배치 위치를 찾는 것이다. 셋째, 각 고위험 공격 경로에 대해 IT 관리자에게 조치 판단을 요청하는 적응형 우선순위 모델을 도입한다. 마지막으로, 유사한 위험 특성을 가진 엣지에 시스템 관리자의 결정을 일반화하는 일반적인 적응형 엣지 제거 정책을 찾음으로써 시스템 관리자의 승인 부담을 최소화하는 end-to-end 적응형 우선순위 모델을 도입한다. 우리는 제안한 모든 모델의 기반이 되는 문제들이 계산적으로 난해함을 보인다.

arXiv:2610.13574v1cs.LG공통 태그 Sequential Decision Making, Combinatorial Optimization

고차원 금융 회귀에서 몬테카를로 트리 탐색을 통한 $L_0$ 특징 선택

$L_0$ Feature Selection via Monte Carlo Tree Search in High-Dimensional Financial Regression

특징(feature) 선택은 수많은 엔지니어링된 변수와 예측 변수 간의 강한 상관관계로 인해 모델(model)의 안정성과 해석 가능성이 저하되는 고차원 금융 회귀에서 핵심적인 문제입니다. 희소 회귀(sparse regression)에는 $L_1$ 정규화(regularization)(Lasso)가 널리 사용되지만, 정보성 신호가 상관관계를 갖는 변수들에 걸쳐 분산되어 있을 때는 수축(shrinkage) 특성이 제약으로 작용할 수 있습니다. 정확한 희소 회귀(exact sparse regression)는 이러한 수축을 피하지만 계산상 다루기 어려운 조합 최적화(combinatorial optimization) 문제를 해결해야 하며, 일반적으로 표본 외(out-of-sample) 오차가 아닌 표본 내(in-sample) 오차를 최소화하도록 적합됩니다. 본 논문에서는 일반화된 중첩 롤아웃 정책 적응(GNRPA)을 적용한 몬테카를로 트리 탐색(Monte Carlo Tree Search) 기반의 특징 선택 프레임워크를 제시합니다. 특징 선택을 순차적 의사결정 과정으로 정식화하며, 후보 부분집합은 학습(training) 오차 대신 표본 외 검증(validation) 성능을 기준으로 점수가 매겨집니다. 또한 본 방법은 부분집합 크기와 다중공선성을 고려하는 사전식 순서화 목적함수(lexicographic objective)를 지원합니다. 저자들은 시장, 거시경제 및 팩터 데이터를 포괄하는 1,072개의 엔지니어링된 특징으로부터 NASDAQ-100 지수의 주간 수익률을 설명하는 동시적 설명 회귀(contemporaneous explanatory regression) 과제에서 이 접근법을 연구합니다. 이는 다중공선성 환경에서의 부분집합 선택의 가치를 별개의 문제인 예측적 전망(forecasting)과 분리합니다. 이 과제에서 제안된 방법은 최적화된 Lasso 기준선(baseline)보다 더 높은 표본 외 설명력을 가진 희소 특징 부분집합을 식별하여, Lasso의 0.6313 대비 0.6961의 표본 외 $R^2$에 도달합니다. 이러한 결과는 몬테카를로 트리 탐색이 금융 회귀의 희소 설명적 특징 선택에서 볼록 정규화(convex regularization)의 실용적인 대안임을 시사하며, 표본 외 적합도만큼 투명성이 중요한 팩터 귀속(factor attribution) 및 위험 분해에 잠재적 가치가 있습니다.

arXiv:2610.10954v1cs.AI공통 태그 Sequential Decision Making, Combinatorial Optimization

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

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.03312v1cs.AI공통 태그 Sequential Decision Making, Combinatorial Optimization

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

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.00912v1cs.AI공통 태그 Sequential Decision Making, Combinatorial Optimization

OR을 수행하는 AI를 위한 OR: OSCAR 프레임워크 내에서 에스컬레이터를 따라 LLM 라우팅하기

OR for AI That Does OR: Routing LLMs up the Escalator inside the OSCAR Framework

대규모 언어 모델(LLM)은 비즈니스 설명을 최적화 모델(optimization model)로 변환할 수 있지만, 실행 가능한 코드가 제약 조건이나 목적 함수를 잘못 나타낼 수 있습니다. 이 경우 솔버(solver)는 잘못된 문제에 대한 최적해를 반환할 수 있습니다. 해당 해가 의도한 운영 규칙을 만족하더라도 더 나은 계획이 존재할 수 있습니다. 최적화 모델링을 반복적으로 사용하는 조직의 경우, LLM 기반 프레임워크는 저비용으로 정확한 수식화를 생성해야 하며 이상적으로는 로컬에서 실행되어야 합니다. 본 연구에서는 개선 사항을 검증하고 가격 및 성능이 서로 다른 LLM 간에 시도를 어떻게 할당할지 연구합니다. 우리는 라벨링된 결정 예시를 바탕으로 검증된 오프라인 시뮬레이터(Simulator)를 사용하여 후보들을 비교하고 단순 실행 가능성을 넘어 탐색을 지속하는 OSCAR(Optimization modeling by Simulator, Coder, And Reviewer)를 개발합니다. 우리는 다음으로 검증된 개선안을 찾는 과정을 관측되지 않은 난이도 하에서의 순차적 의사결정(어떤 LLM을 호출하고 언제 중단할지)으로 모델링합니다. 사전 확률이 알려진 단순화된 환경에서 비용 순서에 따른 에스컬레이션(cost-ordered escalation)이 최적이 되는 조건을 제시합니다. 일반적인 메뉴에 대해서는 사전 확률에 구애받지 않는(prior-free) 경쟁적 보장을 도출합니다. 5개의 벤치마크 문제에서 OSCAR는 단일 GPU에 로컬 배포 가능한 두 개의 소형 오픈 가중치(open-weight) LLM을 사용하여 보고된 설정 기준 95%에서 100%의 정확도를 달성합니다. 이 모델들의 단일 시도 정확도는 평균 29% 및 48%입니다. 문제당 5회 실행에서 Codex와 Claude Code는 OSCAR에 비해 각각 평균 3.1배, 5.8배의 토큰 비용을 발생시킵니다. OSCAR는 예산 및 기밀성 요구사항에 따라 로컬 또는 클라우드에서 오픈 가중치 모델을 지원합니다. 기업은 자연어 운영 규칙을 명확히 하기 위해 실행 가능한 결정과 실행 불가능한 결정에 대한 라벨링된 결정 예시를 유지 관리해야 합니다. OSCAR는 LLM의 해석이 이들과 충돌할 때 이러한 라벨을 따릅니다. LLM 성능과 가격이 변화함에 따라, OSCAR의 단순한 운영 규칙과 조정 가능한 설정은 기업이 모델 선택을 적응시키고 이러한 발전을 활용할 수 있도록 돕습니다.

arXiv:2610.01048v1cs.AI공통 태그 Sequential Decision Making, Combinatorial Optimization

복잡계 알고리즘 설계를 위한 환경으로서의 네트워크 월드 모델

Network World Models as Environments for Algorithm Design on Complex Systems

환경(environment)을 시뮬레이션하고 행동에 따라 환경이 어떻게 변화하는지 예측하는 월드 모델(world model)은 로보틱스와 같은 현실 세계 응용 분야에서 점점 더 많이 활용되고 있습니다. 복잡계 또한 행동의 효과가 즉각적으로 나타나지 않기 때문에 동일한 도구를 필요로 합니다. 캠페인을 위해 시드 노드를 설정하거나 전염병에 대비해 노드를 면역화하는 것은 그 자체만으로는 거의 변화를 일으키지 않으며, 중요한 것은 이후 단계들에 걸쳐 펼쳐지는 결과입니다. 특정 태스크에서 기대 성능을 극대화하도록 이러한 행동을 선택하는 알고리즘을 설계하는 것은 본질적으로 반복적인 과정이며, 모든 후보 알고리즘은 자신이 도출하는 결과에 따라 점수가 매겨져야 합니다. 이러한 결과를 얻는 작업은 시뮬레이션에 의존해 왔으나, 다수의 샘플링된 궤적(trajectory)에 걸쳐 후보들을 평가할 때 그 비용이 병목 현상을 유발합니다. 본 논문에서는 시간에 따른 개입 하에서 네트워크의 확산 역학을 학습하고, 각 행동을 네트워크에 적용하며, 그에 따른 결과를 예측하는 행동 조건부 네트워크 월드 모델을 제안합니다. 이 모델은 코딩 에이전트(agent)가 전체 롤아웃(rollout) 피드백, 행동 수준의 기여도(credit), 대안적 개입에 대한 반사실적 탐침(counterfactual probe)을 활용하여 실행 가능한 알고리즘을 설계하고 개선하는 알고리즘 설계 루프 내에서 고속 평가기 역할을 수행합니다. 8개의 네트워크 태스크와 5개의 확산 모델에 걸쳐, 설계된 알고리즘은 141개 설정 중 138개에서 보고된 가장 강력한 기준선(baseline)과 대등하거나 이를 능가하는 동시에 몬테카를로(Monte Carlo) 시뮬레이션 대비 최대 14.5배 빠른 롤아웃을 가능하게 합니다. 코드는 논문 채택 시 공개될 예정입니다.

토론

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