Infini-gram: Scaling Unbounded n-gram Language Models to a Trillion Tokens

Meta info.

• Authors: Jiacheng Liu, Sewon Min, Luke Zettlemoyer, Yejin Choi, Hannaneh Hajishirzi
• Paper: https://arxiv.org/pdf/2401.17377.pdf
• Affiliation: Allen Institute., UW
• Code: https://github.com/liujch1998/infini-gram
• References: X post, infini-gram HF

TL; DR

∞-n과 조단위 token corpus로 n-gram 쿼리를 효율적으로 처리하는 infini-gram 공개

Suggestion

• ∞-gram LM: infini-gram 엔진 활용하여, effective n을 설정 (pic2)

Effect

ive n: 예측에 사용되는 prompt’s suffix length. 가능한 가장 긴 context로 즉 count가 0이 되기 직전의 n.

• infini-gram index: n-gramcount tables을 미리 계산하지 않고, suffix array로 구동 (pic3)
• ∞-gram으로 interpolate하면 LLM 복잡도 최대 73% 감소 (Llama-2- 70B)
• RedPajama(1.4T)에서 임의의 (n이 얼마나 큰지랑 상관 없이) long n-gram 의 빈도 계산해서 corpus에서 그 출현 위치를 retrieve 하는데에 0.02초(!)
• n-gram LM probability estimation & decoding도 쿼리당 0.04초이내(!)
  • ∞-gram 이면 조금 더 걸리긴 하지만 0.2 이내
• Application
  • token-wise agreement btw ∞-gram’s estimate and actual human written text
  • ∞-gram LM의 human-written text에 대한 prediction 정확도가 47% 수준(pic3 middle)으로 상당히 높고 (pic3 left의 5-gram 기준 29% 대비), 즉 긴 context를 줄 때 LM 성능이 더 좋아질 수 있음을 시사
  • “training data에 따라, next token이 unique하다면, 그 unique token이 actual human-written token일 가능성이 높다.”
• ∞-gram vs LLM agreement
  • ∞-gram과 LLM은 next token을 prediction할 때 서로 다른 token을 생성하는 경향이 있는데,
  • 특히 plot들 좌측이 LM은 gold token의 확률을 0으로 보지만, n-gram agreement는 상당히 높은 것을 확인. (pic5)
  • 앞선 결과와 종합하면 ∞-gram 의 human-written text agreement가 높으므로, LM 생성시 이를 보간할 때 더 나은 성능 가능.