papers/hanzo-sparse-basis-routing/hanzo-sparse-basis-routing.tex

% Sparse-Basis Inverted Indexes and Part-Level Routing for Retrieval over Column Stores
\documentclass[11pt]{article}
\usepackage{../shared/hanzocover}
\usepackage{amsmath, amssymb, amsthm}
\usepackage{booktabs}
\usepackage{graphicx}
\usepackage{xcolor}
\usepackage{enumitem}
\usepackage{array}
\usepackage{listings}
\input{../shared/lstlang}
\usepackage{hyperref}
\hypersetup{colorlinks=true,linkcolor=black,citecolor=blue,urlcolor=blue}

% Status of every component, so a reader can tell what is established from what
% this paper proposes, without inferring it from the tone of a sentence.
\newcommand{\prior}{\textcolor{purple!70!black}{\small[prior art]}}
\newcommand{\proposed}{\textcolor{orange!70!black}{\small[proposed]}}
\newcommand{\meas}{\textcolor{blue!60!black}{\small[measured]}}

% Measured constants are read from results-data.tex, which the harness writes.
% A key that file does not define prints XXX, so a table cannot show a number
% that no run produced, and a number cannot drift from its measurement without
% the drift showing on the page.
\newcommand{\ph}{\textbf{XXX}}
\newcommand{\setres}[2]{\expandafter\def\csname res:#1\endcsname{#2}}
\newcommand{\res}[1]{\ifcsname res:#1\endcsname\csname res:#1\endcsname\else\ph\fi}
\input{results-data}

% One row of the cost table: the key prefix, then the label printed for it.
\newcommand{\costrow}[2]{#2 & \res{#1/parts} & \res{#1/granules} & \res{#1/mib}
  & \res{#1/bpc} & \res{#1/recall} & \res{#1/p50} & \res{#1/p99} \\}
% One row of the exponent table.
\newcommand{\fitrow}[2]{#2 & \res{fit/#1/parts} & \res{fit/#1/granules}
  & \res{fit/#1/mib} & \res{fit/#1/routing} \\}

\theoremstyle{definition}
\newtheorem{definition}{Definition}
\theoremstyle{plain}
\newtheorem{proposition}{Proposition}
\theoremstyle{remark}
\newtheorem{remark}{Remark}

\title{Sparse-Basis Inverted Indexes and Part-Level Routing\\
for Retrieval over Column Stores\\[0.35em]
{\large A design, its prior art, and a protocol for measuring\\
how retrieval cost grows with corpus size}}
\author{
    Hanzo AI Research\thanks{Corresponding author: [email protected]} \\
    \textit{Hanzo Industries Inc (Techstars '17)} \\
    San Francisco, California \\
    \texttt{https://hanzo.ai}
}
\date{Draft, 2026-09-22 \quad No measurements are reported in this version}

\begin{document}

\hanzocoverpage
\maketitle

\begin{abstract}
\noindent
We describe a retrieval design for a merge-based column store whose rows carry
sparse representations over a mixed basis --- words, entities, code symbols,
learned concepts, relations and structural motifs --- alongside dense
embeddings, and we specify how its cost is to be measured. The index is a
weighted inverted file: one posting list per basis element, holding a row
identifier and a weight, so a query written over the same basis is scored only
over the posting lists of the basis elements it activates, with top-$k$
evaluation under block-max pruning. Above it sits a routing structure built per
MergeTree part --- regions described by a centroid, a covering radius, the
maximum weight each basis element reaches inside the region, and counting
statistics --- aggregated into a table-level structure the planner consults to
exclude parts before any per-part index is searched, including the per-part
approximate-nearest-neighbour graph a column store already builds.

Most of the parts are established, and we say which. Weighted inverted files
with dynamic pruning, cluster- and shard-level routing by collection
statistics, covering-radius bounds from metric indexes, and per-segment vector
indexes are prior art. What is proposed here is their arrangement inside the
part lifecycle of a merge-based store: one weighted index over a heterogeneous
basis, block maxima aligned to granules, region summaries that merge when parts
merge, and selection of parts by an upper bound on the score they can still
contribute before any approximate search runs.

The claim we intend to test is narrow. At a fixed query distribution and a
fixed recall target, expected retrieval cost should grow with the size of the
relevant neighbourhood rather than with the size of the corpus. It is not a
worst-case guarantee: a query whose relevant set is the whole corpus costs time
linear in the corpus, under this design and under any other. The protocol fits
$C(N) = aN^{\alpha}$ to parts, granules and bytes touched at a held recall
target, and reports bytes fetched per correct answer, recall@$k$ and latency
percentiles across corpus sizes, against upstream ClickHouse as the baseline.
This version reports no measurements. The baseline lane is only starting, and
every cell in the results section is a placeholder until it writes one.
\end{abstract}

\input{sections/01-introduction}
\input{sections/02-setting}
\input{sections/03-index}
\input{sections/04-routing}
\input{sections/05-method}
\input{sections/06-results}
\input{sections/07-related}
\input{sections/08-limits}
\input{sections/99-conclusion}

{\small
\bibliographystyle{plain}
\bibliography{references}
}

\end{document}