RayFST

RayFST composes two weighted finite-state transducers (FSTs) by encoding arcs as sphere primitives and using NVIDIA OptiX ray traversal to find matching labels.

Requirements

• Linux with a CUDA-capable NVIDIA GPU
• Python 3.10 or newer
• CUDA Toolkit 12.x
• NVIDIA OptiX SDK 9.x
• A recent NVIDIA driver supported by the selected OptiX release

The OptiX SDK is an external dependency and is not vendored in this repository. Download it from the NVIDIA OptiX page. The Python binding is provided by NVIDIA PyOptiX.

Create an environment and install RayFST:

python3 -m venv .venv
source .venv/bin/activate
python -m pip install -e .

Point RayFST to the CUDA and OptiX headers:

export CUDA_INCLUDE_DIR=/usr/local/cuda/include
export OPTIX_INCLUDE_DIR=/path/to/NVIDIA-OptiX-SDK/include

Run the included example

rayfst \
  --left-fst examples/small/left.fst \
  --left-input-symbols examples/small/left.isyms \
  --left-output-symbols examples/small/inner.syms \
  --right-fst examples/small/right.fst \
  --right-input-symbols examples/small/inner.syms \
  --right-output-symbols examples/small/right.osyms \
  --output composed.fst

The result is written in OpenFST text format. Run rayfst --help for scheduling and capacity options.

Input format

FST files use the OpenFST text representation:

source destination input_label output_label [weight]
final_state [final_weight]

Symbol tables contain one symbol and numeric id per line:

<epsilon> 0
token 1

The left output-symbol table and right input-symbol table must contain the same symbols with the same numeric ids. State 0 is treated as the start state. RayFST currently writes final weights as zero.

Python API

from rayfst import ComposeOptions, compose_files

result = compose_files(
    left_fst="examples/small/left.fst",
    left_input_symbols="examples/small/left.isyms",
    left_output_symbols="examples/small/inner.syms",
    right_fst="examples/small/right.fst",
    right_input_symbols="examples/small/inner.syms",
    right_output_symbols="examples/small/right.osyms",
    options=ComposeOptions(dense_rays=2),
)

For unusually large compositions, set worklist_capacity and output_capacity explicitly. These buffers are allocated on the GPU before composition.