🤖 machine learning

Solver-Hard Is Not Model-Hard: A Hardness-Controlled Diagnostic for LLM Constraint Reasoning

본 논문은 정밀하게 통제된 밀도 일치 벤치마크를 통해 증명된 바와 같이, 대규모 언어 모델의 제약 추론 과제 수행 능력이 문제 인스턴스의 근본적인 솔버 난이도에 의해 결정되지 않는다는 것을 입증하며, 이는 증명 난이도 프록시와 모델 정확도 또는 토큰 지출 사이의 상관관계 결여를 통해 드러난다.

원저자: Lucky Verma

게시일 2026-07-21

📖 3 분 읽기☕ 가벼운 읽기

CC BY 4.0

원저자: Lucky Verma

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

당신이 초지능 로봇에게 논리 퍼즐을 푸는 법을 가르치려 한다고 상상해 보세요. 컴퓨터 과학의 세계에는 'SAT'(충족 가능성 문제)라고 불리는 유명한 유형의 퍼즐이 있습니다. 이것은 기본적으로 "이 거대한 규칙 목록의 모든 조건을 만족시키기 위해 빈칸을 '참(True)' 또는 '거짓(False)'으로 채울 수 있는가?"를 묻는 것입니다. 수십 년 동안 과학자들은 어떤 기묘한 현상을 목격해 왔습니다. 퍼즐이 너무 쉽지도, 그렇다고 불가능할 정도로 어렵지도 않은 딱 적절한 복잡함에 도달하면, 인간과 컴퓨터 모두 벽에 부딪힌다는 사실입니다. 이는 마치 뇌 속에 교통 체증이 일어나는 것과 같습니다.

이 현상을 이해하기 위해 연구자들은 보통 두 가지를 살펴봅니다. 첫째는 **밀도(density)**로, 이는 단순히 "규칙들이 얼마나 빽빽하게 들어차 있는가"를 뜻하는 세련된 표현입니다. 규칙이 좁은 공간에 많이 밀집되어 있으면 더 어렵게 느껴집니다. 둘째는 **구조적 난이도(structural hardness)**로, 이는 퍼즐의 숨겨진 형태에 관한 것입니다. 어떤 퍼즐은 단순해 보이지만 풀기 까다로운 뒤틀리고 엉킨 구조를 가지고 있어 빠르게 해결하는 것이 불가능한 반면, 어떤 퍼즐은 지저분해 보여도 그 안에 쉽고 곧은 경로가 숨겨져 있기도 합니다. 여기서 큰 의문은, AI 모델이 실패할 때 그 이유가 퍼즐이 너무 빽빽해서인지(밀도), 아니면 퍼즐의 숨겨진 형태가 너무 까다롭기 때문인지(구조) 하는 점입니다.

이 논문은 저자가 AI를 함정에 빠뜨리기 위해 매우 구체적인 덫을 놓은 한 편의 탐정 이야기와 같습니다. 연구자인 러키 버마(Lucky Verma)는 AI 모델이 논리 퍼즐의 "뒤틀린 형태"를 실제로 이해하고 있는지, 아니면 단순히 규칙이 얼마나 "빽빽한지"를 보고 추측하는 것뿐인지를 확인하고 싶었습니다. 이를 위해 그는 겉보기에는 거의 동일해 보이지만, 내부적으로는 비밀스럽게 매우 다른 두 가지 유형의 퍼즐을 만들었습니다. 두 퍼즐은 규칙의 개수와 "빽빽함"은 동일하지만, 한 유형은 구조가 단순하고 곧은 "사다리(Ladder)" 퍼즐이고, 다른 하나는 전통적인 컴퓨터에게는 악몽과도 같은 "익스팬더(Expander)" 퍼즐입니다. 익스팬더 퍼즐은 구조가 너무 엉켜 있어서 문제를 풀수록 점점 더 커지는 실타래를 푸는 것처럼 지수적인 노력이 필요합니다.

