자연어로 말하면 QUBO 식이 나온다, 그 사이를 누가 메울까

이번에 다룰 논문은 Automating Quadratic Unconstrained Binary Optimization (QUBO) Formulation Generation from Natural Language이며, arXiv 2609.10629로 공개된 연구입니다. 이 연구는 자연어로 적힌 조합 최적화 문제를 QUBO 정식화로 자동 변환하는 종단간 멀티 에이전트 프레임워크를 제안하고, 100문제 규모의 QUBOBench에서 68퍼센트 정확도를 보고합니다. 원문은 제목 아래에 연결되어 있으니, 이 글에서는 그 내용이 실제로 무엇을 뜻하는지 차근차근 따라가 보겠습니다.

안녕하세요, 패트릭입니다.

수학 식으로 바꾸는 일은 왜 늘 사람 몫이었을까

저는 이 논문을 읽기 전에 먼저 제 주변을 떠올렸습니다. 현장에서 최적화 문제를 만나는 사람들은 대개 문장으로 말하는데, 배송 트럭은 다섯 대뿐인데 주문은 스무 군데에서 들어왔고 어떤 손님은 오전에만 받을 수 있다고 말하죠. 공장의 기계는 세 대인데 작업은 열 개가 밀려 있고, 어떤 작업은 같은 기계에서 연달아 할 수 없다고도 합니다. 이런 설명은 사람에게는 분명하지만, 이 설명을 컴퓨터가 풀 수 있는 형태로 바꾸는 순간 갑자기 전문가가 필요해집니다. 변수를 무엇으로 둘지, 제약조건을 어떻게 쓸지, 목적식은 무엇을 최소화할지 정해야 하기 때문입니다.

그렇다면 이 변환 과정을 기계가 대신할 수 있을까요. 제가 이 논문에서 가장 흥미롭게 본 부분은 바로 이 질문을 정면으로 다룬다는 점입니다. 연구팀은 자연어 설명과 테스트 케이스가 주어졌을 때, QUBO라는 특정 수학 형식까지 자동으로 도달하는 파이프라인을 만들었다고 말합니다. 말로 설명하면 답이 나오는 마법이 아니라, 말로 설명하면 풀 수 있는 식이 나온다는 주장인데요. 이 차이는 생각보다 중요합니다. 답을 직접 내는 모델은 틀리면 끝이지만, 식을 만드는 모델은 만든 식을 검증하고 고칠 여지가 남기 때문입니다.

그렇다면 QUBO라는 언어는 무엇을 요구할까

QUBO를 처음 접하면 이름부터 낯설게 느껴집니다. Quadratic, Unconstrained, Binary, Optimization을 줄인 말인데, 말 그대로 이진 변수로 된 제약 없는 이차 최적화 문제라는 뜻입니다. 변수는 0 또는 1만 가질 수 있고, 풀어야 할 식은 일차항과 이차항으로 이루어진 하나의 에너지 함수라서 에너지를 가장 낮게 만드는 0과 1의 조합이 곧 답이 됩니다. 저는 이 구조를 일종의 번역 규칙처럼 이해했는데, 세상의 복잡한 규칙을 전부 0과 1의 선택 문제로 옮겨 적는 규칙이라고 보면 됩니다.

그런데 이 번역이 까다로운 이유는, 원래 문제에는 제약조건이 있기 때문입니다. 예를 들어 한 트럭이 두 경로를 동시에 갈 수는 없다는 조건, 기계 하나가 같은 시간에 두 작업을 할 수 없다는 조건이 그렇습니다. QUBO에는 제약조건을 따로 쓸 자리가 없으므로 제약을 목적식에 페널티 항으로 녹여야 합니다. 제약을 어기면 에너지가 크게 올라가도록 벌점을 주는 방식입니다. 이때 벌점을 얼마나 크게 줄지가 바로 페널티 가중치 문제인데, 너무 작으면 모델이 제약을 무시하고 엉뚱한 답을 내놓고, 너무 크면 진짜로 좋아야 할 답까지 가려버립니다. 논문이 말하는 대로라면, 자연어를 QUBO로 바꾸는 일은 이진 변수 식별과 제약조건 해석, 목적함수 구성, 페널티 항 설계, 가중치 선택이 한꺼번에 맞아야 하는 작업입니다. 하나만 어긋나도 식 전체가 조용히 틀어지죠. (조용히라는 말이 어울리는 이유는, 식은 돌아가는데 답만 살짝 이상해지는 경우가 많기 때문입니다.)

