LLM 에이전트는 세계 모델을 추론할 수 있는가: Agentic Automata Learning 벤치마크
목차
개요
LLM은 게임처럼 규칙이 고정된 환경부터 개방형 세계 탐색까지 다양한 환경에서 상호작용형 에이전트로 점점 더 많이 사용되고 있다. 강력한 성능에도 불구하고, LLM이 자신이 상호작용하는 환경의 올바른 세계 모델을 추론하는지, 아니면 국소적 패턴과 얕은 휴리스틱에 의존하는지는 여전히 불분명하다. 이 질문에 답하려면 환경의 숨겨진 구조를 알 수 있고, 복잡도를 체계적으로 조절할 수 있으며, 에이전트의 발견 과정을 상호작용 내내 관찰할 수 있는 통제된 과제가 필요하다.
이 논문은 고전적인 능동 오토마타 학습(active automata learning)을 에이전트 과제로 재구성한 Agentic Automata Learning을 제안한다. 에이전트는 숨겨진 결정적 유한 오토마타(DFA, deterministic finite automaton)를 오라클과의 상호작용을 통해 식별해야 한다. 상호작용은 두 가지 쿼리로 이루어진다. 멤버십 쿼리(Membership Query)는 어떤 문자열이 목표 언어에 속하는지 묻고, 등가성 쿼리(Equivalence Query)는 가설 DFA를 제출해 그것이 숨겨진 목표와 일치하는지 확인한다. 일치하지 않으면 오라클은 두 DFA가 서로 다르게 분류하는 반례(counterexample)를 반환한다.
이 설정은 과제 복잡도를 통제할 수 있고(DFA의 상태 수), 상호작용 효율을 측정할 수 있으며(쿼리 수), 강력한 베이스라인(고전 오토마타 학습 알고리즘 L*, TTT)과 직접 비교할 수 있는 확장 가능한 테스트베드를 제공한다. 최신 LLM을 평가한 결과, DFA 크기가 커질수록 성능이 급격히 떨어졌다. 추론(reasoning) 모델은 비추론 모델보다 뚜렷하게 강했지만, 궤적 분석은 쿼리 계획, 증거 통합, 가설 구성에서 반복되는 실패를 드러냈다.
방법론
능동 오토마타 학습 배경
오토마타 학습은 학습 알고리즘이 어떤 문자열이 수락(accept)되고 거부(reject)되는지에 대한 관찰로부터 숨겨진 DFA의 구조를 발견할 수 있는 정도를 측정한다. 크게 두 가지 패러다임으로 나뉜다. 능동 오토마타 학습에서는 학습자가 오라클에 쿼리를 던지며 상호작용하고, 수동 오토마타 학습에서는 고정된 레이블 예시 집합으로부터 DFA를 추론한다.
능동 설정에서 학습자는 적응적으로 선택한 쿼리를 통해 숨겨진 DFA를 식별한다. 전통적으로 두 종류의 쿼리가 있다. 멤버십 쿼리는 주어진 단어가 숨겨진 DFA에 의해 수락되는지를 묻고, 등가성 쿼리는 가설 DFA가 숨겨진 DFA와 등가인지 검증하며 반례로 반박될 수 있다.
L*와 TTT 같은 고전 학습기는 반복적인 가설 정제 과정으로 이 과제를 푼다. 등가성 쿼리로 모든 관찰을 만족하는 가설을 제시하고, 반례가 반환되면 다항식 개수의 멤버십 쿼리를 사용해 새로운 가설을 구성하되 적어도 하나의 새로운 상태를 추가한다. 이 알고리즘들은 다항 시간에 숨겨진 DFA로 수렴함이 증명되어 있다. 이는 관찰된 행동의 메모리 유지, 그 위에서의 추론, 이전 상호작용 기반 행동 선택, 새 정보 적응 같은 바람직한 에이전트 특성을 보여준다.
이 논문은 또한 수동 학습 알고리즘을 LLM 에이전트가 상호작용 중 수집한 정보를 평가하는 도구로 사용한다. 에이전트가 수집한 레이블 단어들이 주어졌을 때, 수동 학습기(RPNI, EDSM, Blue-Fringe)가 이미 숨겨진 DFA를 추론할 수 있는지 검사한다.
Agentic Automata Learning 정의
알파벳을 Σ, 그 위의 모든 DFA 집합을 D, 목표 언어 L을 유도하는 최소 DFA를 A라 하자. 에이전트는 일련의 도구 호출(각각 쿼리라 부른다)을 통해 오라클 O_A와 상호작용한다. 각 시점 t에서 에이전트는 두 도구 호출 중 하나를 선택한다. 멤버십 쿼리는 단어 w에 대해 오라클이 그 단어의 수락 여부를 반환하고, 등가성 쿼리는 가설 DFA에 대해 L(A)=L이면 수락을, 다르면 반례를 반환한다.
시점 t에서 에이전트의 프롬프트는 전체 상호작용 히스토리를 담는다.
각 쿼리는 발행된 행동과 오라클 응답의 쌍으로 누적된다. 에이전트의 목표는 L(A)=L인 가설로 등가성 쿼리를 발행해 목표 언어를 식별하는 것이다. 상호작용은 쿼리 예산 T 안에서 등가성 쿼리가 수락되면 성공이며, 비용은 수락된 등가성 쿼리까지 발행된 쿼리 수다. 상호작용의 복잡도는 A의 상태 수로 정의한다.
이 프레임워크의 핵심 장점은 과제 인스턴스를 절차적으로 임의 규모로 생성할 수 있다는 점이다. 구체적으로 이진 알파벳 위 접근 가능한(accessible) DFA 공간에서 균등하게 샘플링하는 Boltzmann 샘플링을 사용하고, 비최소(non-minimal) DFA를 걸러내기 위해 거부 샘플링을 적용한다. 이 절차적 구성은 고정된 사전 정의 과제 풀이나 값비싼 사람 주석에 의존하지 않고, 선택한 알파벳 위에 임의로 많은 환경을 만들 수 있게 한다.
이 과제는 핵심 에이전트 능력을 측정한다. 적응적 계획은 각 쿼리 후 환경 피드백을 받아 목표 DFA의 불확실성을 줄이는 다음 쿼리를 선택해야 하므로 필요하다. 관찰로부터의 추론은 누적된 상호작용 히스토리가 수락·거부 단어로 이루어진 수동 데이터셋을 형성하므로 필요하다. 메모리 조직화는 이전 관찰과의 일관성을 유지하고 알려진 증거와 모순되는 가설이나 답이 이미 함의된 쿼리를 피해야 하므로 필요하다. 도구 사용은 상호작용이 유효한 입력으로 올바르게 호출해야 하는 멤버십·등가성 쿼리를 통해 매개되므로 필요하다.
실험 설정
6개의 최신 모델을 평가했다.
| 모델 | 특징 |
|---|---|
| DeepSeek-V4-Pro | 1.6T 파라미터 모델 |
| Gemini 3.1 Pro Preview | 추론 모델 |
| Gemini-3-Flash-Preview (thinking) | 일부 단계에서만 추론 적용 |
| Gemini-3.1-Flash-Lite-Preview | 비추론 |
| GPT-5.4 (without thinking) | 비추론 |
| Llama-3.3-70B-Instruct-Turbo | 오픈소스, 비추론 |
GPT 추론 변형은 전체 평가 실행의 계산 비용이 크게 높아 주 평가에 포함하지 않았다. 난이도별 한 인스턴스의 예비 샘플에서도 이 변형이 평가된 추론 모델들과 크게 다른 성능을 보일 가능성은 나타나지 않았다.
모델 성능은 두 측면으로 평가한다. 첫째, 성공률(Success Rate)은 모델이 숨겨진 DFA를 성공적으로 식별하는 비율을 측정한다. 둘째, 상호작용 효율은 모델이 성공적으로 DFA를 찾을 때의 도구 호출 수와 고전 알고리즘(TTT)의 도구 호출 수 차이를 성공 실행에 대해 측정한다.
평가 데이터셋은 최소 DFA의 상태 수로 정의된 4개 복잡도 수준(2~3, 4~5, 6~7, 8~9)에 균등 분포된 80개 과제 인스턴스로 구성된다. 각 인스턴스는 수십에서 수백 개의 쿼리를 수반하고 수백만 토큰을 소비하는 긴 상호작용 실행을 요구한다. 런타임과 비용은 DFA 크기에 따라 가파르게 증가해, 실행당 약 20시간, 3천만 토큰, 50달러에 이른다. 전체 실험 스위트의 총 비용은 대략 1,200달러였다.
쿼리 예산은 각 인스턴스에서 해당 DFA에 대해 L와 TTT 중 더 나은 쪽이 요구하는 쿼리 수의 최대 2배로 정의한다. L는 O(|Σ|n²m) 쿼리를, TTT는 O(|Σ|n² + n log m) 쿼리를 사용하며, n은 최소 숨겨진 DFA의 상태 수, m은 최대 반례 길이다. 예산을 2배로 정의하면 할당된 쿼리 예산 내에 올바른 해가 존재함이 보장된다.
오라클의 반례 선택은 두 가지를 균형 있게 고려한다. 최소 반례 길이는 고전 학습 알고리즘의 런타임과 모델에 할당되는 쿼리 예산에 직접 영향을 준다. 동시에 최소 반례는 그보다 짧은 단어가 가설과 숨겨진 DFA를 구분하지 못한다는 암묵 정보를 제공한다. 따라서 짧은 반례를 무작위로 샘플링한다.
상호작용 히스토리에서는 사고 사슬(chain-of-thought) 추론을 단계 간에 보존하지 않는다. 외부에서 관찰 가능한 출력과 환경 피드백만 다음 단계로 전달해, 모델 간 비교 가능성을 유지하고 추론 토큰의 급격한 누적을 피한다. 모든 과제 인스턴스에서 최대 누적 컨텍스트가 해당 모델의 컨텍스트 윈도 용량 아래에 머물러, 성능이 컨텍스트 절단에 영향받지 않음을 확인했다.
주요 결과
복잡도에 따른 성능 저하
모든 모델의 성능은 최소 DFA의 상태 수가 증가할수록 하락했다. 8~9 상태 DFA에서는 어떤 모델도 25% 성공률을 넘지 못한 반면, 고전 알고리즘은 모든 과제 인스턴스를 100% 성공률로 푼다. 이 격차는 상호작용 효율에도 반영된다. 같은 8~9 상태 범위에서 성공 실행만 고려할 때, 최고 성능 모델인 Gemini 3.1 Pro는 TTT보다 약 45.8% 더 많은 도구 호출을 사용한다.
과제의 전반적 어려움과 함께, 프레임워크는 특히 4 상태 이상 오토마타에서 모델 간 큰 차이를 드러낸다.
| 모델 구분 | 4~5 상태 성공률 |
|---|---|
| Gemini 3.1 Pro (추론) | 85% |
| Gemini 3 Flash (부분 추론) | 15% |
| GPT-5.4 (비추론) | 0% |
| Gemini 3.1 Flash Lite (비추론) | 0% |
| Llama-3.3-70B (비추론) | 0% |
추론 메커니즘을 사용하는 모델과 그렇지 않은 모델 사이에 명확한 격차가 나타난다. 부분 추론을 적용하는 Gemini 3 Flash는 중간 수준의 성능을 보였고, 추론을 사용하지 않는 GPT-5.4, Gemini 3.1 Flash Lite, Llama-3.3-70B는 4 상태 이상에서 0% 성공률을 기록했다.
고전 알고리즘 모방 여부
LLM이 L*, TTT 같은 표준 알고리즘의 고전적 정식화로 사전학습되었을 수 있으므로, 강한 성능이 학습 과제를 상호작용으로 푸는 능력이 아니라 알려진 알고리즘 해의 암기나 모방을 반영할 수 있다는 우려가 있다. 저자들은 세 가지 방식으로 이 우려를 완화한다.
첫째, 고전 알고리즘은 결정적이므로 회복까지의 쿼리 시퀀스를 직접 비교해 정확한 모방을 검사할 수 있다. 어떤 과제 인스턴스에서도 모델이 고전 알고리즘과 동일한 쿼리 시퀀스를 만들지 않았으며, 일부 경우 모델이 고전 알고리즘보다 적은 쿼리로 목표 DFA를 회복했다.
둘째, 최고 성능 모델인 Gemini 3.1 Pro는 고전 알고리즘보다 등가성 쿼리(EQ)를 과도하게 사용한다. 고전 알고리즘에서는 등가성 쿼리 수가 숨겨진 DFA의 상태 수로 제한되는데, Gemini 3.1 Pro는 과제 인스턴스의 92.5%에서 이 한계를 초과했다.
셋째, Gemini 3.1 Pro의 행동은 고전 알고리즘이 만족하는 단조성(monotonicity) 속성을 위반한다. 단조성은 등가성 쿼리로 검증하는 모든 가설의 상태 수가 이전에 검증된 모든 가설보다 큰 경우 보존되는데, Gemini 3.1 Pro는 모든 상호작용에서 비단조 가설 시퀀스를 생성했다. 이는 모델이 단지 이들 알고리즘의 잡음 섞인 불안정한 변형을 구현하는 것이 아님을 보여준다.
논문은 “b를 적어도 하나 포함하는 모든 단어”를 수락하는 숨겨진 DFA에 대한 예시 상호작용을 제시한다. Gemini 3.1 Pro는 등가성 쿼리만으로 과제를 풀었고, Llama-3.3-70B, L*, TTT는 멤버십 쿼리와 등가성 쿼리를 모두 사용했다.
오류 분석과 비정보성 쿼리
모델 실패를 상호 배타적인 두 범주로 분류한다. 계획 실패(planning failure)는 모델이 실패하고 어떤 고전 수동 학습 알고리즘(RPNI, EDSM, Blue-Fringe)도 모델이 누적한 관찰로부터 숨겨진 DFA를 추론할 수 없을 때 발생한다. 이 경우 모델이 상호작용 중 충분한 정보를 수집하지 못했다고 가정한다. 추론 실패(reasoning failure)는 모델이 실패했지만 적어도 하나의 수동 학습 알고리즘이 누적된 관찰로부터 숨겨진 DFA를 추론할 수 있을 때 발생한다. 즉 필요한 정보는 있었지만 모델이 그로부터 올바른 DFA를 추론하지 못한 경우다.
모든 평가 모델이 추론 실패와 계획 실패를 모두 겪었다. 다만 더 강한 모델은 약한 모델에 비해 계획 실패 비율이 상대적으로 낮았으며, 약한 모델에서는 계획 실패가 지배적이었다.
비정보성 쿼리(non-informative query)는 그 답이 이전 오라클 응답으로 함의되어 새 증거를 제공하지 못하는 도구 호출이다. 멤버십 쿼리는 같은 단어가 이미 쿼리되었으면 비정보성이다. 등가성 쿼리는 이전 가설을 중복하거나, 제안된 DFA가 이미 알려진 증거와 모순되면 비정보성이다.
비정보성 쿼리는 상호작용이 길어질수록 점점 더 흔해진다. 약 60단계 이후에는 가장 일관적인 모델인 DeepSeek-V4-Pro조차 약 20%의 비정보성 쿼리를 발행한다. 이 패턴은 모든 평가 LLM에서 나타나는 반면, 고전 능동 학습 알고리즘은 구조적으로 0% 비정보성 쿼리를 유지한다. 이는 증거가 컨텍스트에 누적될수록 LLM 에이전트가 그것을 일관되게 조직·사용하는 데 점점 더 어려움을 겪음을 시사한다.
비용 분석
현대 LLM 평가의 핵심 질문은 계산 및 금전 비용이며, 이는 각 과제 인스턴스가 긴 상호작용 시퀀스를 수반하는 에이전트에서 특히 중요하다. 각 추가 상호작용은 컨텍스트 윈도를 늘리고 런타임을 더한다. 평가 프레임워크의 비용은 도구 호출 수에 따라 선형으로 증가하며, Gemini 3.1 Pro가 비용 대부분을 차지한다.
쿼리 예산의 필요성도 분석했다. 쿼리 예산을 늘리면 일반적으로 성공률이 향상되지만 그 효과는 모델에 크게 의존한다. Gemini 3.1 Pro 같은 일부 모델은 예산 증가에 따른 추가 이득이 작은 반면, 다른 모델은 크게 향상된다. 예를 들어 DeepSeek-V4-Pro는 0%에서 55% 성공률로 개선된다. 이는 예산이 작은 모델이 찾지 못했던 DFA를 풀 수 있게 하므로 예산이 중요함을 보여준다.
논문은 또한 이진 성공 지표를 보완하는 연속 유사도 측정인 Best Hypothesis Similarity를 정의한다. 가설 DFA h와 숨겨진 DFA x에 대해, 길이 k=200 이하의 모든 단어에 대한 대칭 차집합(symmetric-difference) 기반 유사도 근사를 계산한다. 이 지표는 두 DFA가 일치하는 단어의 비율을 측정해 [0, 1] 범위 점수를 산출하며, 곱 DFA(product DFA) 위 동적 계획법으로 효율적으로 계산된다.
한계와 주의사항
평가 프레임워크는 런타임, 토큰 사용, API 비용 면에서 비싸며, 이 비용은 과제 복잡도에 따라 증가한다. 전체 평가 스위트는 480회 실행에 약 1,200달러, 평균 데이터포인트당 2.50달러가 들었고, Gemini 3.1 Pro가 대부분을 차지했다. 이 비용 프로파일은 이 설정에만 국한되지 않는다. 최근 연구는 현대 LLM 벤치마크가 점점 더 큰 계산 비용을 수반함을 지적했으며, ProgramBench는 과제 인스턴스당 약 5달러로 이 프레임워크의 2배에 달하는 평균 비용을 보고했다.
향후 연구는 이 프레임워크를 DFA를 넘어 비결정성이나 확률성을 가진 환경으로 확장할 수 있다. 정확한 오라클 피드백 가정을 완화해 잡음 섞이거나 부분적·지연되거나 부정확한 신호를 도입하거나, 등가성 쿼리를 더 약한 피드백으로 대체할 수도 있다. 나아가 이 프레임워크는 추론 시점 평가뿐 아니라 강화학습 같은 학습 환경으로도 활용될 수 있다.
결론
이 논문은 언어 모델이 상호작용을 통해 숨겨진 구조를 추론할 수 있는지를 평가하는 통제된 프레임워크인 Agentic Automata Learning을 도입한다. 환경을 숨겨진 DFA로 모델링하고 멤버십·등가성 쿼리를 허용함으로써, 이 프레임워크는 최종 성공과 발견 과정 모두를 측정한다.
결과는 강한 모델조차 복잡도가 증가할수록 어려움을 겪으며, 정확도, 계획, 추론, 도구 사용, 누적 정보 관리에서 실패함을 보여준다. 현재 LLM 에이전트는 때때로 자명하지 않은 상호작용형 발견을 수행할 수 있지만, 이 과제에서 고전 알고리즘보다 견고성과 효율 모두에서 훨씬 떨어진다. 이 발견은 결과만이 아니라 에이전트가 어떻게 탐색하고 믿음을 갱신하며 피드백을 시간에 걸쳐 사용하는지를 검토하는 평가의 필요성을 동기 부여한다.