LLM을 이용한 충족 가능성 문제 해결: 추론 능력에 대한 매칭 쌍 평가

대규모 언어 모델 (LLMs)은 불리언 충족 가능성 (Boolean satisfiability, SAT) 문제로 암묵적으로 귀결되는 작업에 점점 더 많이 사용되고 있지만, SAT에 대한 이들의 추론 능력은 여전히 불분명합니다. 우리는 표현 불변적 추론 (representation-invariant reasoning)을 조사하기 위해 2-SAT 및 3-SAT, 그리고 두 가지 정형적 환원 (canonical reductions)인 정점 커버 (Vertex Cover) 및 이산 3D 패킹 (discrete 3D packing)을 사용하여 LLM에 대한 체계적인 연구를 제시합니다. 우리는 먼저 정확도 (accuracy), 정밀도 (precision), 재현율 (recall), F1 스코어 (F1 score)를 포함한 전통적인 지표와 SAT 상전이 (phase-transition) 설정을 사용하여 모델을 평가합니다. 우리는 이러한 지표들이 오해를 불러일으킬 수 있음을 발견했습니다. 많은 모델이 충족 가능한 공식을 과도하게 예측함으로써 높은 점수를 얻고, 3-SAT 임계값 주변의 고전적인 easy-hard-easy 시그니처를 재현하는 데 실패하며, 변수의 수가 증가함에 따라 성능이 급격히 저하됩니다. 이 문제를 해결하기 위해, 우리는 최소한으로 차이가 나는 충족 가능 및 불충족 인스턴스에 기반한 쌍 공식 프로토콜 (paired-formula protocol)과 함께, 각 쌍의 두 구성 요소가 모두 올바르게 분류되어야 하는 정확한 차별화율 (Accurate Differentiation Rate, ADR)을 도입합니다. ADR은 휴리스틱 (heuristic) 모델과 추론 지향적 모델을 구분하며 증거 유효성 (witness validity)과 상관관계가 있습니다. CNF를 넘어, 우리는 CNF를 정점 커버 (Vertex Cover)로, 3-SAT를 이산 3D 패킹 (discrete 3D packing)으로 변환하여 교차 표현 일관성 (cross-representation consistency)을 테스트합니다. CNF와 그에 상응하는 그래프 또는 패킹 인스턴스에 대한 모델의 결정은 대부분의 모델에서 인스턴스의 80% 이상에서 일치하며, 이는 표현 전반에 걸쳐 안정적인 결정 규칙이 존재함을 시사합니다. 전반적으로, 우리의 결과는 SAT가 LLM 추론에 대한 보수적인 프로브 (probe)임을 보여주며, ADR을 이용한 쌍 평가가 전통적인 지표보다 더 충실하고 표현에 강건한 (representation-robust) 평가를 제공함을 보여줍니다.