한 번에 답을 쓰게 하면 왜 무너질까

여기서 재미있는 질문이 생깁니다. 언어 모델이 글을 잘 쓰는데, QUBO 식 정도는 한 번에 써낼 수 있지 않을까요. 연구팀도 이 가능성을 그냥 넘기지 않고 직접 비교했는데, 자연어 설명을 주고 한 번의 호출로 QUBO를 생성하는 직접 베이스라인을 세운 뒤 자신들의 멀티 에이전트 방식과 나란히 평가했습니다. 결과만 놓고 보면 직접 방식도 아주 못 쓰지는 않았을 겁니다. 짧고 정형화된 문제에서는 그럴듯한 식이 나왔을 테니까요.

문제는 그다음입니다. 문제가 길어지고 제약이 얽히기 시작하면, 한 번에 쓰는 방식은 앞에서 만든 변수 정의를 뒤에서 잊어버립니다. 앞에서 x3을 트럭 배정 여부로 썼는데, 뒤에서는 x3을 시간대 선택으로 쓰는 셈인데요. 페널티 항도 비슷합니다. 제약이 세 개인데 두 개만 식에 반영되거나, 가중치가 전부 같은 값으로 뭉개지는 경우가 생깁니다. 생각해보면 사람도 비슷하게 실수하는데, 긴 수식을 한 번에 암산으로 쓰려 하면 중간에 부호 하나를 빠뜨리곤 합니다. 그래서 저는 이 대목에서 논문의 문제의식에 공감했습니다. 어려운 것이 모델의 지능이 아니라, 한 번에 너무 많은 결정을 몰아넣는 구조라는 지적이기 때문입니다. 이 구조를 그대로 두면 모델이 커져도 같은 실수가 반복될 가능성이 큽니다.

여러 에이전트로 나누면 무엇이 달라질까

그렇다면 일을 나누면 어떻게 될까요. 연구팀이 제안한 틀은 종단간 멀티 에이전트 프레임워크인데, 하나의 거대한 호출 대신 역할을 나눈 여러 에이전트가 순서대로 정식화를 만들어간다고 이해하면 됩니다. 누군가는 문장에서 결정해야 할 선택지를 뽑아 이진 변수로 정의하고, 다른 누군가는 제약조건을 가려내어 페널티 형태로 바꾸고, 또 다른 누군가는 목적식을 정리합니다. 그리고 마지막에는 전체 식이 서로 모순 없이 맞물리는지 점검합니다. 마치 번역팀이 일하는 방식과 비슷합니다. 초벌 번역가가 원문을 옮기면, 용어 검수자가 변수 이름을 통일하고, 편집자가 전체 문장을 다듬는 셈이죠.

저는 이 구조보다 그 뒤의 태도가 더 중요하다고 봅니다. 일을 나눈다는 것은 중간 산출물을 눈에 보이게 만든다는 뜻이기 때문입니다. 한 번에 쓰는 방식에서는 모델 머릿속에서 변수 정의와 페널티 설계가 뒤섞여서, 어디서 틀렸는지 알기 어렵습니다. 반면 역할을 나누면 변수 정의가 잘못됐는지, 페널티 변환이 잘못됐는지, 가중치가 잘못됐는지를 따로 물을 수 있습니다. 디버깅이 가능해진다는 말인데요. 실제 시스템 관점에서 보면 다음 질문이 바로 생깁니다. 나눈 만큼 호출 횟수와 대기 시간은 늘어나는데, 그 비용을 감당할 만큼 정확도가 올라갈까. 논문이 제시한 숫자는 이 질문에 대한 답으로 읽어야 합니다. 구조를 바꾼 대가가 아니라, 구조를 바꾼 값어치를 묻는 숫자입니다.

테스트 케이스가 옆에 있으면 왜 든든할까

이 프레임워크에서 제가 눈여겨본 장치는 테스트 케이스입니다. 입력으로 자연어 설명만 주는 것이 아니라, 문제를 곁에서 받쳐주는 작은 예제들을 함께 준다는 설정인데요. 처음에는 이게 왜 필요할까 싶을 수 있습니다. 식을 만드는 데 예제가 왜 필요하냐는 의문이 생깁니다. 그런데 막상 식을 써보면 예제의 쓸모가 바로 드러나는데, 예제는 정답 그 자체라기보다 만든 식이 제대로 작동하는지 두드려볼 수 있는 망치에 가깝습니다.

