대형 언어모델의 ‘절차적 추론’은 환상? FSM 시험지로 드러난 장기 계산력 한계와 실용적 돌파구

안녕하세요! 오늘은 최신 논문 “THE ILLUSION OF PROCEDURAL REASONING: MEASURING LONG-HORIZON FSM EXECUTION IN LLMS”를 바탕으로, 대형 언어 모델(LLM)의 절차적 추론 능력을 조명해보려고 합니다. 논문의 주요 아이디어와 함께 기존 연구들과의 차별점, 그리고 실제 LLM 기술 발전에 주는 시사점을 얘기해볼게요!

---

1. 절차적 추론, LLM들은 정말 잘할까?

요즘 LLM들이 퀴즈 풀고 논리 문제 푸는 모습을 보면 ‘와, 진짜 사고하나?’ 싶은 순간이 많죠. 하지만 진짜 ‘절차적 추론(순서대로 규칙을 따라가는 계산)’ 능력은 어떨까요? 알고리즘처럼 딱딱 정해진 룰을 따라가는 문제는 우리 프로그래머들도 디버깅이 쉽지 않은데, LLM도 과연 문제 없이 ‘길게 이어지는 단계’를 완벽히 소화할 수 있을지 궁금했습니다.

 

바로 이 지점에서 이 논문은 ‘ Finite-State Machine(유한 상태 기계, FSM)’라는 아주 엄격하고 명확한 시험지를 만들어서 LLM 능력을 까다롭게 테스트했습니다. FSM은 어떤 상태에서 어떤 액션을 받으면 그 다음 상태로 딱 넘어가야 하는데, 이걸 흐트러짐 없이 몇십 단계, 혹은 수백 단계도 유지해야 하니까 ‘진짜 절차적 계산력’을 확인하는 데 최적이죠.

---

2. 기존 LLM 추론 테스트와 다른 점

많은 과거 연구들은 LLM이 ‘추론을 한다’고 평가할 때, 보통 흔히 볼 수 있는 퀴즈, 논리 퍼즐, 혹은 체인 오브 쏘트(CoT) 방식처럼 문장을 나누며 생각하는 모습을 관찰했죠. 그런데 이런 문제들은

• 계단식 문제가 아니라 중간에 패턴을 외우거나 쉽게 예상 가능한 경우가 많고,
• ‘절차적 실행’이 아니라 ‘패턴 인식 + 암기’가 큰 비중이고,
• 중간 중간 정답을 알려주는 ‘힌트’가 들어가면서 테스트가 완전히 순수하지 않은 경우가 많습니다.

이 논문은 그런 점을 완전히 빼내고 ‘절차적 계산만’ 강조한 FSM 환경에서, 매 턴마다 정확한 상태 전이가 이루어졌는지, 그리고 ‘초반부터 끝까지 완벽히 절차를 따라갔는지’ 엄격히 평가해 신선합니다.

---

3. 논문의 핵심 기술 가치: FSM 실행 능력 측정 체계

논문에서 제안한 핵심 기술 포인트는 다음과 같습니다:

• 완전한 명시적 FSM 정의 제공: 상태, 액션, 전이 규칙을 전부 줘서 ‘모른다’, ‘추론 모호성’이 전혀 없도록 환경이 완벽히 통제됨.
• Turn Accuracy (즉시 계산 능력) + Task Accuracy (장기적 상태 유지 능력) 분리 평가: 순간순간 계산은 맞출 수 있지만 길게 보면 틀리는 점, 다시 말해 ‘절차적 기억 유지’ 문제를 명확히 구분.
• 상태 공간(State space) vs 액션 공간(Action space)의 복잡도 영향 분석: 2상태에 액션 40개 대 40상태에 액션 2개에서 LLM 성능이 극명하게 갈리는 복잡도 모델 제안.
• Multi-step action 문제(한 번에 여러 액션 처리 시도)의 치명적 어려움 발견: 내부적으로 여러 절차 실행을 한 번에 하려 하면 잘 틀리는데, ‘중간 생각 꼼꼼히 적기(think aloud prompt)’로 일부 완화 가능.

---

4. 눈여겨봐야 할 의외의 발견들

① 큰 모델도 50% 정도에 머무르는 장기 절차 추론 한계

 논문 데이터에 따르면 모델 크기가 커질수록 짧은 계단식 추론은 좋아지지만, 오래가면 절반의 성공률도 안 되는 모습을 보입니다. ‘규모 확장만으로 한계 극복 어렵다’고 적혀 있는데, 이 점이 기술적으로 아주 중요해요.

 

② 상태가 적고 액션이 많은 ‘넓고 얕은 FSM’이 더 어려움!

 상식과 달리 액션 종류가 너무 많으면 주문 하나하나 어떤 상태로 가야 할지 ‘룰 찾기’가 매우 힘들어서 오히려 상태가 많고 액션은 적은 ‘깊고 좁은 FSM’이 더 쉽다는 사실! 이건 LLM의 메모리보단 룰 검색 알고리즘 한계 때문인데, 설계할 때 중요한 힌트입니다.

 

③ 한 번에 여러 액션 처리할 때 정확도 급락, 하지만 ‘중간 산출물 외부화’가 해결책

 LLM들이 머릿속으로 한번에 여러 연산을 수행하는 건 여전히 빡센데, ‘생각하는 과정 명시적 적기’(reasoning prompting)를 시키면 성능 회복 가능 부분이 있어요. 즉, ‘내부 계산’만 믿지 말고 ‘생각 과정을 기록하라’는 실용적 시사점을 줍니다.

---

5. 실제 AI 기술 개발에 주는 시사점

• LLM을 이용한 복잡한 절차 자동화, 워크플로우 설계에서 액션이 적고 상태가 많은 단계적 분할이 더 효과적!
  몇 단계에 걸쳐 복잡한 판단 내리는 코딩 어시스턴트, 자동화 봇 설계자라면 ‘넓고 복잡한 분기’를 피하고 ‘좁고 단계별’ 처리로 시스템을 설계해야 강건해진다는 깨달음.
• 단순히 모델 사이즈만 키우는 스케일 업 전략은 한계 명확
  거대 모델 들어가면 국부일처리는 좋아지지만 장기간 절차적 상태 유지 성능은 아직 미묘해서, 구조적 보완책(메모리 모듈, 명시적 상태 관리)이 필수임을 실험적으로 입증.
• 프롬프트 설계 시 ‘계산 중간 과정 기록’ 같은 메타-프롬프트를 쓰는 게 절대적 필요
  LLM의 추론 과정 눈에 보이게 하여 오류 축적 방지하고 복잡한 절차 안정화하는 방향성은 ‘기초 테크닉’으로 자리 잡아야겠어요.

---

6. 마치며

이번 논문은 LLM이 진짜 ‘절차적 추론’을 한다는 환상에서 벗어나, 그 한계와 구조적 약점을 명확히 보여주는 기술적 진단기라 할 수 있습니다. 또, FSM이라는 엄격한 ‘계산 실험실’을 통해 LLM 내적 계산력에 대한 정량적 평가를 가능케 했다는 점에서 연구·실무 양쪽에 큰 가치를 줍니다.

 

여러분이 AI 기술을 직접 다루거나 앞으로 복잡한 추론 태스크에 LLM을 활용하려 한다면, ‘무조건 큰 모델’ 대신 ‘절차 분해, 상태-액션 설계, 중간 거치기’에 주목하는 게 현명한 길이라는 점 꼭 기억해 주세요!