실험은 고전적인 컴퓨터 솔버(Glucose라는 도구)와 여러 대형 AI 모델(Llama 3.3, Llama 4, Mistral 3 등) 사이의 대결이었습니다. 먼저 고전적인 솔버를 테스트했습니다. 예상대로, 솔버는 "익스팬더" 퍼즐에서 엄청나게 고전했습니다. "사다리" 퍼즐에 비해 최대 51배 더 많은 노력(막다른 길에 부딪히는 순간인 "충돌"로 측정)을 들여야 했습니다. 솔버는 쉬운 형태와 어려운 형태의 차이를 명확히 인지하고 있었습니다.

이제 AI 모델들이 등장할 차례입니다. 만약 AI가 논리 전문가처럼 추론한다면, 고전적인 솔버와 마찬가지로 "사다리" 퍼즐은 더 쉽고 "익스팬더" 퍼즐은 더 어렵다고 판단해야 했습니다. 하지만 반전이 있었습니다. AI 모델들은 형태에 대해 전혀 신경 쓰지 않았습니다. 사실, 그들의 성능은 제각각이었습니다. 어떤 모델은 "사다리" 퍼즐을 더 쉽게 풀었고, 다른 모델은 "익스팬더" 퍼즐을 더 쉽게 풀었습니다. 그리고 이들을 모두 평균 냈을 때, 그 차이는 통계적으로 유의미하지 않은 아주 미미한 +1.7 포인트 차이에 불과했습니다. AI 모델들은 숨겨진 구조를 완전히 무시하고 있는 듯 보였습니다.

더 이상한 점은, 연구자들이 AI가 얼마나 많은 "생각 시간"(토큰, 즉 생성된 단어 수로 측정)을 사용하는지 확인했다는 것입니다. 우리는 AI가 어려운 "익스팽더" 퍼즐에 더 많은 시간을 쓸 것이라고 기대할 수 있습니다. 하지만 대신, AI는 종종 "사다리" 퍼즐에 더 많은 시간을 소비하거나, 가장 쉬운 퍼즐에서 막혀서 예산을 낭비하곤 했습니다. 또한 연구진은 AI가 퍼즐의 글자들을 섞어서(증명 보존 재라벨링, proof-preserving relabeling) 모양을 외워서 푸는 것인지도 테스트했습니다. 한 모델은 퍼즐의 순서만 바꿨을 뿐인데 성능이 거의 93 포인트나 폭락했습니다. 이는 해당 모델이 실제 논리가 아니라 표면적인 속임수에 의존하고 있음을 증명합니다.

결론적으로, 이러한 특정 퍼즐들에 대해 "솔버가 어렵다고 해서 모델이 어려운 것은 아닙니다(Solver-Hard is Not Model-Hard)." 어떤 퍼즐가 전통적인 컴퓨터에게 수학적으로 어렵다고 해서, 그것이 반드시 AI에게도 어렵다는 뜻은 아니며 그 반대도 마찬가지입니다. AI가 실패하는 이유는 퍼즐이 너무 어려워서가 아니라, 우리가 기대했던 것처럼 논리적 구조를 제대로 추적하지 못하기 때문입니다. 이는 마치 AI가 퍼즐을 보며 "이건 빽빽해 보이니 어려울 거야"라거나 "내가 전에 봤던 패턴이야"라고 말하며, 실제적인 깊은 구조적 작업을 수행하는 대신 표면적인 단서에 기반해 추측하고 있는 것과 같습니다. 이 연구는 AI 모델이 커진다고 해서 반드시 추론 능력이 향 beğ해진다고 가정해서는 안 된다는 점을 시사합니다. 때때로 그들은 단지 표면적인 단서를 바탕으로 추측하는 데 더 능숙해지고 있을 뿐입니다.

기술 요약: 솔버-하드(Solver-Hard)는 모델-하드(Model-Hard)가 아니다

