[Feature] support for Infini-gram index

[artemru]

The infini-gram index system appears to be very useful for many LLM analysis related application and it would be useful to support it natively as lance index !

Some references :
https://github.com/liujch1998/infini-gram
https://export.arxiv.org/pdf/2401.17377v4
https://arxiv.org/pdf/2504.07096

[hpvd]

thanks for pointing to this. Sounds really interesting!

[BubbleCal]

This looks interesting!

My understanding is that the infini-gram index is based on suffix array because it needs the ability to perform 2 queries:

• count substring
• find substring position

Both are supported today by ngram-index in lance, but I can imagine ngram-index may be not good for long substring query

@artemru Could you tell more about your use cases? And:

• How long is the substring
• How large is the dataset
• What's the expected search latency

[artemru]

@BubbleCal, thanks for your interest !

my basic use case is very similar to what is described in https://arxiv.org/pdf/2504.07096 (a retro engineering of LLM results with different llm systems and reference datasets that I'm playing around).

I want to index large scale corpora such as fineweb-2 or dclm.
For queries, typical input will be around 200 - 500 tokens (at least for english texts).
At that point, I dont need to get super fast latency (it's mostly offline usage), something below 400 ms / query will be good enough!

Currently, the ngrams indexing in lance does not really fit that use-case, it remains too slow for both in indexing and in query, I could not scale it up really.

[BubbleCal]

suffix array indexing would be slower AFAIK, but yeah agree it would be a better solution for long query and offline scenarios

[artemru]

Hi @BubbleCal, i did some vibe-coding implementation for this feature, it looks working ok when i tested it locally, would you be interested to consider it ?