A few weeks ago I released Optiverse, an open-source implementation of DeepMind's AlphaEvolve.

My first experiment was a classic optimization problem: the Traveling Salesman Problem (TSP). After exploring TSP, I wanted to test Optiverse on a more low-level and performance-critical problem. For my second experiment, I worked on compressing sorted integers.

In search engines, searching for a word returns a list of document IDs (integers) that are naturally sorted in increasing order to make processing faster. These integers must be stored and accessed efficiently.

I decided to try this in Go.

In the end, it produced a state-of-the-art implementation better than several C implementations, though not better than the very best ones.

The full code is available in the Optiverse repo: https://github.com/larose/optiverse/tree/main/examples/integer_compression

Problem Description

Here's the exact problem and constraints I gave to Optiverse:

Design and implement a compression algorithm for sorted 32-bit unsigned integers in Go by completing the two function stubs provided below.

Your primary goal is to achieve the lowest possible decompression time while also maintaining a competitive compression ratio and reasonable compression time.

To be competitive, your solution must surpass traditional methods like Variable Byte (VByte), PForDelta, and VTEnc. Drawing inspiration from these or related techniques is allowed, but mere reimplementation is insufficient. True innovation is required.

You are encouraged to explore novel approaches based on well-known general patterns, including but not limited to:

• Delta Encoding and Delta-of-Delta
• Bit-Packing and Frame-of-Reference
• Headerless or Self-Describing Formats
• Table-Driven and SIMD-Accelerated Decoding
• Block-based or chunked compression with skippable blocks

Requirements

Implement the following two functions with these exact signatures:

func Compress(data []uint32) []byte
func Decompress(compressed []byte) []uint32

You may define additional package-level helper functions (no nested functions).

Use only the Go Standard Library. Third-party packages are not allowed.

The use of built-in compression libraries (compress/gzip, flate, zlib, lzw, etc.) is strictly prohibited.

The output of Decompress(Compress(data)) must exactly match the original data.

You may assume that:

• The input to Compress (data) is valid and strictly increasing.
• The input to Decompress (compressed) is valid and was produced by a correct call to Compress.

What the LLM Discovered

As you can see, I prompted the LLM to go beyond traditional approaches, and I even suggested SIMD (Single Instruction, Multiple Data), a form of parallelism offered by the CPU for free. But since Go lacks built-in SIMD support and I didn't allow third-party libraries, it didn't go that route.

That said, to be truly competitive, SIMD would likely have been necessary.

What it did produce is a delta-based compression implementation, which is a core part of all state-of-the-art implementations. It takes advantage of the fact that compressing the deltas (i.e., differences) between sorted integers reduces space and improves speed. This works well because deltas are usually much smaller than the original integers, and smaller values require fewer bits to encode.

Building on this, the algorithm applies block-based encoding with bit-packing. Here's how it works:

• Divide the deltas into fixed-size blocks.
• For each block, find the maximum delta.
• Compute how many bits are needed to represent that max delta.
• Encode each delta in the block using that fixed bit width.

You'll find the full Go implementation in the appendix.

Benchmark Results

I compared the Go implementation generated by Optiverse against a few C implementations using this benchmark.

(Higher = better on both metrics)

CPU: Intel Core i5-6500T @ 2.50GHz

Conclusion

This experiment showed how capable LLMs can be when guided right. Even though it didn’t find a new algorithm, Optiverse came up with a fast, practical solution by trying known ideas like delta encoding and bit packing. It probably tried some bad or made up ideas, but the process filtered those out and kept what worked. In that way, it acted like an agent, trying things and learning as it went.

Appendix

Full Go Implementation

This solution was discovered after ~1000 iterations using Qwen3-235B-A22B with Optiverse.

package main

import (
	"encoding/binary"
	"math/bits"
)

const blockSize = 128