문제 정의
불리언 만족 가능성(SAT) 및 제약 충족 문제(CSP)에 대한 현재의 대규모 언어 모델(LLM) 평가는 두 가지 별개의 속성인 절(clause) 밀도(변수 대비 절의 비율, $\alpha = m/n$ )와 증명 복잡도(불만족 사례를 반박하는 구조적 난이도)를 혼동하는 경우가 많다. 균일 무작위 공식(uniformly random formulas)에서 이러한 속성들은 만족 가능성 상전이(satisfiability phase transition) 근처에서 함께 변하기 때문에, 모델의 실패가 표면적인 밀도 단서에 의한 것인지 아니면 근본적인 알고리즘적 난이도에 의한 것인지 판단하는 것이 불가능하다. 이러한 혼재는 LLM이 인스턴스 수준의 탐색 비용을 추적하는 것인지, 아니면 단순히 밀도 임계값과 관련된 질적 실패 곡선을 재현하는 것인지에 대한 모호함을 야기한다.

방법론
저자들은 통제된 해리(dissociations)를 사용하여 절 밀도를 증명 복잡도로부터 분리하는 구성 타당성 진단법을 제안한다. 실험 설계는 다음 세 가지 주요 대조군에 의존한다:

C1 (핵심 대조): 거의 일치하는 절 밀도( $\alpha \approx 2.67$ $α \approx 2.67$ )와 최대 절 너비(3)를 가지지만, 해상도(resolution) 난이도가 다른 두 가지 그래프 구조상의 테이신(Tseitin) 공식을 비교함:
- 익스팬더 그래프(Expander Graphs): 지수적 해상도를 요구하는 3-정규 익스팬더 (증명-하드).
- 래더 그래프(Ladder Graphs): 다항식 증명을 허용하는 트리에 수(treewidth) 2의 그래프 (증명-이지).
C2 (밀도 제어): 저밀도 익스팬더 테이신 공식과 고밀도( $\alpha \approx 6$ ) 무작위 UNSAT 공식을 비교함. 후자는 높은 밀도에도 불구하고 CDCL(Conflict-Driven Clause Learning) 솔버에게 구조적으로 쉬운 편이다.
C3 (비둘기집 원리 앵커): 그래프 구조가 없는 또 다른 증명-하드 앵커로서 비둘기집 원리(Pigeonhole Principle, PHP) 공식을 사용하며, 이를 무작위 UNSAT과 대조함.

솔버 검증:
LLM을 평가하기 전, 저자들은 이 해리 구조를 Glucose CDCL 솔버(및 5개의 다른 솔버)를 통해 검증했다. 저자들은 반박 비용의 솔버 특이적 프록시로 **충돌 횟수(conflict count)**를 측정했다. 구축된 구조는 솔버의 비용을 성공적으로 분리해 냈다: 크기가 일치할 때, 익스팬더와 래더 공식 사이의 중앙값 충돌 비율은 단조 증가하여 가장 큰 빈(bin)에서 최대 51배에 달했다. 고밀도 무작위 UNSAT 공식은 여전히 솔버에게 가장 쉬운 것으로 나타나, 밀도와 솔버 비용이 서로 분리되어 있음을 확인했다.

LLM 평가 프로토콜:

모델: Llama 3.3 70B, Llama 4 Maverick 17B, Mistral Large 3 675B(모두 자기회귀 트랜스포머)를 온도 0으로 평가함. gpt-oss-120b는 높은 기권율(abstention rate)로 인해 제외됨.
태스크: 모델들에게 243개의 인스턴스(각 모델당 60개, PHP 앵커 3개 포함)에 대해 이진 SAT/UNSAT 판정을 내리도록 함.
지표: 판정 정확도(기권은 오답으로 처리), 증명-하드와 증명-이지 패밀리 간의 정확도 격차, 그리고 정확도와 솔버 충돌 횟수 간의 상관관계.
토큰 소비 분석: 사전 등록된 확장 연구를 통해, 제공자가 보고한 완료 토큰(테스트 시간 연산량의 프록시)이 공식 길이와 검열을 통제했을 때 솔버 비용을 추적하는지 분석함.

주요 결과