구체적인 장면을 떠올려보겠습니다. 오전 배송만 가능한 손님이 있다는 조건이 문장에 있었다고 합시다. 모델이 만든 QUBO 식에 이 조건이 빠졌다면, 테스트 케이스 중 오전 배송을 어긴 가짜 해가 에너지가 낮은 채로 통과해버립니다. 그러면 식이 잘못됐다는 신호가 바로 옵니다. 반대로 페널티 가중치가 너무 커서 정상적인 해까지 막고 있다면, 멀쩡한 예제 해의 에너지가 비정상적으로 높게 나오면서 역시 신호가 옵니다. 저는 이 과정을 오답 노트처럼 이해했는데, 틀린 이유를 말로만 고민하는 대신 작은 문제로 직접 부딪혀보는 과정이라고 보면 됩니다. 물론 테스트 케이스가 완벽할 수는 없습니다. 예제가 원래 문제의 일부만 비추고 있을 수도 있고, 예제 자체가 편향되어 있을 수도 있습니다. 그래서 테스트 케이스는 안전벨트이지 자동운전에 가깝지 않습니다. 그래도 안전벨트가 있고 없고의 차이는 실제 사고율에서 드러나죠. 이 논문의 반복 수정 이야기도 같은 맥락에서 읽힙니다.

고치고 다시 풀면 왜 정확도가 올라갈까

연구팀의 분석에서 가장 눈길을 끄는 대목은 반복적인 자기 수정이 성능 향상에 가장 크게 기여했다는 점인데, 한 번 쓰고 끝내는 대신 만든 식을 실행해보고 틀린 부분을 고쳐서 다시 만드는 고리가 전체 정확도를 끌어올렸다고 합니다. 저는 여기서 조금 멈칫했습니다. 보통은 더 정교한 변수 추출이나 더 좋은 가중치 선택 같은 장치가 주인공이 될 거라고 예상하기 때문입니다. 그런데 주인공은 의외로 평범한 되돌아보기였습니다.

곰곰이 생각해보면 그럴 만도 합니다. QUBO 정식화는 한 번에 맞추기 어려운 작업이고, 실수는 특정 지점에 몰리기 때문입니다. 변수 이름이 뒤에서 바뀌었다면 고치면 되고, 빠진 제약이 있다면 더하면 되고, 가중치가 어긋났다면 조절하면 됩니다. 처음부터 완벽한 식을 쓰는 능력과, 틀린 식을 보고 어디가 틀렸는지 짚는 능력은 서로 다른 능력인데요. 자기 수정 고리는 후자를 정면으로 활용합니다. 테스트 케이스가 실패 신호를 주고, 에이전트가 그 신호를 보고 식의 어느 부분이 원인인지 좁혀 들어갑니다. 마치 초안을 내놓고 퇴고하는 글쓰기와 비슷합니다. 초벌 문장이 서툴러도 퇴고 과정이 탄탄하면 최종 문장은 꽤 좋아집니다. 물론 무한히 고친다고 계속 좋아지는 것은 아닙니다. 고치는 과정에서 새로운 실수를 끼워 넣을 수도 있고, 테스트 케이스에 과하게 맞춘 식이 될 수도 있습니다. 그래서 저는 이 결과를 이렇게 읽었습니다. 자기 수정이 만능이라서가 아니라, QUBO처럼 검증 가능한 중간 형태가 있을 때는 고치는 고리가 특히 잘 맞는다는 이야기로 말이죠.

백 문제를 열두 개 분야로 나눠 물어보면 무슨 일이 생길까

그렇다면 평가는 어떻게 해야 할까요. 연구팀은 QUBOBench라는 새로운 벤치마크를 함께 내놓았습니다. 문헌과 경진대회, 계산 복잡도 이론에서 잘 알려진 어려운 문제들을 모아 100개의 조합 최적화 문제로 엮었고, 열두 개의 응용 분야에 걸쳐 배치했다고 합니다. 저는 이 구성이 꽤 정직하다고 느꼈습니다. 한두 개의 익숙한 문제만 골라 잘 나오는 숫자를 보여주는 대신, 분야를 넓혀서 일반화 능력을 묻겠다는 태도이기 때문입니다.