func Compress(data []uint32) []byte {
	if len(data) == 0 {
		return nil
	}

	compressed := make([]byte, 8)
	binary.LittleEndian.PutUint32(compressed[0:4], data[0])
	if len(data) == 1 {
		return compressed[:4]
	}

	deltas := make([]uint32, len(data)-1)
	for i := range deltas {
		deltas[i] = data[i+1] - data[i]
	}
	binary.LittleEndian.PutUint32(compressed[4:8], uint32(len(deltas)))

	pos := 8
	for i := 0; i < len(deltas); i += blockSize {
		end := i + blockSize
		if end > len(deltas) {
			end = len(deltas)
		}
		block := deltas[i:end]

		maxDelta := uint32(0)
		for _, d := range block {
			if d > maxDelta {
				maxDelta = d
			}
		}

		bitsPerDelta := 0
		if maxDelta > 0 {
			bitsPerDelta = bits.Len32(maxDelta)
		}
		bytesPerDelta := 0
		if bitsPerDelta > 0 {
			bytesPerDelta = (bitsPerDelta + 7) / 8
		}

		if pos+1 > cap(compressed) {
			newCap := cap(compressed) * 2
			if newCap == 0 {
				newCap = 64
			}
			newBuf := make([]byte, len(compressed), newCap)
			copy(newBuf, compressed)
			compressed = newBuf
		}
		compressed = compressed[:pos+1]
		compressed[pos] = byte(bytesPerDelta)
		pos++

		if bytesPerDelta == 0 {
			continue
		}

		packedBytes := len(block) * bytesPerDelta
		if pos+packedBytes > cap(compressed) {
			newCap := cap(compressed)
			for newCap < pos+packedBytes {
				newCap *= 2
			}
			newBuf := make([]byte, len(compressed), newCap)
			copy(newBuf, compressed)
			compressed = newBuf
		}
		compressed = compressed[:pos+packedBytes]

		idx := 0
		switch bytesPerDelta {
		case 1:
			for _, d := range block {
				compressed[pos+idx] = byte(d)
				idx++
			}
		case 2:
			for _, d := range block {
				binary.LittleEndian.PutUint16(compressed[pos+idx:pos+idx+2], uint16(d))
				idx += 2
			}
		case 3:
			for _, d := range block {
				compressed[pos+idx] = byte(d)
				compressed[pos+idx+1] = byte(d >> 8)
				compressed[pos+idx+2] = byte(d >> 16)
				idx += 3
			}
		case 4:
			for _, d := range block {
				binary.LittleEndian.PutUint32(compressed[pos+idx:pos+idx+4], d)
				idx += 4
			}
		}

		pos += packedBytes
	}

	return compressed[:pos]
}

func Decompress(compressed []byte) []uint32 {
	if len(compressed) < 8 {
		if len(compressed) < 4 {
			return []uint32{}
		}
		first := binary.LittleEndian.Uint32(compressed[0:4])
		return []uint32{first}
	}

	first := binary.LittleEndian.Uint32(compressed[0:4])
	numDeltas := binary.LittleEndian.Uint32(compressed[4:8])
	totalLen := int(numDeltas) + 1
	result := make([]uint32, totalLen)
	if totalLen == 1 {
		return result[:1]
	}

	result[0] = first
	pos := 8
	remaining := int(numDeltas)
	prev := first
	currentIdx := 1

	for remaining > 0 {
		bytesPerDelta := int(compressed[pos])
		pos++

		blockSizeCurrent := blockSize
		if remaining < blockSize {
			blockSizeCurrent = remaining
		}
		packedBytes := blockSizeCurrent * bytesPerDelta

		switch bytesPerDelta {
		case 0:
			end := currentIdx + blockSizeCurrent
			value := prev
			for i := currentIdx; i < end; i++ {
				result[i] = value
			}
			currentIdx = end

		case 1:
			p := pos
			endp := pos + blockSizeCurrent
			for p < endp {
				d := uint32(compressed[p])
				prev += d
				result[currentIdx] = prev
				currentIdx++
				p++
			}

		case 2:
			p := pos
			endp := pos + 2*blockSizeCurrent
			for p < endp {
				d := uint32(binary.LittleEndian.Uint16(compressed[p:]))
				prev += d
				result[currentIdx] = prev
				currentIdx++
				p += 2
			}

		case 3:
			p := pos
			endp := pos + 3*blockSizeCurrent
			for p < endp {
				d := uint32(compressed[p]) | (uint32(compressed[p+1]) << 8) | (uint32(compressed[p+2]) << 16)
				prev += d
				result[currentIdx] = prev
				currentIdx++
				p += 3
			}

		case 4:
			p := pos
			endp := pos + 4*blockSizeCurrent
			for p < endp {
				d := binary.LittleEndian.Uint32(compressed[p:])
				prev += d
				result[currentIdx] = prev
				currentIdx++
				p += 4
			}
		}

		remaining -= blockSizeCurrent
		pos += packedBytes
	}

	return result
}