전이의 실패(Failure of Transfer): 고전적 솔버에서 관찰된 난이도 순서가 LLM으로 전이되지 않았다.
- 정확도 격차: 예측된 난이도 격차(Ladder > Expander)는 일관되지 않았다. Llama 3.3은 예측된 방향대로 +20 포인트의 격차를 보였으나, Llama 4는 -32 포인트의 격차(역전됨)를 보였고, Mistral 3는 +17 포인트를 보였다. 통합된 격차는 +1.7 포인트( $p=0.74$ )로, 유의미한 전이 효과를 위한 사전 지정된 임계치를 충족하지 못했다.
- 상관관계: 솔버 충돌 횟수와 모델 정확도 사이에는 음의 연관성이 없었다. 대신, 통합된 상관관계는 약한 양의 상관관계( $r = +0.15$ )를 보여, 높은 솔버 비용이 낮은 모델 정확도를 예측하지 못함을 나타냈다.
- 밀도 vs 난이도: 모델들은 고밀도 무작위 UNSAT 패밀리(솔버에게 가장 쉬운 패밀리)에서 가장 낮은 성능을 보였으며, 이는 밀도나 증명 복잡도 중 어느 것도 모델의 오류를 일관되게 예측하지 못함을 더욱 입증한다.
표면 민감도(Surface Sensitivity): 증명을 보존하는 재라벨링 실험(논리적 구조를 변경하지 않고 변수와 절을 섞음)은 모델별 표면 민감도를 드러냈다. L

Llama 3.3의 경우, 재라벨링 후 모든 클러스터에서 평균 93 포인트의 정확도 하락이 발생한 반면, Llama 4는 거의 영향을 받지 않았다. 이는 모델이 논리적 구조보다는 표면적 형태에 의존할 수 있음을 시사한다.

토큰 소비의 해리(Token Spend Dissociation): 관찰된 완료 토큰 소비량은 솔버 비용과 일관되게 증가하지 않았다.
- 16k 토큰 예산에서, 추론 모델(Nemotron)은 증명-하드인 익스팬더 공식보다 증명-이지인 래더 공식에서 더 많은 토큰을 소비했다.
- 가장 심각한 토큰 소비(16k 제한 도달)는 정확도가 거의 0에 가까웠던 솔버에게 가장 쉬운 패밀리(무작위 UNSAT)에서 발생했다.
- 길이를 통제한 토큰과 솔버 충돌 간의 상관관계는 일반적으로 음수이거나 무효했으며, 모델이 구조적으로 더 어려운 인스턴스에 더 많은 연산을 할당한다는 것을 보여주는 데 실패했다.

의의 및 주장
본 논문은 테스트된 범위 내에서 **"솔버-하드는 모델-하드가 아니다(Solver-Hard Is Not Model-Hard)"**라고 결론짓는다. 주요 기여는 클래식 CDCL 솔버로 검증된 인스턴스 난이도(증명 복잡도로 정의됨)가 절 밀도가 통제되었을 때 LLM의 판정 정확도나 토큰 할당을 예측하지 못한다는 것을 보여주는 제한된 범위의 진단법이다.

구성 타당성: 본 연구는 상전이 근처의 무작위 공식을 사용하는 기존 평가들이 추론 능력보다는 밀도 단서에 대한 민감도를 측정하고 있을 수 있음을 보여준다.
한계점: 저자들은 이 결과가 추론 실패에 대한 보편적 이론이나 자기회귀 아키텍처에 대한 불가능성 증명이 아님을 명시적으로 밝힌다. 결과는 특정 규모(12~30 변수), 사용된 특정 공식 패밀리, 그리고 테스트된 모델들에 국한된다.
시사점: 증명 복잡성 때문에 LLM이 실패한다는 주장은 통제된 해리 하에서 난이도 순서가 전이됨을 먼저 입증해야 한다. 현재의 증거는 클래식한 난이도 순서가 모델의 성능이나 토큰 할당을 예측하는 신뢰할 만한 지표가 아니며, 모델이 공식 직렬화의 표면적 변화에 매우 민감할 수 있음을 시사한다.

기술 요약: 솔버-하드(Solver-Hard)는 모델-하드(Model-Hard)가 아니다

유사한 논문