BIS-1: A Biologically Inspired Search Engine Experiment
BIS-1, the Biological Immune Search Architecture, was another experimental search-engine architecture developed from biological principles.
The central idea was to investigate whether mechanisms analogous to biological immune search could inspire a computational system capable of searching a very large state space without retaining every possible state independently.
The experimental architecture followed four stages:
Rather than attempting to preserve every candidate equally, BIS-1 explored whether large numbers of search states could be screened, grouped, suppressed, and represented more compactly while still preserving the exact witness needed to solve a problem.
The experimental test problem was SUBSET SUM, where a search engine must determine whether some subset of a collection of positive integers sums exactly to a specified target.
BIS-1 was therefore not presented as a completed solution to SUBSET SUM. It was an experimental search architecture designed to answer a deeper question:
Can principles inspired by biological search reduce computational search states without destroying the information required to find an exact solution?
Experiment 2 provided an important answer.
The particular modular compression mechanism tested did not safely preserve witnesses when substantial compression occurred. This negative result did not invalidate the biological-search concept itself. Instead, it identified a boundary that a future biologically inspired search architecture would need to overcome.
The experiment suggested that simply making two states look similar is insufficient. A successful compression mechanism must preserve information about whether those states have equivalent useful futures.
That distinction became one of the most important lessons of the BIS-1 experiment.
An Experimental Journal on the Biological Immune Search Architecture
BIS-1, the Biological Immune Search Architecture, is an experimental approach to exact combinatorial search inspired by a simple question:
Can a search system reduce a very large collection of intermediate states while still preserving the information needed to recover an exact solution?
The architecture is organized around four conceptual operations:
Rather than treating every possible search state as equally important, BIS-1 investigates whether states can be grouped into compact representations while retaining the distinctions that matter for solving the problem.
The initial experimental problem is SUBSET SUM. Given positive integers a1, a2, …, an and a target T, the task is to determine whether some subset adds exactly to T. A valid subset is called a witness.
The difficulty is not simply generating candidate states. The deeper question is whether apparently similar states can safely be treated as equivalent.
Experiment 2: Compression Versus Witness Loss
Experiment 2 tested a modular-signature compression scheme. Instead of storing the complete residual value
for every partial search state, BIS-1 assigned residuals signatures constructed from their remainders modulo a sequence of prime numbers. States with the same signature could therefore be placed into the same class.
This creates a potential compression mechanism. If many exact states can be represented by a much smaller number of classes without destroying the solution, the search representation becomes substantially smaller.
But compression introduces a danger: Two states can look identical to the compressed representation while having different futures. One may still lead to the target while another may not.
Experiment 2 was designed specifically to measure that boundary.
Reading the Experiment 2 Graph
The horizontal axis shows: Mode R states kept ÷ exact states. Moving toward the left represents stronger compression because fewer representative states are being retained. Moving toward the right approaches the original exact-state representation.
The vertical axis shows: Planted witnesses lost (%). Lower values are therefore better. The ideal compression system would occupy the lower-left region of the graph: few states retained and few or no witnesses lost.
The experiment did not produce that behavior for the unrestricted n-bit test regime.
| Regime (n = 20) | Reported Parameter | Mode R States Kept ÷ Exact States | Planted Witnesses Lost |
|---|---|---|---|
| Unrestricted n-bit | Strong compression | ≈ 0.002 | 10 of 10 (100%) |
| Unrestricted n-bit | Strong compression | ≈ 0.006 | 10 of 10 (100%) |
| Unrestricted n-bit | Strong compression | ≈ 0.025 | 10 of 10 (100%) |
| Unrestricted n-bit | Moderate-strong compression | ≈ 0.125 | 9 of 10 (90%) |
| Unrestricted n-bit | Intermediate retention (≈ 54.2%) | ≈ 0.542 | 7 of 10 (70%) |
| Unrestricted n-bit | k = 6 | ≈ 0.952 | 1 of 10 (10%) |
| Unrestricted n-bit | k = 7 | 1.000 | 0 of 10 (0%) |
| Small-weight control | k = 3 (≈ 14.7% retained) | ≈ 0.147 | 0 of 10 (0%) — many unsafe buckets recorded |
For the n-bit instances at n = 20, strong compression corresponded to severe witness loss. At class-to-exact ratios of approximately 0.002, 0.006, and 0.025, all 10 of the 10 planted witnesses were lost. At a ratio of approximately 0.125, 9 of 10 were lost. Even when the representation retained approximately 54.2% as many classes as exact states, 7 of 10 planted witnesses were lost.
Only when the representation approached the exact-state count did witness preservation become reliable. At k = 6, the class-to-exact ratio was approximately 0.952 and 1 of 10 witnesses was still lost. At k = 7, the ratio reached 1.000 and no planted witnesses were lost.
That is the central experimental result. For these n-bit tests, the modular representation became safe only when it had effectively stopped compressing the exact states.
Why the Small-Weight Control Behaved Differently
The small-weight experiments produced an important contrast.
At n = 20 and k = 3, the compressed representation retained approximately 14.7% as many classes as the exact representation while losing none of the 10 planted witnesses. That initially looks like successful compression.
However, the experiment also recorded many unsafe buckets. The result therefore does not demonstrate that the merging rule was intrinsically safe. Instead, the small-weight instances contained sufficiently dense witness structure that a surviving route to a solution could remain even after other useful states were merged away.
This distinction is important. A compression system is not proven safe simply because a solution happens to survive. The stronger requirement is that the representation preserve the distinctions necessary for exact continuation.
What BIS-1 Discovered
The experiment produced a useful negative result. Simple modular similarity is not enough to establish future-search equivalence. Two residual states can share the same modular signature while having different continuation possibilities.
The experiment therefore redirects the BIS-1 investigation. The relevant question is no longer merely: How can many states be given the same compact signature?
The more important question becomes: What information determines whether two states have the same possible future?
That points toward continuation information, meaning information about which sums remain reachable from the items that have not yet been processed. Such information is much closer to the property an exact search engine actually needs.
Two Different Compression Modes
Experiment 2 also distinguished two fundamentally different approaches.
Mode R: Representative Search
Mode R keeps one genuine state from each signature class. Because every retained state corresponds to a genuine subset sum, this mode cannot manufacture a solution that does not exist. Its failure mode goes in the opposite direction: it can discard the state required for a valid witness. Consequently, Mode R can produce a false NO.
Mode S: Signature-Only Search
Mode S operates on modular classes themselves. This asks whether a subset reaches the target modulo M, rather than necessarily reaching the target as an integer. Its characteristic error therefore goes in the other direction. A modular match can exist even when the original exact integer solution does not. Mode S can consequently produce false YES results.
The distinction is useful because the two modes expose opposite consequences of information loss.
An Important Research Principle
BIS-1 illustrates a broader principle for search-engine design: Compression is useful only when the distinctions being removed are irrelevant to future decisions.
A representation can be extremely compact and still be computationally useless if the compression erases the distinction between a state that can eventually reach the target and a state that cannot. Conversely, an exact representation can preserve every distinction while providing little compression advantage.
The difficult region lies between these extremes. The goal is not compression alone. The goal is safe structural compression.
Current BIS-1 Checkpoint
Under Protocol v1.0, the modular-prime residual signatures tested by BIS-1 did not provide safe structural compression for the tested unrestricted n-bit SUBSET SUM instances through n = 20.
When the modular signatures substantially merged states, planted witnesses were lost. When witness loss disappeared, the representation had essentially returned to the exact-state count.
The experiment therefore rejects this particular modular-signature mechanism as the solution BIS-1 was looking for. It does not reject the larger biological-search concept.
Instead, it identifies a more precise requirement for the next architecture: A useful BIS compression rule must distinguish states according to the continuation information required to preserve exact search behavior. That requirement provides a much sharper direction for the next experiment.
Scientific Boundary
BIS-1 is an experimental search architecture, not a proof of a new computational-complexity result. The experiments do not establish that SUBSET SUM has a polynomial-time algorithm. They do not establish P = NP or P ≠ NP.
What the experiments provide is narrower and experimentally useful: a measured failure boundary for one proposed method of compressing exact search states.
Negative results of this kind matter. They tell us not merely that an idea failed, but where the information required for exactness appears to reside. And that may ultimately be the more interesting question: How little information can an exact search engine remember without forgetting the solution?