벤치마크가 넓으면 좋은 점이 있습니다. 특정 분야의 문장 패턴에만 과적합된 시스템은 다른 분야로 넘어가는 순간 티가 납니다. 예를 들어 스케줄링 문제에서는 잘 맞던 변수 정의 방식이, 그래프 문제에서는 전혀 안 통할 수 있죠. 열두 개 분야라는 말은 곧 열두 가지 말투와 열두 가지 제약 스타일을 견뎌야 한다는 뜻입니다. 반면 넓은 벤치마크는 해석할 때 조심할 점도 만듭니다. 100이라는 문제 수가 적지 않지만, 분야별로 나누면 한 분야당 열 문제도 안 되는 셈이라 분야별 강약을 단정하기는 어렵습니다. 그래서 저는 QUBOBench를 분야별 성적표라기보다 체력장에 가깝다고 봅니다. 어디가 약한지 찍어주는 진단서라기보다, 전반적인 전환 능력이 어느 수준인지 보여주는 시험대라는 것이죠. (참고로 데이터와 코드는 프로젝트 페이지로 공개되어 있다고 하니, 재현해보고 싶은 분들은 원문 아래 연결된 자료부터 확인하시면 됩니다.)

68퍼센트라는 숫자를 어떻게 읽어야 할까

이제 숫자를 들여다볼 차례입니다. 논문에 따르면 이 프레임워크는 QUBOBench에서 68퍼센트 정확도를 달성했고, 직접 한 번에 생성하는 방식보다는 22퍼센트 높았다고 합니다. 표면적으로 보면 단순한데, 열 문제 중 일곱 문제 가까운 정식화를 맞췄고 한 번에 쓰는 것보다는 분명히 낫다는 것이죠. 그런데 이 숫자는 그대로 믿기 전에 조건을 봐야 합니다. 정확도의 정의가 무엇인지에 따라 같은 68이라도 느낌이 달라지기 때문입니다.

제가 주목한 것은 정식화 정확도라는 말의 무게입니다. 답을 맞췄다는 말이 아니라, 문제를 푸는 식을 제대로 만들었다는 뜻이기 때문입니다. 식이 맞으면 뒤에 오는 솔버가 양자 방식이든 고전 방식이든 제 역할을 할 수 있습니다. 반대로 식이 틀리면 뒤단 솔버가 아무리 좋아도 소용이 없습니다. 출발점이 틀렸으니까요. 이런 점에서 68퍼센트는 절반을 겨우 넘는 점수가 아니라, 자동화의 출발선으로 읽힙니다. 사람이 손으로 쓰던 식의 3분의 2 정도를 기계가 대신 만들 수 있게 됐다는 신호니까요. 물론 나머지 32퍼센트가 그냥 오답으로 끝나면 현장에서는 쓰기 어렵습니다. 틀린 식을 걸러내는 장치가 함께 있어야 한다는 뜻이죠. 여기서 다시 테스트 케이스와 자기 수정이 중요해집니다. 68이라는 숫자 자체보다, 틀렸을 때 스스로 알아차릴 수 있는지 여부가 실제 도입을 가른다고 저는 봅니다.

그리고 22퍼센트라는 격차도 가볍게 넘길 일이 아닙니다. 같은 언어 모델을 쓰면서도 호출을 나누고 고치는 과정을 넣었을 뿐인데, 스무 문제 이상이 추가로 맞았다는 뜻이기 때문입니다. 모델을 키우는 대신 과정을 바꾼 것만으로 이 정도 차이가 난다면, 앞으로의 개선 여지는 모델 크기 바깥에 있다는 이야기가 됩니다. 저희가 새로운 AI 구조를 볼 때도 모델 이름만 보지는 않습니다. 실제로 무엇이 바뀌었고, 그 변화가 전체 파이프라인에서 어떤 비용과 정확도 교환을 만드는지를 함께 봅니다. 이 논문도 같은 잣대로 보면 됩니다. 호출 횟수는 늘었지만, 한 번에 쓰고 버리는 식보다는 훨씬 쓸모 있는 식이 남는다는 것이죠.

숫자가 아니라 구조를 봐야 하는 이유

