이 작업은 유형에 따라 2만–9만 개 문항을 배치 생성하고, 같은 생성 로직을 실시간 서비스에도 사용하던 수능 영어 문항 생성·검증 시스템의 일부였습니다.
기존 시스템은 지문마다 미리 생성한 정답·오답 선택지를 조합해 서로 중복되지 않는 문항을 여러 개 만들도록 설계돼 있었습니다. 그러나 제가 생성된 문항을 점검하면서 같은 정답·오답 선택지 조합을 여러 문항에 반복 사용하는 버그를 발견했습니다. 예를 들어 두 번째 문항에는 새로운 선택지를 섞어야 하는데, 실제로는 첫 문항과 같은 다섯 선택지로 옳은 것과 틀린 것을 묻고 있었습니다.
그 결과 유효 문항이 기존 수준의 절반가량인 약 4만 개로 줄어 목표에 크게 못 미쳤습니다. 전체 배치 생성에 이미 누적 수천만원대의 LLM 비용이 들어간 상황이라, 부족분을 새로 생성하는 방식은 비용과 검수 부담과 토큰 비용을 다시 늘리는 선택이었습니다.
문제 정의
선택지를 더 만드는 대신 이미 검수한 선택지의 조합을 최대화하는 문제로 다시 정의했습니다. 유효한 문항은 다음 조건을 모두 지켜야 했습니다.
- 두 선택지는 정해진 글자 수 이상 달라야 한다.
- 한 번 사용한 선택지는 이후 최대 두 번까지만 재사용한다.
- 세 선택지가 동일한 순서로 다시 나타나는 조합은 허용하지 않는다.
알고리즘 선정
처음 검토한 그리디 방식은 가능한 모든 조합을 계산하는 구조였고, 지문당 선택지의 개수가 일정 수준을 넘으면 경우의 수가 급격히 커졌습니다. 그래서 큰 입력에는 최적 조합을 보장하지 않더라도 빠르게 해를 찾는 랜덤 그리디가 대안이 됐습니다. 저는 이와 별도로 문제를 정수계획법으로 풀어 보았고, 관리 가능한 규모에서는 제약을 모두 만족하는 최적해를 현실적인 시간 안에 찾을 수 있었습니다.
하나의 지문에서 일정 개수 이상의 문항을 만드는 것은 적절하지 않다는 내용을 콘텐츠팀에 확인한 뒤, 선택지가 50개 미만이면 정수계획법을, 일정 개수 이상이면 랜덤 그리디를 적용했습니다. 조합 규칙과 중복 제거는 문항생성 파이프라인에 연결해 기존 데이터 흐름 안에서 반복 실행할 수 있게 했습니다.
결과
새 선택지를 추가 생성하지 않고 최종 유효 문항을 약 9만 개까지 복구했습니다. 약 4만 개에서 새로 2배 넘는 성장을 만든 것이 아니라, 버그 이전 수준에 가까운 산출량을 되찾은 결과입니다. LLM은 선택지 생성에, 제약 기반 조합 알고리즘은 조합 규칙에 맡겨 이미 검수한 데이터의 활용 범위를 회복했습니다.