LLM은 그래프에서 최단 경로를 학습할 수 있다——하지만 작업 지평선이 늘어나면 실패한다

무엇을 테스트했습니까?

연구원 Tong, Ye, Borovykh, Shokri는 arXiv에 논문을 발표하여 LLM이 고전적인 알고리즘 문제——그래프에서 최단 경로 찾기——에서 체계적 일반화를 달성할 수 있는지를 체계적으로 분석했습니다. 테스트는 일반화의 두 가지 독립적 차원을 다뤘습니다:

1. 공간적 전이 — 특정 그래프 집합에서 훈련한 모델이 다른 토폴로지를 가진 미지의 맵에서 문제를 해결할 수 있습니까?
2. 지평선 길이 스케일링 — 더 짧은 경로(예: 5-10단계)에서 훈련한 모델이 더 긴 경로(50단계 이상)를 올바르게 해결할 수 있습니까?

이 방법론은 표준 벤치마크 유형보다 의도적으로 더 광범위합니다——질문이 새로운지 여부뿐만 아니라 요구사항이 모델이 훈련에서 본 것보다 구조적으로 더 어려운지를 측정합니다.

무엇을 발견했습니까?

결과는 일관적이고 주목할 만합니다:

• 공간적 전이: 성공적. 그래프 집합에서 경로 찾기를 배운 모델은 동일한 크기의 미지의 토폴로지에 성공적으로 일반화합니다. 이는 어느 정도 「알고리즘을 학습」하는 것이 가능하다는 것을 의미합니다.

• 길이 스케일링: 지속적인 실패. 경로 길이가 훈련 범위를 넘어 확장되면 모델은 재귀적 불안정성으로 인해 실패합니다——한 단계의 작은 오류가 끝까지 지수적으로 누적됩니다.

세 가지 개입도 추가로 테스트되었습니다:

• 데이터 커버리지가 능력 경계를 정의합니다 — 모델은 훈련에서 본 것을 알고 있으며, 그것을 넘어서는 스케일링은 작동하지 않습니다.
• RL(강화 학습)은 훈련 범위 내에서 안정성을 개선하지만 일반화 경계를 확장하지 않습니다.
• 추론 시 스케일링(더 많은 토큰 예산, 사고의 연쇄)은 도움이 되지만 기본적인 길이 스케일링 문제를 해결하지 못합니다.

왜 이것이 자율 에이전트에게 중요합니까?

많은 실용적인 에이전트 작업은 긴 지평선을 필요로 합니다: 멀티스텝 계획, 연구, 수일에 걸친 소프트웨어 엔지니어링 프로젝트, 복잡한 시스템의 반복적 디버깅. LLM이 구조적으로 길이로 스케일할 수 없다면——이 논문이 시사하는 것처럼——에이전트의 자율성은 훈련에서 본 문제 크기에 의해 근본적으로 제한됩니다.

이는 이전 발견과 일치합니다(예: LongCoT 벤치마크에서 GPT가 긴 사고의 연쇄 추론에서 9.8% 달성): 겉으로는 가장 강력한 모델들도 문제가 길어지면 무너집니다.

실제로 무엇을 의미합니까?

연구원들은 문제가 해결 불가능하다고 주장하지 않지만 세 가지 불가피한 진실을 식별합니다:

1. 합성 데이터셋 커버리지는 명시적으로 긴 경로를 포함해야 합니다——그렇지 않으면 모델은 그것을 처리하는 방법을 결코 알 수 없습니다.
2. RL과 추론 시 스케일링은 만병통치약이 아닙니다 — 모델이 이미 학습한 것을 개선하지만 새로운 체계적 능력을 추가하지 않습니다.
3. 아키텍처 변경(계층적 에이전트, 명시적 상태 관리가 있는 계획)이 진정한 길이 일반화에 필요할 수 있습니다.

AI 뉴스 독자에게 결론은: 다음에 모델이 「자율 연구 프로젝트를 수행한다」는 내용을 읽을 때, 그 지평선이 실제로 얼마나 깊은지, 그리고 문제가 해당 모델의 훈련 범위 내에 있는지 밖에 있는지 묻는 것이 중요합니다.