여기서는 조금 조심해서 읽을 필요가 있습니다. 68퍼센트라는 숫자가 크다고 해서, 이제 QUBO 전문가가 필요 없어졌다고 말할 수는 없기 때문입니다. 벤치마크에 들어간 100문제는 연구와 경진대회에서 잘 다듬어진 문제들이고, 문장도 비교적 정돈되어 있을 가능성이 큽니다. 그런데 현장의 문장은 그렇지 않습니다. 같은 말을 다르게 하고, 중요한 조건을 빼먹고, 서로 모순되는 요구를 함께 적기도 하죠. 잘 정돈된 문제에서 68퍼센트라면, 지저분한 현장 문장에서는 숫자가 내려갈 수 있습니다. 이 간극을 메우는 것이 다음 연구의 몫이라고 봅니다.

또 하나 짚고 싶은 것은 양자 솔버와의 관계입니다. 논문은 QUBO가 양자와 하이브리드, 양자 영감 솔버와 잘 맞는 형식이라는 점을 배경으로 깔고 있습니다. 이 설명은 맞습니다. QUBO는 실제로 그런 솔버들로 넘기기 좋은 공용어에 가깝기 때문입니다. 그런데 공용어가 있다고 해서 뒤단의 풀이가 저절로 쉬워지는 것은 아닙니다. 식을 잘 만들었다고 해서 큰 문제를 양자 하드웨어가 곧바로 풀 수 있는 것은 아니고, 문제 크기와 연결 구조, 하드웨어 제약 같은 현실적인 벽이 여전히 남습니다. 그래서 저는 이 논문의 기여를 이렇게 정리했습니다. 양자 풀이 자체를 앞당겼다기보다, 양자 풀이로 가기 전의 번역 병목을 줄였다는 것이죠. 번역이 빨라지면 더 많은 문제를 솔버까지 데려갈 수 있고, 솔버 연구도 더 다양한 입력으로 시험받을 수 있습니다. 파이프라인의 앞단이 넓어지면 뒷단의 연구도 덩달아 빨라지는 구조인데요. 이런 앞단 넓히기가 쌓이면 전체 분야의 속도가 달라집니다.

그렇다면 사람의 역할은 어디로 옮겨갈까

마지막으로 제가 앞으로 보고 싶은 것을 적어보겠습니다. 첫째는 가중치 선택의 자동화가 어디까지 갈 수 있는지입니다. 페널티 가중치는 지금도 경험과 시행착오에 기대는 부분이 큰데, 테스트 케이스만으로 매번 적절한 값을 찾을 수 있을지 궁금합니다. 둘째는 실패 사례의 모양입니다. 나머지 32퍼센트는 변수 정의에서 틀린 것인지, 제약 해석에서 틀린 것인지, 아니면 문장 자체가 모호해서 누구라도 틀릴 수밖에 없는 것인지가 궁금하죠. 실패의 종류가 나뉘면 다음에 고칠 곳도 분명해집니다. 셋째는 현장 문장에 대한 내성입니다. 모순되거나 불완전한 설명이 들어왔을 때, 시스템이 조용히 엉뚱한 식을 내놓는 대신 어디가 모호한지 되물을 수 있을까요. 그 이야기는 아마 다음 연구에서 다시 다뤄질 것 같습니다.

처음에 저는 QUBO 자동화를 양자 컴퓨팅의 먼 이야기로 생각했습니다. 그런데 글을 따라가다 보니 오히려 당장 옆의 이야기에 가깝다는 느낌이 들었습니다. 문장으로 된 요구를 컴퓨터가 풀 수 있는 형태로 바꾸는 일은 스케줄 짜기, 경로 정하기, 자원 나누기처럼 우리 주변에 이미 널려 있기 때문입니다. 이 번역이 빨라지고 정확해질수록, 최적화는 전문가의 전유물에서 현장의 도구에 가까워집니다. 그렇다면 사람의 역할은 무엇일까요. 저는 식을 한 줄씩 손으로 쓰는 일보다는, 어떤 제약을 정말 지켜야 하고 어떤 목표를 진짜로 낮춰야 하는지 정하는 일로 옮겨갈 거라고 봅니다. 기계가 식을 쓰는 시대일수록 무엇을 풀어야 하는지 묻는 사람의 질문이 더 중요해지니까요.