„Indeks złożeniowy” (ang. assembly index) definiuje się jako najmniejszą liczbę kroków koniecznych do złożenia obiektu z części elementarnych i obiektów, które mogły istnieć w jego przeszłości, a przez to znalazły się w puli złożeniowej (ang. assembly pool). W przypadku takiej najkrótszej ścieżki przestrzeń złożeniowa odpowiada minimalnej pamięci, czyli minimalnej liczbie operacji niezbędnych do złożenia danego obiektu. Niezależnie od liczby części elementarnych, minimalny indeks złożeniowy obiektu składającego się z takich części jest zadany najkrótszym łańcuchem dodawania dla (sekwencja OEIS A003313). Maksymalny indeks złożeniowy zależy od liczby części elementarnych. Ponadto określanie indeksu złożeniowego jest problemem NP-zupełnym, ponieważ równa się on rozmiarowi najmniejszego programu liniowego (ang. straight-line program, SLP) generującego dany ciąg, co sprowadza jego wyznaczanie do problemu najmniejszej gramatyki. Algorytmy kompresji oparte na gramatykach dają zatem jedynie górne ograniczenia indeksu złożeniowego i nie są z nim równoważne.